Multi-fact query processing in data processing system

• US 8,589,382 B2
• Filed: 12/29/2011
• Issued: 11/19/2013
• Est. Priority Date: 12/29/2011
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Betawadkar-Norwood, Anjali, Lin, Eileen Tien, Tran, Tam Minh Dai
• Primary Examiner(s): Woo, Isaac M
• Application Number:
  US13/340,288
• Publication Number:
  US 20130173528A1
• Time in Patent Office: 691 Days
• Field of Search: 707600-899
• US Class Current: 707/713
• CPC Class Codes: G06F 16/24535 of sub-queries or views

Abstract

Techniques are described for optimizing a multi-fact star schema query to retrieve data from two or more fact tables of a database. The optimization techniques may include internally transforming a received multi-fact star schema query into a group of single-fact sub-queries, thereby reducing or eliminating certain constraints during query processing. The group of sub-queries may be enumerated to determine a query execution plan. The multi-fact star schema query may be executed according to the query execution plan to retrieve the data from the two or more fact tables of the database.

Claims

1. A method comprising:

receiving, by a query optimizer executing on one or more processors of a computing device, a multi-fact star schema query that is executable to retrieve data from two or more fact tables of a database, wherein the two or more fact tables each references a common dimension table of the database;

internally transforming, by the query optimizer, the multi-fact star schema query into a group of single-fact sub-queries, wherein each sub-query of the group of single-fact sub-queries references only one of the two or more fact tables;

enumerating, by the query optimizer, the group of single-fact sub-queries to determine a query execution plan; and

executing, by a runtime execution engine executing on the one or more processors, the multi-fact star schema query according to the query execution plan to retrieve the data from the two or more fact tables of the database.

2. The method of claim 1, wherein internally transforming the multi-fact star schema query into the group of single-fact sub-queries is performed responsive to:

(i) determining that the multi-fact star schema query equi-joins the common dimension table and each of the two or more fact tables on a common joining column of the common dimension table, wherein the common joining column comprises one or more data values; and

(ii) determining that each of the one or more data values of the joining column of the common dimension table are unique within the joining column.

3. The method of claim 1, wherein enumerating the group of single-fact sub-queries further comprises:

determining a set of join combinations, each of the join combinations having a first join partition and a second join partition, wherein the first and second join partitions each comprise a reference to at least one of the two or more fact tables of the multi-fact star schema query;

generating candidate query execution plans for one or more of the set of join combinations; and

selecting, based on decision criteria, one of the candidate query execution plans for executing the multi-fact star schema query.

4. The method of claim 3, wherein the first and second join partitions each comprise a reference to the common dimension table.

5. The method of claim 3, wherein generating the candidate query execution plans comprises:

for each of the join combinations;

determining an intersection of the first and second join partitions, wherein the intersection comprises references to one or more dimension tables of the database that are common to both the first join partition and the second join partition; and

generating the candidate query execution plan for the respective join combination based on the intersection of the first and second join partitions.

6. The method of claim 5, further comprising, when the intersection comprises an empty set, generating the candidate query execution plan for the respective join combination responsive to:

(i) determining that a star schema-specific candidate query execution plan has been generated for each of the first and second join partitions; and

(ii) determining that an inner of a join of the first and second join partitions does not exceed an dynamic programming inner join limit.

7. The method of claim 5, further comprising, when the intersection does not comprise an empty set, generating the candidate query execution plan for the respective join combination responsive to:

for each of the one or more dimension tables of the database that are common to both the first join partition and the second join partition;

(i) determining that the received multi-fact star schema query joins the respective dimension table with each of the two or more fact tables of the multi-fact star schema query; and

(ii) determining that the respective dimension table is referenced in both the first and second join partitions as a dimension table.

8. A computer-readable storage medium encoded with instructions that, when executed, cause one or more processors of a computing device to:

receive, by a query optimizer executing on the processor, a multi-fact star schema query that is executable to retrieve data from two or more fact tables of a database, wherein the two or more fact tables each references a common dimension table of the database;

internally transform, by the query optimizer, the multi-fact star schema query into a group of single-fact sub-queries, wherein each sub-query of the group of single-fact sub-queries references only one of the two or more fact tables;

enumerate, by the query optimizer, the group of single-fact sub-queries to determine a query execution plan; and

execute, by a runtime execution engine, the multi-fact star schema query according to the query execution plan to retrieve the data from the two or more fact tables of the database.

9. The computer-readable storage medium of claim 8, wherein the instructions to internally transform the multi-fact star schema query into the group of single-fact sub-queries further comprise instructions to internally transform responsive to:

(i) determining that the multi-fact star schema query equi-joins the common dimension table and each of the two or more fact tables on a common joining column of the common dimension table, wherein the common joining column comprises one or more data values; and

