skip to content

Why does Lucene index numeric fields as BKD points rather than as terms in the inverted index?

level: seniorimportance: should knowfreq 38%

answer

  1. Ranges over near-unique values are the worst case for terms
  2. Values are organised by value, not by token
  3. Think of a spatial tree, not a dictionary
  4. Whole blocks accepted or pruned without inspection
  5. No frequencies means no relevance score

basics

~20 s

Numbers make terrible terms: encoding them for range search either explodes the term dictionary or forces long term enumerations. Lucene instead writes numerics into a balanced, block-oriented k-d tree on disk, where a range query skips whole leaf blocks that fall entirely inside or outside the bounds.

solid answer

~60 s

Before points existed, Lucene indexed numerics as a trie of terms at several precisions so that a range could be covered by a bounded number of term lookups. It worked, but multiplied the term count per value and made the term dictionary much larger. Since Lucene 6, numeric, date, IP and geo fields use **points**: values are written to a **BKD tree** — a balanced, bulk-loaded k-d tree stored in its own files (`.kdd` data, `.kdi` index, `.kdm` metadata). A range query descends the tree with an `IntersectVisitor`. Nodes whose bounding box lies fully inside the range contribute their entire leaf block without inspecting individual values; nodes fully outside are pruned; only crossing leaves are checked value by value. The result is a document-ID iterator or bitset with a **constant score** — points carry no term or document frequencies, so they cannot participate in relevance. Two consequences matter in production: points are multi-dimensional, which is how geo-points and range fields work, and points store no retrievable value, so sorting or aggregating a numeric still requires doc values.

code

java · 7 lines
java
Document doc = new Document();
// range-searchable, but not sortable
doc.add(new LongPoint("price_cents", 4999L));
// sortable / aggregatable column
doc.add(new NumericDocValuesField("price_cents", 4999L));
// returnable in results
doc.add(new StoredField("price_cents", 4999L));

go deeper

for a junior

Recall that Lucene handles numbers and dates with a different structure from text terms, and that range filters on them are cheap by design.

for a middle

Be ready to describe the tree traversal — fully-inside blocks accepted wholesale, outside blocks pruned, boundary blocks checked value by value — and why the result carries no score.

for a senior

Show the complement in production terms: points match, doc values retrieve, and a numeric field that is filtered and sorted needs both. Be ready to explain a sort failure on a point-only field.

for a principal

Own the storage-strategy angle: which numeric fields earn a points index, which earn doc values, and how cardinality-indifference changed the economics of time-series and geo data compared with the trie era.

