Systematic approach to query optimization

• US 6,567,802 B1
• Filed: 09/06/2000
• Issued: 05/20/2003
• Est. Priority Date: 09/06/2000
• Status: Active Grant

• Current Assignee: Trustees Of The University Of Pennsylvania (University of Pennsylvania)
• Original Assignee: Trustees Of The University Of Pennsylvania (University of Pennsylvania)
• Inventors: Popa, Lucian, Sahuguet, Arnaud, Tannen, Val, Deutsch, Alin
• Primary Examiner(s): JUNG, DAVID YIUK
• Application Number:
  US09/655,890
• Time in Patent Office: 986 Days
• Field of Search: 707/1-206, 709/200, 709/100, 382/305
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24542 Plan optimisation
• 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

The present invention demonstrates the development and application of the chase/backchase (“C&B”) technique to systematically optimize generating alternative query plans, aimed at multiple disparate targets. It further provides a first optimization prototype that uses path-conjunctive query graphs internally. The methods, systems, apparatus and techniques of the present invention capture and extend many aspects of semantic optimizations, physical data independence, use of materialized views and cached queries, as well as generalized tableau-like minimization. Moreover, using a uniform representation with constraints, the techniques make these disparate optimization principles highly cooperative.

This present invention provides a new class of optimization opportunities, such as the non-trivial use of indexes and materialized views enabled only by the presence of certain integrity constraints. Moreover, the technique is valuable when only the presence of semantic integrity constraints enables the use of physical access structures or materialized views.

Claims

1. A method of systematically optimizing the processing of a query in a database management system that operates in a computer network, the method comprising:

a) receiving the executable data query;

b) producing a query plan by applying to the query a relational tableau chase procedure comprising logical constraints which capture all relevant elements for implementation mapping of the query;

c) rewriting the query against a logical schema into an equivalent universal query plan written against a physical schema, given a semantic relationship between the logical schema and the physical schema that explicitly uses all relevant physical structures in the implementation;

d) applying to the universal plan a sequence of backchase steps, which systematically combine use of indexes, materialized views, semantic optimization and minimization, to remove redundancies, joins and scans;

e) generating an alternative cost-based optimal query plan; and

f) executing said optimal query plan.

2. The method according to claim 1, wherein the method is complete.

3. The method according to claim 1, wherein the chase step (b) utilizes applicable constraints to gather all path-conjunctive queries and physical access structures relevant to the original query.

4. The method according to claim 1, wherein the backchase step (d) comprises removing data from the logical schema that is not in the physical schema.

5. The method according to claim 1, wherein the size of the search space for the backchase step (d) is minimized by reducing the size of the query, comprising fragmenting the query and stratifying the constraints by relevance to each fragment.

6. The method according to claim 1, wherein the size of the search space for the backchase step (d) is minimized by reducing the size of the constraint set, comprising splitting the constraints independent of the query.

7. The method according to claim 1, wherein the size of the search space for the backchase step (d) is minimized by reducing the size of both the query and the constraint set by partitioning into independent subparts, comprising (i) fragmenting the query and stratifying the constraints by relevance to each fragment, and (ii) splitting the constraints independent of the query.

8. The method according to claim 5, wherein all alternate plans enabled by indexes are considered.

9. A database management system, comprising:

a database having a plurality of records;

means for accessing and rewriting a query into a universal plan in accordance with a tableau chase procedure based on declarative constraints;

an optimizer for optimizing a query accessing said relational database, by rewriting with the tableau chase procedure the query into a universal plan, followed by a sequence of backchase procedure steps based in part on declarative constraints which eliminate redundancies in the universal plan to reduce cost;

wherein said rewrite rules are expressed in a high-level declarative language, and said query against a logical schema is rewritten into an equivalent universal query plan written against a physical schema, given a semantic relationship between the logical schema and the physical schema;

wherein said optimizer uses said rewrite rules to generate query plans that are minimal in the number of scans and joins it performs;

means for applying to said minimal query plans any cost-based query optimization procedure to produce a globally optimal plan; and

means for executing said optimal plan.

10. The system according to claim 9, wherein the chase procedure utilizes applicable constraints to gather all path-conjunctive queries and physical access structures relevant to the original query.

11. The system according to claim 9, wherein the backchase procedure comprises means for removing data from the logical schema that is not in the physical schema.

12. The system according to claim 9, wherein the size of the search space for the backchase procedure is minimized by reducing the size of both the query and the constraint set by partitioning into independent subparts, comprising (i) means for fragmenting the query and stratifying the constraints by relevance to each fragment, and (ii) means for splitting the constraints independent of the query.

13. A query optimization system for systematically optimizing a query invoking database tables, said system comprising:

means for providing a high-level declarative language, and declarative chase and backchase rules to rewrite a query written against a logical schema into an equivalent universal query plan written against a physical schema, given a semantic relationship between the logical schema and the physical schema;

means for generating alternative queries from the query and rewrite rules;

means for generating query plans that is minimal in the number of scans and joins it performs;

means for applying to said minimal query plans any cost-based query optimization procedure to produce a globally optimal plan; and

means for executing said optimal plan.

14. The system according to claim 13, wherein the chase procedure utilizes applicable constraints to gather all path-conjunctive queries and physical access structures relevant to the original query.

15. The system according to claim 13, wherein the backchase procedure comprises means for removing data from the logical schema that is not in the physical schema.

16. The system according to claim 13, wherein the size of the search space for the backchase procedure is minimized by reducing the size of both the query and the constraint set by partitioning into independent subparts, comprising (i) means for fragmenting the query and stratifying the constraints by relevance to each fragment, and (ii) means for splitting the constraints independent of the query.

17. An apparatus for use in systematically optimizing a query in a database system, wherein the apparatus comprises:

memory for storing at least one data item referenced by the query; and

a processor coupled to the memory and operative to (i) systematically apply to the query a tableau chase procedures and a sequence of backchase procedure steps based in part on declarative constraints along with one or more algebraic rewritings based on explicit substitutions in order to generate a rewritten universal query plan and rewritten query plans that are minimal in the number of scans and joins performed, which are equivalent to the query, wherein each of at least a subset of equivalent substitutions represents a hypothetical database change;

(ii) applying to said minimal query plans any cost-based query optimization procedure to produce a globally optimal plan; and

(iii) execute said optimal plan.

18. The apparatus according to claim 17, wherein the chase procedures utilize applicable constraints to gather all path-conjunctive queries and physical access structures relevant to the original query.

19. The apparatus according to claim 17, wherein the backchase procedure steps comprise removing data from the logical schema that is not in the physical schema.

20. The apparatus according to claim 17, wherein the size of the search space for the backchase procedure steps is minimized by reducing the size of both the query and the constraint set by partitioning into independent subparts, comprising (i) fragmenting the query and stratifying the constraints by relevance to each fragment, and (ii) splitting the constraints independent of the query.