Query Processing and Optimization

Introduction

A database system is useful only when it can answer queries efficiently as well as correctly. A declarative query language such as SQL allows users to specify what data they need without describing the exact sequence of operations required to obtain it. Query processing is the set of activities through which a database management system (DBMS) translates a query into an executable procedure, accesses stored data, and returns the result. Query optimization is the process of selecting an efficient execution strategy from many logically equivalent alternatives.

Optimization is especially important in analytical systems, cloud databases, and AI/ML applications. Training-data preparation, feature extraction, event aggregation, and model monitoring often involve joins, grouping, filtering, and sorting over millions or billions of rows. A poor plan can consume excessive CPU, memory, storage bandwidth, and energy. This chapter examines parsing, logical and physical plans, access methods, join algorithms, cost estimation, statistics, rule-based and cost-based optimization, and the practical interpretation of execution plans.

Learning Objectives

By the end of this chapter, a student should be able to:

1. Explain the stages of query processing.

2. Distinguish relational-algebra plans from physical execution plans.

3. Describe selection, projection, sorting, aggregation, and join algorithms.

4. Explain cardinality estimation and common cost models.

5. Compare heuristic and cost-based optimization.

6. Interpret execution plans and diagnose performance problems.

7. Recommend suitable indexing, query-rewriting, and data-design improvements.

8. Recognize limitations, governance concerns, and emerging developments in optimization.

1. The Query-Processing Pipeline

A typical DBMS processes a SQL statement through the following stages:

1. Parsing and validation: lexical analysis identifies keywords, names, literals, and operators. The parser constructs a parse tree and checks SQL syntax. Semantic analysis verifies that tables and columns exist, data types are compatible, and the user has appropriate privileges.

2. Translation: the validated statement is translated into an internal representation, commonly relational algebra or an equivalent logical query graph.

3. Logical optimization: algebraic transformations produce equivalent expressions that may require less work. Examples include pushing selections below joins and eliminating unused columns.

4. Physical optimization: the optimizer selects access paths and algorithms, such as an index scan instead of a table scan or hash join instead of nested-loop join.

5. Plan generation and execution: the selected plan is compiled or interpreted. The execution engine requests tuples from operators, often using a producer-consumer or iterator model.

6. Result production: rows are formatted and returned to the client, while locks, transactions, buffers, and temporary structures are managed by the DBMS.

The distinction between logical correctness and physical efficiency is fundamental. Two plans can produce exactly the same relation while differing by orders of magnitude in execution time.

2. Logical Query Plans

Relational algebra provides a formal language for logical plans. Important operators include:

• Selection (σ): filters tuples satisfying a predicate.
• Projection (π): retains specified attributes.
• Join (⋈): combines tuples according to a condition.
• Grouping and aggregation (γ): computes functions such as COUNT, SUM, or AVG.
• Union, intersection, and difference: combine compatible relations.
• Sorting (τ): orders tuples, although sorting is often treated as a physical rather than purely relational operation.

For example, consider:

```sql

SELECT c.customer_id, SUM(o.amount) AS total

FROM Customer c JOIN Orders o ON c.customer_id = o.customer_id

WHERE c.region = 'North'

GROUP BY c.customer_id;

```

A direct logical expression is:

γ customer_id, SUM(amount) ( σ region='North' (Customer) ⋈ Orders ).

A better equivalent expression first filters customers and then joins:

γ customer_id, SUM(amount) ( σ region='North'(Customer) ⋈ Orders ).

The transformation is valuable because fewer customer tuples participate in the join. Projection can also be pushed down, provided that columns needed for join predicates, filters, grouping, and final output are retained. A DBMS must preserve semantics: a predicate cannot be pushed below an outer join indiscriminately, and transformations involving NULL values, duplicates, aggregation, or nondeterministic functions require care.

Logical Equivalence and Relational Properties

Common transformations rely on properties such as:

• Selection predicates can often be decomposed: σ(P AND Q)(R) is equivalent to σP(σQ(R)).
• Independent selections can often be reordered.
• Inner joins are associative and commutative, allowing alternative join orders.
• A selection involving only attributes of one input can often be pushed to that input.
• Projection can be pushed down if all attributes needed later are preserved.

These rules generate alternatives without changing the answer. They do not by themselves identify the fastest plan; physical costs and data statistics are still required.

