Data processing: database and file management or data structures – Database design – Data structure types
Patent
1996-08-23
1998-10-13
Black, Thomas G.
Data processing: database and file management or data structures
Database design
Data structure types
707 4, G06F 1730
Patent
active
058227474
ABSTRACT:
A system and method for optimizing a database query is herein disclosed. The system consists of a search engine and a database implementor that determines an optimal plan for executing a SQL query. The SQL query is represented as a query tree consisting of a number of nested expressions. The search engine generates a number of plans from which an optimal plan is selected. Plans are generated through the application of a set of rules consisting of implementation and transformation rules. Implementation rules are used to obtain plans. Transformation rules are used to determine equivalent expressions. A plan for the query tree entails finding plans for each expression within the tree where each plan is generated in accordance with a prescribed set of rules. The database implementor selects the set of rules such that more promising plans are generated rather than generating all possible plans. In a preferred embodiment of the invention, multiple passes are made by the search engine in order to determine the optimal plan. In a first pass, implementation rules are used in order to generate a first plan having a cost that is used as a threshold when generating for additional plans. In each subsequent pass, a set of implementation and transformation rules is used to generate one or more plans whose cost does not exceed the threshold. An optimal plan is selected from the generated plans as the one having the lowest cost.
REFERENCES:
patent: 5091852 (1992-02-01), Tsuchida et al.
patent: 5325525 (1994-06-01), Shan et al.
patent: 5335345 (1994-08-01), Frieder et al.
patent: 5590324 (1996-12-01), Leung et al.
patent: 5598559 (1997-01-01), Chaudhuri
patent: 5659725 (1997-08-01), Levy et al.
Goetz Graefe and William J. McKenna, The Volcano Optimizer Generatolr: Extensibility and Efficient Search, 1993 IEEE pp. 209-218.
Hyeokman Kim, Sukho Lee, Tree Query Optimization in Distributed Object-Oriented Databases, Apr. 1994.
Celis Pedro
Graefe Goetz
Vaishnav Jay
Zeller Hansjorg
Black Thomas G.
Channavajjala Srirama
Tandem Computers Inc.
Williams, Esq. Gary S.
LandOfFree
System and method for optimizing database queries does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for optimizing database queries, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for optimizing database queries will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-327074