在 SQL 中一次合并间隔

Question

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

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

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

它也可以在单次中完成，通过运行每一行并跟踪最大结束时间 - 但如何在标准 SQL 中做到这一点或类似的事情？有任何 O(n) 的方法在 SQL 中做到这一点吗？我现在正在使用 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

在您的链接中，您省略了一个： 我可以使用 SQL Server CTE 来合并相交日期吗？，其中我提出了针对重叠间隔问题的 RECURSIVE CTE 解决方案。递归 CTE 可以以不同的方式处理（与普通的自连接相比），并且通常执行速度快得惊人。

mysql 没有递归 CTE。 Postgres 有，Oracle 有，Microsoft 有。

这里 查询连续列的“运行” Postgres 中的 是另一种，带有模糊因素。

这里 获取总时间间隔如果序列没有破坏，则多行 是另一种。

Answer 3

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

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 中，这可以通过分析函数轻松实现。在这种情况下，最好使用上述方法来最大程度地减少所使用的行数，并将它们带到您的应用程序中，然后您可以编写计算范围的代码并将它们插回到数据库中。

Answer 4

目前，我找到的最佳答案是：使用索引。
这将复杂性从二次降低到 O(n log n)。

使用覆盖索引，查询的速度足以满足我的需求；
仅在开始列或结束列上有一个索引，速度较慢，但​​仍然可以。
在每种情况下，EXPLAIN QUERY PLAN 都告诉我，正如预期的那样，单个表扫描与索引的使用相结合。

在索引中查找元素并不完全是 O(1)，但事实证明已经足够接近了。
建立索引的速度也不慢。

剩下的就是证明真正的 O(n) 算法无法用 SQL 编写。

所以另一个答案是用不同的语言编写它，然后将其应用到 SQLite 表。
有多种方法可以实现这一点：

• 将表导出到 CSV 文件；读取CSV文件，应用算法，生成CSV；将生成的 CSV 文件导入为表格；
• 使用该语言的 SQLite 驱动程序（例如 Perl 的 DBD::SQLite、R 的 RSQLite）
• 编写一个 SQLite 扩展函数，以某种方式与所选语言交互