Query processing and optimisation

In short

Query processing is the sequence of steps a DBMS follows to turn a declarative SQL statement into an executable plan and run it; query optimisation is the step that chooses, among many equivalent plans, the one with the least estimated cost. Because SQL says *what* is wanted and not *how*, the same query can differ in run time by factors of thousands depending on join order, join algorithm and access path. It is examined in every university DBMS paper (cost formulas for joins, equivalence rules, external sorting) and in GATE CS/DA through relational algebra equivalence and cost estimation. On the job it is the core skill behind reading EXPLAIN plans at Flipkart, Zoho, Infosys, TCS, Wipro, Freshworks, NPCI/UPI and UIDAI-scale systems, where a missing index or a bad join order shows up directly as breached SLAs.

Explained

The three stages of query processing

1. Parsing and translation — the parser checks syntax, the semantic analyser validates table and column names, types and privileges against the system catalog (data dictionary), expands views and synonyms, and produces an internal tree.
2. Optimisation — the tree is converted to relational algebra, rewritten using equivalence rules, annotated with algorithms and access paths to form candidate query evaluation plans (QEPs), each costed; the cheapest is selected.
3. Evaluation (execution) — the execution engine runs the chosen plan through the operator tree and returns the result.
4. An annotated expression tree = relational algebra operator + chosen algorithm + chosen access path; this is what EXPLAIN prints.
5. Canonical (initial) form: the naive translation — Cartesian products of all FROM tables, then one big selection from WHERE, then projection. Always correct, almost always disastrous; optimisation's job is to transform it.
6. Query graph: nodes are relations, edges are join predicates; used to reason about join order and to spot Cartesian products.

Relational algebra equivalences and heuristic optimisation

Equivalence rules (both sides give the same multiset for every instance):

• Cascade of selection: σ_{θ1∧θ2}(E) ≡ σ_{θ1}(σ_{θ2}(E)); commutativity: σ_{θ1}(σ_{θ2}(E)) ≡ σ_{θ2}(σ_{θ1}(E)).
• Cascade of projection: Π_{L1}(Π_{L2}(…Π_{Ln}(E))) ≡ Π_{L1}(E) when L1 ⊆ L2 ⊆ … .
• Selection into join: σ_θ(E1 × E2) ≡ E1 ⋈_θ E2; σ_{θ1}(E1 ⋈_{θ2} E2) ≡ σ_{θ1}(E1) ⋈_{θ2} E2 if θ1 uses only E1's attributes.
• Join commutativity and associativity: E1 ⋈ E2 ≡ E2 ⋈ E1; (E1 ⋈ E2) ⋈ E3 ≡ E1 ⋈ (E2 ⋈ E3). Outer joins are not freely associative or commutative.
• Projection distributes over join if the projection list keeps the join attributes.
• Selection distributes over ∪, ∩, −; projection distributes over ∪ only.
• Aggregation: σ before γ (group-by) is valid only on grouping attributes; a predicate on the aggregate belongs in HAVING.
• Heuristic (rule-based) optimisation applies these in a fixed order without costing: push selections down as far as possible, replace σ-over-× with joins, apply the most restrictive selection first, push projections down to shrink tuple width, combine cascades, and evaluate the most selective join first. Output: a single "good" plan, cheap to produce, no guarantee of optimality.
• Query rewriting also handles: subquery flattening/decorrelation (correlated subquery → semi-join or join), predicate transitivity (A=B and B=5 ⇒ A=5), constant folding, view merging, OR-expansion, elimination of redundant DISTINCT, and materialised-view rewriting.

Cost model and statistics

• Cost is dominated by disk I/O, so the standard metric is number of block transfers + number of seeks; CPU time and, in distributed systems, network cost are added. Measuring in blocks (not tuples) is the examinable convention.
• Catalog statistics kept per relation: n_r (tuples), b_r (blocks), l_r (tuple size, bytes), f_r (blocking factor = tuples per block), V(A, r) (distinct values of attribute A), plus index height, number of leaf blocks and clustering factor.
• Histograms capture skew: equi-width (equal value ranges) and equi-depth / height-balanced (equal tuple counts per bucket, better for skew), often with a most-common-values (MCV) list. Oracle gathers these via DBMS_STATS, PostgreSQL via ANALYZE/autovacuum, MySQL via ANALYZE TABLE.
• Selectivity of a predicate = fraction of tuples it passes. Default assumptions when statistics are absent: uniform distribution, attribute-value independence and containment of value sets — all three are the usual cause of bad estimates.
• Buffer size M (blocks of memory available to the operator) enters almost every cost formula; results are reported as block transfers assuming a cold buffer unless stated.
• Errors in cardinality estimation compound multiplicatively up a deep join tree, which is why a plan that looks cheap can run for hours.

