1. Introdução

Esta série de artigos preocupa-se principalmente com índices no PostgreSQL.

Qualquer assunto pode ser considerado sob diferentes perspectivas. Discutiremos assuntos que devem interessar a um desenvolvedor de aplicativos que usa DBMS: quais índices estão disponíveis, por que existem tantos tipos diferentes deles e como usá-los para acelerar as consultas. Provavelmente, o tópico pode ser coberto em menos palavras, mas, em segredo, esperamos que um desenvolvedor curioso também se interesse por detalhes internos, principalmente porque a compreensão de tais detalhes permite não apenas adiar o julgamento de outros, mas também tirar conclusões. de sua preferência.

O desenvolvimento de novos tipos de índices está fora do escopo. Isso requer conhecimento da linguagem de programação C e pertence à experiência de um programador de sistemas, em vez de um desenvolvedor de aplicativos. Pelo mesmo motivo, quase não discutiremos interfaces de programação, mas focaremos apenas no que é importante para trabalhar com índices prontos para uso.

Neste artigo, discutiremos a distribuição de responsabilidades entre o mecanismo de indexação geral relacionado ao núcleo do DBMS e aos métodos individuais de acesso ao índice, que o PostgreSQL nos permite adicionar como extensões. No próximo artigo, discutiremos a interface do método de acesso e conceitos críticos, como classes e famílias de operadores. Após essa introdução longa, porém necessária, consideraremos detalhes da estrutura e aplicação de diferentes tipos de índices: Hash , B-tree , GiST , SP-GiST , GIN e RUM , BRIN e Bloom .

Antes de começar, gostaria de agradecer a Elena Indrupskaya por traduzir os artigos para o inglês.
As coisas mudaram um pouco desde a publicação original. Meus comentários sobre o estado atual das coisas são indicados assim.

Índices

No PostgreSQL, índices são objetos de banco de dados especiais, projetados principalmente para acelerar o acesso aos dados. São estruturas auxiliares: cada índice pode ser excluído e recriado novamente a partir das informações na tabela. Às vezes, você pode ouvir que um DBMS pode funcionar sem índices, embora lentamente. No entanto, esse não é o caso, pois os índices também servem para impor algumas restrições de integridade.

Atualmente, seis tipos diferentes de índices estão embutidos no PostgreSQL 9.6, e mais um índice está disponível como uma extensão - graças a mudanças significativas na versão 9.6. Portanto, espere novos tipos de índices em um futuro próximo.

Apesar de todas as diferenças entre os tipos de índices (também chamados de métodos de acesso), cada um deles eventualmente associa uma chave (por exemplo, o valor da coluna indexada) às linhas da tabela que contêm essa chave. Cada linha é identificada por TID (tupla id), que consiste no número de blocos no arquivo e na posição da linha dentro do bloco. Dito isto, com a chave conhecida ou com algumas informações sobre ela, podemos ler rapidamente as linhas que podem conter as informações de nosso interesse sem verificar a tabela inteira.

É importante entender que um índice acelera o acesso a dados a um certo custo de manutenção. Para cada operação em dados indexados, seja inserção, exclusão ou atualização de linhas da tabela, os índices dessa tabela também precisam ser atualizados e na mesma transação. Observe que a atualização dos campos da tabela para os quais os índices não foram criados não resulta em atualização do índice; essa técnica é chamada de HOT (tuplas somente de pilha).

A extensibilidade implica algumas implicações. Para permitir a adição fácil de um novo método de acesso ao sistema, uma interface do mecanismo de indexação geral foi implementada. Sua principal tarefa é obter TIDs do método de acesso e trabalhar com eles:

Leia os dados das versões correspondentes das linhas da tabela.
Busque versões de linha TID por TID ou em um lote usando um bitmap pré-construído.
Verifique a visibilidade das versões de linha da transação atual, levando em consideração seu nível de isolamento.

O mecanismo de indexação está envolvido na execução de consultas. É chamado de acordo com um plano criado no estágio de otimização. O otimizador, classificando e avaliando diferentes maneiras de executar a consulta, deve entender os recursos de todos os métodos de acesso potencialmente aplicáveis. O método poderá retornar dados na ordem necessária ou devemos antecipar a classificação? Podemos usar esse método para procurar NULL? Esses são os problemas que o otimizador está resolvendo regularmente.

