Lab LD4: DocValues Encodings

Background

DocValues are Lucene's column store — per-doc values laid out by field so that sorting, aggregations, faceting, and function scoring can read a whole column fast. The format is Lucene90DocValuesFormat, files .dvd (data) + .dvm (metadata). The cleverness is in the encodings: a NUMERIC field is stored as delta / GCD / table / monotonic depending on the data shape, and a SORTED/SORTED_SET field stores per-doc ordinals into a sorted term-bytes block. The DocValues chapter and the masterclass index explained these; here you observe them by indexing data that triggers each encoding and comparing .dvd sizes.

You will:

Enumerate NumericDocValues and SortedSetDocValues in code.
Reason about which numeric encoding a field got (delta vs GCD vs table vs monotonic) from the data shape.
Compare .dvd sizes for high- vs low-cardinality data — and watch the encoding choice show up as a size difference.
Connect this to how OpenSearch sorting/aggregations read DocValues and build global ordinals.

Why This Matters for Contributors

Every sort, every terms/stats aggregation, every doc['field'].value in a script reads DocValues. A contributor who knows that a low-cardinality keyword becomes cheap ordinals, that timestamps-at-second-granularity get GCD-compressed, and that high cardinality defeats the table encoding can explain "why is this agg slow / why did .dvd blow up / why does global-ordinal building dominate the profile." This is the structure behind the DocValues and fielddata deep-dive.

Prerequisites

JDK 17+, a lucene-core-*.jar. Set export LUCENE_CP=... (see Lab LD1).
Read index.md (DocValues section) and docvalues-columnar.md.

export LUCENE_CP="/path/to/lucene-core-9.x.x.jar"
export LUCENE_SRC="/path/to/lucene/lucene/core/src/java/org/apache/lucene"

Step-by-Step Tasks

Step 1 — Index numeric + keyword DocValues

DocValuesDump.java indexes three numeric fields (each shaped to trigger a different encoding) and a SortedSetDocValues keyword, then enumerates them.

import org.apache.lucene.document.*;
import org.apache.lucene.index.*;
import org.apache.lucene.store.*;
import org.apache.lucene.util.BytesRef;
import java.nio.file.*;
import java.util.Random;

public class DocValuesDump {
  static final int N = 10000;

  public static void main(String[] args) throws Exception {
    Path dir = Paths.get("ld4-dv");
    Random rnd = new Random(1);
    String[] countries = {"us", "gb", "fr", "de", "jp"};   // low cardinality -> ordinals + table
    try (Directory d = FSDirectory.open(dir)) {
      IndexWriterConfig cfg = new IndexWriterConfig();
      cfg.setUseCompoundFile(false);
      try (IndexWriter w = new IndexWriter(d, cfg)) {
        long ts = 1_700_000_000L;
        for (int i = 0; i < N; i++) {
          Document doc = new Document();
          // (a) GCD-friendly: timestamps at SECOND granularity * 1000 (all multiples of 1000).
          doc.add(new NumericDocValuesField("ts_millis", (ts + i) * 1000L));
          // (b) table-friendly: a status with very few distinct values.
          doc.add(new NumericDocValuesField("status", new int[]{200, 301, 404, 500}[rnd.nextInt(4)]));
          // (c) high-cardinality: a random long -> full-width delta, big.
          doc.add(new NumericDocValuesField("rand", rnd.nextLong()));
          // SORTED_SET keyword: low cardinality -> ordinals into a tiny term block.
          doc.add(new SortedSetDocValuesField("country",
              new BytesRef(countries[rnd.nextInt(countries.length)])));
          // a second country sometimes -> multi-valued
          if (rnd.nextBoolean())
            doc.add(new SortedSetDocValuesField("country",
                new BytesRef(countries[rnd.nextInt(countries.length)])));
          w.addDocument(doc);
        }
        w.forceMerge(1);
        w.commit();
      }

      try (DirectoryReader r = DirectoryReader.open(d)) {
        for (LeafReaderContext ctx : r.leaves()) {
          LeafReader lr = ctx.reader();

          // Enumerate a NumericDocValues column (first 5 docs).
          NumericDocValues status = lr.getNumericDocValues("status");
          System.out.print("status (first 5): ");
          for (int i = 0; i < 5 && status.advanceExact(i); i++) System.out.print(status.longValue() + " ");
          System.out.println();

          // Enumerate the SortedSetDocValues: ordinals + resolve to bytes.
          SortedSetDocValues country = lr.getSortedSetDocValues("country");
          System.out.println("country valueCount (distinct ordinals) = " + country.getValueCount());
          for (long ord = 0; ord < country.getValueCount(); ord++)
            System.out.println("  ord " + ord + " -> '" + country.lookupOrd(ord).utf8ToString() + "'");
          // First doc's ordinal set:
          if (country.advanceExact(0)) {
            System.out.print("  doc 0 ords: ");
            for (int i = 0; i < country.docValueCount(); i++) System.out.print(country.nextOrd() + " ");
            System.out.println();
          }
        }
      }
    }
  }
}

