A Small Compiler for Explaining Delta Lake Pruning

The question behind the number

Explaining Delta Lake pruning sounds like a counting problem. Given a table and a WHERE predicate, how many files can be eliminated before the engine opens the table’s data files? Delta Lake answers that question through two metadata mechanisms: partition pruning drops whole directories from partition values declared in the transaction log; data skipping drops individual files from per-file min/max statistics carried in the same log.

For a user-facing tool, that number matters. It tells whether the physical layout and the predicate are doing useful work. But for a tool that claims to explain pruning, the harder problem is not the count. The harder problem is the chain of trust behind the count. Which expression was actually measured? Which parts of it were rewritten? Which fragments could be decided from partition values, which from file statistics, and which had to be left out? When a file survives, is that a proof that it may match, or only the consequence of an intentionally conservative approximation?

That is the problem delta-explain is built around. It is deliberately smaller than a query planner, but it still needs some of the same machinery: a predicate representation that all consumers share, a normalization pass whose rewrites preserve SQL semantics, a classifier that separates what different metadata domains can decide, and a measurement procedure that compares survivor sets across controlled scans of one snapshot.

The result is a small compiler pointed at an unusual target. It does not produce machine code, and it does not produce an execution plan. It produces a pruning explanation with bounded claims: exact where the input is concrete, conservative where the input is summarized, and incomplete where the predicate cannot be assigned safely.

This piece follows one predicate through that pipeline, then stops at the four design questions the walk raises: who owns the predicate’s representation; when a rewrite may be admitted; what conservatism actually is; and how to measure an optimizer from the outside.

Scope. This piece is about the design model and its reasons, not the tool in use. The companion piece, delta-explain: Making Delta Lake Pruning Visible, covers output format, worked examples, and CI gates. The documentation holds the contract and the reference material.

One predicate through the pipeline

The predicate we follow through the pipeline is deliberately the awkward form of a plain filter:

NOT (pickup_date != '2024-01-03' OR trip_distance <= 5)

It has the same meaning as pickup_date = '2024-01-03' AND trip_distance > 5, but it is written the way a generated query or a hurried refactor might write it. That makes it useful. It forces the tool through the whole chain: parse the SQL, import it into its own predicate representation, normalize it, classify it, lower it, and measure it. A simpler predicate would show the result, but not the machinery behind it.

Run against a real NYC-taxi table, with five daily pickup_date partitions and four files each, the predicate exists in five forms during a single invocation. The table is the fixture behind the validation repo, and every form quoted below is a real dump, not a reconstruction.¹

1. The owned AST, before normalization. The SQL parser first turns the WHERE string into its own source tree. delta-explain then imports that tree into its owned predicate AST. This is the representation used by the rest of the pipeline. Its vocabulary is deliberately narrower than SQL and closer to pruning itself: column-op-literal comparisons, junctions, null checks, IN, and BETWEEN. The tree has been translated out of the parser’s vocabulary into delta-explain’s own, but its logical shape is untouched. The NOT (... OR ...) the user wrote is still a NOT over an OR. Normalization, the first pass that changes shape, comes next:

rendered: NOT (pickup_date <> '2024-01-03' OR trip_distance <= 5)

Not(Or([
  Cmp { col: ColRef(["pickup_date"]),   op: Ne, lit: Str("2024-01-03") },
  Cmp { col: ColRef(["trip_distance"]), op: Le, lit: Number("5") },
]))

The literal is worth noticing. Number("5") is still the raw token, not a typed value. That is because the owned AST is built for reading and classification, not for evaluating the predicate against a table schema. Literal typing happens later, when the predicate is lowered into the form the kernel can evaluate.

2. The owned AST, normalized. The normalization pass now applies De Morgan’s law, pushes the negation to the leaves, and flips the comparison operators on the way:

rendered: pickup_date = '2024-01-03' AND trip_distance > 5

And([
  Cmp { col: ColRef(["pickup_date"]),   op: Eq, lit: Str("2024-01-03") },
  Cmp { col: ColRef(["trip_distance"]), op: Gt, lit: Number("5") },
])

Ne became Eq, Le became Gt, and Not and Or are gone from the tree entirely. This rewrite is sound but not neutral. Because it preserves SQL’s three-valued logic, it can never change which files survive. It can only change how the pruning is explained, for example by making one fragment visible to one phase and another fragment visible to another. That is the license normalization needs, and its limit.

3. The classification. Once the predicate has this shape, the analyzer can walk the normalized conjuncts and route each fragment by the metadata domain that can decide it. The four buckets are the vocabulary of that routing. partition_safe is for fragments decidable from partition values through the kernel. partition_exact is for fragments decidable from partition values but outside the kernel’s grammar. stats_safe is for fragments decidable from file statistics. unsplittable is for fragments that span domains or leave the pruning language altogether.

