[LUCENE-10275] Use interval tree in MultiRangeQuery

• Type: Improvement
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 9.1
• Lucene Fields: New
• Assignee: Ignacio Vera
• Reporter: Ignacio Vera
• Created: 01/Dec/21 10:08
• Updated: 28/Aug/22 16:31
• Resolved: 02/Dec/21 08:57

Description

Currently MultiRangeQuery uses a naive approach that is iterating over a list of clauses to compute relationships between the list of ranges and the kd tree. This clearly does not scale for a large number of clauses.

This problem has already been solved in geo (see https://github.com/apache/lucene/blob/main/lucene/core/src/java/org/apache/lucene/geo/ComponentTree.java). I think it should be easy to make a version of the interval tree for the n-dimensional case. 

 

Issue Links

• links to: GitHub Pull Request #498