Изобретая велосипед или поиск отсутствующего значения ID в MySQL таблице

Разработчики и администраторы систем основанных на sql данных, наверняка, сталкивались с задачей — получить отсутствующее (пропущенное) значение в ряде id записей таблицы. Например номер договора, порядковый номер документа, телефонный номер, айпи-адрес и т.п. При работе с MySQL эта тривиальная задача непропорционально ресурсоемка.

Например, у нас есть пул внутренних телефонных номеров компании от 2001 до 2999 и таблица с выданными из них номерами для сотрудников:

• t1.phone
• 2001
• 2002
• 2003
• 2004
• 2005
• 2009
• 2015
• 2016

Нам нужно найти первое свободное значение (в данном случае 2006) чтобы выделить очередной номер очередному сотруднику. Если свободных значений нет, то нужно выделить следующий из диапазона. Знакомая задача? Решения, которыми изобилует интернет, сводятся к двум принципам:

1) Делать перебор в цикле: например в SQL создать курсор CUR i+1 c 2001 до 2999 и делать запросы

SELECT t1.phone FROM t1 WHERE phone = i

до пустого значения. Цикл можно делать и любым внешним софтом, смысл принципа не меняется.

2) Второй принцип, использовать LEFT (OUTER) JOIN последовательности 2001...2009 с таблицей t1 (WHERE t1.phone IS NULL конечно же), либо таблицы t1 с собой же со сдвигом на шаг:

SELECT MIN(t1.phone)+1 FROM t1 LEFT JOIN t1 AS diff ON (t1.phone = diff.phone+1) WHERE diff.phone IS NULL

Еще один вариант с использованием IN

SELECT ... WHERE phone NOT IN (....)

вообще не рассматриваю из-за громоздкости.

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

Я же захотел решить задачу быстро, не напрягая сервер, и, желательно, в один запрос. В один, не в один, но вот что получилось:

	/*выбираю граничные значения*/
	select 2000,2999 into @num,@maxid;

	select min(f.id) /* внешний селект дополнительный для "очистки" результата union */
	from
		(select s.num, min(s.num) /* первое расхождение рядов */ id
		from (
				select
					/* формирую ряд, в данном случае арифм.прогрессия, но может быть с любым шагом, или вычисляемым */
					@num:=@num+1 num,
					/* выбираю занятые значения */
					r.id 
				from t1 as r
				order by id
			) as s
		where 
			/* применяю условие расхождения рядов */ s.id != s.num /* причем ряды разойдутся и расхождение будет постоянным, поэтому во внешнем селекте использую только первое расхождение - min */
		/* если расхождения небыло, добавляю еще одно возможное значение из диапазона граничных значений либо null, если значения закончились */
		union
		select if(@num+1<@maxid,@num+1,null) num, if(@num+1<@maxid,@num+1,null) 
		) as f
	where /* очищаю лишние результаты union */
		f.id is not null
	limit 1;

По сравнению с джойнами простые селекты выполняются в сотни раз быстрее.

Понятное дело, что такое решение известно, но в интернетах, как ни странно, с наскока его найти не удалось, вот и хочу поделиться эти простым «велосипедом».

Автор: realkazan

Источник