All findings · Lucene finding · LFV-1140 · stringsorter-missing-sentinel-below-long-global-ords

Index sort with STRING_LAST: a merge over more than 2^31 distinct values puts the largest values on the wrong side of documents without a value

A STRING_LAST index sort's merge keys documents without a value at Integer.MAX_VALUE (2,147,483,647) and documents with one at their 64-bit global ordinals. When one addIndexes(CodecReader...) call merges more than 2^31 distinct values, the largest values silently land on the wrong side of the documents without a value (after them ascending, before them with reverse=true); since 8.2.0.

Summary

Priority
Low, rank 980A STRING_LAST index sort merged through addIndexes(CodecReader...) silently places documents without a value ahead of the documents with the largest values, against the declared sort, in every release since 8.2.0. It only happens when the inputs of one call hold at least 2^31 distinct sort values, deleted documents included, so it is an extreme-scale, contrived case.
Impact
data corruption
Since
8.2.0 (2019), LUCENE-8900introduced 2019-07-09 · about 7 years
Affected
every release from 8.2.0 to 10.6.0 and main; not fixed upstream
Status
documented
Found by
semi-formal: a proof-obligation audit of IndexSorter.StringSorter's merge-key contract, witnessed by an executable repro

AI-assisted page: this finding was first signalled by a semi-formal check (an exact check of the real jar, or a modelling hypothesis that a tool then witnessed) and then checked with AI tools; the checks it went through, and what each found, are under Prior reports, history and checks. Not yet triaged by a human. Snapshot of 2026-11-06.

The finding in 30 seconds

The merge keys mix two widths: a document with a value gets its global ordinal as a long, a document without one gets the int sentinel Integer.MAX_VALUE. Once global ordinals reach 2^31 - 1, the sentinel is no longer the largest key.

Background: how an index-sorted merge orders documents

  1. With an index sort, every segment is written in sort order. For a STRING field, a segment keeps each distinct value once in a sorted dictionary and numbers it (its segment ordinal); documents are compared by these numbers.
  2. Segment ordinals mean nothing across segments, so a merge builds an OrdinalMap that numbers the distinct values of all inputs together: the global ordinals, stored as long.
  3. Each document gets a long merge key, its global ordinal, and the merge interleaves the inputs by these keys. For STRING_LAST, a document without a value needs a key above every value.
A four-step picture of an index-sorted merge on a toy example: two segments sorted by the string field s (fig, pear and a document without a value; apple, kiwi); a key step that numbers all values in sort order (apple 0, fig 1, kiwi 2, pear 3, the numbers coming from an OrdinalMap) and gives the document without a value the key Integer.MAX_VALUE, ringed in red as the place of the bug; a merge that takes the smallest key next; and the merged segment apple, fig, kiwi, pear, then the document without a value. Below, an orange Expected panel shows the missing key beyond the last global ordinal, and a blue Actual panel with a red cross shows that with more than 2^31 - 1 values in one merge the last global ordinals pass Integer.MAX_VALUE, so the missing key falls inside the range.
How a merge keeps a string index sort, and where the key of a document without a value can fall below the largest global ordinals. Generated with AI, checked against the code.
Diagram of the bug: two sorted segments are merged with an index sort on field s, STRING_LAST. Segment 1 has 2^30 + 1 values with global ordinals 0 to 1,073,741,824 and a live document without a value; segment 2 has 2^30 + 1 larger values with global ordinals 1,073,741,825 to 2,147,483,649 and a live document with the largest value. The merge key of the document without a value is Integer.MAX_VALUE, 2,147,483,647, which is smaller than the key of the document with the largest value, 2,147,483,649, so the merged segment puts the document without a value at doc 0, before the document with a value.
Merge keys on one number line: both inputs' values get global ordinals 0 to 2,147,483,649, but a document without a value gets 2,147,483,647, the int maximum, below the largest values. So this ascending merge places it ahead of them, although STRING_LAST says last; with reverse=true the largest values would move ahead of it instead. Select the still to open it at full size. Generated with AI, checked against the code.

The finding, step by step

  1. Sort an index by a string field with documents without a value last: new SortField("s", SortField.Type.STRING, false, SortField.STRING_LAST). Within one segment this works.
  2. Merge two indexes sorted this way with one addIndexes(CodecReader...) call. The merge numbers every distinct s value of all inputs, counting values that only deleted documents still hold: with 2^30 + 1 values per input, these global ordinals run from 0 to 2,147,483,649.
  3. You expect each document without a value to get a merge key above every value, so it still sorts last.
  4. Instead its key is the int Integer.MAX_VALUE, 2,147,483,647, which is below the key of the document with the largest value, 2,147,483,649. The merged segment puts the document without a value first, at doc 0 (this ascending example; with reverse=true, where STRING_LAST puts documents without a value first, the same keys move the largest values ahead of them).
  5. No error, with assertions on or off; only CheckIndex at level 2 or higher notices. An index's own merges never see that many values: it takes about 2^31 source documents.

Who is affected

The route shown to reach it: applications that opt into a STRING_LAST index sort on a STRING field and call addIndexes(CodecReader...) on two or more sorted indexes whose dictionaries, deleted documents' values included, together hold more than 2^31 distinct values while the live total fits under MAX_DOCS. An index's own merges cannot get there; STRING_FIRST is unaffected.

Mechanism, terms and numbers397 words

