System and method for optimizing database queries

摘要

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.