Query Operations & Evaluation of Expressions

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

Query Operations and Evaluation of Expressions

How each operator is physically implemented, and how results flow between them — materialization versus pipelining.

🌍 Where this lives: the materialization-versus-pipelining choice explains a behaviour you have certainly seen: SELECT * FROM huge_table LIMIT 10 returns instantly, while SELECT * FROM huge_table ORDER BY x LIMIT 10 takes seconds. The first pipelines — it stops after ten rows. The second must sort, and a sort is a blocking operator that cannot produce its first output until it has consumed its last input. Every "why is this query slow when I only wanted 10 rows" question comes down to which operators in the plan are blocking. Search "blocking vs streaming operators query execution".

The physical operators

A query plan is a TREE of physical operators. Each has a well-defined algorithm and cost. SCAN OPERATORS — how a table's rows are obtained Sequential (table) scan read every page in order Index scan walk the index, fetch each row Index-only scan answer entirely from the index, never touch the heap Bitmap heap scan collect page numbers from the index, sort them, read pages in physical order TID scan direct access by physical row id JOIN OPERATORS Nested loop for each outer row, scan inner Indexed nested loop for each outer row, probe an index on inner Merge join both inputs sorted, walk in step Hash join hash the smaller side, probe SORT / GROUP OPERATORS Sort in-memory quicksort, or external merge sort if it exceeds work_mem HashAggregate hash table keyed by the grouping columns GroupAggregate requires sorted input, aggregates runs OTHER Materialize buffer a subtree's output for reuse Limit stop after n rows Unique remove adjacent duplicates (needs sorted input) Append concatenate subplans (UNION ALL) THE KEY CLASSIFICATION — blocking or not: STREAMING (non-blocking): produces output as it consumes scans, nested loop, hash join PROBE phase, filter, projection, limit, append → can produce the first row almost immediately BLOCKING: must consume ALL input before producing anything sort, hash join BUILD phase, hash aggregate, materialize, EXCEPT/INTERSECT → first row waits for the last input row That single distinction determines whether LIMIT can save you work.

External sort — when data exceeds memory

A sort that does not fit in memory uses EXTERNAL MERGE SORT. PHASE 1 — RUN GENERATION read M pages at a time (M = available buffer pages) sort each chunk in memory write it out as a sorted RUN → produces ⌈ b_r / M ⌉ runs PHASE 2 — MERGE merge (M−1) runs at a time, using one buffer per input and one for output repeat until a single run remains → number of merge passes = ⌈ log_{M−1}( b_r / M ) ⌉ TOTAL COST block transfers = b_r × ( 2 ⌈log_{M−1}(b_r/M)⌉ + 1 ) The "+1" is the final write; each pass reads and writes everything, hence the 2. WORKED EXAMPLE — sorting the enrol table b_r = 2,703 pages, M = 100 buffer pages Phase 1: ⌈2703/100⌉ = 28 runs, each ~100 pages sorted cost = 2×2703 = 5,406 (read all, write all) Phase 2: merge 99 runs at a time passes = ⌈ log₉₉(2703/100) ⌉ = ⌈ log₉₉(27) ⌉ = ⌈ 0.717 ⌉ = 1 pass cost = 2×2703 = 5,406 Total ≈ 2703 × (2×1 + 1) = 8,109 block transfers With only M = 10 buffers: runs = ⌈2703/10⌉ = 271 passes = ⌈ log₉(270) ⌉ = ⌈ 2.55 ⌉ = 3 total ≈ 2703 × (2×3 + 1) = 18,921 → 2.3× more I/O from having 10 buffers instead of 100 THE PRACTICAL LESSON: sort cost is dominated by the number of MERGE PASSES, and that falls logarithmically with memory. This is exactly why increasing PostgreSQL's work_mem often transforms a slow ORDER BY or GROUP BY — it can turn a multi-pass external sort into a single in-memory sort. SET work_mem = '256MB'; -- per sort, per connection EXPLAIN ANALYZE ... ; -- watch for "Sort Method: quicksort Memory: 4096kB" -- versus "Sort Method: external merge Disk: 21MB"

operators.sql

-- All measured on PostgreSQL 18: student 100,000 rows /
-- 736 pages, enrol 500,000 rows / 2,703 pages.

-- ===== SEQ SCAN: reads exactly b_r pages =====
EXPLAIN (ANALYZE, BUFFERS)
SELECT COUNT(*) FROM student WHERE dept = 'ACtE07';
--  Seq Scan on student  (cost=0.00..1986.00 rows=25177)
--        (actual rows=25000.00)
--    Rows Removed by Filter: 75000
--    Buffers: shared hit=736          <- exactly b_r ✔

