Parallel Nested Loops Join

По материалам статьи Craig Freedman: Parallel Nested Loops Join

Перевод Ирины Наумовой.

SQL Server распараллеливает Nested Loops Join, распределяя в случайном порядке строки внешней таблицы по потокам вложенных циклов. В данном случае, речь идёт о строках, которые поступают первыми, и мы их видим вверху, на графическом плане запроса. Например, если на входе соединения вложенных циклов имеется два потока, каждый поток получит приблизительно половину строк. Потоки проходятся по строкам внутренней таблицы соединения (то есть, по строкам, поданным во вторую очередь, мы их видим ниже в плане запроса), точно по такому же алгоритму, как это было бы реализовано в сценарии с последовательной обработкой строк. Таким образом, для каждой обрабатываемой потоком строки внешней таблицы, поток обеспечивает соединение своей внутренней таблицы, используя эту строку в качестве источника коррелированных параметров. Это позволяет потокам работать независимо друг от друга. При этом для внутренней таблицы соединения вложенных циклов SQL Server не добавляет операторы параллелизма и работу с ней не распараллеливает.

Простой пример

Давайте рассмотрим простой пример. Чтобы вынудить оптимизатор выбрать параллельный план, создадим таблицу с большим числом строк. Если Вы решите проверить эти примеры у себя, учтите, что заполнение таблицы тестовыми данными может занять несколько минут.

create table T1 (a int, b int, x char(200))

set nocount on
declare @i int
set @i = 0

while @i < 1000000
  begin
    insert T1 values(@i, @i, @i)
    set @i = @i + 1
  end

select * into T2 from T1
select * into T3 from T1

create unique clustered index T2a on T2(a)
create unique clustered index T3a on T3(a)

select * from T1 join T2 on T1.b = T2.a where T1.a < 100

Rows	Executes
100	1	|--Parallelism(Gather Streams)
100	2	|--Nested Loops(Inner Join, OUTER REFERENCES:([T1].[b], [Expr1007]) OPTIMIZED)
100	2	|--Table Scan(OBJECT:([T1]), WHERE:([T1].[a]<(100)))
100	100	|--Clustered Index Seek(OBJECT:([T2].[T2a]), SEEK:([T2].[a]=[T1].[b]) ORDERED FORWARD)

Сразу заметим, что в плане виден только один оператор Exchange (оператор, указывающий на параллелизм, и обозначенный в этом плане, как Parallelism(Gather Streams)). Так как оператор параллелизма находится в корне плана запроса, все операторы в этом плане (соединение вложенных циклов, просмотр таблицы и поиск по кластерному индексу) будут выполняться в нескольких параллельных потоках.

Индекс на T1 не был создан сознательно. Отсутствие индекса приводит к тому, что для выборки строк будет выполнен просмотр всей таблицы и потом к выборке будет применён предикат с оценкой «T1.a < 100». Поскольку в T1 миллион строк, просмотр таблицы будет дорогостоящей операцией, и поэтому оптимизатор предпочтёт использование распараллеленного просмотра T1.

Заметьте, что просмотр таблицы T1 не располагается первым под оператором параллелизма. В плане запроса мы его видим на внешней стороне оператора соединения вложенных циклов, который как раз и расположен ниже оператора параллелизма. Однако, поскольку просмотр выполняется для внешней стороны соединения и потому что само соединение расположилось в плане запроса ниже места начала параллелизма (то есть, места сбора или перераспределения), для таблицы T1 будет применён распараллеленный просмотр.

Если вспомнить предыдущую статью, распараллеленный просмотр распределяет страницы между потоками динамически. Таким образом, строки при просмотре таблицы T1 также будут распределены между несколькими потоками. Впрочем, неизвестно, какие строки, в какие потоки будут распределены.

Так как этот запрос выполнялся со степенью параллелизма – DOP равным 2, на текстовом плане исполнения запроса мы видим, что в колонке «Executes» для просмотра таблицы и соединения (которые попали в один и тот же поток) стоит значение 2. Кроме того, просмотр с соединением возвращают в общей сложности 100 строк, хотя мы не можем сделать из этого плана вывод, сколько строк возвратил каждый из двух потоков (эту информацию можно получить, используя статистику в виде XML, о будет сказано ниже).

Далее, соединение обращается к внутренней таблице (в этом случае используется поиск по индексу T2), поиск выполняется для каждой из 100 строк, полученных из внешней таблицы. Тут мы имеем дело с маленькой хитростью в понимании представленного выше сценария. Мы видим, что у каждого из двух потоков свой экземпляр поиска по индексу. Также, в плане показано, что поиск по индексу расположен ниже оператора соединения, да и само соединение мы видим ниже оператора параллелизма, но тут не используется распараллеленный просмотр. Вместо просмотра оптимизатор указывает использовать два экземпляра поиска по индексу внутренней таблицы соединения. Эти экземпляры поиска выполняются независимо друг от друга, используя два разных набора строк внешней таблицы и разные коррелированные параметры. Как и в последовательном плане, мы видим 100 исполнений просмотров индекса: по одному для каждой строки внешней таблицы соединения. Независимо от комплектации соединения вложенных циклов со стороны внутренней таблицы, в плане исполнения запроса мы всегда будем видеть выбор последовательного сценария, точно такого же, как это было показано выше в нашем простом примере.

