Postgresql – Constraint to prevent overlapping ranges in an array field in PostgreSQL

arrayconstraintpostgresqlrange-types

If I have a tztrange field in a table, I can make sure that no two rows have values that overlap using an exclusion constraint. To make sure that no two appointments can be scheduled at the same time, for example, I can use:

CREATE TABLE appointment (
    schedule tstzrange,
    EXCLUDE USING gist (schedule WITH &&)
);

Is there a way to get this same behaviour, but for the values in an array field of type tstzrange[] in a single row?

As an explicit example, I want to be able to define a table test with a constraint that lets these successive inserts both succeed, because in each single array the two ranges don't overlap:

INSERT INTO test (distinct_ranges)
    VALUES ('{"[2016-01-01, 2016-02-01)", "[2016-03-01, 2016-04-01)"}');
INSERT INTO test (distinct_ranges)
    VALUES ('{"[2016-01-15, 2016-02-07)", "[2016-02-29, 2016-03-15)"}');

but such that this insert fails regardless of what other rows exist, because in this array the second range overlaps the first:

INSERT INTO test (distinct_ranges)
    VALUES ('{"[2016-01-01, 2016-02-01)", "[2016-01-15, 2016-02-07)"}');

What I've done so far:

First I thought I'd just look up the function that returned whether or not all ranges in an array were pairwise non-overlapping, and then use a check constraint. Unfortunately, that function doesn't seem to be built-in. I also considered using unnest and the * intersection operator, which would probably mean defining a custom aggregate function, although that's not quite right either unless I can get tricky with the aggregator, because the intersection of three ranges might be empty even though two of the ranges overlap.

So now I'm looking at unnesting the array, sorting it by the start of each range, and returning the logical OR of range1 && range2, range2 && range3, and so on up to range(n-1) && range(n), and checking that that result is false. It's far from obvious to me though what the most efficient way to do this is, and I'm still hoping that I've missed some built-in functionality that will help me out at least partially.

Best Answer

I had a similar problem with an array of int4ranges, and solved it (so far to my satisfaction) by writing this for WiTopia who has kindly agreed to let me share. Please satisfy yourself it works before using it in production -- I am still doing that!

CREATE OR REPLACE  FUNCTION overlapping(therange int4range[])
RETURNS BOOLEAN as
$$
BEGIN

        RETURN (
                with  
                      t1 as (select unnest(therange) as lefthand),
                      t2 as (select unnest(therange) as righthand)
                select (select array_length(therange, 1)) !=
                       (select count(*) from t1, t2 where t1.lefthand && t2.righthand)

       );

END;
$$ LANGUAGE plpgsql

I do a && (overlap) based join with the array and itself. Each item will join with itself, and should join with any other item it overlaps as well, so the count of the result of the &&-join would be greater than the count of the original array if there are overlapping items. If there are only non-overlapping items, then each item will join with itself only, and the result of the join will have one row for each element in the original array.

I'd be careful about using this once the arrays got big -- it's N^2 in concept!

After defining this function, I put this constraint in:

check (portsegments is null or not overlapping(portsegments))

The task as I understand it

Pick rows from a table where the period overlaps with a given time frame. Determine distinct ranges of overlapping periods within that set and return the greatest sum(quantity) from any range.

Requires Postgres 9.2+, since there are no range types in older versions.

Assumptions

"Overlapping" is meant in a cascading manner, like tiles on a traditional roof: those are "overlapping" (rainproof), though the highest tile does not directly overlap with the lowest.
All values in period have inclusive bounds ([]). Else you have to adjust for exclusive bounds. (The range of the input parameter can still have arbitrary bounds.)
We filter for exactly one event_type_id. Else you have to add PARTITION BY event_type_id to the window definition.
quantity is an integer. Else you have to adjust for the type in calculations.
Quantities for overlapping periods are counted fully, even if parts of the period are outside your given time frame.
Even works for duplicates on (event_type_id, period).

Best performance with a single subquery

This should be dynamite.

SELECT running_sum - lag(running_sum, 1, 0) OVER (ORDER BY p_start) AS sum_quantity
FROM  (
   SELECT lower(period) AS p_start
        ,(sum(quantity)                      OVER w)::int AS running_sum
        , lead(lower(period), 1, 'infinity') OVER w
                        > max(upper(period)) OVER w AS range_end
   FROM   event
   WHERE  event_type_id = 1
   AND    period && '[2016-01-01 0:0+0,2016-01-10 0:0+0]'::tstzrange 
   WINDOW w AS (ORDER BY lower(period))
   ) sub
WHERE  range_end
ORDER  BY 1 DESC
LIMIT  1;

All three window functions in the subquery can use the same window. This avoids additional sort operations and should be fastest.

Verbose CTE variant with more explanation

Same query, just more verbose and slower, since CTEs materialize derived tables and pose as optimization barriers.

WITH cte1 AS (
   SELECT quantity
        , lower(period) AS p_start
        , upper(period) AS p_end
   FROM   event
   WHERE  event_type_id = 1
   AND    period && '[2016-01-01 0:0+0,2016-01-10 0:0+0]'::tstzrange
   )
,    cte2 AS (
   SELECT (sum(quantity)               OVER w)::int AS running_sum
        , lead(p_start, 1, 'infinity') OVER w               -- next start ..
                          > max(p_end) OVER w AS range_end  -- .. after last end
        , p_start, p_end
   FROM   cte1
   WINDOW w AS (ORDER BY p_start)
   )
SELECT running_sum - lag(running_sum, 1, 0) OVER (ORDER BY p_start) AS sum_quantity
                    -- subtract the previous sum to get the sum of this range
     , p_end::text
FROM   cte2
WHERE  range_end    -- only rows at the end of each range
ORDER  BY 1 DESC    -- biggest sum first
LIMIT  1;           -- only return the winner

sqlfiddle for Postgres 9.3
db<>fiddle here for Postgres 12

You need an index for this to be fast with big tables. The best option would be a GiST index on (event_type_id, period). Details:

Optimizing queries on a range of timestamps (two columns)

Explanation

Filter rows that match your conditions, then sort by the start of the time range (lower(period)) and calculate:

A running sum of quantity (running_sum).
The start of the next period: (lead(lower(period), 1, 'infinity')). Defaults to 'infinity' for the last row to include the last range.
The latest end of any period so far max(upper(period)).

If 2. is later than 3. it's the end of a (sub-)range (range_end).

In the outer SELECT filter rows with range_end and subtract the previous total to get the sum for the range. ORDER BY that result and return the first (LIMIT 1) greatest sum_quantity. Voilá.

Aside

To select all of Jan 7th, 2016, the clean expression is:

'[2016-01-07 00:00:00+00,2016-01-08 00:00:00+00)'::tstzrange

Not:

'[2016-01-07 00:00:00+00,2016-01-07 23:59:00+00]'::tstzrange

Details:

PostgreSQL splitting time range into days

Since the default precision of timestamp values is 6 decimal digits (microseconds resolution), you could also use:

'[2016-01-07 00:00:00+00,2016-01-07 23:59:59.999999+00]'::tstzrange

But that's messy and depends on an implementation detail that might change (even if unlikely). It's not subject to rounding errors, since timestamps are stored as integer values in modern Postgres:

Ignoring timezones altogether in Rails and PostgreSQL

Best Answer

Related Solutions

Postgresql – How to handle bad query plan caused by exact equality on range type

Postgresql – Maximum sum() of overlapping ranges