Execution Plans
How search engines translate "find laptops under $500" into disk reads, iterator operations, and score calculations.
This chapter reveals the internal machinery of query execution. Understanding these mechanics is essential for debugging slow queries and writing efficient search applications. Every millisecond in a search request can be traced to these operations.
3 Layers
Query → Weight → Scorer abstraction for segment-level execution.
O(1)
Amortized cost per document via skip lists and block iteration.
~10x
Profile API adds significant overhead—debug only.
1. The Query → Weight → Scorer Pipeline
This is the fundamental architecture of Lucene query execution. Every search, from a simple term lookup to a complex boolean query with filters, passes through these three layers. Understanding this abstraction is the key to understanding query performance.
The separation exists for a reason: Query objects are reusable and stateless, Weight objects hold index-level statistics (computed once), and Scorer objects handle segment-specific iteration (created per segment). This design enables efficient execution across a segmented index.
User-facing representation. Defines WHAT to search for.
TermQuery, BooleanQueryIndex-level state. Computes IDF, query boosts.
query.create_weight()Segment-level iterator. Computes TF, length norms.
weight.scorer(segment)IDF (Inverse Document Frequency) is computed at the Weight level because it only depends on global term statistics. TF (Term Frequency) is computed at the Scorer level because it varies per document. This separation avoids redundant computation.
2. DocIdSetIterator (DISI)
The DocIdSetIterator (DISI) is the heart of Lucene's query execution. Every query, filter, and scorer ultimately reduces to iterating over document IDs. Understanding DISI patterns is essential for understanding why certain queries are fast and others are slow.
All DISI implementations return documents in increasing docID order within a segment. This monotonic ordering enables efficient set operations (intersection, union) via merge-like algorithms. The key methods arenextDoc() andadvance(target).
int nextDoc()Advance to the next matching document. Returns NO_MORE_DOCS when exhausted.
int advance(int target)Skip to target or beyond. Essential for efficient intersection.
int docID()Return current document ID. Returns -1 before first nextDoc().
long cost()Estimated number of matching docs. Used for optimization decisions.
Key DISI Implementations
| Class | Purpose | Strategy |
|---|---|---|
| TermScorer | Single term matches | Iterate posting list |
| ConjunctionDISI | AND queries | Intersection via leap-frog |
| DisjunctionDISI | OR queries | Union via priority queue |
| ReqExclScorer | MUST_NOT handling | Skip excluded docs |
| BlockMaxDISI | Early termination | Skip low-scoring blocks |
3. Conjunction: The Leap-Frog Algorithm
For AND queries (A AND B AND C), Lucene uses the leap-frog algorithm. Instead of scanning all documents, iterators "leap" over each other to find common documents efficiently. This is why AND queries are typically faster than OR queries.
The algorithm exploits the fact that DISI returns documents in sorted order. When iterator A is at doc 5 and B is at doc 10, we can skip A directly to 10 (or beyond) without checking docs 6-9. This optimization is dramatic when intersecting large posting lists with small ones.
Lucene sorts sub-queries by cost() (estimated matching docs) and puts the cheapest first. This minimizes advance() calls because the smallest iterator drives the leap-frog. If "blue" matches 100 docs and "electronics" matches 1M, we iterate "blue" and check "electronics" only 100 times.
4. Disjunction: Priority Queue
For OR queries (A OR B OR C), Lucene uses a min-heap priority queue. All iterators are placed in a heap ordered by current docID. We pop the minimum, collect all iterators at that docID, compute the combined score, then advance and re-insert them.
Disjunctions are more expensive than conjunctions because we must visit ALL matching documents from any sub-query. However, optimizations like WAND can skip documents that can't make it into the top-K results.
When minimum_should_match is set (e.g., "at least 2 of 5 terms"), Lucene can skip documents that only match one clause. The heap tracks how many iterators are at each docID.
For disjunctions, scores from matching clauses are summed. A document matching "laptop OR notebook OR computer" gets higher score if it matches all three terms.
5. TwoPhaseIterator
Some queries have expensive match conditions. For example, phrase query "quick brown fox" must verify that terms appear consecutively—a position check that requires reading position data. TwoPhaseIterator separates the cheap "might match" check from the expensive "definitely matches" confirmation.
This optimization is crucial for phrase queries, span queries, and any query with a cheap approximation but expensive verification. The first phase narrows candidates using the posting list intersection; the second phase confirms matches by checking positions.
Fast check using posting lists. For phrase "quick brown fox": does doc contain all three terms?
Expensive verification. For phrase "quick brown fox": do terms appear consecutively?
6. Query Rewriting
Before execution, queries are rewritten into optimized, executable forms. This transformation expands wildcards, simplifies Boolean logic, and enables accurate cost estimation. Rewriting requires an IndexReader because the final form depends on what terms exist in the index.
Rewriting is a multi-pass process. Query.rewrite(IndexReader)is called repeatedly until the query returns itself (no more transformations possible). This is why wildcard queries can be slow: they must enumerate matching terms before execution can begin.
Common Rewrites
| Original Query | Rewritten Form | Why |
|---|---|---|
| title:lap* | BooleanQuery(OR: laptop, lap, lapel, ...) | Expand wildcard to actual terms |
| +A +B -C (C=0 docs) | +A +B | Eliminate no-op clauses |
| BooleanQuery(MUST: A) | A | Unwrap single-clause BooleanQuery |
| ConstantScoreQuery(q) | q (with score=1.0) | Remove scoring overhead |
Leading wildcards (*laptop) can be extremely slow because they match potentially millions of terms. The rewrite phase must enumerate all matching terms before execution begins. Use edge-ngram tokenization instead.
7. Profile API
Elasticsearch's Profile API provides detailed timing breakdowns for query execution. Add"profile": true to any search request to see where time is spent. This is essential for diagnosing slow queries—but note that profiling adds ~10× overhead, so never use it in production.
The profile output is structured per-shard and shows the actual Lucene query types (which may differ from your Elasticsearch Query DSL after rewriting). Each query component shows its breakdown of low-level timing metrics.
Key Breakdown Metrics
create_weightTime to create Weight object (IDF calculation, query normalization)
build_scorerTime to create Scorer for each segment (posting list setup)
next_docTime iterating to next matching document (posting list traversal)
advanceTime skipping to target docID (skip list navigation)
scoreTime computing relevance scores (TF-IDF/BM25 calculation)
matchTime in TwoPhaseIterator.matches() (phrase/span verification)
8. Distributed Execution
Elasticsearch distributes queries across multiple shards. The query-then-fetch model minimizes network traffic by first collecting just docIDs and scores, then fetching full documents only for the final top-K results.
This two-phase approach is crucial for efficiency. If we fetched full documents immediately, a query requesting top-10 results from 5 shards would transfer 50 full documents over the network, only to discard 40 of them. With query-then-fetch, we transfer only 50 lightweight (docID, score) pairs in phase 1.
- 1. Coordinator routes to relevant shards
- 2. Each shard executes query locally
- 3. Returns top-K (docID, score) pairs
- 4. Coordinator merges and re-sorts globally
- 1. Coordinator identifies global top-K
- 2. Requests full documents from owning shards
- 3. Assembles final response
- 4. Returns to client
Key Takeaways
Query → Weight → Scorer
Three-layer pipeline: Query defines WHAT, Weight computes IDF, Scorer iterates and scores per segment.
All Matching is Iteration
DocIdSetIterator (DISI) is the heart of Lucene. AND uses leap-frog, OR uses priority queue.
Cost Drives Order
Lucene executes cheapest clauses first in conjunctions, using posting list length as cost estimate.
Profile API
Add "profile": true to see breakdown of create_weight, build_scorer, next_doc, advance, and score timings.