RandomSamplingFacetsCollector never samples the first hit of a segment that starts mid-bin

RandomSamplingFacetsCollector (lucene/facet, opt-in) estimates facet counts from a sample: when a query has more than sampleSize hits, it cuts the hits, in doc order across segments, into bins of binSize = (int) (1.0 / samplingRate) hits and keeps the hit at a random offset in each bin; amortizeFacetCounts divides the sampled counts by samplingRate = sampleSize / totalHits. A bin that a segment boundary cuts in two is carried into the next segment through leftoverBin and leftoverIndex. At the end of a segment createSample handles only randomIndex > counter and randomIndex < counter; when the chosen hit is the first hit of the next segment (randomIndex == counter) neither branch runs, so the carried bin gets no sample, or one at a stale offset. The first hit of a segment that starts mid-bin is therefore never sampled, the sample is smaller than getSamplingRate() says, and amortized counts come out low, silently, in every release since 4.8.0. On average the sample shrinks by at most about (segment boundaries) / (hits): for 4 hits in segments [1 | 3] half the seeds sample 1 hit instead of 2, at 19,940 hits over 20 segments the loss is about 0.05%. The fix is > to >=.

1. Sampling starts in getMatchingDocs() when totalHits > sampleSize (RandomSamplingFacetsCollector.java:132-134): samplingRate = (1.0 * sampleSize) / totalHits (:137); createSample then runs once per segment, in order (:149-155), with binSize = (int) (1.0 / samplingRate) (:164).
2. A segment's first bin (:169-177): if a bin was carried over, limit = leftoverBin and randomIndex = leftoverIndex ("either NOT_CALCULATED, which means we already sampled from that bin, or the next document to sample"); otherwise limit = binSize and randomIndex = random.nextInt(binSize).
3. The loop (:179-189): the hit at counter == randomIndex is sampled (:180-181, the only sampleDocs.set); when counter reaches limit a new bin starts with a fresh randomIndex.
4. End of segment (:191-207): counter == 0 clears the carry-over (:196): the segment ended on a bin edge, or had no hits. A segment with no hits still gets its own MatchingDocs, so it ends an outstanding carry-over (the loss the comment at :191-195 accepts) and the next segment starts a fresh bin, not mid-bin. Otherwise leftoverBin = limit - counter (:198), then if (randomIndex > counter) (:199, "the document to sample is in the next bin") sets leftoverIndex = randomIndex - counter (:201), and else if (randomIndex < counter) (:202) sets NOT_CALCULATED (:205). With randomIndex == counter the hit to sample is offset 0 of the next segment, but neither branch runs.
5. What is left in leftoverIndex. Usually -1 (its initial value, :83, or cleared at :196 / :205): the carried bin starts with randomIndex = -1 and gets no sample. If an earlier carry left an offset k >= 1 that nothing cleared, the carried bin samples offset k instead of 0, or nothing when k is past the bin's end (follows from the code; not isolated in a test). A bin is never sampled twice.
6. Consequence. leftoverIndex is only ever -1 or >= 1 (:83, :196, :201, :205), and a segment that starts mid-bin starts its loop with counter = 0, so its first hit is never sampled.

In the repro, XORShift64Random(1).randomLong() is 0x2200011 (odd), so the first nextInt(2) is 1 (:55-71). Segment 1 (1 hit): limit 2, randomIndex 1; counter ends at 1, equal to randomIndex, so leftoverBin = 1 and leftoverIndex stays -1. Segment 2 (3 hits): the carried bin has limit 1 and randomIndex -1, so hit 1 is skipped; hits 2 and 3 form a fresh bin and one of them is sampled. Total 1; with >= it is 2.

A boundary inside a bin hits the equal case with probability about 1/binSize, so a query with B such boundaries loses up to about B/binSize of its about totalHits/binSize sampled hits: at most about B/totalHits. Executed: a bounded-exhaustive check on the stock jar (3-12 hits, sampleSize 2-3, every split into 1-3 segments, 50 seeds) left 8,429 of 76,250 complete bins without a sample and none with two, 0 with the fix. At 20 segments of 997 hits (sampleSize 200, binSize 99, 3,000 seeds) the first hit of a segment that starts mid-bin was sampled 0 of 57,000 times, 577 with the fix (about 576 expected); the mean sample was 201.285 against 201.393.

