Sum length of overlapping intervals

Question

I've got a table in a Redshift database that contains intervals which are grouped and that potentially overlap, like so:

| interval_id | l  | u  | group |
| ----------- | -- | -- | ----- |
| 1           | 1  | 10 | A     |
| 2           | 2  | 5  | A     |
| 3           | 5  | 15 | A     |
| 4           | 26 | 30 | B     |
| 5           | 28 | 35 | B     |
| 6           | 30 | 31 | B     |
| 7           | 44 | 45 | B     |
| 8           | 56 | 58 | C     |

What I would like to do is to determine the length of the union of the intervals within group. That is, for each interval take u - l, sum over all group members and then subtract off the length of the overlaps between the intervals.

Desired result:

| group | length |
| ----- | ------ |
| A     | 14     |
| B     | 10     |
| C     | 2      |

This question has been asked before, alas it seems that all of the solutions in that thread use features that Redshift doesn't support.

Answer 1

This is not difficult but requires multiple steps. The key is to define the "islands" within each group and then aggregate over those. Lots of subquerys, aggregations, and window functions.

select groupId, sum(ul)
from (select groupId, (max(u) - min(l) + 1) as ul
      from (select t.*,
                   sum(case when prev_max_u < l then 1 else 0 end) over (order by l) as grp
            from (select t.*,
                         max(u) over (order by l rows between unbounded preceding and 1 preceding) as prev_max_u
                  from t
                 ) t
           ) t
      group by groupid, grp
     ) g
group by groupId;

The idea is to determine if there is an overlap at the beginning of each record. For this purpose, it uses a cumulative max function on all preceding records. Then, it determines if there is an overlap by comparing the previous max with the current l -- a cumulative sum of overlaps defines a group.

The rest is just aggregation. And more aggregation.