Implementing selection, projection, sorting and aggregation

Selection access paths (the classic A1–A7 list):

• A1 linear (full table) scan: b_r transfers; works for any predicate; on a key, stops early (≈ b_r/2 on average).
• A2 binary search on a sorted file for an equality predicate: ⌈log₂ b_r⌉ + matching blocks.
• A3 primary B⁺-tree index, equality on key: h + 1 transfers (h = tree height).
• A4 primary index, equality on non-key: h + number of blocks holding matches (records are contiguous).
• A5 secondary index, equality on non-key: h + number of matching records — one random I/O per record, so it degrades fast as the match count grows.
• A6/A7 comparison (range) using primary / secondary index: scan leaves from the first qualifying key; A7 again costs one I/O per record.
• Conjunctive selection: use the single most selective index, or use composite index if it matches the predicates, or intersect record pointers from several indexes (bitmap/index AND). Disjunctive selection needs a union of pointers and falls back to a full scan if any disjunct is unindexed. Negation usually forces a scan.
• Projection is cheap unless DISTINCT is needed, then duplicate elimination costs a sort or a hash pass.
• External merge sort (data larger than memory): pass 0 creates ⌈b_r/M⌉ sorted runs; each later pass merges M−1 runs. Used for ORDER BY, GROUP BY, DISTINCT, sort-merge join and B⁺-tree bulk loading.
• Aggregation / grouping: by sorting (gives ordered output) or by hash aggregation (faster, unordered). Partial aggregation of SUM/COUNT/MIN/MAX is possible during the merge; AVG is computed from SUM and COUNT, DISTINCT aggregates need extra deduplication.

Join algorithms and their costs

• (Tuple) nested-loop join: for each tuple of outer r, scan s. Cost b_r + n_r·b_s transfers; works for any join condition; the worst practical choice.
• Block nested-loop join: for each *block* of r, scan s. Cost b_r + b_r·b_s; with M buffers (M−2 for the outer): b_r + ⌈b_r/(M−2)⌉·b_s. Put the smaller relation outside. If the inner fits in memory, cost collapses to b_r + b_s.
• Index nested-loop join: requires an index on the inner join attribute; cost b_r + n_r·c, where c is the cost of one index probe (≈ h + 1). Ideal when the outer side is already small and selective — the plan behind most OLTP queries.
• Sort-merge join: sort both inputs on the join attribute, then merge; cost = sort(r) + sort(s) + b_r + b_s. Only for equi-joins / natural joins; free if an input is already sorted (clustered index or an earlier ORDER BY), and it delivers sorted output — an interesting order the optimiser will reuse.
• Hash join: partition both inputs with the same hash function on the join attribute, then join partition-wise with an in-memory hash table of the build (smaller) side. Cost 3(b_r + b_s) when no recursive partitioning is needed, which requires roughly M > √b_build. Equi-join only; hybrid hash join keeps partition 0 in memory and saves further I/O. MySQL added hash join in 8.0.18 for equi-joins without usable indexes.
• Skew and overflow: duplicate-heavy join keys overflow a hash partition; handled by overflow resolution or by falling back to block nested-loop for that partition.
• Complex and outer joins: conjunctive conditions join on one condition and filter the rest; disjunctive conditions become a union of joins. Outer joins extend merge/hash joins by emitting unmatched tuples with nulls. Semi-join / anti-join implement EXISTS / NOT EXISTS without materialising duplicates, and semi-join reduction cuts network traffic in distributed queries.

Cost-based plan enumeration (System R and after)

• The optimiser must choose, together: join order, join algorithm per join, access path per table, and whether to sort.
• Search space: for n relations there are n! left-deep orders and (2(n−1))!/(n−1)! orders over all tree shapes — 4 relations give 24 left-deep orders and 120 orders across all shapes; 10 relations give 3.6 million left-deep orders. Exhaustive enumeration is infeasible.
• System R / Selinger dynamic programming: compute the best plan for every subset of relations bottom-up, keeping only the cheapest plan per subset plus the cheapest plan per *interesting sort order*; time O(3ⁿ), space O(2ⁿ).
• Most classical optimisers restrict the space to left-deep trees (the inner of every join is a base relation): it allows index nested-loop pipelines and reduces the space to n!·(algorithms). Modern engines also consider bushy trees for star schemas and parallel execution.
• Beyond ~10–12 joins, engines switch to heuristic search: PostgreSQL uses GEQO, a genetic algorithm, above geqo_threshold (12 by default); Oracle caps permutations and uses adaptive plans.
• Adaptive and feedback techniques: Oracle's adaptive join selection and statistics feedback, SQL Server's interleaved execution, PostgreSQL's re-planning of generic vs custom plans for prepared statements.
• Hints override the optimiser when estimates are hopeless: /*+ INDEX(e emp_dept_ix) */, /*+ LEADING(a b) */, /*+ USE_HASH(b) */ in Oracle; FORCE INDEX, STRAIGHT_JOIN in MySQL; PostgreSQL has no native hints (use pg_hint_plan or enable_* switches).
• Plan caching / shared SQL area: parsing and optimisation are themselves expensive, so plans are cached by SQL text or by prepared statement; using bind parameters instead of literals is both a performance and an SQL-injection safeguard.

