Set operators, pivots and recursion

Which bound on the answer bounds the state?

Set operators, DISTINCT, sort, and the bounded-answer trick

UNION ALL is concatenation: O(1) state, streaming, cardinality is the sum. It is the cheapest operator in SQL. UNION is UNION ALL followed by a dedup, so it is UNION ALL plus a pipeline breaker.

INTERSECT and EXCEPT are a semi-join and an anti-join over all columns, using null-equality (the grouping equality) instead of 3VL. This collapses two apparent topics into mechanisms already covered above.

An asymmetry worth flagging: UNION ALL is free, but INTERSECT ALL and EXCEPT ALL are not cheaper than their set versions. A multiset intersection takes the minimum of the two occurrence counts, and a multiset difference subtracts them. So the engine must count occurrences, not just test membership. The state is the same O(NDV), with different arithmetic. ALL removes a cost only for the operator that never needed to look at the other side.

DISTINCT is GROUP BY with no aggregates. It has the same NDV-sized state and the same escape through sortedness. Its special property, noted above, is that it emits early.

Top-N is the best example of the hypothesis every bound on the answer is a bound on the state. ORDER BY … LIMIT k means "sort, then cut". But the cut is known in advance, so the state shrinks from O(N) to a bounded heap (a structure that always lets you find and remove the smallest of its items) of size k. The saving is a factor N/k, often six orders of magnitude.

LIMIT without an order is the only operator here that reduces the work of its own input. After k rows are produced, a cancellation signal travels upstream and the scan stops. Every other operator can only reduce the work of what comes after it.

OFFSET m must produce and discard m rows, so the page at offset m costs O(m + k). Paging through the whole result costs O(N²/k) in total. Keyset pagination replaces the offset with a predicate on the sort key, so every page costs O(k):

-- Offset paging: page 50,000 still produces and throws away 1,000,000 rows.
SELECT * FROM orders ORDER BY order_ts, order_id LIMIT 20 OFFSET 1000000;

-- Keyset paging: continue after the last row of the previous page.
SELECT * FROM orders
WHERE (order_ts, order_id) > (:last_ts, :last_id)
ORDER BY order_ts, order_id LIMIT 20;

Keyset pagination needs a total order, so it needs a unique tiebreaker column (here order_id). It is the same move as everywhere in this section: a semantic restriction bought an algorithmic property.

Pivot, unpivot, unnest and generators

Unpivot turns k columns into k rows. Cardinality × k, O(1) state, streaming, cheap.

Pivot is more interesting, because its output schema depends on the data. A pivot turns the values of a column into column names. If the list of pivot values is not written in the query text, the engine cannot know the result's columns without first scanning the data. A dynamic pivot therefore needs a metadata pass before the compute pass. That is why most engines require the value list or reject dynamic pivot. It is early versus late binding (deciding the schema before or after seeing data) appearing inside a single operator. This is rare: pivot is the only operator whose output type is not known until the data is read.

Unnest (also called flatten) turns each array into one row per element. It multiplies the row count by the average array length and holds O(1) state. Its hazard is ordering: the fan-out happens before any filter on the elements, and it destroys the parent row's identity unless a key is carried along. "Unnest, then re-aggregate on the parent key" is a very common and very expensive shape. The data is exploded and then imploded.

Table functions and generators produce a cardinality that is a function of an argument, not of any table. generate_series(1, n) produces n rows from no input. The systems consequence is that there are no statistics to estimate from, unless the argument is a literal. That puts generators in the same blind-spot family as UDFs. They are also the standard tool to manufacture data to join against: salt ranges for skew splitting (Join algorithms), dense calendars for filling gaps, and densifying sparse dimensions.

Recursive queries: fixpoint, and the restriction that buys the optimization

A recursive CTE (common table expression, a named subquery that may refer to itself) is fixpoint iteration: apply the recursive term to what you have, add anything new, repeat until nothing new appears.

Example. Find all managers above an employee: start with the employee's direct manager, then add the manager's manager, and so on until there is no higher level.

Naive evaluation joins the entire accumulated result in every round. Rows that were already processed are reprocessed each time, so total work is quadratic in the number of iterations.

Semi-naive evaluation joins only the delta: the rows that were new in the previous round. A row that has already been joined cannot produce anything new. Total work becomes proportional to total output. On a graph of any size, this is the difference between minutes and hours.

Semi-naive evaluation is correct only if the recursive term is monotonic: it may only add rows. That is exactly why SQL forbids aggregation, outer joins and DISTINCT inside the recursive term in most engines. The restriction is not timid design. It is the precondition that makes semi-naive evaluation sound.

Termination is not guaranteed. A cycle in the graph produces rows forever, unless the query carries a visited-path array (expensive, because it grows with depth and must be compared for every row) or the engine imposes a recursion limit. Engines impose the limit. That is a fail-fast escape, and it is the one exception to the earlier statement that approximation is the only degradation mode: this is the single place where the engine simply stops with an error.

State is O(accumulated output). For a transitive closure (all pairs of nodes connected by a path) over a dense graph, that is O(V²) where V is the number of nodes. Transitive closure is the worst amplifier here: bounded input, quadratic output, and no streaming escape. Graph engines exist not because SQL cannot express traversal, but because SQL recursion has no frontier scheduling and no visited-set pruning as first-class concepts.

Case, resolvedConstructed case · Omar and Tarini at Shopsy

Four reports, none failed, all wrong

Omar brought four reports: a NOT IN that returned zero rows, a left join that lost orders, revenue that doubled after a join, and a query with a Python UDF that ran for six hours. Where it started: Relational operators →

Tarini goes through his four reports with the five questions.

NOT IN returned nothing. One NULL in blocked makes x NOT IN (…) UNKNOWN for every non-matching x. The engine needs the three-outcome mark join, and the answer is "nothing" by the rules of 3VL. She rewrites it with NOT EXISTS, which is a plain anti-join and gives the 39 million rows he expected (and runs faster).
Missing orders in the left join. His WHERE c.tier = 'gold' evaluated to UNKNOWN for every unmatched order, so the outer join behaved as an inner join. She moves the condition into ON.
Revenue doubled. The shipping table has two rows per order, so the join fanned out each order to two rows before SUM(amount). A granularity mismatch: the join produced rows at the parcel grain, the aggregate wanted the order grain. She aggregates the shipping table to one row per order first.
The 6-hour UDF. The Python predicate is a hole in the algebra. The optimizer guessed its cost and selectivity, so it built a plan on an invented number, and it called Python once per row. She rewrites the logic as built-in SQL expressions and, for the rest, switches to a vectorized UDF that handles thousands of rows per call. It runs in 9 minutes.

Omar adds the correctness checklist to his notes.