Skip to content

Fuse the keyed top-k search with its binding join to meet the B20 insert bar (VV5d) #423

Closed

Description

@jsam

Part of epic #305. Follow-up to #327 (VV5): its top-k part keeps hnsw_nearest in deployed rules as a keyed view (inputlayer-symbolic PR 92), but does not meet the B20 candidate-insert bar yet.

Problem. The B20 candidate insert at 100,000 x 384-dim vectors and 10,000 query keys takes 13.5 ms p50 from write to delta, against a bar of 10 ms. Instrumented runs split one insert into the ack (~2.7 ms, as on main), the HNSW graph insert in the maintainer (~2.0 ms), the nearest operator's 10,000 exact distance checks (~0.6 ms) and the rest of the maintainer round (4-10 ms, against ~0.2 ms on main). Per-operator timely logging puts that rest in Differential Dataflow arrangement maintenance of the nearest view, the largest part being the operator's output arranged by query vector for the join with the atom that binds the query (nn(K, Id, D) <- qkey(K, QV), hnsw_nearest("idx", QV, k, Id, D)). A merge transient after the view build was tested and ruled out.

Target. The nearest operator keeps the binding atom's rows per query key and emits the joined rows itself, so the search and its binding join are one operator: no join, and none of its two arrangements, on the path of a candidate insert. Optionally, also take the graph insert off the critical path: searches overlay the round's pending index steps instead of waiting for them to be applied.

Acceptance. The nearest-view oracles (src/view_maintainer/nearest_tests.rs, src/storage_engine/maintained_nearest_tests.rs) pass unchanged; B20 candidate insert <= 10 ms p50 at 100,000 x 384-dim and 10,000 keys on the benchmark host through the perf slot, with delete refill and query-vector change no slower than with the separate join.

Size M. Dependencies #327 top-k part (inputlayer-symbolic PR 92). Order right after it.

Activity

  1. jsam commented on Oct 9, 2026

    @jsam
    ContributorAuthor

    Update: with #100 (a round advances only the dataflows its writes reach) on main, the B20 candidate insert at 100,000 x 384-dim and 10,000 keys is 5.4 / 5.2 ms p50 (two runs, perf slot, main 0e452a44 vs inputlayer-symbolic PR 92 head 7aa28758), under the 10 ms bar; delete refill 3.7 / 4.1 ms, query-vector change 5.0 / 5.1 ms. The bar no longer depends on this fusion. It would still remove the join's two arrangements (memory and per-round work), so it stays a candidate optimization rather than a blocker.

  2. jsam commented on Oct 10, 2026

    @jsam
    ContributorAuthor
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions