Points and BKD Trees

The inverted index is brilliant at "which docs contain this term" and useless at "which docs have a number between 30 and 70." Range queries, geo queries, and multi-dimensional lookups need a spatial structure, not a postings list. Lucene's answer is points: values indexed into a BKD tree (block KD-tree), a disk-resident, write-once KD-tree that answers range and nearest-region queries efficiently. Every numeric range, every date range, and every geo_point bounding-box query in OpenSearch is a BKD-tree traversal underneath.

This is the Lucene layer beneath the numeric and geo parts of Mapping and Analysis: when that chapter says a long, date, or geo_point field is "indexed," this is the index it builds.

After this chapter you can: explain why points replaced the old numeric trie terms; describe the BKD tree's structure and the BKDWriter/BKDReader split; use PointValues and the IntPoint/LongPoint/DoublePoint field types; trace a range query through a BKD traversal; and connect it to OpenSearch numeric, date, and geo_point queries.

Why points replaced numeric trie terms

Before points (Lucene < 6), numeric range queries were a hack on the inverted index: a number was indexed at multiple precisions as a set of terms (NumericRangeQuery / "trie" fields), and a range query OR'd together the terms covering it. It worked but was costly — it bloated the terms dictionary with synthetic terms, it didn't generalize past one dimension, and range queries expanded into large boolean queries.

Points (PointValues, the BKD format) replaced all of that with a purpose- built structure:

The lesson generalizes: when the access pattern is "values in a region," you want a spatial tree, not an inverted list. Points are how Lucene serves numeric, date, IP, and geo simultaneously with one structure.

grep -rn "class PointValues\|class IntPoint\|class LongPoint\|class DoublePoint\|class LatLonPoint" \
  lucene/core/src/java/org/apache/lucene/document/ \
  lucene/core/src/java/org/apache/lucene/index/PointValues.java

The BKD tree

A KD-tree recursively partitions k-dimensional space, splitting on one dimension at a time. Lucene's BKD variant ("block KD") is built for disk: it groups points into fixed-size leaf blocks (e.g. ~512 points), builds a balanced tree of split nodes over those blocks, and writes the whole thing once, immutably, into the segment. It is bulk-loaded — points are sorted and the tree built bottom-up — which is why it's fast to build and tight on disk, at the cost of being write-once (perfectly fine: segments are immutable anyway).

Structure:

• Leaf blocks hold the actual point values plus the doc IDs that own them.
• Inner nodes store split values: "left subtree has dim-d < v, right has ≥ v," plus the min/max bounding box of each subtree.
• A query descends, and at each node uses the subtree's bounding box to prune: if a subtree's box is entirely inside the query range, accept all its docs without inspecting them (CELL_INSIDE_QUERY); if entirely outside, skip it (CELL_OUTSIDE_QUERY); if it straddles, recurse (CELL_CROSSES_QUERY).

flowchart TD
    Root["root: bbox of all points"] -->|"crosses query"| N1["split on dim x @ v1"]
    N1 -->|"inside query -> accept all"| L1["leaf block (512 pts) all matched"]
    N1 -->|"crosses"| N2["split on dim y @ v2"]
    N2 -->|"outside -> skip"| L2["leaf block (pruned)"]
    N2 -->|"crosses -> scan"| L3["leaf block: test each point"]

grep -rn "class BKDWriter\|class BKDReader\|enum Relation\|CELL_INSIDE_QUERY\|CELL_OUTSIDE_QUERY\|CELL_CROSSES_QUERY" \
  lucene/core/src/java/org/apache/lucene/util/bkd/ \
  lucene/core/src/java/org/apache/lucene/index/PointValues.java

Note: The three-way relation (INSIDE/OUTSIDE/CROSSES) is the whole trick. A range query that covers a dense region accepts huge subtrees wholesale and only scans the boundary blocks. That's why a numeric range over a large matching set is cheap — it doesn't enumerate matches, it accepts subtrees.

BKDWriter and BKDReader

The format splits, as most Lucene structures do, into a writer (index time) and a reader (query time), via the PointsFormat sub-codec (see Segments and Codecs).

The query model is a visitor: you give PointValues.intersect an IntersectVisitor. Lucene walks the tree, calling your compare(minPacked, maxPacked) at each node to get a Relation (so it can prune), and visit(docID) for every point inside a fully-matched cell (or visit(docID, packedValue) for straddling leaf blocks where it must test each value). This is exactly how IntPoint.newRangeQuery and friends are implemented.

grep -rn "interface IntersectVisitor\|void intersect\|Relation compare\|void visit" \
  lucene/core/src/java/org/apache/lucene/index/PointValues.java

The point field types

You index a point by adding a *Point field to a document; you query it with that type's static factory methods. The values are stored as packed byte arrays (big-endian, so byte comparison equals numeric comparison) — that uniform encoding is what lets one BKD implementation serve ints, longs, doubles, and geo.

// Index side:
doc.add(new LongPoint("created", epochMillis));      // BKD-indexed
doc.add(new IntPoint("price", 4200));

