Query Performance and Database Optimization

Introduction

A database query can be logically correct yet operationally poor. In a small development database, an inefficient query may appear harmless; in production, the same query can consume CPU, exhaust memory, delay transactions, and reduce the responsiveness of an entire application. Query performance is therefore not merely a matter of making one statement execute quickly. It is the disciplined study of how data is stored, accessed, joined, filtered, sorted, and returned under realistic workloads.

Database optimization combines relational theory, storage-engine behavior, indexing, statistics, query rewriting, measurement, and operational judgment. The optimizer normally chooses an execution plan, but its choice depends on the available indexes, table design, data distribution, statistics, and estimated cost. Developers and database professionals must be able to interpret that choice, identify its weaknesses, and improve the system without compromising correctness.

This chapter uses SQL concepts common to systems such as PostgreSQL, MySQL, SQL Server, and Oracle. Syntax and plan terminology differ among products, so production decisions must be verified against the documentation for the selected database management system (DBMS).

Learning Objectives

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

• interpret the main components of an execution plan;
• distinguish logical query processing from physical execution;
• design, test, and maintain useful indexes;
• explain the role of statistics and cardinality estimates;
• rewrite inefficient queries without changing their meaning;
• detect common SQL performance anti-patterns;
• measure performance using repeatable, evidence-based methods; and
• evaluate optimization decisions in relation to concurrency, maintenance, and business requirements.

1. The Performance Model

A query passes through several stages. The DBMS parses SQL, validates names and data types, transforms the relational expression, considers alternative physical plans, estimates their costs, selects a plan, and executes it. The optimizer does not usually search every theoretically possible plan. It applies transformation rules and cost-based decisions to find a sufficiently good plan within practical planning time.

Logical and physical processing

The logical meaning of a query is expressed through relational operations such as selection, projection, join, grouping, and ordering. Physical execution chooses mechanisms for implementing those operations. For example, a selection may be implemented by:

• a sequential or table scan;
• an index seek or index range scan;
• a bitmap-assisted access path; or
• a partition-pruned scan.

A join may use a nested-loop join, hash join, or merge join. These are not interchangeable in cost. A nested-loop join can be excellent when the outer input is small and the inner input is indexed, but poor when both inputs are large. A hash join is often effective for large equality joins, whereas a merge join can be attractive when inputs are already ordered.

A simple cost perspective

Execution time is influenced by many factors, including disk reads, memory access, CPU processing, network transfer, locking, parallelism, and concurrent workload. A useful conceptual model is:

Here, T_total is observed elapsed time; T_startup is fixed or initial work; T_CPU is processor time; T_IO is time spent reading or writing storage; T_wait includes lock, buffer, and scheduling waits; and T_network is data-transfer time. This is a diagnostic model rather than an exact universal equation. The components may overlap, particularly in parallel or asynchronous execution.

The amount of data returned also matters. A query that performs efficiently but sends millions of unnecessary rows to an application can still create a serious system bottleneck.

2. Reading Execution Plans

An execution plan is a tree or graph of physical operators. The plan describes how the DBMS obtains rows, combines them, transforms them, and returns them. In most systems, the plan can be viewed in estimated form and, using an option such as EXPLAIN ANALYZE, in actual form.

Important plan properties

Cost units are DBMS-specific. A cost of 100 in one system cannot be compared directly with a cost of 100 in another, and cost is not necessarily milliseconds.

Access methods

A table scan reads many or all data pages. It is not automatically bad. If a query needs a large proportion of a table, a sequential scan may be cheaper than performing many random index lookups. An index scan or seek uses an index to locate qualifying entries, possibly followed by lookups into the base table. The benefit is greatest when the predicate is selective and the index supports the required columns.

A covering index contains all columns needed by a query, allowing the DBMS to avoid additional base-table lookups. Covering indexes can reduce I/O, but they increase storage and write-maintenance costs.

Join operators

A nested-loop join repeatedly probes the inner input for each outer row. Its approximate work depends on the number of outer rows and the cost of each inner probe. It is often appropriate for a small outer result and an indexed inner relation.

A hash join builds a hash table from one input and probes it with the other. It normally supports equality predicates and can be effective for large, unsorted inputs. If the hash table does not fit in memory, the DBMS may spill to temporary storage.

