Multi-dimensional OLAP query processing method oriented to column store data warehouse

• US 8,660,985 B2
• Filed: 05/16/2012
• Issued: 02/25/2014
• Est. Priority Date: 04/11/2012
• Status: Active Grant

• Current Assignee: Renmin University of China
• Original Assignee: Renmin University of China
• Inventors: Wang, Shan, Zhang, Yan-Song
• Primary Examiner(s): Beausoliel, Jr., Robert
• Assistant Examiner(s): ALLEN, NICHOLAS E
• Application Number:
  US13/514,294
• Publication Number:
  US 20130275365A1
• Time in Patent Office: 650 Days
• Field of Search: 707/766, 707/776, 707/918, 707/919
• US Class Current: 707/602
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP

Abstract

A multi-dimensional OLAP query processing method oriented to a column store data warehouse is described. With this method, an OLAP query is divided into a bitmap filtering operation, a group-by operation and an aggregate operation. In the bitmap filtering operation, a predicate is first executed on a dimension table to generate a predicate vector bitmap, and a join operation is converted, through address mapping of a surrogate key, into a direct dimension table tuple access operation; in the group-by operation, a fact table tuple satisfying a filtering condition is pre-generated into a group-by unit according to a group-by attribute in an SQL command and is allocated with an increasing ID; and in the aggregate operation, group-by aggregate calculation is performed according to a group item of a fact table filtering group-by vector through one-pass column scan on a fact table measure attribute.

Claims

1. A multi-dimensional on-line analytical processing (OLAP) query processing method oriented to a column store data warehouse, an OLAP query being divided into a bitmap filtering operation, a group-by operation and an aggregate operation;

among them, a fact table and dimension tables being stored by adopting a column store model, a dimensional attribute column is loaded into main memory to form a memory dimensional attribute array, wherein a primary key is corresponding to a subscript of the memory dimensional attribute array;

a foreign key attribute value of the fact table tuple is mapped to a subscript of the memory dimensional attribute array in the corresponding dimension table; and

the fact table and the dimension tables complete a multi-table join operation through a corresponding relation between the foreign key and the primary key, wherein;

in the bitmap filtering operation, a predicate is executed on the dimension table to generate a predicate vector bitmap, and a join operation is converted, through address mapping of a surrogate key, into a direct dimension table tuple access operation, thereby implementing access according to a position;

in the group-by operation, a fact table tuple satisfying a filtering condition is pre-generated into a group-by unit according to a group-by attribute in an SQL command and is allocated with an increasing ID; and

in the aggregate operation, group-by aggregate calculation is performed according to a group item of a fact table filtering group-by vector through one-pass column scan on a fact table measure attribute.

2. The multi-dimensional OLAP query processing method oriented to a column store data warehouse according to claim 1, wherein:

when the memory cannot accommodate all dimension tables, dimension table group-by attribute columns need to be accessed in the query processing are loaded into the memory to form memory dimensional vectors, a predicate operation is performed on the dimension tables, and predicate operation results are stored in a bitmap with the same length as the dimension table, to serve as predicate vectors for recording satisfaction states of different dimension table records with the predicate operation results.

3. The multi-dimensional OLAP query processing method oriented to a column store data warehouse according to claim 1, wherein:

a group-by aggregate hash table and a fact table filtering group-by vector are pre-created, wherein the group-by aggregate hash table is pre-created by using the group-by attributes and additional IDs in the query as objects, and the fact table filtering group-by vector is a numerical vector having the same length as the fact table.

4. The multi-dimensional OLAP query processing method oriented to a column store data warehouse according to claim 1, wherein:

foreign key attribute groups having dimension table join relation in the fact table are sequentially scanned, each foreign key attribute group record is read, the fact table foreign key attribute value is directly mapped to a predicate vector subscript, and bit data recorded by the bit in the predicate vector is taken out to perform an AND operation; and

if a result of the bit operation is false, the next foreign key attribute group record is read; and

if the result of the bit operation is true, the value of each foreign key is mapped to a subscript of a dimension table group-by attribute vector.

5. The multi-dimensional OLAP query processing method oriented to a column store data warehouse according to claim 1, wherein:

a designated data item in a group-by dimensional attribute vector is extracted and then hash group-by is performed, and if a current hash key value exists, the hash group ID is taken out and recorded in a position in the fact table filtering group-by vector and corresponding to the current fact table tuple; and

if the current hash key value does not exist, a new hash group is created in the group-by hash table and allocated with an increasing ID, and at the same time, the hash group ID is recorded in a position in the fact table join vector and corresponding to the current fact table tuple.

6. The multi-dimensional OLAP query processing method oriented to a column store data warehouse according to claim 1, wherein:

after the scan of the fact table foreign key attribute group is completed, the fact table filtering group-by vector and a preset group-by aggregate hash table are obtained, and an array of aggregate functions is created according to a maximum ID value to serve as a group-by aggregate accumulator.

7. The multi-dimensional OLAP query processing method oriented to a column store data warehouse according to claim 6, wherein:

when a non-zero data item is scanned in the fact table filtering group-by vector, a measure attribute column stored in a disk is accessed according to a vector subscript position, and the measure attribute value is sent to a unit with a subscript of the group-by aggregate accumulator array corresponding to the hash group ID value in the fact table filtering group-by vector, so as to perform the aggregate calculation.

8. The multi-dimensional OLAP query processing method oriented to a column store data warehouse according to claim 7, wherein:

after the aggregate calculation is completed for all the measure attribute columns, the group-by aggregate hash table and each group-by aggregate accumulator are merged according to a sequence of the IDs and the array subscripts, so as to generate a final OLAP aggregate result.

9. The multi-dimensional OLAP query processing method oriented to a column store data warehouse according to claim 1, wherein:

if the query processing procedure comprises multiple distributed aggregate functions, each distributed aggregate function is processed sequentially by scanning a fact table join result vector.

10. A multi-dimensional on-line analytical processing (OLAP) query processing method oriented to a column store data warehouse, an OLAP query being divided into a bitmap filtering operation, a group-by operation and an aggregate operation, a fact table and dimension tables being stored by adopting a column store model, wherein:

in the bitmap filtering operation, a predicate is executed on the dimension table to generate a predicate vector bitmap, and a join operation is converted, through address mapping of a surrogate key, into a direct dimension table tuple access operation, thereby implementing access according to a position;

in the group-by operation, a fact table tuple satisfying a filtering condition is pre-generated into a group-by unit according to a group-by attribute in an SQL command and is allocated with an increasing ID;

in the aggregate operation, group-by aggregate calculation is performed according to a group item of a fact table filtering group-by vector through one-pass column scan on a fact table measure attribute;

after the scan of the fact table foreign key attribute group is completed, the fact table filtering group-by vector and a preset group-by aggregate hash table are obtained, and an array of aggregate functions is created according to a maximum ID value to serve as a group-by aggregate accumulator; and

when a non-zero data item is scanned in the fact table filtering group-by vector, a measure attribute column stored in a disk is accessed according to a vector subscript position, and the measure attribute value is sent to a unit with a subscript of the group-by aggregate accumulator array corresponding to the hash group ID value in the fact table filtering group-by vector, so as to perform the aggregate calculation.