SQLinfo.ru - Все о MySQL

Форум пользователей MySQL

Задавайте вопросы, мы ответим

Вы не зашли.

#1 19.01.2017 16:24:09

gif-t
Завсегдатай
Зарегистрирован: 08.08.2011
Сообщений: 74

Выборка минимального отсутсвующего индекса

CREATE TABLE `tbl` (
  `id` int(11) unsigned NOT NULL,
   ...
) ENGINE=InnoDB DEFAULT CHARSET=latin1;
 

Таблица заполнена числами, нужно найти минимальное отсутствующее в ней.
Примеры:

0,1,2,4,5,9 - минимальное свободное: 3
4,1 - минимальное: 0
10,0,2 - минимальное: 1

Сейчас делаю полную выборку с сортировкой, и в приложении перебираю индексы:

int id = indexes[0];
for(size_t i=0;i<indexes.size();++i) {
    if(id!=indexes[i]) break;
    ++id;
}

Можно это дело оптимизировать до одного запроса, без полной выборки всей таблицы и последующей обработки?

Неактивен

 

#2 19.01.2017 16:27:23

deadka
Администратор
Зарегистрирован: 14.11.2007
Сообщений: 2012

Re: Выборка минимального отсутсвующего индекса

Создайте проиндексированную табличку t2 с числами от 1 до максимального и сделайте LEFT JOIN Вашей таблицы WHERE t2.num IS NULL limit 1;


Зеленый свет для слабаков, долги отдают только трусы, тру гики работают только в консоли...

Неактивен

 

#3 19.01.2017 16:30:20

gif-t
Завсегдатай
Зарегистрирован: 08.08.2011
Сообщений: 74

Re: Выборка минимального отсутсвующего индекса

А как создать заполненную таблицу?

Неактивен

 

#4 19.01.2017 16:32:50

deadka
Администратор
Зарегистрирован: 14.11.2007
Сообщений: 2012

Re: Выборка минимального отсутсвующего индекса

Ну первое что идет в голову - таблицу  с автоинкрементнрым полем сделать, вставить туда одно значение.
Далее нужное количество раз

insert into t select * from t;


Зеленый свет для слабаков, долги отдают только трусы, тру гики работают только в консоли...

Неактивен

 

#5 19.01.2017 16:47:02

gif-t
Завсегдатай
Зарегистрирован: 08.08.2011
Сообщений: 74

Re: Выборка минимального отсутсвующего индекса

Одним запросом сложновато будет.
Вот нашел на просторах:

SELECT t1.id+1 AS Missing
FROM tbl AS t1
LEFT JOIN tbl AS t2 ON t1.id+1 = t2.id
WHERE t2.id IS NULL
ORDER BY t1.id LIMIT 1;

Работает, но не соображу каким образом

Отредактированно gif-t (19.01.2017 16:48:31)

Неактивен

 

#6 19.01.2017 16:55:39

vasya
Архат
MySQL Authorized Developer
Откуда: Орел
Зарегистрирован: 07.03.2007
Сообщений: 5041

Re: Выборка минимального отсутсвующего индекса

не работает, попробуйте для случая:
4,1 - минимальное: 0

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

Неактивен

 

#7 19.01.2017 16:59:10

gif-t
Завсегдатай
Зарегистрирован: 08.08.2011
Сообщений: 74

Re: Выборка минимального отсутсвующего индекса

Да, берутся все числа, увеличенные на 1. Т.е. поиск начинается с минимального  в таблице.

Неактивен

 

#8 19.01.2017 17:00:46

gif-t
Завсегдатай
Зарегистрирован: 08.08.2011
Сообщений: 74

Re: Выборка минимального отсутсвующего индекса

vasya, совет правильный, только ума не приложу, как сделать одним запросом?

Неактивен

 

#9 19.01.2017 17:07:34

vasya
Архат
MySQL Authorized Developer
Откуда: Орел
Зарегистрирован: 07.03.2007
Сообщений: 5041

Re: Выборка минимального отсутсвующего индекса

select t2.num from t2 LEFT JOIN `Ваша таблица` x on t2.num=x.id WHERE t2.num IS NULL order by t2.num limit 1;


где t2 это вспомогательная постоянная проиндексированная табличка t2 с числами от 0 до максимально необходимого. Создается один раз.

Неактивен

 

#10 19.01.2017 17:09:35

gif-t
Завсегдатай
Зарегистрирован: 08.08.2011
Сообщений: 74

Re: Выборка минимального отсутсвующего индекса

Мне кажется если union'ом прилепить к выборке 0, будет самый оптимальный рабочий вариант...

Неактивен

 

#11 19.01.2017 17:10:22

gif-t
Завсегдатай
Зарегистрирован: 08.08.2011
Сообщений: 74

Re: Выборка минимального отсутсвующего индекса

Спасибо, завтра попробую

Неактивен

 

#12 20.01.2017 09:17:52

gif-t
Завсегдатай
Зарегистрирован: 08.08.2011
Сообщений: 74

Re: Выборка минимального отсутсвующего индекса

Оцените пожалуйста данный запросик:

SELECT `Missing` FROM (SELECT id+1 AS Missing
FROM `tbl`
UNION
SELECT 0 AS id) AS t1
LEFT JOIN `tbl` AS t2 ON t1.Missing = t2.id
WHERE t2.id IS NULL
ORDER BY t1.Missing LIMIT 1;

Здесь выбираются все id, увеличенные на 1, и добавляется еще 0. Т.е. на таблице
10,3,4,5 будет 4,5,6,11,0. отсутствующие: 0,11
0,2,3,4 будет 1,3,4,5,0. отсутствующие: 1,5
1,2,6,4 будет 2,3,5,7,0. отсутствующие: 0,3,5,7
4,1 будет 5,2,0. отсутствующие: 0,2,5
Запрос LEFT JOIN'ом выберет все следующие от присутствующих отсутствующие числа. Далее сортировочка и выборка первого из них.

Неактивен

 

#13 20.01.2017 10:02:50

vasya
Архат
MySQL Authorized Developer
Откуда: Орел
Зарегистрирован: 07.03.2007
Сообщений: 5041

Re: Выборка минимального отсутсвующего индекса

оценить с какой позиции?
если с т.з. производительности, то вариант, предложенный deadka, лучше

Неактивен

 

#14 20.01.2017 10:43:16

gif-t
Завсегдатай
Зарегистрирован: 08.08.2011
Сообщений: 74

Re: Выборка минимального отсутсвующего индекса

Да я вот думаю, что-то он действительно не шустрый. Но насчет отдельной теблицы я так и не понял. Я же не могу предсказать какое может быть максимальное значение? Там же могут быть миллионы. Не брать же размерность int'а!? И потом если я сгенерирую таблицу на 4294967296 строк, это, мне кажется, будет еще медленнее работать...
Я вижу еще 2 возможных решения:
- проход в процедуре.
- сделать доп. столбец, в котором хранить значения на 1 больше, и применить этот же алгоритм. Как я понял, затык именно в инкременте всех значений?

Неактивен

 

#15 20.01.2017 13:53:16

vasya
Архат
MySQL Authorized Developer
Откуда: Орел
Зарегистрирован: 07.03.2007
Сообщений: 5041

Re: Выборка минимального отсутсвующего индекса

табличка на размерность int конечно не нужна
есть разные решения, например, отдельно хранить и вычислять нужное значение при изменении данных
для чего вообще нужна эта задача?

Неактивен

 

Board footer

Работает на PunBB
© Copyright 2002–2008 Rickard Andersson