A merge join reads two inputs in join-key order. It can be efficient when suitable indexes or prior sorting provide that order, but sorting large inputs can be expensive.

Cardinality-estimation errors

Cardinality is the number of rows expected or actually produced by an operator. An estimate that is substantially lower or higher than reality can lead to an unsuitable plan. For example, underestimating a result may cause the optimizer to choose nested loops and insufficient memory for a hash operation. Severe errors commonly arise from stale statistics, correlated predicates, data skew, expressions on columns, or assumptions of independence between predicates.

The first practical comparison should be between estimated and actual rows at major operators. If an operator estimates 100 rows but returns 2,000,000, the estimation error is not a minor detail; it may explain the rest of the plan.

3. Index Design and Maintenance

An index is an auxiliary data structure that helps locate rows or produce rows in a useful order. A B-tree index is effective for equality and range conditions such as =, <, >, BETWEEN, and many ordered retrievals. Hash indexes, inverted indexes, spatial indexes, and specialized structures serve other workloads.

Selectivity and usefulness

Selectivity describes how narrowly a predicate identifies rows. A unique identifier is usually highly selective; a Boolean column with values such as TRUE and FALSE is usually less selective. Selectivity is data-dependent and changes over time.

An index is most valuable when it reduces expensive work. Indexing every column is not a solution because indexes consume storage, slow inserts, updates, and deletes, and increase maintenance and optimization complexity.

Composite indexes

A composite index contains multiple columns. Column order matters. Consider:

CREATE INDEX ix_orders_customer_status_date
ON orders (customer_id, status, order_date);

This index is generally useful for predicates beginning with customer_id, and may support combinations involving the leading columns. It may be less useful for a query filtering only on order_date, because that column is not the leading search key. The exact behavior depends on the DBMS and access method.

Index design should reflect common predicates, join keys, ordering requirements, and projected columns. A practical process is:

1. identify frequent or business-critical queries;
2. inspect their predicates, joins, grouping, and ordering;
3. examine existing indexes and their usage;
4. propose the smallest index that supports the workload;
5. test it against representative data and concurrent activity; and
6. monitor whether it remains beneficial.

Sargability

A predicate is commonly called sargable when the DBMS can use an index search argument efficiently. These forms often preserve sargability:

WHERE order_date >= DATE '2025-01-01'

By contrast, applying a function to the indexed column may prevent an ordinary index from being used effectively:

WHERE YEAR(order_date) = 2025

A range predicate is often preferable:

WHERE order_date >= DATE '2025-01-01'
  AND order_date <  DATE '2026-01-01'

The correct syntax for date literals and functions varies by DBMS. Time-zone semantics must also be considered.

Partial, filtered, expression, and included indexes

Some systems support partial or filtered indexes, which index only rows satisfying a condition. These are useful when a small, stable subset is queried frequently. Expression or function-based indexes can support predicates involving computed values, but they introduce requirements for expression determinism and matching query syntax. Included or non-key columns can create covering indexes without changing the search-key order in systems that support them.

Write cost and index maintenance

Every index potentially requires modification when indexed data changes. A rough workload-level principle is:

where f_i is the frequency of updates affecting index i, and c_i is the average maintenance cost for that index. This is a conceptual relationship, not a DBMS-independent measurement formula. It assumes the costs are being compared under the same workload and hardware conditions. An index that saves 20 milliseconds on a rare read may not justify substantial write overhead on a high-volume table.

Indexes also require statistics, may become fragmented or physically disorganized depending on the DBMS, and can become redundant after schema evolution. Maintenance should be guided by evidence rather than performed automatically without diagnosis.

4. Statistics and the Optimizer

The optimizer estimates row counts using statistics such as value distributions, distinct-value counts, minimum and maximum values, and histograms. Statistics may be collected automatically or manually. They become less reliable after substantial data modification, changes in distribution, or bulk loading.

Suppose a query filters on a column with a highly uneven distribution. A uniform-distribution assumption may greatly underestimate a common value or overestimate a rare one. Histograms improve estimates by representing ranges or frequency patterns. However, statistics are summaries, not complete descriptions of the data.

