Thread: Query to find contiguous ranges on a column

Query to find contiguous ranges on a column

From
Peter Hunsberger
Date:
Given a column of data resembling the following:

col
2
3
4
5
11
12
13
14
15
16
17
18
19
23
32
33
34
35
36
37

I need a query to find the contiguous ranges within this column, in
this case returning the result set:

start, end
2, 5
11, 19
23, 23
32, 37

I have one solution that joins the table against itself and does
(among other things) a subselect looking "not exists col +1" and "not
exists col -1" on the two instances of the table to find the start and
end.  This is, as you might guess, is not very efficient (my actual
data is some 6 million+ rows) and I'm guessing there has to be
something more efficient with windowing or possibly grouping on min
and max (though I can't see how to make sure they are part of a
contiguous set).  Anyone have any ideas?

--
Peter Hunsberger

Re: Query to find contiguous ranges on a column

From
Tim Landscheidt
Date:
Peter Hunsberger <peter.hunsberger@gmail.com> wrote:

> [...]
> I have one solution that joins the table against itself and does
> (among other things) a subselect looking "not exists col +1" and "not
> exists col -1" on the two instances of the table to find the start and
> end.  This is, as you might guess, is not very efficient (my actual
> data is some 6 million+ rows) and I'm guessing there has to be
> something more efficient with windowing or possibly grouping on min
> and max (though I can't see how to make sure they are part of a
> contiguous set).  Anyone have any ideas?

You can either use a PL/pgSQL function ("SETOF TEXT" just
for the convenience of the example):

| CREATE FUNCTION SummarizeRanges () RETURNS SETOF TEXT AS $$
| DECLARE
|   CurrentFirst INT;
|   CurrentLast INT;
|   CurrentRecord RECORD;
| BEGIN
|   FOR CurrentRecord IN SELECT col FROM t ORDER BY col LOOP
|     IF CurrentFirst IS NULL THEN
|       CurrentFirst := CurrentRecord.col;
|       CurrentLast  := CurrentRecord.col;
|     ELSIF CurrentRecord.col = CurrentLast + 1 THEN
|       CurrentLast := CurrentRecord.col;
|     ELSE
|       RETURN NEXT CurrentFirst || ', ' || CurrentLast;
|       CurrentFirst := CurrentRecord.col;
|       CurrentLast := CurrentRecord.col;
|     END IF;
|   END LOOP;
|   IF CurrentFirst IS NOT NULL THEN
|     RETURN NEXT CurrentFirst || ', ' || CurrentLast;
|   END IF;
|   RETURN;
| END;
| $$ LANGUAGE plpgsql;

or a recursive query (which I always find very hard to com-
prehend):

| WITH RECURSIVE RecCols (LeftBoundary, Value) AS
|   (SELECT col, col FROM t WHERE (col - 1) NOT IN (SELECT col FROM t)
|    UNION ALL SELECT p.LeftBoundary, c.col FROM RecCols AS p, t AS c WHERE c.col = p.Value + 1)
|   SELECT LeftBoundary, MAX(Value) AS RightBoundary FROM RecCols
|     GROUP BY LeftBoundary
|     ORDER BY LeftBoundary;

Could you run both against your data set and find out which
one is faster for your six million rows?

Tim

Re: Query to find contiguous ranges on a column

From
Thomas Kellerer
Date:
Peter Hunsberger wrote on 13.10.2009 23:23:
> I need a query to find the contiguous ranges within this column, in
> this case returning the result set:
>
> start, end
> 2, 5
> 11, 19
> 23, 23
> 32, 37
>
> I have one solution that joins the table against itself and does
> (among other things) a subselect looking "not exists col +1" and "not
> exists col -1" on the two instances of the table to find the start and
> end.  This is, as you might guess, is not very efficient (my actual
> data is some 6 million+ rows) and I'm guessing there has to be
> something more efficient with windowing or possibly grouping on min
> and max (though I can't see how to make sure they are part of a
> contiguous set).  Anyone have any ideas?

This is the best I can put together right now.

Not very nice, but currently I can't think of a better solution:

