Qual índice usar com muitos valores duplicados?

BÁrvore

Meu problema aqui é que o índice BTree será enorme, pois de fato ele armazenará valores duplicados (também tem, pois não pode assumir que a tabela está classificada fisicamente). Se o BTree for enorme eu acabo tendo que ler tanto o índice quanto as partes da tabela que o índice aponta também...

Não necessariamente — Ter um índice btree que está 'cobrindo' será o tempo de leitura mais rápido, e se isso é tudo que você quer (ou seja, se você pode pagar pelo armazenamento extra), então é sua melhor aposta.

BRIN

Meu entendimento é que posso ter um pequeno índice aqui às custas de ler páginas inúteis. Usar um pequeno pages_per_rangesignifica que o índice é maior (o que é um problema com o BRIN já que preciso ler todo o índice), ter um grande pages_per_rangesignifica que vou ler muitas páginas inúteis.

Se você não pode arcar com a sobrecarga de armazenamento de um índice btree de cobertura, o BRIN é ideal para você, porque você já possui clustering (isso é crucial para que o BRIN seja útil). Os índices BRIN são minúsculos , portanto, todas as páginas provavelmente estarão na memória se você escolher um valor adequado de pages_per_range.

Existe uma fórmula mágica para encontrar um bom valor de pages_per_range que leve em consideração esses trade-offs?

Nenhuma fórmula mágica, mas comece com um tamanho pages_per_range um pouco menor do que a média (em páginas) ocupada pelo avalor médio. Você provavelmente está tentando minimizar: (número de páginas BRIN verificadas)+(número de páginas heap verificadas) para uma consulta típica. Procure Heap Blocks: lossy=nno plano de execução pages_per_range=1e compare com outros valores para pages_per_range— ou seja, veja quantos blocos de heap desnecessários estão sendo verificados.

GIN/GiST

Não tenho certeza se eles são relevantes aqui, pois são usados ​​principalmente para pesquisa de texto completo, mas também ouvi dizer que eles são bons em lidar com chaves duplicadas. Um índice GIN/ ajudaria aqui?GiST

Pode valer a pena considerar o GIN, mas provavelmente não o GiST - no entanto, se o agrupamento natural for realmente bom, o BRIN provavelmente será uma aposta melhor.

Aqui está uma comparação de amostra entre os diferentes tipos de índice para dados fictícios um pouco como o seu:

tabela e índices:

create table foo(a,b,c) as
select *, lpad('',20)
from (select chr(g) a from generate_series(97,122) g) a
     cross join (select generate_series(1,100000) b) b
order by a;
create index foo_btree_covering on foo(a,b);
create index foo_btree on foo(a);
create index foo_gin on foo using gin(a);
create index foo_brin_2 on foo using brin(a) with (pages_per_range=2);
create index foo_brin_4 on foo using brin(a) with (pages_per_range=4);
vacuum analyze;

tamanhos de relação:

select relname "name", pg_size_pretty(siz) "size", siz/8192 pages, (select count(*) from foo)*8192/siz "rows/page"
from( select relname, pg_relation_size(C.oid) siz
      from pg_class c join pg_namespace n on n.oid = c.relnamespace
      where nspname = current_schema ) z;

nome | tamanho | páginas | linhas/página
:----------------- | :------ | ----: | --------:
foo | 149 MB | 19118 | 135
foo_btree_covering | 56MB | 7132 | 364
foo_btree | 56MB | 7132 | 364
foo_gin | 2928kB | 366 | 7103
foo_brin_2 | 264kB | 33 | 78787
foo_brin_4 | 136kB | 17 | 152941

cobrindo btree:

explain analyze select sum(b) from foo where a='a';

| PLANO DE CONSULTA |
| :------------------------------------------------- -------------------------------------------------- ------------------------------------------- |
| Agregado (custo=3282.57..3282.58 linhas=1 largura=8) (tempo real=45.942..45.942 linhas=1 voltas=1) |
| -> Index Only Scan usando foo_btree_covering em foo (cost=0.43..3017.80 rows=105907 width=4) (tempo real=0.038..27.286 rows=100000 loops=1) |
| Índice Cond: (a = 'a'::texto) |
| Buscas de pilha: 0 |
| Tempo de planejamento: 0,099 ms |
| Tempo de execução: 45,968 ms |

btree simples:

drop index foo_btree_covering;
explain analyze select sum(b) from foo where a='a';

| PLANO DE CONSULTA |
| :------------------------------------------------- -------------------------------------------------- ----------------------------- |
| Agregado (custo=4064.57..4064.58 linhas=1 largura=8) (tempo real=54.242..54.242 linhas=1 voltas=1) |
| -> Varredura de índice usando foo_btree em foo (custo=0,43..3799.80 linhas=105907 largura=4) (tempo real=0,037..33.084 linhas=100000 loops=1) |
| Índice Cond: (a = 'a'::texto) |
| Tempo de planejamento: 0,135 ms |
| Tempo de execução: 54,280 ms |

BRIN pages_per_range=4:

drop index foo_btree;
explain analyze select sum(b) from foo where a='a';

