Database table look-up

• US 8,359,316 B2
• Filed: 03/01/2010
• Issued: 01/22/2013
• Est. Priority Date: 03/01/2010
• Status: Active Grant

• Current Assignee: Maplebear Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Franke, Hubertus, Fuh, You-Chin, Min, Hong, Purcell, Terence P., Shuf, Yefim
• Primary Examiner(s): Hu, Jensen
• Application Number:
  US12/714,617
• Publication Number:
  US 20110213775A1
• Time in Patent Office: 1,058 Days
• Field of Search: 707/737
• US Class Current: 707/737
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning

Abstract

Techniques for database table look-up are provided. The techniques include storing one or more column attributes of a database table in a data structure, wherein the data structure also comprises a record identification (RID) column of a table, one or more predicate columns corresponding to the RID column, and a sequence number column that is associated with one or more updated records, generating a key using one or more portions from one or more of the one or more predicate columns, using the key to partition the data structure, wherein partitioning the data structure comprises partitioning the one or more predicate columns for evaluation, and evaluating the one or more predicate columns against the data structure for each matching predicate column-data structure partition.

Claims

1. A method for database table look-up, wherein the method comprises:

storing one or more column attributes of a database table in a data structure, wherein the data structure is an auxiliary structure for the database table and also comprises a record identification (RID) column of a table that associates the database table and the auxiliary structure, one or more predicate columns corresponding to the RID column, and a sequence number column that is associated with one or more updated records;

generating a key using one or more portions from one or more of the one or more predicate columns;

using the key to partition the data structure, wherein partitioning the data structure comprises partitioning the one or more predicate columns for evaluation; and

evaluating the one or more predicate columns against the data structure for each matching predicate column-data structure partition.

2. The method of claim 1, wherein the one or more updated records comprise at least one of newly added data, updated data and deleted data.

3. The method of claim 1, wherein the data structure defines one or more database operations, wherein the one or more database operations comprise at least one of insert, update and delete.

4. The method of claim 1, further comprising encoding each value of each of the one or more predicate columns with at least one of bit string encoding and integer encoding.

5. The method of claim 4, wherein an encoding overflow is handled by applying a secondary encoding for updated records.

6. The method of claim 1, further comprising over-partitioning the data structure, wherein over-partitioning the data structure comprises creating more partitions than an expected number of threads.

7. The method of claim 1, further comprising partitioning in conjunction with bloom filtering for partition and predicate pruning.

8. The method of claim 1, wherein the one or more column attributes comprise data of one or more additional columns.

9. The method of claim 1, wherein the key comprises at least one of a concatenated bit string and a concatenated integer.

10. The method of claim 1, wherein using one or more portions from one or more of the one or more predicate columns comprises taking at least one of one or more bits and one or more digits from one or more of the one or more predicate columns.

11. The method of claim 1, wherein partitioning comprises using a multidimensional scheme to divide the data structure and decouple a predicate search.

12. The method of claim 1, wherein evaluating comprises evaluating via at least one of a scan and a search.

13. The method of claim 1, further comprising sorting one or more rows within each partition based on at least one of one or more subsets of columns and one or more corresponding encoding values to expedite a predicate search.

14. The method of claim 1, further comprising providing a system, wherein the system comprises one or more distinct software modules, each of the one or more distinct software modules being embodied on a tangible computer-readable recordable storage medium, and wherein the one or more distinct software modules comprise a query optimizer module, a predicate transformation module, a dictionary module, a predicate encoding module and an operation module executing on a hardware processor.

15. A computer program product comprising a tangible computer readable recordable storage medium including computer useable program code for database table look-up, the computer program product including:

computer useable program code for storing one or more column attributes of a database table in a data structure, wherein the data structure is an auxiliary structure for the database table and also comprises a record identification (RID) column of a table that associates the database table and the auxiliary structure, one or more predicate columns corresponding to the RID column, and a sequence number column that is associated with one or more updated records;

computer useable program code for generating a key using one or more portions from one or more of the one or more predicate columns;

computer useable program code for using the key to partition the data structure, wherein partitioning the data structure comprises partitioning the one or more predicate columns for evaluation; and

computer useable program code for evaluating the one or more predicate columns against the data structure for each matching predicate column-data structure partition.

16. The computer program product of claim 15, wherein the one or more updated records comprise at least one of newly added data, updated data and deleted data.

17. The computer program product of claim 15, wherein the data structure defines one or more database operations, wherein the one or more database operations comprise at least one of insert, update and delete.

18. The computer program product of claim 15, further comprising computer useable program code for encoding each value of each of the one or more predicate columns with at least one of bit string encoding and integer encoding.

19. The computer program product of claim 15, further comprising computer useable program code for partitioning in conjunction with bloom filtering for partition and predicate pruning.

20. A system for database table look-up, comprising:

a memory; and

at least one processor coupled to the memory and operative to;

store one or more column attributes of a database table in a data structure, wherein the data structure is an auxiliary structure for the database table and also comprises a record identification (RID) column of a table that associates the database table and the auxiliary structure, one or more predicate columns corresponding to the RID column, and a sequence number column that is associated with one or more updated records;

generate a key using one or more portions from one or more of the one or more predicate columns;

use the key to partition the data structure, wherein partitioning the data structure comprises partitioning the one or more predicate columns for evaluation; and

evaluate the one or more predicate columns against the data structure for each matching predicate column-data structure partition.

21. The system of claim 20, wherein the one or more updated records comprise at least one of newly added data, updated data and deleted data.

22. The system of claim 20, wherein the data structure defines one or more database operations, wherein the one or more database operations comprise at least one of insert, update and delete.

23. The system of claim 20, wherein the at least one processor coupled to the memory is further operative to encode each value of each of the one or more predicate columns with at least one of bit string encoding and integer encoding.

24. The system of claim 20, wherein the at least one processor coupled to the memory is further operative to partition in conjunction with bloom filtering for partition and predicate pruning.

25. An apparatus for database table look-up, the apparatus comprising:

means for storing one or more column attributes of a database table in a data structure, wherein the data structure is an auxiliary structure for the database table and also comprises a record identification (RID) column of a table that associates the database table and the auxiliary structure, one or more predicate columns corresponding to the RID column, and a sequence number column that is associated with one or more updated records;

means for generating a key using one or more portions from one or more of the one or more predicate columns;

means for using the key to partition the data structure, wherein partitioning the data structure comprises partitioning the one or more predicate columns for evaluation; and

means for evaluating the one or more predicate columns against the data structure for each matching predicate column-data structure partition.