The Life of a Query

Jr Codex DBMS Notes

Level: Intermediate Prerequisites: Module 5, Chapter 5: The Buffer Pool Time to complete: ~20 minutes

Table of Contents

1. The Four Stages
2. Parsing and Rewriting
3. The Plan Tree
4. The Iterator Model
5. Blocking vs Streaming Operators
6. Access Paths
7. Summary & Next Steps

1. The Four Stages

Text to Rows
─────────────────────────────────────────
  SQL text
      │
  [1] PARSE       syntax ──► a tree; validate
      │           names against the catalog
      ▼
  [2] REWRITE     expand views, flatten
      │           subqueries, apply algebraic laws
      ▼
  [3] PLAN        enumerate equivalent plans,
      │           estimate each cost, pick one
      ▼
  [4] EXECUTE     run the chosen plan tree
      │
  rows
─────────────────────────────────────────

Stage 3 is the subject of Chapters 2 and 3. This chapter covers the machinery around it.

2. Parsing and Rewriting

PARSING
─────────────────────────────────────────
  - is the SQL syntactically valid?
  - do the tables and columns exist? (asks the
    CATALOG — Module 1, Chapter 3)
  - are the types compatible?
  - does the user have permission?

  Produces a query tree. Fails here are your
  ordinary syntax and typo errors.

REWRITING — before any cost is considered
─────────────────────────────────────────
  VIEW EXPANSION     a view's definition is
                     substituted inline

  SUBQUERY FLATTENING  many subqueries become
                     joins, which the planner can
                     then reorder freely

  PREDICATE PUSHDOWN  σ moves below ⋈
                     (Module 2, Chapter 3's most
                      valuable rewrite)

  CONSTANT FOLDING   WHERE x > 2 + 3 becomes
                     WHERE x > 5

  These are UNCONDITIONAL — always improvements,
  so no costing is needed.
─────────────────────────────────────────

