OBJECTIVE. There has been extensive work in query optimization since the early ‘70s. It is hard to capture the breadth and depth of this large body of work in a short article. Therefore,I have decided to focus primarily on the optimization of SQL queries in relational database systems and present my biased and incomplete view of this field. The goal of this article is not to be comprehensive, but rather to explain the foundations and present samplings of significant work in this area.
Two key components of the query evaluation componentof a SQL database systemare the query optimizer and the query execution engine.
The query optimizer takes a parsed representation of a SQL query as input and is responsible for generating an efficient execution plan for the given SQL query from the space of possible execution plans.
query optimization can be viewed as a difficult search problem. in order to solve this problem, need to provide - a space of plans (search space) - cost estimation - enumeration algorithm
A desirable optimizer is one where (1) the search space includes plans that have low cost (2) the costing technique is accurure (3) the enumerating algorithm is efficient.