Database system with methodology for generating bushy nested loop join trees

• US 7,882,100 B2
• Filed: 01/24/2005
• Issued: 02/01/2011
• Est. Priority Date: 01/24/2005
• Status: Active Grant

• Current Assignee: Sybase Incorporated (SAP SE)
• Original Assignee: Sybase Incorporated (SAP SE)
• Inventors: Andrei, Mihnea
• Primary Examiner(s): Ly; Cheyne D
• Application Number:
  US10/905,861
• Publication Number:
  US 20060167865A1
• Time in Patent Office: 2,199 Days
• Field of Search: 707 2- 3, 707/10, 707/714, 707/719, 707/797, 709/201
• US Class Current: 707/714
• CPC Class Codes: G06F 16/24544 Join order optimisation

Abstract

A database system with methodology for generating bushy nested loop join trees is described. In one embodiment, for example, an improved method is described for optimization of a query requesting data from a database, the method comprises steps of: generating a left deep operator tree for returning data requested by the query based on traversing a left deep operator tree search space; transforming the left deep operator tree into a semantically correct structure for returning data requested by the query; and building a query execution plan for returning data requested by the query based on the semantically correct structure.

Claims

1. An improved method for optimization of a query requesting data from a database, the method executed by a processor comprising:

generating a search space comprising only left deep nested loop join trees for returning data requested by the query;

traversing the search space to select an optimal left deep nested loop join tree for execution of the query;

after selection of an optimal left deep nested loop join tree including one or more outer joins and/or one or more semi-joins, transforming the selected left deep nested loop join tree into a semantically correct bushy tree structure for returning data requested by the query; and

building a query execution plan for returning data requested by the query based on the semantically correct bushy tree structure.

2. The method of claim 1, wherein said transforming step includes determining a portion of the left deep nested loop join tree requiring transformation into a bushy tree shape for generating a semantically correct query execution plan.

3. The method of claim 2, wherein said transforming step includes transforming said portion of the left deep nested loop join tree into a bushy tree shape.

4. The method of claim 2, wherein said portion of the left deep nested loop join tree requiring transformation includes a left deep nested loop join subtree.

5. The method of claim 2, wherein said portion of the left deep nested loop join tree requiring transformation includes a left deep semi-join subtree.

6. The method of claim 2, wherein said portion of the left deep nested loop join tree requiring transformation includes an outer join.

7. The method of claim 1, wherein said generating step includes substeps of:

generating subplans structured as left deep nested loop join subtrees for obtaining data requested by the query;

grouping said subplans into classes based on tables covered by each subplan; and

for each class, selecting a particular subplan having favorable execution costs.

8. The method of claim 7, wherein said generating step further comprises:

generating a left deep nested loop join tree based on combining particular subplans covering all tables from which the query requests data.

9. The method of claim 1, further comprising:

converting the query into a tree of logical operators.

10. The method of claim 9, wherein said generating step includes generating a left deep nested loop join tree comprising a tree of physical operators corresponding to the tree of logical operators.

11. The method of claim 9, wherein said generating step includes marking portions of the left deep nested loop join tree which require transformation to generate a semantically correct query execution plan equivalent to the tree of logical operators.

12. The method of claim 1, wherein said generating step includes identifying portions of the left deep nested loop join tree requiring transformation.

13. The method of claim 12, wherein said transforming step includes transforming identified portions of the left deep nested loop join tree.

14. A computer-readable storage medium having processor-executable instructions for performing a method for optimization of a query requesting data from a database, the method executed by a processor comprising:

generating a search space comprising only left deep nested loop join trees for returning data requested by the query;

traversing the tree search space to select an optimal left deep nested loop join tree for execution of the query;

after selection of an optimal left deep nested loop join tree including one or more outer joins and/or one or more semi-joins, transforming the selected left deep nested loop join tree into a semantically correct bushy tree structure for returning data requested by the query; and

building a query execution plan for returning data requested by the query based on the semantically correct bushy tree structure.

15. A system for optimization of a query requesting data from a database, the system comprising:

a computer having a processor and memory;

a search engine for generating a search space comprising only left deep nested loop join trees for returning data requested by the query and traversing the search space to select an optimal left deep nested loop join tree for execution of the query;

a transform module for transforming the left deep nested loop join tree selected by the search engine and including one or more outer joins and/or one or more semi-joins into a semantically correct bushy tree structure; and

a generator module for generating a query execution plan for returning data requested by the query based on the semantically correct bushy tree structure.

16. The system of claim 15, wherein the transform module identifies a portion of the left deep nested loop join tree requiring transformation into a bushy tree shape for generating a semantically correct query execution plan.

17. The system of claim 16, wherein the transform module transforms said portion of the left deep nested loop join tree into a bushy tree shape.

18. The system of claim 16, wherein said portion of the left deep nested loop join tree requiring transformation includes a left deep nested loop join subtree.

19. The system of claim 16, wherein said portion of the left deep nested loop join tree requiring transformation includes a left deep semi-join subtree.

20. The system of claim 16, wherein said portion of the left deep nested loop join tree requiring transformation includes an outer join.

