Time is work divided by the capacity you kept busy

Why is elapsed time not "work divided by capacity", and what are the only three reasons a machine sits idle?

From "work" to "idleness"

Earlier topics in query processing treat a query as a mathematical object. One topic asks what an operator computes and at what asymptotic cost (a join of two sorted lists costs about n + m comparisons). Another asks which tree of operators is cheapest under estimated row counts. Both reason in units of work: rows touched, bytes scanned, comparisons performed. Both quietly assume that once a plan is chosen, elapsed time is proportional to the work the plan names.

This mechanism is where that assumption breaks, and it breaks in one specific way:

The new constraint is the machine itself: a finite number of cores, a real clock, memory that is not equally near every core, and handoffs between steps that can cost as much as the computation they connect. The constraint that stops mattering is asymptotics. Nothing here changes the complexity class of any algorithm. Every mechanism here is a constant factor between 2× and 100×. Those constants come from three places: per-tuple control-flow overhead, cache and branch behaviour, and idleness.

A plan that is 2× better than the alternative, executed by a runtime that keeps only 25% of the machine busy, loses to the worse plan run by a runtime that keeps 90% busy. That is Hana's dashboard.

---

Three idlenesses

Idleness has exactly three causes. This mechanism's three groups of mechanisms are the three answers. It is worth deriving them, because for any mechanism it tells you which bill you are about to receive.

1. Dependency idleness: a unit waits for its producer

A plan is a graph with edges. A consumer cannot work until its producer has made something. The only escape is to overlap producer and consumer, and overlapping needs a buffer between them. The buffer costs memory, and its depth follows Little's Law (L = λW): to keep a consumer fed across a producer latency W at rate λ, you need λW units in flight. Execution models are about this idleness. They answer three questions: who owns the thread, what size of unit crosses each edge, and who is allowed to say "not yet".

2. Imbalance idleness: a unit waits for a peer

Many workers run in parallel. At a barrier or a join point, everyone waits for the slowest one. This is forced by variance in task duration plus any synchronization. The escape is smaller work units plus dynamic assignment. The cost is dispatch overhead and lost locality (data that was in a core's cache is no longer used by that core). Parallelism is about this idleness.

3. Exclusion idleness: a unit waits for a shared resource

Workers share a hash table, a scheduler lock or memory bandwidth, and they take turns. This is forced by sharing itself. The escape is to partition the resource per worker. The cost is duplication and a merge step. This is the coordination cost that limits scaling (the contention and coherency terms of the Universal Scalability Law: workers waiting for each other, and keeping their copies consistent), arriving at the execution level. It is also why the shuffle exists at all: partitioning by key is the act of converting exclusion into data movement.

To pay none of the three, you would have to give up global order or determinism. That is the conservation statement of this mechanism: you can move the cost, but you cannot remove it.

---

Why the shuffle gets its own group

The shuffle earns first-class status for a structural reason, not an empirical one. It is the only operation whose number of edges grows as the product of the two stage widths (M producers × R consumers), rather than linearly with the number of workers. Everything else here has O(n) coordination. The shuffle has O(n²).

The one number to carry through the whole shuffle discussion is:

Compare it to the minimum efficient transfer of the storage or network underneath. That minimum is roughly 2 MB for spinning disk, about 4 MB for object storage, and about 250 KB for NVMe (fast flash drives). The comparison tells you at once whether a shuffle is limited by bandwidth (bytes per second) or by operations (requests per second). It also tells you which of the six shuffle mechanisms in The shuffle is the relevant one. This single division explains sort shuffle, file consolidation and remote shuffle services as the same fix applied at three different places.

---

The second number: the barrier and the maximum

Consider n tasks that all sit behind a barrier. Each task has a mean duration, and the durations vary. The coefficient of variation c is the standard deviation divided by the mean (c = 0.3 means a typical task is about 30% above or below the mean). For light-tailed durations (those without extreme outliers):

This is why straggler mitigation is a first-class mechanism and not an operational nicety. It is also the principle "variance costs more than volume" in its sharpest form: here the variance is multiplied by fan-in (the number of tasks behind the barrier).