Criando um mecanismo de busca avançado com PostgreSQL

 (xata.io)
6 pontos por GN⁺ 2023-07-13 | 1 comentários | Compartilhar no WhatsApp
  • A busca de texto completo do PostgreSQL é uma abordagem para construir recursos de busca sem um mecanismo separado, combinando tsvector, tsquery, @@, ts_rank e índices GIN
  • Termos de busca e documentos são normalizados no nível de lexeme, e consultas podem ser expressas com operadores como AND, OR, NOT e FOLLOWED BY, permitindo implementar boa parte da sintaxe comum de busca
  • Em um ambiente de exemplo, o índice GIN reduziu o tempo de busca de mais de 200 ms para cerca de 4 ms, mas, quando há muitos resultados, o custo de ranking e ordenação com ts_rank pode se tornar um gargalo
  • O ajuste de relevância pode ser implementado adicionando sinais como peso do título, número de votos, avaliação, gênero e atualidade à expressão de ordenação, ou atribuindo pesos por coluna com setweight
  • Tolerância a erros de digitação, busca facetada, autocomplete, busca exata por frase e busca híbrida também são possíveis, mas no PostgreSQL é preciso compor os componentes manualmente, e em conjuntos de dados grandes é necessário verificar os limites de desempenho

A abordagem da busca de texto completo no PostgreSQL

  • O PostgreSQL fornece componentes de baixo nível para busca de texto completo, que podem ser combinados para criar funcionalidades de um mecanismo de busca
  • Essa abordagem é flexível, mas exige mais trabalho de implementação do que Elasticsearch, Typesense e Meilisearch, que têm busca de texto completo como caso de uso principal
  • As consultas de exemplo usam o dataset Wikipedia Movie Plots do Kaggle
    • Inclui 34.000 títulos de filmes
    • O tamanho em formato CSV é de cerca de 81 MB

Componentes principais

  • A busca de texto completo do PostgreSQL funciona principalmente com os seguintes elementos
    • tsvector: armazena o texto pesquisável como uma lista de lexemes normalizados
    • tsquery: representa uma consulta de busca normalizada
    • @@: operador de correspondência que verifica se um tsquery combina com um tsvector
    • ts_rank, ts_rank_cd: calculam a pontuação de relevância dos resultados
    • Índice GIN: índice invertido para consultar tsvector com eficiência

tsvector e configurações de busca

  • tsvector armazena uma lista ordenada de lexemes
    • Um lexeme é parecido com um token, mas é uma string normalizada para que diferentes formas da mesma palavra sejam unificadas
    • Na configuração para inglês, a normalização converte maiúsculas em minúsculas e remove sufixos
  • Ao analisar uma frase em inglês com to_tsvector, stop words como “I”, “to” e “an” são removidas
    • “refuse” e “Refusing” são ambos convertidos para refus
    • A pontuação é ignorada
    • A posição das palavras e seus pesos no texto original também são registrados
  • Se, em vez da configuração english, for usada a configuração simple, as palavras são incluídas na forma em que aparecem no texto
    • “refuse” e “refusing” permanecem como lexemes diferentes
    • A configuração simple é especialmente útil para colunas com rótulos ou tags
  • O PostgreSQL oferece configurações de busca embutidas para vários idiomas, mas não há configuração para CJK (chinês, japonês e coreano)
    • Para idiomas não suportados, a configuração simple pode funcionar bem na prática
    • Ainda assim, não é certo que ela seja suficiente para CJK

tsquery e representação de consultas

  • tsquery é um tipo de dado que representa uma consulta de busca normalizada
    • Os termos de busca já devem estar normalizados como lexemes
    • Vários termos podem ser combinados com operadores AND, OR, NOT e FOLLOWED BY
  • to_tsquery, plainto_tsquery e websearch_to_tsquery ajudam a transformar o texto digitado pelo usuário em um tsquery apropriado
    • O papel principal é normalizar as palavras contidas no texto de entrada
  • Com websearch_to_tsquery, é possível criar consultas mais próximas de uma caixa de busca comum
    • darth vader é tratado como um AND lógico, exigindo que as duas palavras estejam no documento
    • Também é possível fazer busca OR e excluir palavras
    • A busca por frase representa palavras aparecendo em sequência e na ordem correta
  • Na configuração para inglês, stop words como “the” são removidas, então em algumas buscas por frase quase toda a expressão pode desaparecer
    • Nesses casos, usar a configuração simple pode produzir o resultado esperado
  • O operador @@ é usado para verificar se um tsquery corresponde a um tsvector

