Real query engines (Postgres, DuckDB, basically every SQL database) execute a query as a tree of operators, where each operator pulls rows from its child one at a time -- this is called the "Volcano" or iterator model. SELECT name FROM t WHERE age > 40 becomes roughly: Project(Filter(Scan(t), age > 40), [name]).

Scan is done for you. Implement Filter, Project, Limit, Sort, and NestedLoopJoin so they all follow the same iterator protocol (__iter__ / __next__):

• Filter(child, predicate) -- yields only rows from child where predicate(row) is True.
• Project(child, columns) -- yields each row from child narrowed down to just columns, in that order.
• Limit(child, n) -- yields at most n rows, then stops.
• Sort(child, key) -- yields every row from child, ordered by key.
• NestedLoopJoin(left, right_rows, predicate, combine) -- for each row from left, re-scans all of right_rows and yields combine(left_row, right_row) for every right_row where predicate(left_row, right_row) holds.

The missing link: not every operator can stream

Filter, Project, and Limit are all streaming: each __next__ call does a bounded amount of work and returns as soon as it can, without needing to know anything about rows it hasn't seen yet. This is what lets a real database answer SELECT * FROM huge_table WHERE x = 1 LIMIT 10 without ever reading the whole table, and without ever holding more than one row in memory at a time.

Sort cannot do this. To know which row comes first, it has to have already seen every row -- there's no way around reading the entire child before producing a single output row. This makes Sort a blocking operator, and it's a genuinely expensive fact about databases: ORDER BY on an unindexed column means the engine must materialize and hold the entire intermediate result before your query can return its first row, no matter how small your LIMIT is. (Real engines have a trick for exactly this case -- see the grounding links below.)

NestedLoopJoin is the naive join strategy: for every one of left's rows, walk all of right_rows looking for matches. That's O(n * m) work for n left rows and m right rows -- correct, but the reason real planners only reach for it when no index or hash-based strategy is available (see this course's Hash Join exercise for the faster alternative, and MVCC/B-Tree exercises for how an index would let a join skip the full re-scan entirely).

Example

rows = [{"id": 1, "age": 36}, {"id": 2, "age": 85}]
plan = Project(Filter(Scan(rows), lambda r: r["age"] > 40), ["id"])
list(plan)  # -> [{"id": 2}]

Constraints

• Filter/Project/Limit must only ever look at one row at a time, pulling more from child as needed -- never materialize the whole result eagerly. Limit(child, n) specifically must pull exactly n rows from child (not n + 1) when at least n are available.
• Sort must not touch child at all until its first __next__ call (building a plan shouldn't run it), and that first call is where all buffering/sorting happens; every later call just walks the buffered result.
• NestedLoopJoin.right_rows is a plain list, re-scanned from the start for every left row -- it is never exhausted the way a one-shot iterator would be. One left row can produce zero, one, or many output rows.
• Let StopIteration propagate naturally when a child (or left) is exhausted -- don't catch and re-raise it yourself.

Real-world grounding

• Postgres's sequential scan + filter: src/backend/executor/nodeSeqscan.c
• Postgres's LIMIT: src/backend/executor/nodeLimit.c
• Postgres's sort node, including the bounded/"top-N heapsort" optimization that kicks in specifically for ORDER BY ... LIMIT n (avoiding a full materialize+sort when only the top n rows are needed): src/backend/executor/nodeSort.c, src/backend/utils/sort/tuplesort.c
• Postgres's nested loop join: src/backend/executor/nodeNestloop.c
• DuckDB's filter/projection/join operators: physical_filter.cpp, physical_projection.cpp, physical_nested_loop_join.cpp

All of these work the same pull-based way as this exercise, just vectorized (operating on batches of rows per call, not one row at a time) for performance.