Как стать автором
Поиск
Написать публикацию
Обновить

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

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

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

Для миллиона записей в худшем случае нужно сделать 20 выборок (log_(2)_1000000)
А в вашем алго сколько выборок сделается в худшем случае?
Всего голосов 7: ↑5 и ↓2+3
Да, была у меня и такая мысль. Т.к. нам известна формула последовательности/ряда и мы можем вычислить количество и сумму значений в любом диапазоне значений, и по кол-ву значений половинным делением найти диапазон где есть только одно отсутствующее значение и вычислить его сумму.
Но это итерационный метод, просто с меньшим кол-вом итераций. Но по сути — преребор сумм значений. У меня же нет «худшего случая» всегда делается только одна выборка, а потом фильтруются результаты. Проверял на таблицах порядка миллиона записей, итерационно или джойн — все равно занимали 20-30 секунд, мой запрос 0,3 секунды.
Комментарий пока не оценивали0
При наличии правильного индекса, достаточном количестве памяти и количественном ограничении выборки (id от 2000 до 2099) не должно быть 30 секунд, никак. Что-то написано неправильно.
Курсор в принципе медленная штука, потому его надо использовать, только когда не помогает ничего.
А так — лично я вижу всего две выборки, в случае, когда оптимизатор не справляется с одной.
Комментарий пока не оценивали0
Проверял на таблицах порядка миллиона записей
Список из тысячи телефонов — пример
Комментарий пока не оценивали0
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)

Ищите индексы, коллега…
Всего голосов 1: ↑1 и ↓0+1
Индексы могут быть, а могут и не быть, и данные из ряда могут быть в разных форматах.

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

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

Мой запрос найдет быстро, в один прием, без временных таблиц и прочего.
Комментарий пока не оценивали0
А если использовать вариант «индексов может не быть», то зачем SQL? И, тем более, зачем в разных форматах? Этот жеж микроскоп, не надо им махать.
Всего голосов 2: ↑2 и ↓0+2
Ситуации разные бывают. Например разными разработчиками в разное время писался разный софт, использующий по сути одни и те же данные для разных задач. В результате софт работает, а вот с данными — беда. Быстро реструктуризировать базу и переписать софт не представляется возможным, тк трудовые ресурсы ограничены, а проект высоконагружен 24/7. Но из-за того что несколько лет назад проектируя базу «не подумали о расширении», проект зашел в такой логический тупик и отъедает ресурсы на тривиальных операциях.
Комментарий пока не оценивали0
Ответа не нашли потому что «искусственно придуманная сложность», а зачем дырки в idшниках затыкать?
Всего голосов 5: ↑5 и ↓0+5
Прочитал про «пул телефонных номеров» ещё раз, надо было просто создать все записи для номеров и колонку assigned(типа кому назначено, а там уже foreign key или что там нужно), если она NULL — номер пустой и выбирается тогда всё одним простым запросом.
Всего голосов 4: ↑4 и ↓0+4
Понятное дело «просто создать все записи» пула — это изменить условия задачи. И если это было бы возможно, то конечно — хорошее решение. Но ситуации и системы бывают разные. В моем случае — «занятые значения» хранились даже не в одной таблице, а в нескольких, каждая использовалась своим внешним сервисом и быстро переделать архитектуру без изменения всех внешних обработчиков никак не представлялось возможным, а оптимизировать работу нужно было «уже вчера». Отсюда и родилось решение.

А пример с телефонными номерами в одной таблице — это только пример, для пояснения алгоритма.
Всего голосов 1: ↑1 и ↓0+1
Не нужно удалять номер из пула когда он освобождается, а ставить ему флаг, например free=1
Далее делаем SELECT FROM… WHERE free=1 LIMIT 1
если не найден то делаем инсерт с NULL.
Всего голосов 5: ↑5 и ↓0+5
Ответил уже youlose чуть выше. Суть поста не в рассмотрении способов хранения данных, а в оптимизации решения поиска значений, если данные «таки уже хранятся именно так ». В уменьшении времени поиска и нагрузки на сервер,
Повторюсь — пример с телефонными номерами — только пример.
Всего голосов 2: ↑1 и ↓10
Ещё можно однократно сделать табличку с одним столбцом и в качестве данных использовать последовательность чисел нужного диапазона. Ну а дальше легко найти пропуски с помощью LEFT JOIN.
Всего голосов 1: ↑1 и ↓0+1
Ну а последовательность легко генерируется:
SET @v:=2000;
INSERT INTO `table` SET `id`=@v:=@v+1; /* повторить нужное кол-во раз */

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

