Query Optimization and Decomposition

DSA, Database System & Operating System — Data Models, Normalization, and SQL, NEC licence examination syllabus (Nepal Engineering Council).

Query Optimization and Decomposition

Turning a declarative query into an efficient plan — parsing, rewriting, enumerating alternatives, and choosing.

🌍 Where this lives: the optimiser is the reason SQL is worth using. You write what you want and it derives how — and for a five-table join there are 120 orderings, each with several access paths and join algorithms, so thousands of candidate plans. Choosing well is why a query over a hundred million rows returns in milliseconds. It is also why SQL performance advice is often wrong: "this rewrite is faster" usually means "this rewrite happens to defeat a bad estimate on my data". The durable skill is reading EXPLAIN and finding where the estimate diverged from reality. Search "how query optimizers work join order enumeration".

The query processing pipeline

SQL text │ ▼ 1. PARSER syntax check → parse tree │ ▼ 2. SEMANTIC do the tables and columns exist? are types ANALYSIS compatible? expand *, resolve views │ ▼ 3. QUERY rewrite into relational algebra; DECOMPOSITION normalise predicates; flatten subqueries; remove redundancy │ ▼ 4. LOGICAL apply algebraic equivalences: OPTIMIZATION push selections down, push projections down, convert σ over × into joins │ ▼ 5. PHYSICAL enumerate access paths and join OPTIMIZATION algorithms; estimate cost from statistics; choose the cheapest plan │ ▼ 6. CODE produce an executable plan tree GENERATION │ ▼ 7. EXECUTION run the iterator pipeline │ ▼ result STEPS 3–4 are RULE-BASED (always-correct rewrites). STEP 5 is COST-BASED (needs statistics and may be wrong). That division matters: a rule-based rewrite can never make a query slower in principle, whereas a cost-based decision is only as good as the estimates feeding it.

Query decomposition — four sub-tasks

1. ANALYSIS — is the query even meaningful? · every relation and attribute exists · types are compatible in every comparison · the query graph is CONNECTED. A disconnected graph means a missing join predicate and therefore an accidental Cartesian product. SELECT * FROM student, course; -- disconnected! → 100,000 × 3 = 300,000 rows from a 3-row table 2. NORMALIZATION — put the WHERE clause into a canonical form conjunctive normal form (CNF): (a ∨ b) ∧ (c ∨ d) · lets the optimiser treat each ∧ term independently and push it down separately · also detects contradictions: WHERE marks > 90 AND marks < 50 → provably empty; the optimiser can return zero rows WITHOUT reading the table 3. SIMPLIFICATION — remove redundancy using idempotence rules p ∧ p ≡ p p ∧ true ≡ p p ∧ false ≡ false p ∨ ¬p ≡ true p ∧ (p ∨ q) ≡ p WHERE dept='ACtE07' AND (dept='ACtE07' OR marks>90) simplifies to WHERE dept='ACtE07' Also: apply integrity constraints. If a CHECK guarantees marks ≤ 100, then WHERE marks > 200 is provably empty. 4. RESTRUCTURING — express as an algebra tree and improve it · convert subqueries into joins (DECORRELATION) where possible · push selections and projections down · reorder joins DECORRELATION, the most valuable of these: -- correlated: the inner query runs PER OUTER ROW SELECT * FROM student s WHERE marks > (SELECT AVG(marks) FROM student s2 WHERE s2.dept = s.dept); -- decorrelated: the aggregate is computed ONCE per dept SELECT s.* FROM student s JOIN (SELECT dept, AVG(marks) a FROM student GROUP BY dept) t ON t.dept = s.dept WHERE s.marks > t.a; For 100,000 students in 4 departments, the correlated form logically requires 100,000 aggregate computations; the decorrelated form requires 4. Modern optimisers perform this rewrite automatically, but not in every case — a correlated subquery in the SELECT list or with LIMIT often defeats it.

Heuristic (rule-based) optimization