Índices GIN e desempenho de busca

  • GIN é a sigla de Generalized Inverted Index, um tipo de índice projetado para consultas que procuram valores de elementos contidos em valores compostos
  • O GIN pode ser usado não apenas para busca em texto, mas também para consultas em JSON
  • É possível criar uma coluna tsvector combinando várias colunas pesquisáveis e então criar um índice GIN sobre essa coluna
  • No ambiente de exemplo, o índice GIN reduziu o tempo de busca de mais de 200 ms para cerca de 4 ms

Ranking e cálculo de relevância

  • Para uma boa experiência de busca, os resultados devem ser ordenados por relevância
  • O PostgreSQL fornece duas funções de ranking predefinidas: ts_rank e ts_rank_cd
    • Ambas consideram a frequência de ocorrência dos termos de busca
    • ts_rank_cd também reflete a proximidade entre lexemes correspondentes
  • A relevância depende fortemente da natureza da aplicação
    • As funções de ranking padrão são mais um ponto de partida, e podem ser substituídas por uma função própria ou combinadas com outros fatores conforme necessário
  • ts_rank precisa acessar a coluna search de cada resultado
    • Se muitas linhas corresponderem à condição WHERE, o PostgreSQL precisará visitar todas elas para calcular o ranking e ordenar
    • No ambiente de exemplo, uma consulta foi retornada em 5–7 ms, mas uma consulta como darth OR vader, que precisava ranquear mais de 1.000 resultados, levou cerca de 80 ms

Ajuste de relevância

  • A relevância baseada em frequência de palavras é um bom padrão inicial, mas os dados podem ter sinais mais importantes do que a frequência
  • No dataset de filmes, os seguintes sinais podem ser refletidos na relevância
    • Tratar correspondências no título como mais importantes do que correspondências na descrição ou sinopse
    • Promover filmes mais populares com base na avaliação ou no número de votos
    • Se o usuário prefere comédia, posicionar filmes de comédia mais acima
    • Considerar títulos mais recentes como mais relevantes do que títulos antigos
  • Mecanismos de busca dedicados oferecem recursos para configurar como diferentes colunas ou campos influenciam o ranking

Boost com números, datas e valores exatos

  • O PostgreSQL não fornece diretamente boost com base em outras colunas, mas ranking no fim das contas é uma expressão de ordenação, então é possível adicionar seus próprios sinais
  • Para refletir o número de votos, isso pode ser implementado somando ao score de ranking um boost baseado na contagem de votos
    • No exemplo, é usado log para suavizar o impacto
    • O coeficiente 0.01 ajusta o booster para uma escala parecida com a do score de ranking
  • Também é possível criar uma função mais complexa que aumente a avaliação apenas quando o número de votos atingir certo nível
  • Se quiser promover um gênero específico, pode usar uma função como valueBooster, que retorna um coeficiente apenas quando o valor coincide com o de uma determinada coluna

Pesos por coluna

  • Os lexemes em tsvector podem receber pesos
  • O PostgreSQL oferece quatro pesos: A, B, C e D
    • A é o peso mais alto
    • D é o mais baixo e o padrão
  • A função setweight permite controlar os pesos ao criar a coluna tsvector
  • Ao dar mais peso à coluna de título, filmes cujo termo de busca aparece no título sobem para o topo dos resultados e também recebem uma pontuação maior
  • O fato de existirem apenas quatro classes de peso é uma limitação, e os pesos precisam ser aplicados ao calcular o tsvector

Tolerância a erros de digitação e busca difusa

  • O PostgreSQL não oferece suporte direto a busca difusa nem tolerância a erros de digitação ao usar tsvector e tsquery
  • Partindo da suposição de que há erros de digitação na consulta, isso pode ser implementado da seguinte forma
    • Indexar todos os lexemes do conteúdo em uma tabela separada
    • Para cada palavra da consulta, procurar palavras candidatas por similaridade ou distância de Levenshtein
    • Modificar a consulta para incluir as palavras encontradas
    • Executar a busca com a consulta modificada
  • No exemplo, é usada a distância de Levenshtein, por ser uma das abordagens usadas por mecanismos de busca para busca difusa
  • Depois de obter a lista de palavras candidatas, a consulta precisa ser ajustada para incluir todas elas

