将单独的范围组合成最大可能的连续范围

Question

我正在尝试组合多个日期范围（我的负载大约为最多 500 个，大多数情况下为 10 个），这些日期范围可能会或可能不会重叠到最大的可能连续日期范围中。例如：

数据：

CREATE TABLE test (
  id SERIAL PRIMARY KEY NOT NULL,
  range DATERANGE
);

INSERT INTO test (range) VALUES 
  (DATERANGE('2015-01-01', '2015-01-05')),
  (DATERANGE('2015-01-01', '2015-01-03')),
  (DATERANGE('2015-01-03', '2015-01-06')),
  (DATERANGE('2015-01-07', '2015-01-09')),
  (DATERANGE('2015-01-08', '2015-01-09')),
  (DATERANGE('2015-01-12', NULL)),
  (DATERANGE('2015-01-10', '2015-01-12')),
  (DATERANGE('2015-01-10', '2015-01-12'));

表看起来像：

 id |          range
----+-------------------------
  1 | [2015-01-01,2015-01-05)
  2 | [2015-01-01,2015-01-03)
  3 | [2015-01-03,2015-01-06)
  4 | [2015-01-07,2015-01-09)
  5 | [2015-01-08,2015-01-09)
  6 | [2015-01-12,)
  7 | [2015-01-10,2015-01-12)
  8 | [2015-01-10,2015-01-12)
(8 rows)

预期结果：

         combined
--------------------------
 [2015-01-01, 2015-01-06)
 [2015-01-07, 2015-01-09)
 [2015-01-10, )

视觉表现：

1 | =====
2 | ===
3 |    ===
4 |        ==
5 |         =
6 |             =============>
7 |           ==
8 |           ==
--+---------------------------
  | ====== == ===============>

Answer 1

假设/澄清

1. 无需区分infinity和开上界 ( upper(range) IS NULL)。（您可以采用任何一种方式，但这种方式更简单。）

• NULL 与infinityPostgreSQL 范围类型

2. 由于date是离散类型，所有范围都有默认[)边界。 手册：

内置范围类型int4range、int8range和daterange都使用规范形式，包括下限和排除上限；也就是说，[)。

对于其他类型（例如tsrange！），如果可能，我会强制执行相同的操作：

• 在 PostgreSQL 中使用 EXCLUDE 防止相邻/重叠条目

纯SQL解决方案

为清楚起见，使用 CTE：

WITH a AS (
   SELECT range
        , COALESCE(lower(range),'-infinity') AS startdate
        , max(COALESCE(upper(range), 'infinity')) OVER (ORDER BY range) AS enddate
   FROM   test
   )
, b AS (
   SELECT *, lag(enddate) OVER (ORDER BY range) < startdate OR NULL AS step
   FROM   a
   )
, c AS (
   SELECT *, count(step) OVER (ORDER BY range) AS grp
   FROM   b
   )
SELECT daterange(min(startdate), max(enddate)) AS range
FROM   c
GROUP  BY grp
ORDER  BY 1;

或者，与子查询相同，读取速度更快但不太容易：

SELECT daterange(min(startdate), max(enddate)) AS range
FROM  (
   SELECT *, count(step) OVER (ORDER BY range) AS grp
   FROM  (
      SELECT *, lag(enddate) OVER (ORDER BY range) < startdate OR NULL AS step
      FROM  (
         SELECT range
              , COALESCE(lower(range),'-infinity') AS startdate
              , max(COALESCE(upper(range), 'infinity')) OVER (ORDER BY range) AS enddate
         FROM   test
         ) a
      ) b
   ) c
GROUP  BY grp
ORDER  BY 1;

如何？

a: 在按 排序时range，使用窗口函数计算上界 ( )的运行最大值enddate。
用 +/- 替换 NULL 边界（无界）infinity只是为了简化（没有特殊的 NULL 情况）。

b：在相同的排序顺序中，如果前一个enddate早于startdate我们有一个间隙并开始一个新的范围（step）。
_{请记住，上限总是被排除在外。}

c：grp通过使用另一个窗口函数计算步数来形成组 ( )。

在外部SELECT构建范围从每个组的下限到上限。瞧。

或者少一个子查询级别，但翻转排序顺序：

SELECT daterange(min(COALESCE(lower(range), '-infinity')), max(enddate)) AS range
FROM  (
   SELECT *, count(nextstart > enddate OR NULL) OVER (ORDER BY range DESC NULLS LAST) AS grp
   FROM  (
      SELECT range
           , max(COALESCE(upper(range), 'infinity')) OVER (ORDER BY range) AS enddate
           , lead(lower(range)) OVER (ORDER BY range) As nextstart
      FROM   test
      ) a
   ) b
GROUP  BY grp
ORDER  BY 1;

在第二步中使用ORDER BY range DESC NULLS LAST(with NULLS LAST) 对窗口进行排序，以获得完全颠倒的排序顺序。这应该是更便宜的（更容易产生，匹配建议的索引的排序顺序完全）和精确的拐角例rank IS NULL。看：

• PostgreSQL 按日期时间 asc 排序，先为空？

相关答案有更多解释：

• 比较多个日期范围

使用 plpgsql 的程序解决方案

适用于任何表/列名称，但仅适用于 type daterange。
带有循环的过程式解决方案通常较慢，但在这种特殊情况下，我希望该函数速度更快，因为它只需要一次顺序扫描：

