По материалам статьи Craig Freedman: Summary of Join Properties
Следующая таблица суммирует характеристики трех операторов соединения, которые были описаны в моих трех предшествующих статьях.
| Nested Loops Join | Merge Join | Hash Join |
Лучше подходит… | Для относительно маленьких таблиц с индексом у внутренней таблицы по ключу соединения. | Для относительно больших таблиц с индексами, позволяющими упорядочить данные по ключам соединения эквивалентности и/или, когда требуется упорядочивание после соединения. | Для запросов к большим хранилищам и большим таблицам. Хорошее распараллеливание, которое масштабируется линейно. |
Параллелизм | Поддерживает большое число параллельных подключений пользователей. | Соединение "многие к одному" с индексами для упорядочивания - поддерживает большое число параллельных подключений пользователей. | Лучше подходит для не большого числа параллельных подключений пользователей с высокими требованиями к производительности. |
Stop and go | Нет | Нет | Да (только для стадии компоновки) |
Требуется соединение по эквивалентности | Нет | Да (кроме полного внешнего соединения) | Да |
Внешние и полусоединения | Только левые соединения (полные внешние соединения только через трансформацию) | Все типы соединений | Все типы соединений |
Использование памяти | Нет | Нет (может потребоваться для сортировки, которая использует память) | Да |
Использование tempdb | Нет | Да (только для соединений "многие ко многим") | Да (если соединение выйдет за пределы памяти и при сбросе на диск) |
Требует упорядочивания | Нет | Да | Нет |
Сохраняет порядок | Да (только внешнего входного потока) | Да | Нет |
Примеры
В этой части статьи демонстрируется, как небольшие изменения в запросе могут привести к изменениям в выборе оптимизатором типа соединения. Давайте начнём с двух таблиц, по 1000 строк в каждой:
create table T1 (a int, b int, x char(200))
create table T2 (a int, b int, x char(200))
set nocount on
declare @i int
set @i = 0
while @i < 1000
begin
insert T1 values (@i * 2, @i * 5, @i)
insert T2 values (@i * 3, @i * 7, @i)
set @i = @i + 1
endТак как у таблиц нет индексов, простое их соединение будет выполнено посредством хэш-соединения:
select * from T1 join T2 on T1.a = T2.a|--Hash Match(Inner Join, HASH:([T1].[a])=([T2].[a]),RESIDUAL:([T2].[a]=[T1].[a])) |--Table Scan(OBJECT:([T1])) |--Table Scan(OBJECT:([T2])) |
Однако, есть одна вещь, для которой хэш-соединение работает плохо, это когда в запросе нужно быстро вернуть первые несколько строк. Предположим, что мы хотим получить только первые 10 строк:
select top 10 * from T1 join T2 on T1.a = T2.a|--Top(TOP EXPRESSION:((10))) |--Nested Loops(Inner Join, WHERE:([T2].[a]=[T1].[a])) |--Table Scan(OBJECT:([T1])) |--Table Spool |--Table Scan(OBJECT:([T2])) |
Теперь мы наблюдает использование соединения вложенных циклов. Индекса нет, так что этот план предполагает просмотр всей T2 для каждой строки из T1, пока не будут найдены 10 пар строк. Если для нахождения 10 пар потребуется выполнить много просмотров таблицы T2, этот план станет обходиться очень дорого. К счастью, если Вы выполняете этот запрос с включённым сбором статистики, Вы увидите, что просмотр T2 выполниться только 28 раз.
Примечания:
Как можно было ожидать, оператор в вершине возвратит первые N строк, а затем закончит работу со своим поддеревом. В этом примере это N - 10.
Организация очереди для таблицы может помочь оптимизации. В этом примере, очереди почти не используются. Однако, давайте посмотрим что будет, если вместо "select *" мы бы написали "select T2.a". В таблице T2 имеется три столбца, включая столбец с типом char (200), но нам нужен только один целочисленный столбец T2.a. Таким образом, мы можем хранить в очереди только T2.a. T2 может содержать около 40-ка строк на страницу, поскольку размер строки у неё чуть более 200 байт. Сканирование всех 1000 строк в T2 потребует обработки приблизительно 25 страниц. Очередь может вместить значения столбца T2.a для всех 1000 строк, что займёт всего одну или две страницы.
Возвращаясь к предыдущему примеру, если будет запрошено слишком много строк, соединение вложенных циклов окажется дорогим. Лучшим выбором становиться соединение слиянием:
select top 100 * from T1 join T2 on T1.a = T2.a|--Top(TOP EXPRESSION:((100))) |--Merge Join(Inner Join, MANY-TO-MANY MERGE:([T2].[a])=([T1].[a]),RESIDUAL:([T2].[a]=[T1].[a])) |--Sort(ORDER BY:([T2].[a] ASC)) | |--Table Scan(OBJECT:([T2])) |--Sort(ORDER BY:([T1].[a] ASC)) |--Table Scan(OBJECT:([T1])) |
Точно так же, если нужно упорядочивание, соединение слиянием тоже будет работать хорошо, так как понадобиться отсортировать как минимум одну из таблиц:
select top 10 * from T1 join T2 on T1.a = T2.a
order by T1.a(План у этого запроса по существу такой же, как был ранее при TOP 100)
Теперь давайте добавим кластеризованный индекс:
create unique clustered index T1a on T1(a)Возвращаясь к нашему первому соединению, мы теперь получим соединение слиянием "многие к одному":
select * from T1 join T2 on T1.a = T2.aselect * from T1 join T2 on T1.a = T2.a |--Merge Join(Inner Join, MERGE:([T1].[a])=([T2].[a]),RESIDUAL:([T2].[a]=[T1].[a])) |--Clustered Index Scan(OBJECT:([T1].[T1a]), ORDERED FORWARD) |--Sort(ORDER BY:([T2].[a] ASC)) |--Table Scan(OBJECT:([T2])) |
Оптимизатор решил, что, так как одна таблица уже отсортирована, можно также отсортировать и другую таблицу, а потом использовать соединение слиянием вместо хэш-соединения.
Но, если к просмотру T1 добавить предикат, оптимизатор вернётся к хэш-соединению:
select * from T1 join T2 on T1.a = T2.a
where T1.b < 100|--Hash Match(Inner Join, HASH:([T1].[a])=([T2].[a]),RESIDUAL:([T2].[a]=[T1].[a])) |--Clustered Index Scan(OBJECT:([T1].[T1a]), WHERE:([T1].[b]<(100))) |--Table Scan(OBJECT:([T2])) |
План соединения слиянием должен сортировать все 1000 строк T1, в то время как для хэш-соединение планируется сформировать хеш-таблицу только по 20 строкам из T1, которые соответствуют предикату T1.b < 100. Таким образом, план хэш-соединения задействует меньше памяти и менее вероятен сброс на диск.
Но, если опять добавит к запросу требование по сортировке, мы снова вернёмся к соединению слиянием:
select * from T1 join T2 on T1.a = T2.a
where T1.b < 100
order by T1.a|--Merge Join(Inner Join, MERGE:([T1].[a])=([T2].[a]),RESIDUAL:([T2].[a]=[T1].[a])) |--Clustered Index Scan(OBJECT:([T1].[T1a]),WHERE:([T1].[b]<(100)) ORDERED FORWARD) |--Sort(ORDER BY:([T2].[a] ASC)) |--Table Scan(OBJECT:([T2])) |
Как видно, соединение слиянием сохраняет порядок, и поэтому нет необходимости в заключительном упорядочивании. Хэш-соединение не сохраняет порядок, так что понадобилась бы дополнительная сортировка. Т.о. при хэш-соединении понадобились бы два потребляющих память оператора. Обратите внимание, что один потребляющий память оператор не обязательно лучше, чем два. В действительности, это зависит от того, в каком объёме памяти эти операторы нуждаются.
Далее, давайте к просмотру T2 добавим предикат:
select * from T1 join T2 on T1.a = T2.a
where T2.b < 100|--Nested Loops(Inner Join, OUTER REFERENCES:([T2].[a])) |--Table Scan(OBJECT:([T2]), WHERE:([T2].[b]<(100))) |--Clustered Index Seek(OBJECT:([T1].[T1a]), SEEK:([T1].[a]=[T2].[a]) ORDERED FORWARD) |
После уменьшения кардинальности T2, индексированное соединение вложенных циклов становится предпочтительным.
Наконец, давайте посмотрим что будет, если используется большая таблица T3, содержащая 100000 строк:
create table T3 (a int, b int, x char(200))
declare @i int
set @i = 0
while @i < 100000
begin
insert T3 values (@i * 5, @i * 11, @i)
set @i = @i + 1
endРассмотрим простое соединение T1 и T3:
select * from T1 join T3 on T1.a = T3.a|--Hash Match(Inner Join, HASH:([T1].[a])=([T3].[a]),RESIDUAL:([T3].[a]=[T1].[a])) |--Clustered Index Scan(OBJECT:([T1].[T1a])) |--Table Scan(OBJECT:([T3])) |
Даже при наличии индекса по T1, выбирается хэш-соединение. Вспомним, что при соединении T1 и T2, исходя из размера таблиц, использовалось соединение слиянием. Чтобы добиться соединения слиянием нужно, что бы обе эти таблицы были одинаково отсортированы. Для хэш-соединения вполне достаточно памяти, чтобы сформировать хеш-таблицу по T1 с 1000 строк, в то время как соединению слиянием понадобился необходимый для сортировки всей имеющей 100000 строк таблицы T3 объём памяти. Таким образом, хэш-соединению памяти нужно значительно меньше.
Подсказки
Хотя мы не рекомендуем использование подсказок оптимизатору (если в этом нет абсолютной необходимости) для исследовательских целей они вполне применимы, т.к. позволяют видеть, как разные варианты и типы соединений влияют на планы исполнения запроса и производительность, поскольку, используя подсказки можно вынудить SQL Server создавать разные планы запроса. Существующие подсказки (hints) перечислены в электронной документации. Следует помнить, что с их помощью невозможно заставить сервер выбрать совершенно любой план исполнения, и что использование неправильных подсказок может привести к тому, что SQL Server не сможет найти допустимый план запроса, что приведёт к появлению ошибки:
Msg 8622, Level 16, State 1, Line 1 |
Кроме того, Вы можете использовать в запросе подсказки, которые укажут SQL Server использование конкретного типа соединения или зададут порядок соединения. Подсказки в запрос можно добавить с помощью предложения OPTION, добавляемого в конец инструкций. Я уже использовал некоторые из подсказок оптимизатору в примерах, опубликованных в предыдущих статьях. Для этих целей можно использовать следующие подсказки: LOOP JOIN, MERGE JOIN, HASH JOIN и FORCE ORDER. Первые три подсказки указывают оптимизатору использовать заданный тип соединения. Если были указаны две подсказки соединения, оптимизатор будет использовать только эти два типа соединения; так можно запретить использование каких то типов соединения. FORCE ORDER указывает оптимизатору порядок соединения таблиц, он будет таким, как таблицы расположены в предложении FROM.
Вы можете указать подсказки соединения непосредственно в предложении FROM, задав тип и порядок соединения. Это очень мощные подсказки. С их помощью, Вы можете точно определить тип соединения для каждого из соединений. Используя круглые скобки, можно задать любой порядок соединения, включая Bushy - деревья. В качестве отвлечённого примера, рассмотрим подсказки, которые приводят к использованию Bushy - дерева со всеми тремя типами соединений:
select *
from (T1 inner merge join T2 on T1.a = T2.a)
inner hash join
(T3 inner loop join T4 on T3.a = T4.a)
on T1.b = T3.bДалее…
В следующей статье я опишу еще несколько проблем соединений.