For this predicate, the classification is clean:

partition_safe:  Some("pickup_date = '2024-01-03'")
partition_exact: None
stats_safe:      Some("trip_distance > 5")
unsplittable:    None
confidence:      Conservative

A comparison on pickup_date, the partition column, can be used in the partition phase. A comparison on trip_distance, a non-partition column with file statistics, belongs to the statistics phase. Nothing has to be left aside. This classification is already a small explanation: it says which part of the predicate can be checked from partition values, which part can be checked from file statistics, and whether any fragment has fallen outside the pruning language.

4. The kernel predicates, one per phase scan. The classified fragments are then lowered into delta-kernel’s Predicate IR. The partition-only scan receives the partition-safe fragment. The full scan receives the predicate that the kernel can evaluate after normalization and after unsupported fragments have been stripped. This is the full-scan lowering:

Junction(JunctionPredicate { op: And, preds: [
  Binary(BinaryPredicate { op: Equal,
    left:  Column(ColumnName { path: ["pickup_date"] }),
    right: Literal(String("2024-01-03")) }),
  Binary(BinaryPredicate { op: GreaterThan,
    left:  Column(ColumnName { path: ["trip_distance"] }),
    right: Literal(Double(5.0)) }),
]})

The change in vocabulary is deliberate. Eq became Equal, Cmp became BinaryPredicate, and the literal that was Number("5") upstream is now Double(5.0), coerced against trip_distance’s schema type at lowering. The same schema-driven coercion is what lets a quoted '2024-01-01' compared to a DATE column prune as a date.

Both forms derive from the same owned tree, so the explanation the analyzer renders and the scan the kernel runs cannot silently refer to different predicates.

5. The survivor sets. The scans over one snapshot close the loop:

baseline:            20 files
partition-only scan: 4 files
full scan:           2 files

The first drop, from the baseline to the partition-only scan, eliminates 16 files and is credited to partition pruning. The second drop, from the partition-only scan to the full scan, eliminates 2 more files and is credited to data skipping. That day holds four files laid out by distance, and the two whose trip_distance max is <= 5 cannot match the predicate.

The measurement works by subtraction. Each scan adds one layer of predicate information to the previous scan. The difference between two adjacent survivor sets is the contribution of the layer that was added.

The same pipeline also shows what happens when the predicate leaves the pruning language. In UPPER(pickup_date) = '2024-01-03' AND trip_distance > 8, the UPPER(pickup_date) = '2024-01-03' fragment classifies as unsplittable and never reaches lowering. The dump says it in one line:

scan predicate after stripping unsupported fragments: trip_distance > 8

The unsupported fragment survives only in the report, as an UNSUPPORTED_EXPRESSION warning and a degraded confidence, while the kernel scans with what remains: 20 files to 7, on the same table. The result is not a failed explanation, but a bounded one. The tool reports the fragment it could measure, keeps the fragment it could not measure visible, and degrades the confidence instead of pretending that the whole predicate contributed to pruning.

The walk is complete: one string, five forms, two numbers. It is also a compressed list of design decisions. The same owned tree feeds several consumers. The first transformation rewrote the user’s predicate and needed a semantic license. One phase reasoned from concrete partition values while another reasoned from file statistics. And the two numbers came from metadata scans built for measurement rather than from an engine’s execution plan.

The four sections that follow explain those decisions one at a time.

Who owns the representation?

Every system that reads the same expression in more than one way faces the same choice: a shared representation with many consumers, or a private representation per consumer. Compilers settled this long ago in favor of a common IR, and not for elegance. Two representations of the same program do not usually fail loudly. They drift apart one bugfix at a time.

delta-explain is a small instance of that decision. sqlparser-rs parses the WHERE string and produces the parser’s source tree. delta-explain immediately converts that tree into its owned predicate AST, the vocabulary seen in the walk above. From that point on, every internal consumer reads the same owned tree.

That boundary matters because delta-kernel-rs, the Rust implementation of the Delta protocol, is the only door to the table. It replays the transaction log, checkpoint Parquet included, and runs the metadata scans. To ask the kernel a pruning question, delta-explain must lower its owned AST into the kernel’s Predicate IR. But the lowering is only one consumer. The analyzer reads the same owned AST and produces the classification shown in the report. The kernel bridge reads it and produces the predicates evaluated by the scans. The partition evaluator reads it again and decides what can be decided from partition literals when the kernel grammar cannot express the fragment. Three consumers, not three parsers.

