The k-NN Query Path

A knn query is a _search request, so it rides the same query-then-fetch scatter-gather you already know from Search Execution: the coordinating node fans out to shards, each shard returns its local top-k, the coordinator reduces to a global top-k, then fetches _source for the winners. What makes k-NN different is what happens inside the query phase on each shard — a KNNQuery that, depending on the engine, either calls down into native faiss/nmslib across JNI or runs Lucene's own KnnFloatVectorQuery. And what makes it interesting is the pile of variations layered on top: approximate vs exact (script-score fallback), filtered k-NN, radial search, and rescoring after quantized retrieval.

This chapter traces one knn query from REST down to the per-segment search and back up through the coordinator reduce, with a grep target at every hop so you can find the real classes in your checkout. It assumes architecture, engines, algorithms, and native integration; it leans on Search Execution for the fan-out it does not re-derive.

After this chapter you can:

• Name every class a knn query passes through, from KNNQueryBuilder to KNNScorer, and find each in source.
• Explain the two-phase k-NN fan-out and why k-NN's per-shard "top-k" interacts awkwardly with size and pagination.
• Distinguish approximate ANN, exact (script_score) k-NN, filtered k-NN (pre- vs post-filtering / "efficient filtering"), and radial search.
• Explain rescoring: why quantized retrieval needs a full-precision second pass and where it runs.

Note on terminology: the cluster manager (formerly master) owns cluster state and the model system index; it is off the query hot path. k-NN search is a per-shard, per-segment, data-node concern coordinated by the same coordinating node as any _search.

The cast — classes on the k-NN query path

# Orient in the query package of a k-NN checkout:
ls src/main/java/org/opensearch/knn/index/query
grep -rln "class KNNQueryBuilder\|class KNNQuery\b\|class KNNWeight\|class KNNScorer\|KNNQueryFactory" \
  src/main/java/org/opensearch/knn/index/query

Hop 0 — the REST request

A k-NN search is an ordinary _search with a knn query clause. The minimum is a field, a query vector, and k:

curl -XPOST 'localhost:9200/products/_search?pretty' -H 'Content-Type: application/json' -d '
{
  "size": 10,
  "query": {
    "knn": {
      "embedding": {
        "vector": [0.12, 0.88, /* ... dimension floats ... */ 0.45],
        "k": 10
      }
    }
  }
}'

k is "how many neighbours each shard's ANN search should return," not the same as top-level size — a distinction that bites people (see Common bugs). The clause is registered as a query and parsed into a KNNQueryBuilder.

grep -rn "registerQuery\|knn\"\|NAME\|fromXContent\|KNNQueryBuilder" \
  src/main/java/org/opensearch/knn/plugin/KNNPlugin.java \
  src/main/java/org/opensearch/knn/index/query/KNNQueryBuilder.java

Hop 1 — KNNQueryBuilder → KNNQuery

KNNQueryBuilder is the QueryBuilder for the clause: it holds the field name, the query vector, k, an optional filter, and radial params (min_score/max_distance). On the coordinating node it may rewrite (resolve the field, validate dimension/space_type against the mapping). On the shard, doToQuery(QueryShardContext) builds the Lucene Query — a KNNQuery (for faiss/nmslib) or, for the lucene engine, delegates to Lucene's KnnFloatVectorQuery. The engine decision comes from the field's KNNVectorFieldType/KNNMethodContext.

grep -rn "doToQuery\|doRewrite\|getKnnEngine\|KNNEngine\|KnnFloatVectorQuery\|RNNQuery\|RadialSearch\|maxDistance\|minScore" \
  src/main/java/org/opensearch/knn/index/query/KNNQueryBuilder.java

Validation happens here, early: dimension mismatch (query vector length ≠ field dimension), space-type incompatibilities, asking for IVF/PQ params on a non-faiss field — all are rejected before any search runs. A clear validation failure here is far better than a confusing recall problem later.

Hop 2 — KNNQuery → KNNWeight → KNNScorer (per segment)

This is the Lucene Query/Weight/Scorer triad, the same shape any Lucene query uses (see Search Execution and the Lucene HNSW chapter):

• KNNQuery — the immutable query object: field, vector, k, filter, radial params.
• KNNWeight.scorer(LeafReaderContext) — called once per segment. This is where the real work is set up: it resolves the per-segment k-NN data (the faiss/nmslib graph for this segment, loaded via the native cache), applies any filter, runs the ANN search, and produces the segment's matching docIds with scores.
• KNNScorer — iterates those results as a Lucene Scorer (a DocIdSetIterator with a score()), so the rest of Lucene's collection machinery treats k-NN hits like any other scored hits.

