7

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

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

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

它也可以通过运行每一行并跟踪最大结束时间来一次完成——但是如何在标准 SQL 中做到这一点，或者类似的东西？在 SQL 中是否有任何O(n) 方法可以做到这一点？我现在正在使用 SQLite；这次，特定于 SQLite 的解决方案也将帮助我。

从相关问题的答案（1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9）我无法判断这是否可能。

你能？

4

4 回答 4

6

好吧，这是一个适用于 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)
于 2012-01-25T20:54:56.713 回答
1

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

mysql 没有递归 CTE。Postgres 有，Oracle 有，微软有。

在这里查询 Postgres 中连续列的“运行”是另一种方法，带有一个软糖因素。

如果序列未中断是另一个，则从多行获取总时间间隔。

于 2011-12-10T20:32:28.400 回答
0

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

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

在索引中找到一个元素并不是 O(1)，但结果证明已经足够接近了。建立索引也不慢。

剩下的就是不能用 SQL 编写真正的 O(n) 算法的证据。

所以另一个答案是用不同的语言编写它，然后将其应用于 SQLite 表。有多种方法可以使这项工作：

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

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

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 中，这可以通过分析功能轻松实现。在这种情况下，最好的办法是使用上述方法来最小化使用的行数并将它们带到您的应用程序中，您可以在那里编写计算范围的代码并将它们插入回数据库中。

于 2011-12-10T20:17:43.937 回答