Skiplists to the rescue: how a niche data structure helped Antithesis beat BigQuery’s point-lookup problem

From book club curiosity to real-world fix

Skiplists used to be a curiosity — neat theory, cute diagrams, a rabid cult. So why did one suddenly become the linchpin of a production system? It has been reported that after a discussion in Phil Eaton’s Art of Multiprocessor Programming book club, engineers at Antithesis realized a generalization of skiplists was the missing piece for a gnarly performance problem they’d been wrestling with for years.

The emotional bit is obvious: a problem that looked intractable is suddenly manageable. Cue the head-scratch, then the grin. For years their fuzzer-generated testing runs produced a branching tree of timelines — parent pointers everywhere — and answering simple ancestor queries meant doing repeated point lookups. Those are cheap in OLTP databases. In Google BigQuery? Not so much. BigQuery is tuned for massive scans and parallel aggregation, not fetching one row at a time. The natural parent-walk turned into an O(depth) disaster.

Skiplist ideas, scaled up

So what did they do? It has been reported that Antithesis adapted skiplist ideas — think linked lists with “express lanes” — into a tree-friendly design (the blog calls it a skip-tree). Instead of walking parent pointers one step at a time, the structure provides probabilistic jump pointers that let you leap up the history in logarithmic-ish steps. The upshot: far fewer point lookups against BigQuery, and you can keep the bulk of the heavy log data where it belongs.

This is one of those satisfying tapes-into-wires moments: a decades-old academic trick translating into practical savings on modern analytic platforms. Who would’ve guessed a cult data structure would pay the rent? The story is a neat reminder — sometimes the right tool has been hiding in plain sight all along.

Sources: antithesis.com, Hacker News