// Query side (Lucene):
Query q = LongPoint.newRangeQuery("created", lo, hi);          // a date range
Query g = LatLonPoint.newDistanceQuery("loc", lat, lon, 5000); // 5km radius

grep -rn "newRangeQuery\|newDistanceQuery\|newBoxQuery\|newPolygonQuery" \
  lucene/core/src/java/org/apache/lucene/document/LongPoint.java \
  lucene/core/src/java/org/apache/lucene/document/LatLonPoint.java

Note: A field is often indexed both as a point (for range queries) and as doc values (for sorting/aggregations — see DocValues). They are two different structures answering two different questions about the same value. OpenSearch numeric fields enable both by default.

How OpenSearch numeric, date, and geo queries use points

The OpenSearch field mappers build the matching Lucene point field, and the query builders produce the matching point query. Walk it from the mapper:

# Numeric & date fields create LongPoint/IntPoint/etc:
grep -rn "LongPoint\|IntPoint\|DoublePoint\|newRangeQuery\|PointRangeQuery" \
  server/src/main/java/org/opensearch/index/mapper/NumberFieldMapper.java \
  server/src/main/java/org/opensearch/index/mapper/DateFieldMapper.java

# geo_point uses LatLonPoint:
grep -rn "LatLonPoint\|newBoxQuery\|newDistanceQuery\|GeoPointFieldMapper\|LatLonShape" \
  server/src/main/java/org/opensearch/index/mapper/GeoPointFieldMapper.java

So a range: { created: { gte: "now-1d" }} is, four layers down, a LongPoint.newRangeQuery that BKDReader answers by pruning subtrees of the date BKD tree. Knowing this lets you reason about why a range over a high- cardinality timestamp on a huge index is still fast (subtree pruning) and why an over-broad range that matches most docs is not (it accepts nearly everything and the cost moves to whatever consumes the matches).

flowchart TD
    OS["range: {created: gte..lte}"] --> QB["RangeQueryBuilder (OpenSearch)"]
    QB --> LQ["LongPoint.newRangeQuery (Lucene)"]
    LQ --> PV["PointValues.intersect(visitor) per segment"]
    PV --> BKD["BKDReader walks tree, prunes via Relation"]
    BKD --> Hits["matched docIDs -> DocIdSetIterator"]

Reading exercise

# 1. The point types and the read API.
grep -rn "class IntPoint\|class LongPoint\|class LatLonPoint\|class PointValues" \
  lucene/core/src/java/org/apache/lucene/document/ \
  lucene/core/src/java/org/apache/lucene/index/PointValues.java

# 2. The BKD writer/reader and the prune relation.
grep -rn "class BKDWriter\|class BKDReader\|enum Relation\|CELL_CROSSES_QUERY" \
  lucene/core/src/java/org/apache/lucene/util/bkd/ \
  lucene/core/src/java/org/apache/lucene/index/PointValues.java

# 3. The visitor model.
grep -rn "interface IntersectVisitor\|Relation compare\|void visit" \
  lucene/core/src/java/org/apache/lucene/index/PointValues.java

# 4. The range query implementation.
grep -rn "class PointRangeQuery" lucene/core/src/java/org/apache/lucene/search/

# 5. OpenSearch mappers that build points.
grep -rn "LongPoint\|IntPoint\|LatLonPoint\|newRangeQuery" \
  server/src/main/java/org/opensearch/index/mapper/NumberFieldMapper.java \
  server/src/main/java/org/opensearch/index/mapper/GeoPointFieldMapper.java

# 6. See the point files in a real shard.
find /path/to/shard/index -name "*.kdd" -o -name "*.kdi" -o -name "*.kdm"

Answer:

1. How did Lucene do numeric ranges before points, and name three concrete problems that approach had.
2. Describe the BKD tree: leaf blocks, split nodes, and the bounding boxes that enable pruning. Why is it bulk-loaded and write-once?
3. Explain the three-way Relation (INSIDE/OUTSIDE/CROSSES) and how it makes a range over a large matching set cheap.
4. Write (from memory) how you'd query a date range with LongPoint, and explain how date becomes a LongPoint.
5. Walk a geo_distance query from the OpenSearch builder to LatLonPoint to BKDReader.
6. Why is a numeric field often indexed as both a point and doc values? What does each answer?

Common bugs and symptoms

Validation: prove you understand this

1. Contrast numeric trie terms vs points with a table, and state the one-sentence reason points are strictly better for ranges.
2. Draw a small BKD tree with leaf blocks and bounding boxes, and trace a range query showing one INSIDE, one OUTSIDE, and one CROSSES decision.
3. Explain the BKDWriter/BKDReader/PointValues/IntersectVisitor roles and which files each produces or reads.
4. Match four OpenSearch query types (numeric range, date range, geo bbox, geo distance) to their Lucene point factory methods.
5. Explain why a numeric field carries both a point index and doc values, naming the question each answers.
6. Given a slow geo_distance query on a large index, explain whether BKD pruning can help and what you'd change.