Evaluation: materialisation, pipelining and reading plans

• Materialised evaluation: evaluate one operator at a time, write each intermediate result to disk, read it back. Simple, costs extra I/O ≈ ⌈n/f⌉ blocks written and read per intermediate.
• Pipelined evaluation: tuples flow from an operator to its parent as they are produced; no intermediate writes, first row arrives sooner. Demand-driven (lazy, iterator) pipelines implement open() / next() / close() per operator — the standard Volcano iterator model; producer-driven (eager) pipelines push tuples.
• Pipeline breakers cannot pipeline their input: sorting, hash-join build side, grouping without pre-sorted input, DISTINCT, and set difference.
• Reading a plan: look for the estimated vs actual rows gap (a mis-estimate at the bottom poisons everything above), full scans on large tables, nested loops with a large outer, sorts spilling to disk (external merge Disk: in PostgreSQL, TempWrite elsewhere), and the loop count on the inner side.
• Fixes in order of leverage: add or correct an index (including covering/index-only indexes), refresh statistics, rewrite the predicate to be SARGable (WHERE joining_date >= '2026-01-01' AND joining_date < '2027-01-01' instead of WHERE YEAR(joining_date)=2026), reduce returned columns, then consider hints or materialised views.

Key points

• Query processing - parsing and translation, optimisation, evaluation; the catalog supplies all metadata and statistics.
• Canonical form - Cartesian products then one selection; the optimiser's starting point, never its answer.
• Equivalence rules - selection cascade and commutativity, projection cascade, join commutativity and associativity, σ over × becoming a join.
• Heuristic optimisation - push selections and projections down, most restrictive operation first; fast, not provably optimal.
• Cost metric - block transfers plus seeks; CPU and network added where relevant.
• Statistics - n_r, b_r, f_r, l_r, V(A,r), index height; equi-depth histograms and MCV lists capture skew.
• Selectivity assumptions - uniformity, independence and containment; all three are why estimates go wrong.
• b_r = ⌈n_r / f_r⌉ - the bridge between tuple counts and I/O cost.
• Access paths - full scan, binary search, primary index equality/range, secondary index equality/range; secondary index costs one random I/O per matching record.
• Crossover point - above roughly 5–10% selectivity a full scan beats an unclustered index scan.
• External merge sort - ⌈b_r/M⌉ initial runs, (M−1)-way merges; cost 2·b_r per pass.
• Block nested-loop join - b_r + ⌈b_r/(M−2)⌉·b_s; always make the smaller relation the outer one.
• Index nested-loop join - b_r + n_r·(h+1); the OLTP workhorse, needs a small selective outer.
• Sort-merge join - equi-joins only, produces sorted output, free if an input is already ordered.
• Hash join - 3(b_r + b_s) for equi-joins, needs M > √b_build; best for large unindexed joins.
• Join size estimate - n_r·n_s / max(V(A,r), V(A,s)) on a common attribute; ≤ n_r if the attribute is a key of s.
• Left-deep trees - n! orders, enable pipelining with index nested loops; System R dynamic programming is O(3ⁿ).
• Pipelining vs materialisation - pipelining avoids intermediate writes; sort, hash build, DISTINCT and grouping are pipeline breakers.

Formulas and examples

Example 1 — selectivity and result size. employee: n = 50,000; V(dept) = 25; salary from ₹10,000 to ₹2,00,000 per month.

• dept = 'Sales' → 50,000 / 25 = 2,000 tuples, s₁ = 0.04.
• salary > 1,00,000 → 50,000 × (2,00,000 − 1,00,000)/(2,00,000 − 10,000) = 50,000 × 100000/190000 = 26,316 tuples, s₂ = 0.5263.
• Both (AND) → 50,000 × 0.04 × 0.5263 = 1,053 tuples.
• Either (OR) → 50,000 × [1 − (0.96 × 0.4737)] = 50,000 × 0.5453 = 27,263 tuples.

