Sparse keyword aggregations scan the full dictionary during result construction

perfloop-oss/elasticsearch · INEFFICIENT ALGORITHM

https://perfloop.ai/t/oss/case_vycxvq13jv

Verdict

VERIFIED · settled 2026-10-03

What happened: The paired measurements met the required improvement.

Hypothesis

Default keyword terms aggregations can scan the shard's whole term dictionary after a selective search. Most visited terms have zero counts and cannot enter a positive-minimum-count result. Avoiding those visits could reduce CPU, but the net benefit after recording collected terms has not been measured.

An ordinal is the integer ID assigned to a term. The benefiting consumer operation is GET /index/_search with a top-level keyword terms aggregation, default count ordering and size, min_doc_count=1, no children, and no include/exclude rules. The repository documents queries matching very few documents and the default global_ordinals mode in docs/reference/aggregations/search-aggregations-bucket-terms-aggregation.md:674-706. High-cardinality aggregation fields and retained ordinal mappings are described in docs/reference/elasticsearch/mapping-reference/eager-global-ordinals.md:19-48 and 65-72. These passages support the sparse-search pattern, not a numerical production distribution or its prevalence. The measured fixture is one constructed sample of that pattern on revision f7c7bee6d30a546944fc276965544681c72494b2.

The common route is AggregationPhase.preProcess registering AggregatorCollectorManager, followed by ContextIndexSearcher.search calling doAggregationPostCollection after successful collection or timeout. AggregatorCollector.doPostCollection builds each top-level result. TermsAggregatorFactory.bytesSupplier defaults keyword fields with ordinals to global_ordinals except its known match-no-documents shortcut. For dictionary cardinality above 2048, its filter rewrite and low-cardinality alternatives do not apply. Its single-owner, no-children, no-include/exclude branch chooses dense counting without considering match density (TermsAggregatorFactory.java:92-157, 449-568). No failure, retry, or manual optimization flag is needed for the named workload.

With valueCount greater than zero and excludeDeletedDocs=false, each successfully completed DenseGlobalOrds finalization visits all C=valueCount ordinals. With the unfiltered predicate, it reads each count and forwards only positive counts when min_doc_count is positive. DenseGlobalOrds.buildAggregations then sums forwarded counts, selects shard candidates, and constructs the result. Skipping zero-count ordinals does not discard a contribution to that sum or candidate set. Empty dictionaries take the separate branch at GlobalOrdinalsStringTermsAggregator.java:194-202; exceptions can stop the scan early. The C-visit bound is not a claim about every invocation.

A broader dictionary-sized counter-zeroing repair is not supported by this revision. AbstractBigByteArray.java:26-31 uses a shared zero page, and lines 102-108 allocate backing pages on writes. This proposal therefore targets enumeration rather than claiming that every dense aggregation allocates or clears C long values.

CPU receipt call_BTopihFtnnpw2Bxy8yqDwC0Q ran OrdinalDensityWorkloadTests.testSelectiveDensity through :server:test. Its retained fixture created 100,000 distinct keyword values in one segment and completed 1,000 shard searches, each matching 100 documents with distinct values. It asserted the default dense strategy, 25 shard buckets, and sum_other_doc_count=75. A private Gradle init script disabled the test entitlement agent after an environment-specific attach failure. The aggregation implementation was unchanged.

The verified JFR bundle contains 639 JVM CPU sample counts, including Gradle, indexing, test setup, and repeated searches. Pprof aggregates 34 samples, 5.32% of that receipt's cost, under forEachAllowDeletedDocs; 5 are self samples. This includes required consumer updates and does not estimate a saving. The fixture uses test context construction and mock array/recycler instrumentation, and does not measure REST handling, coordinating-node reduction, or production traffic.

For that fixture, source-derived counts are 100,000 candidate visits versus 100 collected ordinals per completed result: the proposed delta is 99,900 zero-count visits per search, not the required updates for the 100 collected ordinals. A warm sparse search otherwise collects only those matching document/value pairs and builds a bounded shard queue. This supports an inferred dominant-cost prior for dictionary enumeration within aggregation finalization, while the measured frames establish eligible-call cost. Overall shard-query savings remain uncertain, especially because collection bookkeeping can offset the removed scan. The path prior is inferred from the default factory route, not from production frequency.

The internal direction adds no consumer-visible operation, type, protocol, or configuration. The terms documentation still describes this default top-bucket operation. Its recommendation to use composite aggregation when requesting all unique terms (terms documentation:112-116) is a different operation, not an accepted retirement decision for this target. Maintainer acceptance of the proposed internal enumeration change is unmeasured.

The Case proof target is lower total CPU for collection plus result construction in the benefiting selective keyword search, with identical buckets, ordering, counts, and other-document totals. Reproduce the retained fixture with ./gradlew :server:test --tests '*OrdinalDensityWorkloadTests.testSelectiveDensity' -Dtests.seed=4BB9EE064472008C -I .perfloop/ordinal-profile.gradle, then compare baseline and changed full shard-query runs with retained readers and production array/recycler behavior. Dictionary cardinality and match density sweeps are optional samples. Dense match-all searches are regression controls for extra collection bookkeeping, not evidence of sparse benefit; min_doc_count=0 controls protect zero-count semantics. Unchanged or higher whole-query CPU would reject the performance claim. Production prevalence and any effect on end-to-end service latency remain outside this measurement.

Change to test: Record distinct collected ordinals for standard, single-owner keyword terms aggregations without children or include/exclude rules, and enumerate them when min_doc_count is positive, with a density-based fallback to the existing scan. Preserve count storage, bucket ordering, other-document totals, and zero-count/deleted-document behavior without adding public settings.

Where it lives

perfloop-oss/elasticsearch · server/src/main/java/org/elasticsearch/search/aggregations/AggregatorCollector.java

Evidence

100k keyword shard query with 100 sparse hits · 10 sample pairs

metric baseline candidate paired median change confidence range required result
query_thread_cpu_ns 483855 201339 −58.5% (−283196) −292109 to −278577 < −24193 PASSED
ns/op 523681 224064 −57.5% (−301163) −307242 to −293392 ≤ 26184 PASSED

100k keyword shard query, match-all dense control · 10 sample pairs

metric baseline candidate paired median change confidence range required result
query_thread_cpu_ns 3376051 3420616 +1.1% (+38093) −27332 to +154678 ≤ 168803 PASSED
ns/op 3573880 3623037 +1.5% (+52438) −19489 to +161865 ≤ 178694 PASSED

100k keyword shard query memory, match-all dense control · 10 sample pairs

metric baseline candidate paired median change confidence range required result
request_peak_bytes 808480 812288 +0.5% (+3808) +3808 to +3808 ≤ 40424 PASSED
gc.alloc.rate.norm 657628 679559 +3.3% (+21807) +21249 to +22168 ≤ 32881 PASSED

Checks: 1 of 1 passed. Verification: no defect found.

Timeline