[LUCENE-8796] Use exponential search in IntArrayDocIdSet advance method

• Type: Improvement
• Status: Closed
• Priority: Minor
• Resolution: Fixed
• Fix Version/s: 9.0, 8.2
• Lucene Fields: New, Patch Available
• Assignee: Unassigned
• Reporter: Luca Cavanna
• Created: 08/May/19 12:13
• Updated: 28/Aug/22 15:45
• Resolved: 18/Jun/19 10:34

Description

Chatting with jpountz , he suggested to improve IntArrayDocIdSet by making its advance method use exponential search instead of binary search. This should help performance of queries including conjunctions: given that ConjunctionDISI uses leap frog, it advances through doc ids in small steps, hence exponential search should be faster when advancing on average compared to binary search.

 

Issue Links

• links to: GitHub Pull Request #667