ACCESSING A DIMENSIONAL DATA MODEL WHEN PROCESSING A QUERY

• US 20130117255A1
• Filed: 11/08/2011
• Published: 05/09/2013
• Est. Priority Date: 11/08/2011
• Status: Active Grant

• Current Assignee: Wrp IP Management, LLC
• Original Assignee: International Business Machines Corporation
• Inventors: Liu, Shaorong, Sharpe, David C., Sizto, Chi Man J.
• Granted Patent: US 9,043,310 B2
• Time in Patent Office: Days
• US Class Current: 707/714
• CPC Class Codes: G06F 16/2456 Join operations
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP

Abstract

Techniques are disclosed for accessing a dimensional data model when processing a query. In one embodiment, the query is processed by performing a two-stage zigzag join operation including a zigzag main join and a zigzag back join. The zigzag main join is configured to generate a set of row identifiers of fact records satisfying any local predicates in the query. The zigzag back join is configured to generate query results based on the set of row identifiers. The query results are returned responsive to the query.

Claims

1. A computer-implemented method for processing a query against a dimensional data model, the dimensional data model comprising a fact table and a plurality of dimension tables, the method comprising:

determining, from each dimension table, a respective set of dimension records satisfying any local predicates in the query pertaining to the respective dimension table;

based on the sets of dimension records and by operation of one or more computer processors, identifying, from the fact table, a set of row identifiers of fact records satisfying any join predicates and local predicates in the query, wherein the row identifier of each fact record is identified by joining a respective, distinct, concatenated dimension record to the fact table and applying any local predicates to the fact table, wherein each concatenated dimension record is generated by concatenating a join key value from each set of dimension records, wherein the join key values for generating at least a first concatenated dimension record are determined based on a feedback record, wherein the feedback record comprises at least a portion of a next ordered fact record succeeding a previously identified fact record; and

generating query results responsive to the query by joining, to the sets of dimension records, one or more fact records in the fact table selected based on the row identifiers.

2. The computer-implemented method of claim 1, wherein retrieval of one or more dimension payload columns is deferred until generating the query results, to facilitate data retrieval from the plurality of dimension tables, wherein the set of row identifiers is sorted according to an order in which data pages of the fact table are stored, to facilitate data retrieval from the fact table, and wherein the method further comprises:

prior to generating the query results, prefetching at least a portion of a first data page.

3. The computer-implemented method of claim 1, wherein generating query results by joining, to the sets of dimension records, one or more fact records in the fact table selected based on the row identifiers comprises performing one or more consuming pushdown operations on the a data page of the fact table.

4. The computer-implemented method of claim 1, wherein the query does not specify any payload column in a first dimension table, wherein the first dimension table includes a surrogate key column, wherein a payload column comprises a column other than the join key column and the surrogate key column, wherein the first dimension table stores, in the surrogate key column, a range of surrogate key values between a minimum key value and a maximum key value.

5. The computer-implemented method of claim 4, further comprising, prior to determining a respective set of dimension records from each dimension table:

generating a bitmap having a count of bits greater than a difference between the maximum key value and the minimum key value, wherein each bit represents whether any dimensional records having a corresponding join key value not violating any local predicate of the query;

wherein the bitmap is used in at least one of identifying the feedback record and joining the accessed fact records to the plurality of dimension tables.

6. The computer-implemented method of claim 1, wherein the query specifies at least one payload column in a first dimension table, wherein the first dimension table includes a key column selected from a join key column densely storing values in a value range and a surrogate key column, wherein a payload column comprises a column other than the join key column and the key column, and wherein the method further comprises, prior to determining a respective set of dimension records from each dimension table:

storing, in at least one of a table and an index, the key column and the payload column, wherein the key column includes a plurality of row identifiers of the first dimension table;

storing, in an in-memory array, a plurality of buffer entries, each buffer entry comprising a join key value and an associated row identifier of the first dimension table; and

sorting the plurality of buffer entries in the in-memory array, without sorting any records in the table, wherein the sorted buffer entries are ordered by the join key column and the surrogate key column;

wherein the sorted buffer entries are used in at least one of identifying the feedback record and joining the accessed fact records to the plurality of dimension tables.

7. The computer-implemented method of claim 6, wherein the dimensional data model is selected from at least one of a star schema and a snowflake schema, and wherein the method further comprises:

generating an index for at least one join key value and associated row identifier not stored in the in-memory array, wherein the index comprises a B-tree, wherein the at least one join key value is further associated with a payload value, and wherein the associated payload value is stored in at least one of the index and the table.

8. A computer program product, comprising:

a computer-readable storage medium having computer-readable program code embodied therewith for processing a query against a dimensional data model, the dimensional data model comprising a fact table and a plurality of dimension tables, the computer-readable program code comprising;

computer-readable program code configured to determine, from each dimension table, a respective set of dimension records satisfying any local predicates in the query pertaining to the respective dimension table;

computer-readable program code configured to identify, from the fact table and based on the sets of dimension records, a set of row identifiers of fact records satisfying any join predicates and local predicates in the query, wherein the row identifier of each fact record is identified by joining a respective, distinct, concatenated dimension record to the fact table and applying any local predicates to the fact table, wherein each concatenated dimension record is generated by concatenating a join key value from each set of dimension records, wherein the join key values for generating at least a first concatenated dimension record are determined based on a feedback record, wherein the feedback record comprises at least a portion of a next ordered fact record succeeding a previously identified fact record; and

computer-readable program code configured to generate query results responsive to the query by joining, to the sets of dimension records, one or more fact records in the fact table selected based on the row identifiers.

