PriorityQueue: optimize where we collect then iterate by using O(N) heapify [LUCENE-10302]
- 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
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