For an index sort on a STRING field, IndexSorter.StringSorter gives each document a long merge key: its global ordinal from an OrdinalMap over all inputs' dictionaries, or, for a document without a value and STRING_LAST, the int sentinel Integer.MAX_VALUE. Global ordinals are not bounded by the int range, so at 2^31 distinct values in one merge the largest value ties with the sentinel (reader order decides), and with more than 2^31 the largest values get keys above it: the merged segment silently places documents without a value ahead of them (ascending sort; with reverse=true, where STRING_LAST puts documents without a value first, the same keys move the largest values ahead of them), against its declared sort. The in-segment comparator of the same class stays correct, because segment ordinals are ints. The route shown to get there is addIndexes(CodecReader...) over heavily deleted sorted indexes of about 2^31 documents in total; an index's own merges cannot, and STRING_FIRST is not affected. In 7.6.0-8.1.1 the same input threw ArithmeticException (Math.toIntExact, LUCENE-8592); LUCENE-8900 made the keys long in 8.2.0 and dropped that guard. Low priority; the fix is a long sentinel.

The mechanism (main 5adff78bb168, IndexSorter.java)

  1. getComparableProviders builds OrdinalMap.build(null, values, PackedInts.DEFAULT) over every input's SortedDocValues, deleted documents' values included (:487); getGlobalOrds returns LongValues (:497).
  2. It sets final int missingOrd = Integer.MAX_VALUE for STRING_LAST, else Integer.MIN_VALUE (:488-493).
  3. A document with a value returns globalOrds.get(readerValues.ordValue()), a long; a document without one returns missingOrd, widened to 2,147,483,647 (:498-506).
  4. The keys are cached per reader and compared with Long.compare (:98-111); MultiSorter orders the merged documents by that comparison (MultiSorter.java:88-97), and MergeState.java:223 takes the merge's doc maps from MultiSorter.sort.
  5. The in-segment getDocComparator (:512-528) fills an int[] with the same sentinel and int segment ordinals, which always stay below Integer.MAX_VALUE, so inside one segment the order is right. Only the merge keys disagree with it.

The numbers in the repro

segment 1segment 2
dictionary2^30 + 1 terms, global ordinals 0 .. 1,073,741,8242^30 + 1 terms, global ordinals 1,073,741,825 .. 2,147,483,649
live documentno value: key 2,147,483,647the largest value: key 2,147,483,649

Since 2,147,483,647 < 2,147,483,649, the document without a value is merged first. STRING_FIRST is not affected: Integer.MIN_VALUE is below every global ordinal (all >= 0).

Exposure and likelihood315 words
  • How the input is legal. addIndexes(CodecReader...) reserves only the sum of live numDocs() (IndexWriter.java:3275-3297); OneMerge(CodecReader...) sets totalMaxDoc to that sum (MergePolicy.java:245-255); the default findMerges(CodecReader...) puts all inputs in one merge (MergePolicy.java:616-619); with an index sort the inputs are not wrapped (IndexWriter.java:3548-3566). The OrdinalMap still counts values that only deleted documents hold, so heavily deleted sources of about 2^30 documents each can pass 2^31 global ordinals while the merged index fits MAX_DOCS. A scale model with the document limit lowered to 10 showed exactly this accounting: addIndexes(Directory...) rejected the inputs, addIndexes(CodecReader...) accepted them, and the largest live key, 11, counted the deleted documents' values.
  • Not reachable otherwise. An index's own merges cannot get there for a single-valued STRING sort (its maxDoc is at most MAX_DOCS < 2^31 - 1). addIndexes(Directory...) (IndexWriter.java:3124-3144), which the bundled IndexMergeTool uses, counts maxDoc and rejects such inputs. The open PR #16847 (long global doc ids) may widen the reach to ordinary merges, depending on its final design.
  • Effect. Live documents without a value sort ahead of the documents with the largest values (ascending sort; with reverse=true, where STRING_LAST puts documents without a value first, the same keys move the largest values ahead of them); either way the merged segment contradicts its declared sort, and document contents are unchanged. CheckIndex at level 2 or higher reports segment has indexSort=<string: "s"> missingValue=SortField.STRING_LAST but docID=0 sorts after docID=1; the default level 1 reports the index clean. Code that relies on the index sort, such as early termination on that sort, could return wrong top hits (by reading, not executed).
  • Default vs opt-in. Opt-in: an index sort, STRING_LAST, and the expert addIndexes(CodecReader...) API. Assertions on or off make no difference.
  • Likelihood: contrived. About 2^31 source documents (an estimate: hundreds of GB) in one call; no public report found since 8.2.0 (2019).

Minimal repro

One JUnit test method: two one-document segments whose SortedDocValuesProvider gives each 2^30 + 1 terms, 2^31 + 2 global ordinals in all. It asks StringSorter for its merge keys and checks that the document without a value sorts after the one with the largest value. Deterministic, single thread; needs a 2 GB heap.

TestStringSorterMissingLast.java (one JUnit test, lucene/core tests)114 lines
/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.lucene.index;

import java.util.List;
import org.apache.lucene.document.Document;
import org.apache.lucene.search.SortField;
import org.apache.lucene.store.Directory;
import org.apache.lucene.tests.util.LuceneTestCase;
import org.apache.lucene.util.BytesRef;

public class TestStringSorterMissingLast extends LuceneTestCase {

  public void testMissingKeyAboveGlobalOrdsPastIntRange() throws Exception {
    try (Directory dir = newDirectory()) {
      try (IndexWriter w =
          new IndexWriter(dir, new IndexWriterConfig().setMergePolicy(NoMergePolicy.INSTANCE))) {
        w.addDocument(new Document());
        w.commit();
        w.addDocument(new Document());
      }
      try (DirectoryReader r = DirectoryReader.open(dir)) {
        LeafReader a = r.leaves().get(0).reader();
        LeafReader b = r.leaves().get(1).reader();
        int n = (1 << 30) + 1;
        IndexSorter sorter =
            new IndexSorter.StringSorter(
                SortField.Provider.NAME,
                SortField.STRING_LAST,
                false,
                leaf -> leaf == a ? new OneDoc(0, n, -1) : new OneDoc(n, n, n - 1));
        IndexSorter.ComparableProvider[] keys = sorter.getComparableProviders(List.of(a, b));
        long missing = keys[0].getAsComparableLong(0);
        long present = keys[1].getAsComparableLong(0);
        // expected: the missing key sorts after global ord 2^31 + 1; actual: it is
        // Integer.MAX_VALUE
        assertTrue("missing=" + missing + " present=" + present, missing > present);
      }
    }
  }

