O caminho de uma consulta

Antes de entrarmos no assunto da otimização propriamente dito, precisamos rever qual é o caminho de uma consulta no banco de dados.

(A seção a seguir é adaptada da documentação do PostgreSQL)

1. O programa aplicativo transmite um comando para o servidor, e aguarda para receber de volta os resultados transmitidos pelo servidor.
2. O estágio de análise verifica o comando transmitido pelo programa aplicativo com relação à correção da sintaxe, e cria a árvore de comando.
3. O sistema de reescrita recebe a árvore de comando criada pelo estágio de análise, e procura por alguma regra(armazenada nos catálogos do sistema) a ser aplicada na árvore de comando. Realiza as transformações especificadas no corpo das regras. Uma das aplicações do sistema de reescrita é a criação de visões. Sempre que é executado um comando em uma visão (ou seja, uma tabela virtual), o sistema de reescrita reescreve o comando do usuário como um comando acessando as tabelas base especificadas na definição da visão, em vez da visão.
4. O planejador/otimizador recebe a árvore de comando (reescrita), e cria o plano de comando que será a entrada do executor. Isto é feito criando primeiro todos os caminhos possíveis que levam ao mesmo resultado. Por exemplo, se existe um índice em uma relação a ser varrido, existem dois caminhos para a varredura. Uma possibilidade é uma varredura seqüencial simples, e a outra possibilidade é utilizar o índice. Em seguida é estimado o custo de execução de cada umdos caminhos, e escolhido o mais barato. O caminho mais barato é expandido em um plano completo para que o executor possa utilizá-lo.
5. O executor caminha recursivamente através da árvore do plano, e traz as linhas no caminho representado pelo plano. O executor faz uso do sistema de armazenamento ao varrer as relações, realiza classificações e junções, avalia as qualificações e, por fim, envia de volta as linhas derivadas.

O papel do otimizador

