Optimizing snowflake schema queries

• US 8,671,091 B2
• Filed: 08/02/2006
• Issued: 03/11/2014
• Est. Priority Date: 08/02/2006
• Status: Active Grant

• Current Assignee: Micro Focus LLC (Open Text Corporation)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Cherniack, Mitch, Lawande, Shilpa, Tran, Nga
• Primary Examiner(s): Ly, Cheyne D
• Application Number:
  US11/461,937
• Publication Number:
  US 20080033914A1
• Time in Patent Office: 2,778 Days
• Field of Search: 707/606, 707/714, 707/791
• US Class Current: 707/714
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: G06F 16/24544 Join order optimisation
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP

Abstract

For a database query that defines a plurality of separate snowflake schemas, a query optimizer computes separately for each of the snowflake schemas a logical access plan for obtaining from that schema'"'"'s tables a respective record set that includes the data requested from those tables by that query. The query optimizer also computes a logical access plan for obtaining the query'"'"'s results from the record sets in which execution of the logical access plans thus computed will result.

Claims

1. A method comprising:

receiving inputs that represent a query and that, applied to a database, define independent snowflake schemas in which each snowflake schema includes one or more pairs of join tables from the query;

generating a subquery for each snowflake schema in which the subquery contains one or more join predicates that involve one or more attributes from one or more join tables of the snowflake schema;

computing, by a computing system, for each of the generated subqueries, an access plan for obtaining from one or more tables of the subquery'"'"'s snowflake schema data requested by the subquery;

executing the access plans to obtain each subquery'"'"'s results;

generating an anchor query that joins the results produced by the generated subqueries into a result equivalent to a result produced by the query; and

generating a logical plan for the anchor query that uses the results of the generated subqueries as table inputs of the logical plan.

2. The method of claim 1, wherein computing the access plan for a subquery in the generated subqueries comprises computing, separately for each of the one or more tables whose snowflake degree in the subquery'"'"'s snowflake schema exceeds zero, a respective access plan for obtaining the data requested by the subquery from each of the one or more tables whose snowflake degree in the subquery'"'"'s snowflake schema exceeds zero.

3. The method as defined in claim 1, wherein the database comprises a column store.

10. The method of claim 2, wherein each of the one or more tables whose snowflake degree in the subquery'"'"'s snowflake schema exceeds zero is treated as a fact table of a star schema and the method comprises treating as a dimension table of that star schema any snowflake-degree-zero table directly reachable from each of the one or more tables whose snowflake degree in the subquery'"'"'s snowflake schema exceeds zero.

11. The method of claim 2, wherein each of the one or more tables whose snowflake degree in the subquery'"'"'s snowflake schema exceeds zero is treated as a fact table of a star schema and the method comprises treating as a dimension table of that star schema any results from execution of the access plan determined for each table of snowflake degree greater than zero that is directly reachable from the one or more tables whose snowflake degree in the subquery'"'"'s snowflake schema exceeds zero.

12. The method of claim 1, wherein each subquery'"'"'s respective access plan is selected based on a consideration of a space of self-similar left-deep trees defined by primary-key/foreign-key relationships among tables in the subquery'"'"'s snowflake schema.

13. The method of claim 12, wherein each snowflake schema'"'"'s respective access plan is selected based on evaluation of the space in view of the projections provided by the database'"'"'s physical layout.

24. The method of claim 1, wherein the access plan for each of the generated subqueries is associated with projections of the database'"'"'s physical layout, and wherein attribute values of the projections are stored in the physical layout according to respective sort orders of the projections, the access plan being for use in obtaining the results of the subquery.

4. A system comprising:

one or more processors; and

computer readable storage comprising instructions that are to cause the one or more processors to;

accept input signals that represent a query that, applied to the database, define a plurality of independent snowflake schemas in which each snowflake schema includes one or more pairs of join tables from the query;

generate a subquery for each snowflake schema in which the subquery contains one or more join predicates that involve one or more attributes from one or more join tables of the snowflake schema;

compute, for each of the generated subqueries, an access plan for obtaining from one or more tables of the subquery'"'"'s snowflake schema data requested by the subquery;

execute the access plans to obtain each subquery'"'"'s results;

generate an anchor query that joins the results produced by the subqueries into a result equivalent to a result produced by the query; and

generate a logical plan for the anchor query that uses the results of the generated subqueries as table inputs of the logical plan.

5. The system of claim 4, wherein, to compute the access plan for a subquery in the generated subqueries, the instructions are further to cause the one or more processors to compute, separately for each of the one or more tables whose snowflake degree in the first subquery'"'"'s snowflake schema exceeds zero, a respective access plan for obtaining the data requested by the subquery from each of the one or more tables whose snowflake degree in the subquery'"'"'s snowflake schema exceeds zero.

