Query Optimization using Heuristics - Cost Estimation

Query Optimization using Heuristics - Cost Estimation

AU: Dec,-13,16, May-15, Marks 16

Heuristic Estimation

• Heuristic is a rule that leads to least cost in most of cases.

• Systems may use heuristics to reduce the number of choices that must be made in a cost-based fashion.

• Heuristic optimization transforms the query-tree by using a set of rules that typically t improve execution performance. These rules are

1. Perform selection early (reduces the number of tuples)

2. Perform projection early (reduces the number of attributes)

3. Perform most restrictive selection and join operations before other similar on she is ont ni bold do operations (such as cartesian product).

• Some systems use only heuristics, others combine heuristics with partial cost-based optimization.

Steps in Heuristic Estimation

Step 1: Scanner and parser generate initial query representation

Step 2: Representation is optimized according to heuristic rules

Step 3: Query execution plan is developed

For example: Suppose there are two relational algebra -

(1) σ_{city= "Pune"} (T_cname Branch)  Account  Customer)

(2) Π_cname(σ_city="Pune (Branch Account  Customer))

The query evaluation plan can be drawn using the query trees as follows-

Out of the above given query evaluation plans, the Fig. 4.16.1 (b) is much faster than Fig. 4.16.1 (a) because - in Fig. 4.16.1 (a) the join operation is among Branch, Account and Customer, whereas in Fig. 4.16.1 (b) the join of (Account and Customer) is made with the selected tuple for City="Pune". Thus the output of entire table for join operation is much more than the join for some selected tuples. Thus we get choose the optimized query.

Cost based Estimation

• A cost based optimizer will look at all of the possible ways or scenarios in which a query can be executed.

• Each scenario will be assigned a 'cost', which indicates how efficiently that query can be run.

• Then, the cost based optimizer will pick the scenario that has the least cost and execute the query using that scenario, because that is the most efficient way to run the query.

• Scope of query optimization is a query block. Global query optimization involves multiple query blocks.

• Cost components for query execution

      • Access cost to secondary storage

      • Disk storage cost

      • Computation cost

      • Memory usage cost

      • Communication cost

• Following information stored in DBMS catalog and used by optimizer

     • File size

     • Organization

     • Number of levels of each multilevel index

     • Number of distinct values of an attribute

     • Attribute selectivity

• RDBMS stores histograms for most important attributes

Review Questions

1. Explain query optimization with an example.  AU: Dec,-16, Marks 8

2. Discuss about the Join order optimization and Heuristic optimization algorithms. AU May-15, Marks 16