The OpenNET Project / Index page

[ новости /+++ | форум | теги | ]

форумы  помощь  поиск  регистрация  майллист  вход/выход  слежка  RSS
"Как отловить первый свободный id с autoincrement"
Вариант для распечатки  
Пред. тема | След. тема 
Форумы Программирование под UNIX (Public)
Изначальное сообщение [ Отслеживать ]

"Как отловить первый свободный id с autoincrement"  +/
Сообщение от svfolder email(ok) on 13-Дек-09, 15:34 
День добрый всем!

Вопросик вот такой, кто знает ответ, подскажите пожалуйста.

Имеем таблицу с полем id и свойством autoincrement

в поле забиты значения

1
2
3
4
10

Как запросом отловить первый свободный, ранее используемый id, то есть 5?

Просьба, вопросов типа (зачем это нужно), не задавать.

С Уважением Дмитрий.

Высказать мнение | Ответить | Правка | Cообщить модератору

Оглавление

Сообщения по теме [Сортировка по времени | RSS]


1. "Как отловить первый свободный id с autoincrement"  +/
Сообщение от BigHO on 13-Дек-09, 15:53 

держать таблицу свободных идентификаторов для слаборазряженных БД и диапазоны - для сильноразряженных. Иное на больших массивах данных будет жестко тормозить. А так можно будет даже транзакции строить.

Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

2. "Как отловить первый свободный id с autoincrement"  +/
Сообщение от svfolder email(ok) on 13-Дек-09, 23:01 
>
>держать таблицу свободных идентификаторов для слаборазряженных БД и диапазоны - для сильноразряженных.
>Иное на больших массивах данных будет жестко тормозить. А так можно
>будет даже транзакции строить.

Думаю вы немного не поняли суть. У нас нет возможности отслеживать, у нас есть уже готовая таблица с заполненными данными, и необходимо запросом найти это значение.

С отслеживанием все было бы элементарно.

Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

3. "Как отловить первый свободный id с autoincrement"  +/
Сообщение от DeadLoco (ok) on 13-Дек-09, 23:46 
>Думаю вы немного не поняли суть. У нас нет возможности отслеживать, у
>нас есть уже готовая таблица с заполненными данными, и необходимо запросом
>найти это значение.

Боюсь, что дешево - никак. Тем более, что в БД данные организованы в множества, а не в списки. Списки через ид - это уже поверх множеств.

Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

4. "Как отловить первый свободный id с autoincrement"  +/
Сообщение от svfolder email(ok) on 14-Дек-09, 07:01 
>>Думаю вы немного не поняли суть. У нас нет возможности отслеживать, у
>>нас есть уже готовая таблица с заполненными данными, и необходимо запросом
>>найти это значение.
>
>Боюсь, что дешево - никак. Тем более, что в БД данные организованы
>в множества, а не в списки. Списки через ид - это
>уже поверх множеств.

Понятно. Но все же я не упоминал о том, что нужно легкое изящное решение, решение нужно любое, и сложное тоже, просто вопрос не в легкости решения, а в достижении решения вопроса любыми средствами.

Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

5. "Как отловить первый свободный id с autoincrement"  +/
Сообщение от Pahanivo email(ok) on 14-Дек-09, 10:03 
>[оверквотинг удален]
>>>нас есть уже готовая таблица с заполненными данными, и необходимо запросом
>>>найти это значение.
>>
>>Боюсь, что дешево - никак. Тем более, что в БД данные организованы
>>в множества, а не в списки. Списки через ид - это
>>уже поверх множеств.
>
>Понятно. Но все же я не упоминал о том, что нужно легкое
>изящное решение, решение нужно любое, и сложное тоже, просто вопрос не
>в легкости решения, а в достижении решения вопроса любыми средствами.

предложу первый пришедший в голову вариант )) типа деление отрезка пополам
и так есть ряд автоинкрементов из 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 шагов

Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

13. "Как отловить первый свободный id с autoincrement"  +/
Сообщение от DeadLoco (ok) on 24-Дек-09, 19:34 
>предложу первый пришедший в голову вариант )) типа деление отрезка пополам

Кстати, очень хорошее решение.

Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

6. "Как отловить первый свободный id с autoincrement"  +/
Сообщение от XAnder (ok) on 14-Дек-09, 10:27 
>Имеем таблицу с полем id и свойством autoincrement
>
>в поле забиты значения
>
>1 2 3 4 10
>
>Как запросом отловить первый свободный, ранее используемый id, то есть 5?

А если тупо "select id from таблица order by id" - как-то так? Потом ловить результаты этого запроса, пока следующий на единицу больше предыдущего. Как только это условие нарушится, так сразу и нашли то, что нам нужно.