-- ===== INDEX ONLY SCAN: the heap is never touched =====
EXPLAIN (ANALYZE, BUFFERS)
SELECT COUNT(*) FROM student WHERE marks > 90;
--  Aggregate  (cost=318.04..318.05 rows=1)
--    ->  Index Only Scan using idx_student_marks on student
--          (cost=0.42..292.84 rows=10081)
--
-- Cost fell from 2010 (seq scan) to 318 — a 6x improvement —
-- because COUNT(*) needs only the indexed column. The index
-- is a COVERING index for this query, so no heap fetch is
-- required at all.

-- ===== BITMAP HEAP SCAN: random I/O turned sequential ====
EXPLAIN (ANALYZE, BUFFERS)
SELECT COUNT(*) FROM student WHERE marks = 100;
--  ->  Bitmap Heap Scan on student (cost=25.18..808.89)
--        Recheck Cond: (marks = '100'::numeric)
--        Heap Blocks: exact=735
--        ->  Bitmap Index Scan on idx_student_marks
--              (cost=0.00..24.89) Buffers: shared read=6
--
-- TWO-PHASE execution:
--   phase 1  read 6 index pages, build a bitmap of the heap
--            pages that contain matches
--   phase 2  sort the bitmap, read those heap pages ONCE
--            each, in physical order
--
-- Without the bitmap, a plain index scan would jump between
-- heap pages in index order and could read the same page
-- repeatedly. The bitmap converts random reads into a
-- sequential sweep.
-- "Recheck Cond" appears because a lossy bitmap may only
-- record the PAGE, so each row must be re-tested.

-- ===== SORT ELIMINATED by an index =====
EXPLAIN (ANALYZE, BUFFERS)
SELECT roll FROM student ORDER BY marks DESC LIMIT 10;
--  Limit  (cost=0.42..0.97 rows=10) (actual rows=10.00)
--    Buffers: shared hit=10
--    ->  Index Scan Backward using idx_student_marks
--          (cost=0.42..5556.02 rows=100000) (actual rows=10)
--
-- No Sort node at all. The index is already in marks order,
-- so scanning it BACKWARD yields descending order for free.
-- Total pages: 10.
--
-- Note the cost pair 0.42..5556.02:
--    0.42    = startup cost (reach the first row)
--    5556.02 = total cost (scan the whole index)
-- LIMIT 10 stops early, so the EFFECTIVE cost is 0.97.
-- That startup/total split is how the planner reasons about
-- LIMIT, and it only works because Index Scan is STREAMING.

The four plans compared, all on the same table: operation cost pages ──────────────────────────────────────────────── Seq Scan, 25% match 1986 736 Index Only Scan, marks>90 318 — (heap never read) Bitmap Heap Scan, 990 rows 809 741 Index Scan Backward + LIMIT 10 0.97 10 The Index Only Scan is the standout: cost 318 versus 2010 for the equivalent seq scan, purely because the query never needs a column outside the index. That is why COVERING INDEXES matter, and why PostgreSQL added INCLUDE columns: CREATE INDEX idx ON student(marks) INCLUDE (name); -- name is stored in the index leaf but not part of the -- key, so SELECT name WHERE marks=100 becomes index-only

The 0.42..5556.02 cost pair is worth understanding properly. The planner tracks two numbers for every node: startup cost (work before the first row emerges) and total cost (work to produce all rows). LIMIT can only exploit a low startup cost, which is why it helps enormously above a streaming operator and not at all above a Sort.

Materialization versus pipelining

Given the expression π_{name}( σ_{dept='ACtE07'}( Student ⋈ Enrol ) ) MATERIALIZED EVALUATION compute each operator fully, writing the result to a temporary relation, then feed it to the next. Student ⋈ Enrol → temp1 on disk (500,000 rows) σ(temp1) → temp2 on disk (125,000 rows) π(temp2) → final cost = the operators' own cost + writing temp1 and temp2 + reading them back → the intermediate I/O can DOUBLE the total cost PIPELINED EVALUATION as each output tuple is produced, pass it straight to the next operator. No temporary relation exists. join produces a tuple → σ tests it → π trims it → out cost = the operators' own cost only → no intermediate I/O at all Also: the first result row appears almost immediately, which matters for interactive queries and for LIMIT. TWO WAYS TO DRIVE A PIPELINE: DEMAND-DRIVEN (pull / iterator model) each operator has open(), next(), close() the parent calls next() on its child when it wants a row → this is what virtually every real DBMS uses; also called the VOLCANO or iterator model PRODUCER-DRIVEN (push) each operator pushes rows to its parent as it makes them → used by some modern compiled-query engines WHEN MATERIALIZATION IS UNAVOIDABLE: · a BLOCKING operator (sort, hash build, aggregate) must consume all input first · a subtree whose result is used MORE THAN ONCE — compute once, reuse · when the pipeline would need more memory than available PostgreSQL shows this explicitly as a Materialize node: -> Materialize -> Seq Scan on small_table in a nested loop, so the inner relation is scanned from memory on each of the outer rows rather than re-read from disk.

