What is Query Processing?
“Taking a user’s query and finding the best, fastest, and cheapest way to execute
it in a distributed system.”
The system must decide:
● Where is the data located?
● How to access that data?
● Which site should perform the work?
● How to reduce communication cost?
● How to combine results from different sites?
Why Query Processing Is Hard in Distributed Databases?
Because data is spread across multiple servers.
Challenges include:
1. Communication Cost → Sending data between sites is slow and expensive.
2. Different Data Locations → Tables may be stored at various sites.
3. Different Database Systems → Sites may use different DBMS versions.
4. Network issues → Delays, failures, etc.
1. Query Parsing (What does the query mean?)
The system checks if the query is correct.
It breaks the query into smaller parts such as:
● SELECT
● FROM
● WHERE
For query:SELECT Name FROM Student WHERE Marks > 80
The system identifies:
● Table: Student
● Column: Name
● Condition: Marks > 80
Data Localization (Where is the data?)
The system checks which site(s) store the required tables.
✔ Example:
● Student table in Site A
● Marks table in Site B
If needed, the system decides:
● Should data be moved?
● Or processed at each site?
Query Decomposition (Break the query into subqueries)
The query is divided into sub-queries to run on each site.
✔ Example:
If Student table is on Site A, and Marks on Site B:
● Subquery 1 → run at Site A
● Subquery 2 → run at Site B
Optimization
Best site to perform work
● Best order of operations
● Minimum data transfer
Two types of optimization:
a) Local Optimization
Each site tries to process its part efficiently.
b) Global Optimization
System tries to minimize overall network cost.
✔ Example:
Instead of sending whole Student table to Site B,
only send Names of students with Marks > 80 from Site B to Site A.
Query Execution (Run the plan)
● Subqueries run at different sites.
● Required data is retrieved and processed.
● Results are sent back to the main site.
6. Result Merging and Output
● All results from different sites are combined.
● Final answer is formatted.
● Sent to the user.
Types of Costs in Query Processing
Communication Cost (Most Important)
This is the cost of transferring data between different sites (servers).
✔ In distributed databases, this is the highest and most expensive cost.
Includes:
● Cost of sending a table from one site to another
● Cost of sending intermediate results
● Cost of sending final results back to the user
Because network sending is much slower than local processing.
Example:
Site A needs data from Site B →
If 10,000 rows must be sent over the network, the communication cost is high.
Local Processing Cost
This is the cost of processing the query at each site, such as:
● Scanning tables
● Performing selections (WHERE)
● Performing joins
● Sorting
● Aggregation (SUM, COUNT, AVERAGE)
⭐ Example:
Site A scans its table to apply “Marks > 80”.
This uses CPU & disk at that site → this is local processing cost.
I/O Cost (Input/Output Cost)
This cost includes:
● Reading data from disk
● Writing data to disk
● Temporary files creation during joins, sorting, etc.
⭐ Example:
If a join creates a temporary table on disk, this increases I/O cost.
Factors Affecting Query Cost
Size of data
Bigger data → more time → high communication cost
Number of sites
More sites → more data transfers
Join operations
Joins between tables at different sites are very expensive
Network speed
Slow network → higher cost
Location of data
If needed data is at multiple sites, cost increases
Query complexity
More operations = more cost
How Query Optimization Reduces Cost
The system tries to:
● Move small data instead of big data
● Push selection/filters to the site with data
● Perform joins at the best site
● Reduce network message
● Avoid unnecessary data transfers
✔ Example (Very Easy)
Query:
SELECT Name FROM Student WHERE Marks > 80
Instead of sending the whole Student table to Site B: