Posted on 2 Comments

Finding (and grouping) contiguous ranges

Here’s an interesting problem that came up… a user wants to find “ranges” or items in a table, or call them series if you will. The range is of course entirely dynamic, dependent on the data in the table.
Say a table contains 1,2,5,6,7,12,17,18,19,20 then we have (1,2) (5,6,7) (12) (17,18,19,20)
All clear?
The trick is of course to write some SQL that actually finds these ranges, so you can do a select that identifies lowest-highest in each range, so given the above you’d want to see 1-2,5-7,12-12,17-20. It involves grouping, but you can’t group by on an unknown.

This is the solution:

  CREATE TEMPORARY TABLE gaps (gap INT PRIMARY KEY)
    SELECT 0
    UNION
    SELECT t1.test
      FROM range AS t1 LEFT JOIN range AS t2 ON t1.test=T2.test-1
     WHERE t2.test IS NULL;

  SELECT range.test AS probe,
         MIN(range.test) AS range_start,
         (SELECT MIN(gaps.gap)
            FROM gaps
           WHERE gaps.gap >= probe) AS range_end
    FROM range
    GROUP BY range_end;

It can be done without the temp table, but in this case we add an index to the field in the temp table, which will speed up the second query significantly.

The probe column is necessary because a) you want the result to return the lowest in the group but b) you can’t use the range_start aggregate value in the subquery as that would be a chicken&egg case.

Please note that there could be typos and practical mishaps in the above, but the idea works and is quite educational. Please feel free to post a comment with corrections/improvements! And if you know a better/faster way to do this, it’d be great to hear from you too!

Posted on 2 Comments

2 thoughts on “Finding (and grouping) contiguous ranges

  1. Hey,
    Awesome post, saved me a LOT of time and is quite efficient! There were only two changes really that I had to make:

    t1.test=T2.test-1
    change to
    t1.test=t2.test-1

    and I was unsure on why in the first query there is:
    “SELECT 0
    UNION”
    It seems to work perfectly fine without it and it was causing me primary key errors?

    Awesome work, once again thank you!

  2. Thanks for posting this nice solution to a common SQL problem. I encountered a similar problem: grouping contiguous rows having an equivalent key (rather than adjacent keys as in this example) where you want to preserve the order of the table. The solution is posted here: http://gcbenison.wordpress.com/2011/09/26/queries-that-group-tables-by-contiguous-blocks/

    A note on the previous comment –
    The cause of the primary key errors is that the temporary table expects the column to be named ‘gap’; here is a corrected version:

    CREATE TEMPORARY TABLE gaps (gap INT PRIMARY KEY)
    SELECT 0 AS gap
    UNION
    (SELECT t1.test
    FROM range AS t1 LEFT JOIN range AS t2 ON t1.test=t2.test-1
    WHERE t2.test IS NULL);

Comments are closed.