Tecnologia

Como o PostgreSQL usa múltiplos índices na mesma consulta?

Por: , dezembro 11, 2013


“O PostgreSQL é capaz de usar múltiplos índices de uma tabela numa mesma consulta?”. Esta foi (não exatamente com essas palavras) uma pergunta realizada há alguns dias na lista pgbr-geral. Este pequeno artigo, é uma expansão da resposta que forneci ao meu xará.
Vamos pensar num exemplo simples, onde queremos executar a seguinte consulta numa tabela com 10 milhões de tuplas:

SELECT a, b FROM foo WHERE a = 10 AND b = 100;

E ainda, vamos supor que a tabela foo tenha dois índices, um apenas na coluna A e outro apenas na coluna B.

Quando o PostgreSQL usa apenas um índice?

O PostgreSQL vai poder usar qualquer um dos índices que você criou. Mas para decidir qual (ou quais) usará, ele tentará “adivinhar” quantos registros cada filtro retornará. Para tanto, o otimizador do PostgreSQL tentará responder as seguintes perguntas (não somente essas, mas outras não vem ao caso):

  1. Quantas tuplas somente o filtro a = 10 retorna?
  2. Quantas tuplas somente o filtro b = 100 retorna?
  3. Quantas tuplas ambos filtros, a = 10 AND c = 100 retornam?

Esse “adivinhar” é baseado nas estatísticas do banco de dados (vamos deixar essa pra outro momento). Vamos supor alguns exemplos baseados nos itens acima:

  1. Existem aproximadamente 100.000 registros com a = 10.
  2. Existem aproximadamente 10 registros com b = 100.
  3. Existe aproximadamente 1 registro (apenas) com ambos, a = 10 AND b = 100.

Nesse caso podemos dizer que o PostgreSQL irá preferir usar somente o índice em (B). Nessa navegação, ele recupera os 10 registros onde b = 100 e, em seguida, busca (da tabela mesmo) aquele registro onde a = 10, ou seja, depois de pegar do índice teria o trabalho de verificar apenas 10 registros, que representam apenas 0,001% da tabela toda (muito pouco). Isso vale bem mais a pena do que o trabalho extra para navegar nos dois índices.
Mais ainda. Se formos pensar que esses 10 registros estão cada um em uma página diferente, e, assumindo que cada página possui 8KB (o padrão), isso significa que é preciso trazer do disco para a memória apenas 80KB de dados. Esses 80KB podem ser facilmente armazenados em memória e a busca pelo registro com a = 10 pode ser feito daí (não é bem assim que acontece, mas tudo bem).

Quando (e como) o PostgreSQL usa vários índices?

Agora, vamos pensar num conjunto de dados diferente, onde:

  1. Existem aproximadamente 10.000 de registros com a = 10.
  2. Existem aproximadamente 1.000 registros com b = 100.
  3. Existem aproximadamente 10 registros com ambos, a = 10 AND b = 100.

Nesse último caso, se o PostgreSQL usar qualquer um dos dois índices unicamente, ainda teria muitas tuplas a buscar da tabela, para no final ficar com apenas 10 registros. Assumindo o mesmo que anteriormente, que cada tupla está numa página de 8KB, isso significaria recuperar da tabela (se navegasse primeiro no índice em B) quase 8MB (1.000 * 8KB), o que já é bem mais custoso.
Nesse caso então ele irá preferir navegar pelos dois índices juntos, e pegar só o que interessa da tabela.
Agora, como ele faz isso?
Ele irá usar uma estrutura auxiliar, conhecida como bitmaps ou mapa de bits, e o seguinte algoritmo:

  1. Navega no índice em (A) e busca pelos registros onde a = 10. Com o resultado, gera um bitmap marcando as tuplas que casam com esse filtro com o valor 1 e que não casam com 0.
  2. Navega no índice em (B), busca pelos registros onde b = 100 e gera um bitmap desse resultado também.
  3. Realiza uma operação de AND nos dois bitmaps, o que é bem rápido (são só bitmaps) e gera como resultado um novo bitmap, que mapeia quais são as tuplas da tabela que contém ambos os valores.
  4. Por fim, basta navegar nas páginas da tabela marcadas com o bitmap resultante do AND anterior.

Para esclarecer mais essa questão do bitmap, vamos supor uma tabela com apenas 8 tuplas, se uma navegação no índice em A retornasse as tuplas 1,4 e 7 e no índice em B as tuplas 4 e 6. Os bitmaps formados seriam:

  1. 2. 3. 4. 5. 6. 7. 8.
  1  0  0  1  0  0  1  0  => bitmap recuperado do índice em A
  0  0  0  1  0  1  0  0  => bitmap recuperado do índice em B
  =========================> operação AND
  0  0  0  1  0  0  0  0