Correlated predicates create another difficulty. If country and currency are strongly related, treating them as independent can produce an incorrect estimate for:

WHERE country = 'GB' AND currency = 'GBP'

Some DBMSs support extended or multi-column statistics to represent such relationships. The appropriate remedy may instead be schema redesign, query simplification, or a better index.

After a significant data change, statistics may need refreshing. A plan should be rechecked after statistics updates because a new plan can be better, worse, or simply different. Plan stability mechanisms, such as baselines or hints, should be used cautiously: forcing a plan can protect against regressions but can also preserve an obsolete decision.

5. Rewriting Inefficient Queries

Optimization must preserve semantics. A faster query that returns different rows is incorrect.

Retrieve only what is needed

Avoid SELECT * in production interfaces when only a few columns are required. Explicit projection can reduce I/O, network transfer, memory use, and coupling to schema changes.

Filter early, but understand the optimizer

Relational optimizers can often push filters below joins automatically. Nonetheless, clear predicates and correct join conditions help both the optimizer and human reviewers. Early filtering is especially important when it reduces a large intermediate result.

Replace unnecessary distinctness

DISTINCT may hide duplicate-producing joins and force sorting or hashing. First determine why duplicates occur. If the requirement is to test whether a related row exists, EXISTS often communicates the intent more directly:

SELECT c.customer_id
FROM customers AS c
WHERE EXISTS (
    SELECT 1
    FROM orders AS o
    WHERE o.customer_id = c.customer_id
      AND o.status = 'OPEN'
);

This should not be treated as a universal guarantee of better performance; the plan depends on indexes, statistics, and data size.

Avoid accidental Cartesian products

A missing or incomplete join predicate can produce a Cartesian product. If relations contain n and m rows, the unconstrained product contains n × m row combinations before later filtering. This multiplication can overwhelm memory and temporary storage.

Use correct anti-join logic

NOT IN can produce unexpected results when the subquery contains NULL, because SQL uses three-valued logic. When the intended question is whether no matching row exists, NOT EXISTS is often safer:

SELECT c.customer_id
FROM customers AS c
WHERE NOT EXISTS (
    SELECT 1
    FROM orders AS o
    WHERE o.customer_id = c.customer_id
);

The exact semantics must still be verified, particularly when nullable keys are involved.

Pagination

Large offset pagination can require the DBMS to find and discard many preceding rows. Keyset, or seek, pagination uses a stable ordering key:

SELECT order_id, order_date, total_amount
FROM orders
WHERE (order_date, order_id) < (:last_date, :last_id)
ORDER BY order_date DESC, order_id DESC
FETCH FIRST 50 ROWS ONLY;

Row-value syntax varies across DBMSs. The ordering must be deterministic, usually by adding a unique tie-breaker such as order_id, and an appropriate composite index is normally required.

Avoid implicit conversions

Comparing unlike data types can force conversion and prevent efficient index use. Store and compare values using compatible data types. Do not rely on implicit conversion rules, which can differ among DBMSs and may introduce correctness as well as performance problems.

6. Common Performance Anti-Patterns

Functions on indexed columns

As discussed, expressions such as LOWER(email) or CAST(account_id AS ...) may prevent ordinary index access. Use normalized stored values, compatible parameters, or an expression index where justified.

Leading wildcards

A predicate such as LIKE '%phone%' generally cannot use a conventional B-tree index to locate the beginning of the search term. Full-text, trigram, or specialized search technology may be more appropriate.

N+1 queries

An application may issue one query to retrieve parent rows and then one query per parent to retrieve children. For k parents, this can create approximately k + 1 round trips rather than one set-oriented operation. Remedies include joins, carefully designed batch queries, prefetching, or a data-access strategy suited to the relationship.

Over-indexing

Redundant and overlapping indexes increase write cost and can confuse maintenance decisions. Index usage reports should be interpreted with workload coverage in mind: an index that appears unused during a short observation window may support a monthly report.

Unbounded result sets

Returning all rows to an application is risky even when the database can produce them quickly. Apply business-appropriate limits, streaming, batching, or asynchronous export mechanisms.

Parameter-sensitive behavior

