Distributed Query Processing

Distributed query processing involves decomposing a global query into sub-queries, executing them at the appropriate sites, and combining the results.

Overview

Distributed query processing involves decomposing a global query into sub-queries, executing them at the appropriate sites, and combining the results.

Steps in Distributed Query Processing

Global SQL Query │ ▼ 1. Query Decomposition → Translate to relational algebra → Apply algebraic optimizations │ ▼ 2. Data Localization → Replace global relations with fragments → Determine which fragments/sites are needed │ ▼ 3. Global Optimization → Choose optimal execution strategy → Minimize communication cost │ ▼ 4. Local Optimization → Each site optimizes its sub-query locally │ ▼ 5. Execution & Assembly → Sub-queries execute at each site → Results collected and combined

Communication Cost Model

Total Cost = CPU Cost + I/O Cost + Communication Cost Communication Cost = n_msg × t_msg + data_size × t_transfer Where: n_msg = number of network messages t_msg = latency per message (fixed overhead) data_size = bytes transferred t_transfer = bandwidth cost per byte Key insight: Minimize data transferred over network. Sending 1MB over LAN is cheap. Sending 1GB over WAN is expensive.

Query Decomposition Example

Employee(EmpID, Name, DeptID)	at Site A (Delhi)
Department(DeptID, DeptName)	at Site B (Mumbai)
Query	SELECT Name FROM Employee e JOIN Department d
1. Compute σ_{DeptName='CS'}(Department) at B	{DeptID=1}
3. A computes	π_{Name}(Employee ⋈ {DeptID=1})
Communication cost	send 1 tuple + return result
Communication cost: send entire Employee table	expensive!

Semi-Join Technique

Used to reduce the amount of data transferred:

Semi-join of R with S on attribute A

R ⋉ S = π_R(R ⋈ S) — result contains only R's columns

Benefit: Instead of sending all of S, send only S's join attributes.

Then only matching tuples of R are sent back.

Algorithm

1. Project S on join attribute A: Proj_S = π_A(S) (small!)

2. Send Proj_S to R's site

3. Compute R' = R ⋉ Proj_S (filter R to matching tuples)

4. Send R' to S's site (or result site)

5. Complete the join at destination

Trade-off: Extra message vs. much less data transferred

Effective when S is large and join attribute has low selectivity

Join Ordering in Distributed Query

For a query joining tables at different sites, join order matters:

Tables	A (Site 1), B (Site 2), C (Site 3)
Option 1	(A ⋈ B) at Site 1, then ⋈ C
Option 2	(B ⋈ C) at Site 2, then ⋈ A

Overview

Distributed query processing involves decomposing a global query into sub-queries, executing them at the appropriate sites, and combining the results.

Steps in Distributed Query Processing

Communication Cost Model

Query Decomposition Example

Employee(EmpID, Name, DeptID)	at Site A (Delhi)
Department(DeptID, DeptName)	at Site B (Mumbai)
Query	SELECT Name FROM Employee e JOIN Department d
1. Compute σ_{DeptName='CS'}(Department) at B	{DeptID=1}
3. A computes	π_{Name}(Employee ⋈ {DeptID=1})
Communication cost	send 1 tuple + return result
Communication cost: send entire Employee table	expensive!

Semi-Join Technique

Used to reduce the amount of data transferred:

Semi-join of R with S on attribute A

R ⋉ S = π_R(R ⋈ S) — result contains only R's columns

Benefit: Instead of sending all of S, send only S's join attributes.

Then only matching tuples of R are sent back.

Algorithm

1. Project S on join attribute A: Proj_S = π_A(S) (small!)

2. Send Proj_S to R's site

3. Compute R' = R ⋉ Proj_S (filter R to matching tuples)

4. Send R' to S's site (or result site)

5. Complete the join at destination

Trade-off: Extra message vs. much less data transferred

Effective when S is large and join attribute has low selectivity

Join Ordering in Distributed Query

For a query joining tables at different sites, join order matters:

Tables	A (Site 1), B (Site 2), C (Site 3)
Option 1	(A ⋈ B) at Site 1, then ⋈ C
Option 2	(B ⋈ C) at Site 2, then ⋈ A

Distributed Query Processing

Overview

Steps in Distributed Query Processing

Communication Cost Model

Query Decomposition Example

Semi-Join Technique

Semi-join of R with S on attribute A

Algorithm

Join Ordering in Distributed Query

Continue learning this concept

Distributed Query Processing

Overview

Steps in Distributed Query Processing

Communication Cost Model

Query Decomposition Example

Semi-Join Technique

Semi-join of R with S on attribute A

Algorithm

Join Ordering in Distributed Query

Continue learning this concept