Wide Values projections restart property searches for every field

perfloop-oss/helix-db · Inefficient Algorithm

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

Verdict

VERIFIED · settled 2026-11-14 · pull request opened as HelixDB/helix-db#1299

What happened: The paired measurements met the required improvement.

Hypothesis

Values projections repeatedly search each stored record's field names even though its bytes and validation are already cached. Selecting many fields from a wide record can repeat most of the same name comparisons. The repeated work is measured in a controlled fixture; representative record widths, selection counts and complete-query CPU savings remain unknown.

ExecutionContext::project_values loops over every selected name for each row. row_property and element_property ultimately use view::Row::value, defined at crates/db/src/encoding/v2/values/property/view/mod.rs:175-184. Each call starts a fresh linear search of the archived property vector. For R successfully evaluated rows, K flat stored selections and P stored properties per row, this lookup component can perform O(R*K*P) name comparisons. Actual work depends on matching positions and missing names; errors can stop it early. The per-batch record cache removes repeated reads and validation, not these searches.

Measurement receipt call_Oqq4P3MyJrFXyJzwibat59oY, output:1, retains the successful provisional command `cargo test -p db --lib perfloop_projection_probe -- --nocapture --test-threads=1`. Sixteen directly seeded records each contained 256 flat fields in controlled order. Selecting the final 1, 4 or 16 fields produced respectively 4,096, 16,288 or 63,616 name comparisons, while each query used the same 16 multi-get keys and no individual raw gets. All returned values were asserted. The fixture controls stored order to expose the mechanism; it does not establish typical write order, consumer width or latency.

The larger storage-read and full-row-decoding improvements are already implemented in https://github.com/HelixDB/helix-db/commit/0ca91214744ceb6c1a512349b4386ad19f2ef322 and https://github.com/HelixDB/helix-db/commit/8ededbd4feea640ec5e4ee69d9d5a7a35c65fd31. The proposed delta is shared name resolution inside the existing validated record representation. It needs no stored-format or public query-API change. Current open PRs did not show this lookup change; the inspected overlapping encoding PR https://github.com/HelixDB/helix-db/pull/1068 concerns numeric index strings. Discord discussion could not be searched through the blocked public entry point, so that coverage remains unknown.

The smallest useful Case check is a provisional multi-name lookup comparator followed by complete native Values execution, including setup, validation and result-object allocation. Optional samples can vary row count, stored width, selected-field count and early versus late matches. Compare a one-field control to catch index-building overhead, and preserve first stored-name wins and exact dotted-name precedence. Reduced name comparisons establish the local delta; only consumer-level CPU and allocation measurements can establish a worthwhile gain.

Change to test: Resolve selected stored fields together, or construct a bounded first-name lookup once per cached record, so wide projections do not restart the property scan for every field. Retain a cheap single-field path and preserve name precedence, missing-field omission and validation behavior.

Where it lives

perfloop-oss/helix-db · crates/db/src/execution/interpreter/stream/projection/dispatch.rs

Evidence

Eight-field Values on property rows · 30 sample pairs

metric baseline candidate paired median change confidence range required result
cpu_ns/op 16500000 13750000 −15.2% (−2500000) −3500000 to −1000000 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
ns/op 17075029 14318908 −15.1% (−2581466) −3746665 to −1512798 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 110075 110077 +2 +1.4 to +2.6 loss ≤ 0.05 × |baseline median| PASSED
B/op 14269824 14270400 +576 +281.6 to +870.4 loss ≤ 0.05 × |baseline median| PASSED
peak_rss_bytes 81829888 82323456 +276480 −1425408 to +1339392 loss ≤ 0.05 × |baseline median| PASSED

Late sixteen-field Values on wide rows · 11 sample pairs

metric baseline candidate paired median change confidence range required result
cpu_ns/op 1800000 800000 −55.6% (−1000000) −1500000 to −600000 loss ≤ 0.05 × |baseline median| PASSED
ns/op 1876380 850747 −54.1% (−1014991) −1411599 to −730225 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 4661 4663 +2 +2 to +2 loss ≤ 0.05 × |baseline median| PASSED
B/op 830616 831720 +0.1% (+1104) +1104 to +1104 loss ≤ 0.05 × |baseline median| PASSED
peak_rss_bytes 59424768 59850752 +409600 −1753088 to +2179072 loss ≤ 0.05 × |baseline median| PASSED

Eight-field Values on reopened property rows · 26 sample pairs

metric baseline candidate paired median change confidence range required result
cpu_ns/op 37250000 35000000 −2500000 −3500000 to +1500000 loss ≤ 0.05 × |baseline median| PASSED
ns/op 38208657 36300111 −2611412 −3695415 to +1491238 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 211413 211415 +2 −4.6 to +9.2 loss ≤ 0.05 × |baseline median| PASSED
B/op 40006730 40007158 +576 −2662 to +4109 loss ≤ 0.05 × |baseline median| PASSED
peak_rss_bytes 103915520 104448000 +133120 −1167360 to +3407872 loss ≤ 0.05 × |baseline median| PASSED

One-field Values on property rows · 101 sample pairs

metric baseline candidate paired median change confidence range required result
cpu_ns/op 10300000 10300000 −100000 −600000 to +400000 loss ≤ 0.05 × |baseline median| PASSED
ns/op 10614797 10698344 −98016 −677031 to +392448 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 66019 66019 0 0 to +0.6 loss ≤ 0.05 × |baseline median| PASSED
B/op 12904440 12904472 +32 +32 to +326.4 loss ≤ 0.05 × |baseline median| PASSED
peak_rss_bytes 81825792 82026496 +143360 −466944 to +942080 loss ≤ 0.05 × |baseline median| PASSED

Four-field Values on one search-result row · 1040 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 2865 2967 +4% (+115.6) +85.27 to +142 loss ≤ 0.05 × |baseline median| PASSED

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

Timeline