LRUQueryCache on main gives one query only 1/16 of the cache, so a filter over more than 16 segments never hits

On Lucene main an LRUQueryCache built with the public 2-arg or 4-arg constructor is split into 16 partitions, and each partition is limited to maxSize / 16 entries and maxRamBytesUsed / 16 bytes (#15558). Since #16657 the partition is chosen from query.hashCode() alone, so every per-segment entry of one query lands in the same partition. A filter cached on more than maxSize / 16 segments therefore evicts its own entries in LRU order and, when every search looks it up on the same segments in the same order (as in the repro: one thread, no executor), never hits: with maxSize 256, the class javadoc's example, a TermQuery over 17 one-document segments gets 0 hits on the second identical search, while the cache holds 16 of its 256 entries and 15 partitions are empty. Results stay correct, but the cache rebuilds every DocIdSet on every search. The verbatim javadoc configuration (2-arg constructor, UsageTrackingQueryCachingPolicy) shows the same over 20 and 34 segments of 10,000 documents. Main only (future 11.0) and opt-in: caching is off by default on main. 10.5.2 and the parent commit of #16657 get all 17 hits. A fix that enforces the budget for the cache as a whole and evicts the oldest entry across partitions passes the test and 2,340 tests of the search package.

1. Sixteen hard shares. The 4-arg constructor always passes 16 partitions (:150); the 2-arg constructor delegates to it (:252). The 6-arg constructor gives each partition maxSize / numberOfPartitions entries and maxRamBytesUsed / numberOfPartitions bytes (:191-196). From #15558 (d50fb36d9af).
2. Routing by query only. get and putIfAbsent pick the partition with query.hashCode() & (numberOfPartitions - 1) (:424-426, :435-437), and so does getPartitionNumber (:1269-1279, used by cleanUp). The comment at :1273-1276 gives the reason: "so that every (segment, query) entry for a given query lands in the same partition. This lets each partition maintain a complete, cache-wide view of the queries it holds (see uniqueQueries), which is what makes per-partition query canonicalization and count-once RAM accounting correct." From #16657 (fadd63e0eb4).
3. Per-partition LRU eviction. After each insert, evictIfNecessary (:1223-1248) evicts in access order (LinkedHashMap(16, 0.75f, true), :960) while requiresEviction() holds, which compares the partition with its own share: size > maxSize || this.ramBytesUsed > maxRamBytesUsed (:1214-1221).
4. The cliff. All S per-segment entries of one filter compete for maxSize / 16 slots (16 with 256). A search visits the segments in order; the 17th insert evicts the least recently used entry, the same filter's entry for segment 0. The next search misses there, re-inserts it and evicts segment 1's entry, and so on. Each miss builds the DocIdSet again. The zero holds when every search looks the filter up on all its segments in the same order and nothing else evicts from that partition (the repro: one thread, no executor, an always-cache policy); other visit orders, executor slices or policies that cache only some segments were not run.
5. Before #16657 the partition came from QueryCacheKey.hashCode(), then 31 * identityHashCode(segment key) + identityHashCode(query), so a query's 17 entries spread over the 16 partitions and all hit.
6. The memory share works the same way. One query's entries must also fit in maxRamBytesUsed / 16. One cache shared by several readers, as the class javadoc allows (:80-81), counts all readers' entries of a filter together. The same javadoc also advises "to not share this cache across too many indices" (:70-72).

• Who is exposed. Main only (future 11.0), and only applications that configure a query cache: caching is disabled by default on main (IndexSearcher.java:82-84, CHANGES #14187). Every cache built with the public 2-arg or 4-arg constructor has 16 partitions.
• What it takes. A filter cached on more than floor(maxSize / 16) segments, or on that many (reader, segment) pairs when one cache is shared by several readers: 17 with the class javadoc's 256, 63 with MIGRATE.md's 1,000. With the 2-arg constructor only segments that pass MinSegmentSizePredicate(10000) count: at least 10,000 docs and more than half the average docs per segment (LRUQueryCache.java:278-296); the javadoc-config runs use equal 10,000-doc segments, which pass both checks. Ordinary index shapes: #12140 was about a 34-segment index.
• Effect. The cache rebuilds every DocIdSet on every search and gives nothing back, while it holds a small fraction of its budget (16 of 256 entries, 22,560 of 52,428,800 bytes in the javadoc config). The study's indicative timing (shared machine, no JMH) put the 16-partition cache at about no-cache cost and a 1-partition cache 3-5x faster for 34 segments.
• Silent. No exception or log; only getHitCount(), getCacheCount() and getEvictionCount() show it.
• Results stay correct in every run.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: cache hits on the second search expected:<17> but was:<0>
       org.junit.Assert.fail(Assert.java:89)
       org.junit.Assert.failNotEquals(Assert.java:835)
       org.junit.Assert.assertEquals(Assert.java:647)
       org.apache.lucene.search.TestLRUQueryCacheManySegments.testFilterOverSeventeenSegmentsIsCached(TestLRUQueryCacheManySegments.java:67)

• Contract. LRUQueryCache.java:61-62 ("evicts queries using a LRU (least-recently-used) eviction policy in order to remain under a given maximum size and number of bytes used"); :138-139 and :244-245 ("cache at most maxSize cache entries (each entry being a segment-query pair) with at most maxRamBytesUsed bytes of memory").
• Stale placement sentence. :66-68: "the same query cached against different segments results in separate cache entries that may reside in different partitions" (written by #15558, not updated by #16657).
• Example configurations. Class javadoc :76-86 (maxNumberOfCachedQueries = 256, 50 MB, 2-arg constructor, shareable "across several queries and readers"); MIGRATE.md:227-236 (new LRUQueryCache(1_000, 50 MB) to turn caching back on).
• Intent record. In #16657 msfroh suggested moving the canonical uniqueQueries map into the partitions (comment 5625039695). In the reply by the author, sgup432, throughput is the reason given for the earlier (segment, query) routing, and concentration is the trade-off named for routing by query: "the partition number is decided based on the composite key - (segment, query) for better throughput. Until unless we route to partition by queries only ... But the tradeoff being a hot-query segments concentrate in one partition" (comment 5625728241). msfroh noted that "eviction is managed on a per-partition basis" (comment 5626616110); the benchmarks posted on #16657 measure throughput only. In #15558 the author explained that "16 partitions, with each having 1 as maxSize" made a test miss a query's second segment entry, and enlarged the test cache (comment 3752469966). Nobody in #16657 (approved with no review comments), #15558 or #14222 stated what the concentration does to capacity or hit rate: that one query's entries are capped at maxSize / 16, or that a filter over one more segment gets zero hits. The evidence shows stale documentation and a real cliff, not that the maintainers rejected the cap.
• Why tests missed it. TestLRUQueryCache builds caches far larger than its indices, pads sizes by 16 since #15558 (:117-118, :742), or uses one partition (:2236-2238, where the comment "160 so that each partition(total 16 by default) can hold 10 keys at max" sits over a cache built with 1 partition); #16657's three tests use 1- or 2-segment indices (maxSize 1,000,000 at :2859-2901, 100 at :2918-2976). No test asserts hits for one filter over more than maxSize / 16 segments.
• Precedent. #12140 "LRUQueryCache disabled for indices with more than 33 segments" (type:bug, closed as completed in 2023): a cache that silently never helps on a realistic index was treated as a bug.

Strongest case (the cross-model refute reviewer, rated strong): "at most maxSize" is an upper bound, not a promise that the whole budget is usable under skew; query-only routing is deliberate (:1273-1276); the class is @lucene.experimental (:117); #15558's author knowingly changed what maxSize means, saw 1-entry shares cause a test miss and padded the tests by 16 (#15558 comment 3752469966: maxSize now "denotes the total keys a cache can hold"); #16657's author named the concentration of a hot query's segments in one partition as the trade-off (comment 5625728241); the cache is opt-in and off by default on main; and the repro uses one-document segments and an always-cache policy.

Why we still report it: these facts show that each design choice was deliberate, not that anyone accepted a per-query cap of maxSize / 16 or zero hits beyond it. The cap is undocumented and the class javadoc describes the opposite placement; the documented example sizes hit it, including the verbatim 2-arg configuration on 10,000-doc segments; @lucene.experimental allows API changes, not a silent loss of the cache's benefit. This remains a judgement call: maintainers may choose to document the cap and raise the example sizes.

Three code options were built and run in a scratch worktree of 645d4fe14a20; a documentation-only answer is listed last. If maintainers see the cap as an accepted trade-off, the cache-wide budget and documenting the cap are the two real choices.

Keeps #16657's query-only routing, canonicalization and count-once memory accounting, and #15558's per-partition locks. Each partition may use the whole budget; after each putIfAbsent, evictIfOverBudget() (below) runs without holding any partition lock and, while the cache holds more than maxSize entries or maxRamBytesUsed bytes, evicts the least recently used entry of the partition whose least recently used entry is the oldest. To compare entries of different partitions, QueryMetadata (a record today) becomes a small class with a volatile long lastUsed set to System.nanoTime() on insert and on each lookup; the partition gets eldest() (read lock plus the map's monitor) and evictLeastRecentlyUsed() (the old eviction loop body, same ConcurrentModificationException check). The class javadoc sentence about partitions is corrected.

  private void evictIfOverBudget() {
    while (getCacheSize() > maxSize || ramBytesUsed() > maxRamBytesUsed) {
      LRUQueryCachePartition victim = null;
      long oldestLastUsed = 0;
      for (LRUQueryCachePartition partition : lruQueryCachePartition) {
        final QueryMetadata eldest = partition.eldest();
        if (eldest != null && (victim == null || eldest.lastUsed - oldestLastUsed < 0)) {
          victim = partition;
          oldestLastUsed = eldest.lastUsed;
        }
      }
      if (victim == null || victim.evictLeastRecentlyUsed() == false) {
        return;
      }
    }
  }

Trade-offs

• One System.nanoTime() and a volatile write per lookup; when the cache is over budget, each eviction round peeks 16 partitions (16 read-lock acquisitions). No benchmark was run (LRUQueryCacheBenchmark exists in lucene/benchmark-jmh).
• The totals are read without a global lock, so under concurrent inserts the cache can briefly exceed the budget or evict one entry too many: close to, not exactly, a single cache-wide LRU.
• Side effect: a cache with maxSize < 16 now caches, which changes small-cache behaviour the #15558 author knew of and accepted. Not changed: the memory eligibility guard maxRamBytesUsed / numberOfPartitions (:800), a separate question.

What the checks validated

• The test: stock fails, + fix passes, with assertions on and off, through gradle and the standalone runner.
• + fix, gradle, seed DEADBEEF: TestLRUQueryCache, the new test, TestUsageTrackingFilterCachingPolicy, TestBooleanScorer, TestDocValuesOrdinalSetIterator: 89 tests, 3 skipped (@AwaitsFix, skipped on stock too), 0 failures, assertions on and off; TestLRUQueryCache also with seeds 5EED1234 and C0FFEE; the whole org.apache.lucene.search.* package: 2,340 tests, 49 skipped, 0 failures (the test framework installs an LRUQueryCache as the default cache); :lucene:core:check -x test passes.
• Shadowed into the stock jars: the verbatim javadoc config gets full hits on 12, 20 and 34 segments with 0 evictions; the tie-break probe's 5 tests pass (shared cache 18 of 18, scored MUST + FILTER 17 of 17).
• Full-cache probe (8 segments, maxSize 64, each round one hot filter then a new one-off filter, 40 rounds): hot-filter hits in rounds 20-39 are 0 of 160 on stock and 160 of 160 with the fix, the same as a 1-partition cache (also 264 evictions). Not run: the full test suite, nightly tests, a concurrency stress run, a benchmark.

The same budget change, but the victim is the partition that holds the most entries (or bytes). The repro and the same suites pass.

Trade-offs

In the full-cache probe the hot filter gets 0 of 160 hits in three runs: its partition is the largest, and its least recently used entry is the next one it needs, so the cyclic scan comes back once the cache is full.

Use QueryCacheKey.hashCode() for the partition, as before #16657 (+6/-11). The repro passes.

Trade-offs

#16657's own tests testQueryRamAccountedOncePerDistinctQuery ("8656 should be < 2x 4168") and testCanonicalQueryInstanceSharedAcrossSegments fail: a query is canonicalized and its memory counted once per partition, which #16657 fixed. The hard 1/16 shares stay, so an uneven spread can still evict early. It could be combined with a cache-wide canonical-query map, which the #16657 author discussed (reference counts or weak references).

State that one query's entries are limited to maxSize / numberOfPartitions entries and bytes, correct the class javadoc's partition sentence, and raise the example sizes in the javadoc and MIGRATE.md; or use fewer partitions for small caches.

Trade-offs

Leaves the cliff for anyone who sizes the cache by the entries a workload actually needs.

Method: code reading (non-formal tier). The study's "search-concurrency-model" unit was building a TLA+ model of the cache's concurrency; while reading the code it noted that maxSize < 16 caches nothing and that each partition gets 1/16 of the memory. A verifier (search concurrency model) reproduced those claims and found the larger one: since #16657 one filter over more than maxSize / 16 segments never hits, using the verbatim class-javadoc configuration, a shared cache, a sweep of the cliff, and older LRUQueryCache sources on the main classpath to attribute it to #16657. The hunt then kept only that claim, wrote the one-test repro (repro-minimal/), bisected it with single-commit builds and re-verified it.