Oracle faster overlap check

Question

I've a table with two columns beginrange and endrange. No overlapping ranges should be allowed.There are indexes on these columns and we've tried many sql conditions like

inputBegin between beginRange and endRange or
inputEnd between beginRange and endRange 

not ( inputEnd < beginRange or inputStart > endRange )

etc Which work fine, except they're very slow as the table contains over 5mil records.

Is there anyway to write a much efficient overlap check?

Edit: I've thought of one more solution, oracle will count the index only when count() is done on a NOT NULL column with an index. If beginRange and endRange are NOT NULL and both have an index we can have three sums:

count(endRange) where inputBegin > endRange
+
count(beginRange) where inputEnd < beginRange
=
count(beginRange/endRange)

so with UNION ALL I would get three rows, and in the code I need to check if sum of first two equals the third. Of course I'm assuming only index will be counted and no rows will be accessed. Any other way?

Answer 1

I'm not sure whether you want to:

1. check if a row you are about to insert overlaps with some of the existing rows, or
2. search through all the existing rows and identify those that overlap?

---

If (1), then what you are essentially already doing...

SELECT *
FROM YOUR_TABLE
WHERE :inputEnd > beginRange AND :inputStart < endRange;

...will give you overlaps and should be very performant, provided you have a composite index whose components are in opposite directions: {beginRange ASC, endRange DESC}.

---

If (2), then you can utilize windowing like this:

SELECT *
FROM (
    SELECT
        YOUR_TABLE.*,
        LEAD(beginRange) OVER (ORDER BY beginRange) nextBeginRange
    FROM YOUR_TABLE
)
WHERE endRange > nextBeginRange;

This will give you every range that overlaps with its next range (where meaning of "next" is defined in the context of beginRange ordering).

Strictly, this doesn't even need a composite index (unless you want covering) - just a simple index on {beginRange} should ensure decent performance.

Answer 2

This is an answer - if certain assertions can be made:

You have a table with beginRange and endRange columns where there ano no two existing rows with overlapping (beginRange, endRange).

You want to insert a new row with (inputStart, inputEnd) but check if it overlaps with any of the existing rows on the table.

Then you can use this condition which should be fast - with a simple index on startRange:

WHERE input_Start <
      ( SELECT endRange
        FROM
          ( SELECT endRange
                 , ROW_NUMBER() OVER(ORDER BY startRange DESC) AS rn 
            FROM tableX
            WHERE startRange < input_End
          ) tmp
        WHERE rn = 1
      )


  --- TRUE  --> Overlaps
  --- FALSE --> No overlap

Answer 3

There is no one index that can satisfy this query. Which actually means that you're best creating two indexes, and running two queries, then UNIONing the results...

1) Create an Index on InputBegin
2) Create a separate Index on InputEnd
3) Run the following query

SELECT * FROM yourTable WHERE InputEnd   < ExclusionPeriodStart 
UNION ALL
SELECT * FROM yourTable WHERE InputBegin > ExclusionPeriodEnd

The first query can then use a range seek on the InputEnd index. The second query can also then use a range seek, but on a different index.

By keeping the queries separate, the two different requirements don't interfere with each other, and the most optimal index can be used.

You also already know (by understanding your data) that there is no overlap in the results (no record can start before it finishes, so no record can appear in both queries). This means that UNION ALL can be used instead of the slower UNION.

As far as I know, there is no way to perform this query faster than this. (On 5m records, it's probably faster to just scan the whole table on small data-sets.)

EDIT: That answer assumes that you're trying to find all records that do not appear inside a fixed range. If you want to check every record against every other record, then you need a different approach...

Checking for every overlap is expensive. Also, if you have these four ranges, working out which to delete is impossible...

1 -->--> 4
      3 -->--> 6
            5 -->--> 8
                  7 -->--> 9

Should you delete ranges 1 and 3, or 2 and 4?

What you can do, is find all the ranges that have another range overlapping with them.

And what you don't want is to find that A overlaps with B, and B overlaps with A.

SELECT
  *
FROM
  yourTable   AS first_range
INNER JOIN
  yourTable   AS second_range
    ON  second_range.start_date >= first_range.start_date
    AND second_range.start_date <= first_range.end_date

This will necesarrily scan the whole table for first_range. But because you only check the start_date of the second range, it will be able to use a range seek on the start_date index for any collisions.

EDIT2: Or perhaps you need the opposite of the first answer?

If you want all ranges that do collide with a set range, a modification of the same approach works.

SELECT * FROM yourTable WHERE InputEnd   >= ExclusionPeriodStart 
INTERSECT
SELECT * FROM yourTable WHERE InputBegin <= ExclusionPeriodEnd

This may not, however, be great. You'll take a percentage of the table in query1, and intersect it with almost all of the rest of the table. Instead you can fall back on the simple approach, but then add an optimisation...

SELECT
  *
FROM
  yourTable
WHERE
    InputStart <= ExclusionPeriodEnd
AND InputEnd   >= ExclusionPeriodStart

The first condition in the WHERE clause can be resolved with a range seek, and then scan all the resultant records to test for the second condition. So, can we reduce the range that needs scanning (currently (start of table) -> (ExclusionPeriodEnd)).

We can if we know one extra piece of information : The maximum length of any one range...

SELECT
  *
FROM
  yourTable
WHERE
    InputStart <= ExclusionPeriodEnd
AND InputStart >= ExclusionPeriodStart - (maximumLength)
AND InputEnd   >= ExclusionPeriodStart

Now the first TWO conditions form a range seek, and give a much smaller set of data to scan for the last condition.

How do you know the max lnegth though? You could scan the whole table, but that's a self defeating attempt at an optimisation.

Instead, you could index a calcuated field; a calculation that gives the max length of the range. SELECT MAX(calculatedField) FROM yourTable then avoids scanning the whole table. Or you could keep track with a trigger. Which is fine for INSERTS, but a bit messier when you have a DELETE (If you delete the longest range, do you scan the whole table again to find the new longest range? Probably not, you could be tempted to keep the old max length instead).

Answer 4

Assuming existing ranges don't overlap, then {beginRange} should be a (primary or alternate) key and detecting if new range would overlap with some of the existing ones could be done like this:

SELECT *
FROM YOUR_TABLE
WHERE beginRange = (
    SELECT MAX(beginRange)
    FROM YOUR_TABLE
    WHERE beginRange < :inputEnd
)
AND :inputStart < endRange

• If the new range overlaps with some of the existing ranges, this query returns the "highest" one.
• If there is no overlap, it returns an empty result set.

The index "under" the {beginRange} key is enough for efficiency (we only need to support the "MAX scan").