• Who. Only applications that opt in to facet sampling with RandomSamplingFacetsCollector (its constructors, or createManager(sampleSize, seed) with IndexSearcher.search). A read-only code search (2026-10-26) found no use of the class in Elasticsearch, OpenSearch or Solr.
• When. A multi-segment index and a query with totalHits >= 2 * sampleSize, so that binSize >= 2; with binSize 1 every hit is sampled and no bin crosses a boundary. Each segment boundary that falls inside a bin then triggers it with probability about 1/binSize, as long as the next segment has hits (a segment with no hits drops the carried bin anyway). Deterministic for a given seed and segment layout, with assertions on and off.
• What the user sees. Silently smaller samples than getSamplingRate() implies and amortized counts biased low. The first hit of every segment that starts mid-bin has sampling probability exactly 0: a systematic bias, not sampling noise.
• How much. Large only for few hits over many segments: in the repro half the seeds sample 1 hit instead of 2 and the mean amortized count is 3.0 instead of 4; in small filtered multi-segment probe indexes 66 of 2,400 searches got an empty sample and so no facet result, 0 with the fix. Negligible at the scale the feature targets (CHANGES.txt: "in cases where there are millions of hits"): about 0.05% of the sample at 19,940 hits over 20 segments.

ByteBuffersDirectory, NoMergePolicy and one commit give exactly the segments [1 | 3]; a plain IndexSearcher without an executor runs one slice on the calling thread. Segments [1 | 3] put a boundary inside bin {0,1}; sampleSize 2 on 4 hits gives binSize 2 exactly, so the binSize truncation of LFV-437 plays no part; sampler seed 1 makes the first draw 1, the equal case (any small odd seed does the same). Bin {2,3} lies wholly in segment 2 and is always sampled, so one total count is enough. The test sits in package org.apache.lucene.facet only to live next to TestRandomSamplingFacetsCollector; it uses nothing package-private.

It compiles against 10.4.0 and later: MatchAllDocsQuery.INSTANCE first appears in 10.4.0 (#15499), and the unchanged test does not compile against the 10.3.2 jars. It fails on main and on the 10.6.0 and 10.5.2 jars. For 10.0-10.3 use new MatchAllDocsQuery(): that one-token variant fails the same way on 10.0.0. It does not compile against 9.x (MatchingDocs fields, not record accessors), where the hunt's per-era variants show the same failure.

Regression test: this same test; it passes with the recommended fix and fits as one more method of TestRandomSamplingFacetsCollector.

cp $REPRO/TestRandomSamplingSegmentBoundary.java $LUCENE/lucene/facet/src/test/org/apache/lucene/facet/
cd $LUCENE && ./gradlew :lucene:facet:test --tests TestRandomSamplingSegmentBoundary -Ptests.seed=DEADBEEF -Ptests.asserts=true
# the same with -Ptests.asserts=false (without the flag, seed DEADBEEF also runs with assertions off)

# gradle, stock 645d4fe14a20, -Ptests.seed=DEADBEEF -Ptests.asserts=false (stack trimmed; the same with assertions on)
TestRandomSamplingSegmentBoundary > testBinCrossingSegmentBoundaryIsSampled FAILED
    java.lang.AssertionError: sampled hits expected:<2> but was:<1>
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:C327B571467E623A]:0)
        at junit@4.13.2/org.junit.Assert.assertEquals(Assert.java:647)
        at org.apache.lucene.facet.TestRandomSamplingSegmentBoundary.testBinCrossingSegmentBoundaryIsSampled(TestRandomSamplingSegmentBoundary.java:57)

# with '>' changed to '>=' at RandomSamplingFacetsCollector.java:199
# result: BUILD SUCCESSFUL, 1 test, 0 failures, with assertions on and off

