Bags, NULLs and the operator lattice

Where do silent wrong answers start?

The five questions that give any operator's cost profile

This article is not about what operators compute. It is about what each one forces the engine to do. That is captured by five questions. Ask them of any operator and you know its cost profile before you choose an algorithm:

1. Multiplicity. What does it do to the row count, and by what factor?
2. State. What must it remember, and which parameter sizes that memory: N (all rows), NDV (distinct values), k (a limit), or a frame width?
3. Requires. Which property must its input already have: order, partitioning, distinctness, completeness?
4. Provides or destroys. Does the output still carry the order or partitioning that the input had?
5. Equality and NULLs. Which of SQL's two equalities does it use, and where does three-valued logic change the answer?

The fifth question looks like trivia and is not. It is where silent wrong answers come from. It is the only part of this mechanism where the failure is invisible instead of slow.

---

SQL is bag algebra, not set algebra

One fact must be fixed first, because it silently sets the cost of everything below. In textbook relational algebra, a set has no duplicates, so the projection operator π (choose some columns) also removes duplicates. That would make projection a blocking operator.

SQL works on bags (also called multisets): collections where the same row may appear many times. SELECT a, b FROM t does not remove duplicates. So projection holds O(1) state and streams. Duplicates are kept by default; removing them is done only on request (DISTINCT). This choice keeps the most frequently used operator of the language non-blocking.

Every place where SQL does fall back to set semantics (UNION, INTERSECT, EXCEPT, DISTINCT) you will find a blocking operator. That is not a coincidence.

---

The lattice: one table for all operators

(Words used above: a semi-join keeps rows of the left table that have at least one match on the right. An anti-join keeps rows with no match. An outer join keeps all rows of one side and pads missing matches with NULLs. A window function computes a value per row from a group of related rows, such as a running total. These are all explained below.)

Read the last two columns together and an important correction appears: "blocking" mixes two independent properties.

• State proportional to the input.
• Inability to emit the first output row early.

DISTINCT has the first without the second. It holds O(NDV) state, but it streams its output from the first row, because a value can be emitted the moment it is first seen. Top-N has the second without the first. It holds only O(k) state, but nothing can be emitted until the last input row is seen, because that row might belong in the top k. Sort has both. Filter has neither.

Treating these as one dial is the standard mistake. It happens because the common cases move together. Two separate dimensions were collapsed into one.

---

SQL has two equalities

SQL has three-valued logic (3VL): a condition can be TRUE, FALSE or UNKNOWN. Comparing with NULL gives UNKNOWN. NULL = NULL is UNKNOWN (not TRUE), and WHERE keeps only rows whose condition is TRUE.

So SQL has two kinds of equality:

• Comparison equality (=) is three-valued. NULL = NULL is UNKNOWN. Joins use this one.
• Grouping equality (written IS NOT DISTINCT FROM) is two-valued and treats two NULLs as equal. GROUP BY, DISTINCT and the set operators use this one.

Small example. Two customers have city = NULL. GROUP BY city puts both into one group (the NULL group). But a JOIN b ON a.city = b.city never matches them with each other.

Three consequences are systems facts, not language trivia:

1. The hash-table key comparator for a join and for a group-by are genuinely different functions. A row whose join key is NULL can be dropped from both inputs of an inner join before it is ever hashed. This is a free filter, and group-by has no equivalent.
2. σ_p(R) ∪ σ_¬p(R) ≠ R whenever p can be UNKNOWN. (In words: "rows where p is true, plus rows where p is false" is not all rows, because rows where p is UNKNOWN are in neither branch.) This forbids splitting a scan into two complementary branches and joining them with a union. It would be an attractive plan shape, and it is simply unavailable.
3. Aggregates skip NULLs. SUM over an empty set is NULL, not 0. COUNT(*) counts rows while COUNT(x) counts the rows where x is not NULL. Because of the empty-set rule, partial aggregation must carry "I saw nothing" as a distinct state, not as a zero. Otherwise combining partial results would turn NULL into 0.

---

Filter and projection: the operators that pay for everything else

A filter holds O(1) state and reduces the row count by its selectivity s. Its own cost hardly matters. Its value is that every operator after it sees only s×N rows. Selectivities multiply along a plan, so where a filter sits matters more than how it is implemented. (Choosing where to place it is the optimizer's problem, not ours.)

Two more points belong here.

Independence is assumed and usually false. To estimate city = 'Pune' AND state = 'Maharashtra', an optimizer multiplies the two selectivities: s₁·s₂. But every row in Pune is also in Maharashtra, so the true selectivity is s₁. The estimate is too small, perhaps by a factor of 30. This is the uniformity-and-independence assumption entering this mechanism directly, and it is the origin of most catastrophic plan choices (why estimation errors multiply).

A WHERE clause containing a subquery is not a filter. x IN (SELECT …) is a semi-join, and x NOT IN (SELECT …) is a null-aware anti-join. The syntax makes them look like the cheapest operator class in the language. The cost model puts them in the most expensive class.

Projection keeps the row count but changes the row width, and width is what everything after it must move. In a columnar engine (one that stores each column separately), dropping a column at scan time is free, because the column is never read. In a row engine the bytes were read anyway, and the projection only narrows what is copied forward. Projection is also where computed expressions live, and therefore where user-defined functions enter the plan.

---

Scalar UDFs: the operator that revokes the founding assumption

This mechanism is built on the fact that a query is a pure function of an immutable snapshot. That fact allows reordering, re-execution, caching and speculation. A user-defined function (UDF) (here: a function written by the user, such as Python code called per row) is opaque to all of it: its cost is unknown, its selectivity is unknown, it may be non-deterministic, and it may have side effects.

Four consequences follow:

1. It blocks pushdown. A predicate that contains a UDF cannot be moved below anything unless the optimizer can prove that is safe.
2. The cost model is fabricated. The optimizer substitutes a constant for the UDF's cost and selectivity. That constant is routinely wrong by three orders of magnitude (1,000×). A plan built around a UDF predicate is built on an invented number.
3. Fixed cost per call. A row-at-a-time call that crosses a language boundary (for example from the engine into Python) pays a fixed serialization cost per row. This is fixed cost per operation sets a natural batch size exactly. The reason vectorized UDFs (for example, Arrow-based) exist is to pass thousands of rows per call so that the fixed cost is shared.
4. Non-determinism breaks retries. A non-deterministic UDF (say, one that calls random() or reads a clock) forbids common subexpression elimination (computing a repeated expression once) and forbids re-execution. This collides head-on with the retry freedom that this whole mechanism assumes.