Applied in this order, because each step enables the next: STEP 1 — break up conjunctive selections σ_{c1 ∧ c2 ∧ c3}(R) → σ_{c1}(σ_{c2}(σ_{c3}(R))) so each part can move independently STEP 2 — push each selection as far down as it can go σ_c(R ⋈ S) → σ_c(R) ⋈ S if c mentions only R THE BIGGEST WIN. Reduces every intermediate result above it. STEP 3 — replace σ over × with a join σ_{r.a = s.b}(R × S) → R ⋈_{a=b} S a join algorithm can use an index; a product cannot STEP 4 — push projections down drop columns as early as possible so intermediate tuples are narrower and more fit per page STEP 5 — choose a join order evaluate the MOST RESTRICTIVE joins first, so intermediate results stay small STEP 6 — identify common subexpressions and compute them once WORKED APPLICATION — an unoptimised query: π_{name, title}( σ_{dept='ACtE07' ∧ credits=3 ∧ s.roll=e.roll ∧ e.course=c.code}( Student × Enrol × Course )) Sizes: |Student| = 100,000 |Enrol| = 500,000 |Course| = 50 NAIVE COST — form the product first: 100,000 × 500,000 × 50 = 2.5 × 10¹² intermediate rows At 185 rows per page that is ~1.35 × 10¹⁰ pages. Utterly infeasible. AFTER STEP 1 and 2 — push the single-table predicates down: σ_{dept='ACtE07'}(Student) → 25,000 rows σ_{credits=3}(Course) → ~17 rows AFTER STEP 3 — turn the remaining equalities into joins: ( σ(Student) ⋈ Enrol ) ⋈ σ(Course) AFTER STEP 5 — join the most restrictive pair first: 25,000 students ⋈ 500,000 enrolments → ~125,000 rows then ⋈ 17 courses → ~42,000 rows AFTER STEP 4 — project early, carrying only name, title and the join keys. Intermediate rows: ~125,000 instead of 2.5 × 10¹². → a factor of 20 million. That is what heuristic optimisation is worth, and why it runs before any cost-based decision.

optimization.sql

-- Verified on PostgreSQL 18. The point of these examples is
-- that you do NOT have to hand-optimise — but you must be
-- able to READ what the optimiser did.

-- ===== 1. selection pushdown, confirmed in the plan =====
EXPLAIN (COSTS OFF)
SELECT s.name, c.title
FROM   student s, enrol e, course c
WHERE  s.roll = e.roll AND e.course = c.code
  AND  s.dept = 'ACtE07';
--  Nested Loop
--    ->  Hash Join
--          Hash Cond: (e.roll = s.roll)
--          ->  Seq Scan on enrol e
--          ->  Hash
--                ->  Seq Scan on student s
--                      Filter: (dept = 'ACtE07'::bpchar)
--                              ^^^^^^^^ pushed to the SCAN ✔
--    ->  Index Scan using course_pkey on course c
--          Index Cond: (code = e.course)
--
-- The dept filter is applied while READING student, not after
-- joining. Rule 2, applied automatically.

-- ===== 2. a contradictory predicate =====
EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM student WHERE marks > 90 AND marks < 50;
--  Bitmap Heap Scan on student  (actual rows=0.00 loops=1)
--    Recheck Cond: ((marks > '90') AND (marks < '50'))
--    Buffers: shared hit=3
--    ->  Bitmap Index Scan on idx_student_marks
--          (cost=0.00..13.42 rows=500) (actual rows=0.00)
--
-- IMPORTANT: PostgreSQL does NOT prove this contradiction and
-- short-circuit it. It plans an ordinary index scan which
-- happens to return zero rows, reading 3 pages.
--
-- Note the estimate: rows=500 versus actual 0. The planner
-- multiplied two range selectivities under the independence
-- assumption; it never reasoned that the ranges are DISJOINT.
--
-- Contradiction detection IS in the textbook simplification
-- rules and some optimisers (SQL Server, Oracle) apply it.
-- PostgreSQL's normalization is deliberately limited, because
-- proving arbitrary unsatisfiability is expensive and the case
-- is rare in real queries.
--
-- The one form it DOES short-circuit is a literal false:
--     SELECT * FROM student WHERE false;
--     -> Result   One-Time Filter: false    (0 pages read)