CREATE OR REPLACE FUNCTION f_range_agg(_tbl text, _col text)
  RETURNS SETOF daterange AS
$func$
DECLARE
   _lower     date;
   _upper     date;
   _enddate   date;
   _startdate date;
BEGIN
   FOR _lower, _upper IN EXECUTE
      format(
         $sql$
         SELECT COALESCE(lower(t.%2$I),'-infinity')  -- replace NULL with ...
              , COALESCE(upper(t.%2$I), 'infinity')  -- ... +/- infinity
         FROM   %1$I t
         ORDER  BY t.%2$I
         $sql$, _tbl, _col)
   LOOP
      IF _lower > _enddate THEN     -- return previous range
         RETURN NEXT daterange(_startdate, _enddate);
         SELECT _lower, _upper  INTO _startdate, _enddate;
   
      ELSIF _upper > _enddate THEN  -- expand range
         _enddate := _upper;
   
      -- do nothing if _upper <= _enddate (range already included) ...
   
      ELSIF _enddate IS NULL THEN   -- init 1st round
         SELECT _lower, _upper  INTO _startdate, _enddate;
      END IF;
   END LOOP;
   
   IF FOUND THEN                    -- return last row
      RETURN NEXT daterange(_startdate, _enddate);
   END IF;
END
$func$  LANGUAGE plpgsql;

称呼：

SELECT * FROM f_range_agg('test', 'range');  -- table and column name

逻辑类似于 SQL 解决方案，但我们可以通过一次完成。

SQL小提琴。

有关的：

• GROUP BY 和聚合顺序数值

在动态 SQL 中处理用户输入的常用练习：

• Postgres 函数中的 SQL 注入与准备好的查询

指数

对于这些解决方案中的每一个，一个简单的（默认）btree 索引range将有助于大表中的性能：

CREATE INDEX foo on test (range);

btree 索引对于范围类型的用途有限，但我们可以获得预先排序的数据，甚至可能只进行索引扫描。

Answer 2

我想出了这个：

DO $$                                                                             
DECLARE 
    i date;
    a daterange := 'empty';
    day_as_range daterange;
    extreme_value date := '2100-12-31';
BEGIN
    FOR i IN 
        SELECT DISTINCT 
             generate_series(
                 lower(range), 
                 COALESCE(upper(range) - interval '1 day', extreme_value), 
                 interval '1 day'
             )::date
        FROM rangetest 
        ORDER BY 1
    LOOP
        day_as_range := daterange(i, i, '[]');
        BEGIN
            IF isempty(a)
            THEN a := day_as_range;
            ELSE a = a + day_as_range;
            END IF;
        EXCEPTION WHEN data_exception THEN
            RAISE INFO '%', a;
            a = day_as_range;
        END;
    END LOOP;

    IF upper(a) = extreme_value + interval '1 day'
    THEN a := daterange(lower(a), NULL);
    END IF;

    RAISE INFO '%', a;
END;
$$;

仍然需要一些磨练，但想法如下：

1. 将范围扩展到单个日期
2. 这样做，用一些极值替换无限上界
3. 根据 (1) 中的顺序，开始构建范围
4. 当 union ( +) 失败时，返回已经构建的范围并重新初始化
5. 最后，返回其余的——如果达到了预定义的极值，则将其替换为 NULL 以获得无限上界

Answer 3

几年前，我测试了不同的解决方案（其中一些类似于 @ErwinBrandstetter 的解决方案），用于在 Teradata 系统上合并重叠周期，我发现以下是最有效的解决方案（使用分析函数，较新版本的 Teradata 具有以下内置函数：该任务）。

1. 按开始日期对行进行排序
2. 查找所有先前行的最大结束日期：maxEnddate
3. 如果该日期早于当前开始日期，则您发现了一个间隙。仅保留这些行加上 PARTITION 中的第一行（由 NULL 指示）并过滤所有其他行。现在您可以获得每个范围的开始日期和上一个范围的结束日期。
4. 然后你只需获取下一行的maxEnddate使用LEAD就差不多完成了。仅对于最后一行LEAD返回 a NULL，要解决此问题，请在步骤 2 中计算分区的所有行的最大结束日期及其COALESCE。

为什么速度更快？根据实际数据，步骤 #2 可能会大大减少行数，因此下一步只需要对一个小子集进行操作，此外它还会删除聚合。

小提琴

SELECT
   daterange(startdate
            ,COALESCE(LEAD(maxPrevEnddate) -- next row's end date
                      OVER (ORDER BY startdate) 
                     ,maxEnddate)          -- or maximum end date
            ) AS range

FROM
 (
   SELECT
      range
     ,COALESCE(LOWER(range),'-infinity') AS startdate

   -- find the maximum end date of all previous rows
   -- i.e. the END of the previous range
     ,MAX(COALESCE(UPPER(range), 'infinity'))
      OVER (ORDER BY range
            ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING) AS maxPrevEnddate

   -- maximum end date of this partition
   -- only needed for the last range
     ,MAX(COALESCE(UPPER(range), 'infinity'))
      OVER () AS maxEnddate
   FROM test
 ) AS dt
WHERE maxPrevEnddate < startdate -- keep the rows where a range start
   OR maxPrevEnddate IS NULL     -- and keep the first row
ORDER BY 1;  

由于这在 Teradata 上是最快的，我不知道 PostgreSQL 是否也一样，如果能得到一些实际的性能数据就好了。