Если поле id индексировано (а чаще всего это так), то "order by" не должен привести к особым тормозам.

Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

7. "Как отловить первый свободный id с autoincrement"  +/
Сообщение от Pahanivo email(ok) on 14-Дек-09, 10:35 
>[оверквотинг удален]
>>
>>Как запросом отловить первый свободный, ранее используемый id, то есть 5?
>
>А если тупо "select id from таблица order by id" - как-то
>так? Потом ловить результаты этого запроса, пока следующий на единицу больше
>предыдущего. Как только это условие нарушится, так сразу и нашли то,
>что нам нужно.
>
>Если поле id индексировано (а чаще всего это так), то "order by"
>не должен привести к особым тормозам.

да ты просто гений!!!
а если записей 500000000?  и каждая 4 байта?

Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

8. "Как отловить первый свободный id с autoincrement"  +/
Сообщение от XAnder (ok) on 14-Дек-09, 10:39 
>да ты просто гений!!!

Я в курсе :-)

>а если записей 500000000?  и каждая 4 байта?

А вот про "если" лучше послушаем того, кто задачу поставил. Какие там у него объёмы?

Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

9. "Как отловить первый свободный id с autoincrement"  +/
Сообщение от Pahanivo email(ok) on 14-Дек-09, 10:57 
>>да ты просто гений!!!
>
>Я в курсе :-)
>
>>а если записей 500000000?  и каждая 4 байта?
>
>А вот про "если" лучше послушаем того, кто задачу поставил. Какие там
>у него объёмы?

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

Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

10. "Как отловить первый свободный id с autoincrement"  +/
Сообщение от XAnder (ok) on 14-Дек-09, 13:58 
>Имеем таблицу с полем 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;

ХЗ, что тут насчёт скорострельности на больших таблицах.

Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

11. "Как отловить первый свободный id с autoincrement"  +/
Сообщение от svfolder email(ok) on 17-Дек-09, 23:02 
>[оверквотинг удален]
>>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, я все решил кроме этой задачи, она меня в тупик поставила :)
По этому я решил поинтересоваться как более опытные люди решат ее.

Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

12. "Как отловить первый свободный id с autoincrement"  +/
Сообщение от аноним on 18-Дек-09, 17:21 
>По этому я решил поинтересоваться как более опытные люди решат ее.

Более опытные люди решают реальные задачи, а не подобным ананизмом занимаются. На собеседовании в голову должно сразу прийти два варианта - с последовательной выборкой и left join, для второго случая обязательно сказать что нужно посмотреть explain, прежде чем выполнять. Все.

Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

14. "Как отловить первый свободный id с autoincrement"  +/
Сообщение от tux2002 email(ok) on 28-Дек-09, 15:36 
>С Уважением Дмитрий.

По простому взять (множество от min(id) до max(id)) minus (select id from table) получим свободные id. Как взять множество от min(id) до max(id) я ч.г. не помню, но пример был на прошлой работе.


Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

15. "Как отловить первый свободный id с autoincrement"  +/
Сообщение от tux2002 email(ok) on 28-Дек-09, 15:55 
> Как взять множество от 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

Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

16. "Как отловить первый свободный id с autoincrement"  +/
Сообщение от tux2002 email(ok) on 28-Дек-09, 16:52 
Фигня вариант, программисты подсказали лучше.
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);


Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

17. "Как отловить первый свободный id с autoincrement"  +/
Сообщение от tux2002 email(ok) on 29-Дек-09, 12:43 
Ещё проще select min(id+1) from test a where id+1 not in (select id from test);

Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

18. "Как отловить первый свободный id с autoincrement"  +/
Сообщение от Тимофей (??) on 06-Фев-10, 16:20 
>Ещё проще select min(id+1) from test a where id+1 not in (select
>id from test);

Одна слабость. Если id=1 отсутствует = то он не будет выдан.

Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

19. "Как отловить первый свободный id с autoincrement"  +/
Сообщение от BigHo on 06-Фев-10, 16:53 
Хорошая возможность убить СУБД на среднем объеме строк и частой вставке.
Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

20. "Как отловить первый свободный id с autoincrement"  +/
Сообщение от Аноним (??) on 07-Фев-10, 14:12 
В один запрос (поле 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;

Высказать мнение | Ответить | Правка | ^ | Наверх | Cообщить модератору

Архив | Удалить

Индекс форумов | Темы | Пред. тема | След. тема




Партнёры:
PostgresPro
Inferno Solutions
Hosting by Hoster.ru
Хостинг:

Закладки на сайте
Проследить за страницей
Created 1996-2024 by Maxim Chirkov
Добавить, Поддержать, Вебмастеру