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étodoTempo
body LIKE '%w15000%' (varredura paralela da tabela)156 ms
to_tsvector(body) @@ query, calculado para cada linha6.174 ms
A mesma consulta com um índice GIN sobre um tsvector armazenado0,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:

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.

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:

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 listIds brutos de 4 bytesDelta + bytes variáveisProporção
um termo muito comum (500.000 documentos)2.000.000 bytes500.000 bytes25%
um termo comum (50.000 documentos)200.000 bytes50.062 bytes25%
um termo raro (500 documentos)2.000 bytes963 bytes48%

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:

ConsultaCorrespondênciasPlano e tempo
uma palavra rara69bitmap index scan, 0,245 ms
search & database (ambas comuns)85.072bitmap index scan, 125 ms
the & of (em quase toda linha)a maioria das linhaso planejador escolheu uma varredura sequencial, 79 ms
três palavras comuns com ORDER BY ts_rank ... LIMIT 10cerca de 47.000varredura 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

Sinônimos

Uma lista de sinônimos deixa uma busca por "laptop" achar "notebook computer". Parece simples e tem várias armadilhas:

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.

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

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:

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

8. Postgres ou um motor dedicado?

Busca de texto completo do PostgresMotor dedicado (Elasticsearch, OpenSearch, Solr, Typesense, Meilisearch)
Consistência com os seus dadostransacional; um só sistemacópia eventualmente consistente
Operaçãonada de novooutro cluster para executar, monitorar, atualizar e proteger
Rankingts_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álisebom conjunto de configurações embutidasecossistema de analisadores muito rico, sinônimos, suggesters
Recursossem facetas embutidas, busca aproximada fraca (o pg_trgm ajuda)facetas, destaque (highlighting), busca aproximada, did-you-mean, geo, agregações
Escalaum 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:

FatorAponta para o PostgresAponta para um motor dedicado
Tamanho do corpus e dos documentoso índice e a parte quente da tabela cabem na memóriao índice é muito maior que a RAM, ou os documentos são grandes (muitas páginas de texto)
Custo das consultasconsultas 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 consultasdezenas de buscas por segundo ao lado da carga normalcentenas ou milhares, que competiriam com a carga transacional por CPU, memória e I/O
Padrão de escritaatualizações moderadas; a coluna de busca muda raramenteum 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)
Atualidadedeve ser pesquisável no instante em que a transação confirmaum segundo ou mais de atraso é aceitável
Necessidades de relevância"contém estas palavras, mais novos primeiro" bastaranking ajustado, field boosts, sinônimos, tolerância a erros de digitação, learning to rank, híbrido com vetores
Idiomasum ou dois, cobertos pelas configurações embutidasmuitos, com decomposição ou tokenizadores CJK, ou analisadores personalizados
Equipe e operaçãoninguém para executar outro clusteralguém é dono do cluster, ou um serviço gerenciado é aceitável
Consistência e permissõesos resultados da busca precisam sempre concordar com o banco de dados e suas regras de acessoa 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

10. Coisas a mencionar em uma entrevista

Resumo rápido

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

Pratique este tema: Databases

Mais guias