apache / apache/lucene

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

Open
#11,338 10 comments 0 reactions 0 assignees View on GitHub
legacy-jira-priority:Major type:enhancement
Dominant language
Java
Stars
3.6k
Forks
1.4k
Avg merge
2d 11h
Merged PRs (30d)
88

Description

Looking at #9918 (LargeNumHitsTopDocsCollector.java ) I got to wondering if there was faster-than O(N\*log(N)) way of loading a PriorityQueue when we provide a bulk array to initialize the heap/PriorityQueue. It turns out there is: the JDK's PriorityQueue supports this in its constructors, referring to "This classic algorithm due to Floyd (1964) is known to be O(size)" – heapify() method. There's [another](https://www.geeksforgeeks.org/building-heap-from-array/) that may or may not be the same; I didn't look too closely yet. I see a number of uses of Lucene's PriorityQueue that first collects values and only after collecting want to do something with the results (typical / unsurprising). This lends itself to a builder pattern that can look similar to LargeNumHitsTopDocsCollector in terms of first having an array used like a list and then move over to the PriorityQueue if/when it gets full (it may not).

---
Migrated from [LUCENE-10302](https://issues.apache.org/jira/browse/LUCENE-10302) by David Smiley (@dsmiley), updated Mar 04 2022
Attachments: [LUCENE_PriorityQueue_Builder_with_heapify.patch](https://apache.github.io/lucene-jira-archive/attachments/LUCENE-10302/LUCENE_PriorityQueue_Builder_with_heapify.patch)
Linked issues:
- #9918

Contributor guide

Open the contributing guide

Research direction

Start with LargeNumHitsTopDocsCollector.java from #9918 and inspect Lucene's PriorityQueue usage where values are collected before iteration. Read the attached LUCENE_PriorityQueue_Builder_with_heapify.patch and compare its proposed builder path with the JDK's O(N) heapify approach. Done means the relevant bulk-collection path uses the intended heap construction and its behavior and performance are verified.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
search
Issue type
Refactor
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.