Query optimizer with schema conversion

• US 8,086,598 B1
• Filed: 02/06/2009
• Issued: 12/27/2011
• Est. Priority Date: 08/02/2006
• Status: Expired due to Fees

• Current Assignee: Micro Focus LLC (Open Text Corporation)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Lamb, Andrew, Cherniack, Mitch, Lawande, Shilpa, Tran, Nga
• Primary Examiner(s): LEWIS, CHERYL RENEA
• Application Number:
  US12/367,415
• Time in Patent Office: 1,054 Days
• Field of Search: 707/606, 707/713, 707/714, 707/797
• US Class Current: 707/714
• CPC Class Codes: G06F 16/24544 Join order optimisation

Abstract

Methods, program products and systems for determining, for a database query that does not represent a snowflake schema, a graph comprising vertices each representing a table joined in the query, a directed edge between each pair of vertices of which a first vertex represents a first table and a second vertex represents a second table that is joined in the query with the first table, each of the edges representing one of an outer join and an inner join. Further determining, for the graph, a directed spanning tree that represents an ordering of joins in the query and includes all outer join edges in the graph.

Claims

1. A method comprising:

determining, for a database query that does not represent a snowflake schema, a graph comprising (a) vertices each representing a table joined in the query, (b) a directed edge between each pair of vertices of which a first vertex represents a first table and a second vertex represents a second table that is joined in the query with the first table, each of the edges representing one of an outer join and an inner join;

determining, for the graph, a directed spanning tree that (a) represents an ordering of joins in the query and includes all outer join edges in the graph, (b) does not include a first subtree having an outer join edge directed from a first vertex to a second vertex, and an inner join edge directed from the second vertex to a third vertex, (c) does not include a second subtree having an outer join edge directed from a fourth vertex to a fifth vertex, and another outer join edge directed from the fourth vertex to a sixth vertex; and

the spanning tree being a sufficient basis for a physical plan to obtain data records that satisfy the query.

2. The method of claim 1 in which determining the directed spanning tree comprises:

for a selected one of the vertices, determining the spanning tree for the graph that is rooted at the selected vertex.

3. The method of claim 2 comprising performing the method of claim 2 iteratively.

4. The method of claim 3 in which each selected vertex has an indegree of vertices that is less than or equal to an indegree of vertices for each of the vertices that have not been selected.

5. The method of claim 4 in which an indegree of vertices of the selected vertex is equal to an indegree of vertices of one of the vertices that has not been selected.

6. The method of claim 5 in which a table represented by the selected vertex has a cardinality that is greater than or equal to a cardinality for a table represented by each of the plurality of vertices that have not been selected.

7. The method of claim 1 where determining the directed spanning tree further comprises:

determining spanning trees for the graph in which each spanning tree is rooted at a same vertex in the graph; and

selecting a spanning tree from the spanning trees as the determined spanning tree, where the selected spanning tree satisfies the constraints and whose product of join selectivities of joins denoted by edges of the selected spanning tree is less than or equal to the corresponding selectivity products for unselected spanning trees.

8. The method of claim 1 where if the edge represents an inner join between the first table and the second table on a foreign key of the first table and a primary key of the second table, the edge is directed from the first vertex to the second vertex.

9. The method of claim 1 where if the edge represents an outer join between the first table and the second table, the edge is directed from the first vertex to the second vertex if the edge represents a left outer join, otherwise if the edge represents a right outer join, the edge is directed from the second vertex to the first vertex.

10. The method of claim 1, further comprising:

identifying one or more distinct snowflake schemas in the spanning tree;

determining, for each of the snowflake schemas, a respective access plan for obtaining data requested by the query for tables represented by vertices in the snowflake schema; and

obtaining the data by executing each snowflake schema'"'"'s respective access plan.

11. A computer program product, encoded on a computer-readable medium, operable to cause data processing apparatus to perform operations comprising:

determining, for a database query that does not represent a snowflake schema, a graph comprising (a) vertices each representing a table joined in the query, (b) a directed edge between each pair of vertices of which a first vertex represents a first table and a second vertex represents a second table that is joined in the query with the first table, each of the edges representing one of an outer join and an inner join;

determining, for the graph, a directed spanning tree that (a) represents an ordering of joins in the query and includes all outer join edges in the graph, (b) does not include a first subtree having an outer join edge directed from a first vertex to a second vertex, and an inner join edge directed from the second vertex to a third vertex, (c) does not include a second subtree having an outer join edge directed from a fourth vertex to a fifth vertex, and another outer join edge directed from the fourth vertex to a sixth vertex; and

