По материалам статьи Craig Freedman: Hash Aggregate

В двух своих предыдущих статьях, я писал об операторе агрегации потока. Агрегат потока хорошо подходит для скалярных агрегатов и для агрегации с использованием индекса, который обеспечивает порядок сортировки по столбцу(цам) предложения GROUP BY или когда сортировка задана явно (например, указано предложение ORDER BY).

Следующий оператор агрегации, это агрегат хэша, который подобен хэш-соединению. Он не требует указания порядка сортировки, зато потребляет память и устанавливает блокировку (то есть, он не выдаёт результатов, пока не обработает всё, что у него на входе). Агрегат хэша является лучшим выбором для эффективной агрегации очень больших наборов данных.

Вот так выглядит алгоритма агрегата хэша в псевдокоде:

for each input row
  begin
      calculate hash value on group by column(s)
      check for a matching row in the hash table
    if   we do not find a match
        insert a new row into the hash table
      else
        update the matching row with the input row
  end
output all rows in   the hash table

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

Память и её сброс

Как и хэш-соединение, агрегат хэша требователен к памяти. Перед исполнением запроса с агрегатом хэша, SQL Server оценивает количество элементов, чтобы понять, сколько памяти потребуется для исполнения этого запроса. В случае с хэш-соединением, будет храниться каждая скомпонованная строка, и поэтому требование к объёму используемой памяти будет пропорционально числу и размеру скомпонованных строк. Число соединяемых строк и количество элементов на выходе соединения никак не влияет на необходимый объем и конфигурацию памяти для соединения. Для агрегата хэша хранится по одной строке для каждой группы, так что требование к общему объёму памяти фактически пропорционально числу и размеру выводимых групп или строк. Если уникальных значений столбца(цов) в предложении GROUP BY не много, будет меньше групп и потребуется меньше памяти. Если уникальных значений столбца(цов) в предложении GROUP BY много, групп тоже будет много и потребуется больше памяти.
Что случается, если запрос выйдет за пределы доступной памяти? Как и в случае с хэш-соединением, при выходе за границы памяти начинается сброс строк в tempdb. Сброшены будут одна или несколько областей памяти или секций, включая некоторое число частично агрегированных результатов вместе со сброшенными хэшами дополнительных новых строк, попавших в эти области памяти или секции. Хотя сброшенные новые строки не будут в этот момент соединяться, их хеши будут разделены на несколько областей памяти или секций. По завершению процессинга всех поступивших на вход групп, подготовленные группы попадают в оперативную память и будут в цикле считываться и соединяться одновременно сразу все сброшенные секции. Разделив сброшенные строки на несколько секций мы уменьшаем размер каждой такой секции и, таким образом, уменьшаем риск того, что цикл повториться слишком много раз.

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

Примеры

Оптимизатор имеет тенденцию избирать агрегат хэша для таблиц с большим числом строк и групп. Например, имея только 100 строк и 10 групп, мы получаем сортировку и агрегат потока:

create table   t (a int, b int,   c int)

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

while @i < 100
  begin
    insert t values (@i   % 10, @i, @i * 3)
    set @i = @i + 1
  end

select sum(b)   from t group by a

^{|--Compute Scalar(DEFINE:([Expr1004]=CASE WHEN [Expr1010]=(0)}

^{| THEN NULL ELSE [Expr1011] END))}

^{|--Stream Aggregate(GROUP BY:([t].[a])}

^{| DEFINE:([Expr1010]=COUNT_BIG([t].[b]),}

^{| [Expr1011]=SUM([t].[b])))}

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

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

Но когда строк становится 1000, а число групп достигает 100, мы получаем в плане агрегат хэша:

truncate table   t

declare @i int
set @i = 100

while @i < 1000
  begin
    insert t values (@i   % 100, @i, @i * 3)
    set @i = @i + 1
  end

select sum(b)   from t group by a

^{|--Compute Scalar(DEFINE:([Expr1004]=CASE WHEN [Expr1010]=(0)}

^{| THEN NULL ELSE [Expr1011] END))}

^{|--Hash Match(Aggregate, HASH:([t].[a]), RESIDUAL:([t].[a] = [t].[a])}

^{| DEFINE:([Expr1010]=COUNT_BIG([t].[b]),}

^{| [Expr1011]=SUM([t].[b])))}

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

Обратите внимание, что хэш берётся по столбцу GROUP BY. Предикат RESIDUAL в агрегате хэша используется для сравнения строк в хеш-таблице, чтобы ввести их, если мы имеем коллизии значений хеш-функции.

Также обратите внимание, что при использовании агрегата хэша отпадает необходимость в сортировке. Сортировка потребует больше памяти, чем агрегат хэша, так как мы должны сортировать 1000 строк, а агрегат хэша нуждаться в памяти только для 100 групп. Однако, если мы явно укажем сортировку, используя для этого в запросе предложение ORDER BY, мы снова получаем агрегат потока:

