Back
+20 XP
Concept

Query Execution: The Volcano Iterator Model

Materializing intermediate SQL tables in RAM exhausts memory. The Volcano Iterator Model structures execution as a tree of operators implementing `open()`, `next()`, and `close()`. The parent pulls one tuple at a time from its child on demand with minimal memory overhead 🌋🔄.

python
class ScanOperator:
    def __init__(self, records):
        self.records = records
        self.cursor = 0
    def open(self): self.cursor = 0
    def next(self):
        if self.cursor < len(self.records):
            val = self.records[self.cursor]
            self.cursor += 1
            return val
        return None
    def close(self): pass

class FilterOperator:
    def __init__(self, child, predicate):
        self.child = child
        self.predicate = predicate
    def open(self): self.child.open()
    def next(self):
        while True:
            row = self.child.next()
            if row is None or self.predicate(row):
                return row
    def close(self): self.child.close()

# Query: SELECT * WHERE val > 20
plan = FilterOperator(ScanOperator([10, 25, 12, 40]), lambda x: x > 20)
plan.open()
print(f"Pulled tuple: {plan.next()}, Pulled tuple: {plan.next()} 🚀")
plan.close()

# 59. Query Execution: The Volcano Iterator Model If a database executes `SELECT UPPER(name) FROM users WHERE age > 21` by first allocating an array of 5,000,000 filtered rows in RAM, and then passing that massive array to a mapping function, a complex 10-table join will exhaust server memory instantly 🛑. ```python # Materialized Intermediate Buffering (Anti-Pattern): # scan_all() -> 100M rows in RAM # filter_all() -> 50M rows in RAM # project_all() -> 50M rows in RAM # Memory usage: 10+ Gigabytes! # Volcano Iterator Pipeline (Pull-Based): # Root calls next() -> Filter calls next() -> Scan pulls ONE row # Memory usage: 1 row in RAM! ``` ### The Volcano Protocol (Open / Next / Close) 1. **`open()`**: Initializes operator resources, resets index cursors, and prepares child operators. 2. **`next()`**: Evaluates expressions and yields exactly **one** tuple to the caller. Returns `None` (or EOF) when depleted. 3. **`close()`**: Cleans up memory allocations, closes file descriptors, and propagates teardown down the plan tree 🌋🔄. --- ### Interactive Pop-Quiz 🧠 #### What is the primary memory advantage of the Volcano iterator model in relational query engines? - [ ] Operators stream individual tuples on-demand without buffering entire intermediate result sets in RAM 🌋 - [ ] It compresses memory using LZ4 within CPU L2 cache - [ ] It converts all database tuples into 64-bit integer pointers - [ ] It runs exclusively on static readonly memory chips --- ### Practical Challenge 🎯 Implement `MapOperator(child, transform_fn)` that takes a Volcano operator, applies `transform_fn(row)` inside `next()`, and stops on `None`. Chain `ScanOperator([1, 2, 3, 4])` -> `FilterOperator(lambda x: x % 2 == 0)` -> `MapOperator(lambda x: x * 10)`. Pull all tuples until `None`, and print the resulting list. <details> <summary>Solution</summary> ```python class ScanOperator: def __init__(self, data): self.data = data self.i = 0 def open(self): self.i = 0 def next(self): if self.i < len(self.data): val = self.data[self.i] self.i += 1 return val return None def close(self): pass class FilterOperator: def __init__(self, child, pred): self.child = child self.pred = pred def open(self): self.child.open() def next(self): while True: row = self.child.next() if row is None or self.pred(row): return row def close(self): self.child.close() class MapOperator: def __init__(self, child, fn): self.child = child self.fn = fn def open(self): self.child.open() def next(self): row = self.child.next() if row is None: return None return self.fn(row) def close(self): self.child.close() plan = MapOperator(FilterOperator(ScanOperator([1, 2, 3, 4]), lambda x: x % 2 == 0), lambda x: x * 10) plan.open() res = [] while True: r = plan.next() if r is None: break res.append(r) plan.close() assert res == [20, 40] print(res) ``` </details>

Checkpoint

What is the primary memory advantage of the Volcano iterator model in relational query engines? 🧠

Practice

Implement `MapOperator(child, transform_fn)` that takes a Volcano operator, applies `transform_fn(row)` inside `next()`, and stops on `None`. Chain `ScanOperator([1, 2, 3, 4])` -> `FilterOperator(lambda x: x % 2 == 0)` -> `MapOperator(lambda x: x * 10)`. Pull all tuples until `None`, and print the resulting list. 🎯

Terminal
01
Tap code blocks below to assemble
Available Blocks