(Adaptado de http://en.wikipedia.org/wiki/Query_optimizer )

O otimizador de consultas é o componente do banco de dados que tenta determinar o o modo mais eficiente de executar uma consulta.

O PostgreSQL usa algumas estatísticas mantidas em tabelas do sistema para direcionar o otimizador. Se essas estatísticas estiverem desatualizadas, você provavelmente não obterá o melhor plano para a consulta.

Para atualizar as estatísticas, devemos executar o comando ANALYZE.

É possível vermos o plano que o otimizador de consultas do PostgreSQL gerou, usando a cláusula EXPLAIN antes da consulta.

Adicionando a cláusula EXPLAIN ANALYZE antes da consulta, ela é de fato executada, de forma que possamos ter a medida do tempo.

Exemplos

Pagila

Vamos usar o banco de dados exemplo pagila, disponível em: http://pgfoundry.org/projects/dbsamples/, que é um exemplo de banco de dados de uma locadora.

Vamos começar com a configuração padrão do otimizador do Postgres. Todas as variáveis no postgresql.conf estão comentadas, o que significa que elas usarão os valores padrão.

Como teste, criei dois bancos iguais, o pagila e o pagila2, com a diferença que não rodei o ANALYZE no pagila2.

A configuração do banco é a padrão do Debian.

A consulta a seguir retorna os filmes e os atores associados a ela:

SELECT f.title, a.first_name FROM film f
INNER JOIN  film_actor ON film_actor.film_id=f.film_id
INNER JOIN actor a on film_actor.actor_id = a.actor_id

Aqui está o plano gerado para essa consulta no pagila2 (o que não recebeu ainda o ANALYZE):

Merge Join  (cost=708.95..795.88 rows=5462 width=185) (actual time=56.274..85.883 rows=5462 loops=1)
  Merge Cond: ("outer".film_id = "inner".film_id)
  ->  Sort  (cost=94.83..97.33 rows=1000 width=149) (actual time=8.489..9.926 rows=1000 loops=1)
        Sort Key: f.film_id
        ->  Seq Scan on film f  (cost=0.00..45.00 rows=1000 width=149) (actual time=0.010..4.517 rows=1000 loops=1)
  ->  Sort  (cost=614.12..627.77 rows=5462 width=42) (actual time=47.775..56.152 rows=5462 loops=1)
        Sort Key: film_actor.film_id
        ->  Merge Join  (cost=0.00..275.06 rows=5462 width=42) (actual time=0.027..33.019 rows=5462 loops=1)
              Merge Cond: ("outer".actor_id = "inner".actor_id)
              ->  Index Scan using actor_pkey on actor a  (cost=0.00..12.20 rows=200 width=44) (actual time=0.010..0.450 rows=200 loops=1)
              ->  Index Scan using film_actor_pkey on film_actor  (cost=0.00..194.08 rows=5462 width=4) (actual time=0.006..13.315 rows=5462 loops=1)
Total runtime: 94.576 ms

Sem entrar nos detalhes, vamos entender esse plano. Primeiro, temos que saber olhar de baixo pra cima.

1. Foi feito um index scan na tabela film_actor (a última linha)
2. Foi feito um index table scan na tabela actor
3. Essas duas tabelas foram unidas usando o algoritmo Merge Join
4. O resultado foi ordenado pela coluna fil,_actor.film_id
5. Foi feito um table scan na tabela film, e o resultado foi ordenado pela coluna film id
6. O resultado do scan na tabela film foi juntado com o resultado anterior, usando o algoritmo Merge Join

E aqui está o plano gerado pelo pagila (o banco no qual foi rodado o ANALYZE):

Merge Join  (cost=562.49..697.92 rows=5462 width=27) (actual time=47.691..78.064 rows=5462 loops=1)
  Merge Cond: ("outer".film_id = "inner".film_id)
  ->  Index Scan using film_pkey on film f  (cost=0.00..51.00 rows=1000 width=22) (actual time=0.011..2.442 rows=1000 loops=1)
  ->  Sort  (cost=562.49..576.15 rows=5462 width=11) (actual time=47.668..56.011 rows=5462 loops=1)
        Sort Key: film_actor.film_id
        ->  Merge Join  (cost=0.00..223.43 rows=5462 width=11) (actual time=0.025..32.304 rows=5462 loops=1)
              Merge Cond: ("outer".actor_id = "inner".actor_id)
              ->  Index Scan using actor_pkey on actor a  (cost=0.00..6.20 rows=200 width=13) (actual time=0.007..0.459 rows=200 loops=1)
              ->  Index Scan using film_actor_pkey on film_actor  (cost=0.00..148.46 rows=5462 width=4) (actual time=0.008..12.557 rows=5462 loops=1)
Total runtime: 86.610 ms

Vamos agora analizar esse plano:

1. Foi feito um scan na tabela film_actor pelo índice film_actor_pkey (a chave primária da tabela)
2. Agora, um scan na tabela actor pelo índice
3. As tabelas foram JOINadas pelo actor_id, e o resultado foi ordenado por film_actor.actor_id
4. A tabela film foi varrida pelo índice.
5. O resultado do JOIN anterior foi juntado com a tabela film.

Procurando clientes e filiais:

SELECT 'Filial ' || filial.store_id as filial, c.first_name || c.last_name as client FROM customer c
INNER JOIN store filial on filial.store_id = c.store_id WHERE c.active = 1

Aqui, o explain do banco sem ANALYZE:

Nested Loop  (cost=1.02..17.65 rows=1 width=84) (actual time=0.042..15.491 rows=584 loops=1)
  Join Filter: ("inner".store_id = "outer".store_id)
  ->  Seq Scan on customer c  (cost=0.00..16.49 rows=3 width=82) (actual time=0.013..1.621 rows=584 loops=1)
        Filter: (active = 1)
  ->  Materialize  (cost=1.02..1.04 rows=2 width=4) (actual time=0.002..0.006 rows=2 loops=584)
        ->  Seq Scan on store filial  (cost=0.00..1.02 rows=2 width=4) (actual time=0.004..0.011 rows=2 loops=1)
Total runtime: 16.480 ms

Repare que foi usado um materialize = um plano foi salvo num arquivo temporário.

E agora, o explain do banco com ANALYZE:

Nested Loop  (cost=4.05..46.50 rows=584 width=23) (actual time=0.175..6.097 rows=584 loops=1)
  ->  Seq Scan on store filial  (cost=0.00..1.02 rows=2 width=4) (actual time=0.008..0.015 rows=2 loops=1)
  ->  Bitmap Heap Scan on customer c  (cost=4.05..16.80 rows=300 width=21) (actual time=0.136..1.248 rows=292 loops=2)
        Recheck Cond: ("outer".store_id = c.store_id)
        Filter: (active = 1)
        ->  Bitmap Index Scan on idx_fk_store_id  (cost=0.00..4.05 rows=300 width=0) (actual time=0.122..0.122 rows=300 loops=2)
              Index Cond: ("outer".store_id = c.store_id)
Total runtime: 7.160 ms

Nesse caso, como as estatísticas já estavam atualizadas, o banco optou por uma otimização e usou o Bitmap Index Scan e o Bitmap Heap Scan.

O Bitmap Index Scan é usado em colunas que tem pouca variação (colunas de baixa cardinalidade). No caso, para cada cliente, eu tenho apenas duas opções de filias às quais ele pode estar associado (1 e 2). Então, o banco cria um mapa de bits para cada um desses valores. Esse mapa é carregado em memória, e é juntado com o resultado do table scan em store, que tem apenas dois valores possíveis.

No último select, ainda assim foi feito um Table Scan na tabela store, onde alguém poderia argumentar que seria melhor um index scan.

Random Page Cost

Existe um parâmetro de configuração, chamado random_page_cost que determina qual o peso que o PostgreSQL dá a leituras não sequencias no disco. Aumentar esse valor favorece o uso de table scans, abaixá-lo favorece o uso de índices. O valor padrão é 4.0.

Para um pequeno teste, vamos baixá-lo para 2.0 e executar a query no banco pagila.

Merge Join  (cost=0.00..42.34 rows=584 width=23) (actual time=0.128..6.012 rows=584 loops=1)
  Merge Cond: ("outer".store_id = "inner".store_id)
  ->  Index Scan using store_pkey on store filial  (cost=0.00..3.02 rows=2 width=4) (actual time=0.092..0.098 rows=2 loops=1)
  ->  Index Scan using idx_fk_store_id on customer c  (cost=0.00..27.64 rows=584 width=21) (actual time=0.015..2.150 rows=584 loops=1)
        Filter: (active = 1)
Total runtime: 6.996 ms

Como o custo do índice estava mais baixo, o otimizador preferiu usar o índice do que gerar o índice bitmap em memória.

Agora, no pagila2, o plano gerado é semelhante ao plano do banco que está com as estatísticas atualizadas:

Nested Loop  (cost=2.01..12.74 rows=1 width=84) (actual time=0.264..5.829 rows=584 loops=1)
  ->  Seq Scan on store filial  (cost=0.00..1.02 rows=2 width=4) (actual time=0.012..0.019 rows=2 loops=1)
  ->  Bitmap Heap Scan on customer c  (cost=2.01..5.82 rows=3 width=82) (actual time=0.182..1.236 rows=292 loops=2)
        Recheck Cond: ("outer".store_id = c.store_id)
        Filter: (active = 1)
        ->  Bitmap Index Scan on idx_fk_store_id  (cost=0.00..2.01 rows=3 width=0) (actual time=0.165..0.165 rows=300 loops=2)
              Index Cond: ("outer".store_id = c.store_id)
Total runtime: 6.861 ms

Executada no pagila2, a query gera o mesmo plano que havia sido gerado para random_page_cost = 4.0. E, com random_page_cost = 2.0, a primeira query do nosso teste passa a usar o índice, mesmo sem o analyze. Mas os custos não são os mesmos - isso porque o pagila2 ainda não teve as estatísticas atualizadas.

Configurações do otimizador

O arquivo de configuração do postgresql (postgresql.conf) contém várias opções que tratam da configuração do otimizador e dos vários métodos de consulta. São eles:

Todos eles podem ser configurados para on ou off, e por padrão todos vem habilitados. Alguns pontos a serem notados:

enable_seqscan = off não desabilita de fato o scan sequencial, já que essa pode ser a única forma de executar certas consultas. O que esse parâmetro faz ne verdade é aumentar o custo de um table scan. O mesmo vale para enable_nestloop (algumas vezes não há forma de resolver uma consulta, exceto por esse tipo de loop) e enable_sort.

Esses valores podem ser alterados em tempo de execução para uma sessão em particular, usando o comando SET.

Esse é apenas um resumo. As descrição completa das opções relativas ao otimizador são encontradas em: http://www.postgresql.org/docs/8.0/static/runtime-config.html .

Listando atores e filmes

A primeira consulta, embora trouxesse a lista de filmes e atoes, não trazia o resultado agrupado pelos filmes, com uma lista de todos os atores.

Vamor fazer essa consulta então.

Existem duas sintaxes que podem ser usadas. A primeira:

select
     film.title AS title,
     array_to_string(array_accum(actor.first_name || ' ' || actor.last_name),',') AS actors
from
     film
     inner join film_actor on film.film_id = film_actor.film_id
     inner join actor on film_actor.actor_id = actor.actor_id
GROUP BY film.title
ORDER BY film.title

E seu explain:

Sort  (cost=768.81..771.31 rows=1000 width=37) (actual time=151.996..153.650 rows=997 loops=1)
  Sort Key: film.title
  ->  HashAggregate  (cost=698.98..718.98 rows=1000 width=37) (actual time=132.534..142.902 rows=997 loops=1)
        ->  Merge Join  (cost=536.24..671.67 rows=5462 width=37) (actual time=53.739..97.676 rows=5462 loops=1)
              Merge Cond: ("outer".film_id = "inner".film_id)
              ->  Index Scan using film_pkey on film  (cost=0.00..51.00 rows=1000 width=22) (actual time=0.012..3.780 rows=1000 loops=1)
              ->  Sort  (cost=536.24..549.90 rows=5462 width=21) (actual time=53.716..63.214 rows=5462 loops=1)
                    Sort Key: film_actor.film_id
                    ->  Merge Join  (cost=0.00..197.18 rows=5462 width=21) (actual time=0.026..36.636 rows=5462 loops=1)
                          Merge Cond: ("outer".actor_id = "inner".actor_id)
                          ->  Index Scan using actor_pkey on actor  (cost=0.00..6.20 rows=200 width=23) (actual time=0.007..0.536 rows=200 loops=1)
                          ->  Index Scan using film_actor_pkey on film_actor  (cost=0.00..122.21 rows=5462 width=4) (actual time=0.009..14.883 rows=5462 loops=1)
Total runtime: 159.766 ms

Uma outra forma possível de fazer essa consulta é essa:

SELECT f.title,
array_to_string(array(select first_name FROM film_actor fa
join actor a ON fa.actor_id = a.actor_id and fa.film_id = f.film_id
),', ') as film_actor
FROM film f

Será que essa forma, além de ser menos compacta, é mais rápida também?

Seq Scan on film f  (cost=0.00..16382.69 rows=1000 width=22) (actual time=1.214..712.919 rows=1000 loops=1)
  SubPlan
    ->  Merge Join  (cost=9.56..16.34 rows=5 width=9) (actual time=0.199..0.687 rows=5 loops=1000)
          Merge Cond: ("outer".actor_id = "inner".actor_id)
          ->  Index Scan using actor_pkey on actor a  (cost=0.00..6.20 rows=200 width=13) (actual time=0.005..0.347 rows=165 loops=1000)
          ->  Sort  (cost=9.56..9.57 rows=5 width=2) (actual time=0.056..0.069 rows=5 loops=1000)
                Sort Key: fa.actor_id
                ->  Bitmap Heap Scan on film_actor fa  (cost=2.02..9.50 rows=5 width=2) (actual time=0.020..0.033 rows=5 loops=1000)
                      Recheck Cond: (film_id = $0)
                      ->  Bitmap Index Scan on idx_fk_film_id  (cost=0.00..2.02 rows=5 width=0) (actual time=0.013..0.013 rows=5 loops=1000)
                            Index Cond: (film_id = $0)
Total runtime: 714.655 ms

Parece que não.

Vemos que na consulta, o maior tempo gasto está no merge join (de 0.199 até 0.687). Vamos desabilitá-lo então. Isso é feito com o comando: set enable_mergejoin = off.

Vejamos o novo plano:

Seq Scan on film f  (cost=0.00..24679.64 rows=1000 width=22) (actual time=0.368..162.552 rows=1000 loops=1)
  SubPlan
    ->  Nested Loop  (cost=2.02..24.63 rows=5 width=9) (actual time=0.037..0.136 rows=5 loops=1000)
          ->  Bitmap Heap Scan on film_actor fa  (cost=2.02..9.50 rows=5 width=2) (actual time=0.020..0.039 rows=5 loops=1000)
                Recheck Cond: (film_id = $0)
                ->  Bitmap Index Scan on idx_fk_film_id  (cost=0.00..2.02 rows=5 width=0) (actual time=0.014..0.014 rows=5 loops=1000)
                      Index Cond: (film_id = $0)
          ->  Index Scan using actor_pkey on actor a  (cost=0.00..3.01 rows=1 width=13) (actual time=0.007..0.009 rows=1 loops=5462)
                Index Cond: ("outer".actor_id = a.actor_id)
Total runtime: 164.212 ms

Fiz um pequeno teste com o beta do PostgreSQL 8.2, e para minha surpresa, o plano gerado para essa consulta é o mesmo que é gerado no 8.1 usando enable_mergejoin = off (com random_page_cost = 2.0).

Entendendo os ícones usados no pgadmin

Escrevi uma pequena descrição para os ícones usados no pgadmin, que está disponível em: http://artigos.waltercruz.com/postgresql/explain

Outra coisa interessante pra se notar é que a grossura das setas é proporcional ao custo das operações.