范围聚合

库片段

范围聚合

适用于 PostgreSQL

8.4

用

SQL

依赖于

无

假设您有一个以 "开始" (s) 和 "结束" (e) 列表示的范围表；我们假设这些是半开区间，即每行代表范围 [s,e)。我们还假设约束 (e > s) 被强制执行，并且 (s,e) 在表中是唯一的。

问题是聚合所有重叠的范围，并生成一个结果，其中每行对应于一个不重叠的范围集合。

例如（为了简单起见，使用整数，但在实践中通常涉及其他类型，例如时间戳）

test=# select * from intervals order by s,e;
 s  | e  
----+----
  1 |  3
  2 |  4
  5 |  6
  5 |  8
  6 |  9
  7 | 10
  8 | 10
 10 | 11
 10 | 15
 11 | 12
 12 | 13
(11 rows)

此结果的期望输出为

  s  |  e 
-----+-----
   1 |   4
   5 |  10
  10 |  15
(3 rows)

对于 SQL 来说，这并不常见，但这个问题可以通过纯粹的程序方式来解决。

首先，按 (s,e) 的升序逐个考虑每个范围。对于每个范围，只有两种可能性：它与我们已经处理过的范围重叠，或者它开始了一个新的不重叠范围。使用 PG 8.4 或更高版本，我们可以使用窗口函数来表达这个想法，如下所示

SELECT s, e,
       CASE WHEN s < max(le) OVER (ORDER BY s,e) THEN null ELSE s END AS new_start
  FROM (SELECT s, e, lag(e) OVER (ORDER BY s,e) AS le FROM intervals) s1;

这里使用子查询是因为我们真正想要的是 max(lag(e))，以排除当前行的 "e" 值，但窗口函数不能直接嵌套。（在 9.0 或更高版本中，可能更方便地简单地将窗口限定子句更改为排除当前行；此功能在 8.4 中不可用。）新列 "new_start" 仅当当前行代表一个新的不重叠区间的左边缘时才包含非空值；所有仅扩展现有区间的行都包含空值。因此，我们的测试数据的输出为

 s  | e  | new_start 
----+----+-----------
  1 |  3 |         1
  2 |  4 |          
  5 |  6 |         5
  5 |  8 |          
  6 |  9 |          
  7 | 10 |          
  8 | 10 |          
 10 | 11 |        10
 10 | 15 |          
 11 | 12 |          
 12 | 13 |          
(11 rows)

现在，我们将此结果扩展到用聚合范围的左边缘标记每一行，该范围是其一部分。为此，我们将上面的内容包装在另一个子查询级别，使用 max(new_start) 作为窗口函数，将每个 "左边缘" 行的值传播到其后继

SELECT s, e,
       max(new_start) OVER (ORDER BY s,e) AS left_edge
  FROM (SELECT s, e,
               CASE WHEN s < max(le) OVER (ORDER BY s,e) THEN null ELSE s END AS new_start
          FROM (SELECT s, e, lag(e) OVER (ORDER BY s,e) AS le FROM intervals) s1) s2;

我们测试数据的输出现在为

 s  | e  | left_edge 
----+----+-----------
  1 |  3 |         1
  2 |  4 |         1
  5 |  6 |         5
  5 |  8 |         5
  6 |  9 |         5
  7 | 10 |         5
  8 | 10 |         5
 10 | 11 |        10
 10 | 15 |        10
 11 | 12 |        10
 12 | 13 |        10
(11 rows)

现在我们可以简单地按 left_edge 分组，以将所有重叠的行聚合在一起

SELECT min(s) as s, max(e) as e
  FROM (SELECT s, e,
               max(new_start) OVER (ORDER BY s,e) AS left_edge
          FROM (SELECT s, e,
                       CASE WHEN s < max(le) OVER (ORDER BY s,e) THEN null ELSE s END AS new_start
                  FROM (SELECT s, e, lag(e) OVER (ORDER BY s,e) AS le FROM intervals) s1) s2) s3
 GROUP BY left_edge;

生成期望输出

 s  | e  
----+----
  1 |  4
  5 | 10
 10 | 15
(3 rows)