Update Research Note Form
Research Note Topic:
Research Note Description:
Optimization is one of the strengths of Relational Databases. This is because, in such a System, relational expressions are at a sufficiently high semantic level to make optimization feasible in the first place. The overall purpose of the optimizer is to is to chaoose an efficient strategy for evaluating a given relational expression. However, there is no guarantee that the implementation strategy chosen is truly optimal, all that can be said is that it is an improvement on the original unoptimized version.
A good optimizer will have Statistical information such as --
The number of values in each domain
The current number of tuples in each base relvar
The current number of distinct values in each attribute in a base relvar
The number of times ach such value occurs in each attribute
There are four broad stages in query processing
1. Cast the query into internal form
The internal form chosen is usually in the form of a query tree.
2. Convert to canonical form
Relational languages usually allow queries to be expressed in a variety of ways. The purpose of this step is to convert these into some equivalent canonical form to eliminate such superficial differences.
3. Choose candidate low level procedures
This is for implementing the various operations in the canonical representation of the query.
4. Genetate query plans and choose the cheapest
Some transformation rules used in the optimization process are
Restrictions , projections, union, intersection, difference, join, commutativity, associativity, idempotencescalar computational expressions, boolean expressions and semantic transformations
The next step is to adopt a ‘divide & conquer’strategy called query decompositionpioneered by the Ingres Prototype. The idea behind this is to break a query involving Range variables into a sequence of smaller queries involving one or two such variables each using Detachment & Touple substitution.
Next, we implement the relational operators using pseudocode alogarithms for five join techniques--
1.brute force 2.index lookup 3.hash lookup 4.merge 5.hash 6.combinations of the above.
Prof. Ashay Dharwadker