3. Physical Query Plans and the Iterator Model

A physical plan specifies how each logical operation will be performed. A plan may contain a sequential scan, index scan, sort, hash build, hash probe, nested-loop join, or parallel exchange. Plans are commonly represented as trees. A parent operator requests rows from its child operators.

In the iterator model, an operator exposes methods such as `open`, `next`, and `close`. A filter requests a row from its child, tests the predicate, and returns qualifying rows. This model supports pipelining: a tuple can flow through several operators without being written to disk. Blocking operators, such as a full sort or some forms of aggregation, must consume all or much of their input before producing output.

Modern systems may also use vectorized execution, in which operators process batches of rows, or compiled execution, in which a plan is converted into specialized machine code. These approaches reduce function-call overhead and improve CPU-cache utilization, but they do not remove the need for sound logical and cost optimization.

4. Selection and Access Algorithms

A selection applies a predicate, such as `salary > 50000`. The principal access methods are:

Sequential Scan

A sequential scan reads pages of a relation and tests each tuple. It is appropriate when the relation is small, when a large fraction of rows qualifies, or when no useful index exists. It also benefits from sequential I/O and read-ahead.

Index Scan

An index scan traverses an index to locate qualifying records. B+-trees support equality and range predicates; hash indexes are primarily useful for equality predicates. An index is attractive when selectivity is high, meaning that only a small fraction of rows qualifies. However, many random lookups into a heap can cost more than one sequential scan. A covering index, containing all columns needed by a query, may avoid base-table lookups.

Selection and Selectivity

The selectivity of a predicate is the fraction of input tuples expected to satisfy it. If relation R has N tuples and selectivity s, the estimated result cardinality is commonly:

|σP(R)| ≈ sN.

This estimate assumes that s is a reasonable representation of the predicate and that relevant correlations are handled. Uniformity and independence assumptions are often convenient but can be wrong. For example, city and postal code are correlated, and a simple product of independent selectivities may severely misestimate a combined predicate.

5. Join Algorithms

Joins frequently dominate query cost. The choice depends on relation sizes, indexes, available memory, ordering, parallelism, and predicate type.

Nested-Loop Join

For each tuple in an outer relation, the algorithm scans the inner relation and tests the join condition. Its basic form is simple but can be expensive. A block nested-loop join improves locality by processing a block of outer pages at a time. If an index exists on the inner join attribute, an index nested-loop join can be highly effective when the outer input is small and each lookup is selective.

Hash Join

For an equijoin, a hash join builds a hash table on the smaller input using the join key, then scans the other input and probes the table. A two-phase grace hash join partitions both inputs into matching hash partitions when they do not fit in memory. Hash joins are generally unsuitable for arbitrary inequality predicates and may spill to disk if memory estimates are inadequate.

Sort-Merge Join

Sort-merge join sorts both inputs on the join attribute and then merges them. It supports equality joins and can be adapted to certain ordered predicates. It is attractive when inputs are already sorted, when sorted output is required, or when external sorting is efficient. Its disadvantages include sorting cost and temporary storage when inputs are not ordered.

Join Ordering

For several inner joins, different orders can have dramatically different intermediate sizes. A good optimizer usually tries to apply selective filters early and to form small intermediate results. Nevertheless, “smallest relation first” is not a universal rule: indexes, available memory, parallelism, and join selectivity also matter.

6. Sorting, Aggregation, and Duplicate Elimination

Sorting may use an in-memory algorithm when the data fits in memory. For larger inputs, external merge sort creates sorted runs and repeatedly merges them using temporary storage. The number of passes depends on relation size, page size, and available buffers.

Aggregation can be implemented by sorting on grouping attributes or by hashing groups. Hash aggregation is often efficient when groups fit in memory; it may spill or repartition when they do not. Sort-based aggregation is useful when ordered output is already needed. A query such as `COUNT(*) GROUP BY department_id` may therefore have several valid physical implementations.

7. Cost Models and Cardinality Estimation

A cost model predicts resource consumption rather than measuring exact future time. Common components include disk I/O, CPU operations, memory use, network transfer, and sometimes energy. In disk-oriented systems, a simplified cost for a sequential scan is approximately the number of pages read. Let B(R) be the number of pages in relation R; then a full scan has an I/O cost proportional to B(R). This is a model, not a universal runtime equation: caching, concurrency, compression, storage technology, and parallelism alter actual behavior.

