Como acelerar a ordenação ORDER BY ao usar o índice GIN no PostgreSQL?

12

Eu tenho uma tabela como esta:

CREATE TABLE products (
  id serial PRIMARY KEY, 
  category_ids integer[],
  published boolean NOT NULL,
  score integer NOT NULL,
  title varchar NOT NULL);

Um produto pode pertencer a várias categorias. category_idsA coluna contém uma lista de IDs de todas as categorias de produtos.

A consulta típica fica assim (sempre procurando por categoria única):

SELECT * FROM products WHERE published
  AND category_ids @> ARRAY[23465]
ORDER BY score DESC, title
LIMIT 20 OFFSET 8000;

Para acelerar, use o seguinte índice:

CREATE INDEX idx_test1 ON products
  USING GIN (category_ids gin__int_ops) WHERE published;

Este ajuda muito, a menos que haja muitos produtos em uma categoria. Ele filtra rapidamente os produtos que pertencem a essa categoria, mas há uma operação de classificação que deve ser executada da maneira mais difícil (sem índice).

Uma btree_ginextensão instalada permite que eu crie um índice GIN com várias colunas como este:

CREATE INDEX idx_test2 ON products USING GIN (
  category_ids gin__int_ops, score, title) WHERE published;

Mas o Postgres não deseja usar isso para classificar . Mesmo quando eu removo o DESCespecificador na consulta.

Quaisquer abordagens alternativas para otimizar a tarefa são muito bem-vindas.

Informação adicional:

  • PostgreSQL 9.4, com extensão intarray
  • atualmente, o número total de produtos é de 260 mil, mas espera-se um crescimento significativo (até 10 milhões, esta é a plataforma de comércio eletrônico para vários locatários)
  • produtos por categoria 1..10000 (pode crescer até 100k), a média está abaixo de 100, mas as categorias com grande número de produtos tendem a atrair muito mais solicitações

O plano de consulta a seguir foi obtido de um sistema de teste menor (4680 produtos na categoria selecionada, 200 mil produtos no total na tabela):

Limit  (cost=948.99..948.99 rows=1 width=72) (actual time=82.330..82.341 rows=20 loops=1)
  ->  Sort  (cost=948.37..948.99 rows=245 width=72) (actual time=80.231..81.337 rows=4020 loops=1)
        Sort Key: score, title
        Sort Method: quicksort  Memory: 928kB
        ->  Bitmap Heap Scan on products  (cost=13.90..938.65 rows=245 width=72) (actual time=1.919..16.044 rows=4680 loops=1)
              Recheck Cond: ((category_ids @> '{292844}'::integer[]) AND published)
              Heap Blocks: exact=3441
              ->  Bitmap Index Scan on idx_test2  (cost=0.00..13.84 rows=245 width=0) (actual time=1.185..1.185 rows=4680 loops=1)
                    Index Cond: (category_ids @> '{292844}'::integer[])
Planning time: 0.202 ms
Execution time: 82.404 ms

Nota # 1 : 82 ms podem não parecer assustadores, mas isso ocorre porque o buffer de classificação se encaixa na memória. Depois de selecionar todas as colunas da tabela de produtos ( SELECT * FROM ...e na vida real existem cerca de 60 colunas), o Sort Method: external merge Disk: 5696kBtempo de execução é dobrado. E isso é apenas para 4680 produtos.

Ponto de ação nº 1 (vem da Nota nº 1): para reduzir o espaço ocupado na memória da operação de classificação e, portanto, acelerar um pouco, seria sensato buscar, classificar e limitar os IDs de produtos primeiro e, em seguida, buscar registros completos:

SELECT * FROM products WHERE id IN (
  SELECT id FROM products WHERE published AND category_ids @> ARRAY[23465]
  ORDER BY score DESC, title LIMIT 20 OFFSET 8000
) ORDER BY score DESC, title;

Isso nos leva de volta a Sort Method: quicksort Memory: 903kB~ 80 ms para 4680 produtos. Ainda pode ser lento quando o número de produtos cresce para 100k.

