Stream L0 index metadata instead of collecting and sorting

perfloop/neon · INEFFICIENT ALGORITHM

https://perfloop.ai/t/oss/case_bn7ej53pyt

Verdict

VERIFIED · settled 2026-08-25 · pull request opened as neondatabase/neon#12937

What happened: The paired measurements met the required improvement.

Hypothesis

A static source trace of `compact_level0_phase1` found that every selected layer calls `index_entries`, each returned vector is extended into `all_keys`, and the aggregate is globally `sort_by_key` before it is retained for `all_keys_iter` during output writing. The direct-callee source check of `DeltaLayerInner::index_entries` showed a forward visit of the entire on-disk B-tree into a `Vec<DeltaEntry>` per layer. The target’s own cancellation comment documents benchmark-scale layers of roughly a million keys, so N is the total key/LSN-entry cardinality across a selected contiguous L0 batch; the byte selection cap does not make N a small constant. A separate source check showed the value side already uses a heap-based `MergeIterator`, making an ordered index cursor a plausible way to preserve the metadata consumers rather than treating that work as unused. The sort comment notes that sorted subranges are fast, so this does not assume worst-case sort behavior or claim an end-to-end bottleneck. No runtime CPU, allocation, or latency measurement was run; the possible saving is the batch-wide metadata materialization and sort, at the real cadence of one background `compaction_loop` L0 batch whenever the threshold is met. Confirm with a reproducible L0-compaction benchmark sweeping both selected-layer count and entries per layer through the documented million-key scale, comparing elapsed phase time (including the emitted `read_lock_held_key_sort_micros` field), allocation bytes/peak RSS, and a CPU profile attributed to index collection/sorting. Also differentially verify identical compacted values, hole choices, duplicate-LSN splits, and output layer descriptors.

Change to test: For each threshold-triggered background L0 compaction batch, replace the batch-wide `all_keys` collection and `sort_by_key` with a bounded k-way cursor over the selected delta-layer B-tree indexes. Feed the existing hole selection and key-size/duplicate-LSN boundary decisions from that ordered cursor while the value merge writes output, preserving hole ranking, duplicate-key splits, and output-layer layout without retaining every `DeltaEntry` for the whole batch.

Where it lives

perfloop/neon · pageserver/src/tenant/tasks.rs

Evidence

10-layer by one-million-entry threshold-triggered L0 compaction · 10 sample pairs

metric baseline candidate paired median change confidence range required result
l0_compaction_10x1m_peak_rss_kib 1006058 356266 −65.1% (−654704) −661644 to −629928 < −50303 PASSED
l0_compaction_10x1m_allocation_bytes 9474019017 6858165093 −27.6% (−2615954012) −2616337480 to −2615204152 ≤ 0 PASSED

10-layer by one-million-entry reverse-disjoint threshold-triggered L0 compaction, three-run median · 10 sample pairs

metric baseline candidate paired median change confidence range required result
l0_compaction_10x1m_reverse_peak_rss_kib 1047086 517714 −50.8% (−532432) −536996 to −516936 < −52354 PASSED
l0_compaction_10x1m_reverse_elapsed_micros 7681058 7078668 −8.1% (−623724) −717273 to −564400 ≤ 384053 PASSED
l0_compaction_10x1m_reverse_allocation_bytes 7845010135 6404967625 −18.4% (−1440058530) −1441691490 to −1439158064 ≤ 0 PASSED
l0_compaction_10x1m_reverse_index_metadata_micros 1020177 861711 −15.5% (−158428) −173359 to −146542 < −51009 PASSED

CPU-sampled 10-layer by one-million-entry L0 compaction · 10 sample pairs

metric baseline candidate paired median change confidence range required result
l0_compaction_10x1m_profiled_phase_cpu_millis 8050 7950 −1.2% (−100) −500 to +200 ≤ 402.5 PASSED

Checks: 1 of 1 passed. Verification: no defect found.

Timeline