Query Optimization

Query Optimization means to find the fastest route to execute the query. During this process, multiple execution plans are generated and at the end the best one is executed.

Steps involved in this process.

• Query
• Parse & Translator
• Relational Algebra
• Optimizer
• Execution Plan
• Evaluation Engine
• Query Output

The core capability of Query Optimization is to search for an execution plan which can find the least time required for query evaluation.

Phases of Query Processing

• Parsing & Translation
• Optimization
• Evaluation

Example:

We normally submit queries in SQL format. In the first phase of Parsing & Translation, SQL query is translated in an internal form where the parser validates the syntax of the query and the relations of the query in the database and so on. Then it is converted into a relational algebra expression, something like below.

Query:
Select col1 from table1 where col1=’XYZ’

Relational Algebra Expression:

σ<column name> = '<value>' (πSno (<column name>))

π<column name> (σ<column name>='<value>' (<column name>))

After a relational algebra expression, the query is converted into, usually, a query tree or graph for an optimization engine which then performs various analyses on the query data and applies many rules for an equivalent and efficient representation. Which then generates a few executions plans from which the best execution plan is selected and passed to the execution engine. The final step is to generate code for the selected execution plan which is executed by the runtime database processor to produce the query result.

Query Optimizers for a few famous databases.

• Oracle Optimizer uses RBO [rule-based optimizer] and CBO [cost-based optimizer].
• Teradata Optimizer uses its knowledge base of statistics and demographics to determine how best to access, join, and aggregate tables.
• SQL Server Optimizer is a cost-based optimizer. It analyzes several candidate executions plans for a given query, estimates the cost of each of these plans and selects the plan with the lowest cost of the choices considered