Speed up GroupingSelectors when using a descending sort on a high cardinality field
- Dominant language
- Java
- Stars
- 3.6k
- Forks
- 1.4k
- Avg merge
- 2d 11h
- Merged PRs (30d)
- 88
Description
### Description
I've ran a benchmark (using Solr admittedly, not Lucene), that compares the speed of various sorted queries. The fields mentioned in the benchmark are the fields that were sorted on.
Benchmark parameters:
- 1M documents
- High cardinality fields are unique values per document (an incrementing counter)
- Low cardinality fields had 500 unique values
- All fields were single-valued
- The different fields were tested: `LongPointField`, `StrField` and `TrieLongField` (No longer in lucene)
- All sort fields were tested using both DocValues and Uninversion.
- Queries
- 10 results were requested, for both grouped and non-grouped
- Each field type, docValues/Uninversion combination were ran in 8 configurations doing a matrix of:
- Grouping and Non-grouping
- Sort `asc` and `desc`
- High Cardinality values and Low Cardinality values
- The grouping:
- All queries were grouped by a the same string field (250,000 unique values, docValues enabled)
- The sort field was used both for both the group sorting and the document sorting within the groups
Overall there are some interesting findings:
- **For un-grouped queries (sorting by a high cardinality field), ascending sorts were 5x faster than descending sorts. For grouped queries, they were 40x faster.** That is ultimately what this issue is meant to address, so I highlighted it in the chart above.
- Note: Low cardinality fields had no difference in speed
- DocValues and Uninverted fields has similar sorting performance for grouped queries. (This is likely related to https://github.com/apache/lucene/issues/10368)
I know that since this benchmark is using Solr, it's only so useful here. So I can utilize lucenebench to try to recreate this as well, if that would help.
I also have the flame graphs for these benchmarks, which aren't as useful as a screenshot but I will provide one anyways (LongPointField, docValues, highCardinality, grouped, sorted descending):
Contributor guide
Assessment
This issue has not been assessed yet.