DATABASE SYSTEM WITH METHODOLOGY FOR DISTRIBUTING QUERY OPTIMIZATION EFFORT OVER LARGE SEARCH SPACES

In a database system, a method for optimization of a query is described. When a query is received which requests data from a database, a plurality of plans which can be used for obtaining data requested by the query are enumerated. A search tree is created based upon these plans, with nodes of the search tree representing segments of the plans. A limited number of nodes of the search tree are selected for evaluation to limit the effort spent on query optimization. A complete plan for execution of the query is generated by evaluating the selected nodes of the search tree and, if the evaluation determines that a given node is more favorable than comparable nodes previously evaluated, retaining the given node as part of the complete plan.