postgresql index postgresql-performance Yaroslav Stavnichiy
fonte
Nesta página: hlinnaka.iki.fi/2014/03/28/…, há um comentário que btree_gin não pode ser usado para classificação.
Mladen Uzelac
OK, reformulei o título para permitir mais opções.
Yaroslav Stavnichiy
Você está sempre procurando por uma única categoria? E forneça algumas informações mais básicas: versão do Postgres, cardinalidades, linhas por categoria (min / avg / max). considere as instruções nas informações da tag para postgresql-performance . E: scorepode ser NULL, mas você ainda classifica por score DESC, não score DESC NULLS LAST. Um ou outro não parece certo ...
Erwin Brandstetter
Adicionei informações adicionais conforme solicitado. Estou sempre procurando por categoria única. E score, de fato, NÃO é NULL - corrigi a definição da tabela.
Yaroslav Stavnichiy

Respostas:

9

Eu fiz muitas experiências e aqui estão minhas descobertas.

GIN e classificação

O índice GIN atualmente (a partir da versão 9.4) não pode ajudar no pedido .

Dos tipos de índice atualmente suportados pelo PostgreSQL, apenas a B-tree pode produzir saída classificada - os outros tipos de índice retornam linhas correspondentes em uma ordem não especificada e dependente da implementação.

work_mem

Obrigado Chris por apontar para este parâmetro de configuração . O padrão é 4 MB e, se o seu conjunto de registros for maior, aumentar work_mempara o valor adequado (pode ser encontrado em EXPLAIN ANALYSE) pode acelerar significativamente as operações de classificação.

ALTER SYSTEM SET work_mem TO '32MB';

Reinicie o servidor para que as alterações entrem em vigor e verifique novamente:

SHOW work_mem;

Consulta original

Eu preenchi meu banco de dados com produtos de 650k com algumas categorias com até 40k produtos. Simplifiquei um pouco a consulta removendo a publishedcláusula:

SELECT * FROM products WHERE category_ids @> ARRAY [248688]
ORDER BY score DESC, title LIMIT 10 OFFSET 30000;

Limit  (cost=2435.62..2435.62 rows=1 width=1390) (actual time=1141.254..1141.256 rows=10 loops=1)
  ->  Sort  (cost=2434.00..2435.62 rows=646 width=1390) (actual time=1115.706..1140.513 rows=30010 loops=1)
        Sort Key: score, title
        Sort Method: external merge  Disk: 29656kB
        ->  Bitmap Heap Scan on products  (cost=17.01..2403.85 rows=646 width=1390) (actual time=11.831..25.646 rows=41666 loops=1)
              Recheck Cond: (category_ids @> '{248688}'::integer[])
              Heap Blocks: exact=6471
              ->  Bitmap Index Scan on idx_products_category_ids_gin  (cost=0.00..16.85 rows=646 width=0) (actual time=10.140..10.140 rows=41666 loops=1)
                    Index Cond: (category_ids @> '{248688}'::integer[])
Planning time: 0.288 ms
Execution time: 1146.322 ms

Como podemos ver, work_memnão bastava Sort Method: external merge Disk: 29656kB(o número aqui é aproximado, ele precisa de um pouco mais de 32 MB para a classificação rápida na memória).

Reduzir a pegada de memória

Não selecione registros completos para classificação, use IDs, aplique classificação, deslocamento e limite e carregue apenas 10 registros necessários:

SELECT * FROM products WHERE id in (
  SELECT id FROM products WHERE category_ids @> ARRAY[248688]
  ORDER BY score DESC, title LIMIT 10 OFFSET 30000
) ORDER BY score DESC, title;