Não apenas o otimizador precisa de informações sobre o método de acesso. Ao criar um índice, o sistema deve decidir se o índice pode ser construído em várias colunas e se esse índice garante exclusividade.

Portanto, cada método de acesso deve fornecer todas as informações necessárias sobre si mesmo. As versões inferiores a 9.6 usavam a tabela "pg_am" para isso, enquanto a partir da versão 9.6 os dados eram movidos para níveis mais profundos, dentro de funções especiais. Vamos nos familiarizar com essa interface um pouco mais.

Todo o resto é tarefa do método de acesso:

Implemente um algoritmo para criar o índice e mapear os dados em páginas (para que o gerenciador de cache do buffer processe uniformemente cada índice).
Pesquise informações no índice por um predicado no formato " expressão do operador de campo indexado ".
Avalie o custo de uso do índice.
Manipule os bloqueios necessários para o processamento paralelo correto.
Gere registros de log write-ahead (WAL).

Primeiro, consideraremos os recursos do mecanismo de indexação geral e depois consideraremos diferentes métodos de acesso.

Mecanismo de indexação

O mecanismo de indexação permite que o PostgreSQL trabalhe com vários métodos de acesso de maneira uniforme, mas levando em consideração seus recursos.

Principais técnicas de digitalização

Varredura de índice

Podemos trabalhar de maneira diferente com os TIDs fornecidos por um índice. Vamos considerar um exemplo:

postgres=# create table t(a integer, b text, c boolean); postgres=# insert into t(a,b,c) select s.id, chr((32+random()*94)::integer), random() < 0.01 from generate_series(1,100000) as s(id) order by random(); postgres=# create index on t(a); postgres=# analyze t;

Criamos uma tabela de três campos. O primeiro campo contém números de 1 a 100.000, e um índice (independentemente do tipo) é criado nesse campo. O segundo campo contém vários caracteres ASCII, exceto os não imprimíveis. Finalmente, o terceiro campo contém um valor lógico verdadeiro para cerca de 1% das linhas e falso para o restante. Linhas são inseridas na tabela em uma ordem aleatória.

Vamos tentar selecionar um valor pela condição "a = 1". Observe que a condição se parece com " expressão do operador de campo indexado ", em que o operador é "igual" e a expressão (chave de pesquisa) é "1". Na maioria dos casos, a condição deve ser assim para o índice a ser usado.

 postgres=# explain (costs off) select * from t where a = 1;

  QUERY PLAN ------------------------------- Index Scan using t_a_idx on t Index Cond: (a = 1) (2 rows)

Nesse caso, o otimizador decidiu usar a verificação de índice . Com a varredura de índice, o método de acesso retorna os valores TID um a um até a última linha correspondente ser atingida. O mecanismo de indexação acessa as linhas da tabela indicadas por TIDs, por sua vez, obtém a versão da linha, verifica sua visibilidade em relação às regras de simultaneidade multiversão e retorna os dados obtidos.

Verificação de bitmap

A verificação de índice funciona bem quando lidamos com apenas alguns valores. No entanto, à medida que o número de linhas recuperadas aumenta, é mais provável que você volte à mesma página da tabela várias vezes. Portanto, o otimizador alterna para a verificação de bitmap .

 postgres=# explain (costs off) select * from t where a <= 100;

  QUERY PLAN ------------------------------------ Bitmap Heap Scan on t Recheck Cond: (a <= 100) -> Bitmap Index Scan on t_a_idx Index Cond: (a <= 100) (4 rows)

O método de acesso primeiro retorna todos os TIDs que correspondem à condição (nó Bitmap Index Scan) e o bitmap das versões de linha é criado a partir desses TIDs. As versões de linha são lidas na tabela (Bitmap Heap Scan), cada página sendo lida apenas uma vez.

