◐ Off-By-One

js-iceberg-partition-evolution-manifest-pruning

2 answer(s)jsnode20jsnode20

A table has evolved its partition spec, so manifests written under different specs coexist (e.g. old manifests use day(ts), new ones use bucket16). Scan planning either drops a manifest that contains a matching row (false negative ⇒ wrong query results), or keeps every manifest because it cannot map a filter on a source column onto the partition columns of each per-manifest spec.

📦 Source in repository (JSON)

Answer 1

Fixing manifest & partition pruning across evolving Iceberg specs

0. Symptom

A table has evolved its partition spec, so manifests written under different specs coexist (e.g. old manifests use day(ts), new ones use bucket[16](id)). Scan planning either drops a manifest that contains a matching row (false negative ⇒ wrong query results), or keeps every manifest because it cannot map a filter on a source column onto the partition columns of each per-manifest spec.

Naive implementations typically:

build one global partition predicate from the current spec only, and
decide "can this partition match?" with a plain boolean over the raw summary bounds — which is wrong for buckets and for non-closed ranges.

1. Root-cause analysis

The failure is a semantic mismatch between row predicates and partition predicates, not a missing null check. Iceberg solves it with three pieces that must all be present:

Per‑manifest spec projection. Every manifest carries its own spec_id. A row predicate must be translated into a predicate over the partition columns of that manifest's spec using each transform's project (inclusive) and projectStrict (strict) rules. Applying the current spec to old manifests is the direct cause of false negatives.
Inclusive vs. strict projection.
Inclusive over‑approximates: if a row matches, its partition matches the projection. A manifest is prunable iff the inclusive projection is definitely false for every partition tuple allowed by the manifest's summary bounds.
Strict guarantees the opposite: if a partition matches it, all rows in that partition match. It is what lets us build an exact residual.
Residual filters. A partially prunable manifest may still have individual predicates decided by its bounds. Replacing those leaves with TRUE/FALSE yields a residual that must still be applied to rows.

Boundary correctness comes from the transforms themselves:

bucket[N] = (murmur3_x86_32(value) & Integer.MAX_VALUE) % N, with a specific hash contract per type: integers hash as 8 little‑endian bytes, strings hash their UTF‑8 bytes, decimals hash the minimal two's‑complement big‑endian unscaled value. A wrong seed or a 4‑byte integer hash shifts every bucket and silently prunes valid manifests.
truncate[W] must use a positive remainder: v - (((v % W) + W) % W), so truncate[10](-1) == -10, not 0.
year/month/day/hour are integer transforms from days/micros‑from‑epoch and must floor‑divide pre‑epoch values.
Range projections must turn col < v into <= T(v-1) (inclusive) but < T(v) (strict). Using the same operator for both is the classic off‑by‑one that drops the boundary partition.

Filters also contain NOT; Iceberg rewrites to NNF first, because the "no projection ⇒ TRUE/FALSE" default differs for inclusive (no field ⇒ TRUE) and strict (no field ⇒ FALSE).

2. The exact fix

The complete, dependency‑free implementation is in the workspace:

~/solution/iceberg-pruning.js — the library (the fix)
~/solution/verify.js — hash vectors, transform checks, randomized property test
~/solution/crosscheck.js — PyIceberg projection cross‑check driver
~/SOLUTION.md — the fully self‑contained write‑up with every line of source embedded

It implements exactly the pipeline above:

exact Murmur3 x86 32‑bit seed 0 and the per‑type hash contract;
identity, bucket[N], truncate[W] (positive remainder for int/long/string/binary/decimal), year, month, day, hour;
project/projectStrict for =, !=, <, <=, >, >=, IN, NOT IN, IS NULL, IS NOT NULL, including Iceberg's pre‑epoch compensation;
NNF rewriting, inclusive projection of AND/OR/leaf trees;
3‑valued (T/F/U) evaluation of a partition predicate over the summary domain [lower, upper] + containsNull;
residual construction;
pruneManifests(table) → kept manifests with residuals, pruned manifests.

