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

20

Я пытаюсь объединить несколько диапазонов дат (моя загрузка составляет около 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
wiki.postgresql.org/wiki/Range_aggregation
Евгений Коньков

Ответы:

22

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

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

  2. Поскольку 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;

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

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

объяснять

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.

Связанный:

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

Показатель

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

CREATE INDEX foo on test (range);

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

Эрвин Брандштеттер
источник
@Villiers: Мне было бы очень интересно, как каждое из этих решений работает с вашими данными. Может быть, вы можете опубликовать еще один ответ с результатами теста и некоторой информацией о вашей таблице и кардинальности? Лучше всего EXPLAIN ( ANALYZE, TIMING OFF)сравнивать с лучшими из пяти.
Эрвин Брандштеттер,
Ключом к этому типу проблем является функция задержки SQL (также можно использовать лидерство), которая сравнивает значения отсортированных строк. Это исключило необходимость самостоятельных объединений, которые также можно использовать для объединения перекрывающихся диапазонов в один диапазон. Вместо диапазона, любая проблема с двумя столбцами some_star, some_end может использовать эту стратегию.
Кемин Чжоу
@ErwinBrandstetter Эй, я пытаюсь понять этот запрос (тот, у которого есть CTE), но я не могу понять, для чего (CTE A) max(COALESCE(upper(range), 'infinity')) OVER (ORDER BY range) AS enddate? Разве это не может быть просто COALESCE(upper(range), 'infinity') as enddate? AFAIK max() + over (order by range)вернется только upper(range)сюда.
user606521
1
@ user606521: Вы наблюдаете случай, когда верхняя граница непрерывно увеличивается при сортировке по диапазону - что может быть гарантировано для некоторых распределений данных, и тогда вы можете упростить, как вы предлагаете. Пример: фиксированные диапазоны длин. Но для диапазонов произвольной длины следующий диапазон может иметь большую нижнюю границу, но все же более низкую верхнюю границу. Таким образом, нам нужна самая большая верхняя граница из всех диапазонов.
Эрвин Брандштеттер,
6

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

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, чтобы получить бесконечную верхнюю границу
Dezso
источник
Мне кажется довольно дорогим бегать generate_series()на каждом ряду, особенно если могут быть открытые диапазоны ...
Эрвин Брандштеттер,
@ErwinBrandstetter да, это проблема, которую я хотел проверить (после того, как мой первый экстремум был 9999-12-31 :). В то же время мне интересно, почему мой ответ имеет больше голосов, чем ваш. Возможно, это легче понять ... Итак, будущие избиратели: ответ Эрвина превосходит мой! Голосуй там!
Дезсо
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, было бы неплохо получить реальные цифры производительности.

dnoeth
источник
Достаточно ли сделать заказ только по началу диапазона? Работает ли это, если у вас есть три диапазона с одинаковым началом, но разным концом?
Салман А
1
Он работает только с начальной датой, нет необходимости добавлять отсортированную по убыванию конечную дату (вы проверяете только пробел, поэтому, какой бы ни была первая строка для данной даты, будет соответствовать)
dnoeth
-1

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

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
Функция окна одновременно рассматривает только два смежных значения и пропускает цепочки. Попробуй с ('2015-01-01', '2015-01-03'), ('2015-01-03', '2015-01-05'), ('2015-01-05', '2015-01-06').
Эрвин Брандштеттер