Query processing turns declarative SQL into physical work. This lesson is for learners who already know joins and indexes and now need to read an execution plan without treating it as a mysterious diagram.
You will trace parsing, binding, rewriting, optimization, and execution; compare scan and join operators; diagnose row-estimation errors; and test a tuning change with evidence rather than intuition.
When a SQL query is submitted to a DBMS, it goes through several stages before results are returned:
| Stage | Input | Output | Key Activity |
|---|---|---|---|
| Parsing | SQL string | Parse tree | Syntax check, tokenization |
| Translation | Parse tree | Relational algebra expression | Semantic check, schema lookup |
| Optimization | Relational algebra expression | Execution plan | Cost estimation, plan selection |
| Evaluation | Execution plan | Query result | Physical operators, I/O |
A query tree (also called a query evaluation tree) represents a relational algebra expression. Leaf nodes are relations, while internal nodes perform operations such as selection, projection, and join.
Example: For the query SELECT name FROM students WHERE age > 20:
Heuristic Optimization transforms the query tree to improve efficiency before cost-based analysis:
| Aspect | Heuristic Optimization | Cost-Based Optimization |
|---|---|---|
| Approach | Apply rules (push selections down, etc.) | Estimate cost of multiple plans, pick cheapest |
| Statistics needed | No | Yes (table sizes, index info, cardinality) |
| Quality | Good for simple queries | Better for complex queries |
| Speed | Fast (no cost computation) | Slower (evaluates many plans) |
| Used by | Older/simpler systems | PostgreSQL, Oracle, SQL Server, MySQL |
For a query joining n tables, there are O(n!) possible join orderings. The optimizer uses dynamic programming or greedy algorithms to find a good order without evaluating all possibilities.
Key principle: Perform the join that produces the smallest intermediate result first. Use selectivity estimates (from statistics) to predict result sizes.
An execution plan specifies the exact physical operations to execute a query. You can view it using:
| Plan Component | Description |
|---|---|
| Seq Scan | Full table scan - reads every row |
| Index Scan | Uses an index to find rows |
| Index Only Scan | Satisfies query entirely from index (no table access) |
| Nested Loop Join | For each row in outer table, scan inner table. Good for small tables. |
| Hash Join | Build hash table from smaller relation, probe with larger. Good for large unsorted tables. |
| Merge Join | Both inputs sorted on join key. Very efficient for sorted data. |
| Sort | Sorts rows for ORDER BY or merge join |
| Aggregate | Computes GROUP BY, COUNT, SUM, etc. |
Parsing confirms that tokens form valid SQL, but binding gives names their meaning. The binder resolves tables, aliases, columns, functions, data types, and privileges against the catalog. An unqualified column that exists in both joined tables is ambiguous even when a human can guess the intended table. Type resolution can also insert implicit conversions that later affect index use.
Before searching physical plans, a rewrite stage applies equivalence rules. It may expand a view, simplify constants, remove an unused join when constraints prove it safe, transform a correlated subquery, or push a predicate through a view. A rewrite must preserve SQL semantics, including NULL behavior, duplicates, outer joins, and volatile functions; an apparently obvious manual rewrite can be incorrect when those details differ.
The optimizer cannot execute every candidate plan to discover its real cost, so it predicts row counts from statistics. Typical inputs include table and index size, distinct counts, null fractions, value frequencies, histograms, and physical page estimates. Cardinality estimates flow from one operator to the next and influence join order, join algorithm, memory grants, and whether an index lookup appears affordable.
Estimates fail when statistics are stale, predicates use correlated columns that are modeled as independent, parameter values are unusually common or rare, expressions hide distributions, or data changed sharply after a load. Compare estimated rows with actual rows at the first operator where they diverge. A mistake near a leaf can multiply through the rest of the plan; fixing a later symptom may leave the real cause untouched.
| Evidence | Interpretation | Investigation |
|---|---|---|
| Estimate 10, actual 500000 | Severe underestimation | Statistics, skew, correlation, parameter value |
| Estimate 500000, actual 10 | Severe overestimation | Predicate simplification and histogram coverage |
| Good leaf estimates, bad join estimate | Relationship model is weak | Join-key distribution and constraints |
| Estimates change by parameter | Value sensitivity is expected | Plan reuse and representative tests |
Join order decides which rows meet first; the join algorithm decides how they meet. A nested-loop join reads an outer input and searches the inner input for each outer row. It is effective when the outer side is small and the inner side has a cheap lookup. It becomes painful when underestimated outer rows trigger thousands of repeated scans.
A hash join builds an in-memory hash table from one input and probes it with the other. It suits large equality joins without useful ordering, but needs enough memory; overflow partitions spill to temporary storage. A merge join advances through inputs ordered on the join keys. It can stream efficiently and support some range-like conditions, but sorting unsorted inputs may dominate its cost.
Some operators can emit a row as soon as they receive one; others are blocking. A filter is commonly pipelined, while a full sort must usually consume its input before returning the first ordered row. Hash builds, distinct operations, and some aggregates also retain state. Blocking operators increase time to first row and can request substantial working memory.
When the granted memory is too small, a sort or hash operation may spill runs or partitions to temporary storage. Spills add I/O and can become worse under concurrency. When a grant is much too large, a few queries can reserve memory that other sessions need. Diagnose both the operator and the incorrect row or row-width estimate that caused the grant, rather than merely increasing a global memory setting.
Preparing or caching plans avoids repeated optimization, but one reusable plan may not fit every parameter. A plan compiled for a rare customer might use an index and nested loop; the same plan can be poor for a customer owning half the table. Products use different plan-cache and parameter-sensitive strategies, so inspect the database-specific behavior before forcing recompilation or disabling reuse.
First confirm that parameter sensitivity, rather than stale statistics or an application regression, explains the variance. Capture the parameter set, plan identifier, compile time, execution counts, and row estimates. Then choose the narrowest remedy: improve statistics or indexing, rewrite the query to expose stable selectivity, separate genuinely different workloads, or use a supported plan-control option with monitoring.
Read the plan in the engine's data-flow direction, which is not always the visual top-to-bottom order. Confirm the statement and parameters, find the expensive or long-running branch, and compare estimated with actual rows. Follow the first major divergence toward its inputs. Check filters, access predicates, repeated loops, memory spills, and rows discarded after expensive work.
EXPLAIN without execution is safer for a modifying query but shows estimates only. An analyze option actually runs the statement in many products, so never assume it is harmless for INSERT, UPDATE, or DELETE. Use a transaction and rollback only when the engine guarantees the relevant effects are transactional, or test against a controlled copy. Record a baseline before changing SQL, indexes, or configuration, then compare one change at a time.
EXPLAIN ANALYZE
SELECT c.customer_id, COUNT(*) AS order_count
FROM customers AS c
JOIN orders AS o
ON o.customer_id = c.customer_id
WHERE o.status = 'pending'
GROUP BY c.customer_id;
-- Use the equivalent plan command for your DBMS.
-- ANALYZE executes the query, so use it only when safe.SELECT order_id, customer_id, ordered_at
FROM orders
WHERE customer_id = 42
AND ordered_at >= '2026-07-01'
AND ordered_at < '2026-08-01';
-- The half-open range remains correct for timestamps and
-- exposes bounds that a composite index can use.The optimizer considers join orders, access paths, filters, indexes, statistics, and intermediate result sizes. Two queries that return the same rows may expose different opportunities for predicate pushdown or use functions that prevent index access.
The optimizer chooses algorithms based on estimated row counts. If it expects ten rows but receives a million, it may choose nested-loop joins, insufficient memory, or a poor join order.
Rewrite only when the plan or clarity improves. Modern optimizers can transform many subqueries automatically, and EXISTS is often clearer for testing whether related rows exist.
Explore 500+ free tutorials across 20+ languages and frameworks.