Method for laying out fields in a database in a hybrid of row-wise and column-wise ordering

• US 8,099,440 B2
• Filed: 08/15/2008
• Issued: 01/17/2012
• Est. Priority Date: 08/15/2008
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Johnson, F. Ryan, Raman, Vijayshankar, Reiss, Frederick R., Sidle, Richard S., Swart, Garret F.
• Primary Examiner(s): Lovel, Kimberly
• Assistant Examiner(s): Uddin, Mohammed R
• Application Number:
  US12/192,504
• Publication Number:
  US 20100042587A1
• Time in Patent Office: 1,250 Days
• Field of Search: 707/802, 707/713
• US Class Current: 707/802
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/24569 Query processing with adaptation to specific hardware, e.g. adapted for using GPUs or SSDs

Abstract

A method, system, and article are provided for employment of a hybrid layout of representation of data objects in computer memory. Columns of the database are separated based upon a classification of the columns. A vertical partition in the form of a bank is provided to receive an assignment of one or more data objects identified in the columns. Each bank is sized to be a divisor of a size of an associated hardware register. Assignment of data objects to banks organizes the data in a manner that support efficient query processing that mitigates the quantity of banks required to respond to the query.

Claims

1. A method for representing a database of multiple data objects on computer memory, comprising:

separating a data object with multiple attributes into at least two parts—

a first part having measure columns laid out in row-major order and a second part having non-measure columns laid out in a vertical partition, said measure and non-measure columns representing different characteristics of a database table;

creating a hybrid layout of said database table by organizing attributes of said first and second parts into at least two separate banks, with the bank being a vertical partition containing a subset of the attributes;

sizing each bank as a divisor of a machine register size; and

storing said first and second parts in the at least two separate banks.

2. The method of claim 1, further comprising sizing each bank as a power of two of a number of bits corresponding to a machine word size.

3. The method of claim 1, wherein a size of the bank is dictated by hardware specification.

4. The method of claim 1, further comprising separating a measure column of the table from the non-measure column of the table, including placing at least one measure column in a first bank and placing at least one data object from the non-measure column in a second bank, wherein said first bank is separate from said second bank.

5. The method of claim 1, further comprising placing multiple data objects identified in the non-measure columns in a single bank with optional spacing in the bank between adjacent objects.

6. The method of claim 1, further comprising placing data objects from commonly aggregated columns of the table into a single bank.

7. The method of claim 1, further comprising storing a data attribute redundantly in multiple banks for one or more of the data attributes.

8. The method of claim 1, further comprising storing corresponding separated parts of all data objects together in a bank for objects within a page.

9. The method of claim 1, further comprising executing a query on the data objects, the execution comprising:

evaluating query conditions on each object;

forming a list of the objects for each bank that pass the query conditions on attributes that are stored in that bank; and

merging the lists from each bank to form a list of objects that pass all query conditions.

10. The method of claim 9, further comprising representing the formed list of objects as a bitmap.

11. The method of claim 9, further comprising filtering the list by applying query conditions that include attributes from multiple banks.

12. The method of claim 9, wherein the lists are used to fetch commonly aggregate columns for those objects in the list, and aggregate the values in those columns.

13. An article configured to represent a database of multiple data objects on computer memory, the article comprising:

a computer-readable medium including computer program instructions and to process a query responsive to the configuration, the instructions comprising;

instructions to separate a data object with multiple attributes into at least two parts —

a first part having measure columns laid out in row-major order and a second part having non-measure columns laid out in a vertical partition, said measure and non-measure columns representing different characteristics of a database table;

instructions to create a hybrid layout of said database table by organizing attributes of said first and second parts into at least two separate banks, with the bank being a vertical partition containing a subset of the attributes;

instructions to size each bank as a divisor of a machine register size; and

instructions to said first and second parts in the at least two separate banks.

14. The article of claim 13, further comprising instructions to separate a measure column of the table from the non-measure column of the table, including placement of at least one measure column in a first bank and placement of at least one data object from the non-measure column in a second bank, wherein said first bank is separate from said second bank.

15. The article of claim 13, further comprising instructions to place multiple data objects from the non-measure columns in a single bank with optional spacing in the bank between adjacent data objects.

16. The article of claim 13, further comprising instructions to place commonly aggregated data objects of the table subject to a query into a single bank.

17. The article of claim 13, further comprising instructions to execute a query on the data objects, the query comprising:

evaluating query conditions on each object;

forming a list of the objects for each bank that pass predicates of the query conditions; and

merging the lists from each bank to form a list of objects that pass all predicates.

18. The article of claim 17, further comprising instructions to represent the formed list of objects as a bitmap.

19. The article claim 17, wherein the lists are used to fetch commonly aggregate columns for those objects in the list, and aggregate the values in those columns.

20. A method for representing a database of multiple data objects on computer memory, comprising:

separating a data object with multiple attributes into at least two parts—

a first part having measure columns laid out in row-major order and a second part having non-measure columns laid out in a vertical partition, said measure and non-measure columns representing different characteristics of a database table, said measure columns used by a query for aggregation and not for predicate evaluation or group-by processing, and said non-measure column identifiable by their presence in a dimension table of said database;

creating a hybrid layout of said database table by organizing attributes of said first and second parts into at least two separate banks, with the bank being a vertical partition containing a subset of the attributes;

sizing each bank as a divisor of a machine register size; and

storing said first and second parts in the at least two separate banks.