По материалам статьи Craig Freedman: Subqueries: ANDs and ORs

В статье Введение в соединения, я показал примеры того, как можно использовать полусоединение для оценки подзапроса в EXISTS. В качестве резюме, давайте рассмотрим другой пример:

create table   T1 (a int, b int)
create table   T2 (a int)
create table   T3 (a int)

select * from   T1
where exists   (select * from   T2 where T2.a = T1.a)

^{|--Nested Loops(Left Semi Join, WHERE:([T2].[a]=[T1].[a]))}

^{|--Table Scan(OBJECT:([T1]))}

^{|--Table Scan(OBJECT:([T2]))}

Этот план возвращает те строки из T1, для которых имеются соответствующие строки в T2.
Точно так же может использоваться анти-полусоединение для оценки подзапроса в NOT EXISTS:

select * from   T1
where not   exists (select   * from T2 where   T2.a = T1.a)

^{|--Nested Loops(Left Anti Semi Join, WHERE:([T2].[a]=[T1].[a]))}

^{|--Table Scan(OBJECT:([T1]))}

^{|--Table Scan(OBJECT:([T2]))}

Этот план возвращает те строки T1, для которых нет соответствующих строк в T2.
Обратите внимание, что SQL Server для каждого из этих запросов может использовать любой тип соединения (вложенные циклы, слияние или хеширование). Все три типа соединения поддерживают полусоединения.
Теперь я собираюсь показать, что случается, если совместить AND или OR вместе с несколькими подзапросами NOT EXISTS или EXISTS (или, в математических терминах - как SQL Server работает с конъюнкциями и дизъюнкциями подзапросов).

Конъюнкция (AND)

Конъюнкция довольно простая штука. Мы просто последовательно объединяем несколько полусоединений, одно за другим. Этот метод работает для любой комбинации подзапросов NOT EXISTS и/или EXISTS. Например:

select * from   T1
where exists   (select * from   T2 where T2.a = T1.a) and
        not exists   (select * from   T3 where T3.a = T1.b)

^{|--Nested Loops(Left Anti Semi Join, WHERE:([T3].[a]=[T1].[b]))}

^{|--Nested Loops(Left Semi Join, WHERE:([T2].[a]=[T1].[a]))}

^{| |--Table Scan(OBJECT:([T1]))}

^{| |--Table Scan(OBJECT:([T2]))}

^{|--Table Scan(OBJECT:([T3]))}

Этот план возвращает строки из T1, для которых есть соответствующие строки в T2, и для которых нет соответствующих строк в T3. Как и прежде, SQL Server для каждого из этих полусоединений может использовать любой тип соединения.

Дизъюнкция (OR)

Дизъюнкция будет поинтересней. Тут нельзя просто объединить несколько полусоединений, как это делается для конъюнкции. Рассмотрим такой запрос:

select * from   T1
where exists   (select * from   T2 where T2.a = T1.a) or
        exists (select   * from T3 where   T3.a = T1.b)

Нужно возвратить строку из T1, если она удовлетворяет условию любого из подзапросов. Мы не можем отказаться от не подходящей строки, пока не будут проверены условия обеих подзапросов. Существует два пути преобразования оптимизатором такого запроса, и мы рассмотрим оба:

Путь 1:

select * from   T1
where exists
    (
    select * from T2 where T2.a = T1.a
    union all
    select * from T3 where T3.a = T1.b
    )

Этот запрос перед выполнением полусоединения объединяет результаты двух подзапросов. Полусоединение возвратит строку из T1, если для этой строки подзапросы вернут какой-либо результат. Ниже представлен план запроса (полученный по первоначальному запросу, в котором не было union all):

^{|--Nested Loops(Left Semi Join, OUTER REFERENCES:([T1].[a], [T1].[b]))}

^{|--Table Scan(OBJECT:([T1]))}

^{|--Concatenation}

^{|--Table Scan(OBJECT:([T2]), WHERE:([T2].[a]=[T1].[a]))}

^{|--Table Scan(OBJECT:([T3]), WHERE:([T3].[a]=[T1].[b]))}

Как Вы видите, оператор конкатенации выполняет полное объединение.

Путь 2:
Показанные ниже SQL синтаксис не отражает в точности второй путь, но очень к нему близок:

select * from   T1
where exists   (select * from   T2 where T2.a = T1.a)
union
select * from   T1
where exists   (select * from   T3 where T3.a = T1.b)

