How do I find gaps between ranges of numbers?

Question

Consider the following table:

T_ID | T_START | T_END
-----+---------+------
   1 | 0.25    | 0.5
   2 | 0.8     | 1
   3 | 0.4     | 0.6
   4 | 0.2     | 0.3
   5 | 0.7     | 0.8

T_ID is unique. Each row represents a continuous range of numbers and is a subset of 0 to 1. T_START is less than T_END.

I need to identify any ranges not included between 0 and 1. Note that some ranges do overlap. The exclusivity of the endpoints is not relevant for my use case; I only need to identify what the endpoints of the gaps are. (As such, single point gaps are not a consideration.)

For this specific data set, I'd expect the result to be

GAP_START | GAP_END
----------+--------
0         | 0.2
0.6       | 0.7

The actual data set is large and will be aggregated over some other data (hundreds of thousands of rows, with possibly 100 row per aggregate group), so performance is important. (Answers that are not performant but may be improved are welcome, though.)

I considered trying to first determine what the covered ranges are and then trying to reverse that, but I haven't been able to figure out how to even compute the covered ranges. A simple GROUP BY is insufficient, since we have chains of overlapping ranges that would be merged into a single range, even though not all ranges overlap each other. I am of the mind that a recursive query might be helpful, but I haven't been able to figure out the logic for it yet.

I've created a SQLFiddle with this example dataset.

I am, sadly (and unproductively), not at liberty to modify the underlying representation.

Answer 1

After a pretty good amount of digging, I found this blog post on doing this for date ranges, and it turns out to work equally well on numeric ranges, with a little modification for handling the 0 and 1 endpoints.

Taking the query from there and renaming the columns to be a bit more clear, we have

SELECT * FROM
  (SELECT MAX(T_END) OVER (ORDER BY T_START) GAP_START,
          LEAD(T_START) OVER (ORDER BY T_START) GAP_END
   FROM T)
WHERE GAP_START < GAP_END

This warrants quite a bit of explanation. Step by step:

1. For each row, it gets the maximum T_END from all rows where T_START is less than or equal to the current row's T_START. This gives us the biggest range end of all the ranges that overlap this row's range start.
2. For each row, it gets the T_START of the first row where the T_START is greater than the current row. This gives us the next biggest range start.
3. It filters out any rows where the maximum T_END is greater than or equal to the next T_START. This means that the biggest overlapping range end extends out to or beyond the next range start. In other words, there is no gap between this row and the next, either because this row ends where the next begins or because other overlapping rows cover all points between the two.

This doesn't quite handle the requirement of all gaps over the range of 0 to 1, though. It only picks the gaps between the minimum range start and the maximum range end of all the rows. To check for gaps at the ends of the 0 and 1 range, we can use the following queries.

For gaps starting at 0:

SELECT 0 AS GAP_START, MIN(T_START) AS GAP_END
FROM T
HAVING MIN(T_START) > 0

For gaps ending at 1:

SELECT MAX(T_END) AS GAP_START, 1 AS GAP_END
FROM T
HAVING MAX(T_END) < 1

Both of these queries will return no rows if there is no gap at the endpoint.

Putting it all together into a single query:

SELECT * FROM
  (SELECT MAX(T_END) OVER (ORDER BY T_START) GAP_START,
          LEAD(T_START) OVER (ORDER BY T_START) GAP_END
   FROM T)
WHERE GAP_START < GAP_END
UNION ALL
SELECT 0 AS GAP_START, MIN(T_START) AS GAP_END
FROM T
HAVING MIN(T_START) > 0
UNION ALL
SELECT MAX(T_END) AS GAP_START, 1 AS GAP_END
FROM T
HAVING MAX(T_END) < 1

The result is exactly as stated in the question, ignoring order. SQLFiddle of the query.