Efficient and scalable data evolution with column oriented databases

• US 8,244,735 B2
• Filed: 05/03/2010
• Issued: 08/14/2012
• Est. Priority Date: 05/03/2010
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: He, Bin, Hsiao, Hui-I
• Primary Examiner(s): Syed, Farhan
• Application Number:
  US12/772,697
• Publication Number:
  US 20110270844A1
• Time in Patent Office: 834 Days
• Field of Search: None
• US Class Current: 707/745
• CPC Class Codes: G06F 16/213 with details for schema evolution support
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices

Abstract

A method, system and program product for data evolution on column oriented databases is disclosed. For an input evolution operation, reusable and non-reusable attributes are identified. For attributes in a target schema that cannot be reused from the source schema, data and bitmap indexes of those attributes are generated from source data and bitmap indexes. A decompose operation is disclosed for decomposing a table into two tables. A merge operation is disclosed in which only one input table can be reused for mergence. A second merge operation is disclosed in which both input tables cannot be reused for mergence.

Claims

1. A computer-implemented method for decomposing a first table into a second table and a third table comprising:

identifying reusable and non-reusable attributes of data stored in the first table;

generating data and bitmap indexes for the second table;

re-using attributes of the first table in the third table; and

outputting the first table, the second table, and the third table, after decomposing the first table into the second table and the third table, in a visual form including at least one of displaying said tables on a display unit or printing said tables on a printer,

wherein the generating of data and bitmap indexes for the second table includes;

locating a first tuple position in the first table for each of a plurality of unique values of a join attribute;

forming a filtering vector from a plurality of located positions of the unique values of the join attribute by taking bits specified in a list of positions of tuples in the first table;

generating at least one of the data and bitmap indexes for the second table for a first attribute in the second table corresponding to a first attribute in the first table, and

computing a target bitmap index for each unique value of the first attribute in the second table as a corresponding source bitmap index filtered by the filter vector; and

generating target data for the first attribute in the second table.

2. The method of claim 1, wherein no entire bitmap of a column is accessed.

3. The method of claim 1, wherein the first two words of the filter vector are recorded in a file.

4. The method of claim 1, wherein the first table contains multiple key attributes, and bitmaps of the multiple key attributes are combined.

5. The method of claim 1, wherein an offset index of a column is scanned to access values for a row.

6. The method of claim 5, wherein hashing is used to recognize distinct values during the scan of the column.

7. A system comprising:

a computer including a computer processor configured to process data evolution;

a computer user interface configured to enter data for a first table and a second table;

a data evolution engine; and

a computer display configured to update the first, second, and third tables after decomposing the first table into the second table and the third table in a visual form including displaying said tables on a display unit,

wherein the data evolution engine is configured to;

merge the first table and the second table into a third table;

reuse attributes from the first table in the third table;

generate data and bitmap indexes for attributes in the third table not reused from the first table; and

update a target bitmap vector, the step of updating the target bitmap vector including;

updating the target bitmap vector and target data of each non-key attribute in a first tuple of a plurality of tuples of the first table, according to a bitmap vector of a key attribute in the first tuple of the first table;

clustering the plurality of tuples in the first table according to each non-key attribute; and

performing the updating of the target bitmap vector for the first tuple of the plurality of tuples in the first table and for at least one of the non-key attributes in the first tuple in the first table.

8. The system of claim 7, wherein the data evolution engine further accesses attribute values of the first table sequentially.

9. The system of claim 7, wherein the data evolution engine further accesses one of the key attributes of the first table randomly.

10. The system of claim 7, wherein the data evolution engine further returns a vector corresponding to a list of values from a first key attribute of the first table, wherein the first table contains a single attribute.

11. The system of claim 7, wherein the data evolution engine further performs an AND operation on the bitmap vectors of the key attribute from the first table and a key attribute from the second table, and wherein the first table contains multiple attributes.

12. The system of claim 7, wherein the data evolution engine further combines the key attribute in the first table with a key attribute in the second table with an OR operation.

13. A computer program product for data evolution, the computer program product comprising:

a non-transitory computer readable storage medium having computer readable program code embodied therewith, the computer readable program code including;

computer program code configured to identify reusable and non-reusable attributes of data stored in the first table;

computer program code configured to merge a first table and a second table into a third table, wherein attributes of the first table and attributes of the second table are not reused in the third table;

computer program code configured to generate data and bitmap indexes for attributes in the third table, and

computer program code configured to output the first, second, and third tables after decomposing the first table into the second table and the third table in a visual form including on a display unit,

wherein the computer program code configured to generate data and bitmap indexes for attributes in the third table includes;

computer program code configured to compute a number of occurrences of a first unique value of a key attribute in the first table and a first unique value of a key attribute in the second table;

computer program code configured to generate a corresponding data and bitmap index for each tuple in the first table and for each non-key attribute of a first tuple in the first table, in which the first unique value of the key attribute in the first table occurs in the first table, for each of a plurality of unique values of the key attribute of the first table such that a bitmap vector for the first unique value of the key attribute in the first table is derived from the computed number of occurrences of the first unique value of the key attribute in the first table; and

computer program code configured to generate a corresponding data and bitmap index for each tuple in the second table and for each non-key attribute of a first tuple in the second table, in which the first unique value of the key attribute occurs in the second table, for each of a plurality of unique values of the key attribute of the second table.

14. The computer program product of claim 13, wherein a number of occurrences of the first unique value of the key attribute of the first table and first unique value of the key attribute of the second table is stored in a hash structure.

15. The computer program product of claim 13, wherein the computer program code computing a number of occurrences of the first unique value of a key attribute in the first table and the first unique value of a key attribute in the second table scans the first table and the second table in a first pass and a second pass.

16. The computer program product of claim 15, wherein the first pass only accesses a second attribute common to the first table and the second table.

17. The computer program product of claim 15, wherein the second pass scans the first table and the second table in separate operations.

18. The computer program product of claim 13, wherein a total count of a number of inputs and outputs on disks in a computer readable medium is of the order of a table size of the first table and the second table, added to a bitmap size of the first table and the second table.

19. A computer-implemented method for use with a column-oriented database, comprising:

performing a decompose table operation on the first data and the first index of the first schema, wherein a first table is decomposed into a second table and a third table;

identifying re-usable and non-reusable attributes of data stored in the first table;

transforming first data from a first schema into a second schema, wherein portions of both the first data and a first index of the first schema are identified that can be re-used in the second schema, and portions of both the first data and the first index of the first schema not included in the re-usable portions of the first data and the first index of the first schema are transformed directly into the second schema;

performing a merge table operation on the first data and the first index of the first schema, wherein a first table and a second table are merged into a third table; and

re-organizing the third table after the merge table operation such that the attributes of a first column in the third table are clustered.

20. The method of claim 19, wherein said transforming first data does not involve query processing.