PostgreSQL: НЕ в сравнении с разницей в производительности, кроме (редакция № 2)

Question

У меня есть два запроса, которые функционально идентичны.Один из них работает очень хорошо, другой - очень плохо.Я не вижу, откуда возникает разница в производительности.

Запрос № 1:

SELECT id 
FROM subsource_position
WHERE
  id NOT IN (SELECT position_id FROM subsource)

Это возвращается со следующим планом:

                                  QUERY PLAN                                   
-------------------------------------------------------------------------------
 Seq Scan on subsource_position  (cost=0.00..362486535.10 rows=128524 width=4)
   Filter: (NOT (SubPlan 1))
   SubPlan 1
     ->  Materialize  (cost=0.00..2566.50 rows=101500 width=4)
           ->  Seq Scan on subsource  (cost=0.00..1662.00 rows=101500 width=4)

Запрос № 2:

SELECT id FROM subsource_position
EXCEPT
SELECT position_id FROM subsource;

План:

                                           QUERY PLAN                                            
-------------------------------------------------------------------------------------------------
 SetOp Except  (cost=24760.35..25668.66 rows=95997 width=4)
   ->  Sort  (cost=24760.35..25214.50 rows=181663 width=4)
         Sort Key: "*SELECT* 1".id
         ->  Append  (cost=0.00..6406.26 rows=181663 width=4)
               ->  Subquery Scan on "*SELECT* 1"  (cost=0.00..4146.94 rows=95997 width=4)
                     ->  Seq Scan on subsource_position  (cost=0.00..3186.97 rows=95997 width=4)
               ->  Subquery Scan on "*SELECT* 2"  (cost=0.00..2259.32 rows=85666 width=4)
                     ->  Seq Scan on subsource  (cost=0.00..1402.66 rows=85666 width=4)
(8 rows)

У меня такое ощущение, что мне не хватает чего-то явно плохого в одном из моих запросов, или я неправильно настроил сервер PostgreSQL.Я бы ожидал, что NOT IN хорошо оптимизируется;NOT IN всегда является проблемой производительности или есть причина, по которой он здесь не оптимизируется?

Дополнительные данные:

=> select count(*) from subsource;
 count 
-------
 85158
(1 row)

=> select count(*) from subsource_position;
 count 
-------
 93261
(1 row)

Редактировать : Я исправилAB! = Проблема BA, упомянутая ниже.Но моя проблема, как указано, все еще существует: запрос № 1 все еще значительно хуже, чем запрос № 2.Я полагаю, это следует из того факта, что в обеих таблицах одинаковое количество строк.

Редактировать 2 : я использую PostgresQL 9.0.4.Я не могу использовать EXPLAIN ANALYZE, потому что запрос № 1 занимает слишком много времени.Все эти столбцы НЕ ПУСТО (NULL), поэтому в результате не должно быть различий.

Редактировать 3 : у меня есть индекс для обоих этих столбцов.Я еще не получил запрос № 1 для завершения (сдал через ~ 10 минут).Запрос №2 немедленно возвращается.

Answer 1

Запрос № 1 не является элегантным способом сделать это ... (НЕ) IN SELECT подходит для нескольких записей, но не может использовать индексы наилучшим образом (Seq Scan).

Без ИСКЛЮЧЕНИЯ это может быть написано для более эффективного использования индексов (HASH JOIN).

SELECT sp.id
FROM subsource_position AS sp
    LEFT JOIN subsource AS s ON (s.postion_id = sp.id)
WHERE
    s.postion_id IS NULL

Answer 2

Поскольку вы работаете с конфигурацией по умолчанию, попробуйте увеличить work_mem. Скорее всего, подзапрос заканчивается тем, что он помещается в буфер на диск, поскольку вы допускаете только 1 МБ рабочей памяти. Попробуйте 10 или 20 МБ.

Answer 3

Ваши запросы не являются функционально эквивалентными, поэтому любое сравнение их планов запросов не имеет смысла.

Ваш первый запрос в терминах теории множеств это:

{subsource.position_id} - {subsource_position.id}
          ^        ^                ^        ^

но ваш второй это:

{subsource_position.id} - {subsource.position_id}
          ^        ^                ^        ^

И A - B - это не то же самое, что B - A для произвольных наборов A и B.

Исправьте ваши запросы, чтобы они были семантически эквивалентными, и повторите попытку.

Answer 4

Если id и position_id оба проиндексированы (либо по своему собственному, либо по первому столбцу в многостолбцовом индексе), то все, что необходимо, - это два сканирования индекса - это тривиальный алгоритм набора на основе отсортированного слияния.

Лично я думаю, что у PostgreSQL просто нет интеллекта для оптимизации, чтобы это понять.

(Я пришел к этому вопросу после диагностики запроса, выполняющегося в течение более 24 часов, который я мог выполнить с помощью sort x y y | uniq -u в командной строке в секундах. База данных менее 50 МБ при экспорте с помощью pg_dump.)

PS: более интересный комментарий здесь :

больше работы было вложено в оптимизацию ИСКЛЮЧИТЬ И НЕ СУЩЕСТВУЕТ, чем НЕ В, потому что последний существенно менее полезный из-за его неинтуитивной, но специальной обработки NULL. Мы не собираемся извиняться за это и не будем расценивать это как ошибку.

То, что сводится к тому, что except отличается от not in в отношении нулевой обработки. Я не смотрел детали, но это означает, что PostgreSQL (агрессивно) не оптимизирует его.

Answer 5

Второй запрос использует функцию HASH JOIN в postgresql.Это намного быстрее, чем Seq Scan первого.