| PLANO DE CONSULTA |
| :------------------------------------------------- -------------------------------------------------- ----------------------------- |
| Agregado (custo=21595.38..21595.39 linhas=1 largura=8) (tempo real=52.455..52.455 linhas=1 loops=1) |
| -> Bitmap Heap Scan on foo (custo=888.78..21330.61 linhas=105907 largura=4) (tempo real=2.738..31.967 linhas=100000 loops=1) |
| Verifique novamente Cond: (a = 'a'::text) |
| Linhas Removidas pela Verificação do Índice: 96 |
| Blocos de pilha: com perdas=736 |
| -> Varredura de Índice de Bitmap em foo_brin_4 (custo=0.00..862.30 linhas=105907 largura=0) (tempo real=2.720..2.720 linhas=7360 loops=1) |
| Índice Cond: (a = 'a'::texto) |
| Tempo de planejamento: 0,101 ms |
| Tempo de execução: 52,501 ms |

BRIN pages_per_range=2:

drop index foo_brin_4;
explain analyze select sum(b) from foo where a='a';

| PLANO DE CONSULTA |
| :------------------------------------------------- -------------------------------------------------- ----------------------------- |
| Agregado (custo=21659.38..21659.39 linhas=1 largura=8) (tempo real=53.971..53.971 linhas=1 voltas=1) |
| -> Varredura de Heap de Bitmap em foo (custo=952.78..21394.61 linhas=105907 largura=4) (tempo real=5.286..33.492 linhas=100.000 loops=1) |
| Verifique novamente Cond: (a = 'a'::text) |
| Linhas Removidas pela Verificação do Índice: 96 |
| Blocos de pilha: com perdas=736 |
| -> Bitmap Index Scan em foo_brin_2 (custo=0.00..926.30 linhas=105907 largura=0) (tempo real=5.275..5.275 linhas=7360 loops=1) |
| Índice Cond: (a = 'a'::texto) |
| Tempo de planejamento: 0,095 ms |
| Tempo de execução: 54,016 ms |

GIN:

drop index foo_brin_2;
explain analyze select sum(b) from foo where a='a';

| PLANO DE CONSULTA |
| :------------------------------------------------- -------------------------------------------------- ------------------------------ |
| Agregado (custo=21687.38..21687.39 linhas=1 largura=8) (tempo real=55.331..55.331 linhas=1 loops=1) |
| -> Bitmap Heap Scan on foo (custo=980.78..21422.61 linhas=105907 largura=4) (tempo real=12.377..33.956 linhas=100.000 loops=1) |
| Verifique novamente Cond: (a = 'a'::text) |
| Blocos de pilha: exato=736 |
| -> Bitmap Index Scan em foo_gin (custo=0.00..954.30 linhas=105907 largura=0) (tempo real=12.271..12.271 linhas=100.000 loops=1) |
| Índice Cond: (a = 'a'::texto) |
| Tempo de planejamento: 0,118 ms |
| Tempo de execução: 55,366 ms |

dbfiddle aqui

Além de btree e brin que parecem as opções mais sensatas, algumas outras opções exóticas que podem valer a pena investigar - elas podem ser úteis ou não no seu caso:

• INCLUDEíndices . Eles estarão - esperançosamente - na próxima versão principal (10) do Postgres, por volta de setembro de 2017. Um índice em (a) INCLUDE (b)tem a mesma estrutura que um índice em, (a)mas inclui nas páginas folha, todos os valores de b(mas não ordenados). O que significa que você não pode usá-lo, por exemplo, para SELECT * FROM t WHERE a = 'a' AND b = 2 ;. O índice pode ser usado, mas enquanto um (a,b)índice encontrará as linhas correspondentes com uma única busca, o índice de inclusão terá que passar pelos valores (possivelmente 100K como no seu caso) que correspondem a = 'a'e verificar os bvalores.
  Por outro lado, o índice é um pouco menor que o (a,b)índice e você não precisa da ordem bpara que sua consulta calcule SUM(b). Você também pode ter, por exemplo,(a) INCLUDE (b,c,d)que pode ser usado para consultas semelhantes às suas que agregam em todas as 3 colunas.

• Índices filtrados (parciais) . Uma sugestão que pode parecer um pouco louca ^* no início:

  CREATE INDEX flt_a  ON t (b) WHERE (a = 'a') ;
  ---
  CREATE INDEX flt_xy ON t (b) WHERE (a = 'xy') ;
  

  Um índice para cada avalor. No seu caso, cerca de 100 mil índices. Embora isso pareça muito, considere que cada índice será muito pequeno, tanto em tamanho (número de linhas) quanto em largura (já que armazenará apenas bvalores). Em todos os outros aspectos, porém, ele (os 100K índices juntos) atuará como um índice b-tree (a,b)enquanto usa o espaço de um (b)índice.
  A desvantagem é que você mesmo terá que criá-los e mantê-los, cada vez que um novo valor de afor adicionado à tabela. Como sua tabela é bastante estável, sem muitas (ou nenhuma) inserções/atualizações, isso não parece ser um problema.

• Tabelas de resumo. Como a tabela é bastante estável, você sempre pode criar e preencher uma tabela de resumo com os agregados mais comuns necessários ( sum(b), sum(c), sum(d), avg(b), count(distinct b), etc). Ele será pequeno (apenas 100 mil linhas) e só precisará ser preenchido uma vez e atualizado somente quando as linhas forem inseridas/atualizadas/excluídas na tabela principal.

^{*: ideia copiada desta empresa que executa 10 milhões de índices em seu sistema de produção: The Heap: Running 10 Million Postgresql Indexes In Production (e contando) .}