Use GIN para indexar cadeias de bits

Em uma pesquisa, gostaria de obter todas as linhas que correspondem exatamente à string de bits.

Use um índice B-Tree, o tipo padrão. Não vejo caso para um índice GIN aqui.

Até 1.000 bits resultam em até 133 bytes (ou um pouco mais) de tamanho de armazenamento em disco para um bit varyingtipo .

SELECT pg_column_size(repeat('1', 1000)::varbit)  -- 133

Nem tanto . Um índice B-Tree simples deve servir. Mas talvez a coluna seja grande o suficiente para que os seguintes truques melhorem o desempenho.

Se uma pequena parte da coluna de cadeia de bits for distinta o suficiente para restringir sua pesquisa a poucos resultados, um índice em uma expressão pode fornecer melhor desempenho, porque o índice menor pode caber na RAM e é mais rápido de processar. Não se preocupe com mesas pequenas, a sobrecarga consumiria o benefício. Mas pode fazer uma grande diferença para mesas grandes .

Exemplo

tabela dada:

CREATE TABLE tbl(id serial PRIMARY KEY, b_col varbit);

Se os primeiros 10 bits forem suficientes para restringir uma pesquisa a alguns resultados, você poderá criar um índice na expressão b_col::bit(10) . A conversão parabin(n) trunca o bitstringbit para n.

CREATE INDEX tbl_b_col10_idx ON tbl ((b_col::bit(10)))

Parênteses extras são necessários para o operador de conversão em uma definição de índice. Ver:

• Como criar um índice em uma propriedade json inteira no postgres

Então, em vez da consulta

SELECT * FROM tbl WHERE b_col = '1111011110111101'::varbit; -- 16 bit

Você usaria:

SELECT *
FROM   tbl
WHERE  b_col::bit(10) = '1111011110111101'::bit(10) -- utilize index
AND    b_col = '1111011110111101'::varbit;  -- filter to exact match

Esteja ciente de que valores mais curtos são preenchidos com 0's à direita (bits menos significativos) quando convertidos em bit(n).

Em um aplicativo do mundo real, isso começa a fazer sentido com várias centenas de bits. Teste o ponto de virada.

Otimize ainda mais

Como a maioria das instalações opera com MAXALIGN8 bytes (sistema operacional de 64 bits) ( mais detalhes aqui ), o tamanho do índice é o mesmo para todos os dados que não excedam 8 bytes. Efetivamente, por linha:

identificador de item de 4 bytes
 8 bytes para o cabeçalho da tupla de índice (ou 23 + 1 byte para tuplas de heap)
 ? espaço real para dados
 ? preenchimento para o múltiplo mais próximo de 8 bytes

Mais algumas despesas gerais menores por página e índice/tabela. Detalhes no manual ou nesta resposta relacionada em stackoverflow .

Portanto, você deve ser capaz de otimizar ainda mais a abordagem acima. Pegue o primeiro 64 bits (ou o último ou o que for mais distinto e funcione para você), converta-o biginte crie um índice nessa expressão.

CREATE INDEX tbl_b_col64_idx ON tbl ((b_col::bit(64)::bigint))

Eu lancei duas vezes ( b_col::bit(64)::bigint) pois não há elenco definido entre varbite bigint. Detalhes nesta resposta relacionada no SO:

• Converter hexadecimal na representação de texto em número decimal

Efetivamente, esta é apenas uma função de hash muito rápida e simples, onde o valor de hash também permite procurar intervalos de valores. Dependendo dos requisitos exatos, você pode ir um passo além e usar qualquer IMMUTABLE função de hash semelhante md5(). Detalhes na resposta vinculada acima.

A consulta para ir junto com isso:

SELECT *
FROM   tbl
WHERE  b_col::bit(64)::bigint = '1111011110111101'::bit(64)::bigint -- utilize index
AND    b_col = '1111011110111101'::varbit;  -- narrow down to exact match

O índice resultante deve ser tão grande quanto o do primeiro exemplo, mas as consultas devem ser consideravelmente mais rápidas por três motivos:

• O índice normalmente retorna muito menos acessos (64 bits de informação versus 10 bits)

• O Postgres pode trabalhar com aritmética inteira, que deve ser mais rápida, mesmo para uma =operação simples. (Não testei para verificar isso.)

• O tipo integernão tem sobrecarga como varbit- 5 ou 8 bytes . (Na minha instalação 5 bytes para até 960 bits , 8 bytes para mais).
  Efetivamente, para manter o índice em seu tamanho mínimo, você só pode compactar 24 bits em um varbitíndice - em comparação com 64 bits de informação para um bigintíndice.

CLUSTER

Nesse caso, CLUSTERdeve melhorar o desempenho:

CLUSTER TABLE tbl USING tbl_b_col10_idx;

É uma operação única e deve ser repetida em intervalos de seu projeto. Certifique-se de ler o manual sobreCLUSTER se você quiser usar isso. Ou considere as ferramentas da comunidade como pg_repack ou pg_suqeeze . Detalhes:

• Configurando o PostgreSQL para desempenho de leitura

Se os primeiros 64 bits de seus valores forem exclusivos na maioria das vezes, CLUSTERisso dificilmente ajudará, pois a varredura de índice retornará uma única linha na maioria dos casos. Se não, CLUSTERvai ajudar muito . Consequentemente, o efeito será muito maior para o primeiro exemplo com o índice menos otimizado.