DBMS Notes
Distributed query processing refers to the techniques and algorithms used to execute database queries that involve data stored across multiple sites in a...
What is Distributed Query Processing?
Distributed query processing refers to the techniques and algorithms used to execute database queries that involve data stored across multiple sites in a distributed database system. Unlike centralized systems where all data resides on a single server, a distributed query must determine which data to fetch from which site, how to transfer it across the network, and where to perform the actual computation — all while minimizing the total cost.
The fundamental challenge is network communication cost. Moving data between sites is orders of magnitude more expensive than local disk access. A naive approach that transfers large amounts of data across the network can make even simple queries extremely slow. Distributed query processing optimizes data movement to reduce network traffic while still producing correct results.
Query Processing Strategies
Data Shipping
Move the data to the site where the query is being processed. The requesting site receives all relevant data and performs computation locally.
| Example | Query at Site A needs data from Site B |
| Site A | SELECT * FROM Employee WHERE dept = 'CS' AND salary > 50000 |
| Cost | Network transfer of data from B to A |
| Good when | Data volume is small, many queries will reuse the transferred data |
Query Shipping
Move the query (or sub-query) to the site where the data resides. Results are computed remotely and only the final answer is returned.
| Example | Same query, Query Shipping approach |
| 2. Site B executes | SELECT * FROM Employee WHERE dept = 'CS' AND salary > 50000 |
| Cost | Network transfer of small query + small result set |
| Good when | Query is highly selective (result much smaller than full table) |
Hybrid Approach
Combine data shipping and query shipping based on the specific operations and data volumes involved. Most real distributed optimizers use hybrid strategies.
Distributed Join Processing
Joins across distributed sites are the most expensive operations because they potentially require combining large datasets from different locations.
Naive Approach (Ship Entire Relations)
| Query | SELECT * FROM Employee E JOIN Department D ON E.dept_id = D.dept_id |
| Option 1 | Ship Department to Site A |
| Transfer: 5 KB | Perform join at Site A |
| Total cost | 5 KB network + local join |
| Option 2 | Ship Employee to Site B |
| Transfer: 1 MB | Perform join at Site B |
| Total cost | 1 MB network + local join |
Semi-Join Technique
The semi-join reduces data transfer by sending only the joining column values first, then requesting only the matching rows.
| Query | Employee ⋈ Department (on dept_id) |
| 1. Site B projects dept_id from Department | {CS, EE, ME, CE, IT} |
| 2. Site B sends these dept_id values to Site A (tiny transfer | ~50 bytes) |
| Savings | Instead of transferring all 10,000 Employee rows, |
Bloom Filter Optimization
Instead of sending actual join column values, send a compact Bloom filter (bit array) that allows the remote site to probabilistically filter non-matching rows before transfer.
Distributed Query Optimization
Cost Model
Optimization Approaches
| Approach | Description | Complexity |
|---|---|---|
| Exhaustive Search | Consider all possible plans | Optimal but exponential — impractical for many sites |
| Heuristic-Based | Apply rules like "ship smaller relation" | Fast but may miss optimal plan |
| Semi-join Program | Find minimum-cost sequence of semi-joins | Good balance of quality and speed |
| Two-Phase Approach | Local optimization at each site + global coordination | Practical for real systems |
Factors Affecting Performance
| Factor | Impact |
|---|---|
| Network bandwidth | Higher bandwidth reduces transfer cost |
| Data distribution | Co-located data avoids transfers entirely |
| Query selectivity | Highly selective queries transfer less data |
| Available indexes | Remote indexes allow selective access |
| Replication | Replicas allow choosing nearest copy |
| Fragment allocation | Good fragmentation minimizes cross-site joins |
Example: Complete Distributed Query Plan
| Query | Find names of CS students with GPA > 3.5 |
| Site A | CS students, Site B: EE students, Site C: ME students |
| 2. Site D ships query to Site A | SELECT name FROM Student WHERE GPA > 3.5 |
| 4. Site A returns result (small | just names) to Site D |
| Cost | 2 network messages + local index scan at Site A |
This example shows how proper query routing, combined with knowledge of data distribution, eliminates unnecessary network communication entirely.
Key Takeaways
- Network cost dominates distributed query processing — minimize data movement
- Ship the smaller relation for joins; use semi-joins to reduce transfer volume
- Query shipping is preferred when queries are selective (small results)
- Data shipping is preferred when data will be reused for multiple local operations
- Knowledge of fragmentation and replication is essential for the distributed optimizer
- Semi-joins and Bloom filters are key techniques for reducing inter-site data transfer
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Distributed Query Processing.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Database Management Systems (DBMS) topic.
Search Terms
dbms, database management systems (dbms), unit, distributed, query, processing, distributed query processing
Related Database Management Systems (DBMS) Topics