Uploaded image for project: 'Lucene - Core'
  1. Lucene - Core
  2. LUCENE-8828

Fix Intervals.unordered() without overlaps

    XMLWordPrintableJSON

    Details

    • Type: Improvement
    • Status: Closed
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 8.2
    • Component/s: None
    • Labels:
      None
    • Lucene Fields:
      New

      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)

        Attachments

        1. LUCENE-8828.patch
          15 kB
          Alan Woodward

          Activity

            People

            • Assignee:
              romseygeek Alan Woodward
              Reporter:
              romseygeek Alan Woodward
            • Votes:
              0 Vote for this issue
              Watchers:
              4 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: