ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / MySQL [игнор отключен] [закрыт для гостей] / Поиск "дырки" одним запросом
13 сообщений из 13, страница 1 из 1
Поиск "дырки" одним запросом
    #39030379
Cyrax_02
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Cyrax_02
Участник
В таблице table имеется уникальное поле sid . В отличие от ключевых идентификаторов, это "плотные" идентификаторы, реализующие определённую логику предметной области. При удалении записей образуются "дырки", при добавлении - сначала закрываются имеющиеся "дырки", если таких нет - (max + 1). Т.е. в процессе обработки записей поле sid приблизительно равно числу записей (тем самым, исключается неконтролируемый рост этих sid ).

Задача такая:
Без вспомогательных таблиц и без коррелированных подзапросов одним или несколькими запросами получить самую первую "дырку" (с минимальным значением).

Факт отсутствия "дырок" определяется элементарно. Если дырок нет => (max + 1), если есть, выполняется этот самый волшебный запрос .

P.S. Лет 8 эдак назад, вроде, такую задачу решал. Сейчас буду вспоминать...
...
Рейтинг: 0 / 0
16.08.2015, 19:46:48
| Ответить | Цитировать | Написать  
Поиск "дырки" одним запросом
    #39030381
Добрый Э - Эх
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Добрый Э - Эх
Гость
Cyrax_02,

Левокоррелированное само объединение таблицы со двигом на единицу по сиду с последующим ордербаем и лимитом.
...
Рейтинг: 0 / 0
16.08.2015, 20:02:31
| Ответить | Цитировать | Написать  
Поиск "дырки" одним запросом
    #39030395
Cyrax_02
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Cyrax_02
Участник
авторЛевокоррелированное само объединение таблицы со двигом на единицу по сиду с последующим ордербаем и лимитом. Если вы имеете ввиду такой вариант:
Код: sql
1.
2.
3.
4.
SELECT (PREV.sid + 1) AS hole
FROM table AS PREV LEFT JOIN table AS NEXT ON (NEXT.id = PREV.id + 1)
WHERE (NEXT.id IS NULL)
ORDER BY PREV.id ASC LIMIT 1

то он даст неверный результат, если в таблице table отсутствуют первые 1 или более идентификаторов.

Впрочем для решения этой "проблемы" достаточно предварительно выполнить проверку наличия (sid = 1) и если есть, выполнять этот запрос (если нет, то первой дыркой и будет sid = 1 ).
...
Рейтинг: 0 / 0
16.08.2015, 20:56:52
| Ответить | Цитировать | Написать  
Поиск "дырки" одним запросом
    #39030401
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Akina
Участник
Cyrax_02это "плотные" идентификаторы, реализующие определённую логику предметной областиЕсли логика не допускает движения "обратно" (т.е. если идентификаторы начинаются с sid = 1, то существует возможность построить идентификатор sid = 0) - одним запросом задача решается только с внутренним union (в качестве крайнего рассмотри случай, когда таблица пуста).
...
Рейтинг: 0 / 0
16.08.2015, 21:50:29
| Ответить | Цитировать | Написать  
Поиск "дырки" одним запросом
    #39030406
Добрый Э - Эх
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Добрый Э - Эх
Гость
Cyrax_02то он даст неверный результат, если в таблице table отсутствуют первые 1 или более идентификаторов.заюнионоллить прев копию таблицы на 0... Но тебе же надо без подзапросов.
...
Рейтинг: 0 / 0
16.08.2015, 22:09:30
| Ответить | Цитировать | Написать  
Поиск "дырки" одним запросом
    #39031687
Cyrax_02
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Cyrax_02
Участник
авторЕсли логика не допускает движения "обратно" (т.е. если идентификаторы начинаются с sid = 1, то существует возможность построить идентификатор sid = 0)
Если двигаться "обратно", то для каждого подряд идущего набора "дырок" будет получена "дырка" с максимальным (в этом наборе) sid. А нужно получать минимальный в наборе sid. Поэтому, движение "обратно" не стоит рассматривать вообще.

автородним запросом задача решается только с внутренним union
С внешним же - outer join.

