written 7.7 years ago by | • modified 2.8 years ago |
Subject: Distributed Database
Topic: Distributed query processing and optimization
Difficulty: High
written 7.7 years ago by | • modified 2.8 years ago |
Subject: Distributed Database
Topic: Distributed query processing and optimization
Difficulty: High
written 7.7 years ago by |
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:
Hill Climbing Algorithm
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