[LUCENE-8828] Fix Intervals.unordered() without overlaps

• Type: Improvement
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 8.2
• Lucene Fields: New
• Assignee: Alan Woodward
• Reporter: Alan Woodward
• Created: 04/Jun/19 16:15
• Updated: 28/Aug/22 15:46
• Resolved: 07/Jun/19 14:08

Description

LUCENE-8300 added an option to Intervals.unordered() which would attempt to find intervals that contained all of a set of subintervals where none of the subintervals overlapped. Unfortunately, this implementation was buggy, and could miss documents depending on the order in which the subintervals were passed to the factory method.

After some digging around, I think that it is not in fact possible to implement this in anything other than n! time, because of the need to minimize the resulting intervals. My proposal is to remove the boolean flag, and instead implement an Intervals.unorderedNoOverlaps() method that takes only two subsources, and rewrites NO_OVERLAPS(a, b) to OR(ORDERED(a, b), ORDERED(b, a)). The usual simplifications will apply here, so NO_OVERLAPS(a, a) will end up as ORDERED(a, a)