The Query Engine — Intensive

You typed a JSON object into a _search body. Milliseconds later a ranked list of documents came back. Between those two events is the single most-exercised code path in OpenSearch, and it crosses three distinct worlds: an OpenSearch QueryBuilder tree, a Lucene Query/Weight/Scorer machine, and a similarity function that turns term statistics into a float. This masterclass is the whole journey, in depth — from NamedXContentRegistry parsing the DSL, through rewrite and toQuery, into the Scorer/DocIdSetIterator iteration model, the BM25 formula with a worked numeric example, the top-k skipping algorithms (WAND / MaxScore / Block-Max WAND) that let OpenSearch not score most of the corpus, and the three caches that make the second identical query free.

This chapter assumes you have read the two layers it sits between:

• Query DSL and QueryBuilders — the parse → rewrite → toQuery pipeline and the SearchPlugin.getQueries() hook.
• The Inverted Index and Postings — what a TermQuery does: TermsEnum → PostingsEnum → a DocIdSetIterator.

It is the counterpart, on the read path, of the storage-engine masterclass on the write path, and it feeds directly into Search Execution (the distributed query-then-fetch coordination above it) and Concurrent Segment Search (how the per-segment scoring you learn here is sliced across threads).

After this chapter you can:

• Trace a bool/match query from JSON bytes to a Lucene Query, naming the context object active at each stage.
• Draw the Query → Weight → Scorer → DocIdSetIterator model and explain where TwoPhaseIterator splits approximation from confirmation.
• Write the BM25 score for a document by hand and match it against _explain.
• Explain how Block-Max WAND finds the exact same top-k while skipping the bulk of the postings, and where totalHitsThreshold makes hit counts approximate.
• Reason about which clauses the LRUQueryCache caches, and why filter caches but must (scoring) does not.

Note: "cluster manager" is the OpenSearch term for what older Elasticsearch/Lucene docs call the master node. The query engine itself runs on data nodes, but the coordinating node (any node that receives the request) does the first rewrite. We use the modern names throughout.

The map: four stages, three representations

flowchart TD
    subgraph Coordinating node
      J["JSON DSL bytes"] -->|NamedXContentRegistry| QB["QueryBuilder tree"]
      QB -->|rewrite QueryRewriteContext| QB2["rewritten QueryBuilder tree"]
    end
    subgraph Each data node / each shard
      QB2 -->|rewrite QueryShardContext| QB3["per-shard QueryBuilder"]
      QB3 -->|toQuery QueryShardContext| LQ["Lucene Query"]
      LQ -->|createWeight ScoreMode boost| W["Weight"]
      W -->|scorerSupplier / scorer per segment| SC["Scorer"]
      SC --> IT["DocIdSetIterator + score()"]
      IT -->|collected by| COL["Collector / CollectorManager"]
    end
    COL --> TD["TopDocs (per shard)"]

The three representations you must keep distinct:

Three representations means three classes of bug: a parse bug (the registry never heard of your query name), a toQuery bug (the field type produced the wrong Lucene query), and a scoring/iteration bug (the Scorer skips a doc it should match). Knowing which representation you are debugging is half the fix.

# Orient yourself in an OpenSearch checkout (clone opensearch-project/OpenSearch):
cd ~/src/OpenSearch
ls server/src/main/java/org/opensearch/index/query/ | grep QueryBuilder | head
# Lucene is a dependency; the sources are in the apache/lucene repo. Clone it too:
#   git clone https://github.com/apache/lucene
ls lucene/core/src/java/org/apache/lucene/search/ | grep -E 'Query|Weight|Scorer' | head -40

Stage 1 — Parse: JSON to a QueryBuilder tree

The query object has exactly one key naming the type. AbstractQueryBuilder's parseInnerQueryBuilder reads that key and dispatches through the NamedXContentRegistry to the registered fromXContent parser. The registry is assembled in SearchModule from every core query plus everything each SearchPlugin.getQueries() contributes — this is exactly how a plugin adds a custom query type (k-NN's knn query, neural-search's neural query, etc.).

grep -n "parseInnerQueryBuilder\|NamedXContentRegistry" \
  server/src/main/java/org/opensearch/index/query/AbstractQueryBuilder.java
grep -n "registerQuery\|QuerySpec\|getQueries" \
  server/src/main/java/org/opensearch/search/SearchModule.java