авторзаюнионоллить прев копию таблицы на 0...
После объединения индекс по sid использоваться уже не будет (по отношению к этому объединению). В этом случае запрос становится бесполезным из-за полного перебора.
...
Рейтинг: 0 / 0
18.08.2015, 14:59:30
| Ответить | Цитировать | Написать  
Поиск "дырки" одним запросом
    #39031721
Добрый Э - Эх
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Добрый Э - Эх
Гость
Cyrax_02После объединения индекс по sid использоваться уже не будет.ты бы для начала работающие варианты запросов набросал, сравнил планы и статистику выполнениявыполнения на реальных данных. А уж потом делал бы выводы...
...
Рейтинг: 0 / 0
18.08.2015, 15:29:59
| Ответить | Цитировать | Написать  
Поиск "дырки" одним запросом
    #39031749
Cyrax_02
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Cyrax_02
Участник
авторты бы для начала работающие варианты запросов набросал, сравнил планы и статистику выполнениявыполнения на реальных данных. А уж потом делал бы выводы...
А что - MySQL умеет применять индексы к результатам объединения ?
...
Рейтинг: 0 / 0
18.08.2015, 16:08:23
| Ответить | Цитировать | Написать  
Поиск "дырки" одним запросом
    #39032717
Фотография Lumix
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Lumix
Участник
Cyrax_02,

вот решение, если есть возможность выполнять логику на клиенте

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
create table t (sid int, nid int);
insert into t value (1, 2);
insert into t value (2, 3);
insert into t value (3, 4);

/* delId = 2 */

update t set nid = (select nid from (select nid from t where sid = (*delId) limit 1) v) where nid = (*delId);
delete from t where sid = (*delId);

-- (1, 3)
-- (3, 4)

/* insertId = */
select sid from t where nid != (sid + 1) order by sid limit 1; 

-- 1

/* if insertId > 0 */
update t set nid = nid - 1 where sid = (*insertId)

-- (1, 2)
-- (3, 4)

/* else insertId =  */
select max(sid) + 1 as sid from t; 

-- 4

insert value((*insertId), (*insertId) + 1);

-- (1, 2)
-- (2, 3)
-- (3, 4)



Если мы решали подобную задачу в своем проекте, то мы бы при удалении заносили номер в отдельную таблицу, а при вставке брали бы свободный номер из неё. Ну и прописали бы нормализатор, который вызывался бы с вероятностью 0,05%. Код нормализатора:

Код: sql
1.
delete from tid where id >= (select max(sid) + 1 as maxId from t)
...
Рейтинг: 0 / 0
19.08.2015, 19:00:17
| Ответить | Цитировать | Написать  
Поиск "дырки" одним запросом
    #39033557
Cyrax_02
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Cyrax_02
Участник
Похоже, самый быстрый вариант такой:
Код: php
1.
2.
3.
4.
SELECT (PREV.sid + 1) AS hole
FROM table AS PREV LEFT JOIN table AS NEXT ON (NEXT.sid = PREV.sid + 1)
WHERE (PREV.sid IS NOT NULL) AND (NEXT.sid IS NULL)
ORDER BY PREV.sid ASC LIMIT 1

Одним запросом и без вспомогательных таблиц быстрее - никак.

Проблема данного запроса в том, что всё равно приходится один раз пробегать по всем строкам из таблицы ( table ). Соответственно, получаем линейную зависимость от числа записей в таблице - а это в целом некошерно.

авторЕсли мы решали подобную задачу в своем проекте, то мы бы при удалении заносили номер в отдельную таблицу, а при вставке брали бы свободный номер из неё. Ну и прописали бы нормализатор, который вызывался бы с вероятностью 0,05%
Да, можно использовать вспомогательную таблицу. Что-то подобное я реализовывал в локальном приложении (только во вспомогательной таблице у меня хранились все ранее выданные sid 'ы).

Но в данном случае во вспомогательной таблице пока необходимости нет, поскольку:

а) все операции с sid выполняются только в бэкэнде
б) штатные операции удаления в таблице ( table ) выполняются редко
в) нештатные разовые операции удаления N-го количества записей могут иметь место только в отношении последних добавленных записей - а при удалении последних добавленных записей новые "дырки" не образуются (разве что могут открыться ранее закрытые "дырки")
г) поиск "дырок" вышеприведённым запросом выполняется только при их наличии, а их наличие предварительно проверяется отдельным быстрым запросом