Observe que, na segunda etapa, a condição pode ser verificada novamente (Verifique novamente Cond). O número de linhas recuperadas pode ser muito grande para que o bitmap das versões de linha se ajuste totalmente à RAM (limitado pelo parâmetro "work_mem"). Nesse caso, o bitmap é criado apenas para páginas que contêm pelo menos uma versão de linha correspondente. Esse bitmap "com perdas" requer menos espaço, mas ao ler uma página, precisamos verificar novamente as condições de cada linha contida nela. Observe que, mesmo para um pequeno número de linhas recuperadas e, portanto, o bitmap "exato" (como em nosso exemplo), a etapa "Verificar novamente Cond" é representada no plano de qualquer maneira, embora não seja realmente executada.

Se condições forem impostas em vários campos da tabela e esses campos forem indexados, a verificação de bitmap permitirá o uso de vários índices simultaneamente (se o otimizador considerar isso eficiente). Para cada índice, são criados bitmaps de versões de linha, para os quais é executada multiplicação booleana bit a bit (se as expressões forem unidas por AND) ou adição booleana (se as expressões são unidas por OR). Por exemplo:

 postgres=# create index on t(b); postgres=# analyze t; postgres=# explain (costs off) select * from t where a <= 100 and b = 'a';

  QUERY PLAN -------------------------------------------------- Bitmap Heap Scan on t Recheck Cond: ((a <= 100) AND (b = 'a'::text)) -> BitmapAnd -> Bitmap Index Scan on t_a_idx Index Cond: (a <= 100) -> Bitmap Index Scan on t_b_idx Index Cond: (b = 'a'::text) (7 rows)

Aqui, o nó BitmapAnd une dois bitmaps pela operação "e" bit a bit.

A verificação de bitmap nos permite evitar acessos repetidos à mesma página de dados. Mas e se os dados nas páginas da tabela forem ordenados fisicamente exatamente da mesma maneira que os registros de índice? Não há dúvida de que não podemos confiar totalmente na ordem física dos dados nas páginas. Se dados ordenados forem necessários, devemos especificar explicitamente a cláusula ORDER BY na consulta. Mas é provável que existam situações em que "quase todos" os dados sejam ordenados: por exemplo, se as linhas forem adicionadas na ordem necessária e não forem alteradas depois disso ou após a execução do comando CLUSTER. Em casos como esse, a criação de um bitmap é uma etapa excessiva e uma verificação de índice regular será igualmente boa (a menos que levemos em consideração a possibilidade de ingressar em vários índices). Portanto, ao escolher um método de acesso, o planejador analisa uma estatística especial que mostra a correlação entre a ordenação de linha física e a ordenação lógica dos valores da coluna:

 postgres=# select attname, correlation from pg_stats where tablename = 't';

  attname | correlation ---------+------------- b | 0.533512 c | 0.942365 a | -0.00768816 (3 rows)

Valores absolutos próximos a um indicam uma alta correlação (como na coluna "c"), enquanto valores próximos a zero, pelo contrário, indicam uma distribuição caótica (coluna "a").

Varredura seqüencial

Para concluir a imagem, devemos observar que, com uma condição não seletiva, o otimizador terá razão em preferir a varredura seqüencial de toda a tabela ao uso do índice:

 postgres=# explain (costs off) select * from t where a <= 40000;

  QUERY PLAN ------------------------ Seq Scan on t Filter: (a <= 40000) (2 rows)

O fato é que os índices funcionam melhor, quanto maior a seletividade da condição, ou seja, menos linhas correspondem a ela. O crescimento do número de linhas recuperadas aumenta os custos indiretos da leitura de páginas de índice.

As verificações sequenciais são mais rápidas que as verificações aleatórias, que agravam a situação. Isso vale especialmente para discos rígidos, onde a operação mecânica de levar uma cabeça magnética a uma pista leva muito mais tempo que a própria leitura de dados. Esse efeito é menos perceptível para o SSD. Dois parâmetros estão disponíveis para levar em conta as diferenças nos custos de acesso, "seq_page_cost" e "random_page_cost", que podemos definir não apenas globalmente, mas no nível dos espaços de tabela, ajustando-se às características dos diferentes subsistemas de disco.

Cobrindo índices

