Waystone trails

How KDBS records where a repeated query found its rows and replays those locations, without ever trusting them for a result.

A Waystone trail is a record of where a repeated query found its rows. When the same query runs again with the same arguments, KDBS reads those recorded locations directly instead of descending the primary-key tree again, across every table the query touched. A trail is advisory: every recorded location is checked against the row actually there, and any miss falls back to the normal path. Deleting every trail changes latency and nothing else.

The idea

A trail may replace a lookup. It may never replace a search.

A stale entry that points at the wrong row is easy to catch: the row’s primary key does not match. A stored set that is missing a row inserted since it was recorded cannot be caught, because there is no row to check. So a trail is only used for steps whose completeness comes from primary-key uniqueness, not from the trail: a primary-key equality, or a join step that probes the next table by primary key. A step that must search (a non-key predicate, a range, a scan, a Cabin or index probe, NOT IN, NOT EXISTS) always runs normally.

Terms

Pattern: the shape of a statement with its literals replaced, fingerprinted at parse time. WHERE id = 42 and WHERE id = ? share one pattern_id.
fetch_id: the pattern’s fingerprint with the SELECT list left out. Trails are keyed by it, so SELECT a ... and SELECT COUNT(*) ... over the same FROM ... WHERE share one trail. ANALYZE prints both ids; SHOW PATTERNS lists fetch_id.
Pattern instance: a pattern with its arguments bound, identified by (fetch_id, arg_hash).
Trail: for one pattern instance, the primary key, table, page, page epoch, slot and step number of every row the last execution touched, in execution order.
Waystone: the store of all trails, reached through the sys.patterns catalog table.

How it works

Recording

execution 1 of an instance   count it, record nothing
execution 2                  record the trail: one entry per row a lookup step touched
execution 3 and later        replay the trail, entry by entry

Only lookup-class steps are recorded.
A trail is one page: up to 253 entries of 32 bytes. A trail that would need more is not recorded at all. A truncated trail would look complete to its reader.
Recording again replaces the trail whole; it never merges.
Trails are addressed through a hash directory under each pattern. If two instances collide on one slot, the newer one displaces the older. A header check turns a collision into a miss, never a foreign trail.

Replaying

For each entry, in order, all of these must hold:

The key the step derives from the current execution equals the entry’s primary key. For a join step, the key comes from the current outer row.
The row at the recorded page and slot has that primary key, and the page belongs to the step’s table.
The page’s current epoch equals the recorded epoch. The epoch is a per-page counter that is bumped when the page’s rows move.
MVCC visibility is applied exactly as on the normal path. The trail chooses where to look, never what is visible.

If any check fails, that step alone takes the normal path: a primary-key descent on a B+ tree table, or a chain scan on an older heap table.

Example

Run against the sample tables. The third execution of each statement is served from its trail (replays=1):

kdbs> ANALYZE SELECT * FROM passengers WHERE id = 2
...
step 0 Lookup passengers opens=1 examined=1 matched=1 sel=100% pages=1
kdbs> ANALYZE SELECT * FROM passengers WHERE id = 2
...
step 0 Lookup passengers opens=1 examined=1 matched=1 sel=100% pages=1
kdbs> ANALYZE SELECT * FROM passengers WHERE id = 2
...
step 0 Lookup passengers opens=1 examined=1 matched=1 sel=100% pages=1 replays=1

A join replays every lookup step it recorded:

kdbs> ANALYZE SELECT p.name, t.seat FROM tickets AS t JOIN passengers AS p ON p.id = t.passenger_id WHERE t.id = 1
...
step 0 Lookup tickets AS t opens=1 examined=1 matched=1 sel=100% pages=1 replays=1
step 1 Probe passengers AS p opens=1 examined=1 matched=1 sel=100% pages=1 replays=1
kdbs> SHOW PATTERNS
patterns=2
fetch_id=0x9b8e7707127bd8d4 oid=1 origin=auto pinned=no class=1 uses=0 last_seen=0 waystone=root=145,depth=1
fetch_id=0x9f1042cfcddcf6d oid=2 origin=auto pinned=no class=3 uses=0 last_seen=0 waystone=root=147,depth=1

(... marks ANALYZE lines left out; the join’s output above is from its third execution.)

What it guarantees

A trail is never authoritative; it is the bottom rung of the trust ladder. It holds two engine invariants:

Advisory: deleting trails, wholly or in part, may cost performance and never changes a result.
Never authoritative: a trail chooses where to look, never what is visible.

The engine’s contract test compares replies byte for byte across five configurations: recording on, recording off, replay off, all trails deleted mid-run, and a deliberately corrupted trail whose entries point at valid slots holding different rows.

What it costs

One trail page per pattern instance that executes twice.
Recording and the replay attempt cost 7 to 9% of the server CPU of a point SELECT by primary key, for a lookup a descent already answers directly (measured at the engine’s BN work order; listed as a known gap).
Measured on an earlier engine (the bench/ tree at commit 1769487): replay was 26 to 34 times faster than a chain scan on a table with no primary-key index, and 3 to 7% slower than a descent on a B+ tree table. Every new table is a B+ tree table. The design’s main target is a join chain, where each replayed step saves a descent.

Durability

Trails are not logged. Every server start discards them: each pattern’s directory root is cleared and sys.access_stats is emptied after recovery. The engine cannot tell a crash from a clean stop, so every restart costs every trail. That costs replays, never results. Trails are otherwise never retired, decayed or evicted.

How to observe it

ANALYZE <select>: replays= on each step served from a trail, plus pattern_id and fetch_id.
SHOW PATTERNS, or SELECT * FROM sys.patterns: one row per registered pattern, with its directory root and depth. The uses and last_seen columns are reserved and always read 0; running a pattern writes its trail and nothing to its catalog row.

Configuration

Key	Default	Effect
`waystone_recording`	`on`	Whether a successful `SELECT` records its trail. Turning it off must not change any reply.
`waystone_replay`	`on`	Whether a `SELECT` may be served from a trail. The only Waystone setting that can produce a row, and it still cannot change one.

Limitations

Only lookup steps benefit. A search step is never replaced, and nothing prefetches for it.
A trail holds at most 253 rows; a larger execution is not recorded.
Trails do not survive a restart, and the pages of the previous run’s trails stay allocated (known gap).
On a multi-core instance, two cores recording into one directory slot at once can strand a trail and leak a page. Invariant 8 limits the damage to a lost replay (known gap).
A trail of a dropped table is not retired; it answers nothing.