День добрый всем!Вопросик вот такой, кто знает ответ, подскажите пожалуйста.
Имеем таблицу с полем id и свойством autoincrement
в поле забиты значения
1
2
3
4
10Как запросом отловить первый свободный, ранее используемый id, то есть 5?
Просьба, вопросов типа (зачем это нужно), не задавать.
С Уважением Дмитрий.
держать таблицу свободных идентификаторов для слаборазряженных БД и диапазоны - для сильноразряженных. Иное на больших массивах данных будет жестко тормозить. А так можно будет даже транзакции строить.
>
>держать таблицу свободных идентификаторов для слаборазряженных БД и диапазоны - для сильноразряженных.
>Иное на больших массивах данных будет жестко тормозить. А так можно
>будет даже транзакции строить.Думаю вы немного не поняли суть. У нас нет возможности отслеживать, у нас есть уже готовая таблица с заполненными данными, и необходимо запросом найти это значение.
С отслеживанием все было бы элементарно.
>Думаю вы немного не поняли суть. У нас нет возможности отслеживать, у
>нас есть уже готовая таблица с заполненными данными, и необходимо запросом
>найти это значение.Боюсь, что дешево - никак. Тем более, что в БД данные организованы в множества, а не в списки. Списки через ид - это уже поверх множеств.
>>Думаю вы немного не поняли суть. У нас нет возможности отслеживать, у
>>нас есть уже готовая таблица с заполненными данными, и необходимо запросом
>>найти это значение.
>
>Боюсь, что дешево - никак. Тем более, что в БД данные организованы
>в множества, а не в списки. Списки через ид - это
>уже поверх множеств.Понятно. Но все же я не упоминал о том, что нужно легкое изящное решение, решение нужно любое, и сложное тоже, просто вопрос не в легкости решения, а в достижении решения вопроса любыми средствами.
>[оверквотинг удален]
>>>нас есть уже готовая таблица с заполненными данными, и необходимо запросом
>>>найти это значение.
>>
>>Боюсь, что дешево - никак. Тем более, что в БД данные организованы
>>в множества, а не в списки. Списки через ид - это
>>уже поверх множеств.
>
>Понятно. Но все же я не упоминал о том, что нужно легкое
>изящное решение, решение нужно любое, и сложное тоже, просто вопрос не
>в легкости решения, а в достижении решения вопроса любыми средствами.предложу первый пришедший в голову вариант )) типа деление отрезка пополам
и так есть ряд автоинкрементов из N целых чисел (ВОЗРАСТАЮЩИЙ ряд)
1) для начала находим Nmin и Nmax, также находим само N (в три запроса)
2) далее смотрим если (Nmax - Nmin + 1) = N - то у нас последовательность, следовательно
свободных номеров нет - берем N+1 или оставляем работу мускулу
3) делим ряд пополам (ну или почти пополам если коли-во N нечетное)
получаем два ряда: первый длинной M1=ЦЕЛОЕ(N/2), второй M2=N-M1 (M1 M2 количество элементов в рядах) - проверяем сначало M1 как в 2), если катит, то делим его, если нет, то переходим к M2.
4) нууу и когда M1(M2) достиают минимальной длины (1,2,3 элемента) делаем анализ и ищем свободное число (уже сами, как домашнее задание)PS при N=1000000 можно найти искомое за 18 шагов
>предложу первый пришедший в голову вариант )) типа деление отрезка пополамКстати, очень хорошее решение.
>Имеем таблицу с полем id и свойством autoincrement
>
>в поле забиты значения
>
>1 2 3 4 10
>
>Как запросом отловить первый свободный, ранее используемый id, то есть 5?А если тупо "select id from таблица order by id" - как-то так? Потом ловить результаты этого запроса, пока следующий на единицу больше предыдущего. Как только это условие нарушится, так сразу и нашли то, что нам нужно.
Если поле id индексировано (а чаще всего это так), то "order by" не должен привести к особым тормозам.
>[оверквотинг удален]
>>
>>Как запросом отловить первый свободный, ранее используемый id, то есть 5?
>
>А если тупо "select id from таблица order by id" - как-то
>так? Потом ловить результаты этого запроса, пока следующий на единицу больше
>предыдущего. Как только это условие нарушится, так сразу и нашли то,
>что нам нужно.
>
>Если поле id индексировано (а чаще всего это так), то "order by"
>не должен привести к особым тормозам.да ты просто гений!!!
а если записей 500000000? и каждая 4 байта?
>да ты просто гений!!!Я в курсе :-)
>а если записей 500000000? и каждая 4 байта?
А вот про "если" лучше послушаем того, кто задачу поставил. Какие там у него объёмы?
>>да ты просто гений!!!
>
>Я в курсе :-)
>
>>а если записей 500000000? и каждая 4 байта?
>
>А вот про "если" лучше послушаем того, кто задачу поставил. Какие там
>у него объёмы?я дамаю если у чела был инкремент максимальным размером байт такой проблемы бы не встало ...
>Имеем таблицу с полем id и свойством autoincrement
>
>в поле забиты значения
>
>1 2 3 4 10
>
>Как запросом отловить первый свободный, ранее используемый id, то есть 5?Вот на суд общественности решение задачи одним запросом:
select t1.id+1 from таблица as t1 left join таблица as t2 on t1.id=t2.id-1 group by t1.id having count(t2.id)=0 limit 1;
ХЗ, что тут насчёт скорострельности на больших таблицах.
>[оверквотинг удален]
>>1 2 3 4 10
>>
>>Как запросом отловить первый свободный, ранее используемый id, то есть 5?
>
>Вот на суд общественности решение задачи одним запросом:
>
>select t1.id+1 from таблица as t1 left join таблица as t2 on
>t1.id=t2.id-1 group by t1.id having count(t2.id)=0 limit 1;
>
>ХЗ, что тут насчёт скорострельности на больших таблицах.Сорри что отлучился от общения.
Вопрос ставился не обращая внимания на оптимизацию, а на само решение вопроса.
То есть этот вопрос из тестового задания при приеме на работу, там их было 7, я все решил кроме этой задачи, она меня в тупик поставила :)
По этому я решил поинтересоваться как более опытные люди решат ее.
>По этому я решил поинтересоваться как более опытные люди решат ее.Более опытные люди решают реальные задачи, а не подобным ананизмом занимаются. На собеседовании в голову должно сразу прийти два варианта - с последовательной выборкой и left join, для второго случая обязательно сказать что нужно посмотреть explain, прежде чем выполнять. Все.
>С Уважением Дмитрий.По простому взять (множество от min(id) до max(id)) minus (select id from table) получим свободные id. Как взять множество от min(id) до max(id) я ч.г. не помню, но пример был на прошлой работе.
> Как взять множество от min(id) до max(id)
>я ч.г. не помню, но пример был на прошлой работе.select cast(concat(a.x,b.x,c.x,d.x,e.x) as unsigned) as id from (select id as x from test ) a, (select id as x from test) b, (select id as x from test) c, (select id as x from test) d, (select id as x from test) e where id >= min_id and id <= max_id;
Для 5 знакомест где test:
id
0
1
2
3
4
5
6
7
8
9
Фигня вариант, программисты подсказали лучше.
select min(a.id) from (select id+1 as id from test union select id as id from test) a where a.id not in (select id from test);
Ещё проще select min(id+1) from test a where id+1 not in (select id from test);
>Ещё проще select min(id+1) from test a where id+1 not in (select
>id from test);Одна слабость. Если id=1 отсутствует = то он не будет выдан.
Хорошая возможность убить СУБД на среднем объеме строк и частой вставке.
В один запрос (поле free_first_id - искомое значение):select (cc + 1) as free_first_id, cc, id, id - cc from ( select @d as cc, @d:=id, id from table, (select @d:=0) as t0 order by id ) as t1 where id - cc >1 LIMIT 1;