SortedSetDocValues facets: a sibling label such as "shoes<TAB>" takes over the children of "shoes"

SortedSetDocValues (SSDV) faceting stores each facet path as one term, dim U+001F label U+001F ..., and for a hierarchical dimension it also indexes every ancestor path. When the application creates a DefaultSortedSetDocValuesReaderState for a reader, it walks the terms in sorted order and builds the facet tree from neighbours only: a next term with more components is taken as the first child, one with as many components as the next sibling. That is right only if the separator sorts first after a label, but TAB, CR, LF and every other character from U+0000 to U+001E sort before U+001F, and FacetsConfig itself writes U+001E when it escapes a label that contains U+001F or U+001E. So with documents cat/shoes/red and cat/"shoes<TAB>" the terms sort cat, cat/shoes, cat/shoes<TAB>, cat/shoes/red: getTopChildren(10, "cat", "shoes") returns null and the leaf "shoes<TAB>" reports red (1). Dimension names built the same way (color next to color<TAB>) make a dimension disappear from getTopChildren and getAllDims, give getTopDims a null entry, or make a flat multi-valued requireDimCount dimension lose a label. There is no exception; taxonomy faceting, getSpecificValue and drill-down stay right. Every release from 9.1.0 (2022) to 10.5.2 and main is affected. A fix that finds each term's real parent with a stack of byte prefixes passes the repro, the whole facet test suite and an exhaustive and a randomized differential check.

• SSDV faceting: SortedSetDocValuesFacetField labels, counted by SortedSetDocValuesFacetCounts or ConcurrentSortedSetDocValuesFacetCounts over a DefaultSortedSetDocValuesReaderState built once per reader. No taxonomy index.
• Encoded path: FacetsConfig.pathToString joins the dimension and labels with DELIM_CHAR U+001F and puts the escape character U+001E in front of any U+001F or U+001E inside a part (FacetsConfig.java:550-553, :569-593). Terms sort by unsigned byte, and each term's position is its ord.
• Hierarchical dimension: FacetsConfig.setHierarchical(dim, true). Every prefix of a path is indexed, the bare dimension included (FacetsConfig.java:474-481). A flat multi-valued + requireDimCount dimension indexes its bare dimension term plus dim/label (:491-497).

1. The constructor walks the ords from 0 and handles one run of terms with the same dimension at a time (DefaultSortedSetDocValuesReaderState.java:101-111); a run ends when the next term's dimension differs (:154-159).
2. Inside a run it decides structure from the next term only: more components means "next ord must be a direct child of current ord, this is because we are indexing all ancestral paths" (:161-168); as many means "next ord must be a sibling" (:169-174). DimTree then takes the first child of a path to be the next ord (SortedSetDocValuesReaderState.java:122-124).
3. A sibling that continues a label with a byte below 0x1F sorts between the label and its children: cat/shoes < cat/shoes<TAB> < cat/shoes/red. So shoes is recorded as childless and red becomes the first child of shoes<TAB>.
4. Dimension names: the terms of color<TAB> sort between color and color/red, so the run of color ends after its bare term and a later run of color overwrites its state (prefixToDimTree.put, :185; flat prefixToOrdRange.put, :234). The new state starts at color/red, which has no children. For a flat multi-valued requireDimCount dimension the surviving range starts at a label, which the counting code skips as if it were the dimension term (AbstractSortedSetDocValueFacetCounts.java:274-281).

Documents cat/shoes/red and cat/"shoes<TAB>", setHierarchical("cat", true), MatchAllDocsQuery (U+001F shown as /):

Over three segments with US/New York/Manhattan, US/New York/Brooklyn and US/"New York<CR>", the leaf New York<CR> is returned as a parent with value=1 and the children it was wrongly given, Brooklyn=1, Manhattan=1: a value smaller than the sum of its children.

