Databases Reference
In-Depth Information
The job of the Query Optimizer is to create and assess as many candidate execution plans
as possible, within certain criteria, in order to arrive at the best possible plan. We define
the
search space
for a given query as the set of all the possible execution plans for that
query, and any possible plan in this search space returns the same results. Theoretically,
in order to find the optimum execution plan for a query, a cost-based query optimizer
should generate all possible execution plans that exist in that search space, and correctly
estimate the cost of each plan. However, some complex queries may have thousands, or
even millions, of possible execution plans and, while the SQL Server Query Optimizer
can typically consider a large number of candidate execution plans, it cannot perform
an exhaustive search of all the possible plans for every query. If it did, the time taken to
assess all of the plans would be unacceptably long, and could start to have a major impact
on the overall query execution time.
The Query Optimizer must strike a balance between optimization time and plan
quality. For example, if the Query Optimizer spends one second finding a good enough
plan that executes in one minute, then it doesn't make sense to try to find the perfect
or most optimal plan, if this is going to take five minutes of optimization time, plus the
execution time. So SQL Server does not do an exhaustive search, but instead tries to find
a suitably efficient plan as quickly as possible. As the Query Optimizer is working within
a time constraint, there's a chance that the plan selected may be the optimal plan but it is
also likely that it may just be something close to the optimal plan.
In order to explore the search space, the Query Optimizer uses transformation rules and
heuristics. The generation of candidate execution plans is performed inside the Query
Optimizer using transformation rules, and the use of heuristics limits the number of
choices considered, in order to keep the optimization time reasonable. Candidate plans
are stored in memory during the optimization, in a component called the Memo.
Transformation rules, heuristics, and the Memo will be discussed in more detail in
Chapter 5
,
The Optimization Process
.
