Techniques for bushy tree execution plans for snowstorm schema

• US 8,438,152 B2
• Filed: 10/29/2007
• Issued: 05/07/2013
• Est. Priority Date: 10/29/2007
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Ahmed, Rafi
• Primary Examiner(s): Smith, Brannon W
• Application Number:
  US11/927,324
• Publication Number:
  US 20090112793A1
• Time in Patent Office: 2,017 Days
• Field of Search: 707/714, 707/999.002
• US Class Current: 707/714
• CPC Class Codes: G06F 16/2456 Join operations

Abstract

Methods for transforming a query to simulate a bushy tree execution plan for queries containing joins in series are provided. Left deep tree execution plans are supported by most relational database systems but are inefficient at processing queries directed to databases with snowstorm schema. A snowstorm schema contains several large fact tables and many smaller dimension tables, which make reference to one another. Bushy tree execution plans can be much more efficient for processing queries to snowstorm schema. The decision to choose between left-deep and bushy tree execution plans are based on the relative costs of the two execution plans. The methods provided transform queries which are otherwise executed with left deep tree execution plans into queries which are executed with simulated bushy tree execution plans.

Claims

1. A computer-implemented method, comprising steps of:

in response to determining that a particular query refers to one or more fact tables and one or more dimension tables, generating a transformed query based on the particular query to force a bushy tree execution to compute the results for the particular query;

wherein the particular query specifies at least three join predicates;

wherein the at least three join predicates include a first join predicate, a second join predicate, and a third join predicate;

wherein a table referenced in the first join predicate is also referenced in the second join predicate;

wherein a table referenced in the second join predicate is also referenced in the third join predicate;

wherein generating the transformed query includes;

enclosing, in an unmergeable view, a join operation based on the third join predicate;

modifying the second join predicate to reference the unmergeable view;

determining a first execution cost of the transformed query, wherein determining the first execution cost includes generating and evaluating at least one execution plan for computing the transformed query;

determining a second execution cost of at least one version of the particular query, said version of the particular query being either (1) the particular query or (2) another transformed query based on the particular query, wherein determining the second execution cost includes generating and evaluating at least one execution plan of said at least one version of the particular query;

performing a comparison of the first execution cost of the transformed query and the second execution cost of said at least one version of the particular query;

based on the comparison, selecting the transformed query as an optimized version of the particular query; and

wherein the steps are performed by one or more computing devices in response to executing the code of a query optimizer.

2. The computer-implemented method of claim 1, wherein the step of generating the transformed query is performed in response to determining that a particular set of criteria are met.

3. The computer-implemented method of claim 2, wherein the particular set of criteria includes:

a table referenced in the first join predicate is bigger than a first threshold size,

a table referenced in the first join predicate is smaller than a second threshold size,

a table referenced in the third join predicate is bigger than the first threshold size, and

a table referenced in the third join predicate is smaller than the second threshold size.

4. The computer-implemented method of claim 2, wherein the particular set of criteria includes:

joins referenced in the particular query forming a particular configuration.

5. The computer-implemented method of claim 4, wherein the particular configuration includes a join between a fact table and a plurality of dimension tables.

6. The computer-implemented method of claim 4, wherein the particular configuration includes:

(1) a plurality of fact tables;

(2) at least one join between a fact table in the plurality of fact tables and a plurality of dimension tables; and

(3) at least one join between a first fact table in the plurality of fact tables and a second fact table in the plurality of fact tables.

7. The computer-implemented method of claim 1, wherein the step of generating the transformed query further includes:

enclosing, in a second unmergeable view, a join operation based on the third join predicate; and

modifying the second join predicate to reference the second unmergeable view.

8. A non-transitory computer-readable storage medium storing instructions, wherein the instructions include instructions which, when executed by one or more processors, cause the one or more processors to perform steps comprising:

in response to determining that a particular query refers to one or more fact tables and one or more dimension tables, generating a transformed query based on a particular query to force a bushy tree execution to compute the results for the particular query;

wherein the particular query specifies at least three join predicates;

wherein the at least three join predicates include a first join predicate, a second join predicate, and a third join predicate;

wherein a table referenced in the first join predicate is also referenced in the second join predicate;

wherein a table referenced in the second join predicate is also referenced in the third join predicate;

wherein generating the transformed query includes;

enclosing, in an unmergeable view, a join operation based on the third join predicate;

modifying the second join predicate to reference the unmergeable view;

determining a first execution cost of the transformed query, wherein determining the first execution cost includes generating and evaluating at least one execution plan for computing the transformed query;

determining a second execution cost of at least one version of the particular query, said version of the particular query being either (1) the particular query or (2) another transformed query based on the particular query, wherein determining the second execution cost includes generating and evaluating at least one execution plan of said at least one version of the particular query;

performing a comparison of the first execution cost of the transformed query and the second execution cost of said at least one version of the particular query;

based on the comparison, selecting the transformed query as an optimized version of the particular query; and

wherein the steps are performed by one or more computing devices in response to executing the code of a query optimizer.

9. The computer-readable storage medium of claim 8, wherein the step of generating the transformed query is performed in response to determining that a particular set of criteria are met.

10. The computer-readable storage medium of claim 9, wherein the particular set of criteria includes:

a table referenced in the first join predicate is bigger than a first threshold size,

a table referenced in the first join predicate is smaller than a second threshold size,

a table referenced in the third join predicate is bigger than the first threshold size, and

a table referenced in the third join predicate is smaller than the second threshold size.

11. The computer-readable storage medium of claim 9, wherein the particular set of criteria includes:

joins referenced in the particular query forming a particular configuration.

12. The computer-readable storage medium of claim 11, wherein the particular configuration includes a join between a fact table and a plurality of dimension tables.

13. The computer-readable storage medium of claim 11, wherein the particular configuration includes:

(1) a plurality of fact tables;

(2) at least one join between a fact table in the plurality of fact tables and a plurality of dimension tables; and

(3) at least one join between a first fact table in the plurality of fact tables and a second fact table in the plurality of fact tables.

14. The computer-readable storage medium of claim 8, wherein the step of generating the transformed query further includes:

enclosing, in a second unmergeable view, a join operation based on the third join predicate; and

modifying the second join predicate to reference the second unmergeable view.