  private static final class OneDoc extends SortedDocValues {
    private final long first;
    private final int valueCount;
    private final int ord;
    private final BytesRef term = new BytesRef(new byte[8]);
    private int doc = -1;

    OneDoc(long first, int valueCount, int ord) {
      this.first = first;
      this.valueCount = valueCount;
      this.ord = ord;
    }

    @Override
    public BytesRef lookupOrd(int o) {
      long v = first + o;
      for (int i = 7; i >= 0; i--, v >>>= 8) {
        term.bytes[i] = (byte) v;
      }
      return term;
    }

    @Override
    public int getValueCount() {
      return valueCount;
    }

    @Override
    public int ordValue() {
      return ord;
    }

    @Override
    public boolean advanceExact(int target) {
      doc = target;
      return ord >= 0;
    }

    @Override
    public int docID() {
      return doc;
    }

    @Override
    public int nextDoc() {
      return advance(doc + 1);
    }

    @Override
    public int advance(int target) {
      return doc = (target == 0 && ord >= 0) ? 0 : NO_MORE_DOCS;
    }

    @Override
    public long cost() {
      return 1;
    }
  }
}
Command
cp $REPRO/TestStringSorterMissingLast.java $LUCENE/lucene/core/src/test/org/apache/lucene/index/
cd $LUCENE && ./gradlew :lucene:core:test --tests org.apache.lucene.index.TestStringSorterMissingLast -Ptests.seed=DEADBEEF -Ptests.heapsize=2g
# the same failure with -Ptests.asserts=false
Expected
The key of the document without a value is above the largest present key, 2,147,483,649.
Observed
AssertionError: missing=2147483647 present=2147483649, on main with assertions on and off, and on the 10.6.0 jars with assertions off.

All files of this repro: repro/LFV-1140/

More files, environment, full output349 words

TestStringSorterMissingLast (one method, extends LuceneTestCase, package org.apache.lucene.index of the lucene/core tests, ASF header included). It uses only public API: IndexSorter.StringSorter's constructor with SortField.STRING_LAST and a SortedDocValuesProvider. Segment 1's document has no value; segment 2's document holds the largest of the 2^31 + 2 terms. The cost is the OrdinalMap over 2^31 + 2 terms, so the test needs -Ptests.heapsize=2g (the default 512 MB test heap is too small: a run with a 512 MB heap ran out of memory inside OrdinalMap.build). No smaller input can show the bug: it needs at least 2^31 global ordinals (2^31 gives a tie with the missing key, more than 2^31 a strict inversion; the repro uses 2^31 + 2).

The dictionaries are larger than their one-document segments, which IndexWriter never writes itself; they stand in for huge segments whose values mostly belong to deleted documents. The real trigger, about 2^31 source documents in one addIndexes(CodecReader...) call, was not run. An end-to-end variant that runs the real addIndexes(CodecReader...) merge over two sorted segments (each a deleted document with a value and a live document, dictionaries enlarged to 2^30 + 1 terms by a FilterCodecReader) fails on main, 10.6.0, 10.5.2 and 9.12.3 with STRING_LAST: the document with a value must be doc 0 expected:<0> but was:<1>, and passes with 2^10 + 1 terms; it is supporting evidence, not the repro.

As a regression test the same method fits in TestIndexSorting next to testMissingStringLast. With the fix in place, the file passes checkGoogleJavaFormat; it differs from the first executed copy only by one comment wrapped onto two lines, as the formatter asked, and fails the same way. Through gradle the test takes about 3 minutes (its test JVMs run with -XX:TieredStopAtLevel=1 -XX:ActiveProcessorCount=1), about 80 s with a plain JUnit launcher.

Environment

lucenemain 5adff78bb168 (12.0.0-SNAPSHOT) and 10.6.0: fails
jdkOpenJDK 25.0.3 (build 25.0.3+9-LTS)
osLinux aarch64 (nothing platform-specific)

Observed output

TestStringSorterMissingLast > testMissingKeyAboveGlobalOrdsPastIntRange FAILED
    java.lang.AssertionError: missing=2147483647 present=2147483649
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:475E6A8AB947C209]:0)
        at org.junit.Assert.fail(Assert.java:89)
        at org.junit.Assert.assertTrue(Assert.java:42)
        at org.apache.lucene.index.TestStringSorterMissingLast.testMissingKeyAboveGlobalOrdsPastIntRange(TestStringSorterMissingLast.java:51)

# -Ptests.asserts=false: the same failure; 10.6.0 jars, assertions off: the same failure

Why it looks unintended

  • STRING_LAST promises "missing string values sort last", and ComparableProvider promises its long keys order documents as the comparator does; neither has a size limit.
  • In 7.6.0-8.1.1 this input threw ArithmeticException (Math.toIntExact, LUCENE-8592); LUCENE-8900 made the keys long and dropped the guard without discussion.
  • The same class's in-segment comparator keeps documents without a value last; only the merge keys disagree.
