Query Processing and Optimization

Algorithms for Query Processing

Query processing is the series of operations that are performed on a query to transform it into an efficient execution plan. This plan specifies the order in which operations are performed and the access methods used to retrieve data from the database. The main goal is to minimize the overall cost, which usually translates to minimizing I/O operations and CPU time.

Phases of Query Processing

Query processing typically involves several distinct phases:

• Parsing and Translation: The SQL query is parsed to check for syntax errors and then translated into an internal representation, such as a relational algebra expression or a query tree.
• Optimization: The internal representation is transformed into various equivalent forms, and the most efficient execution plan is chosen. This is the most critical phase.
• Execution: The chosen execution plan is executed to retrieve the results.

Representations of Queries

Queries can be represented in several ways:

• SQL: The high-level declarative language.
• Parse Tree: A tree structure representing the syntactic structure of the query.
• Relational Algebra Expression: A formal representation using relational algebra operators (e.g., select, project, join, union, difference, intersection).
• Query Tree: A tree structure where internal nodes represent relational algebra operators and leaf nodes represent relations (tables) or sub-queries.

Algorithms for Relational Operations

The efficiency of query processing heavily depends on the algorithms used to implement relational algebra operations. Let's look at some key operations:

Selection Operation (σ)

The selection operation filters tuples from a relation based on a condition. The choice of algorithm depends on whether the relation is stored in a file, indexed, or hashed.

• Unordered File Scan: Scan the entire relation and check the condition for each tuple. Cost is proportional to the number of tuples (N) in the relation.
• Index Scan: If an index exists on the attribute used in the selection condition, we can use the index to directly locate the relevant tuples. This is very efficient, especially for equality conditions. The cost depends on the index structure (e.g., B-tree).
• Hash Table Scan: If a hash index is available, we can directly compute the hash value of the selection attribute and retrieve the corresponding bucket, significantly reducing the search space.

Join Operation (⋈)

The join operation combines tuples from two relations based on a join condition. This is often the most expensive operation in a query. Several algorithms exist:

1. Nested Loop Join (NLJ)

This is the simplest join algorithm. For each tuple in the outer relation, it scans the entire inner relation to find matching tuples.

Algorithm: For each tuple t1 in R: For each tuple t2 in S: If t1 and t2 satisfy the join condition, then output t1 ⋈ t2.

Cost: O(N * M), where N is the number of tuples in R and M is the number of tuples in S. This is very inefficient for large relations.

Block Nested Loop Join: An improvement where blocks of tuples from the outer relation are read into memory, and then the inner relation is scanned for each block. This reduces the number of disk I/Os.

2. Block Nested Loop Join (BNLJ)

This algorithm reads blocks of tuples from the outer relation into memory and then scans the inner relation once for each block.

Algorithm: Read a block of tuples from R into a buffer (B_R). Scan S. For each tuple t2 in S, check if it joins with any tuple in B_R. Repeat until all blocks of R are processed.

Cost: O(N * M / B), where B is the size of the buffer in terms of number of tuples. It's better than NLJ if B > 1.

3. Indexed Nested Loop Join (INLJ)

This algorithm is efficient when one of the relations (say, S) has an index on the join attribute. For each tuple in the outer relation (R), it uses the index on S to quickly find matching tuples in S.

Algorithm: For each tuple t1 in R: Use the index on S.join_attr to find tuples in S that match t1.join_attr. Output the joined tuples.

Cost: O(N * log_bM) if R is the outer relation and S has an index, where b is the block size. This is significantly better than NLJ for large relations.

4. Sort-Merge Join

This algorithm first sorts both relations on the join attribute and then merges them.

Algorithm: Sort R on the join attribute to get R'. Sort S on the join attribute to get S'. Merge R' and S' to find matching tuples.

Cost: O(N log N + M log M) for sorting, plus O(N+M) for merging. This is efficient if the relations are already sorted or if the cost of sorting is less than the cost of other join methods.

5. Hash Join

This algorithm uses hash tables. It partitions both relations into smaller sets based on the hash value of the join attribute. Then, it joins the corresponding partitions.

Algorithm: Build Phase: Choose one relation (say, R) as the build input. Hash its tuples on the join attribute and store them in a hash table in memory. Probe Phase: For each tuple in the other relation (S, the probe input), hash its join attribute and probe the hash table to find matching tuples.

Cost: On average, O(N + M). This is generally the most efficient join algorithm for large, unsorted relations when memory is sufficient to hold the hash table for the build relation.

Projection Operation (Π)

The projection operation eliminates columns from a relation. It also removes duplicate rows.

• Sort-Based Projection: Sort the relation on the projection attributes, then scan to eliminate duplicates. Cost is dominated by sorting.
• Hash-Based Projection: Use a hash table to group tuples with the same projection attribute values, then eliminate duplicates. Average cost is O(N).

Set Operations (Union, Intersection, Difference)

These operations combine or compare tuples from two relations.

• Sort-Based: Sort both relations on all attributes, then perform a merge-like pass to compute the set operation.
• Hash-Based: Use hash tables to group tuples and perform the operation.

Query Optimization