Como regra, a principal tarefa de um método de acesso é retornar os identificadores das linhas correspondentes da tabela para que o mecanismo de indexação leia os dados necessários dessas linhas. Mas e se o índice já contiver todos os dados necessários para a consulta? Esse índice é chamado de cobertura e, nesse caso, o otimizador pode aplicar a verificação apenas do índice :

 postgres=# vacuum t; postgres=# explain (costs off) select a from t where a < 100;

  QUERY PLAN ------------------------------------ Index Only Scan using t_a_idx on t Index Cond: (a < 100) (2 rows)

Esse nome pode dar uma idéia de que o mecanismo de indexação não acessa a tabela e obtém todas as informações necessárias apenas do método de acesso. Mas esse não é exatamente o caso, pois os índices no PostgreSQL não armazenam informações que nos permitem avaliar a visibilidade da linha. Portanto, um método de acesso retorna versões de linhas que correspondem à condição de pesquisa, independentemente de sua visibilidade na transação atual.

No entanto, se o mecanismo de indexação precisasse procurar sempre visibilidade na tabela, esse método de verificação não seria diferente de uma verificação de índice comum.

Para resolver o problema, nas tabelas, o PostgreSQL mantém um chamado mapa de visibilidade, no qual a aspiração marca as páginas em que os dados não foram alterados por tempo suficiente para que esses dados sejam visíveis em todas as transações, independentemente da hora de início e do nível de isolamento. Se o identificador de uma linha retornada pelo índice estiver relacionado a essa página, a verificação de visibilidade poderá ser evitada.

Portanto, a aspiração regular aumenta a eficiência dos índices de cobertura. Além disso, o otimizador leva em consideração o número de tuplas mortas e pode decidir não usar a varredura apenas de índice, se prever altos custos indiretos para a verificação de visibilidade.

Podemos aprender o número de acessos forçados a uma tabela usando o comando EXPLAIN ANALYZE:

 postgres=# explain (analyze, costs off) select a from t where a < 100;

  QUERY PLAN ------------------------------------------------------------------------------- Index Only Scan using t_a_idx on t (actual time=0.025..0.036 rows=99 loops=1) Index Cond: (a < 100) Heap Fetches: 0 Planning time: 0.092 ms Execution time: 0.059 ms (5 rows)

Nesse caso, não era necessário acessar a tabela (Heap Fetches: 0), pois a aspiração acabou de ser feita. Em geral, quanto mais próximo esse número de zero for, melhor.

Nem todos os índices armazenam valores indexados junto com identificadores de linha. Se o método de acesso não puder retornar os dados, não poderá ser usado para verificações apenas de índice.

O PostgreSQL 11 introduziu um novo recurso: INCLUDE-indexes. E se houver um índice exclusivo que carece de algumas colunas para ser usado como índice de cobertura para alguma consulta? Você não pode simplesmente adicionar as colunas ao índice, pois isso quebrará sua exclusividade. O recurso permite incluir colunas não chave que não afetam a exclusividade e não podem ser usadas nos predicados de pesquisa, mas ainda podem servir para verificações apenas de índice. O patch foi desenvolvido pela minha colega Anastasia Lubennikova.

Nulo

Os NULLs desempenham um papel importante nos bancos de dados relacionais como uma maneira conveniente de representar um valor inexistente ou desconhecido.

Mas um valor especial é especial para lidar. Uma álgebra booleana regular se torna ternária; não está claro se NULL deve ser menor ou maior que os valores regulares (isso requer construções especiais para classificação, NULLS FIRST e NULLS LAST); não é evidente se as funções agregadas devem considerar NULLs ou não; uma estatística especial é necessária para o planejador ...

Da perspectiva do suporte ao índice, também não está claro se precisamos indexar esses valores ou não. Se NULLs não estiverem indexados, o índice poderá ser mais compacto. Mas se NULLs forem indexados, poderemos usar o índice para condições como " campo indexado IS [NÃO] NULL" e também como um índice de cobertura quando nenhuma condição for especificada para a tabela (pois, neste caso, o O índice deve retornar os dados de todas as linhas da tabela, incluindo aquelas com NULLs).