(ii) determining that each of the one or more data values of the joining column of the common dimension table are unique within the joining column.

10. The computer-readable storage medium of claim 8, wherein the instructions to enumerate the group of single-fact sub-queries further comprise instructions to:

determine a set of join combinations, each of the join combinations having a first join partition and a second join partition, wherein the first and second join partitions each comprise a reference to at least one of the two or more fact tables of the multi-fact star schema query;

generate candidate query execution plans for one or more of the set of join combinations; and

select, based on decision criteria, one of the candidate query execution plans for executing the multi-fact star schema query.

11. The computer-readable storage medium of claim 10, wherein the first and second join partitions each comprise a reference to the common dimension table.

12. The computer-readable storage medium of claim 10, wherein the instructions to generate the candidate query execution plans further comprise instructions to:

for each of the join combinations;

determine an intersection of the first and second join partitions, wherein the intersection comprises references to one or more dimension tables of the database that are common to both the first join partition and the second join partition; and

generate the candidate query execution plan for the respective join combination based on the intersection of the first and second join partitions.

13. The computer-readable storage medium of claim 12, further comprising instructions to:

when the intersection comprises an empty set, generate the candidate query execution plan for the respective join combination responsive to;

(i) determining that a star schema-specific candidate query execution plan has been generated for each of the first and second join partitions; and

(ii) determining that an inner of a join of the first and second join partitions does not exceed an dynamic programming inner join limit.

14. The computer-readable storage medium of claim 12, further comprising instructions to:

when the intersection does not comprise an empty set, generate the candidate query execution plan for the respective join combination responsive to;

for each of the one or more dimension tables of the database that are common to both the first join partition and the second join partition;

(i) determining that the received multi-fact star schema query joins the respective dimension table with each of the two or more fact tables of the multi-fact star schema query; and

(ii) determining that the respective dimension table is referenced in both the first and second join partitions as a dimension table.

15. A computing device, comprising:

one or more processors;

a query optimizer executable by the one or more processors to receive a multi-fact star schema query that is executable to retrieve data from two or more fact tables of a database, wherein the two or more fact tables each references a common dimension table of the database;

a multi-fact transformation engine executable by the one or more processors to internally transform the multi-fact star schema query into a group of single-fact sub-queries, wherein each sub-query of the group of single-fact sub-queries references only one of the two or more fact tables;

an optimizer join enumerator executable by the one or more processors to enumerate the group of single-fact sub-queries to determine a query execution plan; and

a runtime execution engine executable by the one or more processors to execute the multi-fact star schema query according to the query execution plan to retrieve the data from the two or more fact tables of the database.

16. The computing device of claim 15, wherein the multi-fact transformation engine is further executable by the one or more processors to internally transform the multi-fact star schema query into the group of single-fact sub-queries responsive to:

(i) determining that the multi-fact star schema query equi-joins the common dimension table and each of the two or more fact tables on a common joining column of the dimension table, wherein the common joining column comprises one or more data values; and

(ii) determining that each of the one or more data values of the joining column of the common dimension table are unique within the joining column.

17. The computing device of claim 15, wherein the optimizer join enumerator is further executable by the one or more processors to:

determine a set of join combinations, each of the join combinations having a first join partition and a second join partition, wherein the first and second join partitions each comprise a reference to at least one of the two or more fact tables of the multi-fact star schema query;

generate candidate query execution plans for one or more of the set of join combinations; and

select, based on decision criteria, one of the candidate query execution plans for executing the multi-fact star schema query.

18. The computing device of claim 17, wherein the optimizer join enumerator is further executable by the one or more processors to generate the candidate query execution plans by:

for each of the join combinations;

determining an intersection of the first and second join partitions, wherein the intersection comprises references to one or more dimension tables of the database that are common to both the first join partition and the second join partition; and

generating the candidate query execution plan for the respective join combination based on the intersection of the first and second join partitions.

19. The computing device of claim 18, wherein the optimizer join enumerator is further executable by the one or more processors to:

when the intersection comprises an empty set, generate the candidate query execution plan for the respective join combination responsive to;

(i) determining that a star schema-specific candidate query execution plan has been generated for each of the first and second join partitions; and

(ii) determining that an inner of a join of the first and second join partitions does not exceed an dynamic programming inner join limit.

20. The computing device of claim 18, wherein the optimizer join enumerator is further executable by the one or more processors to:

when the intersection does not comprise an empty set, generate the candidate query execution plan for the respective join combination responsive to;

for each of the one or more dimension tables of the database that are common to both the first join partition and the second join partition;

(i) determining that the received multi-fact star schema query joins the respective dimension table with each of the two or more fact tables of the multi-fact star schema query; and

(ii) determining that the respective dimension table is referenced in both the first and second join partitions as a dimension table.