9. The computer program product of claim 8, wherein retrieval of one or more dimension payload columns is deferred until generating the query results, to facilitate data retrieval from the plurality of dimension tables, wherein the set of row identifiers is sorted according to an order in which data pages of the fact table are stored, to facilitate data retrieval from the fact table, and wherein the computer-readable program code further comprises:

computer-readable program code configured to, prior to generating the query results, prefetch at least a portion of a first data page.

10. The computer program product of claim 8, wherein generating query results by joining, to the sets of dimension records, one or more fact records in the fact table selected based on the row identifiers comprises performing one or more consuming pushdown operations on the a data page of the fact table.

11. The computer program product of claim 8, wherein the query does not specify any payload column in a first dimension table, wherein the first dimension table includes a surrogate key column, wherein a payload column comprises a column other than the join key column and the surrogate key column, wherein the first dimension table stores, in the surrogate key column, a range of surrogate key values between a minimum key value and a maximum key value.

12. The computer program product of claim 11, wherein the computer-readable program code further comprises:

computer-readable program code configured to, prior to determining a respective set of dimension records from each dimension table, generate a bitmap having a count of bits greater than a difference between the maximum key value and the minimum key value, wherein each bit represents whether any dimensional records having a corresponding join key value not violating any local predicate of the query, wherein the bitmap is used in at least one of identifying the feedback record and joining the accessed fact records to the plurality of dimension tables.

13. The computer program product of claim 8, wherein the query specifies at least one payload column in a first dimension table, wherein the first dimension table includes a key column selected from a join key column densely storing values in a value range and a surrogate key column, wherein a payload column comprises a column other than the join key column and the key column, and wherein the computer-readable program code further comprises, prior to determining a respective set of dimension records from each dimension table:

computer-readable program code configured to store, in at least one of a table and an index, the key column and the payload column, wherein the key column includes a plurality of row identifiers of the first dimension table;

computer-readable program code configured to store, in an in-memory array, a plurality of buffer entries, each buffer entry comprising a join key value and an associated row identifier of the first dimension table; and

computer-readable program code configured to sort the plurality of buffer entries in the in-memory array, without sorting any records in the table, wherein the sorted buffer entries are ordered by the join key column and the surrogate key column;

wherein the sorted buffer entries are used in at least one of identifying the feedback record and joining the accessed fact records to the plurality of dimension tables.

14. The computer program product of claim 13, wherein the dimensional data model is selected from at least one of a star schema and a snowflake schema, and wherein the computer-readable program code further comprises:

computer-readable program code configured to generate an index for at least one join key value and associated row identifier not stored in the in-memory array, wherein the index comprises a B-tree, wherein the at least one join key value is further associated with a payload value, and wherein the associated payload value is stored in at least one of the index and the table.

15. A system, comprising:

one or more computer processors;

a memory containing a program, which when executed by the one or more computer processors is configured to perform an operation for processing a query against a dimensional data model, the dimensional data model comprising a fact table and a plurality of dimension tables, the operation comprising;

determining, from each dimension table, a respective set of dimension records satisfying any local predicates in the query pertaining to the respective dimension table;

from the fact table and based on the sets of dimension records, identifying, a set of row identifiers of fact records satisfying any join predicates and local predicates in the query, wherein the row identifier of each fact record is identified by joining a respective, distinct, concatenated dimension record to the fact table and applying any local predicates to the fact table, wherein each concatenated dimension record is generated by concatenating a join key value from each set of dimension records, wherein the join key values for generating at least a first concatenated dimension record are determined based on a feedback record, wherein the feedback record comprises at least a portion of a next ordered fact record succeeding a previously identified fact record; and

generating query results responsive to the query by joining, to the sets of dimension records, one or more fact records in the fact table selected based on the row identifiers.

16. The system of claim 15, wherein retrieval of one or more dimension payload columns is deferred until generating the query results, to facilitate data retrieval from the plurality of dimension tables, wherein the set of row identifiers is sorted according to an order in which data pages of the fact table are stored, to facilitate data retrieval from the fact table, and wherein the operation further comprises:

prior to generating the query results, prefetching at least a portion of a first data page.

17. The system of claim 15, wherein generating query results by joining, to the sets of dimension records, one or more fact records in the fact table selected based on the row identifiers comprises performing one or more consuming pushdown operations on the a data page of the fact table.

18. The system of claim 15, wherein the query does not specify any payload column in a first dimension table, wherein the first dimension table includes a surrogate key column, wherein a payload column comprises a column other than the join key column and the surrogate key column, wherein the first dimension table stores, in the surrogate key column, a range of surrogate key values between a minimum key value and a maximum key value.

19. The system of claim 18, wherein the operation further comprises, prior to determining a respective set of dimension records from each dimension table:

generating a bitmap having a count of bits greater than a difference between the maximum key value and the minimum key value, wherein each bit represents whether any dimensional records having a corresponding join key value not violating any local predicate of the query;

wherein the bitmap is used in at least one of identifying the feedback record and joining the accessed fact records to the plurality of dimension tables.

20. The system of claim 15, wherein the query specifies at least one payload column in a first dimension table, wherein the first dimension table includes a key column selected from a join key column densely storing values in a value range and a surrogate key column, wherein a payload column comprises a column other than the join key column and the key column, and wherein the operation further comprises, prior to determining a respective set of dimension records from each dimension table:

storing, in at least one of a table and an index, the key column and the payload column, wherein the key column includes a plurality of row identifiers of the first dimension table;

storing, in an in-memory array, a plurality of buffer entries, each buffer entry comprising a join key value and an associated row identifier of the first dimension table; and

sorting the plurality of buffer entries in the in-memory array, without sorting any records in the table, wherein the sorted buffer entries are ordered by the join key column and the surrogate key column;

wherein the sorted buffer entries are used in at least one of identifying the feedback record and joining the accessed fact records to the plurality of dimension tables.