Verifying a Backfill with Range Checksums Instead of Full Comparison

A backfill that rewrites nine million records and reports success has proved only that it ran to completion, which is a weaker claim than the one the resumable position tracking was built to support. Whether every record was transformed exactly once, with the right value, is a separate claim, and the cheapest way to support it is not to re-read both sides in full. It is to divide the keyspace into ranges, reduce each range to a short digest on both sides, and compare the digests. A mismatch says which range is wrong; agreement on every range is strong evidence that nothing was skipped, duplicated, or mis-transformed.

Why a per-row comparison is the wrong default

Comparing the old and new representation row by row is exact and expensive: it doubles the read volume of the backfill, and on a dataset that took hours to write, the verification pass takes hours of comparable I/O. More importantly, it produces output that is hard to act on. A row-level diff over nine million records yields either nothing or an unbounded list, and a list of four thousand mismatched primary keys is not a diagnosis; it is a starting point for one.

Range digests trade exactness for localisation and cost. Each side is scanned once and reduced to R digests, where R is the number of ranges. The comparison is then R comparisons of fixed-size values, and the result is either “all ranges agree” or “these specific ranges disagree”. The verification pass costs one additional full read rather than two, and it can be run incrementally: a range whose digest matches need not be examined again, while a mismatched range can be narrowed by splitting it.

The trade is that agreement of digests is not proof of agreement of contents. Two different multisets of rows can hash to the same digest, with probability governed by the digest width. A 128-bit digest makes accidental collision negligible for any realistic dataset size, and a 256-bit digest removes the concern from practical consideration. What the digest cannot detect at all is a transformation that was applied identically to both sides: comparing the old table to the new table finds nothing if the comparison reads the new table twice.

The digest must be order-independent

The natural way to compute a range digest is to concatenate the rows and hash the result. That is wrong for this purpose, because the two sides do not necessarily produce rows in the same order. The backfill may have written rows in key order while the verification scan reads them in index order; a table that has been compacted or reorganised may return them differently again. A concatenation hash over an unordered stream is a hash of the order, not of the contents, and it will report a mismatch for a range whose contents are identical.

The fix is to make the per-range digest a function of the multiset rather than the sequence. There are two standard constructions.

The first hashes each row independently and combines the results with an order-independent operator. XOR is the cheapest: digest = h(row_1) XOR h(row_2) XOR .... It is fully parallelisable and requires no buffering. Its weakness is that a row present an even number of times cancels out, so a duplicated record is invisible; for verification of a transformation that is supposed to be applied exactly once, that is a real gap. XOR also cannot distinguish a range with two rows from a range with zero rows if the two rows hash to the same value, which is the same cancellation in miniature.

The second sums the per-row hashes modulo a large integer, digest = sum(h(row_i)) mod 2^128. Addition, unlike XOR, is not self-inverse, so a duplicate shifts the sum rather than cancelling, and a missing row shifts it in the other direction. In fixed-width arithmetic the wrap is the modulus, which is harmless provided both sides compute it in the same width; summing into an arbitrary-precision numeric avoids the question entirely. Summation also gives a useful property that XOR lacks: the difference between two range digests is the sum of the differences of the individual rows, which means a mismatch is not merely detected but is arithmetically consistent with a set of missing and extra rows. In practice this does not localise to a specific key, since recovering which rows differ from a sum requires the candidate set, but it confirms the magnitude of the discrepancy.

-- Order-independent range digest: sum of per-row 60-bit hashes,
-- widened to numeric so a large range cannot overflow.
SELECT
  width_bucket(id, 0, 1000000, 64) AS rng,
  count(*)                          AS n,
  sum(('x' || substr(md5(canonical_row), 1, 15))::bit(60)::bigint::numeric) AS h
FROM transformed
GROUP BY 1 ORDER BY 1;

The count(*) alongside the digest is not redundant. Two ranges with the same digest but different row counts are a contradiction that no hash collision can explain, and the count is exact, free, and catches the most common failure: a range that was skipped entirely.

Choosing the range boundaries

Ranges should be defined on the same key the backfill used to page, and their boundaries should be fixed values rather than quantiles computed at verification time. If the boundary set is derived from the current data distribution, the two sides can be partitioned differently, since a row inserted between the two scans shifts the quantile boundaries, and the comparison then mixes rows across ranges. Fixed boundaries computed once, at the start of the migration, keep both sides partitioned identically for the duration.

The number of ranges sets the resolution of localisation and the cost of the comparison. A thousand ranges over nine million rows gives about nine thousand rows per range, which is a tractable amount to examine when a digest mismatches, and a thousand digest comparisons is a trivial amount of data to move. A hundred thousand ranges gives finer localisation and more comparison overhead, and the digest rows themselves become a table that needs its own storage and join.

Uniform ranges are the simplest choice and are wrong when the key distribution is skewed. A range defined by equal-width key intervals will contain almost everything if the key is monotonically increasing with time and the data is recent-heavy, and almost nothing in the older intervals. The result is a few enormous ranges that are expensive to examine and many empty ones that verify trivially. Ranges defined by key prefix or by hash of the key distribute more evenly, at the cost of making the range predicate a hash computation rather than a simple comparison, which matters because the predicate has to be applied to both sides identically.

Narrowing a mismatched range

A mismatch on a range of nine thousand rows is the point at which exact comparison becomes affordable. The procedure is a bisection: split the range at its midpoint key, compute digests for both halves on both sides, and recurse into the half that disagrees. With nine thousand rows, about fourteen splits reduce the range to a single row. The cost is logarithmic in the range size rather than linear, and the result is the specific key at which the two sides diverge.

That key is rarely the whole story. A divergence at one key in a range usually indicates a class of divergence: a data type that canonicalises differently, a null that was mapped to a default on one side and preserved on the other, a timestamp that lost its timezone in the transformation. The useful response is to look for the class rather than to fix the row, because the digest comparison will report the same mismatch on every range where the class appears.

Two systematic causes dominate. The first is canonicalisation: the two sides must serialise a row into bytes identically, which means a fixed column order, a fixed representation for nulls, a fixed precision for numerics, and a fixed timezone for timestamps. A digest computed over a timestamp on one side and a timestamptz on the other will mismatch everywhere, and the mismatch says nothing about the backfill. The second is the boundary condition itself: a range predicate written as id >= lo AND id < hi on one side and id > lo AND id <= hi on the other puts the boundary row in different ranges, producing two mismatches that are mirror images of each other.

What a digest comparison does not establish

The verification establishes that the transformed data, as read now, reduces to the same digests as the source data, as read now. It does not establish that the transformation is semantically correct: a backfill that writes a column into the wrong column consistently on both sides of a comparison passes trivially, because the comparison was never against an independent definition of correctness. It also does not establish that the source data was itself correct, and it does not catch a row that was deleted from both sides during the window.

Those are arguments for a small number of independently derived spot checks in addition to the digest comparison: a sample of rows checked against an expected value computed by a separate path. The digests cover coverage and consistency at scale; the spot checks cover semantics on a sample. Neither alone is a verification, and the combination is cheap enough that skipping either is hard to justify.

The final consideration is timing. Verification run once at the end of a backfill establishes a property of a moment. On a table that continues to receive writes, that moment passes immediately, and the state diverges again through normal operation, which is correct, since the write path is supposed to maintain the new representation. Verification is meaningful when it runs against a quiescent range or when the write path has already been switched to the new representation, and running it on a range that is actively being modified produces mismatches that reflect the window rather than the backfill. The sequence that makes this coherent is the one described in expand, migrate, contract, with verification as the gate between the migration and the contract step rather than as a step performed after everything is finished.