MySQL – Finding Contiguous Ranges in Grouped Data

gaps-and-islandsgroup byMySQL

I have a table with the following structure:

CREATE TABLE `Rings` (
    ID_RingType CHAR(2),
    Number MEDIUMINT UNSIGNED,
    ID_User INT(11)
);

and with data:

INSERT INTO `Rings` VALUES
  ('AA',1,1),
  ('AA',2,1),
  ('AA',3,1),
  ('AA',11,1),
  ('AA',12,1),
  ('AA',13,1),
  ('AA',14,1),
  ('AA',15,1),
  ('AB',16,1),
  ('AB',17,1),
  ('AB',18,1),
  ('AB',19,1),
  ('AB',20,2),
  ('AB',21,2),
  ('AB',22,2);

I wish to group the data based on ID_User and ID_RingType and for each contiguous range of numbers list the MIN and MAX.

The results should look like:

ID_User | ID_RingType | MIN  | MAX
1       | 'AA'        | 1    | 3
1       | 'AA'        | 11   | 15
1       | 'AB'        | 16   | 19
2       | 'AB'        | 20   | 22

I went through several posts on this topic but was not able to tweak them to fit my data.

Any help would be appreciated.

Best Answer

The answer with the variables is going to be more efficient but here is an answer with pure SQL:

select 
    a.id_user, 
    a.id_ringtype, 
    a.number      as min,
    min(b.number) as max
from 
    rings as a 
  join rings as b 
    on  a.id_user = b.id_user 
    and a.id_ringtype = b.id_ringtype 
    and a.number <= b.number 
where not exists 
      ( select 1 
        from rings as c 
        where c.id_user = a.id_user 
          and c.id_ringtype = a.id_ringtype 
          and c.number = a.number - 1
      )
  and not exists 
      ( select 1 
        from rings as d 
        where d.id_user = b.id_user 
          and d.id_ringtype = b.id_ringtype 
          and d.number = b.number + 1
      ) 
group by 
    a.id_user, 
    a.id_ringtype, 
    a.number ;

Efficiency will depend on many factors (mainly distibution of data) but an index on (id_user, id_ringtype, number) is essential for this query.

SUGGESTED QUERY

SELECT
    CONCAT(A.ndx,' - ',A.ndx+9) "score range",
    IFNULL(B.rowcount ,0) "number of occurrences"
FROM
(
    SELECT 0 ndx UNION SELECT 10 UNION SELECT 20 UNION
    SELECT 30 UNION SELECT 40 UNION SELECT 50 UNION SELECT 60
    UNION SELECT 70 UNION SELECT 80 UNION SELECT 90
) A
LEFT JOIN
(
    SELECT ndx,COUNT(1) rowcount FROM
    (SELECT FLOOR(score/10)*10 ndx FROM yoshi_scores) AA
    GROUP BY ndx
) B USING (ndx);

SAMPLE DATA

use test
DROP TABLE IF EXISTS yoshi_scores;
CREATE TABLE yoshi_scores
(id int not null auto_increment,
score int not null,primary key (id), key (score));
INSERT INTO yoshi_scores (score) VALUES
(97),(74),(22),(98),(65),(62),(47),(64),(82),( 8),(60),(12),
(27),(14),(13),(28),(60),(12),(27),(34),(32),(89),(15),( 2);

Data would look like this

mysql> SELECT * FROM yoshi_scores ORDER BY id;
+----+-------+
| id | score |
+----+-------+
|  1 |    97 |
|  2 |    74 |
|  3 |    22 |
|  4 |    98 |
|  5 |    65 |
|  6 |    62 |
|  7 |    47 |
|  8 |    64 |
|  9 |    82 |
| 10 |     8 |
| 11 |    60 |
| 12 |    12 |
| 13 |    27 |
| 14 |    14 |
| 15 |    13 |
| 16 |    28 |
| 17 |    60 |
| 18 |    12 |
| 19 |    27 |
| 20 |    34 |
| 21 |    32 |
| 22 |    89 |
| 23 |    15 |
| 24 |     2 |
+----+-------+
24 rows in set (0.00 sec)

SUGGESTED QUERY EXECUTED

