Find blocks of unused numbers

from the Artful Common Queries page


In a table of sequential IDs with no missing values, some are used and some are not. Find the blocks of unused IDs, if any:

DROP TABLE IF EXISTS tbl;
CREATE TABLE tbl(id INT,used BOOL);
INSERT INTO tbl VALUES (1,1),(2,1),(3,0),(4,1),(5,0),(6,1),(7,1),(8,1),
                       (9,0),(10,0),(11,1),(12,1),(13,0),(14,0),(15,0);
SELECT * FROM tbl;
+------+------+
| id   | used |
+------+------+
|    1 |    1 |
|    2 |    1 |
|    3 |    0 |
|    4 |    1 |
|    5 |    0 |
|    6 |    1 |
|    7 |    1 |
|    8 |    1 |
|    9 |    0 |
|   10 |    0 |
|   11 |    1 |
|   12 |    1 |
|   13 |    0 |
|   14 |    0 |
|   15 |    0 |
+------+------+

The first ID in any unused sequence has used=0 and either no immediate predecessor, or an immediate predecessor where used=1. The last ID of any unused sequence either has no successor or the successor has used=1. So:

1. Find the first first ID of every unused sequence by left joining each row with used=0 to the immediate predecessor row, conditioning the result on the predecessor row not existing or having used=1.

2. As a basis for finding the last ID of every unused sequence that is followed by a row with used=1, left join first unused rows to rows with larger IDs and used=1.

3. As a basis for finding the last ID of an unused sequence which is also the largest ID in the table, left join first unused rows to rows with larger IDs and used=0.

4. For each first unused ID, the last unused ID in its sequence is one less than the smallest used ID greater than the first ID if it exists, otherwise it is the maximum unused ID greater than the first ID.

SELECT firstUnused, IF(mincid IS NULL, IFNULL(did,firstUnused),mincid-1) AS lastUnused
FROM (
  SELECT first.id AS firstUnused, MIN(c.id) AS mincid, MAX(d.id) AS did 
  FROM (
    SELECT a.id 
    FROM tbl a 
    LEFT JOIN tbl b ON a.id=b.id + 1
    WHERE a.used=0 AND (b.id IS NULL OR b.used=1)
  ) AS first
  LEFT JOIN tbl c ON first.id<c.id AND c.used=1
  LEFT JOIN tbl d ON first.id<d.id AND d.used=0 
  GROUP BY firstUnused
) AS e;
+-------------+------------+
| firstUnused | lastUnused |
+-------------+------------+
|           3 |          3 |
|           5 |          5 |
|           9 |         10 |
|          13 |         15 |
+-------------+------------+

Thanks to Don Armstrong for finding a case where our previous algorithm failed.

Return to the Artful Common Queries page