grep -rn "class KNNWeight\|public Scorer scorer\|doANNSearch\|getFilteredDocIds\|exactSearch\|JNIService\|queryIndex" \
  src/main/java/org/opensearch/knn/index/query/KNNWeight.java
grep -rn "class KNNScorer\|DocIdSetIterator\|float score\|iterator()" \
  src/main/java/org/opensearch/knn/index/query/KNNScorer.java

Inside KNNWeight.scorer — the per-segment search

For the faiss/nmslib engines, the per-segment search is a JNI call. KNNWeight gets the segment's native index pointer from NativeMemoryCacheManager (loading it on demand, subject to the native circuit breaker — see native integration and memory) and calls JNIService.queryIndex(pointer, queryVector, k, ...). faiss walks the HNSW graph (or probes IVF cells), returns the top-k (docId, distance) pairs for that segment, and KNNWeight converts faiss distances into OpenSearch scores via the field's SpaceType (e.g. for L2, score is a monotonic transform of 1/(1+d²)).

For the lucene engine, there is no JNI: KnnFloatVectorQuery runs Lucene's HNSW search over the segment's .vec/.vex/.vem files using VectorUtil for the distance math, and returns its own TopDocs.

flowchart TD
    KW["KNNWeight.scorer(leaf segment)"] --> ENG{engine?}
    ENG -->|faiss / nmslib| NC["NativeMemoryCacheManager.get(segment)<br/>(load via JNI if cold, CB-gated)"]
    NC --> JNI["JNIService.queryIndex(ptr, vec, k)"]
    JNI --> FA["faiss/nmslib: walk HNSW / probe IVF<br/>-> top-k (docId, distance)"]
    FA --> SC["convert distance -> score via SpaceType"]
    ENG -->|lucene| LV["KnnFloatVectorQuery over .vec/.vex/.vem<br/>VectorUtil distance (Panama SIMD)"]
    LV --> SC
    SC --> KS["KNNScorer: DocIdSetIterator + score()"]

The key structural fact: k-NN search is per-segment. Each segment has its own graph; k neighbours are retrieved from each segment, and the per-shard top-k is the merge of all segments' results. More segments → more graphs walked per query → why merge policy and segment count matter for k-NN latency, and why force-merging to fewer segments is a real k-NN tuning lever (at the cost of expensive merges that rebuild graphs).

Hop 3 — per-shard reduce, then the coordinator reduce

Within a shard, Lucene's collector merges the per-segment KNNScorer results into the shard's top results — bounded by the larger of k and size. Then we are back on the standard search-execution rails: each shard ships its top docIds + scores in a QuerySearchResult, the coordinator's SearchPhaseController.reducedQueryPhase does a sorted merge into the global top-k, and a fetch phase pulls _source for the winners.

