Distributed Query Processing
Distributed Query Processing is the method of executing a database query across
multiple interconnected database sites in a distributed database system (DDBS).
Instead of all data being stored in one location, it’s spread across different sites
(possibly in different cities or countries), but the system should still appear to users as
one single database.
When data is distributed:
• A query might require data from multiple sites.
• Simply fetching all data to one location and then processing it would be slow and costly.
• The system must decide where, how, and in what order to execute operations for
minimum cost.
Steps in Distributed Query Processing
• Query Decomposition
The high-level user query (e.g., SQL) is broken down into an algebraic
representation (like relational algebra).
• Data Localization
o The logical query plan is mapped to the actual fragmented and
replicated data across sites.
o This step finds which fragments are needed and where they are
located.
• Global Query Optimization
o Generates alternative execution strategies.
o Chooses the one with minimum cost based on:
▪ Communication cost (network transfer time)
▪ Local processing cost
o Often uses cost-based optimization or heuristics.
• Query Execution Plan Generation
o Creates a physical plan: specifies the sequence of operations, their
locations, and data transfer steps.
o Plan is then sent to the relevant sites.
• Local Processing
o Each site executes its part of the query using its local DBMS.
• Result Assembly
o The partial results from all sites are combined at the coordinator site.
o Final output is sent to the user.
Example 1:
Site A: Orders table and Site B: Customers table
Consider an SQL Query: “Find the names of all customers who live in Chennai and list the
order IDs of the orders they have placed.”
SELECT [Link], O.order_id
FROM Customers C, Orders O
WHERE [Link] = 'Chennai'
AND C.customer_id = O.customer_id;
Efficient distributed plan:
1. At Site B: σ_city='Chennai'(Customers) → sends matching customer IDs to Site A.
2. At Site A: Join Orders with received customer IDs → sends final order details to
coordinator.
This avoids sending all customers or all orders over the network.
Example 2: Join across two sites
Consider a SQL Query: “Select the name of every customer who lives in Chennai, along with
the amount of each order they have placed.”
Scenario
• Site A: Orders(order_id, customer_id, amount)
• Site B: Customers(customer_id, name, city)
Query
SELECT [Link], [Link]
FROM Customers C, Orders O
WHERE [Link] = 'Chennai'
AND C.customer_id = O.customer_id;
Execution Strategy
1. At Site B, filter Customers by city = 'Chennai'.
2. Send only the matching customer IDs to Site A.
3. At Site A, join with Orders to get amounts.
4. Send results to coordinator.
Benefit → Avoids sending all customer data over the network.
Example 3: Aggregation from multiple sites
Scenario
• Site X: Sales data for North region.
• Site Y: Sales data for South region.
• Site Z: Sales data for East region.
Query : Select the total sales amount from the Sales table.
SELECT SUM(amount) AS total_sales
FROM Sales;
Execution Strategy
1. At each site, compute SUM(amount) locally.
2. Send only the totals to coordinator.
3. Coordinator adds them up.
Benefit → Huge reduction in data transfer (sending 3 numbers instead of millions of rows).
Example 4: Fragmented table query
Scenario
Select the employees who earns more than 50,000 USD.
• Employee table is horizontally fragmented:
o Site 1: Employees in India.
o Site 2: Employees in USA.
Query
SELECT name
FROM Employee
WHERE salary > 50000;
Execution Strategy
1. Push the salary filter to both sites.
2. Get matching rows from each site.
3. Merge results at coordinator.
Benefit → Parallel execution at both sites.
Example 5: Replicated data query
Scenario
• Product table is fully replicated at Site P and Site Q.
Query
SELECT *
FROM Product
WHERE category = 'Electronics';
Execution Strategy
• Choose the nearest/least-loaded site (P or Q) to process the query.
Benefit → Load balancing and reduced response time.