ACCESSING DATA IN A COLUMN STORE DATABASE BASED ON HARDWARE COMPATIBLE INDEXING AND REPLICATED REORDERED COLUMNS

• US 20090254516A1
• Filed: 04/07/2008
• Published: 10/08/2009
• Est. Priority Date: 04/07/2008
• Status: Active Grant

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: Teradata US, Inc. (Teradata Corporation)
• Inventors: Chamdani, Joseph I., Meiyyappan, Krishnan, Surlaker, Kapil, Yang, Liuxi, Shau, James, Krishnamurthy, Ravi, Corwin, Michael, Branscome, Jeremy
• Granted Patent: US 8,862,625 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/134 Distributed indices
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/24557 Efficient disk access during query execution
• CPC Class Codes: G06F 16/24562 Pointer or reference processing operations

Abstract

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.

Claims

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;

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; and

determining data related between the first and second tuples based on reading a memory at an address calculated from the row identifier in the index.

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;

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; and

means for determining data related between the first and second tuples based on reading a memory at an address calculated from the row identifier in the index.

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;

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; and

program code for determining data related between the first and second tuples based on reading a memory at an address calculated from the row identifier in the index.

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;

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; 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 calculated from the at least one row identifier in the index.

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. The method of claim 5, wherein reading the index comprises calculating at least one address in a memory based on at least one pointer in the index to another row of the index.

8. The method of claim 5, wherein reading the index comprises calculating a pointer to another column serving as an extension to the index.

9. 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;

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; 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 calculated from the at least one row identifier in the index.

10. 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;

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; 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 calculated from the at least one row identifier in the index.

11. A method of searching for data in a column-store database, said method comprising:

identifying a group to which the data is a member;

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; and

retrieving data in the group based on reading memory at addresses calculated from the at least one row identifier in the index.

12. The method of claim 11, wherein identifying the group to which the data is a member comprises identifying a range of dates related to the data.

13. The method of claim 11, wherein identifying the group to which the data is a member comprises identifying a token in the data.

14. The method of claim 13, wherein identifying the token in the data comprises identifying a sequence of characters surrounded by at least one delimiter.

15. The method of claim 11, wherein identifying the group to which the data is a member comprises identifying an enumerated range to which the data is a member.

16. The method of claim 15, wherein identifying the enumerated range comprises identifying the data as a zip code.

17. The method of claim 15, wherein identifying the enumerated range comprises identifying the data as comprising a phone number.

18. The method of claim 15, wherein identifying the enumerated range comprises identifying address information in the data.

19. The method of claim 15, wherein identifying the enumerated range comprises determining whether the data is within a range of predetermined values.

20. The method of claim 11, further comprising reading an additional column having entries that are reordered into a sequential input/output pattern of access.

21. The method of claim 20, 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.

22. The method of claim 21, wherein retrieving data in the group comprises sequentially fetching data from storage based on addresses derived from the starting and ending row identifiers.

23. An apparatus comprising means configured to search for data in a column-store database according to the method of claim 11, said apparatus comprising:

means for identifying a group to which the data is a member;

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; and

means for retrieving data in the group based on reading memory at addresses calculated from the at least one row identifier in the index.

24. A computer readable medium comprising program code for performing the method of claim 11, said computer readable medium comprising:

program code for identifying a group to which the data is a member;

program code for determining a row identifier corresponding to the group in a first table;

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; and

program code for retrieving data in the group based on reading memory at addresses calculated from the at least one row identifier in the index.