javac -cp "$LUCENE_CP" DocValuesDump.java
java  -cp "$LUCENE_CP:." DocValuesDump
ls -la ld4-dv/    # _0.dvd _0.dvm

Expected (ordinals are the sorted term order, so de < fr < gb < jp < us):

status (first 5): 404 200 500 301 200
country valueCount (distinct ordinals) = 5
  ord 0 -> 'de'
  ord 1 -> 'fr'
  ord 2 -> 'gb'
  ord 3 -> 'jp'
  ord 4 -> 'us'
  doc 0 ords: 2 4

country stored five distinct ordinals 0..4 mapping to the sorted country bytes; each doc stores a small set of ordinals, not the strings. That is the whole SORTED_SET trick: per-doc ints + one shared, sorted term block.

Step 2 — Reason about which numeric encoding each field got

The writer (Lucene90DocValuesConsumer.writeNumericField) inspects each column and picks an encoding. Map your three fields:

Field	Data shape	Likely encoding	Why
`ts_millis`	all multiples of 1000, increasing	GCD (factor 1000) then delta	dividing by gcd=1000 drops ~10 bits/value
`status`	4 distinct values	table	store a 2-bit ordinal into a `{200,301,404,500}` table
`rand`	random 64-bit	delta at near-full width	no common factor, no small table → can't compress much

Read the decision code:

grep -n "gcd\|GCD\|writeNumericField\|uniqueValues\|TABLE\|MONOTONIC\|minMax\|numBitsPerValue" \
  "$LUCENE_SRC/codecs/lucene90/Lucene90DocValuesConsumer.java" | head -30
grep -n "DELTA_COMPRESSED\|GCD_COMPRESSED\|TABLE_COMPRESSED\|MONOTONIC_COMPRESSED\|SPARSE_COMPRESSED\|CONST_COMPRESSED" \
  "$LUCENE_SRC/codecs/lucene90/Lucene90DocValuesFormat.java"

The consumer computes min, max, the GCD of all values, and the count of unique values, then chooses: a tiny unique-set → table; a non-trivial GCD → divide it out; otherwise → delta at bitsRequired(max-min) bits. Monotonic block encoding (a per-block slope + small residuals) is used for (near-)increasing sequences and for the addresses that index variable-length data and sparse jump tables.

Step 3 — High- vs low-cardinality: compare .dvd contributions

The dramatic demonstration: build two indices that differ only in the cardinality of one numeric field, and watch .dvd change. Cardinality.java:

import org.apache.lucene.document.*;
import org.apache.lucene.index.*;
import org.apache.lucene.store.*;
import java.nio.file.*;
import java.util.Random;

