Sampled facets on a concurrent searcher sample large slices twice

RandomSamplingFacetsCollector counts facets on a random sample of about sampleSize hits when a query matches more, and amortizeFacetCounts divides the sampled counts by getSamplingRate() to estimate the real ones. Its createManager(sampleSize, seed) is the CollectorManager "for concurrent random sampling": on an IndexSearcher with an executor it gives each slice its own collector and merges them. Since #13542 (10.0.0) the merge builds the merged collector's original hits from each slice collector's getMatchingDocs(), which that class overrides to return the slice's own sample. The merged collector then samples those samples again, while getSamplingRate() reports only the second stage. The hits of every slice with at least about 2 x sampleSize hits are thinned twice, so a label's amortized count is low in proportion to its hits in such slices; with equal slices, as in every repro, the sample is sampleSize^2 x numSlices / totalHits and every count is low by exactly sliceHits / sampleSize (8x, 10x, 16x and 64x). Hits in smaller slices are sampled once and counted correctly. getOriginalMatchingDocs() returns the union of the per-slice samples instead of the original hits. Default slicing is enough (an index with more than 5 segments has 2 or more slices), and intra-segment partitions do it on one segment. No error is raised. A searcher without an executor (or whose search has one slice), and every 9.x release (where the merge read getOriginalMatchingDocs(), as the design asked), sample once. Merging each slice's original hits fixes it; the whole facet test suite passes.