Busca facetada

  • A busca facetada é amplamente usada, especialmente em sites de e-commerce, para que o usuário refine repetidamente o escopo da busca
  • No PostgreSQL, isso pode ser implementado definindo manualmente as categorias e adicionando-as à condição WHERE da busca
  • Também é possível criar categorias de forma algorítmica com base nos dados existentes
    • No exemplo, é criada uma faceta “Decade” com base no ano do filme
    • A quantidade de correspondências por década pode ser calculada e exibida entre parênteses
  • Para obter várias facetas em uma única consulta, é possível combinar CTEs
  • Essa abordagem pode funcionar bem em datasets pequenos e médios, mas pode ficar lenta em datasets muito grandes

Escopo e limites de um mecanismo de busca com PostgreSQL

  • Ao combinar os componentes de busca de texto completo do PostgreSQL, é possível construir um mecanismo de busca bastante avançado
  • A busca baseada em PostgreSQL também oferece suporte a joins e transações ACID
    • Esses são recursos que outros mecanismos de busca normalmente não têm
  • Outros tópicos avançados de busca que valem exploração incluem
    • Sugestões e autocomplete
    • Correspondência exata de frases
    • Busca híbrida combinada com pg-vector
  • Esses recursos são possíveis com PostgreSQL, mas exigem compor os componentes manualmente
  • Em alguns casos, o desempenho pode cair em datasets muito grandes
  • O texto seguinte, part 2, compara implementar a busca no PostgreSQL com adicionar o Elasticsearch à infraestrutura e sincronizar os dados

Leituras relacionadas