## Why numbers do not belong in a term dictionary An inverted index is built for a vocabulary: a moderate number of distinct tokens, each matching many documents. Numbers invert that shape. Prices, timestamps and measurements are near-unique, and the dominant query is not equality but *range*: everything between two bounds. Expressed naively as terms, a range query over a million distinct values means a million term lookups. Lucene's pre-6.0 answer was a numeric trie: index each value several times at decreasing precision, so a range could be covered by a bounded set of coarse and fine terms. It worked, and the tuning knob for how many precision levels to index was a familiar sight in old schemas — but it multiplied the number of terms per value, inflating the term dictionary and slowing every merge. ## The BKD tree Since Lucene 6 numerics use **points**, backed by a **BKD tree** (block k-d tree): a balanced k-d tree that is bulk-loaded when a segment is written, and stored on disk in `.kdd` (leaf data), `.kdi` (inner-node index) and `.kdm` (metadata) — one set per segment, immutable like everything else in a segment. Each value is stored as a fixed-width big-endian byte array so that byte comparison equals numeric comparison. Points are inherently **multi-dimensional**: a single field can hold a value per dimension, which is how two-dimensional geo-points, and range field types encoded as intervals, are implemented on the same structure. Leaves hold a block of points and their document IDs; inner nodes hold split values and the bounding box of their subtree. ## How a range query executes Query execution is a tree traversal driven by an `IntersectVisitor` with three outcomes per node: - **CELL_OUTSIDE_QUERY** — the node's bounding box does not intersect the range; the whole subtree is pruned without reading it. - **CELL_INSIDE_QUERY** — the box lies entirely within the range; every document under the node matches, and the leaf's document IDs are collected in bulk without comparing individual values. - **CELL_CROSSES_QUERY** — the boundary passes through; descend, and at leaf level compare values one by one. Only the crossing cells — a thin frontier around the range boundary — pay per-value work. This is what makes a range over a broad slice of a large index cheap relative to term enumeration. The output is a document-ID iterator, usually materialised into a bitset for reuse. It carries **no scores**: points store no term frequency, no document frequency, no positions. A point range query is wrapped in a constant score, which is precisely why range predicates belong in filter context. ## Points and doc values are complements, not alternatives This is the single most useful practical point. Points answer *which documents fall in this range*. They cannot answer *what value does document 42 hold* — the tree is organised by value, not by document. Sorting, aggregating, or scripting on a numeric therefore reads **doc values**, an entirely separate columnar structure. A field indexed as a point but without doc values will filter and fail to sort; a field with doc values but no point will sort and be forced into a linear scan for range predicates. Lucene even exploits having both. `IndexOrDocValuesQuery` wraps a point-based range query together with a doc-values-based range predicate and decides at query time which to run: if the range is highly selective and the query leads with it, the BKD tree is the better entry point; if another clause already restricts the candidate set to a few documents, checking a doc value per candidate is cheaper than descending a tree. This cost-based choice happens per segment, per query. ## Operational notes - **Merging** rebuilds the tree for the merged segment. BKD trees are bulk-loaded structures, not incrementally rebalanced, so their cost lands during flush and merge, not during indexing of a single document. - **Precision.** Values are stored exactly at their encoded width, unlike the old trie's precision levels; there is no precision-step tuning knob any more. - **Cardinality behaviour.** Points are indifferent to how many distinct values exist — a billion unique timestamps are no worse than a thousand repeated ones, which is exactly the opposite of the term dictionary's behaviour and the reason the migration was such a win for time-series data. - **Exact-match queries** on a numeric are expressed as a degenerate range with equal bounds; there is no separate term lookup path. ## How to say it in an interview Inverted indexes are built for vocabularies and ranges over near-unique numbers are the worst case for them. Points move numerics to a value-ordered tree where a range is a box intersection, whole blocks are accepted or pruned without inspection, and the answer is an unscored document set. Then add the complement: points match, doc values retrieve, and a numeric field usually needs both.

  • If a numeric field is indexed as a point, why does sorting on it still need doc values?
    A BKD tree is organised by value: it answers which documents fall in a range, but there is no path from a document ID to its value without traversing the tree. Sorting and aggregating need per-document access, which is exactly what the columnar doc-values structure provides. Numeric fields normally carry both.
  • Why does a point range query contribute no relevance score?
    Points store only values and document IDs — no term frequency, no document frequency, no positions. There is nothing for a similarity to score with, so Lucene wraps the result in a constant score. In practice that is what you want: range predicates are filters, and keeping them unscored makes them cacheable.
  • What does IndexOrDocValuesQuery decide, and why is that decision made per query?
    It holds both a point-based and a doc-values-based form of the same range predicate and picks based on the estimated cost of the leading clause. If the range drives the query, descending the BKD tree wins; if another clause already narrowed the candidates to a handful, checking a doc value per candidate is cheaper. The right choice depends on the other clauses, so it cannot be fixed at index time.
  • How did the old numeric-trie approach differ in index size?
    It indexed each value several times at decreasing precision so ranges could be covered by a bounded number of terms. That multiplied terms per document, inflated the term dictionary, and made merges heavier. Points store each value once in a value-ordered tree and are indifferent to cardinality.

saying these in an interview costs you the question

  • Believing numerics are still just terms in the dictionary
  • Expecting a point range query to contribute to relevance
  • Assuming points make doc values unnecessary for sorting
  • Thinking the BKD tree is rebalanced on every document insert
  • Claiming high numeric cardinality bloats the points structure

context

resolving links…