A pack build is a counting sort
We compile Wikidata — 120 million entities, 1.76 billion statements — into a memory-mapped knowledge pack. The classic way to build something like that is a chain of external sorts: sort every statement by subject, merge-join the labels, re-sort by object, join again, sort once more into the final layout. Touch every record eight or ten times. Shuffle terabytes through the disk. Wait half a day.
We kept asking a question that sounds naive: copying 200GB takes under an hour — why should restructuring it take twenty? The answer turned out to be that comparison sorting was never actually required. It was a habit.
Order can be computed instead of discovered
Our keys aren't arbitrary strings. They're integers in a known, nearly dense range. And for keys like that, math has had a better offer on the table forever: counting sort — two linear passes, zero comparisons.
Here's the observation that reframed the whole build: constructing a CSR graph layout is counting sort. The offsets array every CSR needs is exactly the prefix sum of a histogram. So:
- Pass one: stream the records, count edges per node. Cheap — it's just counts.
- Prefix-sum the counts. Now you know the final byte address of every single edge before writing anything.
- Pass two: stream again, write each edge straight into its final slot.
The data lands already in order. There is no "end sort" because nothing was ever out of order. Order was computed, not discovered.
The joins dissolve the same way
Those expensive sorts existed to join labels onto statements — a statement needs the names of the entities it mentions, and those live elsewhere in the dump. But lay the label table out addressably — entity number times slot size — and the join becomes a positional read. No sort. No merge. Just look at the address where the label has to be.
One comparison sort survives: the key dictionaries. But those are small — about 130 million keys, a couple gigabytes — and that sorts in RAM in seconds. Which gives us a rule we now apply across the whole pipeline:
Comparison-sort only what fits in RAM. Distribute everything that doesn't.
Sometimes you don't even need two passes
One step further, and it's my favorite part. The source dump is entity-ordered —
every entity's statements arrive together. So in plain arrival order, each node's
edges are already physically contiguous. Append them as they come, record each
node's (offset, length) in a compact addressing table, and the forward graph is
built in one pass, at parse speed. CSR never required globally sorted rows —
sortedness only bought us compressible offset arrays. An explicit addressing
table buys that back for about a gigabyte, and deletes an entire sorting phase
from existence.
None of this is exotic. Counting sort is undergraduate material. Log-structured storage and out-of-core graph systems have used these shapes for a decade. The lesson we keep relearning is quieter, and it's the one I'd put on a poster: when a pipeline feels slow, the biggest wins rarely come from making a phase faster. They come from noticing a phase never needed to exist.