• A given SQL query is translated by the query processor into a low level program called an execution plan
• An execution plan is a program in a functional language
• The physical relational algebra extends the relational algebra with primitives to search through the internal storage structure of DBMS.

Basic Steps in Query Processing

1. Parsing and translation
2. Optimization
3. Evaluation

1. Parsing and translation

• Translate the query into its internal form. This is then translated into relational algebra.
• Parser checks syntax, verifies relation.

2. Optimization

• SQL is a very high level language:
  • The users specify what to search for- not how the search is actually done
  • The algorithms are chosen automatically by the DBMS.
• For a given SQL query there may be many possible execution plans.
• Amongst all equivalent plans choose the one with lowest cost.
• Cost is estimated using statistical information from the database catalog.

3. Evaluation

• The query evaluation engine takes a query evaluation plan, executes that plan and returns the answer to that query.