Skip to content

Approximate reverse mode for keyed top-k views above engine.vector_topk_keys (VV5c) #414

Closed

Description

@jsam

Part of epic #305. Split from #327 (VV5), whose top-k part keeps hnsw_nearest in deployed rules as a keyed view.

Problem. The keyed top-k operator of #327 (src/view_maintainer/nearest.rs) checks every inserted or moved candidate against every query key: O(keys) exact distances per candidate. That meets B20 (candidate insert <= 10 ms p50) at 10,000 keys, but the cost grows linearly with the number of query keys, so a deployment with many more keys (users, sessions, agents) pays it on every write to the indexed relation.

Target. Above engine.vector_topk_keys (default 10,000) query keys, an approximate reverse mode: the operator keeps an HNSW index of the query vectors themselves and, on a candidate insert or vector change, searches it with radius = the largest current k-th distance of any key, then checks exactly only the keys it returns (insertion with displacement as today). Below the threshold the exact O(keys) check stays. The mode switch is per operator, at a revision, with no change to the rows of keys whose neighbours do not change. Semantics and recall trade-off documented in vectors.mdx.

Acceptance. Oracle on random histories with more keys than the threshold: results never contain a row the index could not return, recall@10 against brute force >= 0.95 on embedding-like data, and results equal the exact mode's below the threshold; candidate insert with 100,000 keys at 1M x 384-dim <= 10 ms p50 on the benchmark host; engine.vector_topk_keys in the configuration docs.

Size M. Dependencies #327 (top-k operator). Order slot 9.

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