Объединение отдельных диапазонов в максимально возможные смежные диапазоны

Я пытаюсь объединить несколько диапазонов дат (моя загрузка составляет около 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 |           ==
--+---------------------------
  | ====== == ===============>

Предположения / Разъяснения

1. Не нужно различать infinityи открывать верхнюю границу ( upper(range) IS NULL). (Вы можете сделать это в любом случае, но так проще.)

   • NULL и infinityв диапазоне типов PostgreSQL

2. Поскольку dateэто дискретный тип, все диапазоны имеют [)границы по умолчанию . По документации:

   Встроенные типы дальности int4range, int8rangeи daterangeлюбое использование канонической форме , которая включает в себя нижнюю границу и не включает верхнюю границу; то есть [).

   Для других типов (например tsrange,!) Я бы применил то же самое, если это возможно:

   • Предотвращение смежных / перекрывающихся записей с помощью EXCLUDE в PostgreSQL

Решение с использованием чистого 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;

Или с одним меньшим уровнем подзапроса, но с измененным порядком сортировки:

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(с NULLS LAST), чтобы получить полностью перевернутый порядок сортировки. Это должно быть дешевле (проще производить, точно соответствовать порядку сортировки предлагаемого индекса) и быть точным для угловых случаев с rank IS NULL.
  • PostgreSQL сортирует по datetime asc, сначала ноль?

объяснять

a: При упорядочении по range, вычислите рабочий максимум верхней границы ( enddate) с помощью оконной функции.
Замените NULL-границы (неограниченные) на +/- infinityпросто для упрощения (без особых NULL-случаев).

b: В том же порядке сортировки, если предыдущий enddateболее ранний, чем startdateу нас, есть пробел и начинается новый диапазон ( step).
_{Помните, верхняя граница всегда исключается.}

c: Сформировать группы ( grp) путем подсчета шагов с помощью другой оконной функции.

Во внешней SELECTсборке колеблется от нижней до верхней границы в каждой группе. Вуаля.
Тесно связанный ответ на SO с дополнительным объяснением:

• Сравните несколько диапазонов дат

Процедурное решение с plpgsql

Работает для любого имени таблицы / столбца, но только для типа 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($$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$$
            , _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 Fiddle.

Связанный:

• GROUP BY и агрегировать последовательные числовые значения

Обычное упражнение для обработки пользовательского ввода в динамическом SQL:

• SQL-инъекция в функции Postgres против подготовленных запросов

Показатель

Для каждого из этих решений простой (по умолчанию) индекс btree rangeбудет способствовать производительности в больших таблицах:

CREATE INDEX foo on test (range);

Индекс btree имеет ограниченное использование для типов диапазонов , но мы можем получать предварительно отсортированные данные и, возможно, даже сканирование только по индексу.

Я придумал это:

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, чтобы получить бесконечную верхнюю границу

Несколько лет назад я тестировал различные решения (среди прочих, похожие на @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, было бы неплохо получить реальные цифры производительности.

Ради интереса я дал ему шанс. Я обнаружил, что это самый быстрый и чистый способ сделать это. Сначала мы определяем функцию, которая объединяется, если есть перекрытие или если два входа смежны, если нет перекрытия или смежности, мы просто возвращаем первый диапазон дат. Подсказка +- это объединение диапазонов в контексте диапазонов.

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;