sequenceDiagram
    participant C as Client
    participant Co as Coordinating node
    participant S1 as Shard A (data node)
    participant S2 as Shard B (data node)
    C->>Co: POST /idx/_search { knn: { field, vector, k } }
    par Query phase (scatter) — k-NN per shard
        Co->>S1: ShardSearchRequest
        Note over S1: KNNWeight per segment -> JNI/Lucene ANN<br/>merge segments -> shard top-k
        Co->>S2: ShardSearchRequest
        Note over S2: same: per-segment ANN -> shard top-k
    end
    S1-->>Co: top (docId, score) [no _source]
    S2-->>Co: top (docId, score)
    Note over Co: SearchPhaseController.reducedQueryPhase<br/>-> GLOBAL top-k by score
    par Fetch phase (only winners' shards)
        Co->>S1: ShardFetchRequest (docIds)
        Co->>S2: ShardFetchRequest
    end
    S1-->>Co: _source for its winners
    S2-->>Co: _source ...
    Co-->>C: SearchResponse (hits sorted by score)

Note: Because each of N shards returns up to k candidates, the coordinator reduces over N·k candidates to produce the global top-k. Total recall is therefore a function of both per-shard k and shard count. This is also why fewer, larger shards can give better k-NN recall than many tiny shards at the same total k — each shard's graph sees more of the data.

Approximate vs exact: the script-score fallback

The default knn query is approximate — it walks the ANN structure and may miss true neighbours (that is the whole HNSW/IVF trade-off from the algorithms chapter). When you need exact k-NN — ground truth, or recall measurement, or a tiny corpus where ANN is pointless — you do a brute-force scan via the script_score path: a knn_score script (Painless, backed by KNNScoreScript) that computes the exact distance from the query to every matching document and lets the normal scorer sort them.

curl -XPOST 'localhost:9200/products/_search' -H 'Content-Type: application/json' -d '
{
  "size": 10,
  "query": {
    "script_score": {
      "query": { "match_all": {} },
      "script": {
        "source": "knn_score",
        "lang": "knn",
        "params": { "field": "embedding", "query_value": [/* ... */], "space_type": "l2" }
      }
    }
  }
}'

grep -rln "KNNScoreScript\|knn_score\|ScriptEngine\|class KNNScoringSpace\|exactSearch" \
  src/main/java/org/opensearch/knn/plugin/script src/main/java/org/opensearch/knn/index/query

There is also an internal exact path: when a filter is so selective that there are fewer matching docs than it is worth walking the graph for, KNNWeight can fall back to an exact scan over just the filtered docs. That is the next topic.

Filtered k-NN: pre- vs post-filtering and "efficient filtering"

"Give me the 10 nearest vectors that also match this filter" is the single most requested k-NN feature, and the naive approaches both fail:

• Post-filtering (search ANN for k, then drop the ones that fail the filter): if the filter is selective, you can throw away most of your k results and return fewer than k — or even zero. Recall craters.
• Pre-filtering by brute force (compute the filter bitset, then exact-scan only those docs): correct, but O(filtered N) — fine for tiny filtered sets, terrible for large ones.

The good answer is efficient (in-graph) filtering: push the filter into the ANN traversal so the graph search only ever accepts docs that pass the filter, walking the graph until it has k valid neighbours. faiss supports this via an id-selector; Lucene's KnnFloatVectorQuery supports it with a filter Query (see the Lucene HNSW chapter). k-NN chooses a strategy based on the filter's selectivity:

flowchart TD
    F["knn query with filter"] --> B["compute filter bitset for the segment"]
    B --> SEL{"filtered cardinality vs threshold"}
    SEL -->|very selective<br/>(few docs pass)| EX["exact brute-force over the filtered docs<br/>(cheap, 100% recall on the subset)"]
    SEL -->|not very selective| EFF["ANN with the filter pushed into traversal<br/>(faiss id-selector / Lucene filtered HNSW)"]
    EX --> R[top-k valid neighbours]
    EFF --> R

curl -XPOST 'localhost:9200/products/_search' -H 'Content-Type: application/json' -d '
{
  "query": {
    "knn": {
      "embedding": {
        "vector": [/* ... */],
        "k": 10,
        "filter": { "term": { "category": "shoes" } }
      }
    }
  }
}'

grep -rn "filter\|getFilteredDocIds\|cardinality\|exactSearch\|FilterWeight\|expandNearestNeighbors\|MAX_DISTANCE\|filterWeight" \
  src/main/java/org/opensearch/knn/index/query/KNNWeight.java

Warning — filter explosion: the exact-vs-efficient decision hinges on the filter's cardinality per segment. A filter that is selective globally can still be non-selective in some segments. If recall or latency surprises you under a filter, check whether you fell into the exact path on big segments or the post-filter path in an older version. Push the filter into the knn clause's filter; do not wrap the whole knn query in a bool/post_filter and expect efficient filtering.

Radial search: min_score / max_distance

Sometimes you do not want "the k nearest" — you want "every vector within a distance/score threshold," however many that is. That is radial search, expressed with max_distance (a distance cutoff) or min_score (a score cutoff) instead of k:

curl -XPOST 'localhost:9200/products/_search' -H 'Content-Type: application/json' -d '
{
  "query": {
    "knn": {
      "embedding": {
        "vector": [/* ... */],
        "max_distance": 0.35
      }
    }
  }
}'

Internally this is a different traversal: rather than stopping at k results, the search expands the neighbourhood until no candidate within the radius remains. It is supported on faiss and lucene engines (grep your version for the exact support matrix). The trap is unbounded result size: a loose threshold over a dense region can match an enormous number of docs, so radial search must still respect size and can be expensive. Treat max_distance/min_score as a semantic threshold you tune against your space, not a free "give me everything close" button.

grep -rn "max_distance\|min_score\|RadialSearch\|RNNQuery\|radius\|MAX_DISTANCE\|MIN_SCORE" \
  src/main/java/org/opensearch/knn/index/query

Rescoring: full-precision after quantized retrieval

When the field uses a compressed representation — PQ, byte/FP16 scalar quantization, binary quantization, or on_disk mode (all in quantization and disk-ANN) — the ANN search runs over approximate vectors, so its scores are noisy and its ordering is imperfect. The production pattern is a two-pass query:

1. Retrieve an over-fetched candidate set (oversample × k) using the cheap, compressed representation.
2. Rescore those candidates by computing the full-precision distance for each (reading the original float32 vectors), then re-sort and keep the true top-k.

This recovers most of the recall lost to compression while keeping the fast first pass. It is expressed with a rescore block (or enabled automatically for on_disk mode):

curl -XPOST 'localhost:9200/products/_search' -H 'Content-Type: application/json' -d '
{
  "query": {
    "knn": {
      "embedding": {
        "vector": [/* ... */],
        "k": 10,
        "rescore": { "oversample_factor": 2.0 }
      }
    }
  }
}'

flowchart LR
    Q[query vector] --> A["pass 1: ANN over compressed vectors<br/>retrieve oversample*k candidates"]
    A --> B["pass 2: rescore candidates with<br/>full-precision float32 distance"]
    B --> C["re-sort -> true top-k"]

grep -rn "rescore\|oversample\|RescoreContext\|fullPrecision\|reScore\|ExactSearcher" \
  src/main/java/org/opensearch/knn/index/query

The oversample factor is a recall/latency dial: more candidates → better post-rescore recall → more full-precision distance computations. This is the same idea as Lucene's quantized-vectors-then-rescore pattern (see HNSW in Lucene); k-NN exposes it as a first-class query option because disk-based and PQ indexes depend on it for acceptable recall.

Putting it together — the full fan-out

sequenceDiagram
    participant U as User
    participant Co as Coordinating node
    participant SH as Shard (data node)
    participant SEG as Segment(s)
    participant NAT as faiss (native) / Lucene HNSW
    U->>Co: knn query (field, vector, k, [filter|radial|rescore])
    Co->>Co: KNNQueryBuilder rewrite/validate (dimension, space, engine)
    Co->>SH: ShardSearchRequest (query phase)
    SH->>SEG: KNNWeight.scorer per segment
    SEG->>NAT: ANN search (JNI queryIndex / KnnFloatVectorQuery)
    NAT-->>SEG: per-segment top-k (docId, distance)
    SEG-->>SH: merge segments -> shard top-k (KNNScorer scores)
    opt rescore (compressed index)
        SH->>SEG: full-precision distance for candidates
        SEG-->>SH: re-sorted true top-k
    end
    SH-->>Co: QuerySearchResult (docIds + scores)
    Co->>Co: reducedQueryPhase -> global top-k
    Co->>SH: fetch phase (_source for winners)
    SH-->>Co: hits
    Co-->>U: SearchResponse

Common bugs and symptoms

Validation: prove you understand this

1. List, in order, every class a knn query passes through from REST to per-segment search and back to the coordinator reduce. For each, say which node it runs on and what it produces.
2. Explain why k-NN search is per-segment, what that implies for the relationship between segment count and query latency, and why force-merge is a k-NN tuning lever.
3. Distinguish k from top-level size. A user sets k:10, size:50 on a 5-shard index and gets 10 hits. Diagnose it and give the fix.
4. Contrast post-filtering, brute-force pre-filtering, and efficient (in-graph) filtering. What does KNNWeight decide between, and on what signal?
5. When would you use exact script_score k-NN instead of the approximate knn query? What is the cost, and which class implements the exact score?
6. Explain radial search and the failure mode of a too-loose max_distance. How does it differ structurally from a k-bounded search?
7. Walk the rescoring two-pass flow: what runs in pass 1, what runs in pass 2, what oversample_factor trades off, and why disk-based/PQ indexes need it.

When you can do all seven, you understand the runtime. Trace it for real in the lab lab-k2-trace-a-knn-query. For where the native graphs that serve hop 2 actually live, return to native integration and memory; for the compressed representations that make rescoring necessary, read quantization and disk-ANN; for the coordinator fan-out this builds on, re-read Search Execution.