public class Cardinality {
  static final int N = 200_000;
  public static void main(String[] args) throws Exception {
    build("ld4-low",  true);    // low cardinality: value in {0..3}
    build("ld4-high", false);   // high cardinality: full-range random long
  }
  static void build(String name, boolean low) throws Exception {
    Random rnd = new Random(9);
    try (Directory d = FSDirectory.open(Paths.get(name))) {
      IndexWriterConfig cfg = new IndexWriterConfig();
      cfg.setUseCompoundFile(false);
      try (IndexWriter w = new IndexWriter(d, cfg)) {
        for (int i = 0; i < N; i++) {
          Document doc = new Document();
          long v = low ? rnd.nextInt(4) : rnd.nextLong();
          doc.add(new NumericDocValuesField("v", v));
          w.addDocument(doc);
        }
        w.forceMerge(1);
        w.commit();
      }
    }
  }
}

javac -cp "$LUCENE_CP" Cardinality.java
java  -cp "$LUCENE_CP:." Cardinality

echo "LOW  cardinality .dvd:"; du -b ld4-low/_*.dvd
echo "HIGH cardinality .dvd:"; du -b ld4-high/_*.dvd

Expected: the low-cardinality .dvd is far smaller. With only 4 distinct values, the writer uses the table encoding — 2 bits/doc, so ~~200000 × 2 / 8 = 50 KB. The high-cardinality random longs can't be tabled or GCD'd; they need near-full width (~~200000 × 8 = 1.6 MB). Same doc count, ~30× size difference — entirely the encoding choice the data shape forced.

LOW  cardinality .dvd:   ~55_000 bytes
HIGH cardinality .dvd: ~1_600_000 bytes

Step 4 — Inspect with CheckIndex

cp -r ld4-dv ld4-copy
java -cp "$LUCENE_CP" org.apache.lucene.index.CheckIndex ld4-copy -verbose 2>&1 \
  | grep -iA3 "test: docvalues\|docvalues"

The DocValues test reads back every column and validates the .dvd/.dvm checksums. It confirms the field types (NUMERIC, SORTED_SET) and value counts.

Step 5 — Connect to OpenSearch sorting, aggregations, global ordinals

Local (per-segment) ordinals are not directly comparable across segments — us might be ordinal 4 in one segment and 3 in another. For a shard-wide terms aggregation OpenSearch builds global ordinals: a unified ordinal space across all segments of a shard, with per-segment maps from local→global ordinal. The agg then counts by global ordinal (cheap ints) and resolves to bytes once at the end.

flowchart TD
    Seg0["segment 0: local ords {de,fr,gb,jp,us}"] --> GO["build global ordinals (shard-wide)"]
    Seg1["segment 1: local ords (different order)"] --> GO
    GO --> Map["per-segment local→global ordinal maps"]
    Map --> Agg["terms agg counts by GLOBAL ordinal"]
    Agg --> Resolve["resolve top buckets' ordinals → bytes once"]

# In an OpenSearch checkout, the global-ordinals + fielddata machinery:
grep -rn "GlobalOrdinals\|globalOrdinal\|buildGlobalOrdinals\|OrdinalMap" \
  server/src/main/java/org/opensearch/index/fielddata/ 2>/dev/null | head
# Lucene's cross-segment ordinal map:
grep -rn "class OrdinalMap" "$LUCENE_SRC/index/OrdinalMap.java"

A sort on a numeric field reads NumericDocValues (the column you enumerated).
A terms agg on a keyword reads SortedSetDocValues and (for the shard result) global ordinals.
A stats/avg agg reads numeric DocValues directly.

The full story — fielddata vs DocValues, when global ordinals are (re)built, and the heap cost — is in the DocValues and fielddata deep-dive.

Deliverables

DocValuesDump.java — enumerates NumericDocValues and SortedSetDocValues; prints ordinals → bytes and a doc's ordinal set.
The reasoning table mapping ts_millis/status/rand to GCD/table/delta, backed by the Lucene90DocValuesConsumer grep.
Cardinality.java + a du -b showing the low-cardinality .dvd is ~30× smaller than high-cardinality.
A CheckIndex DocValues-test capture.
The global-ordinals explanation + the OpenSearch grep.

