@realkazan30 июн 2014 в 08:29

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

2 мин

36K

MySQL * Программирование *

Из песочницы

Recovery Mode

Комментарии 37

@itforge 30 июн 2014 в 08:49

Если честно, не понял ваш алгоритм, вернее, разбираться лень.

У меня такая мысль возникла. Можно что-то типа бинарного поиска сделать, если индекс на колонку есть. Например, зная минимиальный и максимальный id, делаем выборку count(*) where id < (min_id + max_id)/2 и, сравнивая count(*) и ожидаемое кол-во понимаем, есть ли в «младшей» половине ID'ов дырки. Далее делим нужную половину опять попалам и т.д.

Для миллиона записей в худшем случае нужно сделать 20 выборок (log_(2)_1000000)
А в вашем алго сколько выборок сделается в худшем случае?

@realkazan 30 июн 2014 в 09:04

Да, была у меня и такая мысль. Т.к. нам известна формула последовательности/ряда и мы можем вычислить количество и сумму значений в любом диапазоне значений, и по кол-ву значений половинным делением найти диапазон где есть только одно отсутствующее значение и вычислить его сумму.
Но это итерационный метод, просто с меньшим кол-вом итераций. Но по сути — преребор сумм значений. У меня же нет «худшего случая» всегда делается только одна выборка, а потом фильтруются результаты. Проверял на таблицах порядка миллиона записей, итерационно или джойн — все равно занимали 20-30 секунд, мой запрос 0,3 секунды.

@kolu4iy 30 июн 2014 в 10:02

При наличии правильного индекса, достаточном количестве памяти и количественном ограничении выборки (id от 2000 до 2099) не должно быть 30 секунд, никак. Что-то написано неправильно.
Курсор в принципе медленная штука, потому его надо использовать, только когда не помогает ничего.
А так — лично я вижу всего две выборки, в случае, когда оптимизатор не справляется с одной.

@realkazan 30 июн 2014 в 10:10

Проверял на таблицах порядка миллиона записей
Список из тысячи телефонов — пример

@kolu4iy 30 июн 2014 в 10:28

select count(*) from search_sites;

+----------+
| count(*) |
+----------+
| 5985543 |
+----------+
1 row in set (0.00 sec)

select a.sid from search_sites as a left join search_sites as b on a.sid+1=b.sid where a.sid is not null and a.sid between 300 and 700;

…
1604 rows in set (0.01 sec)

describe select a.sid from search_sites as a left join search_sites as b on a.sid+1=b.sid where a.sid is not null and a.sid between 300 and 700;

+------+-------------+-------+-------+---------------+-------+---------+------+------+--------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+------+-------------+-------+-------+---------------+-------+---------+------+------+--------------------------+
| 1 | SIMPLE | a | range | index,sid | index | 8 | NULL | 801 | Using where; Using index |
| 1 | SIMPLE | b | ref | index,sid | index | 8 | func | 1 | Using where; Using index |
+------+-------------+-------+-------+---------------+-------+---------+------+------+--------------------------+
2 rows in set (0.00 sec)

Ищите индексы, коллега…

@realkazan 30 июн 2014 в 11:16

Индексы могут быть, а могут и не быть, и данные из ряда могут быть в разных форматах.

Например есть таблицы занятых айпи-адресов:

user_ip
+------+-------------+
| user_id | ip |
+------+-------------+
| 1 | 10.10.12.34 |
| 2 | 10.10.12.7 |
| 3 | 10.10.12.12 |
+------+-------------+

device_ip
user_ip
+------+-------------+
| dev_id | ip |
+------+-------------+
| 1 | 10.10.12.1 |
| 2 | 10.10.12.2 |
| 3 | 10.10.12.3 |
+------+-------------+

reserve_ip
+------+-------------+
| id | ip |
+------+-------------+
| 1 | 168430792 |
| 2 | 168430793 |
| 3 | 168430794 |
+------+-------------+

Нужно найти первый свободный айпи из подсети 10.10.12.0/24

Мой запрос найдет быстро, в один прием, без временных таблиц и прочего.

@kolu4iy 30 июн 2014 в 11:22

А если использовать вариант «индексов может не быть», то зачем SQL? И, тем более, зачем в разных форматах? Этот жеж микроскоп, не надо им махать.

@realkazan 30 июн 2014 в 11:30

Ситуации разные бывают. Например разными разработчиками в разное время писался разный софт, использующий по сути одни и те же данные для разных задач. В результате софт работает, а вот с данными — беда. Быстро реструктуризировать базу и переписать софт не представляется возможным, тк трудовые ресурсы ограничены, а проект высоконагружен 24/7. Но из-за того что несколько лет назад проектируя базу «не подумали о расширении», проект зашел в такой логический тупик и отъедает ресурсы на тривиальных операциях.