Parse failures surface here as ParsingException / XContentParseException before any index is touched — a typo'd query name fails fast with unknown query [...]. This is covered in depth in Query DSL and QueryBuilders; we move on to where the real query-engine work begins.

Stage 2 — Rewrite: simplify before you score

Rewriteable.rewrite drives QueryBuilder.rewrite(QueryRewriteContext) → doRewrite on each node, repeatedly until a fixpoint (rewrite can be a multi-round process). Two things happen at two different places:

1. On the coordinating node with a plain QueryRewriteContext: async resolution (terms lookup fetching the lookup doc, wrapper/percolator, geo-shape pre-fetch), and cheap constant folding.
2. Per shard with a QueryShardContext (a QueryRewriteContext subclass that also has the MapperService and an IndexSearcher): range clauses that cannot match this shard's min/max rewrite to MatchNoneQueryBuilder. That feeds the can_match shard-skipping optimization in Search Execution.

grep -n "doRewrite\|MatchNoneQueryBuilder\|rewrite(" \
  server/src/main/java/org/opensearch/index/query/RangeQueryBuilder.java \
  server/src/main/java/org/opensearch/index/query/BoolQueryBuilder.java

After OpenSearch's QueryBuilder.rewrite, the resulting Lucene Query is rewritten again by Lucene itself: IndexSearcher.rewrite(Query) loops calling Query.rewrite(IndexSearcher) until stable. A PrefixQuery becomes a MultiTermQuery enumeration or a constant-score wrapper; a BooleanQuery with one MUST clause collapses. Two rewrite systems, stacked — keep them straight.

Stage 3 — toQuery: become a Lucene Query

AbstractQueryBuilder.toQuery(QueryShardContext) → doToQuery produces an org.apache.lucene.search.Query. The field type from the mapping decides the shape: MatchQueryBuilder consults the field analyzer to tokenize the input, then emits one TermQuery per token inside a BooleanQuery (or a PhraseQuery / SynonymQuery). A term query does not analyze — a classic mistake on analyzed text fields.

grep -n "doToQuery\|MappedFieldType\|getSearchAnalyzer\|analyzer" \
  server/src/main/java/org/opensearch/index/query/MatchQueryBuilder.java
# BoolQueryBuilder maps each clause list onto BooleanClause.Occur:
grep -n "Occur\|addClause\|MUST\|SHOULD\|FILTER\|MUST_NOT\|minimumShouldMatch" \
  server/src/main/java/org/opensearch/index/query/BoolQueryBuilder.java

The execution model: Query → Weight → Scorer → DocIdSetIterator

This is the heart of Lucene, and the part most engineers never internalize. A Query is an immutable, reusable description. To run it you ask it for a Weight, which captures per-search state (statistics, the boost). The Weight then produces, per segment, a Scorer that walks matching docs and scores them.

flowchart LR
    Q["Query (immutable)"] -->|"createWeight(searcher, ScoreMode, boost)"| W["Weight"]
    W -->|"scorerSupplier(LeafReaderContext)"| SS["ScorerSupplier (knows cost)"]
    SS -->|"get(leadCost)"| S["Scorer"]
    S -->|"iterator()"| DISI["DocIdSetIterator: nextDoc()/advance()"]
    S -->|"score()"| F["float score"]
    S -->|"twoPhaseIterator()"| TPI["TwoPhaseIterator: matches()/matchCost()"]

The pieces, precisely:

DocIdSetIterator is the universal currency. Postings, a BKD range, a cached bitset, a conjunction — every matching set in Lucene is one of these. That is what lets a bool conjunction intersect a term (postings), a range (points), and a cached filter (bitset) in one tight loop.

TwoPhaseIterator exists because some matches are cheap to approximate and expensive to confirm. A PhraseQuery approximates with the conjunction of its terms' postings (docs containing all terms) and confirms by checking positions — matches() only runs on the survivors of the cheap approximation(). The matchCost() lets Lucene order confirmations cheapest-first.

grep -n "abstract class Weight\|scorerSupplier\|abstract.*scorer" \
  lucene/core/src/java/org/apache/lucene/search/Weight.java
grep -n "class Scorer\|getMaxScore\|twoPhaseIterator" \
  lucene/core/src/java/org/apache/lucene/search/Scorer.java
grep -n "class DocIdSetIterator\|NO_MORE_DOCS\|nextDoc\|advance\|cost" \
  lucene/core/src/java/org/apache/lucene/search/DocIdSetIterator.java
