A junção de hash e o agregado de hash usam o mesmo código do operador internamente, embora um agregado de hash use apenas uma única entrada (compilação). A operação básica do agregado de hash é descrita por Craig Freedman :
Como na junção de hash, o agregado de hash requer memória. Antes de executar uma consulta com um agregado de hash, o SQL Server usa estimativas de cardinalidade para estimar quanta memória precisamos para executar a consulta. Com uma junção de hash, armazenamos cada linha de construção, para que o requisito de memória total seja proporcional ao número e tamanho das linhas de construção. O número de linhas que ingressam e a cardinalidade de saída da associação não afetam os requisitos de memória da associação. Com um agregado de hash, armazenamos uma linha para cada grupo, para que o requisito total de memória seja proporcional ao número e tamanho dos grupos ou linhas de saída. Se tivermos menos valores exclusivos do grupo por coluna (s) e menos grupos, precisaremos de menos memória. Se tivermos mais valores exclusivos do grupo por coluna (s) e mais grupos, precisaremos de mais memória.
Ele continua falando sobre a recursão de hash:
Então, o que acontece se ficarmos sem memória? Novamente, como junção de hash, se ficarmos sem memória, devemos começar a espalhar linhas para o tempdb. Derramamos um ou mais buckets ou partições, incluindo quaisquer resultados parcialmente agregados, além de novas linhas adicionais que hash para os buckets ou partições derramados. Embora não tentemos agregar as novas linhas derramadas, nós as misturamos e as dividimos em vários buckets ou partições. Depois de concluir o processamento de todos os grupos de entrada, produzimos os grupos de memória concluídos e repetimos o algoritmo lendo e agregando uma partição derramada por vez. Ao dividir as linhas derramadas em várias partições, reduzimos o tamanho de cada partição e, assim, reduzimos o risco de que o algoritmo precise repetir várias vezes.
Resgate
O resgate de hash é levemente documentado, mas mencionado por Nacho Alonso Portillo em Qual é o nível máximo de recursão para o hash iterador antes de forçar o resgate?
O valor é uma constante, codificado no produto, e seu valor é cinco (5). Isso significa que, antes que o operador de hash scan recorra a um algoritmo baseado em classificação para qualquer subpartição que não se encaixe na memória concedida do espaço de trabalho, cinco tentativas anteriores de subdividir a partição original em partições menores devem ter ocorrido.
O "operador de varredura de hash" mencionado é uma referência à classe interna CQScanHashem sqlmin.dll. Essa classe lidera a implementação do operador de hash (em todas as suas formas, incluindo agregados parciais e fluxos distintos) que vemos nos planos de execução.
Algoritmo de resgate
Isso nos leva ao cerne de suas perguntas - o que exatamente o algoritmo de resgate faz? É "baseado em classificação" ou baseado em "uma espécie de coisa de loops aninhados"?
É indiscutivelmente ambos, dependendo do seu ponto de vista. Quando a recursão de hash atinge o nível 5, a partição de hash na memória muda de uma tabela de hash para um índice b-tree inicialmente vazio nos valores de hash. Cada linha de uma única partição de hash derramada anteriormente é pesquisada no índice da árvore b e inserida (novo grupo) ou atualizada (mantendo agregados) conforme apropriado.
Essa série de inserções não ordenadas em uma árvore-b também pode ser vista como uma classificação de inserção ou como uma pesquisa de loops aninhados indexados.
De qualquer forma, é garantido que esse algoritmo de fallback seja concluído eventualmente, sem alocar mais memória. Pode ser necessário várias passagens se o espaço disponível para a árvore b não for suficiente para conter todas as chaves de agrupamento e agregados da partição de estouro.
Depois que a memória disponível para armazenar o índice b-tree é esgotada, qualquer outra linha (da partição atual derramada) é enviada para uma única nova partição tempdb (que é garantidamente menor) e o processo se repete conforme necessário. O nível de derramamento permanece em 5 porque a recursão do hash terminou. Alguns detalhes de processamento podem ser observados com o sinalizador de rastreio não documentado 7357.
