PostgreSQL: НЕ В отличие от EXCEPT разницы в производительности (отредактировано # 2)

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

Запрос №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)

Изменить. Я исправил проблему A-B!= B-A, упомянутую ниже. Но моя проблема, как указано, все еще существует: запрос №1 все еще намного хуже, чем запрос №2. Это, я считаю, следует из того факта, что обе таблицы имеют одинаковое количество строк.

Изменить 2. Я использую PostgresQL 9.0.4. Я не могу использовать EXPLAIN ANALYZE, потому что запрос № 1 занимает слишком много времени. Все эти столбцы NOT NULL, поэтому в результате этого не должно быть разницы.

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

Ответ 1

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

Ответ 2

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

Без EXCEPT это можно записать для более эффективного использования индексов (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

Ответ 3

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

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

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

но ваша вторая:

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

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

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

Ответ 4

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

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

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

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

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

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

Ответ 5

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