Para cada método de acesso, os desenvolvedores tomam uma decisão individual quanto à indexação de NULLs ou não. Mas, como regra, eles são indexados.

Índices em vários campos

Para oferecer suporte a condições para vários campos, índices de várias colunas podem ser usados. Por exemplo, podemos criar um índice em dois campos da nossa tabela:

 postgres=# create index on t(a,b); postgres=# analyze t;

O otimizador provavelmente preferirá esse índice a unir bitmaps, pois aqui obtemos prontamente os TIDs necessários sem nenhuma operação auxiliar:

 postgres=# explain (costs off) select * from t where a <= 100 and b = 'a';

  QUERY PLAN ------------------------------------------------ Index Scan using t_a_b_idx on t Index Cond: ((a <= 100) AND (b = 'a'::text)) (2 rows)

Um índice de várias colunas também pode ser usado para acelerar a recuperação de dados por uma condição para alguns dos campos, começando pelo primeiro:

 postgres=# explain (costs off) select * from t where a <= 100;

  QUERY PLAN -------------------------------------- Bitmap Heap Scan on t Recheck Cond: (a <= 100) -> Bitmap Index Scan on t_a_b_idx Index Cond: (a <= 100) (4 rows)

Em geral, se a condição não for imposta no primeiro campo, o índice não será usado. Mas, às vezes, o otimizador pode considerar o uso do índice mais eficiente do que a varredura seqüencial. Expandiremos esse tópico ao considerar os índices "btree".

Nem todos os métodos de acesso oferecem suporte à criação de índices em várias colunas.

Índices em expressões

Já mencionamos que a condição de pesquisa deve se parecer com " expressão do operador de campo indexado ". No exemplo abaixo, o índice não será usado, pois uma expressão contendo o nome do campo é usada em vez do próprio nome do campo:

 postgres=# explain (costs off) select * from t where lower(b) = 'a';

  QUERY PLAN ------------------------------------------ Seq Scan on t Filter: (lower((b)::text) = 'a'::text) (2 rows)

Não é preciso muito tempo para reescrever essa consulta específica para que apenas o nome do campo seja gravado à esquerda do operador. Mas se isso não for possível, os índices nas expressões (índices funcionais) ajudarão:

 postgres=# create index on t(lower(b)); postgres=# analyze t; postgres=# explain (costs off) select * from t where lower(b) = 'a';

  QUERY PLAN ---------------------------------------------------- Bitmap Heap Scan on t Recheck Cond: (lower((b)::text) = 'a'::text) -> Bitmap Index Scan on t_lower_idx Index Cond: (lower((b)::text) = 'a'::text) (4 rows)

O índice funcional é construído não em um campo da tabela, mas em uma expressão arbitrária. O otimizador considerará esse índice para condições como " expressão do operador de expressão indexada ". Se o cálculo da expressão a ser indexada for uma operação cara, a atualização do índice também exigirá recursos de computação significativos.

Lembre-se também de que uma estatística individual é coletada para a expressão indexada. Podemos conhecer essa estatística na visualização "pg_stats" pelo nome do índice:

 postgres=# \dt

  Table "public.t" Column | Type | Modifiers --------+---------+----------- a | integer | b | text | c | boolean | Indexes: "t_a_b_idx" btree (a, b) "t_a_idx" btree (a) "t_b_idx" btree (b) "t_lower_idx" btree (lower(b))

 postgres=# select * from pg_stats where tablename = 't_lower_idx';

É possível, se necessário, controlar o número de cestas de histograma da mesma maneira que para campos de dados regulares (observando que o nome da coluna pode diferir dependendo da expressão indexada):

 postgres=# \d t_lower_idx

  Index "public.t_lower_idx" Column | Type | Definition --------+------+------------ lower | text | lower(b) btree, for table "public.t"

 postgres=# alter index t_lower_idx alter column "lower" set statistics 69;

O PostgreSQL 11 apresenta uma maneira mais limpa de controlar o destino das estatísticas dos índices, especificando o número da coluna no comando ALTER INDEX ... SET STATISTICS. O patch foi desenvolvido pelo meu colega Alexander Korotkov e Adrien Nayrat.

Índices parciais