@youlose 30 июн 2014 в 08:50

Ответа не нашли потому что «искусственно придуманная сложность», а зачем дырки в idшниках затыкать?

@youlose 30 июн 2014 в 09:01

Прочитал про «пул телефонных номеров» ещё раз, надо было просто создать все записи для номеров и колонку assigned(типа кому назначено, а там уже foreign key или что там нужно), если она NULL — номер пустой и выбирается тогда всё одним простым запросом.

@realkazan 30 июн 2014 в 09:14

Понятное дело «просто создать все записи» пула — это изменить условия задачи. И если это было бы возможно, то конечно — хорошее решение. Но ситуации и системы бывают разные. В моем случае — «занятые значения» хранились даже не в одной таблице, а в нескольких, каждая использовалась своим внешним сервисом и быстро переделать архитектуру без изменения всех внешних обработчиков никак не представлялось возможным, а оптимизировать работу нужно было «уже вчера». Отсюда и родилось решение.

А пример с телефонными номерами в одной таблице — это только пример, для пояснения алгоритма.

@Azy 30 июн 2014 в 09:36

Не нужно удалять номер из пула когда он освобождается, а ставить ему флаг, например free=1
Далее делаем SELECT FROM… WHERE free=1 LIMIT 1
если не найден то делаем инсерт с NULL.

@realkazan 30 июн 2014 в 09:55

Ответил уже youlose чуть выше. Суть поста не в рассмотрении способов хранения данных, а в оптимизации решения поиска значений, если данные «таки уже хранятся именно так ». В уменьшении времени поиска и нагрузки на сервер,
Повторюсь — пример с телефонными номерами — только пример.

@PaulZi 30 июн 2014 в 09:59

Ещё можно однократно сделать табличку с одним столбцом и в качестве данных использовать последовательность чисел нужного диапазона. Ну а дальше легко найти пропуски с помощью LEFT JOIN.

@PaulZi 30 июн 2014 в 10:01

Ну а последовательность легко генерируется:

SET @v:=2000;
INSERT INTO `table` SET `id`=@v:=@v+1; /* повторить нужное кол-во раз */

@realkazan 30 июн 2014 в 10:05

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

@PaulZi 30 июн 2014 в 10:07

Если у вас есть данные по скорости выполнения запросов для сравнения, было бы интересно самому.

@realkazan 30 июн 2014 в 10:18

Зависит от конфигурации и мощности сервера, но для сравнения

При наличии в таблице t1 миллиона записей запрос

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

или, как вы предлагаете (в таблице pool — полная последовательность)

SELECT MIN(pool.phone) FROM pool LEFT JOIN t1 ON (pull.phone = t1.phone) WHERE t1.phone IS NULL

выполняется — 20-30 сек

мой запрос на той же базе и сервере — 0,3 сек

@robofox 30 июн 2014 в 13:45

А зачем MIN(pool.phone)? Конечно он будет выполняться уйму времени, ведь он пробегает все телефоны, затем ищет минимальный.
Если вместо этого сделать LIMIT 1 и добавить ORDER BY, запрос выполнится как раз за 0.3 сек, а может и быстрее. Попробуйте, интересно же.

SELECT pool.phone FROM pool LEFT JOIN t1 ON (pull.phone = t1.phone) WHERE t1.phone IS NULL ORDER BY t1.phone LIMIT 1

@realkazan 30 июн 2014 в 18:29

Что быстрее order или min/max? Будет зависеть от данных конечно, но мне кажется ордеру больше памяти потребуется. По логике то. Попробую померить

@robofox 30 июн 2014 в 19:49

Может быть индекса нет, и в этом все дело?

@zuborg 30 июн 2014 в 10:57

Есть ещё один метод, который Вы не упомянули: держать отдельную таблицу с «пропущеными» номерами. Тогда INSERT будет предельно краток — берем минимальный номер из нашей таблицы, а если она пустая — то создаем новый номер. На большом кол-ве INSERT-ов это выльется в ощутимую экономию ресурсов. Обновлять таблицу тоже можно в удобное время когда есть запас по ресурсу.

@realkazan 30 июн 2014 в 11:03

Т.е держать пул свободных номеров?

@orloffkirill 30 июн 2014 в 11:13

Вообще, мне кажется, что держать пул всех номеров — это правильно в вашем случае.
А, как уже ранее было сказано, иметь одно поле, типа client_id: либо пустое, либо с айдишником клиента. В таком случае ваша проблема не появляется.

НЛО прилетело и опубликовало эту надпись здесь

@zuborg 30 июн 2014 в 16:51