Query optimization is the process of finding the most efficient way to execute a given query. Since there can be many equivalent ways to execute a query (different join orders, different algorithms for operations), the optimizer's role is to select the plan with the lowest estimated cost.

Cost Estimation

To choose the best plan, the system needs to estimate the cost of each plan. The cost is typically measured in terms of I/O operations (disk reads/writes) and CPU time. This estimation relies on:

• Database Statistics: Information about the data, such as the number of tuples in each relation, the number of distinct values for each attribute, and the distribution of values.
• System Information: Information about the hardware, such as disk speed, memory size, and CPU speed.

For example, to estimate the cost of a selection `σ<sub>A=v</sub>(R)`, we need to know the number of tuples in R (N), the number of distinct values of A (distinct(R, A)), and whether an index exists on A.

If there is no index, the estimated number of tuples returned is N / distinct(R, A). If there is an index, the cost is much lower and depends on the index type.

Optimization Techniques

Query optimizers employ various techniques to find the best plan.

1. Heuristic Optimization

This approach uses a set of rules (heuristics) to transform the query tree into a more efficient one. It doesn't explore all possible plans but relies on general principles.

• Pushing Selections Down: Move selection operations as close to the leaf nodes (relations) as possible. This reduces the number of tuples that need to be processed by subsequent operations, especially joins.
• Pushing Projections Down: Move projection operations down to reduce the number of columns processed.
• Avoiding Cross Products: Try to replace cross products with joins whenever possible.
• Order of Joins: Choose a join order that minimizes intermediate results, often by joining smaller relations first or relations with good join conditions.

Example: Consider `(R ⋈ S) ⋈ T`. If we have a selection `σ<sub>A=v</sub>(R)`, it's better to apply it before the joins: `(σ<sub>A=v</sub>(R) ⋈ S) ⋈ T`.

2. Cost-Based Optimization

This is the more sophisticated approach used in most modern database systems. It generates multiple possible execution plans and estimates the cost of each plan using database statistics. The plan with the lowest estimated cost is chosen.

This involves:

• Generating Equivalent Plans: Exploring different join orders, different join algorithms, and different ways to implement operations.
• Cost Estimation: Using statistics to estimate the cost of each plan.
• Selecting the Minimum Cost Plan: Choosing the plan with the lowest estimated cost.

Dynamic Programming for Join Order Optimization

For queries involving multiple joins, the number of possible join orders can be very large. Dynamic programming is often used to efficiently find the optimal join order.

The principle is to build up optimal plans for joining subsets of relations.

Let `Opt(S)` be the optimal plan for joining the set of relations `S`.

To compute `Opt(S)`, we consider all possible ways to split `S` into two non-empty subsets `S1` and `S2` such that `S1 ∪ S2 = S` and `S1 ∩ S2 = ∅`. We then consider joining the optimal plan for `S1` with the optimal plan for `S2`.

`Opt(S) = min { Cost(Opt(S1) ⋈ Opt(S2)) }` for all valid splits `S1`, `S2`.

The base cases are `Opt({Ri})`, which is just the relation `Ri` itself.

This approach systematically finds the best join order by considering all subproblems and combining their optimal solutions.

System R Optimizer (An Early Example)

The System R optimizer was one of the first to employ cost-based optimization using dynamic programming for join ordering. It considered different join orders and different algorithms for each operation, using a cost model based on I/O and CPU. It also implemented heuristics like pushing selections down.

Modern Optimizers

Modern database optimizers are highly sophisticated. They:

• Handle complex SQL features (subqueries, outer joins, aggregates).
• Consider various physical operators (different join algorithms, index usage, sort orders).
• Use detailed statistics and adaptive optimization techniques (re-optimizing during execution if statistics are inaccurate).
• Support parallel execution plans.

Example Scenario: Optimizing a Join Query

Consider a query to join three tables: `Employees (E)`, `Departments (D)`, and `Projects (P)`. `SELECT * FROM Employees E, Departments D, Projects P WHERE E.dept_id = D.id AND D.proj_id = P.id AND E.salary > 50000;`

Possible join orders (ignoring the selection for a moment):

• (E ⋈ D) ⋈ P
• (E ⋈ P) ⋈ D
• (D ⋈ E) ⋈ P
• (D ⋈ P) ⋈ E
• (P ⋈ E) ⋈ D
• (P ⋈ D) ⋈ E

The optimizer would:

1. Parse the query and convert it to a relational algebra expression.
2. Apply heuristics: Push the selection `E.salary > 50000` down to the Employees table.
3. Generate possible join orders for `(σ<sub>E.salary > 50000</sub>(E) ⋈ D ⋈ P)`.
4. For each join order, consider different join algorithms (Nested Loop, Hash Join, Sort-Merge Join) and the possibility of using indexes on join attributes.
5. Estimate the cost of each complete plan (including the selection, projections, and joins).
6. Choose the plan with the minimum estimated cost.

For instance, if `Employees` is very large but has an index on `dept_id`, and `Departments` is smaller, the optimizer might choose to join `Employees` and `Departments` first using an indexed nested loop or hash join, and then join the result with `Projects`.