-- ===== 3. a redundant predicate: also NOT removed =====
--   SELECT * FROM student
--   WHERE dept='ACtE07' AND (dept='ACtE07' OR marks > 90);
--
--  Bitmap Heap Scan on student
--    Recheck Cond: (((dept='ACtE07') AND (dept='ACtE07'))
--                   OR (marks > '90'))
--    Filter: (dept = 'ACtE07')
--    ->  BitmapOr
--          ->  Bitmap Index Scan on idx_student_dept
--          ->  Bitmap Index Scan on idx_student_marks
--
-- The absorption law  p ∧ (p ∨ q) ≡ p  is valid, and
-- PostgreSQL does NOT apply it. It keeps the OR, builds a
-- bitmap from BOTH indexes, then re-filters. The answer is
-- correct; the plan does strictly more work than necessary.
--
-- THE LESSON: the simplification rules describe what an
-- optimiser MAY do, not what every optimiser DOES. Verify
-- with EXPLAIN rather than assuming, and write the simple
-- predicate yourself.

-- ===== 4. decorrelation: correlated vs join =====
EXPLAIN (ANALYZE, BUFFERS)
SELECT s.roll FROM student s
WHERE  s.marks > (SELECT AVG(s2.marks) FROM student s2
                  WHERE s2.dept = s.dept);

EXPLAIN (ANALYZE, BUFFERS)
SELECT s.roll FROM student s
JOIN  (SELECT dept, AVG(marks) AS a FROM student GROUP BY dept) t
      ON t.dept = s.dept
WHERE  s.marks > t.a;
-- Compare the two plans. The second computes 4 group averages
-- once; whether the first does the same depends on the
-- optimiser's ability to decorrelate this shape. When it
-- cannot, the difference is dramatic — which is why writing
-- the join form yourself is a defensive habit for hot
-- queries.

Cost-based join ordering

The number of possible join orders explodes: n relations, considering only LEFT-DEEP trees: n! considering ALL tree shapes (bushy): (2(n−1))! / (n−1)! n=2 2 orders 2 bushy n=3 6 12 n=4 24 120 n=5 120 1,680 n=6 720 30,240 n=8 40,320 17,297,280 n=10 3,628,800 ~1.76 × 10¹² Exhaustive search is impossible beyond a handful of tables. SOLUTION 1 — DYNAMIC PROGRAMMING (System R, 1979) Build the best plan for every SUBSET of relations, smallest first, reusing the optimal sub-plans. cost: O(3ⁿ) time, O(2ⁿ) space n=10 → 59,049 steps instead of 1.76 × 10¹² — feasible Relies on the assumption that the optimal plan for a set contains optimal plans for its subsets. That is not strictly true once sort order matters, which is why System R also tracks INTERESTING ORDERS: a slightly costlier sub-plan that produces sorted output may win overall by eliminating a later sort. SOLUTION 2 — GENETIC / RANDOMISED SEARCH Beyond a threshold (PostgreSQL: geqo_threshold = 12 relations) switch to a genetic algorithm: generate random plans, keep the best, mutate and recombine. No optimality guarantee, but bounded planning time. LEFT-DEEP vs BUSHY: left-deep ((A ⋈ B) ⋈ C) ⋈ D each join's outer input is a base relation → pipelines beautifully, only n! orders bushy (A ⋈ B) ⋈ (C ⋈ D) → more parallelism, far larger search space Most optimisers restrict to left-deep for this reason. WHY THE OPTIMISER STILL GETS IT WRONG: · errors in cardinality estimates COMPOUND. Four joins each off by 3× gives 81× at the top, and the plan chosen there is effectively arbitrary. · the independence assumption for AND-ed predicates · user-defined functions have no statistics · data changing faster than ANALYZE runs

explain_reading.sql

-- THE DIAGNOSTIC PROCEDURE for a slow query. This is the
-- practical skill the whole topic exists to support.

-- STEP 1: get the plan WITH actual numbers.
EXPLAIN (ANALYZE, BUFFERS, VERBOSE)
SELECT s.dept, COUNT(*) FROM student s
JOIN   enrol e ON e.roll = s.roll
WHERE  s.marks > 90
GROUP  BY s.dept;