The full argument183 words
  • Contracts. SortField.java:346: "Pass this as a missingValue constructor parameter to have missing string values sort last." IndexWriterConfig.java:504: setIndexSort, "Set the Sort order to use for all (flushed and merged) segments." IndexSorter.java:57-62: ComparableProvider "Returns a long so that the natural ordering of long values matches the ordering of doc IDs for the given comparator". No javadoc, CHANGES entry or test caps the combined dictionary of a merge.
  • History. LUCENE-8592 (#9638, 9f29ed0757e, 2018) wrapped the global ordinal in Math.toIntExact, so this input threw (executed on 7.6.0 and 8.1.1). LUCENE-8900 (#9943, 17f2f96a5cf, 2019, "Simplify MultiSorter") turned the keys into longs and returned the raw ordinal but kept the int sentinel; its thread mentions neither.
  • Tests. TestIndexSorting.testMissingStringLast (TestIndexSorting.java:479) checks the property on small inputs only; no test covers global ordinals past the int range.
  • Not claimed, not investigated. The SortedSetSortField route through the same code. SortedSetSelector documents "Fields containing Integer.MAX_VALUE or more unique values are unsupported" (SortedSetSelector.java:35); whether that limit, stated for one selector view, also covers the combined dictionary of a merge was not examined.
The devil's-advocate check118 words

Strongest argument: Michael McCandless wrote on #9638 that for single values "it should never happen that the long ord exceeds positive int space"; no Lucene merge or bundled tool reaches 2^31 values; and the repro uses synthetic dictionaries larger than their segments. Why it fails: that sentence is a claim of impossibility, true for an index's own merges, and its consequence was a fail-loud guard that a later refactor removed as a side effect. addIndexes(CodecReader...) legally merges inputs whose dictionaries exceed it, and Lucene itself feeds StringSorter views whose value count exceeds maxDoc (SortedSetSortField.java:184-191, through SortedSetSelector, whose views report the whole multi-valued dictionary, SortedSetSelector.java:156-157). The argument lowers the priority (hence Low), not the intent.

Suggested fix

Recommended Use Long.MAX_VALUE / Long.MIN_VALUE as the missing merge key (A, recommended, validated)

Make the missing merge key a long outside the global-ordinal range in StringSorter.getComparableProviders: Long.MAX_VALUE for STRING_LAST, Long.MIN_VALUE for STRING_FIRST. The in-segment int sentinels stay. The repro passes, and so do the 62 TestIndexSorting tests.

      OrdinalMap ordinalMap = OrdinalMap.build(null, values, PackedInts.DEFAULT);
      // global ordinals are longs and may exceed Integer.MAX_VALUE
      final long missingOrd;
      if (missingValue == SortField.STRING_LAST) {
        missingOrd = Long.MAX_VALUE;
      } else {
        missingOrd = Long.MIN_VALUE;
      }
All options and trade-offs3 options ยท 372 words

Option A was built and checked through gradle on 5adff78bb168; B is an equivalent variant and C a fail-loud alternative, neither run in this form (C is what 7.6.0-8.1.1 did). A and B keep addIndexes(CodecReader...) working on such inputs; C rejects a legal call.

Use Long.MAX_VALUE / Long.MIN_VALUE as the missing merge key (A, recommended, validated)

In IndexSorter.StringSorter.getComparableProviders (IndexSorter.java:488-493), declare missingOrd as long and use Long.MAX_VALUE for STRING_LAST, Long.MIN_VALUE otherwise. Global ordinals are >= 0 and below the total value count, so these keys are always outside their range. getDocComparator keeps its int sentinels, which are correct for int segment ordinals.

      OrdinalMap ordinalMap = OrdinalMap.build(null, values, PackedInts.DEFAULT);
      // global ordinals are longs and may exceed Integer.MAX_VALUE
      final long missingOrd;
      if (missingValue == SortField.STRING_LAST) {
        missingOrd = Long.MAX_VALUE;
      } else {
        missingOrd = Long.MIN_VALUE;
      }

Trade-offs

No cost: the key is already a long. The merged order changes only for inputs that hit the bug.

What the checks validated

  • Gradle in a scratch worktree at 5adff78bb168, seed DEADBEEF, -Ptests.heapsize=2g: the repro fails without the fix (assertions on and off: missing=2147483647 present=2147483649) and passes with it (assertions off).
  • With the fix and assertions on: the repro (1) and TestIndexSorting (62, including testMissingStringLast and the other three testMissing*String* tests): 63 tests, 0 failures, 0 skipped.
  • checkGoogleJavaFormat passes with the fix and the repro in place.
  • The end-to-end addIndexes(CodecReader...) variant passes with the same change shadowed in, and the cross-model reviewers' boundary tests and the four upstream testMissing*String* tests passed with it in their own runs.

Use the OrdinalMap's value count and -1 as the missing keys (B, equivalent variant)

Set the STRING_LAST key to ordinalMap.getValueCount() and the STRING_FIRST key to -1: one past the largest global ordinal and one below the smallest.

Trade-offs

The same order as A with dense keys; A stays closer to the existing code. Not run.

Restore Math.toIntExact on the global ordinal (C, not recommended)

Narrow the global ordinal with Math.toIntExact, as LUCENE-8592 did, so such a merge throws ArithmeticException instead of writing a mis-sorted segment.

Trade-offs

Loud instead of silent, but a legal addIndexes(CodecReader...) call is then rejected. 7.6.0 and 8.1.1 behave this way (executed); not run on main.

Downstream note

Only an application that itself runs such an addIndexes(CodecReader...) merge can trigger it; a downstream product that relies on early termination over a STRING_LAST index sort could then return wrong top hits from the merged segment (by reading, not executed).

How it was found

A proof-obligation audit of IndexSorter.StringSorter's contract: its merge keys must order documents as its in-segment comparator does, for every global ordinal an OrdinalMap can return. The obligation fails once global ordinals reach Integer.MAX_VALUE, and a one-method JUnit test on the stock main jars witnessed it.

The method in full130 words

Method: semi-formal (a proof-obligation audit of a class's contract, witnessed by an executable repro).

  • The obligation comes from ComparableProvider (IndexSorter.java:57-62): the long keys must order documents as getDocComparator does. For StringSorter the audit compares the key ranges: global ordinals take any value in [0, valueCount) with a long valueCount, while the missing key is fixed at Integer.MAX_VALUE. The obligation holds only while valueCount <= 2^31 - 1, and nothing on the addIndexes(CodecReader...) path enforces that.
  • A one-method JUnit test with dictionaries just past that bound witnessed the gap, and the long sentinel made it pass.
  • An independent reproducer wrote its own end-to-end addIndexes test, cross-model reviews and a devil's-advocate verifier tried to refute it, and an adjudication re-ran the tests ("Prior reports, history and checks").

Prior reports, history and checks

Prior reports

No prior report found (searched 2026-11-02: GitHub issues, PRs and commits incl. the JIRA archive, downstream trackers, four mailing lists, the web and the files of all 408 open PRs; re-checked the same day). Nearest: #9638 (LUCENE-8592, which added the fail-loud guard) and #9943 (LUCENE-8900, which dropped it).

Searches3 searches

No issue, PR, review comment, list thread, JIRA entry or downstream report describes the STRING_LAST missing merge key falling below long global ordinals, and nothing upstream fixes it. Limits: keyword search only; one web query was throttled; private reports are not visible.

What was searched, when, and what turned up
WhereWhenHowFound
GitHub issues, PRs and commits (apache/lucene, apache/lucene-solr), JIRA archive, dev@, java-user@, issues@ and commits@ lists, Elasticsearch, OpenSearch, Solr, web2026-11-02two scripted prior-report searches (52 queries: 1,418 hits, 0 high, 7 medium, all medium read; and 24 list and JIRA queries: 532 hits, the only high one LUCENE-8592) and 43 manual GitHub searches: StringSorter, missingOrd, getComparableProviders, STRING_LAST global ordinal, toIntExact global ordinal, index sort missing ordinal overflow, ...no report of this defect
Open PRs and recent activity2026-11-02the changed files of all 408 open PRs; full reads of #16847, #16571 and #16851; items created on 2026-11-02 (#16962-#16965); commits on IndexSorter.java and MultiSorter.java; a re-checknone touches IndexSorter.java; #16571, #16847 and #16851 edit MultiSorter.java for other reasons; #16847 (long global doc ids) would widen the reach if it lands
Related items (read)2026-11-02#9638 / LUCENE-8592, #9943 / LUCENE-8900, #16202, #8625 / LUCENE-7574, #11253 / LUCENE-10216history only: the guard, its removal, the last change to IndexSorter.java, an older missing-ordinal bug with another cause, and the change that created findMerges(CodecReader...)

History

Introduced by LUCENE-8900 "Simplify MultiSorter" (17f2f96a5cf, branch_8x aad4b411cdd, 2019-07-09, #9943), first released in 8.2.0. 7.6.0-8.1.1 throw ArithmeticException on the same input instead (executed on 7.6.0 and 8.1.1; the tags between have the same Math.toIntExact). Every release run from 8.2.0 to 10.6.0, and main, fails; not fixed upstream.

Versions tested11 rows

Before: LUCENE-6766 (2016) introduced the int sentinel; LUCENE-8592 (9f29ed0757e, Jim Ferenczi, 2018, #9638) added Math.toIntExact on the global ordinal, so 7.6.0-8.1.1 fail loudly. 7.0.0-7.5.0 truncate the ordinal with an (int) cast, a different defect (by reading).

Introduced: 17f2f96a5cf on master and aad4b411cdd on branch_8x (Adrien Grand, 2019-07-09; a JIRA patch migrated as #9943). In MultiSorter, return Math.toIntExact(globalOrds.get(readerValues.ordValue())); became return globalOrds.get(readerValues.ordValue()); while missingOrd stayed an int. On the 8.2.0 jars, putting back only the pre-commit MultiSorter.java restores the ArithmeticException, and the commit's file with long sentinels passes. LUCENE-9330 (2020) moved the code unchanged into IndexSorter.StringSorter.

Not fixed upstream: upstream main 1c2072f0284 (2026-11-02) still has the int sentinel; the last commit on IndexSorter.java is e6f12f31d08 (#16202, 2026-06-05). 8.8.2-8.11.3 are inferred, not run.

Versions and branches executed, with results
Version or commitVerdictResult
7.5.0 probepasses (a different (int)-cast defect, not this bug)
7.6.0, 8.1.1 probeArithmeticException: integer overflow (Math.toIntExact)
8.2.0 probefails: the document without a value merged to doc 0
8.2.0 + pre-commit MultiSorter.java bisectArithmeticException
8.2.0 + commit with long sentinels bisectpasses
8.5.2 probefails
8.6.0, 8.11.4, 9.0.0 affectedfails (equivalent test)
9.12.3, 10.5.2 affectedfails, assertions off
10.6.0 affectedfails, assertions off (this repro)
main 5adff78bb168 JUnit, gradlefails, assertions on and off
main with fix A not affectedpasses; the 62 TestIndexSorting tests pass

Independent checks

The finder's test, an independent reproducer with its own end-to-end addIndexes test, two executed cross-model reviews (OpenAI GPT-5.6: real, high), a devil's-advocate verifier and an adjudication (confirmed, Low, medium confidence: proof-only end to end) all found it real, and a final re-run reproduced it. This doc's gradle runs reproduced it and validated the fix.

Checks and verdicts364 words

The cross-model reviews ran on the older main ea57360912ed, where IndexSorter.java is identical to 5adff78bb168; the intended-lens test was re-run on 5adff78bb168. Every other check ran on 5adff78bb168 or release jars.

Each independent check and its verdict
CheckVerdictWhat it found
finder reproducedProvider-level test fails on main (assertions on and off), 10.6.0 and 9.12.3 with missing=2147483647 present=2147483649; the long sentinel makes it pass.
independent reproducer real, LowOwn end-to-end test through addIndexes(CodecReader...), written from the claim only, fails on main (assertions on and off), 10.5.2 and 9.12.3; a 2^10 + 1 term control passes; the fix makes it pass; CheckIndex level 2 flags the merged segment, level 1 does not.
cross-model review, refute lens (OpenAI GPT-5.6, executed) real (high)Own boundary test fails with assertions on and off, a 12-term control passes, both pass with the fix, and TestIndexSorting.testMissingStringLast passes with the fix. Intended argument rated weak.
cross-model review, intended lens (OpenAI GPT-5.6, executed) real (high)Rejected the works-as-designed case: STRING_LAST and ComparableProvider are unconditional, nothing caps the merged dictionary, and LUCENE-8900 dropped the guard without discussion. Its boundary test fails on 5adff78bb168; the four upstream testMissing*String* tests pass with the fix.
devil's-advocate verifier real, LowExamined design assumption, documented limits, misuse, unreachability, the synthetic witness and scale; only scale survives, and it bears on priority. Its scale model with the document limit lowered to 10 confirmed the accounting the trigger relies on.
adjudication confirmed, Low, mediumRe-ran the end-to-end test on main with a fresh seed, assertions off: fails. Medium confidence because the full-scale trigger was not run.
final re-run and repro check reproducedRe-runs on main and 10.6.0 fail, with the fix shadowed in they pass; one deterministic test, legal public-API input, silent result with assertions off.
this doc's gradle check reproduced; fix A validatedGradle at 5adff78bb168: the repro fails with assertions on and off; with fix A it passes, and with assertions on the repro plus TestIndexSorting run 63 tests with 0 failures; checkGoogleJavaFormat passes with the fix and the (comment-rewrapped) repro. The repro also fails on the 10.6.0 release jars, assertions off.

Diagram file

The diagram as a still image, generated with AI and checked against the code. It is under 10 MB, the limit for a GitHub attachment.

Sources and provenance

Finding record, Lucene and upstream sources, repro files and diagram notes1,702 words

Finding record

LFV-1140, snapshot of 2026-11-06

Registry title
Index sorting by a STRING field with STRING_LAST: at merge, a document without a value gets the int key Integer.MAX_VALUE while documents with a value get long global ordinals, so when the inputs of one merge hold more than 2^31 - 1 distinct values (reachable through IndexWriter.addIndexes(CodecReader...)), the merged segment silently puts documents without a value ahead of documents with a value
Area
index / index sorting at merge: IndexSorter.StringSorter merge keys (MultiSorter), reached through IndexWriter.addIndexes(CodecReader...)
Priority
Low, rank 980: A STRING_LAST index sort merged through addIndexes(CodecReader...) silently places documents without a value ahead of the documents with the largest values, against the declared sort, in every release since 8.2.0. It only happens when the inputs of one call hold at least 2^31 distinct sort values, deleted documents included, so it is an extreme-scale, contrived case.
Impact class
data corruption
Impact note
Hits only applications that opt into an index sort on a STRING field with missing value STRING_LAST and call IndexWriter.addIndexes(CodecReader...) on the leaves of two or more indexes already sorted the same way whose doc-values dictionaries, counting values that only deleted documents still hold, together have at least 2^31 distinct values while the live total fits under MAX_DOCS: the merged segment then silently places live documents without a value ahead of the documents with the largest values, contrary to its declared sort, with -ea and -da; CheckIndex at level 2 or higher reports the violation (the default level 1 does not), and index-sort early termination on that sort could return wrong top hits (by reading, not executed); STRING_FIRST, an index's own merges of a single-valued STRING sort (maxDoc <= MAX_DOCS < 2^31 - 1) and smaller addIndexes calls are not affected, and the full-scale trigger (2^31 or more source documents) was not run (proof-only end to end).
Summary
You configure the index sort new SortField("s", SortField.Type.STRING, false, SortField.STRING_LAST) and merge, with IndexWriter.addIndexes(CodecReader...), sorted source indexes whose 's' dictionaries together hold more than 2^31 - 1 distinct values, expecting documents without a value to come after every document with one, as STRING_LAST and the in-segment comparator promise. At merge, IndexSorter.StringSorter gives a document with a value its long global ordinal (from an OrdinalMap over every input's full dictionary, deleted documents' values included) but gives a document without a value the int key Integer.MAX_VALUE, so every value whose global ordinal is above 2^31 - 1 sorts after the missing documents (a value at exactly 2^31 - 1 gets the same key as they do). The merged segment is written out of its declared sort with no error: in an end-to-end addIndexes(CodecReader...) test over two one-live-document segments whose dictionaries a FilterCodecReader enlarges to 2^30 + 1 terms each, the document without a value ends up at doc 0.
Introduced
17f2f96a5cf8e0001a81b9327c2ddced053e6934 on master and its branch_8x copy aad4b411cdd2d517328a2444147b407d4a38343d (the one that shipped first, in 8.2.0), 'LUCENE-8900: Simplify MultiSorter' (a JIRA patch, migrated as apache/lucene#9943, no pull request; by jpountz, +1 from danmuzi). In MultiSorter#getComparableProviders, case STRING, the merge key became a long and 'return Math.toIntExact(globalOrds.get(readerValues.ordValue()))' became 'return globalOrds.get(readerValues.ordValue())', while 'final int missingOrd = Integer.MAX_VALUE' (STRING_LAST) / Integer.MIN_VALUE stayed, so a global ordinal of 2^31 - 1 or more now silently reaches the missing key instead of throwing. The toIntExact guard came from LUCENE-8592 (9f29ed0757e, 2018, #9638); the int sentinel dates from LUCENE-6766 (231cb3eb42e, 2016); LUCENE-9330 (de2bad90390 / ad0cefb8ec2, 2020) moved the code unchanged into IndexSorter.StringSorter, which is what git blame shows on main. [read: git log -S 'Math.toIntExact(globalOrds.get' on MultiSorter.java in the history clone lists exactly the three LUCENE-8592 commits and the two LUCENE-8900 commits; exec: on the 8.2.0 jars, shadowing only MultiSorter.java with the aad4b411cdd^ source restores the loud ArithmeticException, and the aad4b411cdd source with long sentinels passes] (2019-07-09 (author date of 17f2f96a5cf and aad4b411cdd))
First affected version
8.2.0 [exec] (the first release with LUCENE-8900: the MultiSorter probe merges the document without a value ahead of the largest value). 8.1.1 and 7.6.0 throw ArithmeticException on the same input (Math.toIntExact from LUCENE-8592), a loud failure, not this bug [exec]; 7.0.0-7.5.0 narrow the global ordinal with an (int) cast instead, a different defect [read; the 7.5.0 probe passes]; 6.2.0-6.6.x fail loudly ('Too many documents') [read]
Affected versions
8.2.0 through 10.6.0 (released 2026-10-29, 4ae946e5a9b) and main 5adff78bb168 (12.0.0-SNAPSHOT). Executed (fail): main with -ea and -da (the finder's provider-level test, the independent reproduction's end-to-end addIndexes test, the GPT reviewers' own tests, the intended-behaviour check's re-runs, the adjudication and the registration check); 10.6.0 (the finder's test with -da, and the independent reproduction's test with -da at the registration check); 10.5.2 (the independent reproduction, -da); 9.12.3 (the finder and the independent reproduction, -da); 9.0.0, 8.11.4 and 8.6.0 (the finder's test, pre-9.1 test-framework copy); 8.5.2 and 8.2.0 (the MultiSorter probe). Inferred [read: same code on the same line, tags not in the local clone]: 8.8.2 to 8.11.3. Not affected: 7.6.0 to 8.1.1 throw ArithmeticException instead [exec 7.6.0, 8.1.1]; 7.0.0-7.5.0 have a different (int)-truncation defect [read]; 6.2.0-6.6.x fail loudly [read]. Not new in 10.6 (10.5.2 and 9.12.3 fail). Not fixed upstream: upstream main 1c2072f0284 (author date 2026-11-02) still has the int sentinel; the last upstream commit on IndexSorter.java is e6f12f31d08 (#16202, author date 2026-06-05), and no open PR touches IndexSorter.java.
Status
documented (brief, checks and a per-finding doc exist)
Verification
Confirmed by AI-run checks: an independent repro, a cross-model review that agreed, an intended-behaviour check, a prior-report search and a skeptical audit; not yet triaged by a person.
Found by
semi-formal: proof-obligation audit
Upstream and prior reports
none found (2026-11-02, on top of the finder's, the independent reproduction's, the intended-behaviour check's and the adjudication's searches; rechecked the same day): two scripted prior-report searches (52 queries over GitHub issues, PRs and commits, downstream repositories, the dev@, java-user@, issues@ and commits@ lists, the JIRA archive and the web: 1418 distinct hits, 0 high, 7 medium; and 24 list and JIRA queries: 532 hits, 1 high, the LUCENE-8592 precedent), 43 manual GitHub searches (apache/lucene, apache/lucene-solr, Elasticsearch, OpenSearch, Solr), the changed-file lists of all 408 open apache/lucene PRs, the threads of #9638, #9943, #16202, #16847, #16571, #16851 and others, the upstream commit lists of IndexSorter.java on main, branch_10x and branch_10_6, and 7 web searches (one more throttled): no issue, PR, review comment, list thread or JIRA entry reports that the STRING_LAST missing merge key falls below long global ordinals. History, not reports: #9638 (LUCENE-8592, closed 2018-12-07), where mikemccand suggested Math.toIntExact for the global-ordinal merge key because 'it should never happen that the long ord exceeds positive int space' and jimczi applied it, and #9943 (LUCENE-8900, 2019), where jpountz switched the merge keys to longs and dropped that guard without discussing the sentinel. Open PRs #16571, #16847 and #16851 touch MultiSorter.java but not the sentinel, and none touches IndexSorter.java; #16847 (long global doc ids, open) would widen the reach to ordinary merges if it lands. Re-check the same day: GitHub search on apache/lucene (issues and PRs) for 'StringSorter', 'STRING_LAST global ordinal', 'missingOrd', 'index sort missing ordinal overflow' and 'toIntExact global ordinal' (no relevant hit), the items created on 2026-11-02 (#16962-#16965, none about sorting), the open PRs updated since 2026-11-01 (none changes the sentinel), and the commits on IndexSorter.java and MultiSorter.java (still e6f12f31d08, author date 2026-06-05; upstream main 1c2072f0284).
Lucene commit tested
main 5adff78bb168 (12.0.0-SNAPSHOT) through gradle on 2026-11-03 in a scratch worktree, seed DEADBEEF, -Ptests.heapsize=2g: the repro without the fix fails with assertions on and off; with the long-sentinel fix it passes (assertions off), and with assertions on the repro plus TestIndexSorting run 63 tests with 0 failures; checkGoogleJavaFormat passes with the fix and the repro in place. The repro also ran on the 10.6.0 release jars (assertions off: fails). Equivalent tests or a MultiSorter.sort probe ran on 10.5.2, 9.12.3, 9.0.0, 8.11.4, 8.6.0, 8.5.2 and 8.2.0 (all fail) and on 8.1.1 and 7.6.0 (ArithmeticException). Only Linux aarch64 with OpenJDK 25.0.3 was run.

Lucene and upstream sources

Finding record
  • lucene/core/src/java/org/apache/lucene/index/IndexSorter.java:55-62 (at 5adff78bb168) (ComparableProvider: 'Returns a long so that the natural ordering of long values matches the ordering of doc IDs for the given comparator'), :103-108 (merge keys compared with Long.compare), :479-509 (StringSorter.getComparableProviders: OrdinalMap over every input's full dictionary at :487, 'final int missingOrd' = Integer.MAX_VALUE / Integer.MIN_VALUE at :488-493, long global ordinal at :502, missingOrd at :504; fix site), :512-528 (getDocComparator: int segment ordinals with the same int sentinel, correct in-segment)
  • lucene/core/src/java/org/apache/lucene/index/MultiSorter.java:90-97 (at 5adff78bb168) (merge order from the providers' comparison, 'return reverseMuls[i] * cmp') and lucene/core/src/java/org/apache/lucene/index/MergeState.java:223 (index-sorted merges take their doc maps from MultiSorter.sort)
  • lucene/core/src/java/org/apache/lucene/index/IndexWriter.java:3275-3297 (at 5adff78bb168) (addIndexes(CodecReader...) reserves only the sum of leaf.numDocs()) and :3548-3566 (with an index sort the merge readers are not wrapped in SlowCompositeCodecReaderWrapper); lucene/core/src/java/org/apache/lucene/index/MergePolicy.java:245-255 (OneMerge(CodecReader...) totalMaxDoc = sum of numDocs) and :616-619 (default findMerges(CodecReader...) puts all inputs in one OneMerge)
  • lucene/core/src/java/org/apache/lucene/search/SortField.java:346 (at 5adff78bb168) ('Pass this as a missingValue constructor parameter to have missing string values sort last')
  • SECURITY.md lines 28, 38, 42, 46 and 50
The finding in 30 seconds
  • lucene main@5adff78bb168 lucene/core/src/java/org/apache/lucene/index/IndexSorter.java:55-62 (ComparableProvider contract), :98-111 (Long.compare), :479-509 (getComparableProviders: :487 OrdinalMap, :488-493 int missingOrd, :497 LongValues, :502 global ordinal, :504 missingOrd), :512-528 (getDocComparator)
  • lucene main@5adff78bb168 lucene/core/src/java/org/apache/lucene/index/MultiSorter.java:88-97; lucene main@5adff78bb168 lucene/core/src/java/org/apache/lucene/index/MergeState.java:223
  • lucene main@5adff78bb168 lucene/core/src/java/org/apache/lucene/index/MultiSorter.java:96, :101-102 (reverseMul; tie-break by reader index, then doc id)
Who is affected
  • lucene main@5adff78bb168 lucene/core/src/java/org/apache/lucene/index/IndexWriter.java:3124-3144 (addIndexes(Directory...) counts totalMaxDoc), :3275-3297 (addIndexes(CodecReader...) counts numDocs), :3548-3566 (no wrapping with an index sort)
  • lucene main@5adff78bb168 lucene/core/src/java/org/apache/lucene/index/MergePolicy.java:245-255, :616-619
  • lucene main@5adff78bb168 lucene/core/src/java/org/apache/lucene/index/MultiSorter.java:96 (reverseMul applied to the key comparison), :101-102 (ties broken by reader index, then doc id); lucene main@5adff78bb168 lucene/core/src/test/org/apache/lucene/index/TestIndexSorting.java:479-518 (testMissingStringLast, reverse=true expects the document without a value first)
Why it looks unintended
  • lucene main@5adff78bb168 lucene/core/src/java/org/apache/lucene/search/SortField.java:346; lucene main@5adff78bb168 lucene/core/src/java/org/apache/lucene/index/IndexWriterConfig.java:504; lucene main@5adff78bb168 lucene/core/src/java/org/apache/lucene/index/IndexSorter.java:57-62
  • lucene main@5adff78bb168 lucene/core/src/java/org/apache/lucene/search/SortedSetSortField.java:184-191; lucene main@5adff78bb168 lucene/core/src/java/org/apache/lucene/search/SortedSetSelector.java:35, :156-157
  • lucene main@5adff78bb168 lucene/core/src/test/org/apache/lucene/index/TestIndexSorting.java:479 (testMissingStringLast)
  • https://github.com/apache/lucene/issues/9638 (Michael McCandless's comment), https://github.com/apache/lucene/issues/9943
How it was found
  • lucene main@5adff78bb168 lucene/core/src/java/org/apache/lucene/index/IndexSorter.java:57-62, :479-528
Diagrams
  • lucene main@5adff78bb168 lucene/core/src/java/org/apache/lucene/index/IndexSorter.java:487-506; lucene main@5adff78bb168 lucene/core/src/java/org/apache/lucene/index/MultiSorter.java:88-97

Other statements trace to the hunt's working files (models, logs, reviews and briefs), which are not published.

Repro files

About the diagrams

The diagram follows the repro and the code at 5adff78bb168 (IndexSorter.java:487-506, MultiSorter.java:88-97).

Built 2026-11-06 from the hunt's record of this finding and its doc file. Lucene main under test in this hunt: ea57360912ed. Every listed finding was re-run on Lucene main e1faeba08bde on 2026-11-02.