Example 2 — index scan versus full scan (the crossover). Table: n = 100,000 tuples, f = 20 → b = 5,000 blocks. Predicate on a non-key with V = 200 → 500 matching tuples. Unclustered secondary B⁺-tree of height 3.

• Index path: 3 (descend) + 500 (one random I/O per record) = 503 random I/Os. At 5 ms per random I/O → 2,515 ms.
• Full scan: 5,000 sequential block reads. At 0.1 ms per block (read-ahead) → 500 ms.
• The optimiser correctly picks the full scan: selectivity is 0.5% of tuples but the index is unclustered, so 503 seeks cost more than 5,000 streamed blocks. A covering (index-only) scan would avoid the 500 table visits and win again.

Example 3 — join algorithms compared. r = student: n_r = 5,000, b_r = 100 blocks; s = takes: n_s = 10,000, b_s = 400 blocks; M = 12 buffer blocks; B⁺-tree on takes(ID) of height 4.

• Sort r: ⌈100/12⌉ = 9 runs, ⌈log₁₁ 9⌉ = 1 merge pass → 2 passes → 2 × 100 × 2 = 400. Sort s: ⌈400/12⌉ = 34 runs, ⌈log₁₁ 34⌉ = 2 merge passes → 3 passes → 2 × 400 × 3 = 2,400.
• Hash join wins here. Index nested-loop with the full r is 100 + 5,000 × 5 = 25,100 — bad, because the outer is large.

Example 4 — pushing a selection, and why it flips the plan. Add WHERE student.dept = 'CSE', V(dept, student) = 20, f_student = 50 tuples/block. ID is a key of student, V(ID, takes) = 5,000.

• Unpushed: join first → size = 5,000 × 10,000 / max(5,000, 5,000) = 10,000 tuples, then filter → cost ≈ 4,100 transfers (block nested-loop above).
• Pushed: σ gives 5,000/20 = 250 students ≈ 5 blocks; join size = 250 × 10,000 / 5,000 = 500 tuples.
  • Block nested-loop: 5 + ⌈5/10⌉ × 400 = 405 transfers (10× cheaper).
  • Index nested-loop: 5 + 250 × 5 = 1,255 once the 250 selected students sit on 5 blocks (reaching them by scanning the whole 100-block table would cost 100 + 1,250 = 1,350); the index path on the small outer is the plan of choice when takes is far larger.

Example 5 — reading an EXPLAIN plan.

EXPLAIN (ANALYZE, BUFFERS)
SELECT e.emp_id, e.name, SUM(p.amount)
FROM   employee e JOIN payroll p ON p.emp_id = e.emp_id
WHERE  e.dept = 'Sales' AND p.pay_month >= '2026-04-01'
GROUP BY e.emp_id, e.name;

HashAggregate  (rows=1021) (actual rows=1018 loops=1)
  -> Hash Join  (cost=..  rows=1053) (actual rows=12204 loops=1)
       Hash Cond: (p.emp_id = e.emp_id)
       -> Seq Scan on payroll p  (rows=26316) (actual rows=61020)
            Filter: (pay_month >= '2026-04-01')
       -> Hash  (rows=2000) (actual rows=2000)
            -> Index Scan using emp_dept_ix on employee e (rows=2000)

• Estimated 1,053 join rows, actual 12,204 — an 11.6× under-estimate at the join, rooted in a 2.3× miss on payroll (61,020 against 26,316), because pay_month is skewed towards recent months and the uniformity assumption fails.
• Fix: ANALYZE payroll; with a higher default_statistics_target so the histogram resolves recent months, and an index on payroll(pay_month, emp_id) to turn the Seq Scan into an index-only scan. If the estimate stays wrong, the hash build side is the thing to control, not the join method.

Where it is used

• Banking and payments: core banking and UPI switch queries at NPCI-scale volumes, where statement and settlement queries are tuned plan-by-plan on Oracle Exadata and PostgreSQL; a single bad plan on a hot table breaks the transaction-per-second SLA.
• Government and public systems: IRCTC booking and availability, UIDAI/Aadhaar authentication lookups, GSTN return filing, state land-record and PDS portals — all dominated by selective index access paths and plan stability under load.
• E-commerce and product companies: Flipkart, Zomato, Swiggy, Zoho, Freshworks, Razorpay — order, catalogue and dashboard queries where hash joins and partition pruning on MySQL/PostgreSQL decide page latency.
• Job roles: database administrator, performance engineer, data engineer, backend developer; Oracle DBA interviews at TCS, Infosys, Cognizant, Wipro and LTIMindtree routinely ask for a plan to be read aloud and improved.
• Analytics and warehousing: star-schema joins in Snowflake, BigQuery, Redshift, Apache Hive and Spark SQL (Catalyst optimiser) use the same cost-based join reordering, with bushy trees and broadcast (hash) joins for small dimensions.
• Teaching and research: PostgreSQL's planner source and EXPLAIN ANALYZE are the standard lab tool in Indian university DBMS courses for demonstrating these cost formulas on real data.