Этот запрос оценивает два подзапроса как два полностью самостоятельных соединения и объединяет их результаты. Однако, какая-нибудь строка в T1 может быть квалифицирована обоими подзапросами, так что могут получиться дубликаты. Таким образом, понадобится ещё и устранение дубликатов. Поэтому - то в показанном запросе используется "объединение", а не "полное объединение". Однако, как упоминалось выше, это не совсем точно, потому что дубликаты могут быть и непосредственно в T1. Эти дубликаты нельзя удалять, но в приведённом примере они удалены будут (конечно, если у T1 имеется уникальный ключ, и таблица не содержит дубликатов, такое преобразование было бы верным; если же таблица T1 не имеет уникального ключа, ситуацию можно разрешить, используя функцию ROW_NUMBER). К счастью, мы имеем явный уникальный ключ, SQL Server создает уникальный реляционной ключ для каждой таблицы, и его могут использовать внутренние механизмы, чтобы реализовать подобную трансформацию. Ниже показан пример такого плана запроса, который использует хэш-соединение (полученный по первоначальному запросу, к которому была добавлена подсказка оптимизатору option(hash join)):

^{|--Sort(DISTINCT ORDER BY:([Bmk1000] ASC))}

^{|--Concatenation}

^{|--Hash Match(Right Semi Join, HASH:([T2].[a])=([T1].[a]),}

^{| | RESIDUAL:([T2].[a]=[T1].[a]))}

^{| |--Table Scan(OBJECT:([T2]))}

^{| |--Table Scan(OBJECT:([T1]))}

^{|--Hash Match(Right Semi Join, HASH:([T3].[a])=([T1].[b]),}

^{| RESIDUAL:([T3].[a]=[T1].[b]))}

^{|--Table Scan(OBJECT:([T3]))}

^{|--Table Scan(OBJECT:([T1]))}

[Bmk1000] является уникальным идентификатором записей таблицы T1 и используется в качестве уникального реляционного ключа для нашего примера. Сортировка DISTINCT ORDER BY, как я писал выше, устраняет дубликаты [Bmk1000].
Обратите внимание, что хэш-соединения являются правыми, а не левыми полусоединениями. Как Вы знаете, правые и левые полусоединения логически эквивалентны; у них только переставлены местами поступающие на вход таблицы.

Дизъюнкция и подзапросы NOT EXISTS

Для дизъюнкции с NOT EXISTS также имеется две альтернативы. Подзапрос NOT EXISTS отрабатывает с несколько странной на первый взгляд трансформацией. Например, мы можем переписать наш запрос так, как показано ниже:

Запрос:

select * from   T1
where not   exists (select   * from T2 where   T2.a = T1.a) or
        exists (select   * from T3 where   T3.a = T1.b)

Переписываем как:

select * from T1
where exists
    (
     select *
    from (select 0) cs(a)
    where not exists (select * from T2 where T2.a = T1.a)
    union all
     select * from T3 where T3.a = T1.b
    )

Выделенная жирным шрифтом часть представленного выше запроса представляет собой инверсию подзапроса. Если мы находим в T2 соответствующую условию строку, предложение NOT EXISTS становиться ложным и ничего не будет возвращаться из выделенного жирным шрифтом подзапроса. Если в T2 соответствующей строки не найдено, предложение NOT EXISTS вернёт истину, и из выделенного жирным шрифтом подзапроса строка возвращена будет. Значение строки не будет удовлетворять условию соответствия, и потому попадёт в полусоединение с T1. Вот каков будет план такого запроса:

^{|--Nested Loops(Left Semi Join, OUTER REFERENCES:([T1].[a], [T1].[b]))}

^{|--Table Scan(OBJECT:([T1]))}

^{|--Concatenation}

^{|--Table Scan(OBJECT:([T3]), WHERE:([T3].[a]=[T1].[b]))}

^{|--Nested Loops(Left Anti Semi Join)}

^{|--Constant Scan}

^{|--Table Scan(OBJECT:([T2]), WHERE:([T2].[a]=[T1].[a]))}

Выделенная подчёркиванием часть плана соответствует выделенному жирным шрифтом подзапросу. Оператор Constant Scan возвращает одну строку; что соответствует "( select 0)".

Дизъюнкция и SQL Server 2000

SQL Server 2000 реализует дизъюнкцию, используя для этого столбцы пробной таблицы и Passthru предикаты, которые были описаны в предыдущей статье. В частности SQL Server 2000 должен использовать подобные планы для дизъюнкции с подзапросами NOT EXISTS. Например:

select * from   T1
where not   exists (select   * from T2 where   T2.a = T1.a) or
        exists (select   * from T3 where   T3.a = T1.b)

