Database Reference
In-Depth Information
Plan 1
DBMS
SELECT
JOIN
PROJECT
Query Processing
Steps
Plan 2
……….
……….
Generate
several
plans
SELECT
PROJECT
JOIN
Data
Dictionary
Database
Statistics
Query
Optimizer
Plan 3
Select
optimal
plan
JOIN
SELECT
PROJECT
Database
Plan n
……….
……….
PROJECT
JOIN
SELECT
Figure 13-16
Query optimizer: overall function.
query may be executed in six different sequences. In practice, however, queries
contain several operations with complex selection and join conditions. Therefore,
it is not practical to review every possible way a query may be executed. Query
optimizers only consider a feasible subset of all the possible ways.
Next, the query optimizer must have a proven method for choosing the best exe-
cution strategy from the competing strategies. The optimizer adopts an optimiza-
tion technique to evaluate each execution plan. On the basis of the optimization
technique, the optimizer selects the best possible query plan.
We will briefly scrutinize two common techniques used by the query optimizer
for selecting the optimal execution plan. One technique adopts a heuristic approach;
the other approach utilizes cost comparisons. These techniques examine the query
tree for each of the possible ways a query may be executed and then select the tree
that represents the optimal execution plan.
Heuristic Approach
If you consider a single query, it can be transformed into several different distinct
sets of relational algebra operations. Each set of these operations comprises a rela-
tional algebraic expression. When you are able to transform a single query into
several distinct algebraic expressions, in effect, all these expressions are equivalent
and expected to produce the same result. Now the question arises: Which of the
several algebraic expressions will produce the result in the most optimal manner
using the minimum resources and consuming the least time?
As a consequence of parsing the query, an initial query tree representing the SQL
query is constructed. This version of the query tree just represents the initial
transformation of the query into a relational algebraic expression without any
optimization. The optimizer must now transform this initial relational algebraic
expression or its representation as a query tree into a more efficient expression or
tree. The process of transformation continues until the most efficient expression or
tree emerges.
Search WWH ::
Custom Search