Início / dba / Perguntas / 62822
Accepted
Alexandros
Asked: 2014-04-10 04:10:30 +0800 CST

PostgreSQL, matrizes inteiras, índice para igualdade

  • 772

Eu tenho uma lista enorme de matrizes inteiras (300.000.000 registros) armazenadas no banco de dados Postgres 9.2. Desejo pesquisar com eficiência esses registros para uma correspondência exata (somente igualdade). Já ouvi falar do módulo intarray e dos índices gist-gin correspondentes. Gostaria de fazer as seguintes perguntas:

  • O PostgreSQL usa uma função hash para verificar a igualdade de arrays inteiros ou executa um algoritmo de força bruta comparando um a um os elementos do array?
  • Se o PostgreSQL usa uma função hash, existe algum código de função PostgreSQL para realmente obter o resultado da função hash para uma matriz específica?
  • Qual índice será melhor para tal tarefa? B-tree ou os índices gist-gin fornecidos pelo módulo intarray? O dataset será estático, ou seja, uma vez inseridos todos os registros não haverá mais inserções. Portanto, construir o índice/atualizar o tempo do índice não é importante para mim.
postgresql btree

2 respostas

  1. P: O PostgreSQL usa uma função hash para verificar a igualdade de arrays inteiros ou executa um algoritmo de força bruta comparando um a um os elementos do array?

    Não de acordo com funções e operadores de matriz no documento:

    As comparações de matriz comparam o conteúdo da matriz elemento por elemento, usando a função padrão de comparação de árvore B para o tipo de dados do elemento

    Nenhuma menção de hash.

    intarray fornece outros operadores, mas não substitui o operador de igualdade entre int[]. A função _int_same() mais próxima que ela expõe é semanticamente diferente (a ordem dos elementos não importa) e é implementada como classificação+comparação sequencial, não hashing.

    Felizmente, implementar uma pesquisa rápida baseada em hash no nível SQL não é difícil e, no seu caso (arrays grandes, sem atualizações, correspondência exata), pode até ser o método mais eficaz.

    Passos:

    1) escolha uma função hash. Eu sugeriria md5na representação de texto da matriz:

    create function arr_hash(int[]) returns bytea as
$$ select digest($1::text, 'md5');$$
language sql immutable;

    A função digest(text,text)faz parte da pgcryptoextensão. Comparado a md5ele tem a vantagem de produzir binário (16 bytes) em vez de hexadecimal (32 bytes) para um índice mais enxuto.

    2) crie um índice funcional:

    create index index_name on table_name(arr_hash(col_name));

    Será várias ordens de magnitude mais rápido do que um índice GIN para o tipo de conjunto de dados que você possui (na verdade, eu me preocuparia com a criação do índice GIN levando um tempo realmente irracional, mas tente).

    3) use assim:

    select 1 from table_name
 where arr_hash(col_name)=arr_hash('{10,20,30,...lot of values}'::int[])
 and   col_name='{10,20,30,...lot of values}'::int[];
    • 7
  2. Best Answer

    1) como você já descobriu, você não pode usar b-tree porque o tamanho do índice é maior que o tamanho da página

    2) dado:

    Como regra geral, um índice GIN é mais rápido para pesquisar do que um índice GiST, mas mais lento para criar ou atualizar; portanto, o GIN é mais adequado para dados estáticos e o GiST para dados atualizados com frequência.

    Você teria que usar o GIN. E não, o GIN não usa funções de hash nem um algoritmo de força bruta. É um índice reverso:

    Um índice GIN armazena um conjunto de pares (chave, lista de postagem), onde uma lista de postagem é um conjunto de IDs de linha em que a chave ocorre. O mesmo ID de linha pode aparecer em várias listas de postagem, pois um item pode conter mais de uma chave. Cada valor de chave é armazenado apenas uma vez, portanto, um índice GIN é muito compacto para casos em que a mesma chave aparece várias vezes.

    Internamente, um índice GIN contém um índice B-tree construído sobre chaves, onde cada chave é um elemento de um ou mais itens indexados (um membro de um array, por exemplo)

    • 2

relate perguntas