Sort  (cost=2444.10..2444.11 rows=1 width=1390) (actual time=707.861..707.862 rows=10 loops=1)
  Sort Key: products.score, products.title
  Sort Method: quicksort  Memory: 35kB
  ->  Nested Loop  (cost=2436.05..2444.09 rows=1 width=1390) (actual time=707.764..707.803 rows=10 loops=1)
        ->  HashAggregate  (cost=2435.63..2435.64 rows=1 width=4) (actual time=707.744..707.746 rows=10 loops=1)
              Group Key: products_1.id
              ->  Limit  (cost=2435.62..2435.62 rows=1 width=72) (actual time=707.732..707.734 rows=10 loops=1)
                    ->  Sort  (cost=2434.00..2435.62 rows=646 width=72) (actual time=704.163..706.955 rows=30010 loops=1)
                          Sort Key: products_1.score, products_1.title
                          Sort Method: quicksort  Memory: 7396kB
                          ->  Bitmap Heap Scan on products products_1  (cost=17.01..2403.85 rows=646 width=72) (actual time=11.587..35.076 rows=41666 loops=1)
                                Recheck Cond: (category_ids @> '{248688}'::integer[])
                                Heap Blocks: exact=6471
                                ->  Bitmap Index Scan on idx_products_category_ids_gin  (cost=0.00..16.85 rows=646 width=0) (actual time=9.883..9.883 rows=41666 loops=1)
                                      Index Cond: (category_ids @> '{248688}'::integer[])
        ->  Index Scan using products_pkey on products  (cost=0.42..8.45 rows=1 width=1390) (actual time=0.004..0.004 rows=1 loops=10)
              Index Cond: (id = products_1.id)
Planning time: 0.682 ms
Execution time: 707.973 ms

Nota Sort Method: quicksort Memory: 7396kB. Resultado é muito melhor.

JOIN e índice adicional de árvore B

Como Chris aconselhou, criei um índice adicional:

CREATE INDEX idx_test7 ON products (score DESC, title);

Primeiro eu tentei entrar assim:

SELECT * FROM products NATURAL JOIN
  (SELECT id FROM products WHERE category_ids @> ARRAY[248688]
  ORDER BY score DESC, title LIMIT 10 OFFSET 30000) c
ORDER BY score DESC, title;

O plano de consulta difere um pouco, mas o resultado é o mesmo:

Sort  (cost=2444.10..2444.11 rows=1 width=1390) (actual time=700.747..700.747 rows=10 loops=1)
  Sort Key: products.score, products.title
  Sort Method: quicksort  Memory: 35kB
  ->  Nested Loop  (cost=2436.05..2444.09 rows=1 width=1390) (actual time=700.651..700.690 rows=10 loops=1)
        ->  HashAggregate  (cost=2435.63..2435.64 rows=1 width=4) (actual time=700.630..700.630 rows=10 loops=1)
              Group Key: products_1.id
              ->  Limit  (cost=2435.62..2435.62 rows=1 width=72) (actual time=700.619..700.619 rows=10 loops=1)
                    ->  Sort  (cost=2434.00..2435.62 rows=646 width=72) (actual time=697.304..699.868 rows=30010 loops=1)
                          Sort Key: products_1.score, products_1.title
                          Sort Method: quicksort  Memory: 7396kB
                          ->  Bitmap Heap Scan on products products_1  (cost=17.01..2403.85 rows=646 width=72) (actual time=10.796..32.258 rows=41666 loops=1)
                                Recheck Cond: (category_ids @> '{248688}'::integer[])
                                Heap Blocks: exact=6471
                                ->  Bitmap Index Scan on idx_products_category_ids_gin  (cost=0.00..16.85 rows=646 width=0) (actual time=9.234..9.234 rows=41666 loops=1)
                                      Index Cond: (category_ids @> '{248688}'::integer[])
        ->  Index Scan using products_pkey on products  (cost=0.42..8.45 rows=1 width=1390) (actual time=0.004..0.004 rows=1 loops=10)
              Index Cond: (id = products_1.id)
Planning time: 1.015 ms
Execution time: 700.918 ms

Jogando com várias compensações e contagens de produtos, não consegui fazer o PostgreSQL usar um índice adicional de árvore B.

Então eu segui o caminho clássico e criei a tabela de junção :

CREATE TABLE prodcats AS SELECT id AS product_id, unnest(category_ids) AS category_id FROM products;
CREATE INDEX idx_prodcats_cat_prod_id ON prodcats (category_id, product_id);

SELECT p.* FROM products p JOIN prodcats c ON (p.id=c.product_id)
WHERE c.category_id=248688
ORDER BY p.score DESC, p.title LIMIT 10 OFFSET 30000;