select *
from
(
  select soi as start_of_interval,
         case
           when soi is not null and eoi is null then lead(eoi) over()
           when soi is not null and eoi is not null then eoi
           else null
         end as end_of_interval
  from (
      select case
               when col - (lag(col,1,col + 1) over (order by col)) - 1 <> 0 then col
               else null
             end as soi,
             case
               when col - (lead(col,1,col + 1) over (order by col)) + 1 <> 0 then col
               else null
             end as eoi
      from numbers
  ) t1
  where t1.soi is not null
     or t1.eoi is not null
) t2
where t2.start_of_interval is not null
  and t2.end_of_interval is not null;

The outer-most select is needed to get rid of the "empty" rows. I couldn't find a way to push that into one of the
sub-queries.

The execution plan doesn't look too bad (probably better than your plan with a self join and a subselect), but it does
sortthe whole table which might be a problem.  

Regards
Thomas





Re: Query to find contiguous ranges on a column

From
Peter Hunsberger
Date:
On Tue, Oct 13, 2009 at 5:12 PM, Tim Landscheidt <tim@tim-landscheidt.de> wrote:
> Peter Hunsberger <peter.hunsberger@gmail.com> wrote:
>
> You can either use a PL/pgSQL function ("SETOF TEXT" just
> for the convenience of the example):

That works well, takes about 20 seconds to do the 6M+ rows

>
> or a recursive query (which I always find very hard to com-
> prehend):
>
> | WITH RECURSIVE RecCols (LeftBoundary, Value) AS
> |   (SELECT col, col FROM t WHERE (col - 1) NOT IN (SELECT col FROM t)
> |    UNION ALL SELECT p.LeftBoundary, c.col FROM RecCols AS p, t AS c WHERE c.col = p.Value + 1)
> |   SELECT LeftBoundary, MAX(Value) AS RightBoundary FROM RecCols
> |     GROUP BY LeftBoundary
> |     ORDER BY LeftBoundary;
>
> Could you run both against your data set and find out which
> one is faster for your six million rows?
>

Turns out the server is v 8.3, looks like I need to get them to
upgrade it so I get recursive and windowing :-(.  If this happens any
time soon I'll let you know the results.

Many thanks.


--
Peter Hunsberger

Re: Query to find contiguous ranges on a column

From
Tim Landscheidt
Date:
Peter Hunsberger <peter.hunsberger@gmail.com> wrote:

> [...]
>> or a recursive query (which I always find very hard to com-
>> prehend):

>> | WITH RECURSIVE RecCols (LeftBoundary, Value) AS
>> |   (SELECT col, col FROM t WHERE (col - 1) NOT IN (SELECT col FROM t)
>> |    UNION ALL SELECT p.LeftBoundary, c.col FROM RecCols AS p, t AS c WHERE c.col = p.Value + 1)
>> |   SELECT LeftBoundary, MAX(Value) AS RightBoundary FROM RecCols
>> |     GROUP BY LeftBoundary
>> |     ORDER BY LeftBoundary;

>> Could you run both against your data set and find out which
>> one is faster for your six million rows?

> Turns out the server is v 8.3, looks like I need to get them to
> upgrade it so I get recursive and windowing :-(.  If this happens any
> time soon I'll let you know the results.

> Many thanks.

After some tests with a data set of 7983 rows (and 1638 ran-
ges): Don't! :-) The recursive solution seems to be more
than double as slow as the iterative. I'll take it to -per-
formance.

Tim

Re: Query to find contiguous ranges on a column

From
Peter Hunsberger
Date:
On Wed, Oct 14, 2009 at 4:50 PM, Tim Landscheidt <tim@tim-landscheidt.de> wrote:
> Peter Hunsberger <peter.hunsberger@gmail.com> wrote:
>
> After some tests with a data set of 7983 rows (and 1638 ran-
> ges): Don't! :-) The recursive solution seems to be more
> than double as slow as the iterative. I'll take it to -per-
> formance.
>

Interesting, I've never liked recursive on Oracle but performance is
usually reasonable... Thanks for the heads up...


--
Peter Hunsberger