A pesquisa de trigramas fica muito mais lenta à medida que a sequência de pesquisa fica mais longa

16

Em um banco de dados do Postgres 9.1, tenho uma tabela table1com ~ 1.5M linhas e uma coluna label(nomes simplificados para fins de pergunta).

Existe um índice trigrama funcional ativado lower(unaccent(label))( unaccent()foi tornado imutável para permitir seu uso no índice).

A seguinte consulta é bastante rápida:

SELECT count(*) FROM table1
WHERE (lower(unaccent(label)) like lower(unaccent('%someword%')));
 count 
-------
     1
(1 row)

Time: 394,295 ms

Mas a seguinte consulta é mais lenta:

SELECT count(*) FROM table1
WHERE (lower(unaccent(label)) like lower(unaccent('%someword and some more%')));
 count 
-------
     1
(1 row)

Time: 1405,749 ms

E adicionar mais palavras é ainda mais lento, mesmo que a pesquisa seja mais rigorosa.

Tentei um truque simples para executar uma subconsulta para a primeira palavra e, em seguida, uma consulta com a string de pesquisa completa, mas (infelizmente) o planejador de consultas viu através de minhas maquinações:

EXPLAIN ANALYZE
SELECT * FROM (
   SELECT id, title, label from table1
   WHERE lower(unaccent(label)) like lower(unaccent('%someword%'))
   ) t1
WHERE lower(unaccent(label)) like lower(unaccent('%someword and some more%'));
Análise de Heap de Bitmap na tabela1 (custo = 16216.01..16220.04 linhas = 1 largura = 212) (tempo real = 1824.017..1824.019 linhas = 1 loops = 1)
  Verifique novamente Cond: ((lower (unaccent ((label) :: text)) ~~ '% someord%' :: text) AND (lower (unaccent ((label) :: text)) ~~ '% someord e mais %'::texto))
  -> Varredura de índice de bitmap na tabela1_label_hun_gin_trgm (custo = 0.00..16216.01 linhas = 1 largura = 0) (tempo real = 1823.900..1823.900 linhas = 1 loops = 1)
        Índice Cond: ((lower (unaccent ((label) :: text)) ~~ '% someord%' :: text) AND (lower (unaccent ((label) :: text)) ~~ '% someord e mais alguns %'::texto))
Tempo de execução total: 1824.064 ms

Meu problema final é que a string de pesquisa vem de uma interface da web que pode enviar strings bastante longas e, portanto, bastante lenta e também pode constituir um vetor DOS.

Então, minhas perguntas são:

  • Como acelerar a consulta?
  • Existe uma maneira de dividi-lo em subconsultas para que seja mais rápido?
  • Talvez uma versão posterior do Postgres seja melhor? (Eu tentei a 9.4 e não parece mais rápido: ainda o mesmo efeito. Talvez uma versão posterior?)
  • Talvez seja necessária uma estratégia de indexação diferente?
P.Péter
fonte
11
Deve-se mencionar que unaccent()também é fornecido por um módulo adicional e o Postgres não suporta índices na função por padrão, pois não é IMMUTABLE. Você deve ter alterado alguma coisa e deve mencionar o que fez exatamente na sua pergunta. Meu conselho permanente: stackoverflow.com/a/11007216/939860 . Além disso, os índices trigramas oferecem suporte à correspondência sem distinção entre maiúsculas e minúsculas. Você pode simplificar para: WHERE f_unaccent(label) ILIKE f_unaccent('%someword%')- com um índice correspondente. Detalhes: stackoverflow.com/a/28636000/939860 .
Erwin Brandstetter
Eu simplesmente declarei unaccentimutável. Eu adicionei isso à pergunta.
P.Péter
Esteja ciente de que o hack é substituído quando você atualiza o unaccentmódulo. Uma das razões pelas quais sugiro um wrapper de função.
Erwin Brandstetter

Respostas:

34

No PostgreSQL 9.6, haverá uma nova versão do pg_trgm, 1.2, que será muito melhor sobre isso. Com um pouco de esforço, você também pode fazer com que esta nova versão funcione no PostgreSQL 9.4 (você deve aplicar o patch, compilar o módulo de extensão e instalá-lo).