For a simple equality join R ⋈ S on attributes with distinct-value counts V(R,A) and V(S,B), a frequently used estimate is:

|R ⋈ S| ≈ |R| × |S| / max(V(R,A), V(S,B)).

This estimate assumes uniform value distribution and that the join domains overlap in a way captured by the maximum distinct-value count. If the domains do not overlap, or if values are highly skewed, the estimate can be inaccurate.

For a selection on an attribute with a unique index, an equality predicate may have an estimated selectivity near 1/|R|, assuming the value exists and NULL behavior is excluded. For a nonunique attribute, histograms provide a better estimate than a single average. Histograms divide values into ranges or frequency classes. Most-common-value statistics represent skew explicitly.

Worked Example: Cardinality and Plan Choice

Suppose `Orders` contains 1,000,000 rows. The optimizer estimates that `status = 'Cancelled'` has selectivity 0.02. The estimated result is therefore:

1,000,000 × 0.02 = 20,000 rows.

If a sequential scan reads 20,000 pages, while an index lookup requires approximately 20,000 random row accesses plus index traversal, the index may not be preferable on a slow random-I/O device. If a covering index can return the qualifying rows in a compact ordered structure, its cost may be lower. The correct choice depends on page counts, clustering, cache state, and the DBMS cost model; selectivity alone does not determine the plan.

8. Rule-Based and Cost-Based Optimization

Rule-based optimization applies established transformations or preferences. Typical rules include pushing selections and projections, using indexes for selective predicates, and choosing a smaller input as the hash-build side. Rule systems are fast and predictable but may ignore interactions among data size, physical layout, and hardware.

Cost-based optimization (CBO) generates candidate plans, estimates their costs using catalog statistics, and selects the least-cost plan according to its model. Exhaustively enumerating all join orders is expensive because the search space grows rapidly with the number of relations. Optimizers therefore use dynamic programming, branch-and-bound, randomized search, or restricted heuristics. Many practical systems combine rules with CBO: semantic transformations reduce the search space, and cost estimation selects among physical alternatives.

The optimizer's decision is only as reliable as its statistics. Stale statistics, data skew, correlated predicates, parameter-sensitive values, and inaccurate assumptions can cause a poor plan. Adaptive query processing can observe runtime behavior and revise decisions, for example by changing join strategies after detecting that a cardinality estimate was wrong.

9. Reading and Diagnosing Execution Plans

An execution plan should be read from the leaves toward the root, while remembering that displayed cost is usually an estimate, not a measurement. Important fields include:

• estimated and actual row counts;
• estimated and actual time;
• access method and chosen indexes;
• join algorithm and join order;
• number of loops or re-scans;
• memory granted and temporary spills;
• parallel workers and data exchanges;
• filtering performed at each operator.

A major difference between estimated and actual cardinality is a warning sign. It may indicate stale statistics, correlation, skew, an incorrect predicate assumption, or a parameter-sensitive plan. A nested-loop join repeatedly scanning a large input may indicate a missing index or a poor join order. A sort or hash operator spilling to disk suggests inadequate memory, excessive intermediate data, or an unsuitable algorithm. Large network exchanges may reveal that filtering or aggregation occurs too late in a distributed system.

A disciplined tuning process is: establish a baseline; inspect the actual plan; identify the dominant resource; verify estimates; update statistics if appropriate; rewrite the query only when it improves semantics or plan freedom; add or modify indexes cautiously; test with representative data; and measure again. The goal is not to force a particular operator but to improve robust performance across realistic workloads.

10. Applied Case: Feature-Store Query Performance

Background. This illustrative case concerns a retail company that builds daily machine-learning features from `Customers`, `Orders`, and `Payments`. A query joins 50 million orders to payment records, filters to the last 30 days, groups by customer, and returns purchase totals.

Problem. The query takes 18 minutes. Its actual plan shows a sequential scan of all historical orders, a large hash join, and a disk spill during aggregation. Estimated rows after the date filter are 2 million, but the actual number is 14 million because statistics are six months old and recent activity is highly concentrated.

