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

Answer 2

根据评论中我的问题的答案，我认为我的想法行不通。既然你提到你可以（并且我假设你知道如何）通过连接来完成，我有一个想法，通过仅保留属于不同点的范围来最小化要连接的行数，如下所示：

select start, max(end) as end
from (
      select min(start) as start,end
      from table
      group by end
     ) in_tab
group by in_tab.start

上面的内部选择确保没有终点重复，并为每个终点选择最长的起点。外部选择的作用恰恰相反。我们最终得到在不同点开始和结束的范围（删除任何完全包含/重叠的范围）。如果最大范围不大，这可能会起作用。如果这些是日期，并且整个表中的最低日期和其中的最高日期之间存在最大一年差异，那么选择任意两个点的选项将是 365*364，这将是可能行的上限经过以上选择后。然后可以使用您已有的连接方法在临时表中使用这些数据。但根据你提到的数字，理论上我们有一个巨大的数字，使得这次尝试变得无关紧要。即使上面最小化了计算中使用的行，它们仍然太多而无法在连接中使用。

当 RDBMS 没有提供其他非标准功能时，我不知道有什么方法可以在没有连接的 ANSI SQL 中实现这一点。例如，在 Oracle 中，这可以通过分析函数轻松实现。在这种情况下，最好使用上述方法来最小化所使用的行数，并将它们带到您的应用程序中，您可以在那里编写计算范围的代码并将它们插入数据库中。