Query Execution Engine

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Sort Operator: ORDER BY salary ASC
 
Phase 1: Materialization (during Open())
═══════════════════════════════════════════════════════════════
    Input Stream         →  Materialized Buffer
    ─────────────────────────────────────────
    {salary: 65000}      →  [65000]
    {salary: 45000}      →  [65000, 45000]
    {salary: 55000}      →  [65000, 45000, 55000]
    {salary: 75000}      →  [65000, 45000, 55000, 75000]
    ...
    (all 10,000 tuples)  →  [buffer with 10,000 tuples]
    
    Sort buffer: [45000, 55000, 65000, 75000, ...]
                  ↑ sorted order
 
Phase 2: Output (during Next() calls)
═══════════════════════════════════════════════════════════════
    Next() → 45000  (reads from materialized buffer)
    Next() → 55000  (reads from materialized buffer)
    Next() → 65000  (reads from materialized buffer)
    ...
 
Memory: O(n) where n = input tuples

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Hash Aggregate: SELECT dept, SUM(salary), COUNT(*) FROM emp GROUP BY dept
 
Phase 1: Materialization (during Open())
═══════════════════════════════════════════════════════════════
    Input                    Hash Table State
    ─────────────────────────────────────────────────────────
    {dept:A, salary:50000}   {A: {sum:50000, count:1}}
    {dept:B, salary:60000}   {A: {...}, B: {sum:60000, count:1}}
    {dept:A, salary:55000}   {A: {sum:105000, count:2}, B: {...}}
    {dept:C, salary:70000}   {A: {...}, B: {...}, C: {sum:70000, count:1}}
    {dept:B, salary:65000}   {A: {...}, B: {sum:125000, count:2}, C: {...}}
    ...
    (all employees)          Complete hash table of all groups
 
Phase 2: Output (during Next() calls)
═══════════════════════════════════════════════════════════════
    Iterate over hash table entries:
    Next() → {dept:A, sum:105000, count:2}
    Next() → {dept:B, sum:125000, count:2}
    Next() → {dept:C, sum:70000, count:1}
    ...
 
Memory: O(g) where g = number of distinct groups

1
2
3
4
5
6
7
8

WITH expensive_calc AS (
    SELECT dept_id, AVG(salary) as avg_sal
    FROM employees
    GROUP BY dept_id
)
SELECT 
    (SELECT COUNT(*) FROM expensive_calc WHERE avg_sal > 50000) as high_paying_depts,
    (SELECT COUNT(*) FROM expensive_calc WHERE avg_sal < 30000) as low_paying_depts;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Query: SELECT * FROM outer_table o, (complex_subquery) s 
       WHERE o.id = s.ref_id
 
Without Materialization:
═══════════════════════════════════════════════════════════════
    [Nested Loop Join]
        ├── [Scan: outer_table]     (1000 rows)
        └── [Complex Subquery]      ← EXECUTED 1000 TIMES! ❌
 
If subquery takes 100ms: 1000 × 100ms = 100 seconds
 
With Materialization:
═══════════════════════════════════════════════════════════════
    [Nested Loop Join]
        ├── [Scan: outer_table]     (1000 rows)
        └── [Materialize]           ← EXECUTED ONCE ✓
                └── [Complex Subquery]
 
If subquery takes 100ms + scan materialized (1ms × 1000): ~1.1 seconds

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

External Merge Sort (when data exceeds memory):
 
Phase 1: Run Generation
═══════════════════════════════════════════════════════════════
    work_mem = 64MB (can hold ~500K tuples)
    Input = 5M tuples (far exceeds memory)
    
    Fill memory buffer:
        Read 500K tuples → buffer full
        Sort in memory
        Write to temp file: run_0
    
    Fill memory buffer again:
        Read next 500K tuples → buffer full
        Sort in memory
        Write to temp file: run_1
    
    ... repeat until input exhausted ...
    
    Result: 10 sorted runs on disk (run_0 through run_9)
 
Phase 2: Merge
═══════════════════════════════════════════════════════════════
    Open all run files
    Perform k-way merge:
        - Read smallest tuple from each run's buffer
        - Output the minimum
        - Refill that run's buffer as needed
    
    If too many runs to merge at once (k too large):
        - Do multi-pass merging
        - Merge groups of runs into larger runs
        - Repeat until single sorted output
 
