20

I'm trying to combine multiple date ranges (my load is about max 500, most cases 10) that may or may not overlap into the largest possible contiguous date ranges. For example:

Data:

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'));

Table looks like:

 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)

Desired results:

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

Visual representation:

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

Assumptions / Clarifications

  1. No need to differentiate between infinity and open upper bound (upper(range) IS NULL). (You can have it either way, but it's simpler this way.)

  2. Since date is a discrete type, all ranges have default [) bounds. Per documentation:

    The built-in range types int4range, int8range, and daterange all use a canonical form that includes the lower bound and excludes the upper bound; that is, [).

    For other types (like tsrange!) I would enforce the same if possible:

Solution with pure SQL

With CTEs for clarity:

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;

Or, the same with subqueries, faster but less easy too read:

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;

Or with one less subquery level, but flipping sort order:

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;
  • Sort the window in the second step with ORDER BY range DESC NULLS LAST (with NULLS LAST) to get perfectly inverted sort order. This should be cheaper (easier to produce, matches sort order of suggested index perfectly) and accurate for corner cases with rank IS NULL.

Explain

a: While ordering by range, compute the running maximum of the upper bound (enddate) with a window function.
Replace NULL bounds (unbounded) with +/- infinity just to simplify (no special NULL cases).

b: In the same sort order, if the previous enddate is earlier than startdate we have a gap and start a new range (step).
Remember, the upper bound is always excluded.

c: Form groups (grp) by counting steps with another window function.

In the outer SELECT build ranges from lower to upper bound in each group. Voilá.
Closely related answer on SO with more explanation:

Procedural solution with plpgsql

Works for any table / column name, but only for type daterange.
Procedural solutions with loops are typically slower, but in this special case I expect the function to be substantially faster since it only needs a single sequential scan:

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;

Call:

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

The logic is similar to the SQL solutions, but we can make do with a single pass.

SQL Fiddle.

Related:

The usual drill for handling user input in dynamic SQL:

Index

For each of these solutions a plain (default) btree index on range would be instrumental for performance in big tables:

CREATE INDEX foo on test (range);

A btree index is of limited use for range types, but we can get pre-sorted data and maybe even an index-only scan.

  • @Villiers: I would be very interested how each of these solutions performs with your data. Maybe you can post another answer with test results and some info on your table design and cardinalities? Best with EXPLAIN ( ANALYZE, TIMING OFF) and compare best of five. – Erwin Brandstetter May 9 '15 at 13:55
  • The key to this kind of problems is the lag SQL function (lead can also be used) that compare the values of sorted rows. This eliminated the need for self joins which can also be used to merged overlapping ranges into a single range. Instead of range, any problem involving two columns some_star, some_end can use this strategy. – Kemin Zhou Dec 26 '17 at 21:44
  • @ErwinBrandstetter Hey, I am trying to understand this query (the one with CTEs), but I can't figure out what (CTE A) max(COALESCE(upper(range), 'infinity')) OVER (ORDER BY range) AS enddate is for? Can't it be just COALESCE(upper(range), 'infinity') as enddate? AFAIK max() + over (order by range) will return just upper(range) here. – user606521 Jul 27 '18 at 8:29
  • 1
    @user606521: What you observe is the case if the upper bound grows continuously when sorted by range - which may be guaranteed for some data distributions and then you can simplify as you suggest. Example: fixed length ranges. But for ranges of arbitrary length the next range can have a greater lower bound, but still a lower upper bound. So we need the greatest upper bound of all ranges so far. – Erwin Brandstetter Jul 28 '18 at 0:23
6

I've come up with this:

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;
$$;

Still needs a bit of honing, but the idea is the following:

  1. explode the ranges to individual dates
  2. doing this, replace the infinite upper bound with some extreme value
  3. based on the ordering from (1), start building the ranges
  4. when the union (+) fails, return the already built range and reinitialize
  5. finally, return the rest - if the predefined extreme value is reached, replace it with NULL to get an infinite upper bound
  • It strikes me as rather expensive to run generate_series() for every row, especially if there can be open ranges ... – Erwin Brandstetter May 9 '15 at 22:56
  • @ErwinBrandstetter yes, that's an issue I wanted to test (after my first extreme was 9999-12-31 :). At the same time, I am wondering why my answer has more upvotes than yours. This is possibly easier to understand... So, future voters: Erwin's answer is superior to mine! Vote there! – dezso May 11 '15 at 8:19
3

Some years ago I tested different solutions (amongst others some similar to those from @ErwinBrandstetter) for merging overlapping periods on a Teradata system and I found the following the most efficient one (using Analytical Functions, newer version of Teradata have built-in functions for that task).

  1. sort the rows by start date
  2. find the maximum end date of all previous rows: maxEnddate
  3. if this date is less than the current start date, you found a gap. Only keep those rows plus the first row within the PARTITION (which is indicated by a NULL) and filter all other rows. Now you get the start date for each range and the end date of the previous range.
  4. Then you simply get the next row's maxEnddate using LEAD and you're almost done. Only for the last row LEAD returns a NULL, to solve this calculate the maximum end date of all rows of a partition in step 2 and COALESCE it.

Why it was faster? Depending on the actual data step #2 might greatly reduce the number of rows, so the next step needs to operate on a small subset only, additionally it removes aggregation.

fiddle

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;  

As this was fastest on Teradata, I don't know if it's the same for PostgreSQL, would be nice to get some actual performance numbers.

  • Is it sufficient to order by only by start of range? Does it work if you have three ranges each with same start but varying end? – Salman A Jan 24 at 14:30
  • 1
    It works with the start date only, no need to add the end date sorted descending (you only check for the a gap, so whatever is the first row for a given date will match) – dnoeth Jan 24 at 17:47
-1

For fun, I gave it a shot. I found this to be the fastest and cleanest method to do this. First we define a function that merges if there is an overlap or if the two inputs are adjacent, if there is no overlap or adjacency we simply return the first daterange. Hint + is a range union in the context of ranges.

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;

Then we use it like this,

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
    The window function only considers two adjacent values at a time and misses chains. Try with ('2015-01-01', '2015-01-03'), ('2015-01-03', '2015-01-05'), ('2015-01-05', '2015-01-06'). – Erwin Brandstetter Dec 28 '17 at 2:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.