Database system providing methodology for eager and opportunistic property enforcement

• US 20030172059A1
• Filed: 10/30/2002
• Published: 09/11/2003
• Est. Priority Date: 03/06/2002
• Status: Active Grant

• Current Assignee: Sybase Incorporated (SAP SE)
• Original Assignee: Sybase Incorporated (SAP SE)
• Inventors: Andrei, Mihnea
• Granted Patent: US 6,801,905 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: G06F 16/24537 of operators
• CPC Class Codes: G06F 16/24554 Unary operations; Data partitioning operations
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

A database system providing methods for eager and opportunistic property enforcement is described. Plan fragments are generated for obtaining data requested by a query. Plan fragments are grouped together in classes based upon tables of the database covered by each plan fragment. For each class, a particular plan fragment having the lowest execution costs for obtaining the data requested by the query is determined. If grouping is not required at a given class, an operator enforcing ordering is added to this particular sub-plan. However, if grouping is required at the given class, an operator enforcing both grouping and ordering is added to this sub-plan.

Claims

1. In a database system, a method for eager ordering enforcement enabling improved query optimization, the method comprising:

receiving a query requesting data from a database, said query requesting ordering of data;

generating plan fragments for obtaining data requested by the query;

grouping said plan fragments into classes, said classes based upon tables of the database covered by each plan fragment;

for each class, determining a particular plan fragment having the lowest execution costs for obtaining data; and

adding any required ordering enforcement operator to said particular plan fragment.

2. The method of claim 1, wherein said query requesting ordering of data includes a Structured Query Language (SQL) query.

3. The method of claim 1, wherein ordering enforcement includes sorting.

4. The method of claim 1, wherein said required ordering enforcement operator includes a SORT operator.

5. The method of claim 1, further comprising:

converting the query into a tree of logical operators.

6. The method of claim 5, wherein said step of converting the query into a tree of logical operators includes determining orderings of data required by the query.

7. The method of claim 1, further comprising:

generating a query execution plan based upon combining said particular plan fragments covering all tables from which the query requests data.

8. The method of claim 1, further comprising:

generating a tree of physical operators based upon combining said particular plan fragments.

9. The method of claim 1, further comprising:

pruning plan fragments not having the lowest execution costs from each class.

10. The method of claim 1, further comprising:

pruning plan fragments not having the lowest execution costs and not providing a needed ordering from each class.

11. The method of claim 1, wherein said step of adding any required ordering enforcement operator includes adding a grouping and ordering enforcement operator to said particular plan fragment if grouping and ordering are needed at a class.

12. The method of claim 1, wherein said step of adding any required ordering enforcement operator includes adding the strongest available enforcement operator.

13. The method of claim 1, wherein said step of adding any required ordering enforcement operator includes determining whether said required ordering is already provided by said particular plan fragment.

14. The method of claim 1, wherein said step of adding any required ordering enforcement operator includes adding a set ordering enforcement operator for use during optimization of the query.

16. The method of claim 1, wherein said step of generating plan fragments for obtaining data requested by the query includes using a depth-first, bottom-up search engine.

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

18. A downloadable set of computer-executable instructions for performing the method of claim 1.

25. The method of claim 18, further comprising:

generating a tree of physical operators based upon combining said particular plan fragments.

15. The method of claim 15, wherein said set ordering operator is subsequently converted into an appropriate physical operator required by the query.

19. In a database system, a method for eager and opportunistic property enforcement enabling improved query optimization, the method comprising:

receiving a query requesting data from a database, said query requesting ordering and grouping of data;

generating plan fragments for obtaining data requested by the query;

grouping said plan fragments into classes based upon tables covered by each plan fragment;

if grouping is needed at a given class, adding a grouping enforcement operator to plan fragments in the given class having an ordering on the grouping columns;

for each class, determining a particular plan fragment having the lowest execution costs; and

adding any required ordering enforcement operator to said particular plan fragment.

20. The method of claim 19, wherein said query includes a SQL query.

21. The method of claim 19, wherein ordering enforcement includes sorting.

22. The method of claim 19, further comprising:

converting the query into a tree of logical operators.

23. The method of claim 22, wherein said step of converting the query into a tree of logical operators includes determining groupings and orderings required by the query.

24. The method of claim 19, further comprising:

generating a query execution plan based upon combining said particular plan fragments covering all tables from which the query requests data.

26. The method of claim 19, further comprising:

pruning plan fragments not having the lowest execution costs from each class.

27. The method of claim 19, further comprising:

pruning plan fragments not having the lowest execution costs and not providing a needed property from each class.

28. The method of claim 27, further comprising:

retaining a plan fragment providing a needed property if no other plan fragment with lower execution costs provides the needed property.

29. The method of claim 19, wherein said step of adding a grouping enforcement operator includes adding a GROUP ORDERED operator.

30. The method of claim 19, wherein said step of adding any required ordering enforcement operator includes determining whether said required ordering is already provided by said particular plan fragment.

31. The method of claim 19, wherein said step of adding any required ordering enforcement operator includes the substeps of:

determining whether grouping is also needed at the class;

if grouping is needed, adding an operator enforcing grouping and ordering to said plan fragment.

32. The method of claim 19, further comprising:

when adding an operator enforcing ordering to a plan fragment, determining whether grouping is needed at the class;

if grouping is needed, adding an operator enforcing grouping and ordering to said plan fragment instead of an operator enforcing ordering.

33. A computer-readable medium having computer-executable instructions for performing the method of claim 19.

34. A downloadable set of computer-executable instructions for performing the method of claim 19.

35. In a database system, a method for ordering and grouping enforcement enabling improved query optimization, the method comprising:

receiving a query requesting data from a database, said query requesting ordering and grouping of data;

generating sub-plans for obtaining data requested by the query, each said sub-plan comprising a portion of an overall query execution plan;

organizing said sub-plans into classes based upon tables covered by each sub-plan;

for each class, determining a particular sub-plan having the lowest execution costs;

if grouping is not required at a given class, adding an operator enforcing ordering to said particular sub-plan; and

if grouping is required at a given class, adding an operator enforcing grouping and ordering to said particular sub-plan.

36. The method of claim 35, wherein said operator enforcing grouping and ordering comprises a GROUP SORTING operator.

37. The method of claim 35, wherein said operator enforcing ordering comprises a SORT operator.

38. The method of claim 35, further comprising:

generating a tree of physical operators based upon combining said particular sub-plans.

39. The method of claim 35, further comprising:

pruning sub-plans not having the lowest execution costs from each class.

40. The method of claim 35, further comprising:

pruning sub-plans not having the lowest execution costs and not providing a needed property from each class.

41. The method of claim 35, further comprising:

generating a query execution plan based upon combining said particular sub-plans covering all tables from which the query requests data.

42. A computer-readable medium having computer-executable instructions for performing the method of claim 35.

43. A downloadable set of computer-executable instructions for performing the method of claim 35.