Building Cardinal, Part 2: What a Query Plan Knows About Its Rows

Part one made a claim: whether a SQL model can repeat, drop, or miscount rows is a property of its structure, and you can prove it without data. This part is about how. It’s the most technical thing I’ll write in this series, and it’s also the part I’m least worried about being wrong, because almost none of it is mine. The theory is fifty years old.¹ Cardinal’s contribution is applying it to dbt projects, one plan operator at a time, and keeping a receipt for every step.

The facts

Cardinal hands each model’s compiled SQL to a planner and gets back a tree.² The leaves are table scans. Above them sit filters, projections, joins, aggregates, windows, and unions, and the root is the model’s output. The analysis walks that tree from the leaves up, and at every node it computes one record. The important fields:

Keys. Column sets no two rows agree on. An empty list means no key is known, and the rows are a bag.
Dependencies. Pairs of column sets where the left determines the right: for every row, the same order_id always comes with the same shipping_fee. A dependency is marked as an entity dependency when its left side is a real key carried up from somewhere, as opposed to the inputs of a computed expression. Only entity dependencies count as a column’s native grain.
Non-null columns. Proven by the SQL, such as by a where x = 1 or an inner join on x, or declared by a not_null test. The record remembers which.
Inclusion facts. Two kinds. A covers fact says every row of some upstream relation is still here, matched on these columns. A within fact says this node’s values in these columns all come from that relation. A scan has both for itself, trivially, and the interesting question is which survive.
Repeats. Per column, the nearest join below this node where that column’s rows got multiplied.
Status. Known, partial, or unknown, with a reason. This is the field that implements part one’s rule: when a key can’t be worked out, say why once and go quiet.

There’s more, for measures that don’t add and amounts whose unit varies by row, but those are later essays. The list above is enough to catch the double-counted shipping fee.

Two primitives

Every rule and every check is phrased in terms of two operations on a node’s facts.

The first is attribute closure: given a set of columns, which other columns do they determine, following the dependencies and keys transitively? This is Armstrong’s axioms, run until nothing changes.³ If order_id determines customer_id and customer_id determines region, then the closure of {order_id} includes region.

The second is the superkey test: is this set of columns a superkey, meaning does its closure contain some key? If so, no two rows agree on it.

That’s all. Closure says what a group of columns pins down. The superkey test says whether a group of columns pins down a row. “Can this GROUP BY hold two rows from the same order” is the superkey test with the grouping columns. “Does this join fan out” is the superkey test with the join columns, on each side. The constraint is written into the code’s description of itself: every rule and every check is phrased in those two. When a rule wants a third primitive, that’s the signal it’s wrong.

One rule per operator

The analyzer has one file per plan operator, which it did not always have. It started as a single file that grew until a refactor on November 7th split it apart.⁴ Here is what each rule does, roughly in the order the plan gets built.

Scan. The keys come from declarations: a unique test, a primary_key constraint, or meta.cardinal.grain. Each gets an evidence entry saying so. The scan covers itself and is within itself. If the relation is a model analyzed earlier, its finished facts are read from a summary rather than recomputed, which is most of why a full check takes a few hundred milliseconds. Each model is analyzed exactly once.

Filter. Keys survive, since dropping rows can’t create duplicates. Covers facts usually don’t, because a filter may drop rows, and that gets recorded as a possible row loss with the predicate text and its line. Two exceptions: a conjunct that’s true for every row, and a rank filter like row_number() = 1, which keeps exactly one row per partition and so keeps a covers fact on the partition columns. An equality filter proves its column non-null and adds a dependency, because every row now agrees on it.

Projection. Columns move to new positions or get dropped. A key survives if all its columns are copied through. A computed column depends on its inputs, but not as an entity.

Join. This is where most of the code lives. First, for each side, are the join columns a superkey of that side? If both, the join is one-to-one. If one, it’s many-to-one toward the unique side. If neither, it’s many-to-many, and that’s a finding on its own.⁵ The output’s keys follow: a many-to-one join keeps the many side’s keys, and a one-to-many join needs the union of both sides’ keys. Every column from the side that got repeated is marked with this join as its repeat site, so a sum three models downstream can point back here.

The join is also where rows get lost. An inner join keeps every row of one side only if every row has a match. Cardinal can prove that when the side’s join values are within some relation R and the other side covers R on the same columns. That’s exactly what a declared reference provides, and it’s why meta.cardinal.references exists. Without it, the loss is recorded and the covers fact is dropped.