^{|--Filter(WHERE:([Expr1008]=NULL OR [Expr1009]))}

^{|--Nested Loops(Left Semi Join, WHERE:([Expr1008]=NULL)}

^{| OUTER REFERENCES:([T1].[b]),}

^{| DEFINE:([Expr1009] = [PROBE VALUE]))}

^{|--Nested Loops(Left Semi Join, OUTER REFERENCES:([T1].[a]),}

^{| | DEFINE:([Expr1008] = [PROBE VALUE]))}

^{| |--Table Scan(OBJECT:([T1]))}

^{| |--Row Count Spool}

^{| |--Table Scan(OBJECT:([T2]), WHERE:([T2].[a]=[T1].[a]))}

^{|--Row Count Spool}

^{|--Table Scan(OBJECT:([T3]), WHERE:([T3].[a]=[T1].[b]))}

Оба полусоединения в этом плане работают со столбцами пробной таблицы. Как видно, полусоединения столбцов пробной таблицы возвращают каждую удовлетворяющую условию соединения внешнюю строку, после этого столбец пробной таблицы имел бы значение - истина, а если строка не удовлетворяет условию соединения - ложь (NULL). Самое нижнее полусоединение выполняет проверку подзапроса NOT EXISTS: будет ли каждая строка T1 соединяться со строкой T2, и устанавливает соответствующее значение для столбца пробной таблицы ([Expr1008]). Самое верхнее полусоединение использует Passthru предикат, который выполняет проверку [Expr1008]. Так, если строка T1 не соединяется со строкой T2, [Expr1008] принимает значение ложь (NULL), подзапрос NOT EXISTS - принимает значение - истина, предикат Passthru принимает значение - истина, и самое верхнее полусоединение возвращает строку без оценки подзапроса EXISTS. С другой стороны, если строка T1 соединяется со строкой T2: [Expr1008] - истина, подзапрос NOT EXISTS - ложь, предикат Passthru - ложь, и самое верхнее полусоединение выполнит подзапрос EXISTS, чтобы определить, соединяется ли строка T1 со строкой T3, и устанавливает соответствующие значение для столбца пробной таблицы ([Expr1009]). Наконец, в верхней части плана есть фильтр, который проверяет оба столбца пробной таблицы ещё до того, как будут возвращены строки T1, и он определяет, удовлетворяет ли строка условиям хотя бы одного из подзапросов.
Row Count Spool включён в план для оптимизации. Я расскажу о нём в другой раз.
Хотя такое случается довольно редко, точно такой же план запроса может получиться, даже если вместо соединения вложенных циклов будет использоваться соединение слиянием. Вот этот план:

^{StmtText DefinedValues}

^{|--Filter(WHERE:([Expr1008]=NULL OR [Expr1009])) [T1].[a], [T1].[b]}

^{|--Merge Join(Left Semi Join,}

^{| MANY-TO-MANY MERGE:([T1].[b])=([T3].[a]),}

^{| RESIDUAL:([T3].[a]=[T1].[b]) OR [T1].[a], [T1].[b],}

^{| ([Expr1008]=NULL)) [Expr1008], [Expr1009]}

^{|--Sort(ORDER BY:([T1].[b] ASC)) [T1].[a], [T1].[b], [Expr1008]}

^{| |--Merge Join(Left Semi Join,}

^{| | MANY-TO-MANY MERGE:([T1].[a])=([T2].[a]),}

^{| | RESIDUAL:([T2].[a]=[T1].[a])) [T1].[a], [T1].[b], [Expr1008]}

^{| |--Sort(ORDER BY:([T1].[a] ASC)) [T1].[a], [T1].[b]}

^{| | |--Table Scan(OBJECT:([T1])) [T1].[a], [T1].[b]}

^{| |--Sort(ORDER BY:([T2].[a] ASC)) [T2].[a]}

^{| |--Table Scan(OBJECT:([T2])) [T2].[a]}

^{|--Sort(ORDER BY:([T3].[a] ASC)) [T3].[a]}

^{|--Table Scan(OBJECT:([T3])) [T3].[a]}

Я добавил столбец DefinedValues, полученный при включённой опции showplan_all, поскольку в соединении слиянием нет другой возможности отследить столбец пробной таблицы.

Соображения производительности

Все примеры в этой статье работают с кучей. Однако, всё вышесказанное применимо и к таблицам с индексами, т.е. в реальной жизни Вы должны создать индексы, если Вы печётесь о производительности!

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

Подзапросы: AND и OR