Database system with methodology for reusing cost-based optimization decisions

• US 6,618,719 B1
• Filed: 05/19/2000
• Issued: 09/09/2003
• Est. Priority Date: 05/19/1999
• Status: Active Grant

• Current Assignee: Sybase Incorporated (SAP SE)
• Original Assignee: Sybase Incorporated (SAP SE)
• Inventors: Andrei, Mihnea
• Primary Examiner(s): Robinson, Greta
• Assistant Examiner(s): RAYYAN, SUSAN F
• Application Number:
  US09/574,405
• Time in Patent Office: 1,208 Days
• Field of Search: 707/1-3, 707/10, 709/201
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24547 Optimisations to support specific applications; Extensibility of optimisers
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A database system providing a methodology, implemented as an “Abstract Plan on Disc” technology (referred to herein as, “Ariadne”), is described for turning cost based optimization decisions into stored, reusable items. In particular, the present invention provides a novel language interface to the optimizer, through an Abstract Plan, through which it can be given a description of the desired query execution plan (QEP). The language interface defines a declarative language syntax that allows description of the QEP. It does not specify the sequence of operations the database system'"'"'s optimizer and code generator should accomplish to generate the QEP, but rather describes the desired outcome. Such an approach provides an abstraction barrier between an optimizer directives language and some specific optimizer and code generator. In this manner, the present invention allows a database system the ability to generate a better execution plan, and thereby realize better query performance. Such a feature has particular utility in avoiding performance regressions on server release upgrade and in query optimization fine tuning.

Claims

1. In a computer system having a processor, a memory, and a storage device, said storage device storing a database comprising rows of data records, each data record storing information in database columns, said database including an optimizer for selecting a query execution plan specifying how a given database query is executed, a method for executing a database query for selecting particular ones of said data records, the method comprising:

(a) receiving from a user specification of a database query specifying selection of particular ones of said data records, said database query comprising an expression specifying a query condition;

(b) providing a language interface to the optimizer, through which it can be given a user-provided description of a particular desired query execution plan for said specified database query;

(c) through said language interface, receiving from the user specification of the desired query execution plan for said specified database query, the language interface defining a declarative language syntax that allows description of the desired query execution plan in abstract terms, said specification of the desired query execution plan comprising a relational algebra describing the desired execution plan for said specified database query without specifying a particular sequence of operations that the database system must follow;

(d) storing said specified desired query execution plan as a reusable object; and

(e) when executing said database query, performing substeps of;

(i) retrieving said specified desired query execution plan; and

(ii) executing said database query according to the query execution plan set forth in said retrieved specified desired query execution plan.

2. The method of claim 1, wherein said user-provided description of a desired query execution plan comprises an abstract plan allowing cost-based optimization decisions to be turned into reusable objects.

3. The method of claim 2, wherein said abstract plan provides a description of a particular query execution plan that is desired.

4. The method of claim 1, wherein the method operates to prevent performance regression resulting from a system upgrade.

5. The method of claim 1, wherein the method operates to support query optimization fine tuning.

6. The method of claim 1, wherein said user-provided description is not syntactically included in said database query.

7. The method of claim 1, wherein said language interface supports specification of a partial query execution plan.

8. The method of claim 7, wherein a partial query execution plan employs logical operators to specify query execution.

9. The method of claim 1, wherein said language interface supports specification of a full query execution plan.

10. The method of claim 9, wherein a full query execution plan employs physical operators to specify query execution.

11. The method of claim 1, wherein said language interface supports specification of decisions that the optimizer may not take to create the query execution plan.

12. The method of claim 1, further comprising:

upon receipt of the database query, associating the database query with a previously-stored query execution plan.

13. The method of claim 12, wherein said associating step is based, at least in part, on text which comprises the database query.

14. The method of claim 1, wherein the query execution plan is compliant with the user-provided description.

15. The method of claim 1, wherein said specification of the desired query execution plan comprises relational algebra expressions that are not syntactically included in the database query.

16. The method of claim 1, wherein said specification of the desired query execution plan comprises relational algebra expressions that are stored in a system catalog.

17. The method of claim 1, wherein said language interface includes specification of a high level join operator.

18. The method of claim 1, wherein said language interface includes specification of a union operator.

19. The method of claim 1, wherein said language interface includes specification of a scan operator.

20. The method of claim 1, wherein said language interface includes specification of a store operator.

21. The method of claim 1, wherein said language interface includes specification of a nested operator.

22. The method of claim 1, wherein said language interface includes logical operators that allow the optimizer freedom to choose access methods for executing the database query.

23. The method of claim 1, wherein said language interface includes physical operators that do not allow the optimizer freedom to choose access methods.

24. A database system comprising:

a database storing database records and including an optimizer for selecting a query execution plan specifying how a given database query is executed;

a language interface, in communication with the optimizer, through which a user-provided description of a particular high level query execution plan may be specified, the language interface defining a declarative language syntax that allows description of a query execution plan in abstract terms, said declarative language syntax allowing description of the query execution plan without specifying a particular sequence of operations that the database system must follow; and

a module for storing the high level query execution plan as a reusable object, wherein said database system executes the database query according to the stored high level query execution plan.

25. The system of claim 24, wherein said user-provided description of a desired query execution plan comprises an abstract plan allowing cost-based optimization decisions to be turned into reusable objects.

26. The system of claim 25, wherein said abstract plan provides a description of a particular query execution plan that is desired.

27. The system of claim 24, wherein the system operates to prevent performance regression resulting from a system upgrade.

28. The system of claim 24, wherein the system operates to support query optimization fine tuning.

29. The system of claim 24, wherein said user-provided description is not syntactically included in said database query.

30. The system of claim 24, wherein said language interface supports specification of a partial query execution plan.

31. The system of claim 30, wherein a partial query execution plan employs logical operators to specify query execution.

32. The system of claim 24, wherein said language interface supports specification of a full query execution plan.

33. The system of claim 32, wherein a full query execution plan employs physical operators to specify query execution.

34. The system of claim 24, wherein said language interface supports specification of decisions that the optimizer may not take to create the query execution plan.

35. The system of claim 24, further comprising:

a module that associates the database query with a previously-stored query execution plan.

36. The system of claim 35, wherein associating a database query with a previously-stored query execution plan is based, at least in part, on text which comprises the database query.

37. The system of claim 24, wherein the query execution plan is compliant with the user-provided description.

38. The system of claim 24, wherein specification of a desired query execution plan comprises relational algebra expressions that are not syntactically included in the database query.

39. The system of claim 24, wherein specification of a desired query execution plan comprises relational algebra expressions that are stored in a system catalog.

40. The system of claim 24, wherein said language interface includes specification of a high-level join operator.

41. The system of claim 24, wherein said language interface includes specification of a union operator.

42. The system of claim 24, wherein said language interface includes specification of a scan operator.

43. The system of claim 24, wherein said language interface includes specification of a store operator.

44. The system of claim 24, wherein said language interface includes specification of a nested operator.

45. The system of claim 24, wherein said language interface includes logical operators that allow the optimizer freedom to choose access methods for executing the database query.

46. The system of claim 24, wherein said language interface includes physical operators that do not allow the optimizer freedom to choose access methods.