sql - 在 SQL 中一次性合并间隔

Question

假设我有一个包含两列的表:start 和 end，均为整数，并且该表按第一列、第二列排序。每行代表一个区间。

我需要的是合并间隔表:所有重叠或相邻的间隔合并为一个。

它可以用 JOIN 查询构造，但它的行数是二次方的，在我的例子中是 400 万行(我决定编写这个问题，因为查询仍在运行)。

它也可以在 单次 中完成，通过遍历每一行并跟踪最大结束时间 - 但如何在标准 SQL 中执行此操作或类似的操作？在 SQL 中有任何 O(n) 的方法吗？我现在正在使用 SQLite；这次 SQLite 特定的解决方案也会帮助我。

来自相关问题的答案(1、2、3、4、5、6、7、8、9)告诉它是否可能。

可以吗？

Answer 1

好吧，这是一个适用于 MySQL 的解决方案(我不知道它是否适用于 SQlite)。我认为，但无法证明，那是 O(n)(放弃最初对事件表进行排序所花费的时间，即如果它已经按照我认为的问题状态进行了排序。)

> 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)