Materialization — Query Execution Engine | OneNoughtOne

0/131

Database Management SystemsQuery Execution Engine

Query Execution Engine

LevelIntermediate

Duration90 mins

TopicQuery Execution Engine

4 / 5

Materialization

When Pipelining Isn't Enough

Pipelining is elegant and efficient, but it has fundamental limitations. Some operations simply cannot produce output until they've seen all their input. A sort cannot tell you the smallest element without examining every element. An aggregation cannot compute the average without summing all values. In these cases, databases must materialize —explicitly store intermediate results before proceeding. Materialization is the counterpart to pipelining, representing a deliberate trade-off of memory and I/O for correctness or necessity. Understanding when materialization occurs, why it's sometimes preferable, and how to minimize its costs is essential for mastering query execution.

What You Will Learn

By the end of this page, you will understand the concept of materialization and when it's required, explore the trade-offs between materialization and pipelining, examine different materialization strategies and their use cases, and learn techniques for minimizing materialization overhead in query execution.

Understanding Materialization

Materialization in query execution refers to the explicit storage of intermediate query results, either in memory or on disk, before passing them to the next operator. Unlike pipelining, where tuples flow through immediately, materialization captures and holds results. Formal Definition: An operator materializes its output when it stores the complete (or partial) result set before returning any tuples to its parent. The consumers then read from this materialized storage rather than directly from the producing operator. Why Materialization Exists:

Reasons for Materialization

•Algorithmic Necessity — Some algorithms require complete input before producing output (sorting, hashing)
•Multiple Consumers — When an intermediate result is used by multiple operators, materializing avoids recomputation
•Rescan Requirements — Some operations (nested loop join inner) need to scan the same data multiple times
•Memory Management — Controlled spilling to disk when memory limits are exceeded
•Explicit Caching — Deliberate storage of frequently accessed intermediate results
•Transaction Isolation — Materializing ensures a consistent view across query execution

Pipelining

•Tuple flows immediately to parent
•No intermediate storage
•O(1) memory per tuple
•Single-pass processing
•Cannot rescan source

Materialization

•Tuples stored before forwarding
•Explicit intermediate storage
•O(n) memory for n tuples
•Multi-pass processing possible
•Can rescan stored results

Materialization Spectrum

Materialization isn't binary—it exists on a spectrum. Full materialization stores everything to disk. Partial materialization buffers some tuples in memory. Even pipelined operators maintain minimal state (current tuple). Understanding where your query falls on this spectrum is key to performance analysis.

Required Materialization: Blocking Operators

Some operators fundamentally require materialization because their algorithms cannot produce output until they've consumed all input. These are the blocking operators we introduced earlier, now examined from the materialization perspective. Sort Operator: Sorting is the canonical example of required materialization. To produce tuples in sorted order, the sort operator must see all input tuples to determine the global ordering.

Sort Materialization

Execution Trace

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

Hash Aggregate Operator: Aggregation with grouping requires building a complete hash table of all groups and their accumulated values:

Hash Aggregate Materialization

Execution Trace

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

Operators Requiring Materialization
Operator	What Gets Materialized	Why It's Required
Sort	All input tuples	Must see all to determine order
Hash Aggregate	Group states (keys + accumulators)	Must accumulate all group values
Hash Join (Build)	Complete hash table of build relation	Must have complete hash table for probing
Hash Distinct	Set of all distinct values	Must see all to know what's duplicate
Window Functions (some)	Entire partition or frame	Frame may depend on future rows
Set Operations (Except/Intersect)	Complete set for comparison	Must see all to compute set difference/intersection

Memory Implications

Required materialization can consume enormous memory for large inputs. A sort of 10 million rows might need several gigabytes. When memory limits are exceeded, operators must spill to disk—dramatically increasing execution time due to I/O.

Elective Materialization: Strategic Buffering

Not all materialization is algorithmically required. Sometimes, the query optimizer or executor chooses to materialize intermediate results for strategic reasons, even when pipelining would be correct. This elective materialization can improve overall performance. Common Reasons for Elective Materialization:

Strategic Materialization Scenarios

•Multiple Consumers — When an intermediate result feeds multiple parent operators, materializing once beats recomputing multiple times
•Expensive Subexpressions — If computing a value is costly, materializing it avoids repeated computation
•Rescan Prevention — For nested loop joins, materializing the inner input avoids costly repeated base table scans
•Snapshot Isolation — Materializing ensures consistent reads across long-running queries
•Memory Trade-off — Sometimes a small materialization enables more efficient downstream processing