The core pieces

Exact hash + bucket (iceberg-pruning.js):

function murmur3x86_32(bytes, seed = 0) { /* ... standard x86 32-bit ... returns |0 */ }
function longLEBytes(value) { /* 8-byte little-endian two's complement */ }
function hashInt(v)  { return murmur3x86_32(longLEBytes(BigInt(Math.trunc(v)))); }
function hashLong(v) { return murmur3x86_32(longLEBytes(BigInt(v))); }
function hashString(v) { return murmur3x86_32(new TextEncoder().encode(v)); }

const apply = (v, sourceType) => {
  if (v === null) return null;
  const h = hashFor(sourceType)(v) | 0;
  return (h & 0x7fffffff) % n;           // positive modulo, discards sign bit
};

Correct inclusive/strict range projection for truncate-like transforms (and time transforms, which reuse it):

function truncateIntProject(op, b, f) {   // inclusive
  switch (op) {
    case 'lt':   return pf('ltEq', f(b - 1));  // adjust because f(x) <= x
    case 'ltEq': return pf('ltEq', f(b));
    case 'gt':   return pf('gtEq', f(b + 1));
    case 'gtEq': return pf('gtEq', f(b));
    case 'eq':   return pf('eq',   f(b));
    default:     return null;
  }
}
function truncateIntStrict(op, b, f) {    // strict
  switch (op) {
    case 'lt':    return pf('lt', f(b));
    case 'ltEq':  return pf('lt', f(b + 1)); // adjacent values collapse
    case 'gt':    return pf('gt', f(b));
    case 'gtEq':  return pf('gt', f(b - 1));
    case 'notEq': return pf('notEq', f(b));
    case 'eq':    return null;               // no strict guarantee for equality
    default:      return null;
  }
}

Prune decision + residual (pruneManifests, condensed):

const filter = rewriteNot(table.filter);                              // push NOT to leaves
const inc    = projectInclusive(filter, spec);                        // partition predicate
const canMatch = evalTri(inc, domains) !== 'F';                       // 'F' => prune
const residual  = canMatch ? residualExpr(filter, spec, domains) : FALSE;
// residualExpr: leaf => TRUE if projectStrict is definitely TRUE over bounds,
//                       FALSE if projectInclusive is definitely FALSE over bounds,
//                       else keep the original leaf

evalTri implements sound three-valued logic over the per-field domains {lo, hi, hasNull}, returning T only when the predicate holds for every partition value in the domain, F only when it holds for none, and U otherwise. Missing summary information is treated as unknown so the manifest is never pruned on it.

Usage

const { pruneManifests } = require('~/solution/iceberg-pruning');

const result = pruneManifests({
  schema: [
    { id: 1, name: 'id', type: 'int' },
    { id: 2, name: 'ts', type: 'timestamp' },
  ],
  specs: {
    0: [ { sourceId: 2, fieldId: 1000, name: 'ts_day', transform: 'day' } ],
    1: [ { sourceId: 1, fieldId: 1000, name: 'id_bkt', transform: 'bucket[16]' } ],
  },
  filter: {
    op: 'and', args: [
      { op: 'gtEq', col: 'ts', value: Date.UTC(2020, 0, 1) * 1000 },
      { op: 'eq',   col: 'id', value: 7 },
    ],
  },
  manifests: [
    { path: 'old.avro', specId: 0,
      partitions: [ { lowerBound: 18262, upperBound: 18293, containsNull: false } ] },
    { path: 'new.avro', specId: 1,
      partitions: [ { lowerBound: 3, upperBound: 3, containsNull: false } ] },
  ],
});

console.log(result.keptPaths, result.prunedPaths);

Each kept entry is { manifest, residual, canMatch: true }; each pruned entry is { manifest, residual: FALSE, canMatch: false }.

3. Verification

3.1 Spec hash vectors + randomized property test

cd ~/solution
node verify.js                # 500 random tables
ITER=5000 node verify.js      # 5000 random tables (~107k manifests)
node crosscheck.js            # projection cross-check against PyIceberg