Interview questions

• Q: What are the stages of query processing? A: Parsing and translation into relational algebra with semantic checking against the catalog, optimisation to pick the cheapest evaluation plan, and execution of that plan by the evaluation engine.
• Q: Why push selections down a query tree? A: It shrinks the inputs to every operator above, so intermediate results and the I/O to produce them fall sharply; the result is unchanged because σ distributes over join when the predicate uses only one side's attributes.
• Q: Difference between heuristic and cost-based optimisation? A: Heuristic optimisation applies fixed rewrite rules (push selections, most restrictive first) without costing anything; cost-based optimisation enumerates plans, estimates each one's cost from statistics, and picks the minimum.
• Q: When would the optimiser ignore an available index? A: When the predicate is unselective (above roughly 5–10% of rows) and the index is unclustered, when the predicate is not SARGable because a function wraps the column, when statistics are stale, or when the table is small enough to scan in a few blocks.
• Q: Why is hash join usually faster than sort-merge join? A: Hash join costs about 3(b_r + b_s) and never sorts, while sort-merge pays two external sorts; but hash join works only for equi-joins and sort-merge wins when an input is already sorted or sorted output is needed downstream.
• Q: Which relation should be the outer one in a nested-loop join? A: The smaller one, because the cost ⌈b_r/(M−2)⌉·b_s grows with the number of outer passes; in index nested-loop the outer should also be the more selective side.
• Q: What is a left-deep plan and why do optimisers prefer it? A: A join tree where every join's inner input is a base relation; it keeps the search space at n!, allows index nested-loop joins and lets results pipeline without materialising intermediates.
• Q: How is the size of a join estimated? A: For a common attribute A, n_r·n_s / max(V(A,r), V(A,s)); if A is a key of s and a foreign key in r, the result is at most n_r.
• Q: What is a pipeline breaker? A: An operator that must consume its entire input before producing output — sort, hash-join build, grouping, DISTINCT, set difference — so it forces materialisation and delays the first row.
• Q: Cardinality estimates are far off; what do you do? A: Refresh statistics with better histogram resolution, add extended/multi-column statistics for correlated predicates, rewrite the predicate to be estimable, and only then consider hints or plan pinning.
• Q: Why prefer bind parameters over literal SQL? A: The plan is cached and reused instead of being re-parsed and re-optimised per statement, and it prevents SQL injection; the trade-off is that one generic plan may not suit every parameter value under skew.
• Q: How does external merge sort work and what does it cost? A: It writes ⌈b_r/M⌉ sorted runs, then merges M−1 runs per pass; total passes = 1 + ⌈log_{M−1}(⌈b_r/M⌉)⌉ and block transfers = 2·b_r per pass.

Common mistakes

• Using tuple counts instead of blocks in cost formulas, or forgetting that the nested-loop inner relation is scanned once per outer block, not per outer tuple.
• Writing block nested-loop cost as b_r + b_r·b_s when a buffer of M blocks is given — the correct form is b_r + ⌈b_r/(M−2)⌉·b_s.
• Taking the number of merge passes as ⌈log_{M−1}(b_r)⌉ and omitting the initial run-generation pass, or forgetting that each pass costs 2·b_r (read plus write).
• Applying hash join or sort-merge join to a non-equi-join (<, ≠, or a range condition) — only nested-loop variants handle those.
• Assuming an index always helps: an unclustered index on an unselective predicate is slower than a full scan, and a function on the indexed column (UPPER(name), YEAR(dt)) disables it entirely unless a functional index exists.
• Multiplying selectivities for correlated predicates (city = 'Mumbai' AND state = 'Maharashtra') and under-estimating the result by an order of magnitude.
• Treating outer joins as commutative or associative while reordering, which silently changes the result, and pushing a selection past an outer join's null-extended side.

Related topics

SQL queries and joins · Transactions, ACID and indexing · Advanced SQL: subqueries, CTEs and window functions · ER model and normalisation · Database design case studies · NoSQL databases