Query Optimization

When a query is fired in a database, it is parsed and validate before retrieving results from database tables. System will automatically construct a query evaluation plan that minimizes the cost of query evaluation. This process of choosing the most appropriate execution strategy for query processing is called query optimization.

SQL queries are translated into equivalent relational algebra expressions before optimization.

The basic relational algebra operations are −

1. Projection
2. Selection
3. Union
4. Intersection
5. Minus
6. Join

 A query fired in database is first divided into smaller query blocks and then translated to equivalent relational algebra expressions. Optimization includes optimization of each block and then optimization of the query as a whole. It is the job of the query optimizer to come up with a query evaluation plan which is the least costly way. Optimizer needs to generate alternative plans to produce same result for choosing least costly one.

Steps to generate query evaluation plans

1)Generate logically equivalent expressions
2)Find alternate query evaluate plans for same expression
3)Estimate cost of each evaluation plan and choose  expression with the least estimated cost. Finally, materialized views help to speed up processing certain queries.

Once evaluation plans are generated, estimate the cost using statistical information about the relation sizes and index depths.

How to view query evaluation plans in a database?

explain : PostgreSQL
explain plan for/ select * from table(dbms_xplan.display);-Oracle
set showplan_text on; Execute this and then execute query-SQL Server

To display the details of all insructors who earn a salary LESS than the average salary

Equivalent Relational Algebra Expression

query evaluation plan