Why Flattening Matters to You
─────────────────────────────────────────
  A subquery that gets flattened is reordered and
  optimised along with everything else.

  One that CANNOT be flattened stays a separate
  execution — often re-run per outer row (Module 3,
  Chapter 5's correlated subquery).

  This is why the same logic written two ways can
  differ by orders of magnitude, and why Chapter 4
  teaches you to check the plan rather than trust
  the SQL's appearance.
─────────────────────────────────────────

3. The Plan Tree

The output of stage 3 is a tree of physical operators.

A Plan, Drawn
─────────────────────────────────────────
  SELECT s.name, c.title
  FROM students s
  JOIN enrollments e ON s.id = e.student_id
  JOIN courses    c ON e.course_id = c.id
  WHERE s.city = 'Pune';

              ┌──────────────┐
              │  Hash Join   │   ← rows flow UP
              │  e.cid=c.id  │
              └──┬────────┬──┘
         ┌───────┘        └────────┐
  ┌──────▼──────┐          ┌───────▼──────┐
  │  Hash Join  │          │  Seq Scan    │
  │ s.id=e.sid  │          │  courses     │
  └───┬──────┬──┘          └──────────────┘
      │      │
  ┌───▼──┐ ┌─▼──────────┐
  │Index │ │  Seq Scan  │
  │Scan  │ │ enrollments│
  │students│└───────────┘
  │city='Pune'│
  └────────┘
─────────────────────────────────────────

How to Read It
─────────────────────────────────────────
  - LEAVES are access paths — how each table is
    read (Section 6)
  - INTERNAL nodes are operations — joins, sorts,
    aggregates, filters
  - The ROOT produces the final rows
  - Data flows UPWARD, from leaves to root

  Read a plan BOTTOM-UP and INSIDE-OUT. The
  deepest, most-indented node runs first.
─────────────────────────────────────────

4. The Iterator Model

How the tree actually runs — and it is not what most people assume.

The Volcano / Iterator Model
─────────────────────────────────────────
  Every operator implements the same interface:

      open()    prepare
      next()    return ONE row, or nothing
      close()   clean up

  The root is asked for a row. It asks its
  children. They ask theirs. A single row is
  PULLED up through the whole tree, then the next.
─────────────────────────────────────────

class SeqScan:
    def __init__(self, table): self.table = table
    def open(self):  self.it = iter(self.table)
    def next(self):  return next(self.it, None)
    def close(self): self.it = None
 
class Filter:
    def __init__(self, child, pred): self.child, self.pred = child, pred
    def open(self):  self.child.open()
    def next(self):
        while (row := self.child.next()) is not None:      # PULL from below
            if self.pred(row):
                return row                                  # push ONE row up
        return None
    def close(self): self.child.close()
 
class Limit:
    def __init__(self, child, n): self.child, self.n = child, n
    def open(self):  self.child.open(); self.count = 0
    def next(self):
        if self.count >= self.n:
            return None                                     # stops the WHOLE pipeline
        self.count += 1
        return self.child.next()
    def close(self): self.child.close()

Two Consequences That Matter
─────────────────────────────────────────
  MEMORY IS BOUNDED. Rows are not materialised
  between operators. A query returning a million
  rows does not build a million-row list — it
  streams them.

  LIMIT REALLY STOPS EARLY. Because rows are
  pulled, a LIMIT 10 asks for only 10 rows, and the
  scan below it never reads the rest of the table.

  This is why LIMIT is genuinely fast — but only
  when nothing below it is a blocking operator
  (Section 5).
─────────────────────────────────────────

5. Blocking vs Streaming Operators

The Distinction
─────────────────────────────────────────
  STREAMING (pipelined)
    Produces output as it consumes input.
    Scans, filters, projections, nested loop
    joins, merge joins.
    First row out ──► almost immediately.

  BLOCKING (pipeline breakers)
    Must consume ALL input before producing ANY
    output.
    SORT, HASH build side, GROUP BY (hash),
    DISTINCT, window functions.
    First row out ──► only after the whole input
    is read.
─────────────────────────────────────────

Why This Explains a Common Surprise
─────────────────────────────────────────
  SELECT * FROM huge_table LIMIT 10;
      Fast. Streaming scan, stops after 10 rows.

  SELECT * FROM huge_table ORDER BY name LIMIT 10;
      SLOW without an index on name — SORT is
      blocking, so the whole table is read and
      sorted before the first row emerges.

  WITH an index on name, the index scan returns
  rows already ordered, the sort disappears, and
  LIMIT 10 stops after 10 rows again.

  This is Module 5, Chapter 2's "ORDER BY is free
  with a B+ tree" showing up in the plan.
─────────────────────────────────────────

Memory and Spilling
─────────────────────────────────────────
  Blocking operators need memory to hold their
  input. When it exceeds the allowance
  (work_mem in PostgreSQL), they SPILL TO DISK —
  an external merge sort or a partitioned hash.

  A spill is usually a 10-100x slowdown for that
  operator, and it appears explicitly in
  EXPLAIN ANALYZE as "external merge Disk: ...".
  Chapter 4 treats it as a red flag.
─────────────────────────────────────────

6. Access Paths

The leaves of the plan — how a single table is read.

The Options
─────────────────────────────────────────
  SEQUENTIAL SCAN
    Read every page in order.
    Best when: reading a large fraction of the
    table, or the table is small.

  INDEX SCAN
    Descend the index, then fetch each matching
    row from the heap.
    Best when: few rows match (high selectivity).
    Cost: one RANDOM read per matching row.

  INDEX-ONLY SCAN
    All needed columns are in the index; the heap
    is never touched.
    Module 5, Chapter 3's covering index.

  BITMAP HEAP SCAN
    Collect matching row locations from the index
    into a bitmap, SORT them by page, then read
    each page ONCE in physical order.
    Best when: a MEDIUM number of rows match —
    too many for random reads, too few for a full
    scan. Can also combine several indexes.
─────────────────────────────────────────

The Bitmap Scan Is the Clever One
─────────────────────────────────────────
  A plain index scan visiting 50,000 rows does
  50,000 random reads, and may hit the same page
  many times.

  A bitmap scan gathers all 50,000 locations
  first, sorts them by page number, and then reads
  each page exactly once, in order — turning
  random I/O into sequential I/O.

  When you see "Bitmap Heap Scan" in a plan, the
  optimiser decided you were in that middle zone.
  It is usually right.
─────────────────────────────────────────

7. Summary & Next Steps

Key Takeaways

• A query is parsed, rewritten by unconditional algebraic improvements, planned by cost, then executed as a tree of operators read bottom-up.
• The iterator model pulls one row at a time through the tree, which bounds memory and lets LIMIT genuinely stop the scan below it early.
• Blocking operators must consume all input before emitting anything, which is why ORDER BY ... LIMIT 10 is slow without a matching index and fast with one.
• Bitmap heap scans sort matching row locations by page before reading, converting random I/O into sequential I/O for medium-selectivity queries.

Concept Check

1. Why does SELECT * FROM t LIMIT 10 return almost instantly while SELECT * FROM t ORDER BY name LIMIT 10 may not?
2. What does the iterator model's pull-based design buy in terms of memory?
3. When is a bitmap heap scan preferable to both a plain index scan and a sequential scan?

Next Chapter

→ Chapter 2: Join Algorithms

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index | Back to DBMS Index