Back
+30 XP
Concept

Capstone Query Planner: Volcano Iterator Stream Pipeline

Materializing multi-million-row database tables into memory arrays will trigger Linux OOM termination. The Capstone query planner executes declarative pipelines using the Volcano Iterator Model (`open()`, `next()`, `close()`), pulling one tuple at a time across Scan, Filter, and Limit operators in strictly $O(1)$ memory 🌋🌊⚡.

python
class StreamScan:
    def __init__(self, rows):
        self.rows = rows
        self.idx = 0
    def open(self): self.idx = 0
    def next(self):
        if self.idx < len(self.rows):
            row = self.rows[self.idx]; self.idx += 1; return row
        return None

class StreamFilter:
    def __init__(self, src, pred):
        self.src = src; self.pred = pred
    def open(self): self.src.open()
    def next(self):
        while (row := self.src.next()) is not None:
            if self.pred(row): return row
        return None

plan = StreamFilter(StreamScan([10, 25, 40, 55]), lambda x: x > 30)
plan.open()
print("Streamed Tuple:", plan.next())

# 116. Capstone Query Planner: Volcano Iterator Stream Pipeline When querying a 50GB table to find "the first 10 orders greater than \$500", beginner developers write code that loads all 50 million records into a Python list, filters the list, and slices `[:10]`. The operating system immediately terminates the process with exit code 137 (OOM Killer) 🛑. ```python # The Volcano Iterator Model (Goetz Graefe): # Every query operator implements a uniform interface: # 1. open(): Initialize internal cursors and allocate operator state. # 2. next(): Return the NEXT matching tuple, or None if exhausted. # 3. close(): Release file handles and tear down state. ``` ### Pull-Based Streaming Architecture ```mermaid flowchart TD Consumer["Client Consumer (calls next())"] --> Limit["LimitOperator (limit=2)"] Limit --> Filter["FilterOperator (val > 30)"] Filter --> Scan["ScanOperator (Disk/Memory)"] ``` Because the top of the tree (Limit) pulls tuples from the child only when needed, the moment the limit is reached, execution halts immediately! - The pipeline never allocates memory for millions of rows. - Space complexity is strictly **$O(1)$** regardless of dataset size 🌋🌊⚡. --- ### Interactive Pop-Quiz 🧠 #### What is the primary memory advantage of the Volcano Iterator Model over naive list comprehensions? - [ ] It executes in $O(1)$ memory by pulling records on-demand one by one through pipelined operators, never buffering entire tables in RAM 🌋 - [ ] It uses hardware-level AES encryption to compress lists - [ ] It forces Python to run on CUDA GPU cores - [ ] It eliminates the need for disk storage --- ### Practical Challenge 🎯 Implement Volcano query operators: `ScanOperator(data: list[dict])`, `FilterOperator(child, predicate)`, and `LimitOperator(child, limit: int)` implementing standard `open()`, `next() -> dict | None`, and `close()`. Create a pipeline filtering records with `val > 30` and limiting output to 2 tuples from dataset `[{'id': 1, 'val': 10}, {'id': 2, 'val': 50}, {'id': 3, 'val': 90}, {'id': 4, 'val': 120}]`. Verify extracted rows have IDs 2 and 3. Print results. <details> <summary>Solution</summary> ```python class Operator: def open(self): pass def next(self): raise NotImplementedError def close(self): pass class ScanOperator(Operator): def __init__(self, data: list[dict]): self.data = data self.cursor = 0 def open(self): self.cursor = 0 def next(self): if self.cursor < len(self.data): rec = self.data[self.cursor] self.cursor += 1 return rec return None class FilterOperator(Operator): def __init__(self, child: Operator, predicate): self.child = child self.predicate = predicate def open(self): self.child.open() def next(self): while True: rec = self.child.next() if rec is None: return None if self.predicate(rec): return rec def close(self): self.child.close() class LimitOperator(Operator): def __init__(self, child: Operator, limit: int): self.child = child self.limit = limit self.yielded = 0 def open(self): self.child.open() self.yielded = 0 def next(self): if self.yielded >= self.limit: return None rec = self.child.next() if rec is not None: self.yielded += 1 return rec def close(self): self.child.close() raw_data = [ {"id": 1, "val": 10}, {"id": 2, "val": 50}, {"id": 3, "val": 90}, {"id": 4, "val": 120} ] scan = ScanOperator(raw_data) filt = FilterOperator(scan, lambda r: r["val"] > 30) lim = LimitOperator(filt, limit=2) lim.open() results = [] while (row := lim.next()) is not None: results.append(row) lim.close() assert len(results) == 2 assert results[0]["id"] == 2 assert results[1]["id"] == 3 print(f"Volcano Pipeline verified: {results}") ``` </details>

Checkpoint

What is the primary memory advantage of the Volcano Iterator Model over naive list comprehensions? 🧠

Practice

Implement Volcano query operators: `ScanOperator(data: list[dict])`, `FilterOperator(child, predicate)`, and `LimitOperator(child, limit: int)` implementing standard `open()`, `next() -> dict | None`, and `close()`. Create a pipeline filtering records with `val > 30` and limiting output to 2 tuples from dataset `[{'id': 1, 'val': 10}, {'id': 2, 'val': 50}, {'id': 3, 'val': 90}, {'id': 4, 'val': 120}]`. Verify extracted rows have IDs 2 and 3. Print results. 🎯

Terminal
01
Tap code blocks below to assemble
Available Blocks