Грубо говоря, да.
Точнее — «дырок» в текущих распределенных номерах.
Вообще — даже не обязательно держать пул всех номеров — достаточно держать его заполненным в достаточной мере, чтобы хватило до следующего заполнения.

@eduard93 30 июн 2014 в 16:13

А нельзя сделать хранимую процедуру следующего вида?
1. Выбрать все номера из таблицы
2. Цикл по результатам запроса 1, начиная со второго элемента
2.а. Если предыдущий номер не равен текущий номер — 1, вернуть текущий номер

Получился бы один SELECT на этапе 1.

@realkazan 30 июн 2014 в 18:00

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

@potapuff 30 июн 2014 в 19:00

Разве в MySql нет MINUS? www.techonthenet.com/sql/minus.php

@realkazan 30 июн 2014 в 19:33

Minus нет, но подобное вычитание (запрос минус запрос) выполняется left join-ом

@Vapaamies 30 июн 2014 в 22:39

Поискал по фразе «аналитические функции MySQL» и сразу нашел нечто похожее. Поиск «дырок» аналитической функцией сходу не напишу, спать собираюсь.

@realkazan 1 июл 2014 в 09:05

Прекрасное решение подсказал в личке участник stepmex
Без всякого дополнительного построения нумерации и сравнений рядов, изящно решил задачу через (SELECT 1 .....) IS NULL
Великолепная находка, я считаю:

SELECT (`t1`.`phone`+1) as `empty_phone`
FROM `t1`
WHERE (
	SELECT 1 FROM `t1` as `st` WHERE `st`.`phone` = (`t1`.`phone` + 1)
) IS NULL
ORDER BY `t1`.`phone`
LIMIT 1

@PaulZi 2 июл 2014 в 11:25

Только искать этим запросом придётся по одному, т. к. если пропущено несколько номеров подряд, данный запрос при увеличении LIMIT выдаст только первый номер из «большой дырки». Тогда как с генерированным пулом можно выявить сразу все номера за один запрос.

@realkazan 2 июл 2014 в 12:22

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

@num != phone

— все последующие тоже будут не совпадать.
Единственное, надо бы проверить время выполнения на реальных (иногда кривых) данных. Т.к. здесь идет вложенный запрос к таблице, а у меня вложенность используется для сравнения уже выбранных данных в памяти.

@AlexeyP0708 22 авг 2019 в 07:07

Добавлю еще как вариант.В целях чтобы было.
Вычисляет все id которые не назначены.

DELIMITER //
DROP FUNCTION  IF EXISTS createRowEmptyId//
# вычисляет диапазон пропущенных id между before_id и after_id и возвращает строку для под запроса (union select id as alias;)
# аргумент alias назначает псевдоним колонке
# в глобальную переменную @prev устанавливается последний установленный id  по параметру after_id
CREATE FUNCTION `createRowEmptyId`(before_id INT, after_id INT,alias VARCHAR(25))
 RETURNS TEXT
 DETERMINISTIC
BEGIN
	DECLARE answer TEXT DEFAULT '';
	DECLARE count_ids INT DEFAULT 0;
    SET count_ids=after_id-before_id-1;
	WHILE count_ids>0 DO
		SET answer=CONCAT_WS(' ',answer,'UNION SELECT ',after_id-count_ids,' as ',alias);
		SET count_ids=count_ids-1;
	END WHILE;
	set @prev=after_id;
	RETURN answer;
END//
DELIMITER ; 
SET @prev=0;
# Основной Запрос
SELECT @select:= GROUP_CONCAT(DISTINCT createRowEmptyId(@prev,`id`) SEPARATOR ' ')  FROM  `test` ORDER BY `id` ASC ; 
# Подзапрос который сформирует таблицу несуществующих id
set @select=TRIM(@select); 
set @select=CONCAT_WS(' ',TRIM(LEADING 'UNION ' FROM @select),'ORDER BY `empty_id` ASC'); 
PREPARE stmt FROM @select;
EXECUTE stmt;
DROP FUNCTION createRowEmptyId

@AlexeyP0708 22 авг 2019 в 07:50

По существу если клиент сможет сам обработать и сгенерировать несуществующие id можно обойтись таким запросом

SET @prev=1;
SELECT @prev as `before_id`,`id` as `after_id`, `id`-@prev-1 as count_ids,  @prev:=`id`  FROM `test` ORDER BY `id` ASC

@nuclight 12 мар 2024 в 19:55

Для ряда БД еще можно использовать функции LEAD и LAG https://databasetips.net/2019/09/05/sql-3-ways-to-find-gaps-and-missing-values/

Зарегистрируйтесь на Хабре, чтобы оставить комментарий