A plan optimal for a highly selective parameter may be poor for a common parameter. This is sometimes called parameter sniffing or parameter-sensitive optimization, depending on the DBMS. Remedies include improved statistics, alternative query formulations, recompilation strategies, plan variants, or controlled hints. Each has operational cost and must be tested.

7. Evidence-Based Performance Measurement

Optimization should begin with a measurable problem and end with a verified improvement. A reliable method is:

1. define the service-level or user-facing objective;
2. capture the original query, parameters, schema, indexes, and plan;
3. test with representative data volume and distribution;
4. measure elapsed time, CPU, logical reads, physical reads, rows, waits, and concurrency effects;
5. change one important factor at a time;
6. compare both correctness and performance; and
7. monitor the change after deployment.

Benchmarking principles

Warm-cache and cold-cache results answer different questions. Warm-cache measurements examine repeated execution when pages are already in memory; cold-cache measurements include storage retrieval and are more difficult to reproduce safely. Both should be labeled.

Use multiple executions rather than a single timing. Let t₁, t₂, …, t_n represent measured execution times for n repetitions. The arithmetic mean is:

The mean is useful when the observations are comparable and outliers are understood. Percentiles are often more valuable for user experience. The 95th percentile, p95, is the value at or below which approximately 95% of observations fall, subject to the selected percentile method. It describes tail behavior and is not the same as the mean.

Measure production-like concurrency where possible. A query that is fast in isolation may cause contention when many sessions execute it simultaneously. Conversely, a plan that appears slower in a single-session test may scale better under load.

Query correctness and regression testing

Performance tests must verify result sets, not only timings. Compare row counts, key values, aggregates, and null behavior where appropriate. Test boundary cases, empty results, duplicate values, and concurrent updates. Execution plans may change after upgrades, data growth, statistics refreshes, or hardware changes; performance testing is an ongoing operational practice.

8. Applied Case: Illustrative E-Commerce Order Search

Background

An illustrative online retailer stores 80 million orders. Customer-service agents search recent orders by customer, status, and date. The search endpoint has a target of returning the first page within 300 milliseconds at the 95th percentile.

Problem

The original query is:

SELECT *
FROM orders
WHERE DATE(order_date) = :requested_date
  AND status = :status
ORDER BY order_date DESC
LIMIT 50 OFFSET :offset;

Monitoring shows high logical reads and increasing latency as agents request later pages. The function on order_date reduces the usefulness of an ordinary index, SELECT * transfers unnecessary columns, and large offsets require discarded work.

Analysis

The team captures the actual execution plan and observes a broad scan, a sort, and substantial row removal for high offsets. It also checks whether status has sufficient discrimination and whether the date column includes a time component. Results are validated against a reference query to ensure that changing the date predicate does not alter time-zone or boundary semantics.

Approach and solution

The date condition is rewritten as a half-open range:

WHERE order_date >= :start_of_day
  AND order_date <  :start_of_next_day

The query projects only required columns and uses deterministic keyset pagination:

SELECT order_id, customer_id, order_date, status, total_amount
FROM orders
WHERE status = :status
  AND (order_date, order_id) < (:last_date, :last_id)
  AND order_date >= :start_of_day
  AND order_date <  :start_of_next_day
ORDER BY order_date DESC, order_id DESC
FETCH FIRST 50 ROWS ONLY;

The team tests a composite index such as:

CREATE INDEX ix_orders_status_date_id
ON orders (status, order_date DESC, order_id DESC);

The exact index order is evaluated against the retailer’s workload, including searches by customer and reporting queries. The index is not adopted solely because it improves one test; write overhead and storage are included in the decision.

Outcome

In the test environment, logical reads fall substantially and later-page latency no longer grows linearly with the offset. The team also discovers that a small number of status values are highly common, so statistics are refreshed and production-like parameter distributions are tested. The deployment is released gradually, with p95 latency, CPU, storage reads, error rates, and write latency monitored.

Learning points

The improvement came from several coordinated decisions: preserving sargability, limiting projection, replacing offset pagination, creating an index aligned with access patterns, refreshing statistics, and measuring under representative conditions. No single rule guarantees success. Correctness, workload diversity, and operational effects determine whether a tuning change is appropriate.