Example: Multiple Consumers Consider a query with a CTE (Common Table Expression) referenced twice:

CTE Materialization Example
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;

Example: Nested Loop Materialization For nested loop joins where the inner relation is expensive to compute:

Inner Materialization

Plan Comparison

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

Optimizer Heuristics

Query optimizers use cost models to decide when elective materialization pays off. They compare the cost of recomputation versus the cost of materialization + rescanning. PostgreSQL's planner, for example, explicitly considers Materialize nodes when inner relations would otherwise be expensive to rescan.

Materialization Strategies

Not all materialization is equal. Databases employ various strategies depending on the size of intermediate results, memory constraints, and access patterns. Memory-Based Materialization: The fastest option when results fit in memory. Tuples are stored in memory buffers and can be accessed with minimal overhead.

Materialization Strategies
Strategy	Storage	Speed	When Used
In-Memory Buffer	RAM only	Fastest	Small results within work_mem
Memory + Disk Spill	RAM + temp files	Moderate	Results exceed memory limits
Full Disk-Based	Temp tablespace	Slowest	Very large intermediate results
Hash Table	RAM (spills if needed)	Fast lookups	Hash joins, hash aggregates
Tuple Store	Efficient tuple packing	Compact	Materialize nodes, CTE storage

Spilling to Disk: When in-memory buffers are exhausted, operators must spill data to disk. This process significantly impacts performance:

Sort Spilling Process

Process Flow

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

I/O Amplification

Disk-based materialization causes significant I/O amplification. Data is written to disk, then read back—often multiple times for merge passes. A query that could pipeline in 1 second might take 100+ seconds when forced to materialize to disk. Monitoring for disk spills is essential for performance tuning.

Memory Management for Materialization

Effective memory management is critical for materialization performance. Databases use sophisticated techniques to balance memory across operators and minimize disk spillage. Per-Operator Memory Limits: Most databases assign memory budgets to blocking operators. PostgreSQL uses work_mem, which sets the per-operator memory limit:

Memory Budget Example
Configuration
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

Adaptive Memory Allocation: Modern databases increasingly use adaptive strategies that allocate memory dynamically based on actual needs:

Adaptive Memory Strategies

•Memory Pools — Shared memory pools that operators draw from as needed; unused memory stays available
•Dynamic Work Memory — Adjust operator memory based on actual cardinality versus estimates
•Memory Pressure Monitoring — Release memory from completed operators for reuse by active ones
•Cooperative Spilling — Multiple operators coordinate to minimize total disk I/O
•Query-Level Budgets — Global memory limits across all operators in a query

Memory Parameters Across Database Systems
Database	Parameter	Description
PostgreSQL	work_mem	Per-operation memory for sorts and hashes
PostgreSQL	hash_mem_multiplier	Multiplier for hash operations (PG 13+)
MySQL	sort_buffer_size	Memory for sort operations
MySQL	join_buffer_size	Memory for join operations
Oracle	PGA_AGGREGATE_TARGET	Total working memory across all sessions
SQL Server	max server memory	Total buffer pool (includes workspace)

Tuning Memory Parameters

When optimizing for large analytical queries, increasing work_mem (or equivalent) can dramatically improve performance by avoiding disk spills. However, be cautious in high-concurrency OLTP scenarios—if many sessions run large queries simultaneously, they might exhaust server memory.

Materialized Views: Persistent Materialization

Materialized views extend the concept of materialization beyond single query execution. They persistently store the results of a query, enabling fast access to expensive computations. Materialized View Concept: Unlike regular views (which are just stored queries), materialized views store the actual result data. This trades storage space for query performance.

Materialized View Example
SQL
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;

Materialized View Trade-offs:

Advantages

•Extremely fast reads (pre-computed)
•Complex aggregations available instantly
•Can be indexed like regular tables
•Reduces load on source tables
•Enables query rewriting (some DBs)

Disadvantages

•Consumes storage space
•Data may be stale between refreshes
•Refresh can be expensive
•Maintenance overhead
•Must track dependencies

Refresh Strategies: Different applications require different refresh strategies depending on freshness requirements versus computational cost:

Materialized View Refresh Strategies
Strategy	When	Freshness	Cost
On-Demand	Manual trigger	Potentially stale	Control over timing
Scheduled	Cron/job scheduler	Predictable lag	Batch processing
On-Commit	After each write	Always fresh	Write overhead
Incremental	Delta/change processing	Near-fresh	Complex implementation

