apache / apache/lucene

Improve FirstPassGroupingCollector to support early termination and pruning/skipping

Open
#15,136 1 comment 0 reactions 0 assignees View on GitHub
type:enhancement
Dominant language
Java
Stars
3.6k
Forks
1.4k
Avg merge
2d 11h
Merged PRs (30d)
88

Description

### Description

The `FirstPassGroupingCollector` [[1](https://github.com/apache/lucene/blob/main/lucene/grouping/src/java/org/apache/lucene/search/grouping/FirstPassGroupingCollector.java)] from the `lucene-grouping` module is used by OpenSearch to implement `collapse` search queries that deduplicate the search results using a numeric or keyword docvalues field. This logic is implemented in the `CollapsingTopDocsCollector` [[2](https://github.com/opensearch-project/OpenSearch/blob/main/server/src/main/java/org/apache/lucene/search/grouping/CollapsingTopDocsCollector.java)], a subclass of `FirstPassGroupingCollector`.

Comparing the search performance between `CollapsingTopDocsCollector` and the regular `TopFieldCollector` [[3](https://github.com/apache/lucene/blob/main/lucene/core/src/java/org/apache/lucene/search/TopFieldCollector.java)] reveals massive differences, in particular for large hit counts.

Reviewing the source code it looks like the `FirstPassGroupingCollector` lacks many of the features that `TopFieldCollector` provides to improve search performance:

- No support for early terminating search queries when using index sorting.
- No support for non-COMPLETE `ScoreMode`s and setting minimum competitive scores, i.e. no skipping of non-competitive documents even if sorted by relevance score.
- No support for competitive iterators and hit thresholds, i.e. no pruning for indexed numeric sort fields.

This causes the collector to visit all hits exhaustively and causes major performance issues with large indexes.

For example, we have seen search queries with ~1MM hits using an indexed numeric sort field achieve ~15ms with `TopFieldCollector` and ~75ms with `CollapsingTopDocsCollector`. Using a non-indexed numeric sort field (i.e. no competitive iterator is used) the latencies for both collectors are almost equal.

Can the `FirstPassGroupingCollector` be improved to support the features listed above? Or should this be solved with an entirely new collector built from scratch?

I'm looking for guidance from the Lucene maintainers. Thanks!

Ticket reference: https://github.com/opensearch-project/OpenSearch/issues/18861

Contributor guide

Open the contributing guide

Research direction

Start with lucene/grouping/src/java/org/apache/lucene/search/grouping/FirstPassGroupingCollector.java and compare its collection flow with lucene/core/src/java/org/apache/lucene/search/TopFieldCollector.java. Review the OpenSearch CollapsingTopDocsCollector reference and the listed early-termination, ScoreMode, competitive-iterator, and hit-threshold gaps. Done requires maintainer guidance on whether to extend the existing collector or create a new one, followed by an agreed implementation plan.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
performance, search
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.