• Who is exposed. Users of DefaultSortedSetDocValuesReaderState with SortedSetDocValuesFacetCounts or ConcurrentSortedSetDocValuesFacetCounts (both fail alike) on a dimension configured setHierarchical(dim, true), or flat with setMultiValued + setRequireDimCount, where a sibling label continues a label with a character from U+0000 to U+001F, at the end (shoes<TAB>) or followed by more text (shoes<TAB>clearance, executed), and the shorter label has children: untrimmed CRLF or TAB artefacts in imported category paths, or labels that contain U+001E or U+001F. Trimming only the ends of labels does not rule it out. The dimension-name variants need names like color and color<TAB>.
• Default vs opt-in. Default codec, IndexWriterConfig and searcher; the hierarchical (or multi-valued + requireDimCount) setting is opt-in, and hierarchical SSDV facets exist since 9.1.0.
• Scale. Two documents; single- and multi-segment indexes fail alike.
• Index-wide. The tree is built from every term of the field, so a document outside the query, or deleted but not yet merged away, also triggers it; a merge that drops the document restores the tree.
• Silent. No exception, except an AssertionError from getTopDims in the dimension-name variant when assertions are on (a null list entry when they are off). A result can contradict itself: a leaf returned as a parent whose value is smaller than the sum of the children it was wrongly given.
• Not affected. Taxonomy faceting, getSpecificValue, drill-down and hits, flat dimensions without requireDimCount (single- or multi-valued; they index no bare dimension term, executed), and siblings that continue with a character at or above U+0020 (shoes sale). The indexed terms are correct, so a fix needs no reindex.
• How likely. Rare: it needs a label and a sibling label that continues it with a control character, and the shorter label must have children. The searches listed under prior reports found no public report since 9.1.0 (2022).

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: expected:<dim=cat path=[shoes] value=1 childCount=1
  red (1)
> but was:<null>
       org.junit.Assert.fail(Assert.java:89)
       org.junit.Assert.failNotEquals(Assert.java:835)
       org.junit.Assert.assertEquals(Assert.java:120)
       org.junit.Assert.assertEquals(Assert.java:146)
       org.apache.lucene.facet.sortedset.TestSsdvFacetChildrenMovedToTabSibling.testChildStaysUnderItsLabel(TestSsdvFacetChildrenMovedToTabSibling.java:50)