mysql> SELECT
    ->     CONCAT(A.ndx,' - ',A.ndx+9) "score range",
    ->     IFNULL(B.rowcount ,0) "number of occurrences"
    -> FROM
    -> (
    ->     SELECT 0 ndx UNION SELECT 10 UNION SELECT 20 UNION
    ->     SELECT 30 UNION SELECT 40 UNION SELECT 50 UNION SELECT 60
    ->     UNION SELECT 70 UNION SELECT 80 UNION SELECT 90
    -> ) A
    -> LEFT JOIN
    -> (
    ->     SELECT ndx,COUNT(1) rowcount FROM
    ->     (SELECT FLOOR(score/10)*10 ndx FROM yoshi_scores) AA
    ->     GROUP BY ndx
    -> ) B USING (ndx);
+-------------+-----------------------+
| score range | number of occurrences |
+-------------+-----------------------+
| 0 - 9       |                     2 |
| 10 - 19     |                     5 |
| 20 - 29     |                     4 |
| 30 - 39     |                     2 |
| 40 - 49     |                     1 |
| 50 - 59     |                     0 |
| 60 - 69     |                     5 |
| 70 - 79     |                     1 |
| 80 - 89     |                     2 |
| 90 - 99     |                     2 |
+-------------+-----------------------+
10 rows in set (0.00 sec)

mysql>

Why is the Query designed this way ??? Look at the first subquery

(
    SELECT 0 ndx UNION SELECT 10 UNION SELECT 20 UNION
    SELECT 30 UNION SELECT 40 UNION SELECT 50 UNION SELECT 60
    UNION SELECT 70 UNION SELECT 80 UNION SELECT 90
) A

I performed a LEFT JOIN of this to the counts for a reason. Notice that the dataset has nothing in the 50 - 59 range. Its count would not show up in the second query:

mysql> SELECT ndx,COUNT(1) rowcount FROM
    -> (SELECT FLOOR(score/10)*10 ndx FROM yoshi_scores) AA
    -> GROUP BY ndx;
+------+----------+
| ndx  | rowcount |
+------+----------+
|    0 |        2 |
|   10 |        5 |
|   20 |        4 |
|   30 |        2 |
|   40 |        1 |
|   60 |        5 |
|   70 |        1 |
|   80 |        2 |
|   90 |        2 |
+------+----------+
9 rows in set (0.00 sec)

mysql>

I am sure you wanted the range 50 - 59 to show up, so the query is designd to catch all ranges. Any missing range is essentially defaulted to zero.

GIVE IT A TRY !!!

CAVEAT: Unfortunately, the first subquery requires you to hardcode it. It will be the only hardcoding required to make it work.

PostgreSQL – How to Check for Contiguous Date Intervals

First, we combine intervals that overlap to find all the contiguous "islands" of the intervals:

with c as
  ( select *, max(end_date) over (order by start_date
                                  rows between unbounded preceding
                                           and 1 preceding)
                as previous_max
    from my_table
  )
select start_date, 
       coalesce(lead(previous_max) over (order by start_date),
                (select max(end_date) from my_table)
               ) as end_date
from c 
where previous_max < start_date 
   or previous_max is null ;

After that, it's easy to check if a given interval in completely surrounded by one of the found contiguous islands.

   with c as
  ( select *, max(end_date) over (order by start_date
                                  rows between unbounded preceding
                                           and 1 preceding)
                as previous_max
    from my_table
  ) ,
cont as
  ( select start_date, 
           coalesce(lead(previous_max) over (order by start_date),
                    (select max(end_date) from my_table)
                   ) as end_date
    from c 
    where previous_max < start_date 
       or previous_max is null  
   )
select *
from cont
where tsrange(start_date, end_date)
       @>                             -- contains
      tsrange('2015-04-02 22:10:00', '2015-04-02 22:30:00') 
limit 1 ;

Test at SQLfiddle

Best Answer

Related Solutions

Mysql – “GROUP BY” in ranges

SUGGESTED QUERY

SAMPLE DATA

SUGGESTED QUERY EXECUTED

GIVE IT A TRY !!!

PostgreSQL – How to Check for Contiguous Date Intervals

Related Question