That invariant is what makes the survivor-count arithmetic meaningful. Each path contributes a different part of the explanation: the analyzer names the fragments, the kernel scan produces the survivor sets, and the partition evaluator contributes exact decisions over partition literals. If those paths owned different predicate models, they could drift silently. The numbers would still look plausible, but the report could credit a fragment that was not exactly the one scanned or evaluated.

One shared tree prevents that class of error by construction. ADR 0001 records the decision: the parser’s own types are quarantined in a single conversion module, and every other consumer sees only the owned tree. No module gets to smuggle in a second, subtly different view of the predicate.

When is a rewrite admissible?

The second decision in the walk is the most consequential one: the tool rewrote the user’s predicate before measuring it. Optimizers do this constantly. Canonicalization is one of the first things a query planner does to a filter. It is also where planners sometimes go wrong quietly, because every rewrite is a claim that two expressions mean the same thing.

delta-explain follows a narrower rule: a rewrite may change how pruning is explained, but not which files survive. To make that safe, every admitted rewrite must preserve SQL’s three-valued semantics. De Morgan pushdown and small boolean simplifications are the routine cases. The instructive one is LIKE.

pickup_date LIKE '2024-01-0%' is not a comparison the kernel can lower. But when the pattern is a literal prefix, with no wildcards before the trailing % and no escapes, and the column is string-typed, it can be rewritten as a half-open range:

pickup_date >= '2024-01-0' AND pickup_date < '2024-01-1'

Under the same lexicographic code-point ordering the metadata evaluator uses for partition values and file statistics, every string with that prefix is at or above the lower bound, and no string with that prefix reaches the successor prefix. So the normalization pass turns the Like node into two comparisons before classification ever sees it:

== owned AST (before normalization) ==
rendered: pickup_date LIKE '2024-01-0%' AND trip_distance > 8
And([ Like { col: ColRef(["pickup_date"]), pattern: "2024-01-0%", negated: false }, ... ])

== owned AST (normalized) ==
rendered: pickup_date >= '2024-01-0' AND pickup_date < '2024-01-1' AND trip_distance > 8
And([ Cmp { col: ColRef(["pickup_date"]), op: Ge, lit: Str("2024-01-0") },
      Cmp { col: ColRef(["pickup_date"]), op: Lt, lit: Str("2024-01-1") }, ... ])

The gate is soundness, not convenience. The rewrite fires only on a string-typed column, because the successor step is a fact about string order, not about numbers or dates. Where it does fire, the result is inside the pruning language. On the taxi table, the LIKE form scans 20 to 20 to 7, identical to its hand-written range form. A construct is admitted only when the rewrite is provably equivalent to the original predicate. Everything else degrades. ADR 0005 records why LIKE is a first-class node in the shared AST, extended once in the normalization pass, rather than something special-cased outside it.

The same rule explains why the tool refuses broader normal forms. It does not normalize arbitrary predicates into CNF or DNF, the way a textbook transformation would. Those forms can change the shape of what the user wrote, and they can grow exponentially. The price of refusing is smaller than the risk: a top-level OR stays whole, and the measurement section returns to that cost.

Literal typing follows the same discipline. A quoted '2026-07-02' against a DATE column is coerced and can prune as a date. But a DECIMAL literal that exceeds the column’s scale is rejected rather than silently rounded, and an offset-bearing literal against a wall-clock TIMESTAMP_NTZ is rejected as ambiguous rather than silently normalized. This is not fussiness. A mistyped literal can reach the kernel as a type mismatch; the conservative result is to keep every file. On a date-partitioned table, that can turn an apparently selective predicate into a report with zero pruning, exactly where pruning matters most.

Where equivalence cannot be proven, the honest moves are refusal or degradation, never a guess.

Conservatism is a property of the domain

The walk left an asymmetry unexplained: partition pruning came out exact, while data skipping came out conservative, on the same predicate over the same table. The labels do not measure how carefully either mechanism is implemented. They follow from the kind of information each mechanism reasons from.

Data skipping evaluates the predicate over each file’s min/max statistics. This is abstract interpretation in miniature. A range like trip_distance: 1.86..3.75 is not the file’s data. It is a summary of values the file may contain. Evaluating trip_distance > 8 over that range therefore answers a different question from the user’s query. It does not ask whether a matching row exists. It asks whether a matching row can be ruled out.

When the summary proves that no row can match, the file can be dropped. That decision is a proof. When the summary still leaves a match possible, the file must survive. That decision is prudence, not evidence that a matching row is actually present. A file whose trip_distance range is 4..12 survives trip_distance = 5, even though it may contain no row where trip_distance is exactly 5. Over-approximation is the price of deciding from summaries. From min/max statistics alone, the tradeoff is unavoidable: keep every file that may match, and drop only files that cannot match.