Cost: 2× I/O per tuple (write runs + read for merge)
      Potentially more for multi-pass merges

1
2
3
4
5
6
7
8
9
10
11

-- PostgreSQL work_mem setting
SET work_mem = '256MB';  -- Per-operation memory limit
 
-- A query with multiple blocking operators:
SELECT dept, COUNT(*), AVG(salary)
FROM employees
GROUP BY dept      -- Hash Aggregate: uses up to 256MB
ORDER BY dept;     -- Sort: uses up to 256MB
 
-- Total potential memory: 512MB (256MB × 2 blocking operators)
-- If either exceeds 256MB individually, it spills to disk

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

-- Create a materialized view for expensive aggregation
CREATE MATERIALIZED VIEW sales_summary AS
SELECT 
    region,
    product_category,
    DATE_TRUNC('month', sale_date) as month,
    SUM(amount) as total_sales,
    COUNT(*) as transaction_count,
    AVG(amount) as avg_sale
FROM sales
WHERE sale_date >= '2024-01-01'
GROUP BY region, product_category, DATE_TRUNC('month', sale_date);
 
-- Query the materialized view (very fast - reads pre-computed data)
SELECT * FROM sales_summary 
WHERE region = 'North America' AND month = '2024-06-01';
 
-- Refresh the materialized view when underlying data changes
REFRESH MATERIALIZED VIEW sales_summary;
 
-- Optionally refresh concurrently (PostgreSQL - no locks)
REFRESH MATERIALIZED VIEW CONCURRENTLY sales_summary;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

PULL-BASED (Volcano/Iterator Model):
═══════════════════════════════════════════════════════════════
 
Control Flow:     Parent calls Child.Next()
Data Flow:        Child returns tuple to Parent
 
    [Aggregate]  ←── calls Next() ───┐
         │                            │
         │                            │
    [Filter]     ←── returns tuple ──┤
         │                            │
         │                            │
    [Scan]       ←── calls Next() ───┘
 
Execution: Pull on demand, lazy evaluation
 
 
PUSH-BASED (Producer-Driven):
═══════════════════════════════════════════════════════════════
 
Control Flow:     Child calls Parent.consume(tuple)
Data Flow:        Child pushes tuple to Parent
 
    [Scan]       ─── produces, pushes ───┐
         │                                │
         ▼                                │
    [Filter]     ─── pushes if passes ───┤
         │                                │
         ▼                                │
    [Aggregate]  ←── receives tuple ─────┘
 
Execution: Push through pipeline, producer-driven

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

Query: SELECT dept, AVG(salary) 
       FROM employees 
       WHERE hire_date > '2020-01-01' 
       GROUP BY dept
       ORDER BY dept
 
Before Optimization:
═══════════════════════════════════════════════════════
    [Sort]              ← Sorts all groups
        │
    [Hash Aggregate]    ← Aggregates 10M employees
        │
    [Filter]            ← Filters by hire_date
        │
    [Scan: employees]   ← Reads all 10M rows
 
Materialization: Full 10M rows go into Hash Aggregate
 
After Optimization (Predicate Pushdown):
═══════════════════════════════════════════════════════
    [Sort]              ← Sorts all groups
        │
    [Hash Aggregate]    ← Aggregates only 1M rows ✓
        │
    [Scan + Filter]     ← Reads and filters 
        │                  (physical filtering)
    [employees]         ← 1M rows pass filter
 
Materialization: Only 1M rows go into Hash Aggregate
Savings: 90% reduction in materialization!

1
2
3
4
5
6
7
8
9
10
11
12
13

-- Without index: requires Hash Aggregate (blocks) + Sort (blocks)
SELECT dept_id, COUNT(*), SUM(salary)
FROM employees
GROUP BY dept_id
ORDER BY dept_id;
 
-- Create sorted index on grouping column
CREATE INDEX idx_emp_dept ON employees(dept_id);
 
-- With index: Stream Aggregate (pipelines) + no Sort needed!
-- Index scan produces rows in dept_id order
-- Aggregate can emit groups as they complete (streaming)
-- Output already sorted, ORDER BY is free