Como é possível que o Índice Hash não seja mais rápido que o Btree para pesquisas de igualdade?

8

Para todas as versões do Postgres que suportam a indexação de hash , há um aviso ou nota de que os índices de hash são "semelhantes ou mais lentos" ou "não melhores" que os índices btree , pelo menos até a versão 8.3. Dos documentos:

Versão 7.2 :

Nota: Devido à utilidade limitada dos índices de hash, um índice da árvore B geralmente deve ser preferido sobre um índice de hash. Não temos evidências suficientes de que os índices de hash sejam realmente mais rápidos que as árvores B, mesmo para comparações =. Além disso, os índices de hash exigem bloqueios mais grossos; consulte a Seção 9.7.

Versão 7.3 (e até 8.2) :

Nota: O teste mostrou que os índices de hash do PostgreSQL são semelhantes ou mais lentos que os índices da árvore B, e o tamanho do índice e o tempo de construção dos índices de hash são muito piores. Os índices de hash também sofrem desempenho ruim com alta simultaneidade. Por esses motivos, o uso do índice de hash é desencorajado.

Versão 8.3 :

Nota: O teste mostrou que os índices de hash do PostgreSQL não apresentam desempenho melhor que os índices da árvore B, e o tamanho do índice e o tempo de construção para os índices de hash são muito piores. Além disso, atualmente, as operações de índice de hash não são registradas no WAL, portanto, os índices de hash podem precisar ser reconstruídos com o REINDEX após uma falha no banco de dados. Por esses motivos, o uso do índice de hash é atualmente desencorajado.

Nesse segmento da versão 8.0 , eles afirmam que nunca encontraram um caso em que os índices de hash fossem realmente mais rápidos que o btree.

Mesmo na versão 9.2, o ganho de desempenho para qualquer coisa que não fosse escrever o índice real era quase nada, de acordo com esta postagem do blog (14 de março de 2016):
Hash Indexes on Postgres, de André Barbosa.

Minha pergunta é como isso é possível?

Por definição, os índices Hash são uma O(1)operação, onde uma btree é uma O(log n)operação. Então, como é possível que uma O(1)pesquisa seja mais lenta do que (ou até semelhante a) encontrar a ramificação correta e depois encontrar o registro correto?

Eu quero saber o que a teoria da indexação NUNCA poderia tornar isso uma possibilidade!

Sampson Crowley
fonte
A discussão mudou para o bate-papo .
ypercubeᵀᴹ

Respostas:

7

Os índices Btree baseados em disco são realmente O (log N), mas isso é praticamente irrelevante para matrizes de disco que se encaixam nesse sistema solar. Devido ao armazenamento em cache, eles são principalmente O (1) com uma constante muito grande mais O ((log N) -1) com uma constante pequena. Formalmente, isso é o mesmo que O (log N), porque constantes não importam na notação O grande. Mas eles realmente importam.

Grande parte da desaceleração nas pesquisas de índice de hash veio da necessidade de proteção contra corrupção ou conflitos causados ​​pelo redimensionamento da tabela de hash simultaneamente com as pesquisas. Até as versões recentes (todas as versões mencionadas estão comicamente desatualizadas), essa necessidade levou a constantes ainda mais altas e a uma concorrência bastante ruim. Muito mais horas-homem foram para a otimização da simultaneidade BTree do que a simultânea de hash.

jjanes
fonte
Obrigado. Estou muito consciente de quão longe passado sua data de validade dessas versões são, mas eu ainda estava curioso sobre como o desempenho foi tão para trás que eu teria esperado
Sampson Crowley
3

A pesquisa de hash é teoricamente uma O(1)operação quando o hash da chave é mapeado diretamente para o local físico do registro de destino. A maneira como funciona no Postgres, se bem entendi, é um pouco mais complicada: o hash da chave é mapeado para um balde que contém o OID que você está procurando. Um bucket pode potencialmente compreender mais de uma página, que você precisa varrer sequencialmente até encontrar sua chave específica (hash). É por isso que parece mais lento do que o esperado.

O arquivo README do método de acesso ao índice de hash no repositório de código-fonte possui todos os detalhes.

mustaccio
fonte
assim, basicamente, um índice de hash é um tipo de ramificação índice tanto quanto psql está em causa
Sampson Crowley
que realmente faz muito mais sentido sabendo que eles usam baldes para armazenar as chaves reais
Sampson Crowley
também obrigado pelo link para o leia-me. Eu não tinha idéia de quem existia no repo
Sampson Crowley
2
As páginas excedentes precisam ser pesquisadas linearmente e, nos piores casos, degenerados, pode haver um número ilimitado delas. Mas as pesquisas em uma página têm um número limitado de itens que podem existir em uma página, portanto, são O (1) por página excedente e usam uma pesquisa binária para que a constante também não seja muito ruim. Era realmente a disposição para tornar a simultaneidade das operações segura que era o gargalo.
jjanes
11
@AnoE - você ficará surpreso ... Sempre há uma troca entre desempenho e [desperdício de] recursos; em alguns casos, pode-se favorecer o desempenho.
mustaccio