Limit  (cost=122480.06..122480.09 rows=10 width=1390) (actual time=1290.360..1290.362 rows=10 loops=1)
  ->  Sort  (cost=122405.06..122509.00 rows=41574 width=1390) (actual time=1264.250..1289.575 rows=30010 loops=1)
        Sort Key: p.score, p.title
        Sort Method: external merge  Disk: 29656kB
        ->  Merge Join  (cost=50.46..94061.13 rows=41574 width=1390) (actual time=117.746..182.048 rows=41666 loops=1)
              Merge Cond: (p.id = c.product_id)
              ->  Index Scan using products_pkey on products p  (cost=0.42..90738.43 rows=646067 width=1390) (actual time=0.034..116.313 rows=210283 loops=1)
              ->  Index Only Scan using idx_prodcats_cat_prod_id on prodcats c  (cost=0.43..1187.98 rows=41574 width=4) (actual time=0.022..7.137 rows=41666 loops=1)
                    Index Cond: (category_id = 248688)
                    Heap Fetches: 0
Planning time: 0.873 ms
Execution time: 1294.826 ms

Ainda sem usar o índice da árvore B, o conjunto de resultados não se encaixava work_mem, portanto, resultados ruins.

Mas, em algumas circunstâncias, ter um grande número de produtos e um pequeno deslocamento do PostgreSQL agora decide usar o índice da árvore B:

SELECT p.* FROM products p JOIN prodcats c ON (p.id=c.product_id)
WHERE c.category_id=248688
ORDER BY p.score DESC, p.title LIMIT 10 OFFSET 300;

Limit  (cost=3986.65..4119.51 rows=10 width=1390) (actual time=264.176..264.574 rows=10 loops=1)
  ->  Nested Loop  (cost=0.98..552334.77 rows=41574 width=1390) (actual time=250.378..264.558 rows=310 loops=1)
        ->  Index Scan using idx_test7 on products p  (cost=0.55..194665.62 rows=646067 width=1390) (actual time=0.030..83.026 rows=108037 loops=1)
        ->  Index Only Scan using idx_prodcats_cat_prod_id on prodcats c  (cost=0.43..0.54 rows=1 width=4) (actual time=0.001..0.001 rows=0 loops=108037)
              Index Cond: ((category_id = 248688) AND (product_id = p.id))
              Heap Fetches: 0
Planning time: 0.585 ms
Execution time: 264.664 ms

Isso é de fato bastante lógico, pois o índice da árvore B aqui não produz resultado direto, é usado apenas como um guia para varredura seqüencial.

Vamos comparar com a consulta GIN:

SELECT * FROM products WHERE id in (
  SELECT id FROM products WHERE category_ids @> ARRAY[248688]
  ORDER BY score DESC, title LIMIT 10 OFFSET 300
) ORDER BY score DESC, title;

Sort  (cost=2519.53..2519.55 rows=10 width=1390) (actual time=143.809..143.809 rows=10 loops=1)
  Sort Key: products.score, products.title
  Sort Method: quicksort  Memory: 35kB
  ->  Nested Loop  (cost=2435.14..2519.36 rows=10 width=1390) (actual time=143.693..143.736 rows=10 loops=1)
        ->  HashAggregate  (cost=2434.71..2434.81 rows=10 width=4) (actual time=143.678..143.680 rows=10 loops=1)
              Group Key: products_1.id
              ->  Limit  (cost=2434.56..2434.59 rows=10 width=72) (actual time=143.668..143.670 rows=10 loops=1)
                    ->  Sort  (cost=2433.81..2435.43 rows=646 width=72) (actual time=143.642..143.653 rows=310 loops=1)
                          Sort Key: products_1.score, products_1.title
                          Sort Method: top-N heapsort  Memory: 68kB
                          ->  Bitmap Heap Scan on products products_1  (cost=17.01..2403.85 rows=646 width=72) (actual time=11.625..31.868 rows=41666 loops=1)
                                Recheck Cond: (category_ids @> '{248688}'::integer[])
                                Heap Blocks: exact=6471
                                ->  Bitmap Index Scan on idx_products_category_ids_gin  (cost=0.00..16.85 rows=646 width=0) (actual time=9.916..9.916 rows=41666 loops=1)
                                      Index Cond: (category_ids @> '{248688}'::integer[])
        ->  Index Scan using products_pkey on products  (cost=0.42..8.45 rows=1 width=1390) (actual time=0.004..0.004 rows=1 loops=10)
              Index Cond: (id = products_1.id)