Automatic Query Rewriting

Some advanced databases (Oracle, SQL Server) can automatically rewrite queries to use materialized views even when the query doesn't reference them directly. If a query is logically derivable from a materialized view, the optimizer substitutes the view for dramatic performance improvement.

Push-Based vs. Pull-Based Materialization

Modern database research explores alternatives to the traditional pull-based iterator model. Push-based execution (or materialization-first) approaches offer different trade-offs that can significantly impact performance. Pull-Based (Traditional): In pull-based systems, parent operators pull tuples from children. Pipelining is the default; materialization happens only when blocking operators require it.

Push vs Pull Execution

Comparison

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

Push-Based Advantages:

Push-Based Benefits

•Better Cache Locality — Producers run in tight loops, keeping instruction cache hot
•Reduced Function Call Overhead — Data pushed through function pointers eliminates virtual dispatch per tuple
•SIMD-Friendly — Easier to vectorize when producing batches before pushing
•JIT Compilation — Simpler to compile pipeline segments into tight machine code
•Better Prefetching — Producers can prefetch next data while consumer processes current

Full Materialization Model: Some modern in-memory databases (like HyPer) use a full materialization approach where each operator completely materializes its output before the next operator runs. This seems counterintuitive but enables aggressive optimization:

Execution Model Comparison
Model	Memory Usage	Latency	Throughput	Best For
Pull (Pipelining)	O(1) per tuple	Low first-tuple	Moderate	OLTP, interactive
Push (Pipelining)	O(1) per tuple	Low first-tuple	Better	Mixed workloads
Full Materialization	O(n) per operator	Higher first-tuple	Highest	Analytics, batch

Morsel-Driven Parallelism

State-of-the-art systems like HyPer combine push-based execution with 'morsel-driven' parallelism—data is divided into small chunks (morsels) that workers pull from a shared pool, but within each morsel, execution is push-based. This combines the benefits of lazy morsel assignment with aggressive intra-morsel optimization.

Database Management SystemsQuery Execution Engine

Query Execution Engine

LevelIntermediate

Duration90 mins

TopicQuery Execution Engine

4 / 5

Materialization

When Pipelining Isn't Enough

Pipelining is elegant and efficient, but it has fundamental limitations. Some operations simply cannot produce output until they've seen all their input. A sort cannot tell you the smallest element without examining every element. An aggregation cannot compute the average without summing all values. In these cases, databases must materialize —explicitly store intermediate results before proceeding. Materialization is the counterpart to pipelining, representing a deliberate trade-off of memory and I/O for correctness or necessity. Understanding when materialization occurs, why it's sometimes preferable, and how to minimize its costs is essential for mastering query execution.

What You Will Learn

By the end of this page, you will understand the concept of materialization and when it's required, explore the trade-offs between materialization and pipelining, examine different materialization strategies and their use cases, and learn techniques for minimizing materialization overhead in query execution.

Understanding Materialization

Materialization in query execution refers to the explicit storage of intermediate query results, either in memory or on disk, before passing them to the next operator. Unlike pipelining, where tuples flow through immediately, materialization captures and holds results. Formal Definition: An operator materializes its output when it stores the complete (or partial) result set before returning any tuples to its parent. The consumers then read from this materialized storage rather than directly from the producing operator. Why Materialization Exists:

Reasons for Materialization

•Algorithmic Necessity — Some algorithms require complete input before producing output (sorting, hashing)
•Multiple Consumers — When an intermediate result is used by multiple operators, materializing avoids recomputation
•Rescan Requirements — Some operations (nested loop join inner) need to scan the same data multiple times
•Memory Management — Controlled spilling to disk when memory limits are exceeded
•Explicit Caching — Deliberate storage of frequently accessed intermediate results
•Transaction Isolation — Materializing ensures a consistent view across query execution

Pipelining

•Tuple flows immediately to parent
•No intermediate storage
•O(1) memory per tuple
•Single-pass processing
•Cannot rescan source

Materialization

•Tuples stored before forwarding
•Explicit intermediate storage
•O(n) memory for n tuples
•Multi-pass processing possible
•Can rescan stored results

Materialization Spectrum

Materialization isn't binary—it exists on a spectrum. Full materialization stores everything to disk. Partial materialization buffers some tuples in memory. Even pipelined operators maintain minimal state (current tuple). Understanding where your query falls on this spectrum is key to performance analysis.

Required Materialization: Blocking Operators

