Rift / Design

Key mode

A dump with its rows in another order is a different file to a line diff. rift --key compares records by key instead, reading both files once per pass and writing nothing to disk.

DESIGN.md describes this mode under "Key mode". The key mode guide shows how to run it.

Records and keys

--key names where the key is: a CSV column by number or header name (csv:1, csv:id), a field path in NDJSON (json:user.id), or a column of the COPY ... FROM stdin blocks of a pg_dump (copy:id). A record is one line, except in CSV, where a quoted field can hold line breaks. The record's bytes leave out the line terminator, so a change from \n to \r\n alone is not a change. Each key gets a 63-bit hash taken from xxh3 of its bytes.

Sources: crates/rift-core/src/keyed/mod.rs, KeySpec::from_str; crates/rift-core/src/keyed/read.rs, module docs and key_hash.

One pass, one range of key hashes

keyed::compare works in passes. Each pass owns a range of key hashes and reads A and B side by side, a window of each at the same relative position, so files in roughly the same order meet their keys close together. It skips every record whose key hash lies outside its range.

A record in the range goes into a hash table. If its key is not there, the record waits, bytes included, in an arena. When the same key turns up in the other file, Rift compares the two records byte by byte, marks the key as changed when they differ, and frees the waiting bytes for reuse. The table slot keeps only a 31-bit fingerprint of the key hash, in four bytes, to catch a third occurrence. The table is sized at 5/4 of the keys it expects and filled to 80%, which is 5 bytes per key. At the end of a pass, records still waiting are the removed keys (from A) and the added ones (from B), and the pass prints its changes in line order.

Memory follows the two halves. The tables come from the skeleton half. The read windows, the lists of records they hold and the waiting records come from the refine half. A record is compared and counted as unchanged only after its bytes match.

Sources: crates/rift-core/src/keyed/pass.rs, compare, read_pass, Pass::new, Pass::take, Pass::matched, fingerprint, emit; Sizes::new.

Running out of room

A fingerprint cannot say which keys lie above a new top of the range, so a full table cannot be thinned in place, the way the scan thins a sample. When a table or the waiting records outgrow the budget, the pass starts over on a narrower range, sized from how far it had read:

• A full table means the range held too many keys. Tables fill as the files are read, so the new range is the share the table should hold to the end, with a 10% margin.
• Full waiting records mean the files are far out of order. The range is at least halved, and later passes may not widen past 90% of it.

A pass that ends with its tables under 90% full widens the next one toward 90%, at most twofold. Each pass rereads both files. Nothing goes to a temporary file, so key mode needs no disk space and no cleanup, and its cost is time: one read of both files per pass.

Sources: pass.rs, compare (the Outcome::Overflow and Outcome::Done arms), narrowed, fill, scale.

More memory, fewer passes

The table's capacity is what the skeleton half holds at 4 bytes a slot, and the passes needed are about the key count divided by what the table holds. Doubling --mem doubles the keys per pass until one pass covers all of them; beyond that, more memory changes nothing.

On a 256 MiB pair from rift-gen --seed 7 --size 256M --profile shuffled --rows csv (3,350,294 records in A, 3,349,981 in B), rift --key csv:id --stats:

Every run reported the same 100,154 changed keys; the order of the lines differs between pass counts, since each pass prints its own changes, and sorted outputs are identical. Times are single runs with a warm page cache; three more runs at 8M took 2.00 to 2.68 s, and at 64M 0.39 to 0.53 s. Below 16 MiB of --mem one thread does all the work, which accounts for part of the jump from 16M to 8M. Measured 2026-11-07 on an Apple M1, 16 GiB, macOS 27.0.1.

DESIGN.md records the large case: the 10 GiB shuffled CSV pair at --mem 256M takes 6 passes and about 41 s on the M1 with files larger than the page cache, each pass at about the speed of the disk.

Sources: pass.rs, Pass::new, Pass::shards, threads, PARALLEL_REFINE.

Threads

The work is spread twice. A window is cut into chunks at line breaks, and every chunk is split into records on its own thread, assuming a record starts at its first byte and the parser is in the state the window started in. A chunk counts only if the one before it ended where it starts, in that state. A quoted line break at a cut, or a COPY header inside the window, makes the rest parse again; plain rows never do. Then the pass's range is split between shards, one per thread, by bits of the key hash the table does not use, and each shard has a table and waiting records of its own.

Sources: read.rs, module docs; pass.rs, shard.

Duplicate keys

Key mode needs each key once per file. A key that turns up a second time from the same file while its first record waits is a duplicate. A key whose fingerprint matches a key already matched is only a suspect: the matched key's bytes are gone, so the fingerprint might belong to another key. The next pass counts the suspects in their file, or, after the last pass, one more read does. A pass that piles up too many suspects stops and counts them at once.

Duplicates end the run with exit status 2 and the first five keys:

$ rift --key csv:id a.csv b.csv
rift: duplicate keys: 1

Since a suspect is settled one pass later, a duplicate can surface after the changes of its pass were printed. The command line then adds that "the changes printed above are incomplete and must be discarded".

Sources: pass.rs, Pass::duplicate, Pending, collect_dups, FEW; keyed/mod.rs, KeyError; crates/rift-cli/src/keyed.rs, incomplete.

Why not keep A's records whole

The plain way to compare by key is to partition both files by key hash and hold one side's records in a table. DESIGN.md measured that layout at about 28 times the memory per record on shuffled CSV, 138 bytes against 5 for an 81-byte row, and so about as many more passes. Holding only fingerprints of matched keys, and the bytes of records still waiting, is what keeps a pass at a few bytes per key.