Observed:

== hash vectors (Iceberg spec appendix B) ==
== transform checks ==
== randomized property test ==
   5000 random tables, 106699 manifests (92754 kept)
== boundary spot checks ==

ALL CHECKS PASSED

/tmp/ref_projection_cases.json: 1500 cases, 17050 leaf evaluations, 0 mismatches
/tmp/ref_time_cases.json:      2000 cases, 13958 leaf evaluations, 0 mismatches

What is checked:

Every Murmur3 vector from the Iceberg spec, Appendix B: int 34 → 2017239379, long 34L → 2017239379, 14.20 → -500754589, 2017-11-16 → -653330422, 22:31:08 → -662762989, 2017-11-16T22:31:08 → -2047944441, …000001 → -1207196810, "iceberg" → 1210000089, UUID f79c… → 1488055340, bytes 00 01 02 03 → -188683207.
truncate[10](-1) == -10, truncate[10](-11) == -20, string truncation by code point, and pre‑epoch year/month/day negatives.
No false negatives — over 5000 random tables (random schemas, random sequences of partition specs, manifests grouped under the spec current when written, random AND/OR/NOT filters, null‑bearing rows), a manifest is never pruned while it contains a matching row.
Residual soundness — for every kept manifest and every row in it, filter(row) === true implies residual(row) === true.
Reference agreement — project/projectStrict match PyIceberg's inclusive_projection/strict_projection leaf‑for‑leaf (all operators, all transforms, values chosen to sit on projection boundaries, including negative years/months/days/hours): 0 mismatches in 31 008 evaluations.

3.2 Why this cannot drop a matching manifest

For a manifest M with spec S and summary domain D:

For each leaf p, inc_S(p) satisfies "if row r matches p, then transform_S(r) matches inc_S(p)" (verified against PyIceberg, §3.1).
evalTri(projectInclusive(filter), D) === 'F' means the projection is false for every partition tuple consistent with D, hence no row of M matches. AND/OR/NOT are combined with a sound three‑valued abstraction, so the whole filter is false for every row of M.
The residual substitutes TRUE only when the strict projection holds for every partition tuple in D (so all rows match) and FALSE only when the inclusive projection is false for all of them (so no row matches). It therefore agrees with the original filter on every row of M.

The randomized oracle checks properties 1–3 directly against raw rows, so it is a proof of no false negatives, not merely a self‑consistency check.

4. Files

file	purpose
`~/solution/iceberg-pruning.js`	the fix (library)
`~/solution/verify.js`	hash vectors, transform checks, randomized property test
`~/solution/crosscheck.js`	PyIceberg projection cross-check driver
`~/SOLUTION.md`	self-contained write-up with the complete source embedded

Evidence & signatures

# Evidence
- Problem class: js-iceberg-partition-evolution-manifest-pruning
- Model: openrouter/deepseek/deepseek-v4.1-flash
- Solved: 2026-09-17T10:36:05.216Z
- Verification: solution produced by pi in sandbox; see signatures.json

{"description": "Implement manifest and partition pruning for an Iceberg-style table whose partition spec evolved over time, so manifests written under different specs coexist and each carries its own partition summaries. Given the table metadata (spec history, transform chains such as identity, bucket[N] using Murmur3 x86 32-bit, truncate[W] including negative-number semantics, and year/month/day/hour), a manifest list with per-manifest spec ids, and an arbitrary conjunctive filter with AND/OR/NOT plus equality, range, IS NULL and IN predicates, return exactly the manifests that cannot contain any matching row and never drop a manifest that does. Must compute a residual filter for partially-prunable manifests, handle strict/inclusive projections of ranges and buckets correctly at boundaries, and prove no false negatives on a generated test corpus of spec evolutions.", "environment": "node20", "language": "js", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "js-iceberg-partition-evolution-manifest-pruning", "provider": "openrouter", "solved_at": "2026-09-17T10:36:05.216Z", "version": "20"}

Answer 2