Execution models inside one worker

What does it cost to hand a row from one operator to the next?

Boundaries are the cost

Three idlenesses said the runtime's currency is idleness. Execution models attack exactly one of the three idlenesses, dependency. They do it by choosing two things:

1. Who owns the loop? (Does the consumer ask for rows, or does the producer send them?)
2. How much data crosses one control transfer? (One tuple? A batch of 1,000? A whole stage?)

Everything else in this article follows from those two choices, plus one hardware fact: a control transfer costs about as much as a modest amount of real work, and an unpredictable control transfer costs an order of magnitude more.

The consequence deserves to be stated before any mechanism. The cost of an operator pipeline is not the sum of the operators' work. It is the sum of their work plus the cost of the boundaries between them. Boundaries are what execution models manipulate. Every model in this article either amortizes a boundary (spreads its cost over many tuples), deletes a boundary, or moves it somewhere the clock does not notice.

The cube, and a break in scale

Two structural corrections come before the details.

First: the common list of models is a cube, not a spectrum. There are three independent choices:

• Direction of control: pull (the consumer calls the producer) or push (the producer calls the consumer).
• Granularity of transfer: tuple-at-a-time or batch-at-a-time (and, at the extreme, a whole stage as one unit of generated code).
• Binding time of the code: interpreted (a generic operator reads the plan at run time) or compiled (code is generated for this one query).

Two choices on each of three axes give eight combinations, and shipped systems occupy all of them:

(The placement of Spark's code generation in the "pull" row is a simplification. Inside a generated stage, Spark's code is organized as a push-style produce/consume loop; the pull view applies at the stage edges.)

This dissolves the most common claim in the area: "the Volcano model is slow." The iterator model's cost is per-tuple function calls and generic attribute access. It is not the pull direction. Vectorwise is pull-based and was, for years, the fastest analytical engine in existence. Direction and granularity are orthogonal. Treating them as one dial is a reasoning error.

Second: the second half of a typical model list changes scale without announcing it. The first five models (Volcano, push, vectorized, compiled, morsel-driven) govern control flow inside one worker, where a boundary costs nanoseconds. The last four (DAG, BSP, actors, serverless) govern control flow between workers, where a boundary costs milliseconds and can fail. Six orders of magnitude separate the two halves. They answer different questions, and none of the reasoning about one half transfers to the other. So this mechanism treats them as two blocks: this article, and then Across machines.

Volcano / iterator (pull)

The Volcano (or iterator) model is the classic design. Each operator offers three methods: open(), next() which returns one tuple, and close(). The operator at the top calls next() on its child, which calls next() on its child, and so on down to the scan. Each call returns one tuple.

class Filter:                      # a "pull" operator
    def __init__(self, child, pred): self.child, self.pred = child, pred
    def next(self):
        while True:
            row = self.child.next()          # virtual call into the child
            if row is None: return None      # end of input
            if self.pred(row): return row    # virtual call into the predicate

# the top of the plan keeps calling next() until it gets None

The constraint behind this design is logical, not physical: an operator that must return control to its consumer after every tuple has to be resumable. Everything else follows from that.

• Resumability means an operator cannot be written as a simple loop. Its loop must be turned inside out into a state machine whose state lives in the operator's object on the heap, because the loop is suspended on every tuple.
• Therefore intermediate values cannot stay in CPU registers across a tuple. They are written to a tuple structure in memory and read back by the next operator.
• Therefore attribute access goes through a generic interface: an offset lookup, a null check, a type dispatch.
• Therefore the boundary is an indirect virtual call that the compiler cannot inline. That prevents every downstream optimization: no constant folding across operators, no hoisting of loop-invariant work, no vectorization.

The arithmetic. A pipeline of depth d costs d virtual calls per tuple. A call, the indirect branch and the lost inlining cost on the order of tens of cycles per boundary. The useful work in a selective filter (load, compare, branch) is a few cycles. So the ratio of overhead to work is 10× to 50× per operator, multiplied by the pipeline depth. Reported end-to-end gaps on expression-heavy queries reach two orders of magnitude between a tuple-at-a-time interpreter and hand-written code.

What the model buys. This is why it survived thirty years and still runs most transactional (OLTP) databases:

• The consumer's call is the flow control. There are no buffers, no queues, no credit protocol.
• LIMIT 10 is implemented by not calling again. Cancellation is also "not calling again".
• The operator interface is three methods, and any operator composes with any other without knowing its consumer.
• The engineering cost is close to zero.

For a query that returns 10 rows from an index lookup, the per-tuple overhead is multiplied by 10 and is therefore free. That is why Mateo's index lookup is instant.

Boundary condition on the criticism. The iterator model is only bad when the tuple count is large. Its per-tuple overhead is a constant, so the model is wrong exactly in proportion to how analytical the workload is. This is not a flaw discovered later. It is the "fixed cost moves up as the layer below gets faster" principle arriving on schedule as data volumes grew.

Push-based execution

Invert the direction, and the operator becomes a loop again. The producer runs a loop over its input and calls consume(tuple) on its consumer. The consumer's work is inlined into the producer's loop body. Values stay in registers from the scan to the pipeline breaker.

# push: the scan owns the loop; the filter and the aggregate are inlined into it
total = 0
for row in scan:                    # producer owns the loop
    if row.status == 'OK' and row.tariff_zone == 'N':   # filter, inlined
        total += row.kwh                                # aggregate, inlined

This is why push is the natural base for code generation: the generated code is one loop nest, and the operator boundaries no longer exist at run time.

Two more structural advantages:

• A multi-consumer edge (one scan feeding two operators) is trivial in push: call both. In pull it needs an explicit "tee" operator with buffering. So plans where results are shared prefer push.
• Multi-input operators become natural. Each side pushes into its own sink. In pull, one operator has to interleave next() calls on two children.

Now the bill, and it is the reason this model needs a mechanism that is often forgotten: push has no flow control. The producer decides when the next tuple moves, so the consumer has no way to refuse. Inside one thread that does not matter. The call is synchronous, so the producer is blocked while the consumer works. But once a boundary crosses a thread or a machine, the consumer needs a bounded queue and the producer needs to block on it. You have then re-implemented, explicitly and with tuning parameters, what pull gave you for free. Flink's credit-based flow control (a consumer gives the producer "credits" for how many buffers it can accept) exists for exactly this reason, and so does every bounded exchange buffer in every push engine. Early exit needs the same treatment in reverse: LIMIT becomes an out-of-band stop signal sent up the pipeline, not the absence of a call.

This is the principle that control flow is flow control: the party that decides when the next unit moves is the only party that can refuse it. Push buys register residency and pays for it with an explicit backpressure protocol.