• The comments. The branch that misses the case reads "the document to sample is in the next bin" (RandomSamplingFacetsCollector.java:200); the read-back says leftoverIndex is "either NOT_CALCULATED, which means we already sampled from that bin, or the next document to sample" (:171-172). In the equal case neither holds: the bin was not sampled.
• The contract. The sampleSize javadoc: "sampling will be done using a sample ratio of sampling size / totalN" (:97-99); getSamplingRate() "Returns the sampling rate that was used" (:256-259), and amortizeFacetCounts divides by it (:240, :249).
• Design history (#6539, LUCENE-5476). An early patch's notes (Rob Audenaerde) listed that in a small segment "there might be a few hits that are never touched", and Michael McCandless replied "I think these limitations are acceptable?". Shai Erera then noted that createSample "doesn't carry over the bin residue to the next segment ... it might affect the total sample size", and their last patch revision before the commit "Fixed a bug in how carryOver was implemented – replaced by two members leftoverBin and leftoverIndex", asking for "another look, to make sure this time leftover works well". The equal case was never discussed.
• Tests. The only upstream test, TestRandomSamplingFacetsCollector, checks a chi-square bound on per-segment sample proportions and amortized counts within 1.0 of the expected value. Both tolerate this loss; it passes with and without the fix.

The strongest case for "intended" (rated moderate by the cross-model reviews): sampleSize is only "The preferred sample size" (:97); getMatchingDocs warns that per-segment MatchingDocs "might be empty (not containing any hits) as result of sampling" (:115-116); the comment at :191-195 accepts dropping the carry-over after a segment with no hits ("complicates the code and doesn't seem so important"); and the 2014 thread called small-segment losses acceptable.

Why it fails: that accepted loss is scoped to the counter == 0 branch, whose comment covers a segment that ends exactly on a bin edge (nothing is lost) and a segment with no hits (the only case that drops an outstanding carry-over); here the segment has hits and the else branch computes the carry-over with the wrong comparison. The "acceptable" remark concerned an early patch with no carry-over, which was then added to fix it. The bug is not limited to tiny segments: any boundary inside a bin hits it with probability 1/binSize. Giving a reachable hit sampling probability 0, or reusing a stale offset from an earlier bin, is not a trade-off, and the fix costs nothing. Verdict: not intended, a defect (the independent reproduction, the cross-model review, the intended-behaviour check and the adjudication).

Option A was built and run through gradle. B is the same behaviour written as one assignment, so that no stale value can survive; C (document the loss) is not recommended. Workarounds that need no fix: exact counting with a plain FacetsCollector when the hit count is small relative to the number of segments, or a single-segment index.

In the equal case leftoverIndex becomes 0, so the next segment samples its first hit. The comment "the document to sample is in the next bin" then covers the equal case too ("next segment" would be clearer). One file, +1/-1.

       } else {
         leftoverBin = limit - counter;
-        if (randomIndex > counter) {
+        if (randomIndex >= counter) {
           // the document to sample is in the next bin
           leftoverIndex = randomIndex - counter;
         } else if (randomIndex < counter) {

Trade-offs

• Cost. None: one comparison per segment.
• Behaviour change. For a fixed seed, which hits are sampled changes whenever the equal case occurs: the bin that lost its sample gets one again, so the sample and amortized counts rise. Tests or applications that pin a seed and expect exact sampled counts would see different numbers. Worth a CHANGES.txt entry under Bug Fixes.
• Scope. A closes only the equal case. The binSize truncation (LFV-437, so the sample can still exceed sampleSize: mean 201.393 for sampleSize 200 in the scale check with the fix), the documented drop of a carried bin after a segment with no hits (:191-196) and the multi-slice reduce (LFV-765) are unchanged.
• Neighbours. Open PR #16847 edits createSample (maxDoc() to maxLeafDoc()), so a fix may need a rebase; LFV-437, LFV-425 and LFV-765 in the same collector have their own fix sites.

What the checks validated

Applied to a scratch worktree of 645d4fe14a20 and run through gradle with OpenJDK 25.0.3, seed DEADBEEF (2026-10-31):

• stock: the minimal test fails with assertions on and off;
• with the fix: the minimal test passes with assertions on and off;
• the closest suite TestRandomSamplingFacetsCollector passes with -Ptests.iters=10 (10 runs, 0 failures);
• the whole :lucene:facet:test, the new test included, passes (40 classes, 307 tests, 0 failures, 7 skipped);
• checkGoogleJavaFormat, ecjLintMain, ecjLintTest, forbiddenApisMain and forbiddenApisTest for facet pass.
• Earlier, the same change made the finder's test, the independent reproduction's 5 tests (0 of 58,240 bins empty), the bounded-exhaustive model (0 of 76,250), the upstream sampling test (5 iterations), the 4.8.0 history run and the security probe (first hits of mid-bin segments sampled 1,665 of 5,200 times instead of 0) come out right.

leftoverIndex = randomIndex >= counter ? randomIndex - counter : NOT_CALCULATED; after leftoverBin = limit - counter;.

Trade-offs

Same behaviour as A by reading (A's else if (randomIndex < counter) is always true when reached), and it shows that leftoverIndex is always assigned. A slightly larger diff.

Say in the javadoc that a bin crossing a segment boundary may lose its sample.

Trade-offs

Keeps a reachable hit at sampling probability 0 and a sampling rate that overstates the real one, for no saving: the fix is one character.

Method: non-formal (the hunt's tier for findings from code reading and directed testing).

• Code reading. While building the count and statistic inventory of lucene/facet, the finder noticed that the end-of-segment block of createSample tests only randomIndex > counter and randomIndex < counter.
• Bounded-exhaustive check. A driver over the stock jar checked the invariant the code comments state, one sampled hit per complete bin in doc order across segments, for sampleSize 2-3, 3-12 hits, every split into 1-3 segments and 50 sampler seeds: 8,429 of 76,250 complete bins empty, none doubly sampled; 0 empty with the one-character fix.
• JUnit. A public-API test (4 documents in [1 | 3], sampler seeds 1..20) failed on main, 10.5.2 and 9.12.3; a 2026-10-29 minimization cut it to the one-seed test above.