Databases Reference
In-Depth Information
execution plan would be best. We focus here on the practical tradeoff analysis needed to
find the best query execution plan to illustrate the process.
3.1
Query Processing and Optimization
The basic steps of query processing are:
1.
Scanning, parsing, and decomposition of an SQL query.
This step checks for correct
SQL query syntax and generates appropriate error messages when necessary. The
output of this step is an intermediate form of the query known as a query tree or
query execution plan.
2.
Query optimization.
This step includes both local and global optimization. Glo-
bal optimization determines the order of joins and the order of selections and
projections relative to the joins. It also involves restating (recasting) nested join
queries into flat queries involving the same joins. This is the main concept
described in this chapter. Local optimization determines the index method for
selections and joins, using techniques covered in Chapters 2 and 4. Both kinds
of optimization are based on estimates of cost (I/O time) of the various alterna-
tive query execution plans generated by the optimizer. The cost model is based
on a description of the database schema and size, and looks at statistics for the
attribute values in each table involved in queries.
3.
Query code generation and execution.
This step uses classical programming lan-
guage and compiler techniques to generate executable code.
3.2
Useful Optimization Features in Database Systems
In addition to the basics of query processing and optimization described above, there
are many useful features in database management systems today that aid the database
administrator, application developer, and database system itself to process queries more
efficiently.
3.2.1 Query Transformation or Rewrite
Modern databases (e.g., Oracle, DB2, SQL Server) transform (rewrite) queries into
more efficient forms before optimization takes place. This helps tremendously with
query execution plan selection. Examples of the more popular query rewrites are
transforming subqueries into joins or semi-joins, pushing down the group by opera-
tions below joins, the elimination of joins on foreign keys when the tables containing
the results of the join are no longer used in the query, converting outer joins to inner