6. The system of claim 4, wherein the database comprises a column store.

14. The system of claim 5, wherein each of the one or more tables whose snowflake degree in the subquery'"'"'s snowflake schema exceeds zero is treated as a fact table of a star schema and the instructions are further to cause the one or more processors to treat as a dimension table of that star schema any snowflake-degree-zero table directly reachable from the one or more tables whose snowflake degree in the subquery'"'"'s schema exceeds zero.

15. The system of claim 5, wherein each of the one or more tables whose snowflake degree in the subquery'"'"'s snowflake schema exceeds zero is treated as a fact table of a star schema and the instructions are further to cause the one or more processors to treat as a dimension table of that star schema any result from execution of the access plan determined for each table of snowflake degree greater than zero that is directly reachable from the one or more tables whose snowflake degree in the subquery'"'"'s schema exceeds zero.

16. The system of claim 4, wherein each snowflake schema'"'"'s respective access plan is selected based on a consideration of a space of self-similar left-deep trees defined by primary-key/foreign-key relationships among tables in the snowflake schema.

17. The system of claim 16, wherein each snowflake schema'"'"'s respective access plan is selected based on evaluation of the space in view of the projections provided by the database'"'"'s physical layout.

18. The system of claim 4, wherein each snowflake schema includes one or more pairs of join tables from the query such that a first table in each pair is reachable from a second table in the pair.

25. The system of claim 4, wherein the access plan for each of the generated subqueries is associated with projections of the database'"'"'s physical layout, and wherein attribute values of the projections are stored in the physical layout according to respective sort orders of the projections, the access plan being for use in obtaining the results of the subquery.

7. A non-transitory computer readable storage medium containing machine readable instructions readable by a computer system that, when executed by the computer system, perform a method, said machine readable instructions comprising code to cause the computer system to:

accept input signals that represent a query that, applied to the database, defines a plurality of independent snowflake schemas in which each snowflake schema includes one or more pairs of join tables from the query;

generate a subquery for each snowflake schema in which the subquery contains one or more join predicates that involve one or more attributes from one or more join tables of the snowflake schema;

compute, for each of the generated subqueries, an access plan for obtaining from one or more tables of the subquery'"'"'s snowflake schema data requested by the subquery, in which the access plan is associated with projections of the database'"'"'s physical layout, in which the attribute values of the projections are stored in the physical layout according to respective sort orders of the projections, the access plan being for use in obtaining the results of the subqueries;

execute the access plans for to obtain each subquery'"'"'s results;

generate an anchor query that joins the results produced by the subqueries into a result equivalent to a result produced by the query; and

generate a logical plan for the anchor query that uses the results of the generated subqueries as table inputs of the logical plan.

8. The non-transitory computer readable storage medium of claim 7, said machine readable instructions further comprising code to cause the computer system to:

compute, separately for each of the one or more tables whose snowflake degree in the subquery'"'"'s snowflake schema exceeds zero, a respective access plan for obtaining the data requested by the query from each of the one or more tables whose snowflake degree in the subquery'"'"'s snowflake schema exceeds zero.

9. The non-transitory computer readable storage medium of claim 7, wherein the database comprises a column store.

19. The non-transitory computer readable storage medium of claim 8, wherein each of the one or more tables whose snowflake degree in the subquery'"'"'s snowflake schema exceeds zero is treated as a fact table of a star schema and any snowflake-degree-zero table directly reachable from the one or more tables whose snowflake degree in the subquery'"'"'s snowflake schema exceeds zero is treated as a dimension table of that star schema.

20. The non-transitory computer readable storage medium of claim 8, wherein each of the one or more tables whose snowflake degree in the subquery'"'"'s snowflake schema exceeds zero is treated as a fact table of a star schema and any result from execution of the access plan determined for each table of snowflake degree greater than zero that is directly reachable from the one or more tables whose snowflake degree in the subquery'"'"'s snowflake schema exceeds zero is treated as a dimension table of that star schema.

21. The non-transitory computer readable storage medium of claim 7, wherein each snowflake schema'"'"'s respective access plan is selected based on a consideration of a space of self-similar left-deep trees defined by primary-key/foreign-key relationships among tables in the snowflake schema.

22. The non-transitory computer readable storage medium of claim 21, wherein each snowflake schema'"'"'s respective access plan is selected based on evaluation of the space in view of the projections provided by the database'"'"'s physical layout.

23. The non-transitory computer readable storage medium of claim 7, wherein each snowflake schema includes one or more pairs of join tables from the query such that a first table in each pair is reachable from a second table in the pair.