Planning time: 0.630 ms
Execution time: 143.921 ms

O resultado do GIN é muito melhor. Eu verifiquei com várias combinações de número de produtos e offset, em nenhuma circunstância a abordagem da tabela de junções era melhor .

O poder do índice real

Para que o PostgreSQL utilize totalmente o índice para classificação, todos os WHEREparâmetros de consulta e os ORDER BYparâmetros devem residir no índice de árvore B único. Para fazer isso, copiei os campos de classificação do produto para a tabela de junção:

CREATE TABLE prodcats AS SELECT id AS product_id, unnest(category_ids) AS category_id, score, title FROM products;
CREATE INDEX idx_prodcats_1 ON prodcats (category_id, score DESC, title, product_id);

SELECT * FROM products WHERE id in (SELECT product_id FROM prodcats WHERE category_id=248688 ORDER BY score DESC, title LIMIT 10 OFFSET 30000) ORDER BY score DESC, title;

Sort  (cost=2149.65..2149.67 rows=10 width=1390) (actual time=7.011..7.011 rows=10 loops=1)
  Sort Key: products.score, products.title
  Sort Method: quicksort  Memory: 35kB
  ->  Nested Loop  (cost=2065.26..2149.48 rows=10 width=1390) (actual time=6.916..6.950 rows=10 loops=1)
        ->  HashAggregate  (cost=2064.83..2064.93 rows=10 width=4) (actual time=6.902..6.904 rows=10 loops=1)
              Group Key: prodcats.product_id
              ->  Limit  (cost=2064.02..2064.71 rows=10 width=74) (actual time=6.893..6.895 rows=10 loops=1)
                    ->  Index Only Scan using idx_prodcats_1 on prodcats  (cost=0.56..2860.10 rows=41574 width=74) (actual time=0.010..6.173 rows=30010 loops=1)
                          Index Cond: (category_id = 248688)
                          Heap Fetches: 0
        ->  Index Scan using products_pkey on products  (cost=0.42..8.45 rows=1 width=1390) (actual time=0.003..0.003 rows=1 loops=10)
              Index Cond: (id = prodcats.product_id)
Planning time: 0.318 ms
Execution time: 7.066 ms

E este é o pior cenário, com grande número de produtos na categoria escolhida e grande deslocamento. Quando offset = 300, o tempo de execução é de apenas 0,5 ms.

Infelizmente, a manutenção dessa tabela de junção exige um esforço extra. Isso pode ser realizado por meio de visualizações materializadas indexadas, mas isso só é útil quando os dados são atualizados raramente, pois a atualização dessa visualização materializada é uma operação bastante pesada.

Então, eu estou ficando com o índice GIN até agora, com aumento work_meme redução da consulta de pegada de memória.

Yaroslav Stavnichiy
fonte
Você não precisa reiniciar para alterar a work_memconfiguração geral no postgresql.conf. Recarregar é suficiente. E deixe-me alertar contra a definição work_memmuito alta globalmente em um ambiente multiusuário (também não muito baixo). Se você tiver alguma dúvida que precise de mais work_mem, defina-a mais alta para a sessão apenas com SET- ou apenas a transação com SET LOCAL. Veja: dba.stackexchange.com/a/48633/3684
Erwin Brandstetter
Que ótima resposta. Ajudou-me muito, especificamente com a operação de classificação de disco -> na memória, troca rápida para uma grande vitória, obrigado!
Ricardo Villamil 24/09
4

Aqui estão algumas dicas rápidas que podem ajudar a melhorar seu desempenho. Começarei com a dica mais fácil, que é quase sem esforço da sua parte, e passarei à dica mais difícil após a primeira.

1 work_mem

Portanto, vejo imediatamente que uma classificação relatada no seu plano de explicação Sort Method: external merge Disk: 5696kBestá consumindo menos de 6 MB, mas está sendo derramada no disco. Você precisa aumentar sua work_memconfiguração em seu postgresql.confarquivo para ser grande o suficiente para que a classificação possa caber na memória.

