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.
1. A method of relating data across tables in a column-store database, said method comprising:
determining a row identifier of a first tuple in a first table based on identifying a token for a group of data in the first tuple, wherein the token comprises a sequence of characters surrounded by at least one delimiter in the group of data;
reading an index at a row corresponding to the row identifier of the tuple of the first table to obtain another row identifier of a second tuple of another table based on calculating at least one address in a memory based on at least one pointer in the index to another row of the index; and
determining data related between the first and second tuples based on reading a memory at an address determined from a database virtual address space that addresses the entire column-store database and having virtual addresses that are calculated from the row identifier in the index, wherein the memory is coupled to a database hardware accelerator processor comprising dataflow architecture hardware configured to execute database machine code instructions and read the address.
2. The method of claim 1 , wherein reading the index comprises calculating an address in a memory based on the row identifier of the index.
3. An apparatus comprising means for performing the method of claim 1 , said apparatus comprising:
means for determining a row identifier of a first tuple in a first table based on identifying a token for a group of data in the first tuple, wherein the token comprises a sequence of characters surrounded by at least one delimiter in the group of data;
means for reading an index at a row corresponding to the row identifier of the tuple of the first table to obtain another row identifier of a second tuple of another table based on calculating at least one address in a memory based on at least one pointer in the index to another row of the index; and
means for determining data related between the first and second tuples based on reading a memory at an address determined from a database virtual address space that addresses the entire column-store database and having virtual addresses that are calculated from the row identifier in the index, wherein the memory is coupled to a database hardware accelerator processor comprising dataflow architecture hardware configured to execute database machine code instructions and read the address.
4. A computer readable medium comprising computer executable instructions for configuring a processor to perform the method of claim 1 , said medium comprising:
program code for determining a row identifier of a first tuple in a first table based on identifying a token for a group of data in the first tuple, wherein the token comprises a sequence of characters surrounded by at least one delimiter in the group of data;
program code for reading an index at a row corresponding to the row identifier of the tuple of the first table to obtain another row identifier of a second tuple of another table based on calculating at least one address in a memory based on at least one pointer in the index to another row of the index; and
program code for determining data related between the first and second tuples based on reading a memory at an address determined from a database virtual address space that addresses the entire column-store database and having virtual addresses that are calculated from the row identifier in the index, wherein the memory is coupled to a database hardware accelerator processor comprising dataflow architecture hardware configured to execute database machine code instructions and read the address.
5. A method of relating data of one tuple in one table with one or more tuples of another table, said method comprising:
determining a row identifier of a first tuple in a first table based on identifying a token for a group of data in the first tuple, wherein the token comprises a sequence of characters surrounded by at least one delimiter in the group of data;
reading an index at a row corresponding to the row identifier of the tuple of the first table to obtain a set of row identifiers of at least one tuple of another table based on calculating at least one address in a memory based on at least one pointer in the index to another row of the index; and
determining data related between the first tuple of the first table and at least one tuple of the other table based on reading a memory at addresses determined from a database virtual address space that addresses the entire column-store database and having virtual addresses that are calculated from the at least one row identifier in the index, wherein the memory is coupled to a database hardware accelerator processor comprising dataflow architecture hardware configured to execute database machine code instructions and read the address.
6. The method of claim 5 , wherein reading the index comprises calculating an address in a memory based on the at least one row identifier of the index.
7. An apparatus comprising means for performing the method of claim 5 , said apparatus comprising:
means for determining a row identifier of a first tuple in a first table based on identifying a token for a group of data in the first tuple, wherein the token comprises a sequence of characters surrounded by at least one delimiter in the group of data;
means for reading an index at a row corresponding to the row identifier of the tuple of the first table to obtain a set of row identifiers of at least one tuple of another table based on calculating at least one address in a memory based on at least one pointer in the index to another row of the index; and
means for determining data related between the first tuple of the first table and at least one tuple of the other table based on reading a memory at addresses determined from a database virtual address space that addresses the entire column-store database and having virtual addresses that are calculated from the at least one row identifier in the index, wherein the memory is coupled to a database hardware accelerator processor comprising dataflow architecture hardware configured to execute database machine code instructions and read the address.
8. A computer readable medium comprising computer executable instructions for configuring a processor to perform the method of claim 5 , said medium comprising:
program code for determining a row identifier of a first tuple in a first table based on identifying a token for a group of data in the first tuple, wherein the token comprises a sequence of characters surrounded by at least one delimiter in the group of data;
program code for reading an index at a row corresponding to the row identifier of the tuple of the first table to obtain a set of row identifiers of at least one tuple of another table based on calculating at least one address in a memory based on at least one pointer in the index to another row of the index; and
program code for determining data related between the first tuple of the first table and at least one tuple of the other table based on reading a memory at addresses determined from a database virtual address space that addresses the entire column-store database and having virtual addresses that are calculated from the at least one row identifier in the index, wherein the memory is coupled to a database hardware accelerator processor coupled to the processor comprising dataflow architecture hardware configured to execute database machine code instructions and read the address.
9. A method of relating data of one tuple in one table with one or more tuples of another table, said method comprising:
determining a row identifier of a first tuple in a first table based on identifying a token for a group of data in the first tuple, wherein the token comprises a sequence of characters surrounded by at least one delimiter in the group of data;
reading an index at a row corresponding to the row identifier of the tuple of the first table to obtain a set of row identifiers of at least one tuple of another table, wherein reading the index comprises calculating a pointer to another column serving as an extension to the index; and
determining data related between the first tuple of the first table and at least one tuple of the other table based on reading a memory at addresses determined from a database virtual address space that addresses the entire column-store database and having virtual addresses that are calculated from the at least one row identifier in the index, wherein the memory is coupled to a database hardware accelerator processor comprising dataflow architecture hardware configured to execute database machine code instructions and read the address.
10. A method of searching for data in a column-store database, said method comprising:
identifying a group of data based on a token, wherein the token comprises a sequence of characters surrounded by at least one delimiter in the group of data;
determining a row identifier corresponding to the group in a first table;
reading an index at a row corresponding to the row identifier of the group to obtain a set of row identifiers of at least one tuple of another table based on calculating at least one address in a memory based on at least one pointer in the index to another row of the index; and
retrieving data in the group based on reading memory at addresses determined from a database virtual address space that addresses the entire column-store database and having virtual addresses that are calculated from the at least one row identifier in the index, wherein the memory is coupled to a database hardware accelerator processor comprising dataflow architecture hardware configured to execute database machine code instructions and read the address.
11. The method of claim 10 , wherein identifying the group of data comprises identifying a range of dates related to the data.
12. The method of claim 10 , wherein identifying the group of data comprises identifying an enumerated range to which the data is a member.
13. The method of claim 12 , wherein identifying the enumerated range comprises identifying the data as a zip code.
14. The method of claim 12 , wherein identifying the enumerated range comprises identifying the data as comprising a phone number.
15. The method of claim 12 , wherein identifying the enumerated range comprises identifying address information in the data.
16. The method of claim 12 , wherein identifying the enumerated range comprises determining whether the data is within a range of predetermined values.
17. The method of claim 10 , further comprising reading an additional column having entries that are reordered into a sequential input/output pattern of access.
18. The method of claim 17 , wherein reading the additional column comprises:
reading a set of pointers from entries in the additional column that indicate starting and ending row identifiers; and
retrieving only the entries from the column that are within the starting and ending row identifiers.
19. The method of claim 18 , wherein retrieving data in the group comprises sequentially fetching data from storage based on addresses derived from the starting and ending row identifiers.
20. An apparatus comprising means configured to search for data in a column-store database according to the method of claim 10 , said apparatus comprising:
means for identifying a group of data based on a token, wherein the token comprises a sequence of characters surrounded by at least one delimiter in the aroup of data;
means for determining a row identifier corresponding to the group in a first table;
means for reading an index at a row corresponding to the row identifier of the group to obtain a set of row identifiers of at least one tuple of another table based on calculating at least one address in a memory based on at least one pointer in the index to another row of the index; and
means for retrieving data in the group based on reading memory at addresses determined from a database virtual address space that addresses the entire column-store database and having virtual addresses that are calculated from the at least one row identifier in the index, wherein the memory is coupled to a database hardware accelerator processor comprising dataflow architecture hardware configured to execute database machine code instructions and read the address.
21. A computer readable medium comprising program code for performing the method of claim 10 , said computer readable medium comprising:
program code for identifying a group of data based on a token, wherein the token comprises a sequence of characters surrounded by at least one delimiter in the group of data;
program code for determining a row identifier corresponding to the group in a first table based on a token, wherein the token comprises a sequence of characters surrounded by at least one delimiter in the group of data;
program code for reading an index at a row corresponding to the row identifier of the group to obtain a set of row identifiers of at least one tuple of another table based on calculating at least one address in a memory based on at least one pointer in the index to another row of the index; and
program code for retrieving data in the group based on reading memory at addresses determined from a database virtual address space that addresses the entire column-store database and having virtual addresses that are calculated from the at least one row identifier in the index, wherein the memory is coupled to a database hardware accelerator processor comprising dataflow architecture hardware configured to execute database machine code instructions and read the address.