Database Reference
In-Depth Information
query optimizer starts evaluating the most promising execution plan and then considers different execution plans
until the cheapest one is found or too many alternatives are probed. It implements a
branch-and-bound
algorithm.
A
branch
is an alternative (for example, an access path or a join method), and the
bound
is the cost of the best
execution plan found so far—the query optimizer discards a branch (and possibly all its subbranches) as soon as its
current cost gets higher than the bound.
Figure
6-1
shows that to estimate the cost of an execution plan, the query optimizer considers not only the
SQL statement to be optimized, but also a number of other inputs. Some of those other inputs are stored in the data
dictionary and hardly ever change, or are not expected to frequently change, at runtime. They can be considered as a
static environment in which an application runs. Other inputs, though, not only might change frequently or even for
every execution, but might not even be known until runtime. Because of such inputs, a different execution plan might
be generated every time the query optimizer processes a given SQL statement.
Figure 6-1.
The query optimizer considers a number of inputs to produce an execution plan
Some of the inputs in Figure
6-1
are used to determine which options are available. Others are used to estimate
the cost of potential execution plans. The following list briefly describes these inputs and, when possible, points out
which part of the topic provides more information about them:
System statistics:
The query optimizer must know the power of the system it's running on
to provide accurate estimates. For that purpose, system statistics describe both the machine
running the database engine and the performance figures of the storage subsystem.
Chapter 7 describes which system statistics are available, how to manage them, and how
the query optimizer uses them to improve its estimations.
Object statistics:
Table, index, and column statistics, which are stored in the data dictionary,
are essential because they describe the data stored in the database. For example, a query
optimizer that's aware only of the SQL statements to be processed and the structure of the
referenced objects can't provide efficient execution plans. To generate efficient execution
plans, the query optimizer has to be able to quantify the amount of data to be processed and
the cost of processing it by the various alternatives that the query optimizer has to choose
from. Chapter 8 describes which object statistics are available and how to manage them.