Some operators fundamentally require materialization because their algorithms cannot produce output until they've consumed all input. These are the blocking operators we introduced earlier, now examined from the materialization perspective. Sort Operator: Sorting is the canonical example of required materialization. To produce tuples in sorted order, the sort operator must see all input tuples to determine the global ordering.

Sort Materialization

Execution Trace

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

Hash Aggregate Operator: Aggregation with grouping requires building a complete hash table of all groups and their accumulated values:

Hash Aggregate Materialization

Execution Trace

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

Operators Requiring Materialization
Operator	What Gets Materialized	Why It's Required
Sort	All input tuples	Must see all to determine order
Hash Aggregate	Group states (keys + accumulators)	Must accumulate all group values
Hash Join (Build)	Complete hash table of build relation	Must have complete hash table for probing
Hash Distinct	Set of all distinct values	Must see all to know what's duplicate
Window Functions (some)	Entire partition or frame	Frame may depend on future rows
Set Operations (Except/Intersect)	Complete set for comparison	Must see all to compute set difference/intersection

Memory Implications

Required materialization can consume enormous memory for large inputs. A sort of 10 million rows might need several gigabytes. When memory limits are exceeded, operators must spill to disk—dramatically increasing execution time due to I/O.

Elective Materialization: Strategic Buffering

Not all materialization is algorithmically required. Sometimes, the query optimizer or executor chooses to materialize intermediate results for strategic reasons, even when pipelining would be correct. This elective materialization can improve overall performance. Common Reasons for Elective Materialization:

Strategic Materialization Scenarios

•Multiple Consumers — When an intermediate result feeds multiple parent operators, materializing once beats recomputing multiple times
•Expensive Subexpressions — If computing a value is costly, materializing it avoids repeated computation
•Rescan Prevention — For nested loop joins, materializing the inner input avoids costly repeated base table scans
•Snapshot Isolation — Materializing ensures consistent reads across long-running queries
•Memory Trade-off — Sometimes a small materialization enables more efficient downstream processing

Example: Multiple Consumers Consider a query with a CTE (Common Table Expression) referenced twice:

CTE Materialization Example
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;

Example: Nested Loop Materialization For nested loop joins where the inner relation is expensive to compute:

Inner Materialization

Plan Comparison

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

Optimizer Heuristics

Query optimizers use cost models to decide when elective materialization pays off. They compare the cost of recomputation versus the cost of materialization + rescanning. PostgreSQL's planner, for example, explicitly considers Materialize nodes when inner relations would otherwise be expensive to rescan.

Materialization Strategies

Not all materialization is equal. Databases employ various strategies depending on the size of intermediate results, memory constraints, and access patterns. Memory-Based Materialization: The fastest option when results fit in memory. Tuples are stored in memory buffers and can be accessed with minimal overhead.

Materialization Strategies
Strategy	Storage	Speed	When Used
In-Memory Buffer	RAM only	Fastest	Small results within work_mem
Memory + Disk Spill	RAM + temp files	Moderate	Results exceed memory limits
Full Disk-Based	Temp tablespace	Slowest	Very large intermediate results
Hash Table	RAM (spills if needed)	Fast lookups	Hash joins, hash aggregates
Tuple Store	Efficient tuple packing	Compact	Materialize nodes, CTE storage

Spilling to Disk: When in-memory buffers are exhausted, operators must spill data to disk. This process significantly impacts performance:

Sort Spilling Process

Process Flow

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

I/O Amplification

Disk-based materialization causes significant I/O amplification. Data is written to disk, then read back—often multiple times for merge passes. A query that could pipeline in 1 second might take 100+ seconds when forced to materialize to disk. Monitoring for disk spills is essential for performance tuning.

Memory Management for Materialization

Effective memory management is critical for materialization performance. Databases use sophisticated techniques to balance memory across operators and minimize disk spillage. Per-Operator Memory Limits: Most databases assign memory budgets to blocking operators. PostgreSQL uses work_mem, which sets the per-operator memory limit:

Memory Budget Example
Configuration
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

Adaptive Memory Allocation: Modern databases increasingly use adaptive strategies that allocate memory dynamically based on actual needs:

Adaptive Memory Strategies

•Memory Pools — Shared memory pools that operators draw from as needed; unused memory stays available
•Dynamic Work Memory — Adjust operator memory based on actual cardinality versus estimates
•Memory Pressure Monitoring — Release memory from completed operators for reuse by active ones
•Cooperative Spilling — Multiple operators coordinate to minimize total disk I/O
•Query-Level Budgets — Global memory limits across all operators in a query

