Resgate agregado de hash

A junção de hash e a agregação de hash usam o mesmo código de operador internamente, embora uma agregação de hash use apenas uma única entrada (compilação). A operação básica do agregado de hash é descrita por Craig Freedman :

Assim como na junção de hash, a agregação 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 compilação, portanto, o requisito total de memória é proporcional ao número e tamanho das linhas de compilação. O número de linhas que se unem e a cardinalidade de saída da junção não afetam o requisito de memória da junção. Com um agregado de hash, armazenamos uma linha para cada grupo, de modo que o requisito total de memória seja realmente 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, precisamos de menos memória. Se tivermos mais valores exclusivos do grupo por coluna(s) e mais grupos, precisamos de mais memória.

Ele continua falando sobre recursão de hash:

Então, o que acontece se ficarmos sem memória? Novamente, como a junção de hash, se ficarmos sem memória, devemos começar a derramar linhas para tempdb. Derramamos um ou mais buckets ou partições, incluindo quaisquer resultados parcialmente agregados junto com quaisquer novas linhas adicionais que tenham hash para os buckets ou partições derramados. Embora não tentemos agregar as novas linhas derramadas, fazemos o hash e as dividimos em vários buckets ou partições. Assim que terminarmos de processar todos os grupos de entrada, produzimos os grupos na memória concluídos e repetimos o algoritmo lendo e agregando uma partição despejada de cada 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 se repetir muitas 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 iterador de hash antes de forçar o resgate?

O valor é uma constante, codificada no produto, e seu valor é cinco (5). Isso significa que antes que o operador de varredura de hash 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, devem ter ocorrido cinco tentativas anteriores de subdividir a partição original em partições menores.

O "operador de varredura de hash" mencionado há uma referência à classe interna CQScanHashem sqlmin.dll. Esta classe encabeça a implementação do operador de hash (em todas as suas formas, incluindo agregações 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 de árvore b inicialmente vazio nos valores de hash. Cada linha de uma única partição hash derramada anteriormente é pesquisada no índice b-tree e inserida (novo grupo) ou atualizada (mantendo agregações) conforme apropriado.

Essa série de inserções não ordenadas em uma b-tree também pode ser vista como uma ordenação por inserção ou como uma pesquisa de loops aninhados indexados.

Em qualquer caso, é garantido que esse algoritmo de fallback seja concluído eventualmente sem alocar mais memória. Pode exigir várias passagens se o espaço disponível para a b-tree não for suficiente para conter todas as chaves de agrupamento e agregados da partição de estouro.

Assim que a memória disponível para conter o índice b-tree estiver esgotada, quaisquer outras linhas (da partição derramada atual) são enviadas 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 de hash terminou. Alguns detalhes de processamento podem ser observados com o sinalizador de rastreamento não documentado 7357.