EDIT: Além disso, em uma inspeção mais aprofundada, vejo que, depois de usar o índice para verificar catgory_idsquais se encaixam nos seus critérios, a verificação do índice de bitmap é forçada a se tornar "com perdas" e precisa verificar novamente a condição ao ler as linhas nas páginas de heap relevantes . Consulte este post no postgresql.org para obter uma explicação melhor do que eu dei. : P O ponto principal é que você work_memestá muito baixo. Se você não ajustou as configurações padrão do seu servidor, ele não terá um bom desempenho.

Essa correção levará basicamente um tempo para você fazer. Uma mudança para postgresql.conf, e você está fora! Consulte esta página de ajuste de desempenho para obter mais dicas.

2. Mudança de esquema

Portanto, você tomou a decisão em seu design de esquema de desnormalizar category_idsem uma matriz inteira, o que o força a usar um índice GIN ou GIST para obter acesso rápido. Na minha experiência, sua escolha de um índice GIN será mais rápida para leituras do que um GIST, portanto, nesse caso, você fez a escolha certa. No entanto, GIN é um índice não classificado; pensar sobre isso mais como um valor-chave, onde predicados de igualdade são fáceis de verificar, mas operações como WHERE >, WHERE <ou ORDER BYnão são facilitados pelo índice.

Uma abordagem decente seria normalizar seu design usando uma tabela de ponte / tabela de junção , usada para especificar relacionamentos muitos para muitos nos bancos de dados.

Nesse caso, você tem muitas categorias e um conjunto de números inteiros correspondentes category_ide muitos produtos e seus product_ids correspondentes . Em vez de uma coluna na tabela do produto que é uma matriz inteira de category_ids, remova essa coluna da matriz do esquema e crie uma tabela como

CREATE TABLE join_products_categories (product_id int, category_id int);

Em seguida, você pode gerar índices da árvore B nas duas colunas da tabela de ponte,

CREATE INDEX idx_products_in_join_table ON join_products_categories (product_id);
CREATE INDEX idx_products_in_join_table ON join_products_categories (category_id);

Apenas minha humilde opinião, mas essas mudanças podem fazer uma grande diferença para você. Experimente essa work_memmudança, no mínimo.

Boa sorte!

EDITAR:

Crie um índice adicional para ajudar na classificação

Portanto, se com o tempo sua linha de produtos se expandir, determinadas consultas poderão retornar muitos resultados (milhares, dezenas de milhares?), Mas que ainda poderão ser apenas um pequeno subconjunto de sua linha de produtos total. Nesses casos, a classificação pode até ser bastante cara se for feita na memória, mas um índice adequadamente projetado pode ser usado para ajudar na classificação.

Veja a documentação oficial do PostgreSQL descrevendo Indexes e ORDER BY .

Se você criar um índice que corresponda às suas ORDER BYnecessidades

CREATE INDEX idx_product_sort ON products (score DESC, title);

o Postgres otimizará e decidirá se usar o índice ou executar uma classificação explícita será mais econômico. Lembre-se de que não há garantia de que o Postgres use o índice; procurará otimizar o desempenho e escolher entre usar o índice ou classificar explicitamente. Se você criar esse índice, monitore-o para ver se está sendo usado o suficiente para justificar sua criação e descarte-o se a maioria de suas classificações estiver sendo feita explicitamente.

Ainda assim, neste momento, sua melhoria 'maior retorno do investimento' provavelmente estará usando mais work_mem, mas há casos em que o índice pode suportar a classificação.

Chris
fonte
Eu também estava pensando em usar a tabela de junção para evitar o GIN. Mas você não especificou como isso ajudará na classificação. Eu acho que não vai ajudar. Tentei associar a tabela de produtos a um conjunto de IDs de produtos coletados por meio da consulta GIN, que acredito ser bastante semelhante à associação que você está oferecendo, e essa operação não pôde usar o índice da árvore b na pontuação e no título. Talvez eu tenha construído um índice errado. Poderia, por favor, elaborar sobre isso.
Yaroslav Stavnichiy
Desculpas, talvez eu não tenha explicado com clareza suficiente. A alteração de sua work_memconfiguração foi planejada como uma correção para o problema de "classificação em disco", bem como para o problema de verificação de condição. À medida que o número de produtos aumenta, pode ser necessário ter um índice adicional para classificar. Por favor, veja minhas edições acima para esclarecimentos.
28415 Chris