Усложнённый пример

В показанном выше примере SQL Server распараллеливает просмотр для того, чтобы равномерно распределить строки между потоками. В некоторых случаях, это сделать невозможно, и тогда SQL Server может добавить оператор цикличного (RoundRobin) параллелизма, который лучше подходит для распределения строк в некоторых сценариях. RoundRobin направляет каждый следующий пакет строк очередному, изменяющемуся по предопределённой и фиксированной последовательности, потоку. Вот пример, демонстрирующий подобную ситуацию:

select *
from (select top 100 * from T1 order by a) T1top
join T2 on T1top.b = T2.a

 |--Parallelism(Gather Streams)
    |--Nested Loops(Inner Join, OUTER REFERENCES:([T1].[b], [Expr1007]) WITH UNORDERED PREFETCH)
    |--Parallelism(Distribute Streams, RoundRobin Partitioning)
    | |--Top(TOP EXPRESSION:((100)))
    | |--Parallelism(Gather Streams, ORDER BY:([T1].[a] ASC))
    | |--Sort(TOP 100, ORDER BY:([T1].[a] ASC))
    | |--Table Scan(OBJECT:([T1]))
    |--Clustered Index Seek(OBJECT:([T2].[T2a]), SEEK:([T2].[a]=[T1].[b]) ORDERED FORWARD)

Основное отличие этого плана от плана из предыдущего примера в том, что последний использует «TOP 100». Выборка первой сотни может получить правильную оценку, только если поток имеет последовательный плана исполнения (тут нет возможности распилить данные для нескольких потоков, поскольку всё может вылиться в очень большое или наоборот, слишком малое число строк разных потоков). Таким образом, у нас добавляется обработка (например, распределяющая данные по потокам), обеспечивающая распараллеливание после TOP. В таких случаях невозможно задействовать распараллеленный просмотр для выборки строк потоков соединения. Вместо этого распараллеливание для этого соединения выполняется посредством «RoundRobin Partitioning» - круговой «дозировки», которая и поставляет строки для потоков соединения.

Возможные проблемы

У распараллеленного просмотра есть одно главное преимущество перед круговой «дозировкой», он автоматически и динамически балансирует рабочую нагрузку между потоками, в то время как круговая «дозировка» на такое не способна. Как уже было показано в предыдущей статье, если у запроса один поток исполняется медленнее других, распараллеленный просмотр может оказаться удачным решение для повышения производительности сценария.

Если в обслуживании запроса задействовано много потоков и выбрано небольшое количество страниц и/или строк, распараллеленный просмотр и круговая «дозировка» могут оказаться бессильны заставить все потоки соединения работать с высокой производительностью. Некоторые потоки могут не получить для себя строк и будут просто простаивать. Эта проблема наиболее заметна в распараллеленном просмотре, когда каждый поток одномоментно выдает несколько страниц, но делает это не так часто, как распараллеливание, которое одномоментно распределяет по одному пакету (что эквивалентно одной странице).

Мы можем наблюдать эту проблему в простом примере выше, анализируя данные XML статистики:

<RelOp NodeId="1" PhysicalOp="Nested Loops" LogicalOp="Inner Join" ...>

<RunTimeInformation>

<RunTimeCountersPerThread Thread="2" ActualRows="0" ... />

<RunTimeCountersPerThread Thread="1" ActualRows="100" ... />

<RunTimeCountersPerThread Thread="0" ActualRows="0" ... />

</RunTimeInformation>

...

</RelOp>

Все возвращаемые соединением строки обрабатывались потоком 1. Почему? У просмотра таблицы есть остаточный предикат “T1.a <100”. Этот предикат возвращает истину для первых 100 строк в таблице и ложь для остальных строк. Все (три) страницы, содержащие первые 100 строк, направлены в первый поток. Тут не возникает большой проблемы, так как внутренняя сторона соединения обходится довольно дёшево и вносит небольшой процент в суммарную стоимость запроса (по сравнению с просмотром таблицы, который составляет наибольший процент). Однако эта проблема могла бы стать более существенной, если бы внутренняя сторона запроса обходилась заметно дороже. Проблема особенно заметна с секционированными таблицами. О секционированных таблицах мы ещё поговорим в следующих статьях блога, а сейчас иллюстрацию упомянутой тут проблемы можно найти в статье блога SQL Server Development Customer Advisory Team: Partitioned Tables, Parallelism & Performance considerations