21. The system of claim 15, wherein the search engine generates subplans structured as left deep nested loop join subtrees for obtaining data requested by the query.

22. The system of claim 21, wherein the search engine groups said subplans into classes based on tables covered by each subplan.

23. The system of claim 22, wherein the search engine builds a left deep nested loop join tree based on selecting a subplan having favorable execution costs from each class.

24. The system of claim 22, wherein the search engine builds a left deep nested loop join tree by combining subplans covering all tables from which the query requests data.

25. The system of claim 15, further comprising:

a module for converting the query into a tree of logical operators.

26. The system of claim 25, wherein the search engine generates a left deep nested loop join tree comprising a tree of physical operators corresponding to the tree of logical operators.

27. The system of claim 25, wherein the search engine identifies portions of the left deep nested loop join tree which require transformation to generate a semantically correct query execution plan equivalent to the tree of logical operators.

28. The system of claim 27, wherein the transform module transforms identified portions of the left deep nested loop join tree.

29. In a database system, a method for optimization of a query, the method executed by a processor comprising:

generating a search space comprising only left deep nested loop join subtree candidate subplans for executing the query;

building a plan for executing the query in the search space based on selecting candidate subplans having favorable execution costs;

after a plan has been built, determining whether any left deep nested loop join subtree of the plan should be transformed to a semantically correct bushy tree shape;

creating a transformed plan by transforming any left deep nested loop join subtrees determined to need transformation to a semantically correct bushy tree shape; and

constructing a query execution plan for executing the query based on the transformed plan.

30. The method of claim 29, wherein said generating step includes grouping said candidate subplans into classes based on tables covered by each candidate subplan and selecting a particular subplan in each class having lowest execution costs.

31. The method of claim 30, wherein said building step includes building a plan based on combining particular subplans covering all tables from which the query requests data.

32. The method of claim 30, wherein said building step includes building a left deep nested loop join tree comprising a tree of physical operators.

33. The method of claim 29, wherein said building step includes marking a left deep nested loop subtree requiring transformation to generate a semantically correct query execution plan.

34. The method of claim 33, wherein said determining step includes determining whether a left deep nested loop subtree should be transformed based on the marking.

35. The method of claim 29, wherein said determining step includes determining whether a left deep nested loop join subtree of the plan requires transformation to generate a semantically correct query execution plan.

36. The method of claim 29, wherein said creating step includes accumulating leaves of the left deep nested loop subtree to be transformed.

37. The method of claim 36, wherein said creating step includes generating join nodes for joining said leaves.

38. A computer-readable storage medium having processor-executable instructions for performing a method for optimization of a query, the method executed by a processor comprising;

generating a search space comprising only left deep nested loop join subtree candidate subplans for executing the query;

building a plan for executing the query in the search space based on selecting candidate subplans having favorable execution costs;

after a plan has been built, determining whether any left deep nested loop join subtree of the plan should be transformed to a semantically correct bushy tree shape;

creating a transformed plan by transforming any left deep nested loop join subtrees determined to need transformation to a semantically correct bushy tree shape; and

constructing a query execution plan for executing the query based on the transformed plan.

39. A system for optimization of a query requesting data from a database, the system comprising:

a computer having a processor and memory;

a search engine for generating a search comprising only left deep operators trees and traversing the search space to select an optimal left deep operator tree plan for returning data requested by the query;

a transform module for transforming the left deep operator tree selected by the search engine and including one or more outer joins and/or one or more semi-joins into a semantically correct bushy tree structure; and

a code generator for generating a query execution plan for returning data requested by the query based on the semantically correct bushy tree structure.

40. The system of claim 39, wherein the transform module transforms a left deep nested loop join subtree into a bushy subtree.

41. The system of claim 39, wherein the transform module transforms a left deep semi-join subtree into a bushy subtree.

42. The system of claim 39, wherein the transform module identifies a portion of the left deep operator tree requiring transformation into a bushy tree structure for generating a semantically correct query execution plan.

43. The system of claim 42, wherein the transform module transforms said portion of the left deep operator tree into a bushy tree shape.

44. The system of claim 42, wherein said portion of the left deep operator tree requiring transformation includes a nested loop join subtree.

45. The system of claim 42, wherein said portion of the left deep operator tree requiring transformation includes a semi-join subtree.

46. The system of claim 39, wherein the search engine generates subplans structured as left deep operator subtrees for obtaining data requested by the query.

47. The system of claim 46, wherein the search engine groups said subplans into classes based on tables covered by each subplan.

48. The system of claim 47, wherein the search engine builds a left deep operator tree based on selecting a subplan having favorable execution costs from each class.

49. The system of claim 47, wherein the search engine builds a left deep operator tree by combining subplans covering all tables from which the query requests data.

50. The system of claim 39, wherein the search engine marks portions of the left deep operator tree which require transformation to generate a semantically correct query execution plan.

51. The system of claim 39, wherein said transform module determines leaves of the left deep operator tree to be affected by transformation of the left deep operator tree.

52. The system of claim 51, wherein said transform module generates join nodes for joining said leaves.