Subject: Distributed Database

Topic: Distributed query processing and optimization

Difficulty: Medium

Query processing refers to the range of activities involved in extracting data from a database. The activities include translation of queries in high-level database language, into expressions that can be used at the physical levelof the file system, a variety of query-optimization transformations, and actual evaluation of queries. The step involved in processing a query appear in figure below:

1) Parsing and translation.

2) Optimization.

3) Evaluation.

The first action, the system must take in query processing is to translate a given query into its internal form. This translation process is similar to the work performed by the parser of a compiler. In generating the internal form of the query, the parser checks the syntax of the user's query, verifies that the relation names appearing in the query are names of the relations in the database, and so on. The system constructs a parse-tree representation of the query, which it then translates into a relational-algebra expression.

Furthermore, the relational-algebra representation of a query specifies only partially how to evaluate a query. As an illustration, consider the query:

select balance from account where balance < 2500

This query can be translated into either of the following relational-algebra expressions:

• a ',Amer., 2500 (il bita„ce (account)) • n manc• (a Mance < 2500 (account))

To implement the preceding selection, we can search every tuple in account to find tuples with balance less than 2500. If a 13+-tree index is available on the attribute balance, we can use the index instead to locate the tuples. To specify fully how to evaluate a query, we need to provide not only the relational-algebra expression, but also to annotate it with instructions specifying how to evaluate each operation.

A relational-algebra operation annotated with instructions on how to evaluate it is called an evaluation primitive. A sequence balance of primitive operations that can be used to evaluate a query is a query-execution plan or query-evaluation plan. Figure illustrates an evaluation plan for our account example query, in which a particular index (denoted in the figure as "index 1") is specified for the selection operation. The query-execution engine takes a query-evaluation plan, executes that plan, and returns the answers to the query. The different evaluation plans for a give query can have different costs.