Troubleshooting

Symptom	Cause / fix
`getNumericDocValues` returns null	Field name typo, or you used `StoredField` not `NumericDocValuesField`.
`advanceExact(i)` is false for low i	That doc has no value for the field (sparse). Iterate by `nextDoc()` instead.
Ordinals not in the order I expect	Ordinals are the sorted term order (`de<fr<gb<jp<us`), not insertion order.
`.dvd` sizes nearly equal low vs high	`N` too small to amortize the header; raise `N` to 200k+.
`IllegalArgumentException: cannot change DocValues type`	A field can't mix DV types across docs; use one type per field name.
`docValueCount`/`nextOrd` API mismatch	Older Lucene used `NO_MORE_ORDS` sentinel loops; newer uses `docValueCount()`. Adapt to your jar.

Expected Output

A clear ordinal dump for the keyword column, a defensible mapping of each numeric field to its encoding, and a ~30× .dvd size gap between low- and high-cardinality data that you can explain from the table-vs-delta choice — plus the global-ordinal bridge to OpenSearch aggregations.

Stretch Goals

Prove GCD. Index ts_millis (multiples of 1000) vs the same values +1 (no common factor); compare .dvd — the GCD path should shrink the multiples.
Monotonic. Index a strictly increasing long (i) field; reason about (and, via CheckIndex/source, confirm) the monotonic block encoding's slope+residual.
Sparse field + jump table. Add a DocValues field to only 1% of docs; inspect the IndexedDISI jump-table path (grep IndexedDISI "$LUCENE_SRC/codecs/lucene90/").
Global ordinals in OpenSearch. Index a 2-segment keyword index in OpenSearch, run a terms agg, and use _cluster/stats / the field-data API to see global ordinal memory; force-merge to 1 segment and observe it drop.
SORTED vs SORTED_SET. Switch country to SortedDocValuesField (single-valued) and compare the API (ordValue() vs the ordinal set) and .dvd size.

Coding Exercises

These exercises turn "observe the encoding choice" into graded code. Each is a standalone Java program or JUnit test against the Lucene jars on $LUCENE_CP — no Gradle. Build on DocValuesDump.java and Cardinality.java.

(warm-up) Assert the ordinal mapping in a test. Wrap Step 1 in a JUnit test OrdinalTest that asserts country.getValueCount()==5 and that lookupOrd(0..4) returns exactly {de,fr,gb,jp,us} in that order. This pins the "ordinals are sorted term order, not insertion order" invariant.
(warm-up) Round-trip every numeric column. Write NumericRoundTrip that indexes the three numeric fields, then iterates each NumericDocValues with nextDoc() and asserts the read-back value equals what you wrote for every doc (keep a parallel long[]). Green test = the encoder/decoder is lossless regardless of which encoding it chose.
(core) Prove the GCD path shrinks the file. Extend the GCD stretch goal into a test GcdShrinkTest: build index A with ts_millis = multiples of 1000 and index B with the same values +1 (breaking the common factor). Assert dvd(A) < dvd(B) (read both .dvd with Files.size). In a comment, cite the gcd/GCD_COMPRESSED decision line you grep in Lucene90DocValuesConsumer.java.
(core) Drive the low-vs-high cardinality gap as an assertion. Turn Cardinality.java into a test CardinalityGapTest that builds both indices and asserts dvd(high) > 10 × dvd(low) (your data should show ~30×). Then add a third build with value = i (strictly increasing) and reason in a comment which encoding it gets — confirm against the MONOTONIC_COMPRESSED constant you grep.
(core) Decode a SORTED_SET doc's ordinal set programmatically. Write OrdSetDecode that, for the first 10 docs, collects each doc's ordinal set via advanceExact + docValueCount + nextOrd, resolves them to strings with lookupOrd, and asserts the resolved strings are a subset of {de,fr,gb,jp,us}. This exercises the exact per-doc decode path a terms agg uses before global ordinals.
(advanced) Advanced challenge — build a cross-segment OrdinalMap and verify a local→global mapping. Produce a 2-segment keyword index (index a batch, commit(), index another batch, commit(), without force-merge so two segments survive). Locate the API: grep -rn "class OrdinalMap\|OrdinalMap.build\|getGlobalOrds" "$LUCENE_SRC/index/OrdinalMap.java". Write GlobalOrds that collects each segment's SortedSetDocValues, builds an OrdinalMap over them, and asserts that the same country string maps to the same global ordinal across both segments even though its local ordinal differs. Deliverable: a JUnit test that prints, per segment, local ord → global ord for "us" and asserts the global ords are equal. This is exactly what OpenSearch builds for a shard-wide terms agg.

