Database System with Methodology for Generating Bushy Nested Loop Join Trees

• US 20060167865A1
• Filed: 01/24/2005
• Published: 07/27/2006
• Est. Priority Date: 01/24/2005
• Status: Active Grant

• Current Assignee: Sybase Incorporated (SAP SE)
• Original Assignee: Sybase Incorporated (SAP SE)
• Inventors: Andrei, Mihnea
• Granted Patent: US 7,882,100 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 comprising:

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.

2. The method of claim 1, wherein said transforming step includes determining a portion of the left deep operator 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 operator tree into a bushy tree shape.

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

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

6. The method of claim 2, wherein said portion of the left deep operator 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 operator 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 operator 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 operator 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 operator 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 operator tree requiring transformation.

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

14. A computer-readable medium having processor-executable instructions for performing the method of claim 1.

15. A downloadable set of processor-executable instructions for performing the method of claim 1.

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

a search engine for building a left deep operator tree for returning data requested by the query based on traversing a left deep operator tree search space;

a transform module for transforming the left deep operator tree into a semantically correct tree structure; and

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

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

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

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

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

21. The system of claim 17, wherein said portion of the left deep operator tree requiring transformation includes an outer join.

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

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

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

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

26. The system of claim 16, further comprising:

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

27. The system of claim 26, wherein the search engine generates a left deep operator tree comprising a tree of physical operators corresponding to the tree of logical operators.

28. The system of claim 26, wherein the search engine identifies portions of the left deep operator tree which require transformation to generate a semantically correct query execution plan equivalent to the tree of logical operators.

29. The system of claim 28, wherein the transform module transforms identified portions of the left deep operator tree.

30. In a database system, a method for optimization of a query, the method comprising:

generating a plurality of candidate subplans for executing the query, with at least some of said candidate subplans structured as left deep nested loop join subtrees;

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

determining whether any left deep nested loop join subtree of the plan should be transformed to a bushy tree shape;

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

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

31. The method of claim 30, 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.

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

33. The method of claim 31, wherein said building step includes building a left deep operator tree comprising a tree of physical operators.

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

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

36. The method of claim 30, 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.

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

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

39. A computer-readable medium having processor-executable instructions for performing the method of claim 30.

40. A downloadable set of processor-executable instructions for performing the method of claim 30.

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

a search engine for traversing a left deep operator tree search space and generating a left deep operator tree plan for returning data requested by the query;

a transform module for transforming the left deep operator tree into a bushy tree structure; and

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

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

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

44. The system of claim 41, 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.

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

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

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

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

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

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

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

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

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

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