Как получить список чисел отсутвующих в базе PostgreSQL?

Question

[Константин Т]

В базе присутствуют такие данные (например):

1. id: 1 | name: "any_name"
   
2. id: 2 | name: "any_name"
   
3. id: 4 | name: "any_name"
   
4. id: 7 | name: "any_name"
   
5. id: 8 | name: "any_name"
   
6. id: 11 | name: "any_name"
   

Как одним запросом получить не вошедшие в вывод - 3,5,6,9,10 - числа отсутствующие в базе?

Comments

[Константин Т]

Pavel Denisov, смешная шутка

[res2001]

Pavel Denisov, Константин Т,

Надеюсь вы не хотите их переиспользовать?

Видел в одном приложении корпоративного уровня такой подход.
Запрос поиска дыр был не быстрый, но вызывался регулярно, из-за чего все приложение тормозило.
Пришлось потратить много сил, чтоб убедить разрабов отказаться от этой затеи.

https://ru.stackoverflow.com/questions/102635/%D0%...

Answer 1

[Melkij]

Нужен опорный список значений и not exists подзапрос. Опорный список можно сделать через generate_series функцию

select n from generate_series(1,11) as n
where not exists (select from tablename where id = n)

Comments

[longclaps]

Melkij, скажите, not exists и not in равноценны?

SELECT n
FROM generate_series(1, (SELECT max(id) FROM tablename)) AS n
WHERE n NOT IN((SELECT id FROM tablename));

[Melkij]

По результату - да. По плану выполнения - различны.

[longclaps]

Melkij, нет ли у вас хинта, как выбирать тот или иной способ запроса, навскидку, не анализируя план? Вопрос именно к этому кейсу.

[Melkij]

not exists для небольших диапазонов. Вычитывать целиком всю таблицу - смотреть план. Всё равно быстро это не будет.

[Руслан .]

longclaps, Melkij, в данном случае not exists должен быть быстрее чем NOT IN.

Тут фишка в том что при NOT IN нужно построить два датасета и заджойнить их, при этом по вложенному датасету в этом случае нет индекса и поиск будет долгим (возможно сервер сам примет решение сделать какой-нибудь hash join, но все равно это будут накладные расходы на построение хэш таблицы)

Если использовать not exists и по полю id вложенной таблицы есть индекс, то вложенный подзапрос быстро отработает используя индекс для определения наличия id.(судя по описанию id это ключевое поле и индекс должен быть.)

[Melkij]

Руслан, not in на моей тестовой 9.6 с 1млн строк скатывается в hashed SubPlan и работает в полтора раза быстрее not exists nested loops. От распределения данных зависеть будет, тестировал на 0,2% пропущенных значений. И это ещё на Index Only Scan.

Быстрее может быть нарисовать merge join на plpgsql - зная, что вычитывать на самом деле надо только одну табличку прикрутить сбоку итератор и выплёвывать числа если следующий id из цикла по табличке прилетел не +1 от предыдущего. Но тоже проверять нужно, plpgsql как числодробилка ни о чём.

[longclaps]

Руслан, что быстрее - однократный подзапрос SELECT id FROM tablename или множественный SELECT id FROM tablename - вопрос дискуссионный.

[Руслан .]

longclaps, согласен, есть нюансы, все зависит от количества записей, которые возвращает вложенный запрос и от типа данных поля по которому проверяем вхождение и от параметров сервера(количество оперативки, типы дисков) и от нагрузки на сервер со стороны других коннектов:

Вариант с not in:
1. получаем датасет по вложенному запросу и размещаем его например в tempdb
(тут имеем накладные расходы на хранение, т.к. tempdb в оперативке и чем больше откусишь ее, тем меньше останется для других пользователей/запросов)

2. для каждой записи внешней таблицы ищем вхождение во вложенный датасет, тут вариант полный перебор или хэш джойн или еще что-то.

