Как выбрать из таблицы элементы, не содержащиеся во второй?

Question

[Никита Колосов]

Есть таблица x, с полями id и title, есть таблица y с полями id, x_id.

Соответственно, необходимо выбрать все id из таблицы x, которых нет в таблице y.

Решение

select id from x where id not in (select x_id from y);

очень медленное (записей >1000000 и там и там).

Вопрос: можно ли как-то выбрать нужные данные быстро?

Answer 1

[Евгений Быков]

Для увеличения общей производительности надо заставить RDBMS использовать merge, а не hash join и не nested loop с использованием индекса.
Для этого сливаем две таблицы

SELECT id FROM x
UNION ALL
SELECT id FROM x
UNION ALL
SELECT x_id FROM y

В этом наборе каждый id входит 1 раз (если он содержится в y и не содержится в x), 2 раза (если он содержится в x и не содержится в y) и 3 раза (если содержится в обеих таблицах).
Затем группируем и выбираем те группы, которые содержат ровно две записи

SELECT id
    FROM (SELECT id FROM x
          UNION ALL
          SELECT id FROM x
          UNION ALL
          SELECT x_id FROM y
         )
    GROUP BY id
    HAVING COUNT(*) = 2

Такой запрос не требует индексов и будет очень эффективен даже на очень больших таблицах
Разумеется, решение основано на предположении об уникальности id в таблице x, и уникальности x_id в таблице y. Если же id не уникален в таблице x, то надо выполнять
SELECT DISTINCT id FROM x
вместо
SELECT id FROM x
Это же касается таблицы колонки x_id колонки y