Find missing numbers in a sequence

from the Artful Common Queries page

You have a table tbl(id int) with values (1,2,4,18,19,20,21), and you wish to find the first missing number in its sequence of id values:

FROM tbl      AS t1
LEFT JOIN tbl AS t2 ON =
| Missing |
|       3 |

For all the gaps, including gaps of more than 1 value, aggregate on an inequality join ...

SELECT AS 'Missing From', MIN( AS 'Through'
FROM tbl AS a
JOIN tbl AS b ON <
| Missing From | Through   |
|            3 |         3 |
|            5 |        17 |

We often need such lists, so the query is a natural for a stored procedure that finds missing sequence values in any table:

CREATE PROCEDURE MissingInSeq( db VARCHAR(64), tbl VARCHAR(64), col VARCHAR(64) )
  SET @sql = CONCAT( "SELECT  a.", col, 
                     "+1 AS 'Missing From',", 
                     ") - 1 AS 'Through' FROM ",
                     " AS a,", 
                     " AS b WHERE a.", 
                     " < b.", 
                     " GROUP BY a.", 
                     " HAVING a.", 
                     " < MIN(b.", 
                     ") - 1" 
  -- SELECT @sql;
  PREPARE stmt FROM @sql;
  EXECUTE stmt;

A much quicker algorithm

For row counts up to a few thousand, the above approach is fine. For 105 or more rows, Dan Black, a performance improvement engineer at IBM, developed this gem ...

set @last=-1 ;
CREATE TEMPORARY TABLE v(gap varbinary(30) PRIMARY KEY, next int unsigned)
  SELECT IF(@last=-1 OR, 'Exists', CONCAT(@last,'-',id-1)) as gap, as next
  FROM target_table AS a
  ORDER BY id;
SELECT gap FROM v where gap!='Exists';

On a modest laptop it found 8,000 gaps in a 2-million-row table in 0.01 sec. How does it do that? CREATE TABLE...IGNORE...SELECT... silently drops all dupes, so it flies through target_table so long as it can do the whole operation without swapping.

Auto_increment gaps

Auto_increment doesn't guarantee sequentiality, but sometimes—e.g., when you're initialising a production lookup table with predefined values—it's necessary to tighten up a table's auto_increment sequence.

Until someone figures out how to adapt Dan's solution to this problem, a simple method assuming table tbl with id int unsigned primary key auto_increment: drop the auto_increment primary key, set all id values null, then add the auto_increment primary key back in, whereupon MySQL will autofill the column sequentially ...

alter table tbl modify id int unsigned, drop primary key;
update tbl set id=null;
alter table tbl add primary key(id), modify id int unsigned auto_increment;

Note that you have to remove the auto_increment attribute before dropping the primary key, and restore the primary key before restoring the auto_increment attribute.

This won't do, though, if auto_increment values need to be ordered by another column value. To order an auto_increment ID on column othercol ...

alter table tbl modify id int unsigned, drop primary key;
set @count=0;
update tbl set id=(@count:=@count+1) order by othercol;
alter table tbl add primary key(id), modify id int unsigned auto_increment;

Return to the Artful Common Queries page