grep -n "class TwoPhaseIterator\|matchCost\|matches()" \
  lucene/core/src/java/org/apache/lucene/search/TwoPhaseIterator.java

BooleanQuery execution: conjunctions and disjunctions

BooleanQuery is where the Occur clauses become concrete iteration strategy. A BooleanWeight builds a scorer that combines the per-clause scorers according to the clause types.

• Conjunction (MUST/FILTER): ConjunctionDISI sorts the sub-iterators by cost() ascending, drives the rarest (lowest-cost) one as the lead, and calls advance(target) on the others to leap-frog to a common doc. The skip lists in the postings (see The Inverted Index and Postings) make those advance calls sublinear. This is why a rare term + a common term is fast: the rare term leads, the common term skips.
• Disjunction (SHOULD): a DisjunctionScorer over a DisiPriorityQueue ordered by current docID; nextDoc() advances the head(s) and re-heaps. When only top-k by score is needed, the disjunction becomes a WAND-family scorer (next section) instead of scoring every union member.

grep -rn "class BooleanWeight\|class BooleanScorer\|ConjunctionDISI\|DisjunctionScorer\|class WANDScorer\|class MaxScoreScorer" \
  lucene/core/src/java/org/apache/lucene/search/
grep -n "minimumNumberShouldMatch\|FILTER\|MUST_NOT" \
  lucene/core/src/java/org/apache/lucene/search/BooleanWeight.java

Note: a MUST_NOT clause and a FILTER clause both contribute zero to the score and are eligible for caching as a DocIdSet. Move every non-relevance predicate (status flags, timestamps, tenant IDs) into filter, never must.

Scoring: BM25Similarity, the formula and a worked example

Once a Scorer lands on a matching doc, score() asks the Similarity for a number. The default is BM25Similarity, and you should be able to reproduce it on paper. Let:

• tf = term frequency in the document (how many times the term occurs),
• N = number of documents that have the field, n = docs containing the term,
• dl = this field's length (number of terms) in the doc, avgdl = average field length across the index,
• k1 = 1.2, b = 0.75 (the OpenSearch/Lucene defaults).

