Points & BKD range search

This section documents the current Apache Lucene 10.x line — Lucene 10 requires Java 21 — as published at the Apache Lucene documentation and Javadoc, which is the reference these pages are written and verified against. No specific patch version is pinned; examples target lucene-core 10.x and the companion modules. Some areas (the Panama foreign-memory / Vector API internals, codec file-format internals, and the nightly benchmark harness) are linked, not documented in depth.

This content was generated with the assistance of AI and should be verified against the official documentation before being relied on in production, as Lucene iterates quickly.

This section’s bibliography lists the reference material consulted while preparing these pages.

Numeric, date, and multi-dimensional range search in Lucene is served by a points index: a block KD-tree (BKD tree) that stores each field’s values in sorted, packed leaf blocks and answers range and set queries by visiting only the blocks that overlap the query. Points are a separate part of the segment from the inverted index and doc-values, written and queried through the *Point field and query classes below.

The BKD-tree points index

A point field contributes one or more fixed-width byte vectors per document (one dimension for a plain number, several for a geo point or a bounding-box corner). At flush the values are sorted and split recursively into leaf blocks of roughly 512 values; each internal node records the split dimension and split value so a range query can prune whole subtrees. Lookups are O(log n) to reach the first overlapping leaf, then a linear scan of the matching leaves — efficient for both high-selectivity ranges (few leaves) and full scans.

A 2-D BKD tree splitting points into leaf blocks

The *Point classes are in the org.apache.lucene.document package; see the IntPoint Javadoc (the class Javadoc documents the BKD encoding and the shared query factories that every sibling *Point type mirrors). Pre-6.x indexes used NumericRangeQuery over trie-encoded IntField/LongField terms in the inverted index; that approach and its precisionStep tuning were removed when points replaced it — do not use it on a modern index.

Indexing a point

// https://lucene.apache.org/core/10_0_0/core/org/apache/lucene/document/IntPoint.html
import org.apache.lucene.document.Document;
import org.apache.lucene.document.IntPoint;
import org.apache.lucene.document.LongPoint;
import org.apache.lucene.document.DoublePoint;

Document doc = new Document();
doc.add(new IntPoint("year", 1998));            // single dimension
doc.add(new LongPoint("published", epochMillis));
doc.add(new DoublePoint("price", 12.99));
doc.add(new IntPoint("location", gridX, gridY)); // 2 dimensions -> 2-D BKD tree
writer.addDocument(doc);

A Point field is *not stored and has no doc-values on its own — it only feeds the BKD tree. Add a StoredField if you need the value back, or a *DocValuesField (or use the convenience types below) if you need to sort, facet, or range-iterate on it.

newExactQuery / newRangeQuery / newSetQuery

Every *Point class exposes the same three static factories. Ranges are inclusive on both ends; use the type’s nextUp/nextDown helpers (or Math.addExact) to build a half-open range.

// https://lucene.apache.org/core/10_0_0/core/org/apache/lucene/document/LongPoint.html
import org.apache.lucene.document.IntPoint;
import org.apache.lucene.document.LongPoint;
import org.apache.lucene.search.Query;

// exact match
Query q1 = IntPoint.newExactQuery("year", 1998);

// inclusive range  1990 <= year <= 1999
Query q2 = IntPoint.newRangeQuery("year", 1990, 1999);

// open-ended range  year >= 2000
Query q3 = IntPoint.newRangeQuery("year", 2000, Integer.MAX_VALUE);

// half-open  start <= published < end
Query q4 = LongPoint.newRangeQuery("published", start, Math.subtractExact(end, 1));

// membership in a small set (OR of exact values, evaluated in one BKD pass)
Query q5 = IntPoint.newSetQuery("year", 1969, 1977, 1983, 1999);

For a multi-dimensional field, newRangeQuery takes a lower[] / upper[] pair — one bound per dimension, ANDed together (a bounding-box query):

// 2-D box:  x in [10..20] AND y in [30..40]
Query box = IntPoint.newRangeQuery(
        "location",
        new int[] { 10, 30 },
        new int[] { 20, 40 });

DoublePoint/FloatPoint sort by IEEE-754 order after a sortable-bit transform, so newRangeQuery handles negative values and infinities correctly without extra work.

IndexOrDocValuesQuery — points or doc-values, chosen per segment

A range that matches most of the index is cheaper to evaluate by iterating doc-values than by walking the BKD tree; a highly selective range is the opposite. Wrap both forms in IndexOrDocValuesQuery and Lucene estimates the cost per segment at query time and picks the lead iterator accordingly.

// https://lucene.apache.org/core/10_0_0/core/org/apache/lucene/search/IndexOrDocValuesQuery.html
import org.apache.lucene.document.IntPoint;
import org.apache.lucene.document.SortedNumericDocValuesField;
import org.apache.lucene.search.IndexOrDocValuesQuery;
import org.apache.lucene.search.Query;

Query points = IntPoint.newRangeQuery("year", 1990, 1999);
Query dv     = SortedNumericDocValuesField.newSlowRangeQuery("year", 1990, 1999);
Query year   = new IndexOrDocValuesQuery(points, dv);

This requires the field to be indexed both as a point and as numeric doc-values. The IntField/LongField types below do exactly that in one call, which is why they are the recommended way to add a range-searchable number.

Doc-values skip lists (DocValuesSkipper, 10.x)

Lucene 10 added an optional skip-list index over a numeric doc-values field: per block of documents it stores the min/max value (and doc range), so a doc-values range iteration can jump over blocks that cannot match instead of decoding every value. Enable it with the *Field convenience types or by passing a doc-values field configured for indexed sorting; query it through the same newSlowRangeQuery factories, which transparently use the skipper when present.

// https://lucene.apache.org/core/10_0_0/core/org/apache/lucene/index/DocValuesSkipper.html
import org.apache.lucene.document.NumericDocValuesField;

// add a numeric doc-value WITH a skip-list index over it
doc.add(NumericDocValuesField.indexedField("year", 1998));

See the 10.0 release notes entry for the skipper and the *Field types under "Changes in Lucene 10.0.0" ("Add a new DocValuesSkipper abstraction…​" / "Introduce IntField, LongField, FloatField, `DoubleField`").

IntField / LongField / FloatField / DoubleField

These convenience types add both a BKD point and a SortedNumericDocValuesField (with a skip list) for the same value in a single field instance — the value is then range-searchable, sortable, and facetable with no further fields to declare. They also provide newRangeQuery, newExactQuery, newSetQuery, and newSortField, each returning an IndexOrDocValuesQuery (or a skip-list-aware SortField) so the executor still chooses the cheaper access path per segment.

// https://lucene.apache.org/core/10_0_0/core/org/apache/lucene/document/IntField.html
import org.apache.lucene.document.IntField;
import org.apache.lucene.search.Query;
import org.apache.lucene.search.SortField;
import org.apache.lucene.search.SortedNumericSelector;

doc.add(new IntField("year", 1998, org.apache.lucene.document.Field.Store.NO));

Query range = IntField.newRangeQuery("year", 1990, 1999);  // IndexOrDocValuesQuery
Query exact = IntField.newExactQuery("year", 1998);
Query set   = IntField.newSetQuery("year", 1969, 1977, 1999);
SortField newest = IntField.newSortField("year", true, SortedNumericSelector.Type.MIN);

Reach for a bare IntPoint/LongPoint only when you are certain the field will never be sorted or faceted and want to save the doc-values space; otherwise prefer IntField/LongField.

Related pages