Query Optimization and Using Heuristics in query optimization.

 

Query Optimization and Using Heuristics in query optimization. 

A query has many possible execution strategies and the process of choosing a suitable one for processing a query is known as query optimization.The query optimizer module has the task of producing a good execution plan.

There are two main techniques that are employed during query optimization.

The first technique is based on heuristic rules for ordering the operation in a query execution strategy.a heuristic rules for ordering the operations in a query execution strategy.A heuristic is a rule that works well in most cases but is not guaranteed to work well in every case.

The second technique involves systematically estimating the cost of different execution strategies and choosing the execution plan with the lowest cost estimate.

Using Heuristics in query optimization

Optimization techniques that apply heuristic rules to modify the internal representation of a query which is usually in the form of a query tree.The scanner and parser of an SQL query first generate a data structure that corresponds to an initial query representation which is then optimized according to heuristic rules.

The heuristic query optimizer will transform this query tree into an equivalent final query tree that is efficient to execute.The optimizer must include rules for equivalence among relational algebra expressions that can be applied to transform the initial tree into the final optimized query tree.

Steps in converting a query tree during heuristic optimization.

• Initial query tree for SQL tree for SQL query Q.
• Moving select operation down the query tree.
• Applying the more restrictive select operation first.
• Replacing cartesian product and select with join operations.
• Moving project operations down the query tree.

The main heuristic is to apply first the operations that reduce the size of intermediate results.This includes performing as early as possible  Select operations to reduce the number of tuples and project operations to reduce the number of attributes by moving Select and Project operations as far down the tree as possible.The Select and Join operations that are most restrictive that is  result in relations with the fewest tuples or with the smallest absolute size should be executed before other similar operations.

A query optimizer does not depend solely on heuristic rules it also estimates and compares the cost of executing a query using different execution strategies and algorithm and it then choose the strategy with the lowest cost estimate.For this approach to work accurate cost estimates are required so that different strategies can be fairly and realistically.Cost component for query execution are Access cost to secondary storage,Disk storage cost,Computation cost,Memory usage cost,Communication cost etc.