Query Processing Overview

Part II: Query Processing

Query Processing Overview

AU: May-14,16,18, Dec.-19, Marks 16

• Query processing is a collection of activities that are involved in extracting data from database.

• During query processing there is translation high level database language queries into the expressions that can be used at the physical level of filesystem.

• There are three basic steps involved in query processing and those are -

1. Parsing and Translation

• In this step the query is translated into its internal form and then into relational algebra.

• Parser checks syntax and verifies relations.

• For instance - If we submit the query as,

SELECT RollNo, name

FROM Student

HAVING RollNo=10

Then it will issue a syntactical error message as the correct query should be

SELECT RollNo, name

FROM Student

HAVING RollNo=10

Thus during this step the syntax of the query is checked so that only correct and verified query can be submitted for further processing.

2. Optimization

• During this process thequery evaluation plan is prepared from all the relational algebraic expressions. bud off

• The query cost for all the evaluation plans is calculated.

• Amongst all equivalent evaluation plans the one with lowest cost is chosen.

• Cost is estimated using statistical information from the database catalog, such asthe number of tuples in each relation, size of tuples, etc.

3. Evaluation

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

For example - If the SQL query is,

SELECT balance

FROM account

WHERE balance<1000

Step 1: This query is first verified by the parser and translator unit for correct syntax. If so then the relational algebra expressions can be obtained. For the above given queries there are two possible relational algebra

(1) σ_balance<1000(Π_balance (account))

(2) Π_balance ( σ_balance<1000 (account))

Step 2: Query Evaluation Plan: To specify fully how to evaluate a query, we need not only to provide the relational-algebra expression, but also to annotate it with instructions specifying how to evaluate each operation. For that purpose, using the order of evaluation of queries, two query evaluation plans are prepared. These are as follows

Associated with each query evaluation plan there is a query cost. The query optimization selects the query evaluation plan having minimum query cost.

Once the query plan is chosen, the query is evaluated with that plan and the result of the query is output.

Review Questions

1. Briefly explain about query processing.            AU: May-14, 16, Marks 16

2. What is query optimization? Outline the steps in query optimization. AU: May-18, Marks 13

3. Sketch and concise the basic steps in query processing. AU: Dec-19, Marks 3