Нахождение "дыр" в нумерации

После удаления записи в таблице базы данных, автоинкрементное id освобождается и уже никогда не будет использовано.

+-- --+-------------------+------------+-------------+
| id  | name              | date       | origin      |
+---- +-------------------+------------+-------------+
| 1   | housefly          | 2001-09-10 | kitchen     |
| 3   | grasshopper       | 2001-09-10 | front yard  |
| 4   | stink bug         | 2001-09-10 | front yard  |
| 5   | cabbage butterfly | 2001-09-10 | garden      |
| 6   | ant               | 2001-09-10 | back yard   |
| 9   | cricket           | 2001-09-11 | basement    |
| 10  | moth              | 2001-09-14 | windowsill  |
+----+--------------------+------------+-------------+

Это сделано специально для обеспечения уникальности операций. Например, при решении вопроса синхронизации в распределённых базах данных.

На самом деле, повторная нумерация последовательности может создать серьезные проблемы. Например, нельзя переупорядочивать столбец значений последовательности, на который ссылается другая таблица. Изменение нумерации разрушает связь значений со значениями в другой таблице, делая невозможным корректное сопоставление записей двух таблиц.

Причины, по которым стремятся к повторному упорядочиванию:

• Эстетика. Иногда хочется перенумеровать столбец из эстетических соображения. Неразрывные последовательности выглядят более красиво, чем последовательности с дырами. Если ваша причина именно такова, я вряд ли смогу вас переубедить. Тем не менее, это не самая убедительная причина.

• Производительность. Стремление к повторному упорядочиванию может объясняться мнением о том, что удаление пробелов делает столбец последовательности более компактным и позволяет запросам MySQL выполняться быстрее. Но это неверно. Наличие или отсутствие пробелов не беспокоит MySQL, и перенумерация столбца AUTO_INCREMENT не увеличивает производительность. Можно даже сказать, что повторное упорядочивание отрицательно влияет на производительность в том смысле, что таблица остается заблокированной на время выполнения операции, которая может быть достаточно долгой для больших таблиц. Другие клиенты могут в это время читать данные из таблицы, и если они захотят вставить новые строки, то придется подождать завершения операции.

• Нехватка номеров. Верхняя граница значений столбца последовательности определяется типом данных столбца. Если последовательность AUTO_INCREMENT приближается к верхней границе, перенумерация освобождает значения верхушки последовательности. Это разумная причина повторного упорядочивания столбца, но все же во многих случаях и в этом нет необходимости. Можно расширить диапазон значений столбца для увеличения его верхней границы без изменения хранимых значений.

И все же...

Как найти первую отсутствующую запись?

Варианты перебора применимы, но их не рассматриваем. На маленьких объемах данных эти решения работают, но при большом количестве записей они либо ресурсоемки, либо продолжительны во времени, либо и то и другое.

Нашел такое решение:

SELECT (`table`.`id`+1) as `empty_id`
  FROM `table`
 WHERE (
         SELECT 1
           FROM `table` as `st`
          WHERE `st`.`id` = (`table`.`id` + 1)
       ) IS NULL
ORDER BY `table`.`id`
LIMIT 1

⚠️ Но следует помнить, что при большом количестве одновременных запросов в БД может получиться накладка, если два процесса получат один и тот же empty_id.

Обсуждение темы на habr