The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Oct. 13, 1998
Filed:
Aug. 23, 1996
Goetz Graefe, Bellevue, WA (US);
Pedro Celis, Austin, TX (US);
Jay Vaishnav, Cupertino, CA (US);
Hansjorg Zeller, Los Altos, CA (US);
Tandem Computers, Inc., Cupertino, CA (US);
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.