-- STEP 2: read it BOTTOM-UP and INSIDE-OUT. The most deeply
-- indented node runs first.

-- STEP 3: at every node compare  rows=N (estimate)
--                          with  actual rows=M
--   ratio under 10x   -> the estimate is fine
--   ratio over 10x    -> THIS is your problem; everything
--                        above it was planned on a lie

-- STEP 4: check the access methods
--   Seq Scan on a large table with a selective filter
--       -> a missing index
--   "Rows Removed by Filter" very large
--       -> the filter is not selective, or no index supports it
--   "Sort Method: external merge  Disk: 21MB"
--       -> work_mem is too small; the sort spilled
--   Nested Loop with a large outer side
--       -> usually an underestimate on the outer relation

-- STEP 5: fix the CAUSE, not the symptom
--   stale statistics   -> ANALYZE table;
--   missing index      -> CREATE INDEX ...;
--   correlated columns -> CREATE STATISTICS ...;
--   sort spilling      -> SET work_mem = '256MB';
--   bad estimate on an expression -> an expression index

-- ===== a measured before/after =====
-- BEFORE: no index on marks
--  Seq Scan on student  (cost=0.00..1986.00 rows=9971)
--    Buffers: shared hit=736
CREATE INDEX idx_student_marks ON student(marks);
ANALYZE student;
-- AFTER:
--  Index Only Scan using idx_student_marks
--        (cost=0.42..292.84 rows=10081)
--
-- cost 1986 -> 293, a 6.8x reduction, from one index and one
-- ANALYZE. Note ANALYZE is REQUIRED: without fresh
-- statistics the planner may not know the index is
-- worthwhile.

THE ESTIMATE-VERSUS-ACTUAL CHECK, with real measured values: predicate estimated actual ratio verdict ───────────────────────────────────────────────────────── dept = 'ACtE07' 25,177 25,000 1.01× healthy marks > 90 9,971 9,901 1.01× healthy marks = 100 1,130 990 1.14× healthy roll = 54321 1 1 1.00× healthy All four are within 15%, which is why the plans chosen were sensible. A ratio of 100× or 1000× at any node is the signature of a planning failure, and it is almost always one of: stale statistics, correlated predicates, or a predicate the planner cannot see through (a function call, a parameter it has not been given). WHAT TO DO WITH A PLAN YOU DISAGREE WITH — in order: 1. ANALYZE, and re-check. Most bad plans are stale stats. 2. Look for the first node where estimate and actual diverge. 3. Fix the estimate (statistics, indexes, rewriting the predicate) rather than forcing the plan. 4. Only as a last resort, force it — pg_hint_plan, enable_seqscan=off, or an optimisation barrier. Forced plans stop adapting when the data changes, which turns today's fix into next year's outage.

Point 3 is the discipline that separates competent tuning from cargo-culting. A forced plan is frozen: it was right for the data volume you had when you forced it. Fixing the estimate lets the optimiser keep choosing correctly as the table grows from ten thousand rows to ten million.

🌍 Go further: the industry standard reference here is the 2015 paper "How Good Are Query Optimizers, Really?" by Leis et al., which benchmarked real systems and found cardinality estimation errors of several orders of magnitude were routine — and that join order mattered far more than the cost model's precision. It motivated the current wave of learned cardinality estimation (neural networks trained on query feedback) and adaptive execution (re-planning mid-query when reality diverges). Search that paper's title, then "adaptive query execution Spark" for the production answer.

💡 Exam angle: draw the query processing pipeline (parse → analyse → decompose → logical optimise → physical optimise → execute) and name the four decomposition sub-tasks: analysis, normalization, simplification, restructuring. Know the heuristic optimisation order — split conjunctive selections, push selections down, convert σ over × into joins, push projections down, order joins — with selection pushdown as the biggest win, and be able to quantify it. State the join-order explosion (n! left-deep) and that System R's dynamic programming reduces it to O(3ⁿ). Finish with the estimate-versus-actual diagnostic.

Syllabus points

Query optimization
Query decomposition

Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.