Value-fetching prefix scans and longest_prefix_record fall off a cliff beyond the buffer pool (full 512 KiB frame reads on the walker path) #78

Summary

On stores that exceed the buffer pool, two read paths degrade by two orders of magnitude while plain point gets stay fast:

1. Bounded prefix scans that fetch values (tree.range().prefix(..), take 100) cost ~530–580 µs/op while a point get on the same store costs 1.6–2.0 µs. LMDB serves the identical scan in 1.8 µs (~300×).
2. longest_prefix_record is ~19× slower than binary-searching the same answer with tree.get() (130 µs vs 6.5–7.0 µs) on a 540 k-key chain index.

Both symptoms reproduce identically on main (36fb295) and on the PR #76 head (d42da83), so this is not a #76 regression — it looks like a shared property of the scan/LPM walker path.

Environment

• Apple M3 Pro, macOS 26.6, APFS SSD; single-threaded bench, bench profile, rustc 1.97.1
• TreeConfig::new(dir), Durability::Wal { sync: false }, buffer pool 512 frames (256 MiB), background checkpointer on
• Preload settled with an explicit checkpoint() barrier before timing

Reproduction shapes

Symptom 1 — prefix scan under cache pressure (training-dataset manifest shape):

• 2 M keys ds/laion/shard-{s:05}/sample-{i:08} (200 shards × 10 k), 24-byte packed values; on-disk store well above the 256 MiB pool
• Timed op: tree.range().prefix(b"ds/laion/shard-{s:05}/"), consume 100 entries, random shard per op
• Result: ~530–580 µs/op. Point get on the same store: 1.6–2.0 µs. RocksDB: 13.8 µs, SQLite: 16.5 µs, LMDB: 1.8 µs for the same scan under the same cache budget
• A 200 k-key variant of the same shape (fits the pool) scans in ~17 µs, so the cliff is cache-miss behavior, not per-entry cost

Symptom 2 — longest_prefix_record vs app-layer bisect (chained KV-cache index shape):

• 30 k chains, 4–32 levels each (~540 k keys), keys are hash-segment paths kv/llama70b/<h0>/<h1>/.../<hi> (9 bytes/level), 40-byte values; prefix-closed key set
• Timed op: longest stored prefix of a full-depth query (query extends a stored chain by 2 phantom levels; 80 % hit / 20 % miss mix)
• Native longest_prefix_record(query): 130 µs/op
• Binary search over the ~34 candidate depths using plain tree.get(query[..len]): 6.5–7.0 µs/op — ~5 point gets, each on the indexed read path
• At 2 k chains (~36 k keys, fits warm cache) both approaches cost ~5 µs, so the gap grows with blob count

Hypothesis

Point gets stay fast because they use the page-granular indexed read path (~18 KiB per cold read, per the README). The range/LPM walker appears to pin and read full 512 KiB blob frames on every cache miss instead, so any operation routed through the walker (bounded scans, delimiter-less range reads, longest_prefix_record) pays full-frame I/O and evicts the pool under pressure. bm_scan_full_blob_reads vs bm_read_page_hits during these workloads should confirm quickly.

Notably, delimiter rollup listings (scan_keys(..).delimiter(b'/'), take 20) stay excellent on the same stores (~220 ns), as do point gets and CAS — the cliff is specific to value-fetching scans and LPM.

Impact

• Any list/scan endpoint over a store larger than the buffer pool (manifest readers, restore-manifest scans) drops to ~2 kops/s single-threaded
• Until fixed, applications get strictly better chain-lookup latency by bisecting get() calls than by calling the native longest_prefix_record API, which defeats its purpose

Numbers (ns/op, 256 MiB pool, async WAL)

The cross-engine harness (benches/ai_meta.rs, shared engine adapters incl. LMDB/redb/PostgreSQL) is ready locally and will be contributed separately; happy to attach it to this issue meanwhile.