Should TopScoreDocCollector Always Populate Sentinel Values? [LUCENE-8875]

[asfimport]

TopScoreDocCollector always initializes HitQueue as the PQ implementation, and instruct HitQueue to populate with sentinels. While this is a great safety mechanism, for very large datasets where the query's selectivity is high, the sentinel population can be redundant and can become a large enough bottleneck in itself. Does it make sense to introduce a new parameter in TopScoreDocCollector which uses a heuristic (say number of hits > 10k) and does not populate sentinels?

---

Migrated from LUCENE-8875 by Atri Sharma (@atris), resolved Jul 10 2019
Linked issues:

• PriorityQueue: optimize where we collect then iterate by using O(N) heapify [LUCENE-10302] #11338

[asfimport]

Atri Sharma (@atris) (migrated from JIRA)

Another thing to explore is to have a sleek set of arrays instead of ScoreDocs: https://sbdevel.wordpress.com/2015/10/05/speeding-up-core-search/

 

Maybe have a new implementation of a PQ using this idea, and a new Collector which uses the threshold sentinel filling + the new PQ? Only used for very large N?

[asfimport]

Adrien Grand (@jpountz) (migrated from JIRA)

I like pre-populating the hit queue mostly because it makes the collector code simpler and likely a bit faster. As a comparison TopFieldCollector can't pre-populate the hit queue, which forces it to have different code paths for the case that the priority queue is full (common path) or that the queue is not full yet. In general I'm seeing large number of hits as an abuse case.

[asfimport]

Atri Sharma (@atris) (migrated from JIRA)

While I do agree that too many hits are not what top N hits are intended for, but some increasing popular use cases are inclined in that direction (bucket aggregates?) I think it would be fair to allow such users to use a different Collector which optimises their case while not muddling with the commonly used code path. WDYT?

[asfimport]

Adrien Grand (@jpountz) (migrated from JIRA)

What do you mean by bucket aggregates?

[asfimport]

Atri Sharma (@atris) (migrated from JIRA)

I meant Elasticsearch aggregates (although I am not sure if this new proposed collector has a direct improvement in that front, on second thought).

The meat of the point here is that I believe it is the path of minimal invasion if we introduced a new collector which clearly calls out that it is meant for cases when N is very large (>10k?), and lists out the benefits and trade offs clearly.

Are there any catches that are applicable here?

[asfimport]

Adrien Grand (@jpountz) (migrated from JIRA)

Aggregates don't have this issue since they don't track top hits?

+1 to having a separate collector for large N values in sandbox.

[asfimport]

ASF subversion and git services (migrated from JIRA)

Commit ee79a20 in lucene-solr's branch refs/heads/master from Atri Sharma
https://gitbox.apache.org/repos/asf?p=lucene-solr.git;h=ee79a20

LUCENE-8875: Introduce Optimized Collector For Large Number Of Hits (#754)

This commit introduces a new collector which is optimized for
cases when the number of hits is large and/or the actual hits
collected are sparse in comparison to the number of hits
requested.

[asfimport]

ASF subversion and git services (migrated from JIRA)

Commit 7339eb2 in lucene-solr's branch refs/heads/branch_8x from Atri Sharma
https://gitbox.apache.org/repos/asf?p=lucene-solr.git;h=7339eb2

LUCENE-8875: Introduce Optimized Collector For Large Number Of Hits (#754)

This commit introduces a new collector which is optimized for
cases when the number of hits is large and/or the actual hits
collected are sparse in comparison to the number of hits
requested.

[asfimport]

ASF subversion and git services (migrated from JIRA)

Commit ee79a20 in lucene-solr's branch refs/heads/jira/SOLR-13565 from Atri Sharma
https://gitbox.apache.org/repos/asf?p=lucene-solr.git;h=ee79a20

LUCENE-8875: Introduce Optimized Collector For Large Number Of Hits (#754)

This commit introduces a new collector which is optimized for
cases when the number of hits is large and/or the actual hits
collected are sparse in comparison to the number of hits
requested.

[asfimport]

Ignacio Vera (@iverase) (migrated from JIRA)

Closing after the 8.2.0 release