• Facet sampling: RandomSamplingFacetsCollector(sampleSize, seed) keeps about sampleSize hits when a query matches more: it walks the hits in bins of (int) (totalHits / sampleSize) and keeps one random hit per bin. getSamplingRate() is sampleSize / totalHits. getMatchingDocs() returns the sample, getOriginalMatchingDocs() all hits.
• Amortizing: amortizeFacetCounts(result, config, searcher) divides each sampled count by the sampling rate (capped by the label's drill-down term docFreq) to estimate the real count.
• Slices: an IndexSearcher built with an executor splits the index into slices and runs one collector per slice in parallel; a CollectorManager creates the collectors and its reduce merges them. Without an executor there is one slice. Default slicing gives each segment above 250,000 documents its own slice and groups the others, largest first, until a group has 5 segments or more than 250,000 documents (so a group can exceed 250,000); #13542 (10.0.0) added intra-segment partitions.
• createManager(sampleSize, seed): the sampler's CollectorManager, documented as "a CollectorManager for concurrent random sampling through RandomSamplingFacetsCollector".

1. Each slice gets its own RandomSamplingFacetsCollector (RandomSamplingFacetsCollector.java:269-271). Its getMatchingDocs() is overridden: once the slice's hits exceed sampleSize it samples them at sampleSize / sliceHits and returns the sample, one MatchingDocs per segment whose totalHits is copied from the original (:118-141, :209). The unsampled list is getOriginalMatchingDocs() (:143-146).
2. With 2 or more collectors, reduce builds a ReducedRandomSamplingFacetsCollector (:279-282) that fills its original hits from FacetsCollectorManager.reduceMatchingDocs(facetsCollectors) (:291-292). That helper merges the partitions of one segment and reads each collector through getMatchingDocs() (FacetsCollectorManager.java:93-114, line 102): the slice samples.
3. When facet counting asks the merged collector for getMatchingDocs(), it sums the copied totals (the real hit count), sets the rate to sampleSize / totalHits and samples the union of the slice samples again (RandomSamplingFacetsCollector.java:125-140). getSamplingRate() returns this second rate only.
4. amortizeFacetCounts divides by that rate (:240), so the hits of each slice that the first stage thinned count too little, by that slice's sliceHits / sampleSize. The first stage drops hits only when a slice has at least about 2 x sampleSize hits (bin size 2 or more, :164); a smaller slice's hits reach the merge whole, are sampled once and are counted correctly. An executed probe with one slice of 10,000 hits labelled color/x and one of 100 hits labelled color/y, sampleSize 1,000, gives x 1,010 instead of 10,000 and y a correct 100; with the fix, 10,000 and 100.
5. Without an executor the searcher has one slice (IndexSearcher.java:226-231), reduce returns that collector unchanged (RandomSamplingFacetsCollector.java:279-281), and the result is correct; so is any search whose leaves form one slice.

getSamplingRate() is the same in both columns (1/16, 0.05, 1/64, 1/128). The rate applied in the first row is 1/8 x 1/16 = 1/128. In every row (equal slices, integer ratios) the sample size equals sampleSize^2 x numSlices / totalHits; with unequal slices it does not (the probe above samples 110 hits where the formula gives 198).

• Who is exposed. Applications that sample facets with createManager on a searcher built with an executor, on queries whose hits far exceed sampleSize, which is when sampling is used. Taxonomy and sorted-set facet counts both read the merged collector's getMatchingDocs() (read); every repro that counted facets used sorted-set facets, and the taxonomy path was read, not run.
• Default vs opt-in. Two opt-ins, facet sampling and an executor; after that, default slicing is enough (10 segments of 2,000 documents form 2 slices), and intra-segment partitions trigger it on one segment. IndexSearcher.search(Query, Collector) is deprecated in favour of the CollectorManager path "due to its support for concurrency", so createManager is the documented way to sample. The executor constructor is @lucene.experimental.
• Scale. Deterministic: every sampled query on such a searcher whose search has 2 or more slices, one or more of them with at least about 2 x sampleSize hits. A label's amortized count is low in proportion to its hits in those slices; with equal slices, as in every repro, every label is low by exactly sliceHits / sampleSize: 8x, 10x, 16x and 64x. The error grows with the slice size. Hits in smaller slices are counted correctly (executed probe: a label in a 10,000-hit slice amortizes to 1,010 instead of 10,000, one in a 100-hit slice to a correct 100).
• Silent. No exception or log line. getSamplingRate() and MatchingDocs.totalHits look normal, and in these integer-ratio repros the result even looks self-consistent (sampled / originals equals the reported rate), because the "original hits" are already a sample.
• Second broken promise. The class javadoc says "If you require the original set of hits, you can call getOriginalMatchingDocs()". On the merged collector it returns the slice samples (2,000 of 20,000), so the two-pass recipe of the facet user guide (the demo module's facet package overview: find the top facets on the sample, then count them exactly "over the entire matching document set") loses hits too.
• How likely. Plausible: deterministic once both opt-ins meet, but no report exists in the two years since 10.0.0, and no issue in the Elasticsearch, OpenSearch or Solr repositories mentions the collector.
• Not affected. Which documents match, top hits, exact (unsampled) facet counts and the index; searchers without an executor, and searches with one slice; hits in slices below about 2 x sampleSize hits; queries with at most sampleSize hits; 9.x. Nothing is stored wrong, so a fix needs no reindex.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: sampled hits at rate 0.0625 expected:<128> but was:<16>
       org.junit.Assert.fail(Assert.java:89)
       org.junit.Assert.failNotEquals(Assert.java:835)
       org.junit.Assert.assertEquals(Assert.java:647)
       org.apache.lucene.facet.TestSamplingManagerTwoSlices.testSampleSizeWithTwoSlices(TestSamplingManagerTwoSlices.java:64)

• Contract. Constructor javadoc: "If the number of hits is greater than the size, sampling will be done using a sample ratio of sampling size / totalN" (RandomSamplingFacetsCollector.java:97-100). getSamplingRate(): "Returns the sampling rate that was used" (:256). Class javadoc: the original hits through getOriginalMatchingDocs(), and amortized counts (:38-40). createManager: "a CollectorManager for concurrent random sampling through RandomSamplingFacetsCollector" (:261-264), the same sampler run concurrently. All four break once a search has 2 or more slices and one of them has at least about 2 x sampleSize hits.
• Design. LUCENE-10484 (#11520, an issue migrated from JIRA, by @javanna): "the reduction should call getOriginalMatchingDocs instead of getMatchingDocs, which modifies the internal totalHits when called". Its implementation (#765: 7ed0f3d7adb on main, released in 9.2.0 as the branch_9x commit b0ecba4fb24) added each collector's getOriginalMatchingDocs().
• History. #13542 (@javanna, 2024-09-10, intra-segment concurrency) replaced that loop with the new shared helper reduceMatchingDocs, so that partitions of one segment merge into one MatchingDocs. Its PR body names createManager only for that merge ("returned multiple MatchingDocs instances that pointed to the same LeafReaderContext"), and a 2024-07-22 comment by the author lists TestRandomSamplingFacetsCollector.testRandomSampling among the facet tests that failed before the facet code was adapted to partitions; no PR or review comment discusses sample size or rate. Every 9.x release, 9.2.0 to 9.12.3, samples once (executed).
• Tests. TestRandomSamplingFacetsCollector states the intended sample size ("10% of total docs, 20% of the hits", line 96) but asserts only a chi-square over segments and amortized == min(5 x sampled, numDocs / 10) (:133, :135-148). Neither checks the query-wide sample size or compares an amortized count with the true count; the amortized check divides by the merged collector's own rate, so it holds either way, and the test is not built to see this bug.
• Effect size. 16 sampled hits where 128 were asked for, and 256 where 2,048 is the true count, is not sampling noise: the bias is deterministic and the reported rate is wrong.

The strongest "works as designed" case: sampleSize is only "the preferred sample size"; the executor constructor and search(Query, CollectorManager) are @lucene.experimental; createManager never promises the result of one collector; reusing reduceMatchingDocs was deliberate, #13542 was reviewed, and its author saw TestRandomSamplingFacetsCollector fail during that work; FacetsCollector.getMatchingDocs() is documented as "the documents matched by the query", so the sampling override, not the helper, could be blamed; per-slice sampling could be read as a memory saving; the upstream test accepts the result.

Why it fails: the same javadoc sentence fixes the ratio, sampleSize / totalN, and getSamplingRate() reports a rate that was not applied, so the estimates are biased, not merely noisy. getOriginalMatchingDocs() stops returning the original hits. Whichever side is blamed, the sampler's own documented rate and original-hits contract break, and the design issue settled the reduce on getOriginalMatchingDocs exactly because getMatchingDocs is the sampling override ("which modifies the internal totalHits when called"). @lucene.experimental allows API change, not wrong results, and the deprecation of search(Query, Collector) sends users to exactly this path. The reuse was deliberate for the partition merge; nothing in the PR discusses the sample, and every 9.x release reduced the originals. Nor is per-slice sampling a memory saving: each slice collector holds its original hits until the reduce in either case, and each sampled segment is a new bit set of the segment's full size (RandomSamplingFacetsCollector.java:162). The upstream test never checks the sample size. Verdict: a regression (adjudication: confirmed, high; the reproducer, the intended-lens review and the devil's advocate: real; the cross-model reviews rated the intended case weak).

Both validated fixes restore the one-slice numbers in every repro: the same sample sizes, rates and counts. Which documents a fixed seed picks can still differ from one slice, because the merge iterates a hash map of segments. Both were validated through gradle on main only (10.x was run with the release jars, without a fix), and neither was benchmarked. Workaround until a fix ships: run sampled facet collection on an IndexSearcher without an executor, which every test's control shows to be correct, or make sure the search has one slice, for which reduce returns the one collector unchanged (RandomSamplingFacetsCollector.java:279-281). The new test is a ready regression test. Open draft PR #16847 touches both files but not the merge. Only query-time results change; no reindex.

RandomSamplingFacetsCollector.java:291-292, the finder's sketch, +9/-2 lines in one file: wrap each slice's getOriginalMatchingDocs() in a plain FacetsCollector and give those to FacetsCollectorManager.reduceMatchingDocs, which keeps merging partitions of one segment.

      super(sampleSize, seed);
-      this.getOriginalMatchingDocs()
-          .addAll(FacetsCollectorManager.reduceMatchingDocs(facetsCollectors));
+      // Reduce the per-slice ORIGINAL hits: getMatchingDocs() of a slice collector returns that
+      // slice's own sample, and this collector samples the reduced hits again.
+      List<FacetsCollector> originals = new ArrayList<>(facetsCollectors.size());
+      for (RandomSamplingFacetsCollector fc : facetsCollectors) {
+        FacetsCollector original = new FacetsCollector(false);
+        original.getMatchingDocs().addAll(fc.getOriginalMatchingDocs());
+        originals.add(original);
+      }
+      this.getOriginalMatchingDocs().addAll(FacetsCollectorManager.reduceMatchingDocs(originals));

Trade-offs

• One throwaway FacetsCollector per slice. It relies on FacetsCollector.getMatchingDocs() returning its own mutable list, as the plain FacetsCollectorManager reduce already does.
• Side benefit: nothing asks the slice collectors for a sample any more, so the per-slice sampling work (a bit set per segment per slice) disappears.
• The merged collector samples once, with its bins running over the merged segments in hash-map order, as today.

What the checks validated

• Scratch worktree of a9779ef3c193, gradle, JDK 25: the new test fails 3 of 3 on stock with assertions on and off; with the fix, the new test and upstream TestRandomSamplingFacetsCollector pass 4 of 4, on and off, and TestRandomSamplingFacetsCollector passes 20 of 20 iterations; the whole :lucene:facet:test passes, 40 suites and 309 tests, 0 failures, with assertions on (7 skipped) and off (8 skipped); :lucene:facet:check -x test (google-java-format, ecj lint, forbidden-apis) passes.
• Standalone runner with the fix shadowed: the new test 3 of 3 (-ea, -da), printing the one-slice numbers for every several-slice search. The same sketch already passed the finder's, the independent reproducer's, the second verifier's and the devil's advocate's tests, the adjudication's re-run and upstream TestRandomSamplingFacetsCollector (2 seeds).

+19/-3 lines over FacetsCollectorManager.java (+15/-2) and RandomSamplingFacetsCollector.java (+4/-1): an overload of the package-private helper that takes the accessor (the old signature delegates with FacetsCollector::getMatchingDocs), and the sampler's merge passing RandomSamplingFacetsCollector::getOriginalMatchingDocs.

   static Collection<FacetsCollector.MatchingDocs> reduceMatchingDocs(
       final Collection<? extends FacetsCollector> facetsCollectors) {
+    return reduceMatchingDocs(facetsCollectors, FacetsCollector::getMatchingDocs);
+  }
+
+  static <C extends FacetsCollector> Collection<FacetsCollector.MatchingDocs> reduceMatchingDocs(
+      final Collection<? extends C> facetsCollectors,
+      final Function<? super C, List<FacetsCollector.MatchingDocs>> matchingDocsOf) {
     ...
-    for (FacetsCollector facetsCollector : facetsCollectors) {
-      for (FacetsCollector.MatchingDocs matchingDocs : facetsCollector.getMatchingDocs()) {
+    for (C facetsCollector : facetsCollectors) {
+      for (FacetsCollector.MatchingDocs matchingDocs : matchingDocsOf.apply(facetsCollector)) {

   // RandomSamplingFacetsCollector, ReducedRandomSamplingFacetsCollector:
       this.getOriginalMatchingDocs()
-          .addAll(FacetsCollectorManager.reduceMatchingDocs(facetsCollectors));
+          .addAll(
+              FacetsCollectorManager.reduceMatchingDocs(
+                  facetsCollectors, RandomSamplingFacetsCollector::getOriginalMatchingDocs));

Trade-offs

• Makes the dependency explicit for any future subclass whose getMatchingDocs() is not the collected set, and avoids fix A's per-slice wrapper collectors (it adds a Function call per collector instead).
• Touches the shared helper (package-private, so no public API change) instead of one file.

What the checks validated

• Same worktree, gradle: the new test and upstream TestRandomSamplingFacetsCollector pass 4 of 4; the whole :lucene:facet:test passes, 40 suites and 309 tests, 0 failures (assertions on); :lucene:facet:check -x test passes.
• Standalone runner: the new test 3 of 3 (-ea, -da), the finder's test 2 of 2, the independent reproducer's 3 of 3 and the devil's advocate's probe 1 of 1.

Putting back the 9.x loop over getOriginalMatchingDocs() restores the numbers for whole-segment slices, which shows the cause.

Trade-offs

It drops the partition merge #13542 needed: with intra-segment partitions the merged collector would again hold several MatchingDocs for one segment, the failure #13542 fixed. Not proposed.

Method: code reading (the hunt's "non-formal" tier), a hunt unit ("override-hook and accessor-bypass inventory"), 2026-10-27, stock main jars.

• While checking each documented option on every entry path, here the sequential collector against the CollectorManager path of the facet collectors, the hunting AI tool saw that reduceMatchingDocs calls the overridable accessor getMatchingDocs(), which RandomSamplingFacetsCollector overrides to sample. git log -S on both spellings of the merge showed that #13542 replaced getOriginalMatchingDocs() with that call.
• It wrote a differential public-API JUnit (the same manager on a one-slice and a several-slice searcher) and a bounded matrix over the real classes (755 cells, 0 contradictions with the prediction derived from the code, on main and with the fix).
• Then independent AI tools reproduced, reviewed and judged it (see the checks); the devil's advocate added the getOriginalMatchingDocs() symptom and the small-segment default-slicing trigger, and this doc's test combined the three triggers into one upstream-ready class.