9. Professional, Governance, and Contemporary Considerations

Performance tuning can expose sensitive information. Execution plans may reveal table names, predicates, customer identifiers, or literal values. Access to plans, query logs, and monitoring data should follow least-privilege principles, and sensitive values should be masked where possible.

Parameterization is important for both security and performance. Constructing SQL by concatenating untrusted input creates SQL-injection risk and can reduce plan reuse. Parameterization does not eliminate the need to understand parameter-sensitive plans, but it provides a safer and often more stable foundation.

Cloud databases introduce variable resource limits, storage latency, automatic scaling, replicas, and managed maintenance. Distributed SQL systems add network exchanges, data locality, partitioning, and consistency costs. A locally optimal plan may be globally poor if it transfers data across nodes.

AI-assisted coding and database advisors can suggest indexes, rewrites, and anomaly explanations. Their output must be treated as a hypothesis. A generated index may be redundant, a rewrite may change null semantics, and training data may not reflect the organization’s workload. Human review, plan inspection, security checks, and controlled benchmarking remain necessary.

Best practice is therefore evidence-driven rather than rule-driven: establish a baseline, form a specific hypothesis, make a controlled change, verify semantics, measure under realistic conditions, and monitor after release.

Challenges and Limitations

No optimizer has perfect information. Statistics are approximations, workloads change, and hardware behavior is complex. Benchmark environments may not reproduce production concurrency or cache state. Indexes improve reads but increase writes and storage. Hints and forced plans can prevent immediate regressions but may become harmful after data growth. Query-level tuning cannot compensate indefinitely for poor schema design, unsuitable hardware, excessive application round trips, or unrealistic service requirements.

The most difficult performance decisions are trade-offs. A reporting query may favor large scans while transactional queries favor selective indexes. A covering index may reduce reads but enlarge the write path. Denormalization may reduce joins but complicate consistency. Sound optimization makes these trade-offs explicit and measures them against stated objectives.

Chapter Summary

Query performance depends on the interaction of logical SQL, physical execution plans, data distribution, indexes, statistics, storage, memory, network behavior, and concurrency. Execution plans should be read as evidence: compare estimated and actual rows, locate expensive operators, inspect access methods, and distinguish optimizer cost from elapsed time.

Indexes should be designed around real predicates, joins, ordering, and projection, while accounting for storage and write-maintenance costs. Composite index order, sargability, covering strategies, partial indexes, and statistics all influence plan quality. Query rewrites such as half-open date ranges, EXISTS, keyset pagination, explicit projection, and elimination of accidental Cartesian products can remove avoidable work, but every rewrite must preserve semantics.

Reliable tuning is experimental. Establish a baseline, use representative data and concurrency, inspect CPU, I/O, waits, rows, and percentiles, change one factor at a time, verify results, and monitor production behavior. Governance, security, privacy, and human review remain essential when using query logs, automated advisors, or AI-generated recommendations.

Key Terms

Execution plan: A physical strategy selected by a DBMS to execute a query.

Optimizer: The DBMS component that evaluates alternative execution strategies.

Cardinality: The number of rows produced or expected from an operator.

Selectivity: The degree to which a predicate narrows a relation.

Sequential scan: Reading a table or relation broadly, often page by page.

Index scan or seek: Accessing rows through an index search structure.

Covering index: An index containing all columns needed for a query.

Composite index: An index built from two or more columns.

Sargability: The property of a predicate that permits effective index searching.

Statistics: Summaries of data distribution used for cardinality estimation.

Histogram: A statistical summary of value frequencies or ranges.

Nested-loop join: A join that probes an inner input for each outer row.

Hash join: A join using a hash table, normally for equality conditions.

Merge join: A join that combines inputs ordered by the join key.

N+1 query pattern: One parent query followed by one query per parent row.

Keyset pagination: Pagination based on the last retrieved ordering key.

Logical read: A page or block served from the database buffer or memory.

Tail latency: High-percentile response time, such as p95 or p99.

Parameter-sensitive plan: A plan whose suitability changes with parameter values.

Cardinality-estimation error: A difference between estimated and actual row counts.

Review Questions

Short Answer Questions