Aggregate. The grouping columns become a key, with the GROUP BY as evidence. Each output column gets classified: a sum or count is a plain aggregate, an average or percentile is non-additive, a count(distinct …) remembers what it counted and per what, so a later sum of it can be checked for overlap.

Window. A row_number() over a partition makes the pair of partition and row number a key, no matter what the input was. That’s how a dedup CTE earns its uniqueness without a declaration.

Union. A fact holds on the output only if it holds on every branch. The one way a union keeps a key is a constant discriminator column with a different literal per branch, plus a key every branch shares.

Anything else. UNNEST, GROUPING SETS, a Python model: status becomes unknown, with the operator named as the reason, and nothing above it in the tree reports anything.

The shipping fee, traced

Here is part one’s error again, as the facts see it.

-- order_lines: one row per (order_id, line_id), joined from orders
select order_date, sum(line_amount) + sum(shipping_fee) as revenue
from {{ ref('order_lines') }}
group by order_date

In the upstream model, the scan of orders has key {order_id} and the entity dependency order_id → shipping_fee. The join to line items has order_id as a superkey on the orders side and not on the lines side, so it’s one-to-many, the output key is {order_id, line_id}, and shipping_fee gets a repeat site pointing at that join.

Downstream, the aggregate groups by order_date. The G001 check asks: can one group hold several rows of the same order? That’s the closure of {order_date}. It doesn’t contain order_id, so yes. And shipping_fee has a repeat site. So the sum counts the fee once per line, and the finding reports the group, the column’s native grain, and the join that caused it, in another file.

Two details I want to point out. The check never looked at the SQL text. It asked three questions of the facts. And it didn’t fire for sum(line_amount), because line_amount depends on {order_id, line_id}, which is the key of the rows being summed, so nothing repeats.

Every fact knows why

Each fact carries an evidence id into an arena kept per model. An entry is one of a small number of shapes: a declaration with its origin, a GROUP BY with its span, a join that kept a side with the cardinality and the columns, a row number with its partition, an upstream model’s finished chain, and so on. Facts the SQL proves by itself point at entry zero, which is the empty reason.

When a finding needs to explain itself, it walks the chain and prints it outermost first:

one-to-many join on order_id; key of shop.order_items from meta.cardinal.grain

This does two jobs. It makes every message say why rather than what, which is the difference between a finding someone fixes and one they suppress. And it makes the assumptions visible. Declared facts are the only things in the whole analysis taken on trust, and because every proof traces back to them, Cardinal can list them: every key, non-null column, and reference a run relied on, and whether a dbt test actually checks it. The proofs are only as good as the declarations, and the tool knows exactly which declarations it leaned on.

Nulls, and erring toward silence

Everything above has to stay sound when a value is null, and SQL makes that annoying. Two choices worth spelling out.

Inclusion facts compare values null-safely, as IS NOT DISTINCT FROM, which is what keeps every rule correct under projection. And keys come in two strengths: a plain key, and a key that holds only among rows whose columns are non-null. An outer join creates the second kind, because every unmatched row is filled with nulls on one side. So does a dbt unique test, which ignores nulls.⁶ Since an equality join never matches a null anyway, a null-exempt key is enough to prove a join side unique, and that’s what lets a left join to a table with a unique test still count as many-to-one.

Where the analysis can’t decide, it decides nothing. Caps on how many keys and dependencies a node tracks exist so a wide, strange model gets a partial status rather than a slow run. I’d rather miss a finding than report one I can’t prove, and this walk is built so that every finding it does report comes with the chain of facts that made it.

Next: the keys the project doesn’t declare. How Cardinal guesses them from column names and join patterns, why it refuses to use a guess until dbt has tested it, and what the coverage command does with the leftovers.

Functional dependencies and keys come from Codd’s relational model and the normalization work that followed in the early 1970s. The Wikipedia entry on functional dependency is a fine summary. ↩
Apache DataFusion’s SQL front end produces a LogicalPlan. Cardinal takes the plan straight from the SQL-to-relational step and never runs the optimizer, so the tree it walks matches the SQL the author wrote and spans point at the right lines. ↩
Armstrong’s axioms: reflexivity, augmentation, and transitivity. Attribute closure is the fixpoint you get by applying them until the set stops growing. ↩
The commit is “Split grain’s analyze.rs into one file per plan operator.” Same week: “Read SQL text with one lexer instead of five scanners,” which is as honest a commit message as I’ve written. ↩
G003: many-to-many join. Joins with no equality columns at all, such as a date spine crossed with customers, are left alone, since those are nearly always deliberate. ↩
dbt’s generic unique test filters out nulls before checking for duplicates, so passing it says nothing about rows where the column is null. ↩