Partition values live in a different domain. pickup_date = 2024-01-03 is not a summary of a file’s rows. For that partition column, it is the value every row in the file carries. Evaluation is concrete, so it can be exact. The partition_exact bucket exists to exploit that fact for fragments the kernel cannot express.

For example, pickup_date LIKE '%01-03%' is outside the kernel’s grammar and outside the prefix rewrite. A substring pattern is not a range. But against the partition literal '2024-01-03', the fragment is still decidable. The tool evaluates it itself, using the partition evaluator as a third interpreter over the shared AST.

That evaluator uses four outcomes: TRUE, FALSE, NULL, and UNKNOWN. TRUE keeps the file. FALSE and NULL drop it exactly, because the fragment is constant across the file and SQL keeps rows only when the predicate evaluates to true. UNKNOWN means something different: the evaluator does not know how to decide the fragment, so it keeps the file conservatively.

On the taxi table, pickup_date LIKE '%01-03%' AND trip_distance > 5 prunes 20 files to 4, then 4 to 2, the same as the equality form. The kernel could not have lowered the LIKE, but the partition evaluator could decide it from the literal partition value. ADR 0006 records the choice to grow this evaluator over the shared AST rather than reach for a second parser.

Read this way, the confidence labels stop being adjectives and become consequences. A phase whose inputs are concrete values is exact. A phase whose inputs are summaries is conservative. Incomplete marks the third case: part of the predicate could not be assigned safely to either domain, so its contribution cannot be separated. The report is not describing effort. It is describing domains.

Measuring an optimizer from outside

The last question is the one the tool exists for. An execution plan shows the fused result of pruning: one scan, one surviving file list, the elimination already folded in. To explain the result, a measurement has to un-fuse what the engine fuses, and the standard experimental move applies: hold everything constant, vary one input, difference the outcomes.

delta-explain’s version is three nested metadata scans over one snapshot: a baseline with no predicate, a partition-only scan with the partition fragments, and a full scan with everything the kernel can evaluate. Each scan adds constraints to the one before and removes none, so the survivor sets are nested. A file is eliminated at exactly one point along the chain, and the drop between adjacent scans is credited to the mechanism introduced at that point.

The single snapshot matters for the same reason a controlled experiment controls: every scan reads the same table state, so no concurrent commit can shift a count between measurements. And the measurement never touches what it measures at the data level. The kernel’s metadata path resolves the file list and the per-file statistics without opening a single table data file.² That is what makes the numbers engine-independent, and it also makes the cost of the analysis proportional to the log rather than to the data. The same replay carries each file’s raw statistics, so the verbose per-file view and the --assert-stats check read the exact scan that produced the counts. There is no second source to disagree with the first.

What cannot be measured is declared. A top-level OR that mixes partition and non-partition columns stays whole, which is the price of refusing CNF. It reaches the full scan and can still prune there: pickup_date = '2024-01-03' OR trip_distance > 30 still scans 20 to 6 on the taxi table. But the subtraction can no longer separate the mechanisms, so the phase and the run degrade to incomplete. The fragment costs the explanation, not necessarily the pruning.

Even then, the output keeps the boundary visible. A degraded phase line does not print the full predicate as if it all pruned. It shows the honored fragment and annotates what was stripped, trip_distance > 8 (+1 unsupported fragment, keeps all files), so the count and the predicate credited for it always agree.

Closing

Everything above serves one invariant: the survivor set is a superset of the files that contain matching rows. Rewrites may reshape fragments, classification may leave attribution incomplete, and unsupported constructs may drop out of the scan predicate, but every move errs in the same direction: keeping more files, never fewer. The full contract, including conservative survivor sets, degradation rules, exit codes, and the versioned JSON schema, is written down in docs/semantics.md. Survivor-set soundness is validated continuously by a differential harness in which Spark computes, per predicate, the files that actually contain matching rows.

A final note on method. None of the claims in this piece is verified by hand. A public repository, delta-explain-validation, re-checks all of them against the same taxi table: per-case expectations read from the JSON report; metamorphic invariants, such as equivalent predicates producing identical kept sets and degraded predicates keeping exactly what their stripped remainder keeps; an independent replay of the Delta log in plain Python that must reproduce the tool’s kept set file by file; the error contract; and the layer walk that regenerates the dumps quoted above. At the time of writing, the suite is green, and validate.py --layers reprints the end-to-end walk from the live binary.

For the tool in use, including output format, worked examples, and CI gates, see the companion piece: delta-explain: Making Delta Lake Pruning Visible.