P.S. Пока на 25000 записей запрос выполняется 0.2 сек - это приемлемое время. Ну а когда счёт записей пойдёт на миллионы - можно будет задействовать и вспомогательную таблицу. Либо вычислять и запоминать "дырки" (либо в файле, либо в отдельной таблице) ежедневно ночью по крону (тем же самым запросом).
...
Рейтинг: 0 / 0
20.08.2015, 22:04:29
| Ответить | Цитировать | Написать  
Поиск "дырки" одним запросом
    #39033591
Фотография javajdbc
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
javajdbc
Участник
Cyrax_02,


вот интересно,

select count(1) c1
from t
where sid between N1 and N2

с индексом по СИД будет всегда быстрым при любых Н1 < Н2
?

Если так, то можно продумать алгоритм быстрого поиска
делением пополам (или даже золотое сечение?).

Типа если имеется 100К записей сначала делаем

select count(1) c1
from t
where sid between 1 and 50000

если С1 равно 50000, то дырок нет,
смотрим половинку верхнуей половинки

select count(1) c1
from t
where sid between 50000 and 75000

если С1 меньше чем 25000 то берем следуюшее деление....
на милион записей 20 подходов.
...
Рейтинг: 0 / 0
21.08.2015, 02:21:07
| Ответить | Цитировать | Написать  
Поиск "дырки" одним запросом
    #39033883
Cyrax_02
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Cyrax_02
Участник
авторЕсли так, то можно продумать алгоритм быстрого поиска
делением пополам (или даже золотое сечение?).
Позже этот вариант протестирую.
...
Рейтинг: 0 / 0
21.08.2015, 12:54:53
| Ответить | Цитировать | Написать  
Поиск "дырки" одним запросом
    #39034269
Фотография Lumix
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Lumix
Участник
Cyrax_02 P.S. Пока на 25000 записей запрос выполняется 0.2 сек - это приемлемое время. Ну а когда счёт записей пойдёт на миллионы - можно будет задействовать и вспомогательную таблицу. Либо вычислять и запоминать "дырки" (либо в файле, либо в отдельной таблице) ежедневно ночью по крону (тем же самым запросом).

Есть ещё такое решение вашей задачи, которое мы использовали в нескольких проектах:

Храним в базе искусственно созданную матрицу, заполненную навырост

Код: sql
1.
2.
3.
create table masker (id int);
alter ignore table masker add unique index id (id);
insert into masker values (1), (2), (3), (4), (5), (6), (7), (8), (9), (10);




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

Код: sql
1.
select min(id) from masker left join t on id = sid where t.sid is null;




УСКОРЕНИЕ 1

Если мы знаем, что до 23500 записи у нас точно нет дырок, то

Код: sql
1.
delete from masker where id < 23500




УСКОРЕНИЕ 2

По хрону раз в день пересоздавать таблицу с дырками вот так

Код: sql
1.
2.
3.
drop table holes;
set @maxLim := (select max(sid) from t limit 1);
create table holes as select id from masker left join t on id = sid where t.sid is null and id < @maxLim;



Затем при создании каждой новой записи
1) доставать минимальную запись из этой таблицы
2) если она есть, удалять запись и использовать полученный номер
3) если таблица holes пуста, тогда получать max(sid)

PS.

В этот же самый хрон можно вшить нормализатор маскера: если мы знаем, что в среднем в день у нас создается 850 новых записей, а
Код: sql
1.
select max(id) - (select max(sid) from t) < 850 from masker



дает 0,
то

Код: sql
1.
2.
select @gainFactor = select max(id) from matrix;
insert into masker select * from maskerMother where id > @gainFactor and id <= @gainFactor;



В таблице maskerMother хранятся идентификаторы навырост в течение квартала (или даже года)
...
Рейтинг: 0 / 0
21.08.2015, 22:01:07
| Ответить | Цитировать | Написать  
13 сообщений из 13, страница 1 из 1
Форумы / MySQL [игнор отключен] [закрыт для гостей] / Поиск "дырки" одним запросом
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=47&msg=39031721&tid=1832794]:
 0ms
get settings:
 9ms
get forum list:
 16ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 139ms
get topic data:
 8ms
get forum data:
 2ms
get page messages:
 49ms
get tp. blocked users:
 1ms
others: 240ms
total:  470ms
созд. / загр.: 470ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]