[Feature Request] Make use of dynamic pruning for faster cardinality aggregations

[rishabhmaurya]

Is your feature request related to a problem? Please describe

Dynamic pruning algorithms work by dynamically adding negating filters into the query as disjunctions which are non-competitive( or found to be no more competitive while query execution) to prune the search space.
One of the utility is cardinality aggregations. Instead of using negative filter in lucene, if the field is a low cardinality field (to avoid explosion of disjunctions), then the query can be rewritten as a disjunction query of all the unique terms of the field. As the matching documents are evaluated, if the field value is a unique encountered so far, then it can be safely removed from the disjunction query. This ensures that the documents aren't processed twice for a unique value of a field on which cardinality aggregation is run. Also, the query will be early terminated if all disjunctive filters are exhausted.

Describe the solution you'd like

This logic can easily be embedded into Query.rewrite() method when the cardinality aggregation is the only aggregation and field is low cardinality field. Field cardinality upper bound for a query can be estimated either from FieldReader size() or SortedSetDocValues getValueCount().

We need run some benchmarks in order to know when to start enabling this optimization as it may not be very helpful in smaller corpus. I propose running it against noaa workload - https://github.com/opensearch-project/opensearch-benchmark-workloads/blob/bdbd4bbd74fbf319398de1ca169f16744821bcde/noaa/operations/default.json#L765

Related component

Search:Aggregations

Describe alternatives you've considered

No response

Additional context

No response

[rishabhmaurya]

cc @getsaurabh02 @msfroh let me know your thoughts

[rishabhmaurya]

this is the idea from the blogpost - https://www.elastic.co/blog/faster-cardinality-aggregations-dynamic-pruning

[rishabhmaurya]

Here is my attempt at it rishabhmaurya#74 . Thanks @msfroh for suggesting work around to maintain the invariant of Conjunction DISI by lazily propagating the docID on next()/advance() and also validating this approach.

@kkmr and @msfroh Let me know your thoughts, if below algorithm is reasonable enough to proceed here?
Also, if we can optimize upon any of these steps?

Here is the breakdown of algorithm -

1. Check for all preconditions on when this optimization can be enabled -

• 1. Only enabled when Cardinality Aggregation is the only aggregation.
• 2. The field is a low cardinality field.
• 3. Field type is one of Keyword, Numeric?
• 4. Other?

2. Once preconditions are met, while collectors are created and picked for a given segment, create a DynamicPruningCollectorWrapper to wrap the collector with optimization.

3. DynamicPruningCollectorWrapper will enumerate all the terms for the given field and creates a DisjunctionWithDynamicPruningScorer similar to DisjunctionScorer in lucene in conjunction with the parent query. DisjunctionWithDynamicPruningScorer scorer should have following capabilities in addition to what DisjunctionScorer have -

• 1. #removeAllDISIsOnCurrentDoc() - it removes all the DISIs for subscorer pointing to current doc. This is helpful in dynamic pruning for Cardinality aggregation, where once a term is found, it becomes irrelevant for rest of the search space, so this term's subscorer DISI can be safely removed from list of subscorer to process.
• 2. #removeAllDISIsOnCurrentDoc() breaks the invariant of Conjuction DISI i.e. the docIDs of all sub-scorers should be less than or equal to current docID iterator is pointing to. When we remove elements from priority queue, it results in heapify action, which modifies the top of the priority queue, which represents the current docID for subscorers here. To address this, we are wrapping the iterator with SlowDocIdPropagatorDISI which keeps the iterator pointing to last docID before #removeAllDISIsOnCurrentDoc() is called and updates this docID only when next() or advance() is called.

4. When collection of document will start and DynamicPruningCollectorWrapper is used, it will collect all the documents at once by iterating over all the document from the query created in step 3.

5. Dynamic pruning step when collecting a document - when a match is found, all the terms for a given document will be enumerated and collected for cardinality computation. Once done, the subscorer DISI corresponding to each of these terms collected, can be safely removed from the DisjunctionWithDynamicPruningScorer by calling removeAllDISIsOnCurrentDoc(). Once all docs are collected, we can straightaway throw CollectionTerminatedException for early termination of query.

The code change contains a test which covers a happy case - https://github.com/rishabhmaurya/OpenSearch/pull/74/files#diff-8c88c6062265deccbf9f504a86750ae8f6e1ae53350f91f8a226e7886d6c3e7cR101

[kkmr]

I will take this forward

[bowenlan-amzn]

Will work on this.

[bowenlan-amzn]

TODO

• Find the suitable benchmark for the cardinality aggregation