如何找到数字范围之间的差距？

Question

考虑下表：

T_ID | T_START | T_END
-----+---------+------
   1 | 0.25    | 0.5
   2 | 0.8     | 1
   3 | 0.4     | 0.6
   4 | 0.2     | 0.3
   5 | 0.7     | 0.8

T_ID是独特的。每行代表一个连续范围的数字，是 0 到 1 的子集。T_START小于T_END。

我需要确定未包含在 0 和 1 之间的任何范围。请注意，某些范围确实重叠。端点的排他性与我的用例无关；我只需要确定差距的端点是什么。（因此，不考虑单点差距。）

对于这个特定的数据集，我希望结果是

GAP_START | GAP_END
----------+--------
0         | 0.2
0.6       | 0.7

实际数据集很大，并且将聚合到其他一些数据上（数十万行，每个聚合组可能有 100 行），因此性能很重要。（不过，性能不佳但可能会改进的答案是受欢迎的。）

我曾考虑尝试首先确定覆盖范围是什么，然后尝试反转它，但我什至无法弄清楚如何计算覆盖范围。简单GROUP BY是不够的，因为我们有重叠范围链，它们会合并为一个范围，即使并非所有范围都相互重叠。我认为递归查询可能会有所帮助，但我还没有弄清楚它的逻辑。

我用这个示例数据集创建了一个 SQLFiddle 。

可悲的是（而且毫无成效），我不能随意修改底层表示。

Answer 1

经过大量的挖掘，我发现了这篇关于对日期范围执行此操作的博客文章，结果证明它在数字范围上同样有效，对处理 0 和 1 端点进行了一些修改。

从那里获取查询并将列重命名为更清楚一点，我们有

SELECT * FROM
  (SELECT MAX(T_END) OVER (ORDER BY T_START) GAP_START,
          LEAD(T_START) OVER (ORDER BY T_START) GAP_END
   FROM T)
WHERE GAP_START < GAP_END

这需要相当多的解释。一步步：

1. 对于每一行，它得到的最大T_END的，所有行T_START小于或等于当前行的T_START。这为我们提供了与该行范围开始重叠的所有范围的最大范围结束。
2. 对于每一行，它获取大于当前行T_START的第一行的T_START。这为我们提供了下一个最大的范围开始。
3. 它过滤掉最大值T_END大于或等于下一个的任何行T_START。这意味着最大的重叠范围结束延伸到或超出下一个范围开始。换句话说，这一行和下一行之间没有间隙，要么是因为这一行在下一行开始的地方结束，要么是因为其他重叠的行覆盖了两者之间的所有点。

但是，这并不能完全满足 0 到 1 范围内所有间隙的要求。它只选取所有行的最小范围开始和最大范围结束之间的间隙。要检查 0 和 1 范围末端的间隙，我们可以使用以下查询。

对于从 0 开始的间隙：

SELECT 0 AS GAP_START, MIN(T_START) AS GAP_END
FROM T
HAVING MIN(T_START) > 0

对于以 1 结尾的间隙：

SELECT MAX(T_END) AS GAP_START, 1 AS GAP_END
FROM T
HAVING MAX(T_END) < 1

如果端点没有间隙，这两个查询都不会返回任何行。

将它们全部放在一个查询中：

SELECT * FROM
  (SELECT MAX(T_END) OVER (ORDER BY T_START) GAP_START,
          LEAD(T_START) OVER (ORDER BY T_START) GAP_END
   FROM T)
WHERE GAP_START < GAP_END
UNION ALL
SELECT 0 AS GAP_START, MIN(T_START) AS GAP_END
FROM T
HAVING MIN(T_START) > 0
UNION ALL
SELECT MAX(T_END) AS GAP_START, 1 AS GAP_END
FROM T
HAVING MAX(T_END) < 1

结果与问题中所述完全相同，忽略顺序。查询的 SQLFiddle。