Subject: Distributed Database

Topic: Distributed query processing and optimization

Difficulty: High

Query Optimization

Query optimization is the process of selecting the most efficient quey-evaluation plan from among the many strategies usually possible for a given query. It does not expect users to write their queries so that they can be processed efficiently. Rather, it expects the system to construct a query evaluation plan that minimizes the cost of query evaluation.

Distributed query optimization algorithm:

1. Semi-join Algorithm
2. INGRES Algorithm
3. System R Algorithm
4. System R* Algorithm
5. Hill Climbing Algorithm
6. SDD-1 Algorithm

Hill Climbing Algorithm

1. It refinements of an initial feasible solution are recursively computed until no more cost improvements can be made.
2. In hill climbing algorithm, Semijoins, data replication, and fragmentation are not used.
3. It devised for wide area point-to-point networks.
4. It is the first distributed query processing algorithm.

5. The hill-climbing algorithm proceeds as follows:

   i. Select initial feasible execution strategy ES0

   • i.e., a global execution schedule that includes all intersite communication

   • Determine the candidate result sites, where a relation referenced in the query exist

   • Compute the cost of transferring all the other referenced relations to each candidate site

   • ES0 = candidate site with minimum cost

   ii. Split ES0 into two strategies: ES1 followed by ES2

   • ES1: send one of the relations involved in the join to the other relation’s site –

   • ES2: send the join result to the final result site

   iii. Replace ES0 with the split schedule which gives

   iv. Recursively apply steps 2 and 3 on ES1 and ES2 until no more benefit can be gained

   v. Check for redundant transmissions in the final plan and eliminate them