Hash join - Hash join

O hash join é um exemplo de algoritmo de junção e é usado na implementação de um sistema de gerenciamento de banco de dados relacional . Todas as variantes de algoritmos de hash join envolvem a construção de tabelas de hash a partir das tuplas de uma ou ambas as relações unidas e, subsequentemente, sondar essas tabelas de modo que apenas tuplas com o mesmo código de hash precisem ser comparadas quanto à igualdade em equijoins.

As junções de hash são normalmente mais eficientes do que as junções de loops aninhados, exceto quando o lado da prova da junção é muito pequeno. Eles requerem um predicado equijoin (um predicado que compara registros de uma tabela com aqueles da outra tabela usando uma conjunção de operadores de igualdade '=' em uma ou mais colunas).

Junção de hash clássico

O algoritmo de hash join clássico para uma junção interna de duas relações procede da seguinte maneira:

  • Primeiro, prepare uma tabela hash usando o conteúdo de uma relação, de preferência a que for menor após a aplicação de predicados locais. Essa relação é chamada de lado de construção da junção. As entradas da tabela de hash são mapeamentos do valor do atributo de junção (composto) para os atributos restantes dessa linha (os que forem necessários).
  • Assim que a tabela hash for construída, faça a varredura da outra relação (o lado da sonda). Para cada linha da relação de teste, encontre as linhas relevantes da relação de construção, olhando na tabela hash .

A primeira fase é normalmente chamada de fase de "construção" , enquanto a segunda é chamada de fase de "investigação" . Da mesma forma, a relação de junção na qual a tabela hash é construída é chamada de entrada de "construção", enquanto a outra entrada é chamada de entrada de "teste".

Esse algoritmo é simples, mas requer que a relação de junção menor caiba na memória, o que às vezes não é o caso. Uma abordagem simples para lidar com esta situação é o seguinte:

  1. Para cada tupla na entrada de construção
    1. Adicionar à tabela de hash na memória
    2. Se o tamanho da tabela hash for igual ao tamanho máximo da memória:
      1. Analise a entrada de teste e adicione tuplas de junção correspondentes à relação de saída
      2. Redefina a tabela de hash e continue examinando a entrada de compilação
  2. Faça uma varredura final da entrada de teste e adicione as tuplas de junção resultantes à relação de saída

Este é essencialmente o mesmo que o algoritmo de união de loop aninhado de bloco . Este algoritmo faz a varredura eventualmente mais vezes do que o necessário.

Grace hash join

Uma abordagem melhor é conhecida como "grace hash join", em homenagem à máquina de banco de dados GRACE para a qual foi implementado pela primeira vez.

Esse algoritmo evita examinar novamente toda a relação, primeiro particionando ambos e por meio de uma função hash, e gravando essas partições no disco. O algoritmo então carrega pares de partições na memória, constrói uma tabela hash para a relação particionada menor e investiga a outra relação em busca de correspondências com a tabela hash atual. Como as partições foram formadas por hash na chave de junção, deve ser o caso de qualquer tupla de saída de junção pertencer à mesma partição.

É possível que uma ou mais partições ainda não se encaixem na memória disponível, caso em que o algoritmo é aplicado recursivamente: uma função hash ortogonal adicional é escolhida para hash a grande partição em subpartições, que são então processadas como antes. Como isso é caro, o algoritmo tenta reduzir a chance de que ocorra formando as menores partições possíveis durante a fase inicial de particionamento.

Híbrido hash join

O algoritmo de junção de hash híbrido é um refinamento da junção de hash de graça que tira proveito de mais memória disponível. Durante a fase de particionamento, a junção de hash híbrida usa a memória disponível para duas finalidades:

  1. Para manter a página do buffer de saída atual para cada uma das partições
  2. Para manter uma partição inteira na memória, conhecida como "partição 0"

Como a partição 0 nunca é gravada ou lida do disco, a junção de hash híbrida normalmente executa menos operações de E / S do que a junção de hash de graça. Observe que esse algoritmo é sensível à memória, porque há duas demandas concorrentes de memória (a tabela de hash para a partição 0 e os buffers de saída para as partições restantes). A escolha de uma tabela hash muito grande pode fazer com que o algoritmo sofra uma recursão porque uma das partições diferentes de zero é muito grande para caber na memória.

Hash anti-join

Hash joins também podem ser avaliados para um predicado anti-join (um predicado que seleciona valores de uma tabela quando nenhum valor relacionado é encontrado na outra). Dependendo dos tamanhos das tabelas, diferentes algoritmos podem ser aplicados:

Hash esquerdo anti-join

  • Prepare uma tabela hash para o lado NOT IN da junção.
  • Examine a outra tabela, selecionando todas as linhas em que o atributo de junção faz hash para uma entrada vazia na tabela de hash.

Isso é mais eficiente quando a tabela NOT IN é menor do que a tabela FROM

Hash anti-join à direita

  • Prepare uma tabela hash para o lado FROM da junção.
  • Faça a varredura da tabela NOT IN , removendo os registros correspondentes da tabela de hash em cada hit de hash
  • Retorne tudo o que deixou na tabela de hash

Isso é mais eficiente quando a tabela NOT IN é maior do que a tabela FROM

Hash semi-join

A semi-junção de hash é usada para retornar os registros encontrados na outra tabela. Ao contrário da junção simples, ele retorna cada registro correspondente da tabela principal apenas uma vez, não considerando quantas correspondências existem na tabela IN .

Tal como acontece com o anti-join, o semi-join também pode ser à esquerda e à direita:

Hash esquerdo semi-junção

  • Prepare uma tabela hash para o lado IN da junção.
  • Faça a varredura na outra tabela, retornando todas as linhas que produzem um resultado hash.

Os registros são retornados logo após produzirem um hit. Os registros reais da tabela hash são ignorados.

Isso é mais eficiente quando a tabela IN é menor do que a tabela FROM

Hash semi-junção à direita

  • Prepare uma tabela hash para o lado FROM da junção.
  • Faça a varredura da tabela IN , retornando os registros correspondentes da tabela hash e removendo-os

Com esse algoritmo, cada registro da tabela hash (ou seja, tabela FROM ) pode ser retornado apenas uma vez, pois é removido após ser retornado.

Isso é mais eficiente quando a tabela IN é maior do que a tabela FROM

Veja também

Referências

  1. ^ DeWitt, DJ; Katz, R .; Olken, F .; Shapiro, L .; Stonebraker, M .; Wood, D. (junho de 1984). "Técnicas de implementação para sistemas de banco de dados de memória principal". Proc. ACM SIGMOD Conf . 14 (4): 1–8. doi : 10.1145 / 971697.602261 .

links externos