Using Selectivity and Cost
Estimates in Query Optimization
A query optimizer does not depend solely on
heuristic rules; it also estimates and compares the costs of executing a query
using different execution strategies and algorithms, and it then chooses the
strategy with the lowest cost estimate.
For this approach to work, accurate cost
estimates are required so that different strategies can be compared fairly
and realistically. In addition, the optimizer must limit the number of
execution strategies to be considered; otherwise, too much time will be spent
making cost estimates for the many possible execution strategies. Hence, this
approach is more suitable for compiled
queries where the optimization is done at compile time and the resulting
execution strategy code is stored and executed directly at runtime. For interpreted queries, where the entire
process shown in Figure 19.1 occurs at runtime, a full-scale optimization may
slow down the response time. A more elaborate optimization is indicated for
compiled queries, whereas a partial, less time-consuming optimization works
best for interpreted queries.
This approach is generally referred to as cost-based query optimization. It uses
traditional optimization techniques that search the solution space to a problem for a solution that minimizes an
objective (cost) function. The cost functions used in query optimization are
estimates and not exact cost functions, so the optimization may select a query
execution strategy that is not the optimal (absolute best) one. In Section
19.8.1 we discuss the components of query execution cost. In Section 19.8.2 we
discuss the type of information needed in cost functions. This information is
kept in the DBMS catalog. In Section 19.8.3 we give examples of cost functions
for the SELECT operation, and in Section 19.8.4 we discuss cost functions for
two-way JOIN operations. Section 19.8.5 discusses multiway joins, and Section
19.8.6 gives an example.
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.