Pelo último bitmap (00010000) fica fácil perceber que apenas a tuplas 4 precisa ser visitada.
Vale comentar que essa é uma visão simplória. O real bitmap usado pelo PostgreSQL é esparso (ou seja não precisa armazenar TODOS os zeros), e ainda pode (caso seja muito grande) mapear páginas ao invés de tuplas, dessa forma ao navegar na tabela ele recuperará a página e irá fazer uma reverificação na mesma. Dessa forma, trabalhar com bitmaps são operações bem baratas, tanto com relação a performance quanto a espaço. Por exemplo, o bitmap (mapeando por páginas) de uma grande tabela com 1TB de dados, ocuparia no máximo 16MB (não será exatamente isso devido à algumas otimizações do PostgreSQL, mas podemos pensar nisso como um limite aproximado).
Voltando ao exemplo, veja que se a tabela tem 10 milhões e queremos apenas 10 registros, estamos falando de cerca de apenas 0,0001% da tabela, em número de tuplas. Num exemplo mais prático, que veremos a seguir, realizei a mesma operação obtendo o resultado em 2 páginas de um total de 44248 páginas de uma tabela, ou seja, foi necessário recuperar apenas cerca de apenas 0,005% de dados da tabela.
Vale ressaltar que o PostgreSQL usa dados estatísticos para encontrar esses possíveis valores de retorno. Nesse caso ele não precisa da quantidade exata de registros que cada filtro retorna, mas quanto mais próximo do real, melhor serão os planos de execução criados.

Quer uma prova de que isso funciona?

Então vamos ver um exemplo mais prático.
Se você entendeu até aqui, vai achar interessante a operação que segue. Se não entendeu, pode ser que algo mais real ajude, :) (pode deixar dúvidas nos comentários também).
Já vou adiantando que não é um exemplo realista, mas serve para mostrar uma operação e um plano de execução bem comum em casos reais. Além de ajudar a quem está aprendendo a ler o famigerado EXPLAIN.
Vou criar duas tabelas, a exemplo1 (para casar como primeiro exemplo que passei, usa-se apenas um índice) e a exemplo2 (para casar com o segundo, e mais interessante, com uso de bitmaps).
A exemplo1:

-- Criando uma tabela já com 1 milhão de tuplas
CREATE TABLE exemplo1 AS SELECT i AS a, j%100000 AS b FROM generate_series(1, 10) i, generate_series(1, 100000) j;
-- Vamos jogar algum lixo nessa tabela, chegando a 10 milhões de tuplas, apenas para dificultar a leitura do pobre PostgreSQL:
INSERT INTO exemplo1 SELECT i * -1 AS a, j%1000 * -1 AS b FROM generate_series(1, 900) i, generate_series(1, 10000) j;
-- E nosso índices:
CREATE INDEX exemplo1_a_idx ON exemplo1 (a);
CREATE INDEX exemplo1_b_idx ON exemplo1 (b);

A exemplo2 segue a mesma ideia (os valores iniciais mudam):

CREATE TABLE exemplo2 AS SELECT i AS a, j%1000 AS b FROM generate_series(1, 100) i, generate_series(1, 10000) j;
INSERT INTO exemplo2 SELECT i * -1 AS a, j%1000 * -1 AS b FROM generate_series(1, 900) i, generate_series(1, 10000) j;
CREATE INDEX exemplo2_a_idx ON exemplo2 (a);
CREATE INDEX exemplo2_b_idx ON exemplo2 (b);

Só para conferir se temos os mesmos dados dos exemplos:

> SELECT count(*) FROM exemplo1 WHERE a = 10;
count: 100000
> SELECT count(*) FROM exemplo1 WHERE b = 100;
count: 10
> SELECT count(*) FROM exemplo1 WHERE a = 10 AND b = 100;
count: 1
> SELECT count(*) FROM exemplo2 WHERE a = 10;
count: 10000
> SELECT count(*) FROM exemplo2 WHERE b = 100;
count: 1000
> SELECT count(*) FROM exemplo2 WHERE a = 10 AND b = 100;
count: 10

Agora, vamos garantir que o PostgreSQL tem estatísticas suficientes para essas tabelas (afinal são tabelas de 10 milhões de registros):

ALTER TABLE exemplo1 ALTER a SET STATISTICS 1000, ALTER b SET STATISTICS 1000;
ALTER TABLE exemplo2 ALTER a SET STATISTICS 1000, ALTER b SET STATISTICS 1000;
ANALYZE exemplo1;
ANALYZE exemplo2;

Agora, vamos à análise do exemplo 1:

