Query Plan Structure

SQL statements are typically transformed into tree-like execusion plans where data flows from leaf nodes to the root node, producing results at the top. Operators within these trees are usually binary, having one or two child operators. This discussion focuses on modeling the data flow process within execution plans, covering:

• Processing Models
• Access Methods
• Expression Evaluation

Processing Models

Database management systems use different processing models to execute query plans. Three primary approaches exist:

• Iterator Model
• Materialization Model
• Vectorized/Batch Model

Each model suits different workload patterns.

Iterator Model

The most prevalent processing approach, also known as Volcano or Pipeline Model, implements a fetch_next function for each operator in the query plan. Each invocation returns either a single record or null, with null indicating completion. Each operator maintains an internal loop that calls its child operators' fetch_next functions to obtain records for processing, creating a top-down pipeline through the entire query plan.

This approach is used in virtually all row-based database systems including SQLite, MySQL, and PostgreSQL. Key considerations include:

• Some operators remain blocked until children return all records; these are called pipeline breakers, including joins, subqueries, and order-by operations
• Output control is straightforward to implement, such as LIMIT operations that stop calling child operators once sufficient records are obtained

Materialization Model

Each operator processes all input at once and outputs complete results in a single batch. Database systems pass parameters to operators to prevent excessive data processing, following a bottom-up approach.

Each plan operator implements an produce_output function:

• Operators process all descendant records in one operation
• The function returns all records the operator will emit
• Once execution completes, the system no longer needs to return to retrieve additional data

The materialization model:

• Suits OLTP workloads better since they typically require processing small record sets, reducing execution and scheduling overhead
• Works poorly for OLAP queries generating large intermediate results, as the system may need to spill these results to disk between operators

Vectorization Model

Vectorization represents a compromise between Iterator and Materialization models:

• Each operator implements a fetch_next function that returns batches of records rather than individual ones
• Internal loops process tuples in batches
• Batch sizes can vary based on requirements (hardware capabilities, query characteristics)

Vectorization works ideally for OLAP queries:

• Significantly reduces call frequency per operator
• Enables operators to use vectorized instructions (SIMD) for batch tuple processing

Current implementations exist in VectorWise, Peloton, Preston, SQL Server, Oracle, and DB2.

Processing Direction

1. Top-to-Bottom: Executes downward, pulling data from child nodes
2. Bottom-to-Top: Executes upward, pushing data to parent nodes

Models	Direction	Emits	Target
Iterator/Volcano	Top-Down	Single Record	General Purpose
Materialization	Bottom-Up	Entire Record Set	OLTP
Vectorized	Top-Down	Record Batch	OLAP

Access Methods

Access methods define how database systems retrieve data from tables, concepts not defined in relational algebra. Three primary approaches exist:

• Sequential Scan
• Index Scan
• Multi-Index/"Bitmap" Scan

Identical query plans can execute through multiple methods; most database systems prefer using Index Scans when possible.

Sequential Scan

Sequential scanning retrieves records in order from table pages, representing the database's fallback approach.

for current_page in table.storage_pages:
    for record in current_page.records:
        if evaluate_condition(record):
            # process record

The database maintains an internal cursor tracking previously accessed positions (page/slot).

Sequential Scan optimization strategies include:

• Prefetching
• Parallelization
• Buffer Pool Bypass
• Zone Maps
• Late Materialization
• Heap Clustering

Zone Maps

Pre-calculating statistical values (maximum, minimum, average) for attribute values per page and storing them in zone maps. Before accessing pages, the database checks zone maps to determine whether access is necessary. When the system discovers a page's zone map shows a maximum value of 400 for a requested range, accessing that page becomes unnecessary.

Late Materialization

For columnar databases, delaying data transfer timing between operators proves beneficial. If certain column data isn't needed higher in the query tree, only offsets or column identifiers need passing upward. This allows retrieving required data later.

Heap Clustering

When using clustering indexes, records are arranged in pages according to specified order. If queries access indexed attributes, the database can jump directly to target records.

Index Scan

The database selects an index to locate required records. Index selection depends on several factors:

• Attributes contained in the index
• Attributes referenced by queries
• Attribute domain definitions
• Predicate composition
• Whether index keys are unique or non-unique

While many factors influence index selection, the core principle involves filtering out as many records as early as possible, as demonstrated by this query:

SELECT * FROM students
 WHERE age < 30
   AND department = 'CS'
   AND country = 'US';

Student distribution across different attributes might appear:

Scenario #1: 99 people under 30 years old, but only 2 in CS department.

Scenario #2: 99 people in CS department, but only 2 under 30 years old.

For Scenario 1, using department index filters more records; for Scenario 2, using country index filters more records.

Multi-Index Scan

When multiple indexes are available, the system can:

• Calculate tuple ID sets matching each index
• Determine set intersection or union based on predicates (union vs. intersection)
• Retrieve corresponding tuples and complete remaining processing

Using the previous SQL example, if indexes exist on age and department, multi-index scanning proceeds as shown. Set intersections can utilize bitmaps, hash tables, or Bloom filters.

PostgreSQL refers to multi-index scan as Bitmap Scan.

Index Scan Page Sorting

When non-clustering indexes are used, index-ordered retrieval becomes inefficient due to constant page switching, causing unnecessary I/O. To address this, databases typically find all required tuples first, sort them by page ID, then read tuple data, ensuring each required page receives only one I/O during the process.

Modification Queries

Operators modifying the database (INSERT, UPDATE, DELETE) handle constraint checking and index updates.

• Update and delete operators require child operators to pass target record IDs, which they modify themselves. This process tracks modified records because update operations change tuple physical locations, potentially causing scan operators to visit the same tuple multiple times. Consider raising wages by $100 for all employees earning less than $1000; without tracking modifications, someone currently earning $300 would be updated seven times since each modification keeps their wage below $1000, causing subsequent iterations to encounter them again. — Halloween Problem
• Insert operator implementation includes two approaches:
  • Materialize and insert within the operator itself, e.g., direct insert (xxx, yyy, zzz)
  • Obtain data from child operators, then insert within the operator, e.g., retrieving data from other tables, modifying or assembling it before inserting into the current table

Expression Evaluation

Database systems use expression trees to represent WHERE clauses.

Tree nodes represent different expression types:

• Comparisons (=, <, >, !=)
• Conjunction (AND), Disjunction (OR)
• Arithmetic Operators (+, -, *, /, %)
• Constant Values
• Tuple Attribute References

Expression trees enable data filtering decisions, though this process proves inefficient. Many database systems adopt JIT compilation, compiling comparison processes directly into machine code to improve expression evaluation efficiency.

While expression trees offer flexibility, they operate slowly.