Joins, aggregates and windows: what each forces

What does a window function really cost?

The join family, by what each variant does to cardinality

For an equijoin on key k, the output size is

where f_R(v) is the number of rows of R with key v (and likewise for S). This is the dot product of the two frequency vectors.

The mean frequency tells you almost nothing. The answer is dominated by whichever key is common on both sides. Under a Zipf distribution, the top key can contribute more output than the rest of the key domain combined. This one expression predicts everything Join algorithms will say about skew. It also explains why "both tables are 10 GB" is not an input to any useful estimate.

Semi-join. This is the only join variant that cannot amplify: its output is a subset of the left side, each left row at most once. That makes it the standard form of data reduction, and runtime Bloom filters (Join algorithms) are built to approximate it.

Anti-join. Also non-amplifying, but more expensive in one way. A semi-join can stop looking after the first match. An anti-join must exhaust the right side before it can say that a row has no match. Short-circuiting exists for one and not for the other.

Outer joins add rows padded with NULLs. Downstream, a padded NULL looks the same as a NULL that was in the data. Three things follow:

1. A predicate on the null-supplying side, written in WHERE instead of ON, silently turns the outer join back into an inner join. This is the most common outer-join bug, and it is a consequence of the semantics. See the example below.
2. Outer joins are not associative. The NULL padding is created at a specific place, and a later join can match on it. This limits how the optimizer may reorder joins.
3. FULL OUTER needs a match bit per build row and a second output phase. After probing, the engine must emit the build rows that were never matched. So it cannot be written as a pure "probe and emit" pipeline the way the one-sided variants can.

Example (Omar's second report).

-- Intention: keep every order; attach tier only where the customer is gold.
SELECT o.order_id, c.tier
FROM orders o LEFT JOIN customers c ON o.customer_id = c.customer_id
WHERE c.tier = 'gold';          -- WRONG place: unmatched orders have c.tier = NULL,
                                -- NULL = 'gold' is UNKNOWN, so they are dropped.

-- Correct: put the condition in ON, so it limits which customers match.
SELECT o.order_id, c.tier
FROM orders o LEFT JOIN customers c
  ON o.customer_id = c.customer_id AND c.tier = 'gold';

NOT IN versus NOT EXISTS is where three-valued logic becomes an execution structure. If the subquery produces a single NULL, then x NOT IN (…) is UNKNOWN for every x that does not match, and the query returns nothing. (Why: x NOT IN (1, NULL) means x <> 1 AND x <> NULL. The second part is UNKNOWN, so the whole condition is never TRUE.) This is Omar's first report.

So the engine cannot use a plain two-outcome anti-join. It needs three outcomes for each probe:

• matched,
• unmatched and no NULLs present,
• unmatched and NULLs present.

This is the mark join, also called the null-aware anti-join. NOT EXISTS has no such need and compiles to a plain anti-join. That is the whole reason one form is reliably faster than the other. It is a semantics fact, not an implementation quirk.

Lateral / correlated subqueries are loops by definition. The inner expression takes a parameter from the outer row, so it has no set-oriented form until it is decorrelated (rewritten as a normal join). The cost is |R| × (cost per invocation), and the cost per invocation is mostly fixed overhead. So decorrelation is exactly fixed cost sets the batch size: it turns n small invocations into one large batched operation. Hold on to this framing; it explains why decorrelation is worth much more than it seems it should be.

Aggregation: blocking is ignorance about completeness

A group-by holds O(NDV) state (not O(N)) and emits NDV rows. It is blocking for one reason only: the engine does not know when a group is finished.

Supply that knowledge and the blocking disappears. If the input is sorted on the grouping key, each group can be emitted the moment its last row passes, and the state shrinks to O(1).

This generalizes, and it is the most portable idea in this article. Sortedness, hash partitioning, and (in stream processing) a watermark (a promise that no older data will arrive) are three mechanisms that answer one question: is this group complete? Aggregation's memory demand is the price of not knowing.

The algebra of aggregate functions

The function itself decides what is possible. Define three classes:

Example. AVG of two partitions with (sum 10, count 4) and (sum 20, count 6): combine to (30, 10), then 30 / 10 = 3. Averaging the two averages (2.5 and 3.33) would be wrong. For MEDIAN, no fixed-size summary of a partition lets you combine two partitions exactly.

For a holistic aggregate there is no bounded intermediate. That is a theorem about the function, not a gap in the implementation. No combiner exists, so no map-side reduction (summarizing before the data moves) exists, so the raw rows must reach one place. That is the full explanation for why COUNT DISTINCT is the query that destroys clusters. It is also the cleanest confirmation of the principle the function's algebra decides whether partial aggregation is possible. Aggregation algorithms uses this.

Several distinct aggregates multiply state. COUNT(DISTINCT x) needs O(NDV(groups) × NDV(x)) state, not O(NDV(groups)). Several distinct aggregates over different columns cannot share one pass. So engines replicate the input once per distinct column, with a tag. The input is physically expanded k times before aggregation. The semantics forced the replication.

Grouping sets, rollup and cube

GROUPING SETS, ROLLUP and CUBE compute k groupings together. A cube over d columns is 2^d groupings. Two execution shapes exist:

• Expand. Replicate each input row k times, each copy tagged with its grouping set, and run one aggregation over k·N rows.
• Reuse. Compute the finest grouping once, then derive the coarser ones from that output.

Reuse is much cheaper, but it is available only for distributive and algebraic functions. A holistic aggregate needs the raw rows for every grouping set, so a cube over a median is k full aggregations.

One more detail: GROUPING_ID() exists because a NULL in the result is ambiguous. It may mean "this column was aggregated away" or "the value really was NULL". Three-valued logic forced an addition to the language.

Window functions: the cost is the number of distinct sort orders

A window function computes a value for each row from a set of related rows (its window), without collapsing the rows. Examples: ROW_NUMBER() OVER (PARTITION BY customer_id ORDER BY order_ts), or a running total.

Windows preserve cardinality and are still blocking. They require the input sorted on (partition keys, order keys), and then make a single sequential pass.

The practical consequence is not obvious from the syntax: the cost driver is the number of distinct required orderings in the query, not the number of window functions.

• Ten window functions that share one PARTITION BY … ORDER BY cost one sort and one pass.
• Two window functions with incompatible specifications cost two sorts of the whole input.

That is the whole tuning story. It is why windows belong under "operators" and not under "algorithms".

The usual taxonomy (ranking, offsets, frames) describes the surface. The taxonomy that predicts cost is function × frame shape:

(w is the frame width, the number of rows in the window. A frame is the range of rows around the current row that the function sees, such as "the last 7 rows".)

Invertibility is the mechanism. A sliding SUM adds the row that enters the frame and subtracts the row that leaves. A sliding MAX cannot subtract: removing the current maximum tells you nothing about the new maximum. The missing inverse forces an auxiliary structure and turns O(1) into O(log w).

Small example. Sliding SUM over 3 rows on values 5, 2, 7, 4. First frame: 5+2+7 = 14. Slide: 14 − 5 + 4 = 13. Only two operations. For MAX: frame {5,2,7} has max 7. Slide: 5 leaves, 4 enters, and the max is still 7, but when 7 leaves later you would have to know the next largest. A monotonic deque (a queue that keeps only candidates that could still become the max) provides that.

One trap that is a real default: ROWS frames are positional and exact ("the previous 3 rows"). RANGE frames are value-based and must include all peer rows that have equal ordering values, so a tie makes the frame width depend on the data. The SQL default is RANGE, which is both the slower and the more surprising of the two.