主页 / dba / 问题 / 100965
Accepted
Villiers Strauss
Asked: 2015-05-09 05:59:08 +0800 CST

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

  • 772

我正在尝试组合多个日期范围（我的负载大约为最大 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 |           ==
--+---------------------------
  | ====== == ===============>
postgresql aggregate

4 个回答

  1. Best Answer

    假设/澄清

    1. 无需区分infinity和打开上界 ( upper(range) IS NULL)。（无论哪种方式都可以，但这种方式更简单。）
    1. 由于date是离散类型，所有范围都有默认[)范围。 手册：

    内置的范围类型int4range,int8range和daterange都使用包含下限但不包括上限的规范形式；也就是说，[).

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

    纯 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计算上限 ( ) 的运行最大值。 将 NULL bounds (unbounded) 替换为 +/-只是为了简化（没有特殊的 NULL 情况）。enddate
    infinity

    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. 看：

    相关答案和更多解释：

    使用 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小提琴。

    有关的：

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

    指数

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

    CREATE INDEX foo on test (range);

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

    • 32

  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 以获得无限上界
    • 7

  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 是否也一样，如果能得到一些实际的性能数据会很好。

    • 5

  4. 为了好玩，我试了一下。我发现这是最快、最干净的方法。首先，我们定义一个函数，如果有重叠或两个输入相邻，则合并，如果没有重叠或邻接，我们只需返回第一个日期范围。提示+是范围上下文中的范围联合。

    CREATE FUNCTION merge_if_adjacent_or_overlaps (d1 daterange, d2 daterange)
RETURNS daterange AS $$
  SELECT
    CASE WHEN d1 && d2 OR d1 -|- d2
    THEN d1 + d2
    ELSE d1
    END;
$$ LANGUAGE sql
IMMUTABLE;

    然后我们像这样使用它，

    SELECT DISTINCT ON (lower(cumrange)) cumrange
FROM (
  SELECT merge_if_adjacent_or_overlaps(
    t1.range,
    lag(t1.range) OVER (ORDER BY t1.range)
  ) AS cumrange
  FROM test AS t1
) AS t
ORDER BY lower(cumrange)::date, upper(cumrange)::date DESC NULLS first;
    • -1

相关问题