CS Fundamentals Trainer · Guias
Busca e indexação de texto completo
O índice invertido, a análise, o ranking BM25, a compressão de listas de postings, segmentos e merges, busca em shards, como manter um índice em sincronia com o banco de dados e quando a busca de texto completo do Postgres basta.
34 min de leitura
Um usuário digita "postgres index tuning" e espera os dez melhores resultados entre milhões de páginas em poucos milissegundos. Uma consulta LIKE '%word%' não consegue isso, porque precisa ler todas as linhas. A busca funciona porque alguém fez a leitura antecipadamente e guardou o resultado em uma estrutura construída para a pergunta: o índice invertido. Este guia explica essa estrutura, como as consultas e o ranking a usam, por que os motores de busca são construídos com segmentos imutáveis e como operá-la no Postgres ou em um motor dedicado. Executei os números no Postgres 16 e em pequenos scripts Python (código no apêndice).
1. Por que um índice normal não basta
Um índice B-tree (índices de banco de dados) é ordenado pelo valor inteiro, então responde "igual a isto", "começa com isto" e "entre estes". Não consegue responder "contém a palavra index em algum lugar deste parágrafo", porque a posição de uma palavra dentro do texto não diz nada sobre onde a linha se ordena.
Gerei 200.000 documentos sintéticos de 30 a 70 palavras cada (61 MB), tirados de um vocabulário de 20.000 palavras com as frequências desiguais da linguagem natural, e busquei uma palavra rara que ocorre em 68 deles. (O corpus é artificial: não tem gramática, nem tópicos, nem frases repetidas, nem uma distribuição realista de comprimento de documentos, então os tempos mostram como as estruturas se comportam e escalam, e não são o que o seu corpus vai dar. O texto real tem distribuições de termos mais assimétricas, documentos mais longos e agrupamentos, e tudo isso muda o tamanho do índice e o custo das consultas.)
| Método | Tempo |
|---|---|
body LIKE '%w15000%' (varredura paralela da tabela) | 156 ms |
to_tsvector(body) @@ query, calculado para cada linha | 6.174 ms |
A mesma consulta com um índice GIN sobre um tsvector armazenado | 0,245 ms |
A varredura lê tudo e seu custo cresce com os dados; o índice olha a palavra e vai direto às 69 linhas que a contêm. A linha do meio é um aviso: usar funções de texto completo sem um índice é muito pior que um LIKE simples, porque o texto é analisado de novo para cada linha.
2. O índice invertido
Um índice invertido é um dicionário de cada termo para a lista de documentos que o contêm (uma posting list), em geral com as posições do termo dentro de cada documento. "Invertido" porque a direção natural é do documento para as palavras, e este vai das palavras para os documentos.
Construí-lo tem três passos: analisar o texto em termos (tokenizar, passar para minúsculas, remover stop words, talvez fazer stemming), depois coletar os postings e então ordená-los por termo. Percorra passo a passo um exemplo minúsculo, uma vez com semântica AND e outra com OR:
Interactive animation: inverted index
Com AND, a consulta quick dog pega a posting list de quick (D1 e D3), a de dog (D2 e D3) e as intersecta: uma correspondência, D3. Com OR pega a união: três correspondências. Nos dois casos, apenas as listas curtas foram lidas, nunca o texto dos documentos. As posting lists são mantidas ordenadas por id de documento, então uma intersecção é um merge de duas listas ordenadas, e skip pointers permitem pular longos trechos de ids que não correspondem. Começar pelo termo mais raro torna a intersecção mais barata.
Diagram: From documents to results
A cadeia de análise precisa coincidir
O texto é analisado na hora da indexação e a consulta na hora da busca, e os dois devem usar a mesma cadeia; caso contrário, uma consulta por "Running" procura um termo que foi indexado como "run". Passos típicos:
- Tokenização: dividir em palavras. Fácil em inglês, mais difícil em idiomas sem espaços, e cheia de casos especiais (endereços de e-mail, números de versão, hifens).
- Normalização: passar para minúsculas, remover acentos quando apropriado.
- Stop words: descartar palavras muito comuns ("the", "of"). Elas tornam as posting lists enormes e carregam pouco significado, mas removê-las torna impossíveis as buscas por frase como "to be or not to be"; muitos motores modernos as mantêm e contam com a compressão e o ranking.
- Stemming ou lematização: reduzir "indexes", "indexing" e "indexed" a uma única forma. Isso aumenta o recall (acha mais) e diminui a precisão (algumas correspondências estão erradas). É específico de cada idioma.
Escolha-os por campo e por idioma. Um campo com códigos de produto ou nomes de usuário em geral não precisa de stemming algum.
Posições e frases
Para casar com a frase "inverted index", o motor precisa saber que as duas palavras são adjacentes, então os postings guardam posições. No meu corpus de teste, as palavras inverted e index aparecem ambas nos documentos D2 e D7; a frase inverted index casa com os dois, enquanto index inverted não casa com nenhum, o que é uma verificação das posições, não só das palavras. As posições tornam o índice maior e as consultas por frase mais lentas, então os motores só as mantêm quando o campo está configurado para isso.
3. Ranking: qual resultado vem primeiro
Achar as correspondências é a parte fácil; a maioria das consultas casa com milhares de documentos, e os usuários leem os primeiros. Uma pontuação de relevância os ordena.
- Frequência do termo (tf): um documento que menciona o termo com mais frequência provavelmente trata mais dele.
- Frequência inversa de documentos (idf): um termo que ocorre em poucos documentos é mais informativo que um que ocorre na maioria. Uma correspondência em "postgres" vale mais que uma em "the".
- Normalização por comprimento: um termo que aparece três vezes em um documento de 20 palavras diz mais que três vezes em um de 20.000.
O TF-IDF multiplica os dois primeiros. Seu defeito é que o tf cresce sem limite: uma página que repete uma palavra cinquenta vezes vence uma boa página. O BM25, o padrão no Lucene, no Elasticsearch, no OpenSearch e em outros, corrige isso com uma frequência de termo saturante (a décima ocorrência acrescenta muito menos que a segunda) e com a normalização por comprimento controlada por dois parâmetros, em geral k1 de cerca de 1,2 e b de 0,75.
Testei os dois em oito documentos minúsculos com a consulta "search index". O documento D6 é a palavra search repetida dez vezes. Isto é uma demonstração de um mecanismo, construída para mostrar o que a saturação faz, com o documento de spam plantado: não diz nada sobre qual fórmula devolve resultados mais relevantes em consultas reais, e oito documentos inventados não podem dizê-lo. Com o TF-IDF simples ele pontua 6,93 e o documento seguinte 1,19, uma goleada para o spam. Com o BM25 ele pontua 1,39 contra 1,27: ainda vem primeiro aqui, já que é o único documento que casa com search de forma tão intensa, mas a distância encolheu de 5,8 vezes para 1,1 vez, então um único sinal adicional (como uma correspondência no título ou um reforço por atualidade) basta para reordená-los. A saturação reduz o keyword stuffing; não o elimina.
O BM25 é uma boa linha de base e, com um pouco de ajuste, difícil de superar na busca por palavras-chave. Os sistemas reais acrescentam mais sinais por cima: correspondências no título valem mais que no corpo (field boosts), dados de popularidade ou de cliques, atualidade e, mais recentemente, o ranking semântico com embeddings vetoriais, em geral combinado com o BM25 ("busca híbrida") porque os embeddings são bons em significado e ruins em identificadores exatos. Avalie qualquer mudança com um conjunto de consultas de exemplo e julgamentos (precisão e recall em k, nDCG), não olhando cinco consultas. A próxima seção diz o que isso significa na prática.
Evidência de relevância: o que medir e o que as demonstrações não mostram
Os dois números de ranking acima vêm de um exemplo construído. A evidência de que um ranking é melhor vem de outro tipo de teste:
- Uma coleção de teste julgada. Pegue consultas reais (amostradas dos seus logs de consultas, cobrindo as frequentes, as intermediárias e a cauda longa, em cada idioma que você suporta) e, para cada uma, peça a pessoas que julguem a relevância dos primeiros resultados, em uma escala pequena (por exemplo de 0 a 3) com diretrizes escritas. Vários juízes por consulta, e uma medida de quanto eles concordam, dizem quão confiáveis são os rótulos. As coleções públicas (TREC, MS MARCO, BEIR) são úteis para comparar métodos em geral, mas não são os seus documentos nem os seus usuários.
- Métricas com um propósito. Precisão em k (quantos dos primeiros k são relevantes), recall (quantos dos relevantes foram achados), mean reciprocal rank (a que profundidade está o primeiro bom resultado; certo para tarefas de "achar a página") e nDCG (que recompensa pôr os resultados mais relevantes primeiro e trata julgamentos graduados). Escolha a métrica que corresponde a como as pessoas usam a busca e relate-a por grupo de consultas, porque uma média sobre todas as consultas esconde uma regressão em um segmento.
- Consultas suficientes e uma verificação de significância. Uma diferença de alguns pontos em 20 consultas é ruído. Algumas centenas de consultas julgadas, uma comparação pareada do ranking antigo e do novo por consulta e um intervalo de confiança são o mínimo para uma decisão.
- Offline, depois online. Os julgamentos offline são baratos e repetíveis e pegam regressões (mantenha um conjunto "dourado" que toda mudança deve passar). Os testes online (testes A/B em cliques, reformulações, abandono, tempo até o primeiro clique útil, conversão) mostram comportamento real, mas têm viés de posição (as pessoas clicam no primeiro resultado), então interprete os cliques com cuidado.
- Olhe as falhas. Leia as consultas com zero resultados, as que os usuários reformulam logo em seguida e aquelas em que o primeiro resultado foi pulado. Elas mostram problemas (sinônimos ausentes, idioma errado, erros de stemming) que nenhuma média revela.
O mesmo vale para os números de desempenho deste guia: meça em uma amostra dos seus documentos e consultas, com a sua concorrência e a sua taxa de atualização.
4. Tornando o índice pequeno e rápido
As posting lists dominam o tamanho do índice e, felizmente, comprimem bem. Como os ids de documento são ordenados, guarde as diferenças entre eles (codificação delta) e escreva cada diferença com o menor número de bytes de que precisa (codificação de bytes variáveis). Em um teste com 1.000.000 de documentos:
| Posting list | Ids brutos de 4 bytes | Delta + bytes variáveis | Proporção |
|---|---|---|---|
| um termo muito comum (500.000 documentos) | 2.000.000 bytes | 500.000 bytes | 25% |
| um termo comum (50.000 documentos) | 200.000 bytes | 50.062 bytes | 25% |
| um termo raro (500 documentos) | 2.000 bytes | 963 bytes | 48% |
As listas densas têm diferenças pequenas (um byte cada); as listas esparsas têm diferenças maiores e comprimem menos. Os motores de produção usam formatos mais rápidos empacotados em bits (o Lucene usa blocos de frame-of-reference), mas a ideia é a mesma. A compressão também é uma otimização de velocidade: menos dados para ler do disco e da memória e, portanto, menos pressão no cache (veja a hierarquia de memória).
No Postgres, o índice GIN sobre meus 200.000 documentos ocupou 29 MB, contra 61 MB do texto original. É uma boa proporção, mas note os custos: preencher a coluna tsvector com um UPDATE reescreveu todas as linhas, e o heap da tabela media 223 MB depois (as versões antigas das linhas ficam até o espaço ser reutilizado ou a tabela ser reescrita), e um índice GIN torna as escritas mais lentas, que é o preço de todo índice.
Quando o índice não ajuda
O índice é rápido para termos seletivos. Para termos que ocorrem em uma grande parte dos documentos, o trabalho é proporcional ao número de correspondências, não ao tamanho da resposta que você devolve. Nos mesmos 200.000 documentos:
| Consulta | Correspondências | Plano e tempo |
|---|---|---|
| uma palavra rara | 69 | bitmap index scan, 0,245 ms |
search & database (ambas comuns) | 85.072 | bitmap index scan, 125 ms |
the & of (em quase toda linha) | a maioria das linhas | o planejador escolheu uma varredura sequencial, 79 ms |
três palavras comuns com ORDER BY ts_rank ... LIMIT 10 | cerca de 47.000 | varredura paralela, 89 ms |
Duas lições. Primeiro, um termo frequente é barato nas listas comprimidas de um motor dedicado, mas ainda custa tempo proporcional às correspondências, e é por isso que as stop words e as consultas AND que começam pelo termo mais raro importam. Segundo, o ranking custa trabalho para cada correspondência, não para as dez que você devolve: o banco de dados precisa pontuar cerca de 47.000 documentos para achar os 10 melhores. Os motores evitam parte disso com técnicas de terminação antecipada (como o block-max WAND), e as aplicações a evitam estreitando antes os candidatos com filtros, ou limitando a profundidade em que um usuário pode paginar.
5. Erros de digitação e prefixos
- A busca por prefixo ("auto" casando com "automatic") funciona naturalmente em um dicionário de termos ordenado: todos os termos com o prefixo formam um único intervalo. A busca enquanto se digita é construída sobre intervalos de prefixo ou sobre a indexação de n-gramas de borda.
- A correspondência aproximada (fuzzy) acha termos dentro de uma distância de edição. Comparar a consulta com cada termo seria lento, então os motores usam autômatos sobre o dicionário ou n-gramas de caracteres: dividem cada termo em grupos sobrepostos de três caracteres e procuram termos que compartilham muitos. No meu teste, "postgress" casou com postgres (similaridade 0,73), "elastisearch" casou com elasticsearch (0,69) e a grafia britânica/americana "normalization" casou com normalisation (0,65), todos muito acima do melhor candidato seguinte (0,0). O Postgres oferece isso na extensão
pg_trgm. - Sinônimos e expansão de consultas são decididos por domínio ("NYC" e "New York") e exigem cuidado; veja a próxima subseção.
Sinônimos
Uma lista de sinônimos deixa uma busca por "laptop" achar "notebook computer". Parece simples e tem várias armadilhas:
- Onde aplicá-los. Aplicados na hora da consulta (a consulta é expandida para "laptop OR notebook"), uma mudança vale na hora sem reconstrução e o índice continua pequeno. O custo é que os sinônimos de várias palavras são difíceis para o parser da consulta (a frase "new york" precisa casar como uma unidade), a pontuação pode ficar distorcida (quanto mais sinônimos uma consulta tem, mais correspondências) e a expansão acontece em toda consulta. Aplicados na hora da indexação (cada documento também é indexado sob as alternativas), as consultas são simples e rápidas, mas toda mudança na lista exige reindexar os documentos afetados, e o índice é maior. Muitas equipes usam sinônimos na hora da consulta para listas que mudam com frequência e na hora da indexação para as estáveis; qualquer que seja a escolha, a cadeia de análise nas duas pontas tem de ser consistente com ela.
- Direção. "Postgres" pode representar "PostgreSQL", mas uma busca por "database" não deve ficar limitada ao Postgres. Use regras unidirecionais (um termo específico se expande para o geral, ou o contrário, de propósito) e regras de equivalência só onde os termos são realmente intercambiáveis.
- Interação com stemming, stop words e maiúsculas/minúsculas. Os sinônimos são casados em termos analisados, então uma regra escrita para "indexes" talvez nunca dispare depois que o stemming a reduz a "index", e uma regra para uma stop word talvez nunca a veja.
- Contexto. "Apple" e "java" significam coisas diferentes em domínios diferentes, e um sinônimo que ajuda uma consulta prejudica outra. Listas curadas e específicas do domínio, revisadas contra o conjunto de avaliação, vencem um tesauro genérico; a expansão aprendida ou baseada em embeddings precisa das mesmas verificações.
- Manutenção. Mantenha a lista em controle de versão, com um motivo para cada regra, e meça toda mudança nas consultas julgadas. As consultas que não devolvem nada são a melhor fonte de regras novas.
Idiomas e conteúdo multilíngue
Uma cadeia de análise é por idioma. O stemming, as stop words, a tokenização e o tratamento de acentos dependem dela, e uma cadeia para o inglês aplicada ao alemão, ao português ou ao japonês prejudica o recall e a precisão.
- Saiba o idioma de cada documento e de cada consulta. Guarde-o com o documento quando for conhecido (um campo
language), detecte-o quando não for (textos curtos e mistos são onde a detecção falha) e decida o que fazer com as consultas cujo idioma você não consegue dizer (buscar em várias cadeias, ou usar o idioma da interface do usuário). - Padrões de índice. Um campo por idioma (
title_en,title_pt,title_de, cada um com o seu analisador) dá a melhor análise e é simples de consultar quando você sabe o idioma. Um multi-field indexa o mesmo texto sob vários analisadores (por exemplo um com stemming e um exato). Um índice separado por idioma é mais limpo para corpora grandes e para ajuste por idioma. No Postgres, umtsvectoré construído com uma configuração de busca de texto (english,portuguese,germane assim por diante), então guarde a configuração usada em cada linha e use a mesma na consulta; construir todos os vetores com uma única configuração fixa é um erro comum. - Os idiomas diferem no que é uma "palavra". Os compostos alemães (Datenbankindex) precisam de decomposição para casar com "Index"; o chinês, o japonês e o tailandês não têm espaços e precisam de um tokenizador baseado em dicionário ou em n-gramas; o árabe e o hebraico precisam de tratamento morfológico; o turco tem o seu i com ponto e sem ponto. Remover acentos ajuda em um idioma (buscar "cafe" para "café") e prejudica em outro em que o acento separa palavras (em português pais e país, em espanhol año e ano). A normalização Unicode (NFC/NFKC) e um case folding consistente evitam divergências invisíveis.
- O conteúdo de idiomas misturados (uma página em português com termos técnicos em inglês, identificadores de código) é normal. Indexe código e identificadores com uma cadeia que não faz stemming e deixe uma consulta casar com os dois campos.
- A busca entre idiomas (uma consulta em um idioma achando documentos em outro) precisa de tradução ou de embeddings multilíngues, e é um recurso diferente dos acima.
- Avalie cada idioma separadamente. Uma média sobre todas as consultas pode ser boa enquanto um idioma é ruim; mantenha consultas julgadas por idioma.
6. Motores de busca: segmentos, merges e quase tempo real
Um motor dedicado como o Lucene (a biblioteca dentro do Elasticsearch, do OpenSearch e do Solr) não atualiza um índice grande no mesmo lugar. Ele escreve o índice em segmentos imutáveis:
Diagram: Writes create segments; merges compact them
- Um segmento nunca muda depois de escrito. Isso o torna simples de guardar em cache, de ler concorrentemente sem locks e de comprimir bem.
- Um refresh torna os documentos recentes pesquisáveis (cerca de um segundo por padrão no Elasticsearch, daí "quase tempo real" e não tempo real). Um commit os torna duráveis; o log de transações cobre a diferença.
- Um delete só marca o documento; um update é um delete mais um documento novo. O espaço volta quando os segmentos são mesclados em segundo plano.
- Uma consulta busca em todos os segmentos e mescla os resultados, então muitos segmentos pequenos a deixam lenta; a política de merge mantém o número deles sob controle, ao custo de I/O em segundo plano.
Esta é a mesma forma do armazenamento estruturado em log usado por muitos bancos de dados, e tem a mesma troca: escritas rápidas e leituras rápidas de dados antigos, trabalho em segundo plano para manter tudo arrumado.
Escalando horizontalmente
Um índice é dividido em shards, cada um um índice completo do seu próprio subconjunto de documentos (pelo hash do id do documento, veja replicação, particionamento e sharding e consistent hashing), e cada shard tem réplicas para disponibilidade e para distribuir a carga de leitura. Uma consulta vai a uma cópia de cada shard (scatter), cada uma devolve os seus melhores resultados locais, e um nó coordenador os mescla (gather). Duas consequências:
- A latência é definida pelo shard mais lento, então a latência de cauda importa (veja observabilidade sobre percentis).
- As pontuações são locais: o idf é calculado por shard, a menos que se diga ao motor para coletar estatísticas globais, então shards muito pequenos ou desbalanceados podem produzir rankings ligeiramente diferentes. A paginação profunda (página 1.000) obriga cada shard a produzir 1.000 vezes o tamanho da página; prefira cursores "search after" a offsets, como em paginação para APIs.
7. Mantendo o índice de busca em sincronia com o banco de dados
O motor de busca quase nunca é o sistema de registro. A fonte da verdade é o seu banco de dados, e o índice é uma cópia derivada construída para consultas. Manter os dois alinhados é o verdadeiro problema de engenharia.
Diagram: A search index is a derived view of the primary database
- As escritas duplas (a aplicação escreve no banco de dados e depois no índice) falham no meio: o commit do banco de dados tem sucesso e a chamada ao índice falha, ou o contrário. Use uma tabela outbox ou captura de mudanças de dados (CDC) para que o evento seja confirmado na mesma transação dos dados; o padrão é discutido em filas de mensagens e garantias de entrega.
- Torne o indexador idempotente, indexe os documentos pelo seu id primário e uma versão, para que a reentrega e a reordenação de eventos não possam trazer de volta uma versão antiga.
- Espere atraso e projete para ele: um registro salvo há um segundo pode ainda não ser pesquisável (veja consistência). Para "ler a própria escrita", mostre o item novo diretamente do banco de dados. O atraso tem várias partes que se somam: o tempo até o evento de mudança ser publicado (o intervalo do poller da outbox), a espera na fila, o batching do indexador, o intervalo de refresh do motor (cerca de um segundo por padrão no Elasticsearch, e muitas vezes elevado para 30 segundos ou mais durante cargas em massa para ganhar vazão) e o atraso das réplicas se as buscas vão para réplicas. Meça-o de ponta a ponta: escreva um documento de heartbeat ou carimbe cada documento com o seu horário de commit, e acompanhe quanto tempo até que possa ser achado, nos percentis 50, 95 e 99. Depois decida o que o produto promete e alerte quando o atraso o exceder.
- As remoções importam mais que as adições. Se um documento é apagado, despublicado, ou um usuário perde o acesso, o índice de busca precisa parar de devolvê-lo. Uma adição tardia é um incômodo; uma remoção tardia pode vazar dados. Trate as exclusões e as mudanças de permissão como de alta prioridade (um caminho rápido separado) e reconfira o acesso no banco de dados ao carregar os registros completos, para que uma entrada obsoleta do índice não possa expor nada.
- Espere falhas de indexação e trate cada tipo de propósito. Uma requisição em massa pode ter sucesso parcial (o motor devolve um erro para itens individuais, mesmo quando o status HTTP é 200), então confira todos os itens. As falhas transitórias (um timeout, sobrecarga, um nó reiniciando) devem ser repetidas com backoff e jitter (veja padrões de resiliência); as permanentes (um conflito de mapeamento, um documento grande demais, um campo do tipo errado) falharão todas as vezes, então, depois de algumas tentativas, mova o evento para uma dead-letter queue com o motivo, alerte sobre isso e continue, para que um documento ruim não bloqueie o fluxo atrás dele. Use a versão do registro como versão externa onde o motor o suportar, para que um evento mais antigo repetido ou reordenado não possa sobrescrever um mais novo. Aplique backpressure quando o motor estiver saturado (lotes menores, consumo mais lento) e não um laço de repetição sem limite.
- Reconcilie. Mesmo com tudo isso, o índice e o banco de dados divergem (um evento perdido, um bug, uma restauração de um dos lados). Execute uma reconciliação periódica: compare contagens, ids e uma soma de verificação ou versão por registro entre o banco de dados e o índice, relate a diferença como uma métrica e repare-a reindexando os documentos ausentes ou obsoletos. A capacidade de reconstruir o índice inteiro (próximo ponto) é a última linha de defesa.
- Saiba reconstruir. Os mapeamentos e os analisadores mudam; planeje reindexar em um índice novo e trocar um alias para ele, mantendo o antigo até que o novo seja verificado. É por isso que o banco de dados, e não o índice, deve guardar a verdade.
- A autorização também é um problema de busca: filtre os resultados pelo que o usuário pode ver, na consulta (como um filtro em um campo de tenant ou de permissão), não depois, ou as contagens, as facetas e a paginação vazarão e estarão erradas. Veja sistemas multi-tenant.
8. Postgres ou um motor dedicado?
| Busca de texto completo do Postgres | Motor dedicado (Elasticsearch, OpenSearch, Solr, Typesense, Meilisearch) | |
|---|---|---|
| Consistência com os seus dados | transacional; um só sistema | cópia eventualmente consistente |
| Operação | nada de novo | outro cluster para executar, monitorar, atualizar e proteger |
| Ranking | ts_rank (um esquema básico), sem BM25 no núcleo (extensões acrescentam BM25 e outros esquemas) | BM25 e muitos sinais ajustáveis, híbrido com vetores |
| Idioma e análise | bom conjunto de configurações embutidas | ecossistema de analisadores muito rico, sinônimos, suggesters |
| Recursos | sem facetas embutidas, busca aproximada fraca (o pg_trgm ajuda) | facetas, destaque (highlighting), busca aproximada, did-you-mean, geo, agregações |
| Escala | um nó, ou shards manuais; "milhões de documentos" é um número aproximado que depende da carga de trabalho (veja abaixo) | construído para ser distribuído em muitos nós |
Um padrão sensato: comece com a busca de texto completo do próprio banco de dados. Ela é transacional, não há nada a sincronizar e, para um corpus modesto com necessidades simples de relevância, basta. Passe para um motor dedicado quando precisar de ajuste de relevância, facetas, tolerância a erros de digitação, busca enquanto se digita, corpora muito grandes ou tráfego de busca pesado que você não quer pôr no banco de dados primário.
"Modesto" e "pesado" dependem da carga de trabalho, então decida com estas perguntas, e com um teste nos seus próprios dados:
| Fator | Aponta para o Postgres | Aponta para um motor dedicado |
|---|---|---|
| Tamanho do corpus e dos documentos | o índice e a parte quente da tabela cabem na memória | o índice é muito maior que a RAM, ou os documentos são grandes (muitas páginas de texto) |
| Custo das consultas | consultas seletivas, filtros simples (a palavra rara levou 0,25 ms) | muitas correspondências que precisam ser todas ranqueadas (cerca de 47.000 correspondências levaram 89 ms no meu teste, por consulta), várias facetas, agregações profundas |
| Concorrência de consultas | dezenas de buscas por segundo ao lado da carga normal | centenas ou milhares, que competiriam com a carga transacional por CPU, memória e I/O |
| Padrão de escrita | atualizações moderadas; a coluna de busca muda raramente | um fluxo constante de atualizações (os índices GIN agrupam suas inserções em uma lista pendente e podem ficar para trás; toda atualização reescreve a linha e suas entradas de índice) |
| Atualidade | deve ser pesquisável no instante em que a transação confirma | um segundo ou mais de atraso é aceitável |
| Necessidades de relevância | "contém estas palavras, mais novos primeiro" basta | ranking ajustado, field boosts, sinônimos, tolerância a erros de digitação, learning to rank, híbrido com vetores |
| Idiomas | um ou dois, cobertos pelas configurações embutidas | muitos, com decomposição ou tokenizadores CJK, ou analisadores personalizados |
| Equipe e operação | ninguém para executar outro cluster | alguém é dono do cluster, ou um serviço gerenciado é aceitável |
| Consistência e permissões | os resultados da busca precisam sempre concordar com o banco de dados e suas regras de acesso | a cópia pode atrasar, e você pode impor permissões na consulta |
As extensões e variantes borram a fronteira (BM25 e busca vetorial dentro do Postgres, recursos de busca em outros bancos de dados), então confira o que a sua versão oferece antes de decidir. Um plano razoável é começar no Postgres, medir os percentis de latência das consultas, o custo de indexação e a qualidade dos resultados nos seus próprios dados, definir o limite a partir do qual você mudaria e manter a busca atrás de uma interface, de modo que a troca seja um projeto e não uma reescrita.
9. Erros comuns
- Usar
LIKE '%term%'para busca em uma tabela que vai crescer. - Chamar
to_tsvectordentro da cláusulaWHEREsem um índice de expressão correspondente, ou esquecer de armazenar o vetor e indexá-lo. - Analisar documentos e consultas com cadeias diferentes.
- Stemming ou remoção de stop words agressivos que quebram nomes, códigos e consultas por frase.
- Avaliar a relevância a olho em um punhado de consultas, ou tratar uma demonstração sintética como prova de que um ranking é melhor.
- Um analisador para todos os idiomas, remoção de acentos que mistura palavras diferentes e listas de sinônimos que ninguém testa.
- Ignorar o atraso do índice, as falhas parciais em massa e as exclusões tardias, ou não ter como reconciliar o índice com o banco de dados.
- Tratar o índice de busca como fonte da verdade, ou fazer escritas duplas sem uma outbox.
- Deixar os usuários paginarem fundo com offsets.
- Filtrar por permissões depois da busca.
- Pôr a carga de busca no banco de dados primário sem limites e o oposto: construir um cluster para 50.000 documentos.
10. Coisas a mencionar em uma entrevista
- Por que uma B-tree não consegue fazer "contém uma palavra", e o índice invertido como termo para posting list ordenada com posições.
- O AND como uma intersecção de listas ordenadas (a mais rara primeiro), o OR como uma união, uma frase como uma verificação de posições.
- tf, idf e normalização por comprimento; a saturação do BM25; a ideia de que o ranking é um pipeline com muitos sinais, avaliado com julgamentos.
- Compressão do índice com deltas e codificação de bytes variáveis; segmentos imutáveis com merges em segundo plano; refresh em quase tempo real.
- Sharding para escalar, scatter-gather e o custo da paginação profunda.
- O índice como uma visão derivada: o padrão outbox, a indexação idempotente, a reindexação com um alias e as permissões na consulta.
- Começar com a busca de texto completo do Postgres e passar para um motor dedicado por razões específicas e nomeadas que dependem da carga de trabalho (corpus e custo das consultas, concorrência, taxa de atualização, atualidade, necessidades de relevância e de idioma, operação).
- Como saber que um ranking é melhor: consultas julgadas, nDCG e outras métricas, consultas suficientes, testes offline e online e avaliação por idioma; e por que uma demonstração em oito documentos não é evidência.
- Sinônimos (hora da consulta contra hora da indexação, direção, interação com o stemming), análise multilíngue (cadeias por idioma, compostos, CJK, acentos) e o atraso e os modos de falha da indexação (falhas parciais em massa, dead letters, exclusões, reconciliação).
Resumo rápido
- O índice invertido mapeia termos para posting lists ordenadas com posições; uma consulta combina listas e nunca lê o texto. No teste, uma busca GIN levou 0,245 ms contra 156 ms do
LIKEe 6.174 ms de umto_tsvectorsem índice. - A cadeia de análise (tokenizar, normalizar, stop words, stemming) precisa ser a mesma na indexação e na consulta, e é específica de cada idioma.
- A relevância é mostrada por consultas julgadas e métricas nos seus próprios dados, não por demonstrações; os tempos e os exemplos de ranking deste guia usam dados sintéticos para mostrar mecanismos.
- O BM25 melhora o TF-IDF com saturação e normalização por comprimento; o ranking custa trabalho para cada correspondência, não para cada resultado devolvido.
- As posting lists encolhem para cerca de um quarto com codificação delta e de bytes variáveis.
- Os motores escrevem segmentos imutáveis e os mesclam em segundo plano; escalam por sharding com scatter-gather.
- O índice de busca é uma cópia derivada: alimente-o por uma outbox, torne a indexação idempotente, espere atraso e falhas de indexação (trate os erros parciais em massa com repetições e uma dead-letter queue, propague as exclusões rapidamente), reconcilie-o com o banco de dados e saiba reconstruí-lo.
Apêndice: o código dos experimentos
Os experimentos aqui são demonstrações com dados sintéticos (um vocabulário gerado com uma distribuição assimétrica, oito documentos inventados para a comparação de ranking). Mostram como as estruturas se comportam e como os custos escalam; não são benchmarks do Postgres nem de nenhum motor de busca, e não são evidência sobre relevância em texto real. Os tempos vêm de uma pequena máquina virtual e serão diferentes na sua.
O primeiro script escreve 200.000 documentos sintéticos (palavras tiradas de um vocabulário de 20.000 palavras com uma distribuição assimétrica, de modo que poucas palavras são muito comuns e a maioria é rara); não é texto real, mas tem a forma que importa para as posting lists. O script SQL os carrega no Postgres 16, executa as consultas e imprime os planos com EXPLAIN (ANALYZE). Os tempos vêm de uma pequena máquina virtual e variam de uma execução para outra; as contagens de linhas e as formas dos planos são a parte estável. O terceiro script é um mini motor de busca autônomo em Python: análise, um índice invertido com posições, pontuação TF-IDF e BM25, correspondência de frases, compressão de posting lists e similaridade por trigramas.
Gerando o corpus de teste (documentos sintéticos)
import random, bisect
rnd = random.Random(11)
V = 20000
words = [f"w{i}" for i in range(V)]
# readable words for the demo queries
words[0:6] = ["the", "of", "index", "search", "database", "postgres"]
w = [1/(i+1) for i in range(V)]; tot = sum(w); cum = []; a = 0
for x in w: a += x/tot; cum.append(a)
pick = lambda: words[bisect.bisect_left(cum, rnd.random())]
with open("docs.tsv", "w") as f:
for i in range(200000):
n = rnd.randint(30, 70)
f.write(f"{i}\t{' '.join(pick() for _ in range(n))}\n")
Busca de texto completo do Postgres com e sem um índice GIN
\timing off
\set QUIET on
drop table if exists docs; create table docs(id int primary key, body text);
\copy docs from 'docs.tsv'
select pg_size_pretty(pg_total_relation_size('docs')) as table_size;
-- word frequencies of the demo terms
select count(*) filter (where body like '% search %') as search_docs,
count(*) filter (where body like '% w15000 %') as rare_docs from docs;
\timing on
explain (analyze, costs off, timing off) select count(*) from docs where body like '%w15000%';
explain (analyze, costs off, timing off) select count(*) from docs where to_tsvector('simple', body) @@ to_tsquery('simple','w15000');
\timing off
alter table docs add column tsv tsvector;
update docs set tsv = to_tsvector('simple', body);
create index docs_gin on docs using gin(tsv);
vacuum analyze docs;
select pg_size_pretty(pg_relation_size('docs_gin')) as gin_size, pg_size_pretty(pg_relation_size('docs')) as heap_size;
\timing on
explain (analyze, costs off, timing off) select count(*) from docs where tsv @@ to_tsquery('simple','w15000');
explain (analyze, costs off, timing off) select count(*) from docs where tsv @@ to_tsquery('simple','search & database');
explain (analyze, costs off, timing off) select count(*) from docs where tsv @@ to_tsquery('simple','the & of');
explain (analyze, costs off, timing off) select id from docs where tsv @@ to_tsquery('simple','search & database & postgres') order by ts_rank(tsv, to_tsquery('simple','search & database & postgres')) desc limit 10;
BM25, frases, compressão de posting lists e trigramas
import math, re
from collections import defaultdict, Counter
DOCS = {
"D1": "postgres full text search uses a gin index over tsvector columns",
"D2": "an inverted index maps each term to the list of documents that contain the term",
"D3": "search engines rank results with bm25 which refines tf idf with length normalisation",
"D4": "the quick brown fox jumps over the lazy dog",
"D5": "a database index speeds up queries but slows down writes because the index must be updated",
"D6": "search search search search search search search search search search",
"D7": "elasticsearch and lucene store an inverted index in immutable segments that are merged in the background",
"D8": "caching and indexing are different ideas but search systems use both a cache and an index",
}
def tokens(s): return re.findall(r"[a-z0-9]+", s.lower())
STOP = {"a","an","the","of","and","to","in","is","are","that","with","over","each","but","because","must","be","up","down","both","use","uses","which","ideas"}
def build(docs, stop=STOP):
index = defaultdict(dict) # term -> {doc: [positions]}
length = {}
for d, text in docs.items():
toks = tokens(text); length[d] = len(toks)
for pos, t in enumerate(toks):
if t not in stop: index[t].setdefault(d, []).append(pos)
return index, length
index, length = build(DOCS)
N = len(DOCS); avg = sum(length.values()) / N
def idf(t): n = len(index.get(t, {})); return math.log(1 + (N - n + 0.5) / (n + 0.5)) # BM25 idf (Lucene variant, never negative)
def tfidf(q):
s = Counter()
for t in tokens(q):
for d, pos in index.get(t, {}).items(): s[d] += len(pos) * idf(t)
return s
def bm25(q, k1=1.2, b=0.75):
s = Counter()
for t in tokens(q):
for d, pos in index.get(t, {}).items():
tf = len(pos); s[d] += idf(t) * tf * (k1 + 1) / (tf + k1 * (1 - b + b * length[d] / avg))
return s
q = "search index"
print("query:", q)
for name, f in (("tf-idf", tfidf), ("bm25", bm25)):
print(f" {name:6}", [(d, round(v, 2)) for d, v in f(q).most_common(4)])
# phrase queries need positions
def phrase(words):
docs = set(index[words[0]]) if words[0] in index else set()
for w in words[1:]: docs &= set(index.get(w, {}))
return sorted(d for d in docs if any(all(p + i in set(index[w][d]) for i, w in enumerate(words)) for p in index[words[0]][d]))
print("both words 'inverted' and 'index':", sorted(set(index["inverted"]) & set(index["index"])))
print("phrase 'inverted index':", phrase(["inverted", "index"]), " phrase 'index inverted':", phrase(["index", "inverted"]))
# ---- posting list compression: delta + variable-byte
import random, bisect
def varint(n):
out = bytearray()
while True:
b = n & 0x7F; n >>= 7
if n: out.append(b | 0x80)
else: out.append(b); return bytes(out)
def compress(ids):
prev, out = 0, bytearray()
for i in ids: out += varint(i - prev); prev = i
return bytes(out)
rnd = random.Random(4); N_DOCS = 1_000_000
for name, n in (("very common term", 500_000), ("common", 50_000), ("rare", 500)):
ids = sorted(rnd.sample(range(N_DOCS), n))
print(f"posting list of {n:>7} docs out of {N_DOCS}: raw 4-byte ints {4*n:>8} bytes, delta+varint {len(compress(ids)):>7} bytes ({len(compress(ids))/(4*n)*100:.0f}%)")
# ---- fuzzy matching with character trigrams
def trigrams(w): w = f" {w} "; return {w[i:i+3] for i in range(len(w) - 2)}
vocab = ["postgres", "elasticsearch", "lucene", "inverted", "normalisation", "database", "indexing", "segments"]
def similar(q):
a = trigrams(q); return sorted(((len(a & trigrams(v)) / len(a | trigrams(v)), v) for v in vocab), reverse=True)[:2]
for typo in ("postgress", "elastisearch", "normalization"): print(f" '{typo}' ->", [(v, round(s, 2)) for s, v in similar(typo)])
Fontes
- Christopher Manning, Prabhakar Raghavan e Hinrich Schütze, Introduction to Information Retrieval (Cambridge University Press), os capítulos sobre o índice invertido, a compressão de índices, a pontuação e a avaliação.
- Stephen Robertson e Hugo Zaragoza, The Probabilistic Relevance Framework: BM25 and Beyond (Foundations and Trends in Information Retrieval, 2009).
- Documentação do PostgreSQL, Full Text Search, GIN indexes e pg_trgm.
- Documentação do Apache Lucene, scoring and the BM25 similarity, e o guia do Elasticsearch sobre busca em quase tempo real, segmentos e merges.
- Ellen Voorhees e Donna Harman (orgs.), TREC: Experiment and Evaluation in Information Retrieval (MIT Press, 2005), e Nandan Thakur et al., BEIR: A Heterogeneous Benchmark for Zero-shot Evaluation of Information Retrieval Models (2021), sobre coleções de teste e avaliação; Kalervo Järvelin e Jaana Kekäläinen, Cumulated gain-based evaluation of IR techniques (ACM TOIS, 2002), para o nDCG.
- Documentação do Elasticsearch sobre synonym token filters, language analyzers, o refresh interval e a bulk API (erros por item); documentação do PostgreSQL sobre text search configurations e GIN fast update.
- Daniel Lemire e outros sobre compressão de inteiros baseada em SIMD para posting lists (por exemplo Decoding billions of integers per second through vectorization, 2015).
Pratique este tema: Databases