Worked example — the same query, three plans

plans.sql

-- "top 10 students by marks" — measured three ways.

-- ===== PLAN A: no index. Sort is BLOCKING. =====
-- (index dropped for this test)
DROP INDEX IF EXISTS idx_student_marks;
EXPLAIN (ANALYZE, BUFFERS)
SELECT roll FROM student ORDER BY marks DESC LIMIT 10;
--  Limit
--    ->  Sort
--          Sort Key: marks DESC
--          Sort Method: top-N heapsort  Memory: 25kB
--          ->  Seq Scan on student
--                Buffers: shared hit=736
--
-- All 736 pages read, then 100,000 rows sorted. The LIMIT
-- helps only in that PostgreSQL uses a top-N heapsort
-- (keeping just 10 rows) instead of a full sort — but it
-- still must SEE every row.

-- ===== PLAN B: with an index. Sort ELIMINATED. =====
CREATE INDEX idx_student_marks ON student(marks);
ANALYZE student;
EXPLAIN (ANALYZE, BUFFERS)
SELECT roll FROM student ORDER BY marks DESC LIMIT 10;
--  Limit  (cost=0.42..0.97 rows=10) (actual rows=10.00)
--    Buffers: shared hit=10
--    ->  Index Scan Backward using idx_student_marks
--
-- 10 pages instead of 736. No Sort node. The pipeline stops
-- after 10 rows because Index Scan is STREAMING.

-- ===== PLAN C: an aggregate. Blocking or not depends on
-- WHICH aggregate algorithm is chosen. =====
EXPLAIN (ANALYZE, BUFFERS)
SELECT dept, AVG(marks) FROM student GROUP BY dept LIMIT 1;
-- With an index on dept available:
--
--  Limit  (cost=0.29..1288.54 rows=1) (actual rows=1.00)
--    Buffers: shared hit=760
--    ->  GroupAggregate  (cost=0.29..5153.30 rows=4)
--          Group Key: dept
--          ->  Index Scan using idx_student_dept on student
--                (actual rows=25001.00)
--
-- Only 25,001 of 100,000 rows were read. GroupAggregate
-- consumes input already SORTED by the grouping key, so once
-- it has seen the last row of the first dept it can EMIT that
-- group — and LIMIT 1 then stops the scan.
--
-- Now force the hash variant:
--     SET enable_indexscan = off;
--     SET enable_bitmapscan = off;
--
--  Limit  (cost=2236.00..2236.01 rows=1)
--    Buffers: shared hit=736
--    ->  HashAggregate  (cost=2236.00..2236.05 rows=4)
--          Group Key: dept
--          ->  Seq Scan on student (actual rows=100000.00)
--
-- All 100,000 rows read. HashAggregate IS blocking: it cannot
-- know any group is complete until the input is exhausted, so
-- LIMIT 1 saves nothing.
--
-- THE REFINED RULE: LIMIT helps above a STREAMING operator.
-- Whether GROUP BY streams depends on the ALGORITHM —
-- GroupAggregate (sorted input) streams group by group;
-- HashAggregate blocks; Sort always blocks. That is why an
-- index providing grouping order can transform a
-- GROUP BY ... LIMIT query.

🌍 Go further: the iterator model above calls next() once per row, which for a million-row scan means a million virtual function calls — pure overhead. Modern engines fix this two ways: vectorized execution passes batches of ~1000 rows per call (ClickHouse, DuckDB, Snowflake), and query compilation generates machine code for the specific query so there are no operator calls at all (HyPer, and PostgreSQL's JIT for expressions). Both routinely give 10–100× speedups on analytical queries. Search "vectorized query execution vs compilation".

💡 Exam angle: name the physical operators for scans, joins and grouping, and classify them as blocking or streaming — that classification is the highest-value idea here. Know the external merge sort cost formula b_r(2⌈log_{M−1}(b_r/M)⌉ + 1) and be able to work it for given b_r and M. Explain materialization versus pipelining with the intermediate-I/O cost as the difference, and state that pipelining is demand-driven via the iterator model. Finish with why LIMIT helps above a streaming operator and not above a sort or aggregate.

Syllabus points

Query operations; expression evaluation

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.