Let's say I have a table with two columns: start
and end
, both integers, and the table is ordered by the first, then second column. Each row represents an interval.
What I need is the table of merged intervals: all overlapping or adjacent intervals gobbled up into one.
It can be constructed with a JOIN query, but that is quadratic in the number of rows, which is 4 million rows in my case (I decided to compose this question because the query is still running).
It can also be done in a single pass, by running through each row and keeping track of the maximum end time - but how to do that, or something equivalent, in standard SQL? Is there any O(n) way to do it in SQL? I'm using SQLite right now; a SQLite-specific solution would also help me out this time.
From the answers to related questions (1, 2, 3, 4, 5, 6, 7, 8, 9) I can't tell whether it's possible.
Can you?
Well, here is a solution that works in MySQL (I don't know if it will work in SQlite). I think, but cannot prove, that is O(n) (discarding the time it takes to sort the events table initially, i.e. if it is already sorted as I think the question states.)
> SELECT * from events;
+-------+-----+
| start | end |
+-------+-----+
| 1 | 9 |
| 5 | 8 |
| 8 | 11 |
| 11 | 13 |
| 17 | 25 |
| 18 | 26 |
| 33 | 42 |
| 59 | 81 |
| 61 | 87 |
| 97 | 132 |
| 105 | 191 |
| 107 | 240 |
| 198 | 213 |
| 202 | 215 |
+-------+-----+
14 rows in set (0.00 sec)
SET @interval_id = 0;
SET @interval_end = 0;
SELECT
MIN(start) AS start,
MAX(end) AS end
FROM
(SELECT
@interval_id := IF(start > @interval_end,
@interval_id + 1,
@interval_id) AS interval_id,
@interval_end := IF(start < @interval_end,
GREATEST(@interval_end, end),
end) AS interval_end,
events.*
FROM events
ORDER BY start,end) tmp
GROUP BY interval_id;
+-------+------+
| start | end |
+-------+------+
| 1 | 13 |
| 17 | 26 |
| 33 | 42 |
| 59 | 87 |
| 97 | 240 |
+-------+------+
5 rows in set (0.00 sec)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With