1 comentários

 
GN⁺ 2023-07-13
Comentários do Hacker News

  • Não tente fazer isso imitando os recursos do Elasticsearch
    Nos anos 2000, eu já criei um mecanismo de busca em MySQL 3.x que fazia parsing de dados EXIF de imagens para indexar uma taxonomia de 3 níveis com contagens; era algo que vários fornecedores caros não conseguiam fazer direito, e a Autonomy nem sequer acertava a classificação de nível mais alto
    Depois de 6 semanas escrevendo SQL frágil em que até mudar a ordem das colunas no SELECT alterava o desempenho, consegui fazer funcionar, mas não tenho a menor vontade de repetir a experiência. Bancos de dados são essencialmente muito parecidos, mas os mecanismos de busca evoluíram muito mais
    Dá para fazer por curiosidade intelectual, mas busca não é só tokenizar e pronto. Logo aparecem exigências como navegação por categorias, múltiplos idiomas, sinônimos automáticos, sugestões de ortografia do tipo "Você quis dizer", desempenho em grande escala, e você acaba preso num beco sem saída. Pela sua saúde mental, é melhor usar um mecanismo de busca, e para sincronizar PG com ES existem ferramentas como ZomboDB ou PGSync

    • Há duas discussões diferentes misturadas nesta thread. Se você vai criar um mecanismo de busca voltado ao cliente, faz sentido usar uma ferramenta poderosa como Elasticsearch e não reinventar a roda
      Por outro lado, se analistas de dados ou desenvolvedores só querem pesquisar colunas de texto em um banco grande com mais flexibilidade do que LIKE/ILIKE, pode ser mais fácil e mais rápido chegar a 90% criando um índice/tabela de busca full-text dentro do mesmo banco

  • Estou ansioso pela parte 2 comparando Postgres vs Elasticsearch. Um dos aplicativos da empresa usa PG para CRUD de objetos e Elastic para busca, mas subestimamos completamente o esforço de sincronizar os dois armazenamentos de dados e estamos realmente considerando remover o Elasticsearch

    • Um jeito que já usei antes é tratar o Elasticsearch como algo que pode ser reconstruído a qualquer momento
      A cada 5 minutos, um cron procura no banco os objetos a indexar em que last_modified_at > last_indexing_started_timestamp, indexa no Elasticsearch e depois atualiza last_indexing_started_timestamp com o horário de início da sincronização. Assim, os objetos modificados entre o início e o fim da execução são capturados na próxima rodada
      Se for preciso reconstruir o Elasticsearch, basta limpar o último horário de indexação e sincronizar tudo de novo desde o início; isso permite autorrecuperação e evita que a sincronização saia do eixo
    • Em um emprego anterior usamos uma configuração parecida, e não era algo especialmente difícil. Cada vez que uma entidade no PG era atualizada, enviávamos uma mensagem para replicá-la de forma assíncrona no ES, e o lado do ES era preenchido consultando o PG pelo ID
      Como em qualquer trabalho assíncrono, você sempre precisa de monitoramento e retries, mas o ES era estável e rápido, então problemas eram raros. Dito isso, a exigência de consistência era frouxa, então bastava que o estado mais recente do PG chegasse ao ES em um tempo razoável; com outros requisitos, pode ser diferente
    • Seguimos mais ou menos esse caminho, com Postgres para CRUD e Elastic para busca, mas subestimamos não só a sincronização entre os dois armazenamentos como também a operação estável de um cluster Elastic com equipe e experiência limitadas
      Depois que migramos para a busca full-text do Postgres com pesos em índices e consultas, conseguimos resolver tudo o que precisávamos inteiramente dentro do Postgres, só com triggers de atualização e consultas de busca muito rápidas
    • Alguém já usou zombodb? [https://www.zombodb.com/]
    • Já usei, e foi um trabalho difícil mesmo com bastante experiência; alguns resultados chegaram a ser piores. Na maior parte foi parecido, e só em poucos casos foi melhor
      No geral foi um sucesso, e a redução da carga operacional compensou bem o tempo de engenharia investido, mas não é algo para começar de maneira leviana
      Dependendo da necessidade, views materializadas, views normais e triggers podem ser melhores. A busca de texto embutida pode não servir ao seu caso de uso, e criar uma alternativa não é necessariamente tão difícil

  • Sem tempos de consulta p50/p99 sob carga realista, é difícil considerar isso comprovado. Um mecanismo de busca que devolve resultados em 1 minuto não é "avançado", e até um banco relacional como o Postgres pode parecer capaz no papel

    • Como autor do texto, estou planejando um artigo futuro comparando com Elasticsearch, mas acho que não vou tentar fazer benchmarks. Qualquer cenário realista que eu montar provavelmente não vai bater exatamente com o caso de uso de cada um
      Em geral concordo; em escala grande, por exemplo acima de alguns milhões de registros, é bem provável que eu não usaria essa abordagem. Meu principal interesse era ver até que ponto eu conseguiria replicar os recursos
      Em casos de uso de busca pequenos, há a vantagem de manter menos infraestrutura, além de consistência forte, joins e coisas do tipo. Na Xata, também estamos pensando numa transição suave: começar com Postgres em pequena escala e depois migrar para Elasticsearch com o mínimo de breaking changes
    • Quando entrevistei um ex-funcionário do Google, ouvi que eles armazenavam em cache todos os resultados de buscas já feitas e atualizavam esses resultados em cache junto com o índice
      Nessa perspectiva, resultados de busca rápidos em si não parecem tão surpreendentes. Você pode continuar atualizando os resultados em cache em tarefas de background e, quando a requisição chegar, simplesmente entregá-los. Esse tipo de cache e tempo de resposta parece separado da velocidade real de cálculo dos resultados de busca
    • Há um problema em exigir p50/p99 sob carga realista. Como criar a carga realmente realista de um mecanismo de busca em situações em que muita gente na prática não está pesquisando? Ficar disparando termos aleatórios não é realista
      Há pessoas com conexões lentas, e certos termos específicos, como terremoto, podem disparar só em certas regiões
      Se os termos forem aleatórios demais, o cache não terá resultados e o desempenho parecerá pior do que o real; se não forem aleatórios o suficiente, parecerá melhor do que o real
    • O Lucene, base usada por Elasticsearch e Solr, é um índice invertido, e o GIN do artigo também usa a mesma abordagem
      Portanto, a vantagem de ES e afins está em escalar horizontalmente por vários nós ou nos recursos adicionais colocados sobre o índice principal
    • Uso a busca full-text do Postgres e ela funciona bem. Só é preciso saber como ranquear as linhas na consulta
      Usar apenas ts_rank é perfeitamente válido, mas normalmente você acaba querendo ajustar a ordenação com outras métricas de relevância. Se resolver isso, de modo que essa métrica não precise ser o critério principal de ordenação, os resultados ficam tão rápidos quanto consultas normais a tabelas com índice em um banco comum

  • Quando era adolescente, tentei criar um mecanismo de busca e um banco de dados do zero sem entender muito bem nenhum dos dois. Queria ver até onde dava para ir e com que rapidez e relevância eu conseguiria retornar resultados de busca
    Criar rapidamente um banco de dados e um mecanismo de busca básicos provavelmente é bem fácil até para um programador amador. Se você entender algoritmos básicos de ciência da computação e como aproveitar sistema operacional e hardware, dá para fazer em um ou dois meses
    Mesmo com uma linguagem de alto nível, a velocidade não era ruim, e em um notebook de 2003 chegava a cerca de 250 mil QPS. Com sharding, escalabilidade também não é um grande problema. Indexação, travas e consistência são mais complexas do que armazenamento e consulta
    O verdadeiro grande problema é a subjetividade da busca. Quando entram questões como o que a pessoa realmente quer encontrar, como buscar quando nem eu sei o que estou procurando, como impedir quem quer abusar do sistema e como lidar com consultas e conjuntos de dados complexos, a dificuldade sobe várias ordens de magnitude

    • 250 mil RPS parece bastante, já que nem o SQLite hoje em dia faz isso. Índice invertido parece que seria ainda mais caro, e o RocksDB fica em cerca de 130 mil RPS, mas talvez esse número tenha sido em hardware mais forte que o meu notebook ou meu ambiente esteja configurado errado
      Fico curioso se você realmente usou um banco de dados de propósito geral e se esse número está correto. Queria saber que técnicas foram usadas para superar esses motores
    • O maior problema ao criar um mecanismo de busca não é o QPS, e sim o tamanho do conjunto de dados a ser indexado. Se a estrutura de busca couber na memória de uma única máquina, a latência fica quase zero e dá para oferecer um QPS praticamente infinito
      Passando disso, são necessárias soluções criativas, e é aí que começam a surgir vários trade-offs
    • Fico curioso para saber se isso está disponível como open source em algum lugar

  • Um dos vários problemas ao fazer busca dentro do Postgres é que busca é uma carga muito intensiva de CPU, e a tendência é usar cada vez mais GPU também. No cenário ideal, você quer deixar a CPU do banco disponível para atualizações transacionais do modelo de dados principal
    Já vi muitos clusters de ES e Solr rodando a 100% em mais de 10 nós durante reindexação, ou consumindo 30% a 50% em mais de 10 nós mesmo em operação normal. O banco de dados correspondente pode ser, por exemplo, algo como instâncias AWS L/XL com 50 a 100 GB de dados e uso de CPU em torno de 30%
    Se você mover toda a CPU de busca para o banco principal, agora vai precisar shardear o DB. Ainda assim, em projetos paralelos, extensões do PG para busca, joins recursivos e vetores são legais pela diversão e pela simplicidade

    • Não daria para resolver isso fazendo a busca em uma réplica somente leitura?

  • Já fiz isso na prática há algum tempo e consegui montar algo bem rápido
    https://austingwalters.com/fast-full-text-search-in-postgres...
    Atualmente o site é https://askhn.ai

  • Dá para combinar essas técnicas com pgvector para encontrar conteúdo relacionado com embeddings. Achei isso quase mágico

    • Poderia explicar um pouco mais ou indicar algum material de referência?
    • Acho interessante que as pessoas sigam por esse caminho meio gambiarra mesmo podendo usar algo como o Vespa. Em desempenho, relevância, escalabilidade e experiência de desenvolvedor, eu diria que o Vespa é várias ordens de magnitude melhor

  • Só para constar, não é "Dark" Vader, e sim Darth Vader. Eu também achava que era "Dark" quando era criança

    • Em algumas traduções, como em francês, é realmente Dark Vador, então esse "erro" acaba sendo comum
    • Essa parte no texto me incomodou tanto que não consegui me concentrar no resto. Como alguém conhece a citação do Yoda e ainda assim escreve Dark Vader?

  • Texto muito bom e claro. O SQLite também oferece, com plugin padrão, recursos avançados de indexação e stemming
    Para inglês, o SQLite também funciona bem

    • Encontrei um material de experimento com SQLite
      https://github.com/daitangio/knowledge
      Vale testar. É bem poderoso
    • Fico curioso se isso também daria para fazer com FDW. Se só os dados de busca forem replicados, não deve haver muitos writers, então pode funcionar bem para dados de escala intermediária

  • O texto é bom, mas a parte que diz que o PostgreSQL não oferece suporte a busca fuzzy está parcialmente errada. A extensão pg_trgm e índices GIN com trigramas suportam casos de uso de busca fuzzy como os exemplos deste texto
    https://www.postgresonline.com/article_pfriendly/169.html
    As consultas podem ficar muito mais rápidas, mas isso vem ao custo de maior uso de memória e mais trabalho na hora de atualizar