select sum(b)   from t group by a order by a

^{|--Compute Scalar(DEFINE:([Expr1004]=CASE WHEN [Expr1010]=(0)}

^{| THEN NULL ELSE [Expr1011] END))}

^{|--Stream Aggregate(GROUP BY:([t].[a])}

^{| DEFINE:([Expr1010]=COUNT_BIG([t].[b]),}

^{| [Expr1011]=SUM([t].[b])))}

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

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

Если таблица становится достаточно большой, а число групп остается достаточно маленьким, в конечном счете, оптимизатор решит, что дешевле использовать агрегат хэша и сортировку после того, как выполнится агрегация. Например, имея 10000 строк и только 100 групп, оптимизатор решит, что лучше взять хэш и потом сортировать только 100 групп, чем сортировать целых 10000 строк:

truncate table   t

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

while @i < 10000
  begin
    insert t values (@i   % 100, @i, @i * 3)
    set @i = @i + 1
  end

select sum(b)   from t group by a order by a

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

^{|--Compute Scalar(DEFINE:([Expr1004]=CASE WHEN [Expr1010]=(0)}

^{| THEN NULL ELSE [Expr1011] END))}

^{|--Hash Match(Aggregate, HASH:([t].[a]),}

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

^{| DEFINE:([Expr1010]=COUNT_BIG([t].[b]),}

^{| [Expr1011]=SUM([t].[b])))}

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

DISTINCT

Точно так же как и для агрегата потока, агрегат хэша может использоваться для устранения дубликатов:

select distinct   a from t

^{|--Hash Match(Aggregate, HASH:([t].[a]), RESIDUAL:([t].[a] = [t].[a]))}

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

Или несколько иначе, если мы хотим рассмотреть более интересный случай:

select sum(distinct b), sum(distinct c) from t group by a

^{|--Hash Match(Inner Join, HASH:([t].[a])=([t].[a]), RESIDUAL:([t].[a] = [t].[a]))}

^{|--Compute Scalar(DEFINE:([t].[a]=[t].[a]))}

^{| |--Compute Scalar(DEFINE:([Expr1004]=CASE WHEN [Expr1018]=(0)}

^{| | THEN NULL ELSE [Expr1019] END))}

^{| |--Hash Match(Aggregate, HASH:([t].[a]),}

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

^{| | DEFINE:([Expr1018]=COUNT_BIG([t].[b]),}

^{| | [Expr1019]=SUM([t].[b])))}

^{| |--Hash Match(Aggregate, HASH:([t].[a], [t].[b]),}

^{| | RESIDUAL:([t].[a] = [t].[a]}

^{| | AND [t].[b] = [t].[b]))}

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

^{|--Compute Scalar(DEFINE:([t].[a]=[t].[a]))}

^{|--Compute Scalar(DEFINE:([Expr1005]=CASE WHEN [Expr1020]=(0)}

^{| THEN NULL ELSE [Expr1021] END))}

^{|--Hash Match(Aggregate, HASH:([t].[a]),}

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

^{| DEFINE:([Expr1020]=COUNT_BIG([t].[c]),}

^{| [Expr1021]=SUM([t].[c])))}

^{|--Hash Match(Aggregate, HASH:([t].[a], [t].[c]),}

^{| RESIDUAL:([t].[a] = [t].[a]}

^{| AND [t].[c] = [t].[c]))}

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

Этот план логически эквивалентен последнему плану в моей статье про агрегат потока, но тут вместо сортировок, агрегатов потока и соединения слиянием используется агрегат хэша и хэш-соединение. Мы имеем два агрегата хэша, которые устраняют дубликаты (один для "distinct b" и один для "distinct c") и еще два агрегата хэша для вычисления обоих сумм. Хэш-соединение "склеивает" результирующие строки вместе, чтобы сформировать конечный результат.

Подсказки

Вы можете использовать подсказки оптимизатору "ORDER GROUP" и "HASH GROUP" для того, чтобы принудительно вызвать агрегат потока или агрегат хэша соответственно. Эти подсказки затрагивают все операции агрегации во всём запросе. Например:

select sum(b)   from t group by a option(order group)
select sum(b)   from t group by a option(hash group)

SQL Profiler

Вы можете использовать имеющийся в приложении SQL Profiler класс сообщений "Hash Warning" (в категории "Errors and Warnings") для обнаружения запросов с хэш-соединением или когда осуществляется сброс агрегата хэша. Сброс порождает ввод-вывод и может неблагоприятно повлиять на производительность. Для получения более подробной информации об этих сообщения см. Books Online.