Analysis. The stale estimate leads the optimizer to grant too little memory and choose a plan designed for a much smaller input. The date predicate is written on an indexed timestamp column without a function applied to that column, so it is eligible for an index or partition-pruning strategy. However, the existing index is not covering and causes many random lookups.

Approach. Engineers first refreshed statistics and created a partitioning scheme by order month. They added a composite, selectively designed index supporting the date predicate and customer key, while retaining only columns justified by workload analysis. The query was rewritten to aggregate recent orders before joining to payments, because payment data was needed only for customers with qualifying orders. The team validated that the rewrite preserved duplicate and NULL semantics, then tested plans with production-like data volumes.

Outcome. Partition pruning reduced the scanned order data to the relevant months. Early aggregation reduced the join input substantially, and the corrected statistics produced an adequate memory grant. Runtime fell to approximately two minutes in representative tests. The improvement did not come from one universal trick; it resulted from matching logical transformations, physical design, statistics, and workload characteristics.

Learning points. Actual plans are essential; stale statistics can be as harmful as missing indexes; early reduction is useful but must preserve semantics; and indexes should be evaluated against write cost, storage, and the complete workload.

11. Limitations, Governance, and Contemporary Developments

Optimization is not merely a technical speed contest. Additional indexes increase storage and update overhead. Aggressive caching can create unfair resource allocation among users. Query plans can expose sensitive table names, predicates, or data volumes through monitoring interfaces, so access to diagnostic information should be controlled. In regulated settings, organizations should retain appropriate records of data access, performance changes, and automated decisions that depend on database outputs.

AI-assisted tuning systems increasingly recommend indexes, detect anomalies, forecast workload changes, and learn cardinality models. These systems can be useful, but recommendations require validation: training data may reflect temporary workloads, models may fail under distribution shift, and automated changes can harm write performance or create governance risks. Explainable recommendations, rollback mechanisms, workload isolation, and human approval are prudent practices.

Cloud and distributed databases introduce additional considerations: network cost, data locality, shuffles, replication, elasticity, and multi-tenant contention. Columnar storage, vectorized execution, approximate query processing, learned statistics, and adaptive plans are important contemporary developments. None eliminates the core principles of semantic correctness, sound estimates, appropriate physical design, and measurement using representative workloads.

Best Practices

1. Write semantically clear, set-oriented queries and avoid unnecessary columns.

2. Keep statistics current and collect histograms or extended statistics where correlations matter.

3. Inspect actual execution plans, not only estimated plans.

4. Push selective predicates and safe projections toward data sources.

5. Index based on recurring predicates, joins, ordering, and covering opportunities—not on every column.

6. Test parameterized queries with representative parameter values.

7. Monitor spills, memory grants, scans, loops, and cardinality errors.

8. Benchmark changes under realistic concurrency and update workloads.

9. Treat optimizer hints as controlled exceptions, not substitutes for diagnosis.

10. Document changes and provide rollback paths.

Chapter Summary

Query processing converts declarative SQL into executable operations through parsing, semantic validation, logical translation, optimization, physical plan selection, and execution. Logical plans describe relational meaning, whereas physical plans specify algorithms and access paths. Selection, indexing, nested-loop, hash, and sort-merge joins, sorting, and aggregation each have conditions under which they are effective. Cost-based optimization relies on cardinality estimates, histograms, distinct-value counts, and assumptions that may fail under skew or correlation. Rule-based transformations remain valuable for reducing the search space and improving expressions safely. Execution plans reveal access methods, join order, estimates, actual behavior, memory use, and spills. Effective tuning combines statistics, query design, physical design, measurement, and awareness of governance and workload trade-offs.

Key Terms

Parsing: Converting SQL text into a syntactic and semantic representation.

Logical query plan: A relational-algebra representation of what operations are required.

Physical query plan: A specification of algorithms, access paths, and execution operators.

Selection: An operation that filters tuples using a predicate.

Projection: An operation that retains selected attributes.

Selectivity: The fraction of input tuples expected to satisfy a predicate.

Cardinality: The number of tuples produced by a relation or operator.

Sequential scan: Reading relation pages in storage order and testing tuples.

Index scan: Using an index to locate qualifying records.

Nested-loop join: A join that compares inner tuples for each outer tuple or block.

Hash join: An equijoin using a hash table to match join keys.