• Contract. Facets.java:39-44: getTopChildren "Returns the topN child labels under the specified path. Returns null if the specified path doesn't exist or if this dimension was never seen." getAllChildren (:32-37): "all child labels with non-zero counts under the specified path". For a path without children getTopChildren returns null in SSDV and taxonomy faceting alike (AbstractSortedSetDocValueFacetCounts.java:364-371), so the null is not the defect by itself; the defect is that shoes has a child. getTopDims (:59-69): "Results should be the same as calling getAllDims", which drops null results (AbstractSortedSetDocValueFacetCounts.java:122-125).
• Accepted input. FacetField.verifyLabel (FacetField.java:64-73), called for every label and dimension of a SortedSetDocValuesFacetField, rejects only null or empty strings. FacetsConfig "Escapes any occurrence of the path component inside the label" (FacetsConfig.java:552, :582-583). No javadoc, CHANGES or MIGRATE entry limits SSDV label characters.
• Tests. TestTaxonomyFacetCounts#testLabelWithDelimiter (:422) asserts that labels containing U+001F and U+001E work for taxonomy facets. The randomized SSDV tests draw labels from TestUtil.randomRealisticUnicodeString, whose first block starts at U+0000, so they do generate control characters, but almost never the needed pair of sibling labels.
• History. In LUCENE-4795 (2013) mikemccand wanted labels to be allowed to use the delimiter; LUCENE-5339 (4.7.0) replaced the restriction with escaping and rewrote testLabelWithDelimiter, which had expected such a label to be rejected, to assert that labels containing U+001F and U+001E are counted. LUCENE-10250 (#509, 9.1.0) built the tree from adjacency; its review praised "the first child will always have to be one value greater than the parent ordinal" as a memory saving and never discussed characters below the delimiter.
• Consistency. Taxonomy faceting with the same labels and config returns red (1) under shoes (executed control).

The strongest "intended" case: building the tree from sorted order is a deliberate, reviewed memory optimisation (rmuir in #11286: "due to the sorted order, we really do effectively have a tree already"); in 2013 a committer argued that U+001F is "really not expected to be part of a category string" and that applications should keep it out; control characters in labels are unclean data; the facet API is @lucene.experimental; and the dimension-name variants are contrived.

Why it fails: the premise holds only if the separator is the smallest byte that can follow a label, which the encoding does not guarantee, and FacetsConfig itself writes U+001E, which sorts lower. The 2013 stance was replaced by deliberate escaping in LUCENE-5339, backed by an upstream test, and taxonomy faceting handles the same labels. The API accepts these labels and nothing documents a restriction; silently moved children are not a reasonable reading of "unclean data", and @lucene.experimental is about API stability, not wrong counts. The case is weakest for labels containing U+001F/U+001E (escaped on purpose); for raw TAB/CR/LF a committer could reasonably prefer to reject raw control characters in SSDV labels from now on, and the dimension-name variants are contrived. Verdict: a defect (adjudication: confirmed, high), of low likelihood; every check called it real except the refute-lens review, whose "not real" (low) was procedural because it could not run anything.

For clean data (each dimension's terms contiguous, every first child right after its parent) the kept state has the same size as today (a bit set and a sibling array); a dimension split by another one's terms keeps arrays over its whole first-to-last ord range, and the new first-child array appears only for a dimension that needs it. Nothing in the index changes, so no reindex is needed. Nothing was benchmarked. The patch touches the same counting code as two other SSDV facet bugs (a never-seen hierarchical dimension throwing, and the unescaped bare dimension term of flat requireDimCount dimensions), so if they are fixed together one patch needs a rebase.

Three files in lucene/facet/src/java/org/apache/lucene/facet/sortedset/, +175/-127. DefaultSortedSetDocValuesReaderState: one pass over all ords replaces the run-by-run loop. A stack holds the earlier terms that are byte prefixes of the current term (pop while an entry is longer than the common prefix with the previous term). A term's parent is the topmost entry with one component less that the term continues with the delimiter byte; it is always on the stack, because the parent sorts first and every term in between starts with its bytes. Links go into two transient int[] of the field's value count. Each hierarchical dimension keeps its first and last ord (terms of color<TAB> inside the range of color are never linked from it); each flat dimension records its bare dimension ord and its label range separately. DimTree gets a package-private constructor with an optional int[] firstChild, used by iterator(pathOrd) when present. AbstractSortedSetDocValueFacetCounts looks up the bare dimension term of a flat multi-valued requireDimCount dimension and skips ordRange.start() only when it is that term.

// DefaultSortedSetDocValuesReaderState, single pass over ords (condensed)
int common = commonPrefixLength(previous.get(), term);
while (openPaths.isEmpty() == false && openPaths.peek().length > common) {
  openPaths.pop();
}
if (components.length > 1) { // link to the entry it continues with U+001F
  OpenPath parent = findParent(openPaths, term, components.length - 1);
  if (parent != null) {
    if (parent.lastChild == INVALID_ORDINAL) firstChild[parent.ord] = ord;
    else siblings[parent.lastChild] = ord;
    parent.lastChild = ord;
  }
}
openPaths.push(new OpenPath(ord, term.length, components.length));

Trade-offs

• Kept state: for clean data the same size as today. A dimension whose terms are interleaved with another dimension's (the split case) keeps its arrays over its whole first-to-last ord range, the interleaved ords included (today only the last, overwritten run is kept); a dimension that needs first-child links also keeps an int[] firstChild over that range (+4 bytes per ord of the range).
• Construction: two transient int[valueCount] instead of today's per-dimension boxed ArrayList<Integer> and ArrayList<Boolean>; per ord one Arrays.mismatch against the previous term, and per hierarchical term a walk down the stack of open prefix paths, whose length grows with the depth of the hierarchy. Not benchmarked.
• Queries: one lookupTerm each time the children of a flat multi-valued requireDimCount dimension are iterated (getTopChildren, getAllChildren, getAllDims), and in getTopDims one more per such dimension to rank it.
• Compatibility (argued, not tested): a split flat requireDimCount dimension's public OrdRange in the default state now holds only its labels, which direct callers of getOrdRange may notice; custom states that keep today's layout should still work, because the dimension term is then found at ordRange.start(). No test covers a custom state.
• If the unescaped bare dimension term (a separate bug) is fixed by escaping it, the new lookup must use the escaped form.

What the checks validated

• Scratch worktree of a9779ef3c193, gradle, JDK 25: the new test fails 4 of 6 on stock (assertions on and off) and passes 6 of 6 with the fix; the whole :lucene:facet:test, 40 suites and 312 tests, 0 failures, with assertions on and off; TestSortedSetDocValuesFacets with -Ptests.nightly=true -Ptests.iters=5, 95 tests, 0 failures; :lucene:demo:test, 23 tests, 0 failures; :lucene:facet:check -x test (google-java-format, ecj lint, forbidden APIs) passes.
• Standalone runner with the fix shadowed: the finder's and the other checkers' tests 24 of 24, assertions on and off (18 fail on stock, assertions on); the finder's exhaustive check drops from 1,290 to 0 mismatches over 4,525 indexes; the randomized differential check passes 20 of 20 runs (at least 300 random indexes each) with assertions on and off; on stock all 20 runs fail, each at its first or second index.

As suggested in #11286, the prefix path U+001F marks a path's children: DimTree.iterator(pathOrd) could find the first child with one lookupTerm instead of assuming the next ord.

Trade-offs

No extra memory, but term lookups per call; the dimension-split handling of the first option is still needed. Not run.

Like the first option, but DimTree always keeps int[] firstChild.

Trade-offs

Simpler; +4 bytes per ord of every hierarchical dimension, the memory the #509 review chose to save. Not run.

Throw for U+0000-U+001F and change the escape scheme so no escaped byte sorts below the delimiter.

Trade-offs

Not recommended: rejects inputs accepted today and supported by taxonomy facets, changes the term encoding while existing indexes stay wrong, and undoes the escaping of LUCENE-5339. A narrower variant, rejecting only raw C0 controls (not the escaped U+001E/U+001F) from now on, is a defensible compatibility choice for raw TAB/CR/LF, but leaves labels containing U+001E/U+001F and existing indexes wrong.

Say that SSDV labels must not continue a sibling label with a character below U+001F.

Trade-offs

Not recommended: leaves silent wrong results for inputs the API accepts and that FacetsConfig itself produces when escaping.

Method: code reading, then bounded-exhaustive checking (the hunt's "non-formal" tier), a hunt unit (OrdinalMap and its global-ordinal consumers), 2026-10-26.

• While reading the consumers of OrdinalMap's global ords, the finder read "next ord must be a direct child of current ord, this is because we are indexing all ancestral paths" (DefaultSortedSetDocValuesReaderState.java:162-163) and asked what sorts between a path and its children. A probe on the stock jar confirmed it.
• A bounded-exhaustive check of the real jar against brute force (one hierarchical dimension, labels a, a<TAB>, a U+001F, a b, b; every set of 1-3 distinct paths of depth 1-2; 4,525 indexes; every indexed path and the root checked with getAllChildren) found 1,290 mismatching sets: within that universe exactly those with sibling components p and q whose encoded forms continue each other with a byte below 0x1F (a TAB, or the U+001E that FacetsConfig writes in front of a U+001F) where p has a child, and no others, with assertions on and off. It is an exhaustive check of that small universe, not a proof for every label or depth.
• The finder reduced it to a 6-test public-API JUnit; then independent AI tools reproduced, reviewed and judged it (see the checks).