the spanning tree being a sufficient basis for a physical plan to obtain data records that satisfy the query.

12. The program product of claim 11 in which determining the directed spanning tree comprises:

for a selected one of the vertices, determining the spanning tree for the graph that is rooted at the selected vertex.

13. The program product of claim 12 in which each selected vertex has an indegree of vertices that is less than or equal to an indegree of vertices for each of the vertices that have not been selected.

14. The program product of claim 13 in which an indegree of vertices of the selected vertex is equal to an indegree of vertices of one of the vertices that has not been selected.

15. The program product of claim 14 in which a table represented by the selected vertex has a cardinality that is greater than or equal to a cardinality for a table represented by each of the plurality of vertices that have not been selected.

16. The program product of claim 11 where determining the directed spanning tree further comprises:

determining spanning trees for the graph in which each spanning tree is rooted at a same vertex in the graph; and

selecting a spanning tree from the spanning trees as the determined spanning tree, where the selected spanning tree satisfies the constraints and whose product of join selectivities of joins denoted by edges of the selected spanning tree is less than or equal to the corresponding selectivity products for unselected spanning trees.

17. The program product of claim 11 where if the edge represents an inner join between the first table and the second table on a foreign key of the first table and a primary key of the second table, the edge is directed from the first vertex to the second vertex.

18. The program product of claim 11 where if the edge represents an outer join between the first table and the second table, the edge is directed from the first vertex to the second vertex if the edge represents a left outer join, otherwise if the edge represents a right outer join, the edge is directed from the second vertex to the first vertex.

19. The program product of claim 11, including operations further comprising:

identifying one or more distinct snowflake schemas in the spanning tree;

determining, for each of the snowflake schemas, a respective access plan for obtaining data requested by the query for tables represented by vertices in the snowflake schema; and

obtaining the data by executing each snowflake schema'"'"'s respective access plan.

20. A system comprising:

a machine-readable storage device including a program product; and

one or more processors configured to interact with the storage device, execute the program product and perform operations comprising;

determining, for a database query that does not represent a snowflake schema, a graph comprising (a) vertices each representing a table joined in the query, (b) a directed edge between each pair of vertices of which a first vertex represents a first table and a second vertex represents a second table that is joined in the query with the first table, each of the edges representing one of an outer join and an inner join;

determining, for the graph, a directed spanning tree that (a) represents an ordering of joins in the query and includes all outer join edges in the graph, (b) does not include a first subtree having an outer join edge directed from a first vertex to a second vertex, and an inner join edge directed from the second vertex to a third vertex, (c) does not include a second subtree having an outer join edge directed from a fourth vertex to a fifth vertex, and another outer join edge directed from the fourth vertex to a sixth vertex; and

the spanning tree being a sufficient basis for a physical plan to obtain data records that satisfy the query.

21. The system of claim 20 in which determining the directed spanning tree comprises:

for a selected one of the vertices, determining the spanning tree for the graph that is rooted at the selected vertex.

22. The system of claim 21 in which each selected vertex has an indegree of vertices that is less than or equal to an indegree of vertices for each of the vertices that have not been selected.

23. The system of claim 22 in which an indegree of vertices of the selected vertex is equal to an indegree of vertices of one of the vertices that has not been selected.

24. The system of claim 23 in which a table represented by the selected vertex has a cardinality that is greater than or equal to a cardinality for a table represented by each of the plurality of vertices that have not been selected.

25. The system of claim 20 where determining the directed spanning tree further comprises:

determining spanning trees for the graph in which each spanning tree is rooted at a same vertex in the graph; and

selecting a spanning tree from the spanning trees as the determined spanning tree, where the selected spanning tree satisfies the constraints and whose product of join selectivities of joins denoted by edges of the selected spanning tree is less than or equal to the corresponding selectivity products for unselected spanning trees.

26. The system of claim 20 where if the edge represents an inner join between the first table and the second table on a foreign key of the first table and a primary key of the second table, the edge is directed from the first vertex to the second vertex.

27. The system of claim 20 where if the edge represents an outer join between the first table and the second table, the edge is directed from the first vertex to the second vertex if the edge represents a left outer join, otherwise if the edge represents a right outer join, the edge is directed from the second vertex to the first vertex.

28. The system of claim 20, including operations further comprising:

identifying one or more distinct snowflake schemas in the spanning tree;

determining, for each of the snowflake schemas, a respective access plan for obtaining data requested by the query for tables represented by vertices in the snowflake schema; and

obtaining the data by executing each snowflake schema'"'"'s respective access plan.