3

Essentially my question is: how does one do aggregate operations involving overlapping ranges in PostgreSQL 9.3 (or 9.4)? The specific problem I have at hand is that given a range, I want to find the maximum sum() of applicable overlapping ranges. A simple example:

create table event (
  event_id int primary key,
  event_type_id int not null,
  period tstzrange not null,
  quantity int not null
);

insert into event (event_id, event_type_id, period, quantity) values
(1, 1,'[2016-01-06 09:00:00+00,2016-01-08 17:00:00+00]',1),
(2, 1,'[2016-01-07 09:00:00+00,2016-01-07 11:00:00+00]',1),
(3, 1,'[2016-01-07 13:00:00+00,2016-01-07 17:00:00+00]',1),
(4, 2,'[2016-01-07 12:00:00+00,2016-01-07 17:00:00+00]',1);

Given a query with the following clauses:

select ... 
where event_type_id = 1
and period && '[2016-01-07 00:00:00+00,2016-01-07 23:59:00+00]'::tstzrange 
group by event_type_id

The desired result would be: 3, i.e. the maximum sum(quantity) where the ranges of the same event_type_id overlap within a given timestamp range.

  • What else can you tell us about the rules for period? All bounds inclusive? Can there be duplicates for (event_type_id, period)? If not, is that enforced with a UNIQUE constraint or index? Which indexes do you have now (besides the PK)? – Erwin Brandstetter Jan 28 '15 at 16:39
  • I think the result should be 3. All rows for event_type_id = 1 qualify and all overlap: row 1 overlaps with 2 and 3. So we have one range with a sum(quantity) = 3. – Erwin Brandstetter Jan 28 '15 at 21:20
  • You're right, the sum should be 3. Oops! I've edited accordingly. And yes, all ranges are inclusive, and there are no constraints other than the PK and no indexes, since I wanted to keep the example simple. – Rob Feb 3 '15 at 17:22
5

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

  • 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

SQL Fiddle.

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:

Explanation

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

  1. A running sum of quantity (running_sum).
  2. The start of the next period: (lead(lower(period), 1, 'infinity')). Defaults to 'infinity' for the last row to include the last range.
  3. 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:

Since the default precision of timestamp values is 6 digital digits, you could also use:

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

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

  • 1
    This is an incredibly informative answer. Having both methods is particularly helpful, because it helps me learn how me how to apply window functions. Thank you Erwin! – Rob Feb 3 '15 at 17:30
  • This is brilliant ... not only providing the example query but also the detailed explanation ... many thanks Erwin ... you have been referenced in my code (as a jedi master) – Chris Hilton Jul 28 '15 at 17:15
  • Excellent solution! – Royal Pinto Sep 30 '18 at 5:02
1

I am not good enough to post comments so I have to write a reply.

Erwin's answer does not seem to work if an event spans more than one group.

with event(event_id, event_type_id, period, quantity)  as (
    values
     (1, 1, '[2016-01-07 09:00:00+00,2016-01-07 10:00:00+00]'::tstzrange,    1)
    ,(2, 1, '[2016-01-07 09:00:00+00,2016-01-07 11:00:00+00]'::tstzrange,   10)
    ,(3, 1, '[2016-01-07 13:00:00+00,2016-01-07 17:00:00+00]'::tstzrange,  100)
    ,(4, 2, '[2016-01-07 09:00:00+00,2016-01-07 18:00:00+00]'::tstzrange, 1000)
)
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;

Here, events 1 and 2 overlap, 3 sits on its own and 4 overlaps with all the rest but is a different type. The query rightly return 100 because 3 is the one with the most quantity.

Now, change the type of event 4 to 1 so it is taken in consideration, I would expect a result of 1100 since e1+e2+e4 = 1011 and e3+e4 = 1100. Instead I get 1111. Seems that all events are taken together.

  • You might want to consider creating your own question if this is a new issue. If you are here because a question of yours was closed, because a duplicate of... then you might want to consider updating your existing question with this information. This answer will probably be closed soon as Not an answer. – hot2use Apr 23 '18 at 12:14

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.