3. в случае хэш джойн получим доп. накладные расходы на постороение хэш таблицы и на вычисление хэша для каждой записи внешней таблицы. Но есть плюс, т.к. вложенный датасет храниться в оперативке, то операции с ним выполняются быстрее чем с диском (хотя если диск SSD то разница не сильно большая).

Вариант с not exist при наличии индекса:

1. Тут возможна ситуация, что весь индекс или большая его часть закешированы в оперативке и тогда не будет множественных обращений к диску. А поиск в памяти по бинарному дереву (по индексу) может быть быстрее чем по хэш таблице, если учесть время необходимое для вычисления хэша от каждой записи внешней таблицы и на построение хэш таблицы.

2. Если индекс не закеширован то да, на поиск и загрузку страниц индекса с диска требуется больше времени чем поиск в хэш таблице в оперативке.

[Руслан .]

Melkij, это может быть следствием того, что база тестовая и есть много свободной оперативки для построения хэш таблицы.
Есть ли индекс по полю id и если есть то какого типа (уникальный, кластерный)?

[Melkij]

Руслан, вы про какую-то другую СУБД. Нет в postgresql никакого tempdb, тем более разделяемого по кластеру между пользователями в оперативке. work_mem выделяется динамически в приватной памяти каждого отдельного backend под каждый отдельный того требующий узел плана запроса.

быстрее чем с диском (хотя если диск SSD то разница не сильно большая).

О да, разница всего лишь порядками измеряется.

Выше я забыл дописать - 100% cache hit по shared buffers. С дисков не читалось ничего и not in оказался всё равно в полтора раза быстрее. Потому что миллион index lookup всё равно имеют свою цену. И это на index only scan, т.е. для проверки mvcc мы страницы таблички не поднимали.
Запрос с except у меня получается посередине по скорости. А чисто алгоритмически - сюда бы неплохо merge join встал, о чём уже упоминал. Одну табличку читать по индексу уже отсортированную, опорную последовательность мы заранее может гарантировать последовательность значений. То есть на сортировку ресурсов не тратим вовсе.

[Melkij]

И опять вы про какую-то другую СУБД.

если есть то какого типа (уникальный, кластерный)?

primary key, btree.

есть много свободной оперативки для построения хэш таблицы.

Не учитывается планировщиком. Есть work_mem - влезаем - берём его. Нет делаем disksort. Дисковой сортировки не было. hash join вовсе не умеет temp files и всегда в памяти. Если планировщик считает, что не влезет в work_mem - то предпочитает другой план.

[Руслан .]

Melkij, tempdb в MSSQL, но смысл тот же, либо запрос в оперативке обрабатывается, либо дисковые операции.

SSD vs RAM, тут от конкретных продуктов зависит, но да тут 1-2 порядка разница в пользу RAM, но уже не 5 порядков как с HDD

[Константин Т]

Melkij Спасибо за участие в дискуссии, я пока так и не понял что будет быстрее not exists или not in, в таблице примерно ~8 500 000 записей, ключ index добавлен к полю по которому будет поиск

Answer 2

[ponaehal]

ИМХО, если такой вопрос возник, то ВОЗМОЖНО что -то делаете не так. Вещать бизнес-смысл на IDб основная цель которых обеспечить уникальность - это в общем случае не очень правильно.
Тем не менее...
Возможно есть более красивое решение, но сходу не приходит в голову (для каждой БД оно будет свое).
Общий подход:
1. Создаем таблицу t2 с большим количеством строк и с одним полем num. В цикле заполняем ее значениями от 1 до n.
2. В запросе минусуем исходную таблицу из t2
SELECT t.num FROM t2
EXCEPT
SELECT t.id FROM base_table t
все.

ЗЫ Если таблицу делать лень, а число записей небольшое, то можно воспользоваться
SELECT unnest(array[1, 2, 3, 4)

Comments

[Константин Т]

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