The idf (Lucene's robust, always-positive variant):

idf = ln(1 + (N - n + 0.5) / (n + 0.5))

The tf saturation + length normalization term:

tfNorm = (tf * (k1 + 1)) / (tf + k1 * (1 - b + b * dl / avgdl))
score  = boost * idf * tfNorm

Read the two halves as design choices:

• idf rewards rarity: a term in few docs scores higher. The +0.5/+1 guards keep it positive even for a term in every doc.
• tf saturation (k1): the first occurrence of a term matters a lot; the tenth barely moves the needle. As tf → ∞, tfNorm → k1 + 1. k1 tunes how fast it saturates (bigger k1 = slower saturation, term frequency matters more).
• length normalization (b): a 10-word title matching "fox" is more about "fox" than a 10,000-word body that also contains "fox". b=1 fully normalizes by length; b=0 ignores length. The dl is read from the field norms (.nvd/.nvm), a 1-byte lossy encoding of field length.

A worked numeric example

Index: N = 1,000,000 docs; the term "opensearch" appears in n = 2,000 docs; avgdl = 30. Our document has dl = 12 and tf = 3 for "opensearch". Boost = 1.0.

idf    = ln(1 + (1_000_000 - 2_000 + 0.5)/(2_000 + 0.5))
       = ln(1 + 998_000.5/2_000.5) = ln(1 + 498.875) = ln(499.875) ≈ 6.2143

denom  = tf + k1*(1 - b + b*dl/avgdl)
       = 3 + 1.2*(1 - 0.75 + 0.75*12/30)
       = 3 + 1.2*(0.25 + 0.30)
       = 3 + 1.2*0.55 = 3 + 0.66 = 3.66

tfNorm = (tf*(k1+1))/denom = (3*2.2)/3.66 = 6.6/3.66 ≈ 1.8033

score  = 1.0 * 6.2143 * 1.8033 ≈ 11.207

Now run _explain on that doc and you will see those exact sub-values: an idf node ≈ 6.2143, a tfNorm node ≈ 1.8033, multiplied. Lab QE2 makes you reproduce this end to end against a real index and a standalone Lucene program.

grep -n "class BM25Similarity\|float idf\|tfNorm\|k1\|public float score" \
  lucene/core/src/java/org/apache/lucene/search/similarities/BM25Similarity.java
# OpenSearch lets you swap/parameterize similarity per index/field:
grep -rn "BM25Similarity\|SimilarityProvider\|index.similarity" \
  server/src/main/java/org/opensearch/index/similarity/

Note: idf uses per-shard statistics by default — N and n are local to the shard. On small or skewed shards this makes scores differ across shards for the same doc. The DFS phase (dfs_query_then_fetch) gathers global stats first; see Search Execution.

Top-k skipping: WAND, MaxScore, Block-Max WAND

Here is the insight that makes modern search fast: if you only want the top size documents by score, you do not have to score the rest. If a document's best possible score (a known upper bound) cannot beat the worst score currently in your top-k heap, you can skip it without computing its real score. The algorithms differ in how they compute and exploit that bound.

The enabling data structure is impacts: the postings format stores, per skip block, the maximum (freq, norm) impact, so Lucene can compute a tight per-block score upper bound without decoding the block. ImpactsEnum exposes them; the Scorer.getMaxScore(upTo) API returns the bound for docs up to upTo.

flowchart TD
    A["top-k heap, current min = θ"] --> B{"block-max score(block) > θ ?"}
    B -- "no" --> SKIP["advance() past the whole block — never decode it"]
    B -- "yes" --> DEC["decode block, score docs"]
    DEC --> C{"doc score > θ ?"}
    C -- "no" --> NEXT["skip doc"]
    C -- "yes" --> PUSH["push into heap; θ rises"]
    PUSH --> A
    SKIP --> A
    NEXT --> A

The threshold θ is the worst score in the heap, and it rises as the heap fills, so skipping gets more aggressive as the query runs. Crucially, the top-k results are identical to a full scan — only the count of docs scored changes. That is the contract: faster, not different.

The collector drives this. TopScoreDocCollector feeds its current heap minimum to the scorers via setMinCompetitiveScore, which is how θ propagates down to the block-skip decision. And totalHitsThreshold controls when counting stops:

grep -rn "class WANDScorer\|class MaxScoreScorer\|setMinCompetitiveScore\|getMaxScore\|class ImpactsEnum\|class TopScoreDocCollector\|totalHitsThreshold" \
  lucene/core/src/java/org/apache/lucene/search/ \
  lucene/core/src/java/org/apache/lucene/index/ | head -30

Warning: a frequent confusion is "Block-Max WAND changed my results." It does not. If your top-k content changed, something else did (a mapping change, a different analyzer, per-shard idf). What BMW changes is the hits.total when totalHitsThreshold is hit — that is expected and is a count, not a ranking, approximation.

Caching: three different caches, three different keys

The single biggest source of query-engine confusion is conflating the three caches. They key on different things and hold different things.

flowchart TD
    REQ["search request"] --> SRC{"shard request cache?\n(size:0 / aggs)"}
    SRC -- hit --> RESP["whole serialized shard response"]
    SRC -- miss --> QP["query phase per shard"]
    QP --> QC{"LRUQueryCache?\n(per cacheable clause)"}
    QC -- hit --> BITSET["cached DocIdSet (bitset)"]
    QC -- miss --> SCORE["build Scorer, iterate postings"]
    SCORE --> FD["fielddata cache (sort/agg/script on text)"]

The query cache is the subtle one. LRUQueryCache does not cache everything — it asks UsageTrackingQueryCachingPolicy.shouldCache(query):

• The clause must be cacheable (no scoring needed — filter, must_not, constant_score; a scoring must/should is not cached because the cached bitset has no scores).
• The policy tracks usage frequency: a query must be seen often enough before it is cached (cheap, rare queries are not worth a bitset). Tiny segments are also skipped (the heuristic won't cache segments below a small doc count).

grep -n "class LRUQueryCache\|shouldCache\|DocIdSet\|class CachingWrapperWeight" \
  lucene/core/src/java/org/apache/lucene/search/LRUQueryCache.java
grep -n "class UsageTrackingQueryCachingPolicy\|shouldCache\|isCostly\|frequency" \
  lucene/core/src/java/org/apache/lucene/search/UsageTrackingQueryCachingPolicy.java
grep -rn "class IndicesRequestCache\|request_cache\|class IndicesQueryCache" \
  server/src/main/java/org/opensearch/indices/

This is why filter is both faster (no scoring) and cacheable (a reusable bitset), and why moving a predicate from must to filter can turn a 50ms query into a sub-millisecond one on the second run. Lab QE3 measures it. For the OpenSearch-specific tiered caching that spills the shard request cache to disk, see Tiered Caching.

Execution extras: paging, PIT, rescore, function_score, pipelines

The query engine has a set of features that wrap or follow the core scoring loop. Know what each one does to the Scorer/Collector machinery.

• from/size vs search_after: from: 10000, size: 10 builds a heap of 10,010 and discards 10,000 — wasteful and memory-bounded by index.max_result_window. search_after carries the last hit's sort values and resumes; the heap stays size. Use it for deep paging.
• rescore: the main query is cheap and approximate (good recall), the rescore query is expensive and precise (good precision), applied only to the top window_size docs. This is the textbook two-stage ranking and the natural place a learning-to-rank or cross-encoder reranker plugs in.
• search pipelines are the request/response analog of ingest pipelines: SearchRequestProcessors rewrite the request (e.g., a neural query expansion), SearchResponseProcessors post-process hits (e.g., rerank, collapse, personalize). They are the supported extension point that does not require a Lucene Query.

grep -rn "class QueryRescorer\|class RescoreContext\|class FunctionScoreQuery" \
  lucene/core/src/java/org/apache/lucene/search/ \
  server/src/main/java/org/opensearch/
grep -rn "interface SearchRequestProcessor\|interface SearchResponseProcessor\|class PitReaderContext\|search_after\|searchAfter" \
  server/src/main/java/org/opensearch/search/ | head

The Profile API ("profile": true) exposes all of this: per-shard, per-component rewrite_time, build_scorer, score, next_doc, advance, set_min_competitive_score, and a parallel breakdown for aggregations and the collector tree. It is the single best tool for "where did my milliseconds go," and Lab QE1 drives it.

End-to-end worked trace

Put it together for {"bool":{"must":[{"match":{"title":"open source"}}],"filter":[{"term":{"status":"published"}}]}}:

1. Parse: NamedXContentRegistry → BoolQueryBuilder containing a MatchQueryBuilder (must) and a TermQueryBuilder (filter).
2. Rewrite: coordinator rewrite is a no-op here; per-shard rewrite leaves it intact (a range would have been the interesting case).
3. toQuery: the match analyzes "open source" → tokens [open, source] → BooleanQuery(SHOULD open, SHOULD source); the term filter → TermQuery(status:published). Final: BooleanQuery(MUST <match boolean>, FILTER <term>).
4. Weight/Scorer: BooleanWeight → a conjunction of the scoring sub-query and the filter; the filter clause is checked for caching by UsageTrackingQueryCachingPolicy.
5. Iterate + score: the conjunction leads with the rarest iterator, advances the others; matching docs get a BM25 score from the match part only (the filter scores 0); TopScoreDocCollector keeps the top size and feeds θ back for skipping.
6. Collect: per-shard TopDocs go up to the coordinator, which merges and issues the fetch phase (Search Execution).

Trade-offs: when each mechanism helps vs hurts

Common bugs and symptoms

The labs

• Lab QE1: QueryBuilder to Lucene Query — trace a bool/match with _validate/query?rewrite=true and _search?profile=true, then code-trace MatchQueryBuilder.doToQuery.
• Lab QE2: BM25 and Scoring Internals — decompose a score with _explain, change similarity params, reproduce BM25 in a standalone Lucene program, and watch Block-Max WAND keep the top-k identical.
• Lab QE3: Query Cache and Optimization — observe the node query cache and shard request cache, prove a filter hit, and measure must vs filter.

Validation: prove you understand this

1. From memory, name the four stages (parse, rewrite, toQuery, weight/scorer), the context object active in each, and where the coordinating node vs shard boundary falls.
2. Draw Query → Weight → Scorer → DocIdSetIterator, and explain what a TwoPhaseIterator adds and which query type needs it.
3. Compute the BM25 score for: N=500000, n=1000, avgdl=40, dl=20, tf=2, boost=1, defaults k1=1.2, b=0.75. Show idf, tfNorm, and the product.
4. Explain how Block-Max WAND skips a block of docs without decoding it, what data structure supplies the per-block bound, and why the top-k is still exact.
5. Distinguish the node query cache, the shard request cache, and the fielddata cache: what each keys on, what each holds, and which one a filter clause populates.
6. Explain why a predicate in bool.filter is both faster and cacheable versus the same predicate in bool.must, in terms of scoring and UsageTrackingQueryCachingPolicy.

Next: Lab QE1 — QueryBuilder to Lucene Query.