Às vezes, surge a necessidade de indexar apenas parte das linhas da tabela. Isso geralmente está relacionado a uma distribuição altamente não uniforme: faz sentido procurar um valor pouco frequente por um índice, mas é mais fácil encontrar um valor frequente pela varredura completa da tabela.

Certamente, podemos criar um índice regular na coluna "c", que funcionará da maneira que esperamos:

 postgres=# create index on t(c); postgres=# analyze t; postgres=# explain (costs off) select * from t where c;

  QUERY PLAN ------------------------------- Index Scan using t_c_idx on t Index Cond: (c = true) Filter: c (3 rows)

 postgres=# explain (costs off) select * from t where not c;

  QUERY PLAN ------------------- Seq Scan on t Filter: (NOT c) (2 rows)

E o tamanho do índice é 276 páginas:

 postgres=# select relpages from pg_class where relname='t_c_idx';

  relpages ---------- 276 (1 row)

Mas como a coluna “c” tem o valor true somente para 1% das linhas, 99% do índice nunca é realmente usado. Nesse caso, podemos construir um índice parcial:

 postgres=# create index on t(c) where c; postgres=# analyze t;

O tamanho do índice é reduzido para 5 páginas:

 postgres=# select relpages from pg_class where relname='t_c_idx1';

  relpages ---------- 5 (1 row)

Às vezes, a diferença de tamanho e desempenho pode ser bastante significativa.

Classificação

Se um método de acesso retornar identificadores de linha em alguma ordem específica, isso fornecerá ao otimizador opções adicionais para executar a consulta.

Podemos digitalizar a tabela e classificar os dados:

 postgres=# set enable_indexscan=off; postgres=# explain (costs off) select * from t order by a;

  QUERY PLAN --------------------- Sort Sort Key: a -> Seq Scan on t (3 rows)

Mas podemos ler os dados usando o índice prontamente na ordem desejada:

 postgres=# set enable_indexscan=on; postgres=# explain (costs off) select * from t order by a;

  QUERY PLAN ------------------------------- Index Scan using t_a_idx on t (1 row)

Somente “btree” de todos os métodos de acesso pode retornar dados classificados, então vamos adiar uma discussão mais detalhada até considerar esse tipo de índice.

Edifício concorrente

Normalmente, a criação de um índice adquire um bloqueio SHARE para a tabela. Esse bloqueio permite a leitura de dados da tabela, mas proíbe qualquer alteração enquanto o índice está sendo criado.

Podemos garantir isso se, digamos, durante a criação de um índice na tabela "t", realizarmos a consulta abaixo em outra sessão:

 postgres=# select mode, granted from pg_locks where relation = 't'::regclass;

  mode | granted -----------+--------- ShareLock | t (1 row)

Se a tabela for grande o suficiente e usada extensivamente para inserção, atualização ou exclusão, isso pode parecer inadmissível, pois os processos de modificação aguardam a liberação do bloqueio por um longo tempo.

Nesse caso, podemos usar a construção simultânea de um índice.

 postgres=# create index concurrently on t(a);

Este comando bloqueia a tabela no modo SHARE UPDATE EXCLUSIVE, que permite a leitura e a atualização (é proibida apenas a alteração da estrutura da tabela, bem como a aspiração simultânea, a análise ou a criação de outro índice nesta tabela).

No entanto, há também um outro lado. Primeiro, o índice será criado mais lentamente do que o habitual, pois são feitas duas passagens pela tabela em vez de uma e também é necessário aguardar a conclusão de transações paralelas que modificam os dados.

Segundo, com a criação simultânea do índice, um conflito pode ocorrer ou restrições exclusivas podem ser violadas. No entanto, o índice será criado, embora não operacional. Esse índice deve ser excluído e reconstruído. Os índices não operacionais são marcados com a palavra INVALID na saída do comando psql \ d, e a consulta abaixo retorna uma lista completa dos seguintes:

 postgres=# select indexrelid::regclass index_name, indrelid::regclass table_name from pg_index where not indisvalid;

  index_name | table_name ------------+------------ t_a_idx | t (1 row)

Continue lendo .

Índices no PostgreSQL - 1