Memory Parameters Across Database Systems
Database	Parameter	Description
PostgreSQL	work_mem	Per-operation memory for sorts and hashes
PostgreSQL	hash_mem_multiplier	Multiplier for hash operations (PG 13+)
MySQL	sort_buffer_size	Memory for sort operations
MySQL	join_buffer_size	Memory for join operations
Oracle	PGA_AGGREGATE_TARGET	Total working memory across all sessions
SQL Server	max server memory	Total buffer pool (includes workspace)

Tuning Memory Parameters

When optimizing for large analytical queries, increasing work_mem (or equivalent) can dramatically improve performance by avoiding disk spills. However, be cautious in high-concurrency OLTP scenarios—if many sessions run large queries simultaneously, they might exhaust server memory.

Materialized Views: Persistent Materialization

Materialized views extend the concept of materialization beyond single query execution. They persistently store the results of a query, enabling fast access to expensive computations. Materialized View Concept: Unlike regular views (which are just stored queries), materialized views store the actual result data. This trades storage space for query performance.

Materialized View Example
SQL
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;

Materialized View Trade-offs:

Advantages

•Extremely fast reads (pre-computed)
•Complex aggregations available instantly
•Can be indexed like regular tables
•Reduces load on source tables
•Enables query rewriting (some DBs)

Disadvantages

•Consumes storage space
•Data may be stale between refreshes
•Refresh can be expensive
•Maintenance overhead
•Must track dependencies

Refresh Strategies: Different applications require different refresh strategies depending on freshness requirements versus computational cost:

Materialized View Refresh Strategies
Strategy	When	Freshness	Cost
On-Demand	Manual trigger	Potentially stale	Control over timing
Scheduled	Cron/job scheduler	Predictable lag	Batch processing
On-Commit	After each write	Always fresh	Write overhead
Incremental	Delta/change processing	Near-fresh	Complex implementation

Automatic Query Rewriting

Some advanced databases (Oracle, SQL Server) can automatically rewrite queries to use materialized views even when the query doesn't reference them directly. If a query is logically derivable from a materialized view, the optimizer substitutes the view for dramatic performance improvement.

Push-Based vs. Pull-Based Materialization

Modern database research explores alternatives to the traditional pull-based iterator model. Push-based execution (or materialization-first) approaches offer different trade-offs that can significantly impact performance. Pull-Based (Traditional): In pull-based systems, parent operators pull tuples from children. Pipelining is the default; materialization happens only when blocking operators require it.

Push vs Pull Execution

Comparison

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

Push-Based Advantages:

Push-Based Benefits

•Better Cache Locality — Producers run in tight loops, keeping instruction cache hot
•Reduced Function Call Overhead — Data pushed through function pointers eliminates virtual dispatch per tuple
•SIMD-Friendly — Easier to vectorize when producing batches before pushing
•JIT Compilation — Simpler to compile pipeline segments into tight machine code
•Better Prefetching — Producers can prefetch next data while consumer processes current

Full Materialization Model: Some modern in-memory databases (like HyPer) use a full materialization approach where each operator completely materializes its output before the next operator runs. This seems counterintuitive but enables aggressive optimization:

Execution Model Comparison
Model	Memory Usage	Latency	Throughput	Best For
Pull (Pipelining)	O(1) per tuple	Low first-tuple	Moderate	OLTP, interactive
Push (Pipelining)	O(1) per tuple	Low first-tuple	Better	Mixed workloads
Full Materialization	O(n) per operator	Higher first-tuple	Highest	Analytics, batch

Morsel-Driven Parallelism

State-of-the-art systems like HyPer combine push-based execution with 'morsel-driven' parallelism—data is divided into small chunks (morsels) that workers pull from a shared pool, but within each morsel, execution is push-based. This combines the benefits of lazy morsel assignment with aggressive intra-morsel optimization.

Materialization

When Pipelining Isn't Enough

Understanding Materialization

Required Materialization: Blocking Operators

Elective Materialization: Strategic Buffering

Materialization Strategies

Memory Management for Materialization

Materialized Views: Persistent Materialization

Push-Based vs. Pull-Based Materialization

There’s more to understand.

Materialization

When Pipelining Isn't Enough

Understanding Materialization

Required Materialization: Blocking Operators

Elective Materialization: Strategic Buffering

Materialization Strategies

Memory Management for Materialization

Materialized Views: Persistent Materialization

Push-Based vs. Pull-Based Materialization

There’s more to understand.