Patent application number | Description | Published |
20090254516 | ACCESSING DATA IN A COLUMN STORE DATABASE BASED ON HARDWARE COMPATIBLE INDEXING AND REPLICATED REORDERED COLUMNS - Embodiments of the present invention provide hardware-friendly indexing of databases. In particular, forward and reverse indexing are utilized to allow for easy traversal of primary key to foreign key relationships. A novel structure known as a hit list also allows for easy scanning of various indexes in hardware. Group indexing is provided for flexible support of complex group key definition, such as for date range indexing and text indexing. A Replicated Reordered Column (RRC) may also be added to the group index to convert random I/O pattern into sequential I/O of only needed column elements. | 10-08-2009 |
20090254532 | ACCESSING DATA IN A COLUMN STORE DATABASE BASED ON HARDWARE COMPATIBLE DATA STRUCTURES - Embodiments of the present invention provide one or more hardware-friendly data structures that enable efficient hardware acceleration of database operations. In particular, the present invention employs a column-store format for the database. In the database, column-groups are stored with implicit row ids (RIDs) and a RID-to-primary key column having both column-store and row-store benefits via column hopping and a heap structure for adding new data. Fixed-width column compression allow for easy hardware database processing directly on the compressed data. A global database virtual address space is utilized that allows for arithmetic derivation of any physical address of the data regardless of its location. A word compression dictionary with token compare and sort index is also provided to allow for efficient hardware-based searching of text. A tuple reconstruction process is provided as well that allows hardware to reconstruct a row by stitching together data from multiple column groups. | 10-08-2009 |
20090254774 | METHODS AND SYSTEMS FOR RUN-TIME SCHEDULING DATABASE OPERATIONS THAT ARE EXECUTED IN HARDWARE - Embodiments of the present invention provide a run-time scheduler that schedules tasks for database queries on one or more execution resources in a dataflow fashion. In some embodiments, the run-time scheduler may comprise a task manager, a memory manager, and hardware resource manager. When a query is received by a host database management system, a query plan is created for that query. The query plan splits a query into various fragments. These fragments are further compiled into a directed acyclic graph of tasks. Unlike conventional scheduling, the dependency arc in the directed acyclic graph is based on page resources. Tasks may comprise machine code that may be executed by hardware to perform portions of the query. These tasks may also be performed in software or relate to I/O. | 10-08-2009 |
20090319486 | METHODS AND SYSTEMS FOR REAL-TIME CONTINUOUS UPDATES - Embodiments of the present invention provide fine grain concurrency control for transactions in the presence of database updates. During operations, each transaction is assigned a snapshot version number or SVN. A SVN refers to a historical snapshot of the database that can be created periodically or on demand. Transactions are thus tied to a particular SVN, such as, when the transaction was created. Queries belonging to the transactions can access data that is consistent as of a point in time, for example, corresponding to the latest SVN when the transaction was created. At various times, data from the database stored in a memory can be updated using the snapshot data corresponding to a SVN. When a transaction is committed, a snapshot of the database with a new SVN is created based on the data modified by the transaction and the snapshot is synchronized to the memory. When a transaction query requires data from a version of the database corresponding to a SVN, the data in the memory may be synchronized with the snapshot data corresponding to that SVN. | 12-24-2009 |
20090319550 | FAST BULK LOADING AND INCREMENTAL LOADING OF DATA INTO A DATABASE - Embodiments of the present invention provide for batch and incremental loading of data into a database. In the present invention, the loader infrastructure utilizes machine code database instructions and hardware acceleration to parallelize the load operations with the I/O operations. A large, hardware accelerator memory is used as staging cache for the load process. The load process also comprises an index profiling phase that enables balanced partitioning of the created indexes to allow for pipelined load. The online incremental loading process may also be performed while serving queries. | 12-24-2009 |
20100005077 | METHODS AND SYSTEMS FOR GENERATING QUERY PLANS THAT ARE COMPATIBLE FOR EXECUTION IN HARDWARE - Embodiments of the present invention generate and optimize query plans that are at least partially executable in hardware. Upon receiving a query, the query is rewritten and optimized with a bias for hardware execution of fragments of the query. A template-based algorithm may be employed for transforming a query into fragments and then into query tasks. The various query tasks can then be routed to either a hardware accelerator, a software module, or sent back to a database management system for execution. For those tasks routed to the hardware accelerator, the query tasks are compiled into machine code database instructions. In order to optimize query execution, query tasks may be broken into subtasks, rearranged based on available resources of the hardware, pipelined, or branched conditionally | 01-07-2010 |
20100082895 | MULTI-LEVEL CONTENT ADDRESSABLE MEMORY - A multi-level content addressable memory (CAM) architecture compresses out much of the redundancy encountered in the search space of a single CAM, particularly for flow-based lookups in a network. Destination and source address may be associated with internal equivalence classes independently in one level of the multi-level CAM architecture, while flow-specific properties linking arbitrary classes of the destination and source addresses may be applied in a later level of the multi-level CAM. | 04-01-2010 |
20110099155 | FAST BATCH LOADING AND INCREMENTAL LOADING OF DATA INTO A DATABASE - Embodiments of the present invention provide for batch and incremental loading of data into a database. In the present invention, the loader infrastructure utilizes machine code database instructions and hardware acceleration to parallelize the load operations with the I/O operations. A large, hardware accelerator memory is used as staging cache for the load process. The load process also comprises an index profiling phase that enables balanced partitioning of the created indexes to allow for pipelined load. The online incremental loading process may also be performed while serving queries. | 04-28-2011 |
20110167055 | HARDWARE ACCELERATED RECONFIGURABLE PROCESSOR FOR ACCELERATING DATABASE OPERATIONS AND QUERIES - Embodiments of the present invention provide a hardware accelerator that assists a host database system in processing its queries. The hardware accelerator comprises special purpose processing elements that are capable of receiving database query/operation tasks in the form of machine code database instructions, execute them in hardware without software, and return the query/operation result back to the host system. For example, table and column descriptors are embedded in the machine code database instructions. For ease of installation, the hardware accelerators employ a standard interconnect, such as a PCle or HT interconnect. The processing elements implement a novel dataflow design and Inter Macro-Op Communication (IMC) data structures to execute the machine code database instructions. The hardware accelerator may also comprise a relatively large memory to enhance the hardware execution of the query/operation tasks requested. The hardware accelerator utilizes hardware-friendly memory addressing, which allows for arithmetic derivation of a physical address from a global database virtual address simply based on a row identifier. The hardware accelerator minimizes memory reads/writes by keeping most intermediate results flowing through IMCs in pipelined and parallel fashion. Furthermore, the hardware accelerator may employ task pipelining and pre-fetch pipelining to enhance its performance. | 07-07-2011 |
20110167083 | HARDWARE ACCELERATED RECONFIGURABLE PROCESSOR FOR ACCELERATING DATABASE OPERATIONS AND QUERIES - Embodiments of the present invention provide a hardware accelerator that assists a host database system in processing its queries. The hardware accelerator comprises special purpose processing elements that are capable of receiving database query/operation tasks in the form of machine code database instructions, execute them in hardware without software, and return the query/operation result back to the host system. For example, table and column descriptors are embedded in the machine code database instructions. For ease of installation, the hardware accelerators employ a standard interconnect, such as a PCle or HT interconnect. The processing elements implement a novel dataflow design and Inter Macro-Op Communication (IMC) data structures to execute the machine code database instructions. The hardware accelerator may also comprise a relatively large memory to enhance the hardware execution of the query/operation tasks requested. The hardware accelerator utilizes hardware-friendly memory addressing, which allows for arithmetic derivation of a physical address from a global database virtual address simply based on a row identifier. The hardware accelerator minimizes memory reads/writes by keeping most intermediate results flowing through IMCs in pipelined and parallel fashion. Furthermore, the hardware accelerator may employ task pipelining and pre-fetch pipelining to enhance its performance. | 07-07-2011 |
20110218987 | HARDWARE ACCELERATED RECONFIGURABLE PROCESSOR FOR ACCELERATING DATABASE OPERATIONS AND QUERIES - Embodiments of the present invention provide a hardware accelerator that assists a host database system in processing its queries. The hardware accelerator comprises special purpose processing elements that are capable of receiving database query/operation tasks in the form of machine code database instructions, execute them in hardware without software, and return the query/operation result back to the host system. For example, table and column descriptors are embedded in the machine code database instructions. For ease of installation, the hardware accelerators employ a standard interconnect, such as a PCle or HT interconnect. The processing elements implement a novel dataflow design and Inter Macro-Op Communication (IMC) data structures to execute the machine code database instructions. The hardware accelerator may also comprise a relatively large memory to enhance the hardware execution of the query/operation tasks requested. The hardware accelerator utilizes hardware-friendly memory addressing, which allows for arithmetic derivation of a physical address from a global database virtual address simply based on a row identifier. The hardware accelerator minimizes memory reads/writes by keeping most intermediate results flowing through IMCs in pipelined and parallel fashion. Furthermore, the hardware accelerator may employ task pipelining and pre-fetch pipelining to enhance its performance. | 09-08-2011 |
20110246432 | ACCESSING DATA IN COLUMN STORE DATABASE BASED ON HARDWARE COMPATIBLE DATA STRUCTURES - Embodiments of the present invention provide one or more hardware-friendly data structures that enable efficient hardware acceleration of database operations. In particular, the present invention employs a column-store format for the database. In the database, column-groups are stored with implicit row ids (RIDs) and a RID-to-primary key column having both column-store and row-store benefits via column hopping and a heap structure for adding new data. Fixed-width column compression allow for easy hardware database processing directly on the compressed data. A global database virtual address space is utilized that allows for arithmetic derivation of any physical address of the data regardless of its location. A word compression dictionary with token compare and sort index is also provided to allow for efficient hardware-based searching of text. A tuple reconstruction process is provided as well that allows hardware to reconstruct a row by stitching together data from multiple column groups. | 10-06-2011 |
20130268489 | METHODS AND SYSTEMS FOR REAL-TIME CONTINUOUS UPDATES - Embodiments of the present invention provide fine grain concurrency control for transactions in the presence of database updates. During operations, each transaction is assigned a snapshot version number or SVN. A SVN refers to a historical snapshot of the database that can be created periodically or on demand. Transactions are thus tied to a particular SVN, such as, when the transaction was created. Queries belonging to the transactions can access data that is consistent as of a point in time, for example, corresponding to the latest SVN when the transaction was created. At various times, data from the database stored in a memory can be updated using the snapshot data corresponding to a SVN. When a transaction is committed, a snapshot of the database with a new SVN is created based on the data modified by the transaction and the snapshot is synchronized to the memory. When a transaction query requires data from a version of the database corresponding to a SVN, the data in the memory may be synchronized with the snapshot data corresponding to that SVN. | 10-10-2013 |
20140089632 | DIVISION OF NUMERICAL VALUES BASED ON SUMMATIONS AND MEMORY MAPPING IN COMPUTING SYSTEMS - Divisions by numbers that are not divisible by two (2) can be performed in a computing system based on a summation that estimates and/or approximates the reciprocal of the dividing number or denominator value. By way of example, dividing by three (3) can be calculated based on a summation that approximates or estimates one third (⅓) represented as the sum of a selected group of the inverses of the powers of two (2) in a pattern, namely the sum of: ¼, 1/16, 1/64, 1/256, . . . ). Applications of the division techniques are virtually unlimited and include memory mapping of global memory addresses to memory channel addresses by dividing a global memory address into the number of memory channels, allowing memory mapping to be performed in an efficient manner even for large memory spaces using a number of memory channels that are not divisible by two, including prime numbers. | 03-27-2014 |
20140324821 | ACCESSING DATA IN A COLUMN STORE DATABASE BASED ON HARDWARE COMPATIBLE INDEXING AND REPLICATED REORDERED COLUMNS - Embodiments of the present invention provide hardware-friendly indexing of databases. In particular, forward and reverse indexing are utilized to allow for easy traversal of primary key to foreign key relationships. A novel structure known as a hit list also allows for easy scanning of various indexes in hardware. Group indexing is provided for flexible support of complex group key definition, such as for date range indexing and text indexing. A Replicated Reordered Column (RRC) may also be added to the group index to convert random I/O pattern into sequential I/O of only needed column elements. | 10-30-2014 |
20150055391 | DESIGNATED MEMORY SUB-CHANNELS FOR COMPUTING SYSTEMS AND ENVIRONMENTS - A memory channel can be divided into two or more memory sub-channels, wherein each one of the memory sub-channels includes two or more memory components configured to store data made accessible on that memory sub-channel, and wherein the two or more memory components in each one of the memory sub-channels are respectively connected via at least one transmission line and can be individually accessed (addressed) on their associated sub-channel. | 02-26-2015 |