Sort-merge join: A join that sorts inputs and merges matching key values.

Histogram: A statistical summary of value distribution across ranges or frequencies.

Cost model: A model estimating resources required by a plan.

Rule-based optimization: Optimization using predefined semantic or heuristic transformations.

Cost-based optimization: Choosing among candidate plans using estimated costs.

Cardinality estimation: Predicting operator result sizes.

Pipelining: Passing tuples directly between operators without materializing them.

Blocking operator: An operator that must consume substantial input before producing output.

Execution plan: The operator tree and properties used to execute a query.

Review Questions

Short Answer Questions

1. What is the difference between a logical query plan and a physical query plan?

2. Why can pushing a selection below a join improve performance?

3. When is an index scan likely to be preferable to a sequential scan?

4. State one strength and one limitation of hash joins.

5. Why are actual execution plans valuable during performance diagnosis?

Long Answer Questions

1. Explain the complete query-processing pipeline from SQL parsing to result production.

2. Compare nested-loop, hash, and sort-merge joins, including their assumptions and appropriate use cases.

3. Explain cardinality estimation using selectivity, distinct-value counts, and histograms. Discuss sources of error.

4. Compare rule-based and cost-based optimization and explain why modern systems commonly combine them.

5. Describe a systematic method for diagnosing and improving a slow query using an execution plan.

Analytical / Application Questions

1. A query filters 5% of a large table and joins the result to another large table on an equality key. Propose candidate access paths and join algorithms, and explain what statistics are needed before choosing among them.

2. An actual plan estimates 100,000 rows after a predicate but produces 8 million. Analyze at least four possible causes and recommend a diagnostic sequence.

3. Design a performance-improvement strategy for a machine-learning feature query involving a date filter, a large join, and grouped aggregates. Address query rewriting, indexing or partitioning, statistics, validation, and operational trade-offs.

Multiple Choice Questions with Answers

Question 1

Which stage verifies that referenced tables and columns exist and that data types are compatible?

A. Semantic analysis

B. Physical execution

C. Buffer replacement

D. Result formatting

Correct Answer: A. Semantic analysis

Question 2

Which operator is generally used to reduce rows by applying a predicate?

A. Projection

B. Selection

C. Sorting

D. Union

Correct Answer: B. Selection

Question 3

Which join algorithm is primarily designed for equijoins using a hash table?

A. Nested-loop join

B. Sort-merge join

C. Hash join

D. Cartesian join

Correct Answer: C. Hash join

Question 4

If a relation has 1,000,000 rows and a predicate has estimated selectivity 0.02, what is the estimated result cardinality?

A. 2,000 rows

B. 20,000 rows

C. 200,000 rows

D. 500,000 rows

Correct Answer: B. 20,000 rows

Question 5

Which statistic is particularly useful for representing highly frequent individual values?

A. Most-common-value statistics

B. Transaction log size

C. Page replacement count

D. Number of indexes

Correct Answer: A. Most-common-value statistics

Question 6

What is a major limitation of a cost-based optimizer?

A. It cannot represent joins

B. It depends on the accuracy of statistics and cost estimates

C. It always chooses sequential scans

D. It cannot use logical transformations

Correct Answer: B. It depends on the accuracy of statistics and cost estimates

Question 7

Which situation commonly indicates that an operator is exceeding its available memory?

A. A disk spill during sorting or hashing

B. A successful index-only scan

C. A reduced projection list

D. A cached metadata lookup

Correct Answer: A. A disk spill during sorting or hashing

Question 8

Why can early aggregation improve a large join query?

A. It increases the number of intermediate tuples

B. It removes the need for semantic validation

C. It can reduce the amount of data entering the join

D. It guarantees that an index will be used

Correct Answer: C. It can reduce the amount of data entering the join

Question 9

What does a large difference between estimated and actual row counts most directly suggest?

A. A possible cardinality-estimation problem

B. That the SQL parser failed

C. That all indexes are invalid

D. That the result is necessarily incorrect

Correct Answer: A. A possible cardinality-estimation problem

Question 10

Which practice is most appropriate when evaluating a query-tuning change?

A. Test only with a tiny synthetic table

B. Force a join algorithm without measurement

C. Measure using representative data and workload conditions

D. Ignore update and storage costs

Correct Answer: C. Measure using representative data and workload conditions