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

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, нет ли у вас хинта, как выбирать тот или иной способ запроса, навскидку, не анализируя план? Вопрос именно к этому кейсу.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 добавлен к полю по которому будет поиск