O que a versão mais antiga faz é procurar cada trigrama na consulta, obter a união deles e aplicar um filtro. O que a nova versão fará é escolher o trigrama mais raro na consulta e procurar apenas esse e depois filtrar o restante mais tarde.

O mecanismo para fazer isso não existe na 9.1. Na versão 9.4, essa maquinaria foi adicionada, mas o pg_trgm não foi adaptado para usá-la naquele momento.

Você ainda teria um possível problema do DOS, pois a pessoa mal-intencionada pode criar uma consulta que possua apenas trigramas comuns. como '% e%' ou mesmo '% a%'


Se você não pode atualizar para o pg_trgm 1.2, outra maneira de enganar o planejador seria:

WHERE (lower(unaccent(label)) like lower(unaccent('%someword%'))) 
AND   (lower(unaccent(label||'')) like 
      lower(unaccent('%someword and some more%')));

Concatenando a cadeia vazia a ser rotulada, você faz o planejador pensar que ela não pode usar o índice nessa parte da cláusula where. Portanto, ele usa o índice apenas no% someord% e aplica um filtro apenas a essas linhas.


Além disso, se você estiver sempre procurando palavras inteiras, poderá usar uma função para tokenizar a sequência em uma matriz de palavras e usar um índice GIN interno regular (não pg_trgm) nessa função de retorno de matriz.

jjanes
fonte
13
Vale ressaltar que você foi quem escreveu o patch. E testes preliminares de desempenho são impressionantes. Isso realmente merece mais votos (também para a explicação e solução alternativa com a versão atual).
Erwin Brandstetter
Eu estaria mais interessado em pelo menos uma referência ao mecanismo que você usou para implementar o patch que não estava presente na 9.1. Mas, eu concordo com a resposta de Erwin.
Evan Carroll
3

Eu encontrei uma maneira de enganar o planejador de consultas, é um truque bastante simples:

SELECT *
FROM (
   select id, title, label
   from   table1
   where  lower(unaccent(label)) like lower(unaccent('%someword%'))
   ) t1
WHERE lower(lower(unaccent(label))) like lower(unaccent('%someword and more%'))

EXPLAIN resultado:

Varredura de Heap de Bitmap na tabela1 (custo = 6749.11..7332.71 linhas = 1 largura = 212) (tempo real = 256.607..256.609 linhas = 1 loops = 1)
  Verifique novamente Cond: (lower (unaccent ((label_hun) :: text)) ~~ '% someord%' :: text)
  Filtro: (lower (lower (unaccent ((label) :: text))) ~~ '% someord e um pouco mais%' :: text)
  -> Verificação de índice de bitmap na tabela1_label_hun_gin_trgm (custo = 0.00..6749.11 linhas = 147 largura = 0) (tempo real = 256.499..256.499 linhas = 1 loops = 1)
        Cond Condição do índice: (lower (unaccent ((label) :: text)) ~~ '% someord%' :: text)
Tempo de execução total: 256.653 ms

Portanto, como não há índice lower(lower(unaccent(label))), isso criaria uma varredura seqüencial, transformando-a em um filtro simples. Além do mais, um simples E também fará o mesmo:

SELECT id, title, label
FROM table1
WHERE lower(unaccent(label)) like lower(unaccent('%someword%'))
AND   lower(lower(unaccent(label))) like lower(unaccent('%someword and more%'))

Obviamente, essa é uma heurística que pode não funcionar bem, se a parte cortada usada na varredura de índice for muito comum. Mas em nosso banco de dados, não há muita repetição, se eu usar de 10 a 15 caracteres.

Há duas pequenas perguntas restantes:

  • Por que o postgres não pode descobrir que algo assim seria benéfico?
  • O que o postgres faz no intervalo de 0..256.499 (consulte analisar saída)?
P.Péter
fonte
11
No intervalo de tempo entre 0 e 256.499, está criando o bitmap. Em 256.499, produz sua primeira saída, que é o bitmap. Qual também é sua última saída, pois produz apenas uma única saída - um único bitmap concluído.
precisa saber é