Issues to Practice On

DocValues encodings live in apache/lucene (Lucene90DocValuesConsumer, Lucene90DocValuesFormat, OrdinalMap); the global-ordinals consumer lives in opensearch-project/OpenSearch (server/.../index/fielddata). Apache workflow: GitHub issues + PRs, a CHANGES.txt entry — no DCO. Find work with:

gh label list --repo apache/lucene | grep -iE "good first|core/|new feature"   # confirm taxonomy (labels move; check the tracker)
gh issue list --repo apache/lucene --label "good first issue" --state open
gh issue list --repo apache/lucene --search "DocValues OR ordinals OR OrdinalMap in:title,body" --state open
# OpenSearch-side (global ordinals / fielddata / aggregations):
gh issue list --repo opensearch-project/OpenSearch --label "good first issue" --state open
gh issue list --repo opensearch-project/OpenSearch --label "Search:Aggregations" --state open

Representative issue patterns:

DocValues encoding correctness/size. "Field with a common factor not GCD'd," "monotonic block residuals wrong." Approach: build a synthetic column that triggers the encoding, add a size/round-trip test, locate the writer via rg "writeNumericField\|GCD_COMPRESSED", fix.
Global-ordinal memory/rebuild (OpenSearch side). "Global ordinals rebuilt too often / dominate heap." Approach: reproduce with a multi-segment keyword index + terms agg, inspect via the field-data API, locate buildGlobalOrdinals via rg in server/.../index/fielddata, fix + test.

Planted-bug drill. In a copy of DocValuesDump.java, change the country field to a SortedDocValuesField (single-valued) but keep the multi-valued add (two country values for some docs). Run it: you should hit IllegalArgumentException: DocValuesField "country" appears more than once. Now harden: add assertThrows for that case, then revert to SortedSetDocValuesField. Plant a subtler one in OrdinalTest (exercise 1): assert the order is insertion order (us,gb,...) and watch it go red — the failure is the lesson that ordinals are sorted term order.

Etiquette: claim the issue first, reproduce before coding; Apache Lucene PRs need a test + CHANGES.txt (no DCO), OpenSearch PRs need a test + CHANGELOG entry + DCO Signed-off-by (git commit -s). See community-interaction.md.

Validation: prove you understand this

From your dump, list the country ordinals and their bytes, and explain why the order is de,fr,gb,jp,us and what doc 0's ordinal set means.
Name the four numeric encodings and assign ts_millis/status/rand to one each, justifying from the data shape.
Explain your low- vs high-cardinality .dvd size gap in terms of the table vs delta encoding, with the rough byte arithmetic.
Define an ordinal and explain how SORTED_SET stores per-doc values as ordinals + a shared sorted term block.
Explain global ordinals: why local ordinals aren't comparable across segments, what OrdinalMap builds, and how a terms agg uses it.
Say which DocValues structure each of these reads: a numeric sort, a keyword terms agg, an avg agg, and a sparse field's advanceExact.

When you can do all six, you have decoded every major Lucene on-disk format. Return to the masterclass index and re-do its seven-point validation — you should now be able to take any segment file, read its header, name its codec, and reason about its bytes.

Open-Source Engineer & Contributor