> EXPLAIN ANALYZE SELECT a,b FROM exemplo1 WHERE a = 10 AND b = 100;
                                                           QUERY PLAN
   ---------------------------------------------------------------------------------------------------------------------------
1. Index Scan using exemplo1_b_idx on exemplo1  (cost=0.43..135.18 rows=1 width=8) (actual time=0.039..0.044 rows=1 loops=1)
2.   Index Cond: (b = 100)
3.   Filter: (a = 10)
4.   Rows Removed by Filter: 9
5. Total runtime: 0.106 ms
(5 rows)

Como eu havia previsto antes (claro, eu testei né?! =P ), podemos ver claramente que:

  • Da linha 1, o PostgreSQL decidiu usar apenas o índice em B.
  • Da linha 2, usou apenas a condição b = 100, para navegar nesse índice.
  • Da linha 3, usou o filtro a = 10, para verificar apenas os valores (recuperados pelo índice) que casam com os dois filtros.
  • Da linha 4, foram recuperados vários registros do índice e 9 foram ignorados. Se observamos em rows=1 na linha 1, concluímos que foram recuperados 10 registros do índice, mas apenas 1 foi trazido.

E quanto ao exemplo 2?

> EXPLAIN ANALYZE SELECT a,b FROM exemplo2 WHERE a = 10 AND b = 100;
                                                                QUERY PLAN
  ---------------------------------------------------------------------------------------------------------------------------------------
1. Bitmap Heap Scan on exemplo2  (cost=197.13..201.14 rows=1 width=8) (actual time=1.240..1.385 rows=10 loops=1)
2.   Recheck Cond: ((b = 100) AND (a = 10))
3.   ->  BitmapAnd  (cost=197.13..197.13 rows=1 width=0) (actual time=1.204..1.204 rows=0 loops=1)
4.         ->  Bitmap Index Scan on exemplo2_b_idx  (cost=0.00..19.94 rows=1001 width=0) (actual time=0.196..0.196 rows=1000 loops=1)
5.               Index Cond: (b = 100)
6.         ->  Bitmap Index Scan on exemplo2_a_idx  (cost=0.00..176.93 rows=10733 width=0) (actual time=0.241..0.241 rows=10000 loops=1)
7.               Index Cond: (a = 10)
8. Total runtime: 1.605 ms
(8 rows)

Temos (veja que estou lendo de cima para baixo agora):

  • Na linha 6, o PostgreSQL usou o índice em A para filtrar os valores onde a = 10 (linha 7) e gerou um bitmap desse resultado.
  • Na linha 4, o PostgreSQL usou o índice em B para filtrar os valores onde b = 100 (linha 5) e gerou um bitmap desse resultado.
  • Na linha 3, o PostgreSQL realizou um AND dos bitmaps gerados para buscar os valores onde ambos filtros casavam.
  • Na linha 1, ele finalmente navegou na tabela buscando pelas páginas onde o bitmap (da linha 3) marcava como 1, usando o filtro final (linha 2) para recuperar cada registro.

“Péraê!” Eu não poderia usar um único índice em A e B?

Opa. Claro que poderia:

CREATE INDEX exemplo2_ab_idx ON exemplo2 (a, b);

E nesse caso a consulta que citamos iria usar somente esse índice. Mas, lembre-se que índices agilizam as consultas mas causam mais lentidão em atualizações (INSERT/UPDATE/DELETE). Logo, se pensarmos num caso mais complexo, como perguntado na lista, onde tem-se vários campos e consultas variadas em cada um deles, pode não ser tão vantajoso criar um índice para cada um.
Nestes casos não há uma regra fixa, com a experiência, passamos a olhar o plano de execução e saber se aquele BitmapAnd está ruim e deveríamos adicionar (ou substituir) um índice composto com os dois campos (ou até mais). Muitas vezes um índice composto ganha muito pouco em performance, e, se não é usado por outras consultas, pode ser útil manter algo mais genérico, ficando com menos índices e evitando penalizar atualizações. São vários fatores à considerar, não só as consultas que são realizadas nessa tabela, mas também o espaço em disco, a taxa de atualização contra taxa de consultas, as tarefas administrativas, etc.
Só para terem uma ideia, numa bateria de testes com a tabela exemplo2, a mesma consulta com o BitmapAnd levou, em média, 1,3ms, enquanto com o índice composto o tempo reduziu para 0,1ms. O ganho é, de fato, grande, 92,3%. Mas a pergunta é se os 1,2ms de diferença (repararam que não dá nem um segundo né?!) compensa o trabalho em manter vários índices nessa tabela? E claro, a resposta é “depende”. Depende de quantas vezes essa consulta é executada. A concorrência do ambiente. A taxa de atualização. Memória. CPU. Disco. Etc. Etc. Etc.

  • Receba nosso conteúdo em primeira mão.