ACCESSING DATA IN A COLUMN STORE DATABASE BASED ON HARDWARE COMPATIBLE DATA STRUCTURES

• US 20090254532A1
• 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, Krishnamurthy, Ravi, Corwin, Michael, Branscome, Jeremy
• Granted Patent: US 7,966,343 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof

Abstract

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.

Claims

1. A method of accessing data in a column-store, relational database, wherein the column-store relational database comprises data in rows of at least one table and a set of column groups of one or more columns, wherein each column group has a fixed width, said method comprising:

receiving a program of machine code database instructions created for a query on data;

determining virtual addresses for the data, wherein the virtual addresses are computed from a set of row identifiers, a base virtual address of a column group, and a column group width of the data;

calculating respective physical addresses in a memory based on the virtual addresses; and

accessing, at the physical addresses, the data requested in the query.

2. The method of claim 1, wherein the set of row identifiers uniquely identify, external to tables of the database, each tuple of the tables.

3. The method of claim 1, wherein the set of row identifiers is based on a count of tuples of the tables.

4. The method of claim 1, further comprising arithmetically deriving virtual addresses for the data in the column and for other columns in the same tuple from one of the row identifiers, a respective base virtual address for the other column groups, and respective widths of the column groups.

5. The method of claim 1, further comprising checking a validity of the tuple based on information in one or more of the columns of the column-store database.

6. The method of claim 5, wherein the columns having validity information are grouped with other columns based on a frequency of access with the other columns of the column-store database.

7. The method of claim 1, wherein the column-store database comprises tables and wherein accessing data across different tables comprises identifying one or more row identifiers for data in column groups of one table that correspond to data in a different table.

8. An apparatus comprising means configured to perform the method of claim 1, said apparatus comprising:

means for receiving a program of machine code database instructions created for a query on data;

means for determining virtual addresses for the data, wherein the virtual addresses are computed from a set of row identifiers, a base virtual address of a column group, and a column group width of the data;

means for calculating respective physical addresses in a memory based on the virtual addresses; and

means for accessing, at the physical addresses, the data requested in the query.

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

program code for receiving a program of machine code database instructions created for a query on data;

program code for determining virtual addresses for the data, wherein the virtual addresses are computed from a set of row identifiers, a base virtual address of a column group, and a column group width of the data;

program code for calculating respective physical addresses in a memory based on the virtual addresses; and

program code for accessing, at the physical addresses, the data requested in the query.

10. A method of encoding data into a hardware-favorable form for a database, said method comprising:

profiling columns of the data;

compressing the columns of the data into column groups having one or more columns based on the profile of the columns of data;

determining a fixed width for each of the column groups; and

writing the column groups with the selected fixed width into a column-store database.

11. The method of claim 10, wherein determining the fixed width comprises determining a fixed width that is a multiple of a machine word.

12. The method of claim 10, wherein determining the fixed width comprises determining a fixed width that is a multiple of a machine word and minimizes an amount space required to store the column group.

13. The method of claim 10, wherein profiling the columns of data comprises sampling columns of the data.

14. The method of claim 10, wherein profiling the columns of data comprises determining whether data in the column comprises a range of floating point numbers.

15. The method of claim 10, wherein profiling the columns of data comprises determining whether data in the column comprises a range of integers.

16. The method of claim 10, wherein profiling the columns of data comprises determining whether data in the column comprises a finite set of tokens.

17. The method of claim 16, wherein determining whether data in the column comprises a finite set of tokens comprises determining a sequence of characters that are separated by a delimiter.

18. The method of claim 10, wherein profiling the columns of data comprises determining whether data in the column comprises an enumerated range of values.

19. The method of claim 10, wherein profiling the columns of data comprises determining whether data in the column comprises information relating to dates.

20. The method of claim 10, wherein profiling the columns of data comprises determining whether data in the column comprises a range of telephone numbers.

21. The method of claim 10, wherein profiling the columns of data comprises determining whether data in the column comprises a range of address information.

22. The method of claim 10, wherein compressing the columns of the data into a column group comprises compressing the columns based on tokens.

23. The method of claim 10, wherein compressing the columns of the data into a column group comprises compressing the columns based on enumeration.

24. The method of claim 10, wherein compressing the columns of the data into a column group comprises compressing the columns based on a reduced alphabet.

25. The method of claim 10, wherein compressing the columns of the data into a column group comprises compressing the columns based on a range of integer values.

26. The method of claim 10, further comprising:

determining a dictionary of tokens for data in the columns of data; and

determining a sort index for the dictionary of tokens based on assigning the tokens a monotonically increasing sequence of numbers.

27. The method of claim 26, further comprising determining a sorted array of tokens that define a sort order of the tokens.

28. An apparatus comprising means configured to perform the method of claim 10, said apparatus comprising:

means for profiling columns of the data;

means for compressing the columns of the data into column groups having one or more columns based on the profile of the columns of data;

means for determining a fixed width for each of the column groups; and

means for writing the column groups with the selected fixed width into a column-store database.

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

program code for profiling columns of the data;

program code for compressing the columns of the data into column groups having one or more columns based on the profile of the columns of data;

program code for determining a fixed width for each of the column groups; and

program code for writing the column groups with the selected fixed width into a column-store database.