1. Why is an execution-plan cost not generally equivalent to elapsed time in milliseconds?
2. What is the role of statistics in cost-based optimization?
3. Why does column order matter in a composite index?
4. State one reason why NOT EXISTS may be preferable to NOT IN.
5. What is the principal advantage of keyset pagination over large-offset pagination?

Long Answer Questions

1. Explain how nested-loop, hash, and merge joins differ, and describe a workload in which each may be appropriate.
2. Discuss the benefits and costs of covering indexes, including their effects on reads, writes, and storage.
3. Describe a rigorous, evidence-based process for tuning a slow production query.
4. Explain how stale statistics, data skew, and correlated predicates can cause poor execution plans.
5. Analyze the relationship between query rewriting, sargability, correctness, and SQL three-valued logic.

Analytical / Application Questions

1. A query estimates 500 rows at a join input but actually returns 4 million. Identify possible causes, explain how this error could influence join selection, and propose a diagnostic sequence.
2. Design an optimization plan for an API that retrieves orders by status and date, returns five columns, and supports deep pagination. Specify the query changes, possible index, measurements, and correctness checks.
3. An additional index reduces read latency by 15% but increases write latency by 8% on a high-volume transaction table. Explain what workload evidence and business requirements you would use to decide whether to retain it.

Multiple Choice Questions with Answers

Question 1

Which observation most strongly indicates a cardinality-estimation problem?

A. The SQL statement contains an explicit column list.

B. Actual rows differ greatly from estimated rows at a major operator.

C. The query uses a parameterized predicate.

D. The plan contains an order-by operation.

Correct Answer: B. Actual rows differ greatly from estimated rows at a major operator.

Question 2

Why can a sequential scan be the best access method for a query?

A. It always avoids all CPU work.

B. It is required whenever a table has an index.

C. The query needs a large proportion of the table’s rows.

D. It prevents statistics from being used.

Correct Answer: C. The query needs a large proportion of the table’s rows.

Question 3

Which predicate is generally more sargable for an ordinary index on order_date?

A. WHERE YEAR(order_date) = 2025

B. WHERE CAST(order_date AS DATE) = :d

C. WHERE order_date >= :start AND order_date < :next

D. WHERE LOWER(order_date) = :value

Correct Answer: C. WHERE order_date >= :start AND order_date < :next

Question 4

What is a principal cost of adding many indexes to a table?

A. Indexes eliminate the need for transactions.

B. Indexes can increase storage and write-maintenance work.

C. Indexes always make full-table reports impossible.

D. Indexes prevent the optimizer from using statistics.

Correct Answer: B. Indexes can increase storage and write-maintenance work.

Question 5

Which join is commonly suitable for a large equality join involving unsorted inputs?

A. Hash join

B. Nested-loop join with no index

C. Cartesian join

D. String concatenation join

Correct Answer: A. Hash join

Question 6

Why can NOT IN produce unexpected results when its subquery returns NULL?

A. SQL NULL participates in three-valued logic.

B. NULL values are automatically converted to zero.

C. NOT IN always ignores indexes.

D. NULL causes every table scan to fail.

Correct Answer: A. SQL NULL participates in three-valued logic.

Question 7

What is a key property of keyset pagination?

A. It sorts and discards every preceding page.

B. It uses the last ordering key to locate the next page.

C. It requires SELECT *.

D. It removes the need for a deterministic order.

Correct Answer: B. It uses the last ordering key to locate the next page.

Question 8

Which measurement is particularly useful for understanding user-facing tail behavior?

A. The p95 response time

B. The number of columns in the table definition

C. The SQL keyword count

D. The index name length

Correct Answer: A. The p95 response time

Question 9

What does a covering index attempt to avoid?

A. All transaction logging

B. Additional lookups into the base table for required columns

C. The need for a primary key

D. All statistics collection

Correct Answer: B. Additional lookups into the base table for required columns

Question 10

Which practice best represents evidence-based query tuning?

A. Add an index to every filtered column without testing.

B. Force the lowest displayed plan cost regardless of correctness.

C. Establish a baseline, change one factor, and verify performance and results.

D. Judge performance from a single unrecorded execution.

Correct Answer: C. Establish a baseline, change one factor, and verify performance and results.