При наличии в таблице 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 сек

Комментарий пока не оценивали0
А зачем 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
Всего голосов 1: ↑1 и ↓0+1
Что быстрее order или min/max? Будет зависеть от данных конечно, но мне кажется ордеру больше памяти потребуется. По логике то. Попробую померить
Комментарий пока не оценивали0
Может быть индекса нет, и в этом все дело?
Комментарий пока не оценивали0
Есть ещё один метод, который Вы не упомянули: держать отдельную таблицу с «пропущеными» номерами. Тогда INSERT будет предельно краток — берем минимальный номер из нашей таблицы, а если она пустая — то создаем новый номер. На большом кол-ве INSERT-ов это выльется в ощутимую экономию ресурсов. Обновлять таблицу тоже можно в удобное время когда есть запас по ресурсу.
Всего голосов 1: ↑1 и ↓0+1
Т.е держать пул свободных номеров?
Комментарий пока не оценивали0
Вообще, мне кажется, что держать пул всех номеров — это правильно в вашем случае.
А, как уже ранее было сказано, иметь одно поле, типа client_id: либо пустое, либо с айдишником клиента. В таком случае ваша проблема не появляется.
Всего голосов 1: ↑1 и ↓0+1
НЛО прилетело и опубликовало эту надпись здесь
Грубо говоря, да.
Точнее — «дырок» в текущих распределенных номерах.
Вообще — даже не обязательно держать пул всех номеров — достаточно держать его заполненным в достаточной мере, чтобы хватило до следующего заполнения.
Комментарий пока не оценивали0
А нельзя сделать хранимую процедуру следующего вида?
1. Выбрать все номера из таблицы
2. Цикл по результатам запроса 1, начиная со второго элемента
2.а. Если предыдущий номер не равен текущий номер — 1, вернуть текущий номер

Получился бы один SELECT на этапе 1.
Комментарий пока не оценивали0
Самое забавное, что я именно такую функцию с курсором и переделал. Изначально задача и была решена хранимой процедурой с циклом внутри.
Комментарий пока не оценивали0
Minus нет, но подобное вычитание (запрос минус запрос) выполняется left join-ом
Комментарий пока не оценивали0
Поискал по фразе «аналитические функции MySQL» и сразу нашел нечто похожее. Поиск «дырок» аналитической функцией сходу не напишу, спать собираюсь.
Комментарий пока не оценивали0
Прекрасное решение подсказал в личке участник 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
Всего голосов 1: ↑1 и ↓0+1
Только искать этим запросом придётся по одному, т. к. если пропущено несколько номеров подряд, данный запрос при увеличении LIMIT выдаст только первый номер из «большой дырки». Тогда как с генерированным пулом можно выявить сразу все номера за один запрос.
Комментарий пока не оценивали0
Логично, если сравнивать два заполненных ряда, то все «пропуски» найдутся.
Просто зачастую вопрос звучит как «выбрать минимальное доступное значение».
Мой запрос тоже только одно минимальное значение сможет выдать, т.е. в нем, после первого же расхождения 
@num != phone
— все последующие тоже будут не совпадать.
Единственное, надо бы проверить время выполнения на реальных (иногда кривых) данных. Т.к. здесь идет вложенный запрос к таблице, а у меня вложенность используется для сравнения уже выбранных данных в памяти.
Комментарий пока не оценивали0
Добавлю еще как вариант.В целях чтобы было.
Вычисляет все 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

Комментарий пока не оценивали0
По существу если клиент сможет сам обработать и сгенерировать несуществующие 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
Комментарий пока не оценивали0
Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Публикации

Показать лучшие за всё время

Истории

Ваш аккаунт

Разделы

Информация

Услуги

Техническая поддержка
© 2006–2024, Habr