O índice invertido

Objetivos

Nesta aula você vai:

• Visualizar o índice invertido como dicionário de termos para listas de documentos
• Entender por que essa estrutura evita table scan em buscas textuais
• Conectar o conceito aos índices FULLTEXT (MySQL) e GIN/tsvector (PostgreSQL)

Introdução

Um índice B-tree clássico responde bem a “chave igual a X” ou “chave entre A e B”. Texto livre quebrado em tokens não se comporta como chave única: o mesmo termo aparece em milhares de documentos, e a consulta pede união ou interseção de conjuntos. A estrutura natural para isso é o índice invertido: em vez de documento → palavras, guardamos palavra → documentos.

No OficinaHub, o termo torquímetro pode aparecer em 1.240 anúncios. Com índice invertido, a busca começa nessa lista de 1.240 identificadores — não nas 900 mil linhas do catálogo.

Conteúdo

Do documento para o dicionário

Documentos (simplificados):

Índice invertido (postings):

Consulta torquímetro digital:

1. Resolver tokens (torquimetro, digital)
2. Intersectar postings → {101}
3. Ranquear e devolver

Nenhuma varredura das linhas 102 e 104 foi necessária para decidir a candidatura.

Por que B-tree em coluna de texto não substitui

-- Índice B-tree ajuda igualdade/prefixo, não presença de token no meio
CREATE INDEX idx_produtos_nome ON produtos (nome);

SELECT * FROM produtos WHERE nome = 'Torquímetro digital de bancada';
-- ok com B-tree

SELECT * FROM produtos WHERE nome LIKE '%torquímetro%';
-- curinga à esquerda: B-tree pouco ou nada ajuda

O índice invertido indexa termos, não a string inteira como chave monolítica. Por isso casa com a tokenização da aula anterior.

Como os bancos materializam a ideia

MySQL FULLTEXT: CREATE FULLTEXT INDEX constrói estruturas internas de postings sobre as colunas escolhidas. MATCH ... AGAINST consulta esse índice.

CREATE FULLTEXT INDEX ft_produtos_nome_desc
  ON produtos (nome, descricao);

SELECT sku, nome
FROM produtos
WHERE MATCH(nome, descricao) AGAINST ('torquimetro digital' IN NATURAL LANGUAGE MODE);

PostgreSQL: você tipicamente mantém uma coluna tsvector (ou expressão) e cria um índice GIN (ou GiST) sobre ela.

ALTER TABLE produtos
  ADD COLUMN search_vector tsvector
  GENERATED ALWAYS AS (
    to_tsvector('portuguese', coalesce(nome, '') || ' ' || coalesce(descricao, ''))
  ) STORED;

CREATE INDEX idx_produtos_search_gin ON produtos USING gin (search_vector);

SELECT sku, nome
FROM produtos
WHERE search_vector @@ plainto_tsquery('portuguese', 'torquímetro digital');

Em ambos os casos, o otimizador pode escolher um caminho que parte do termo, não da heap completa.

Custo de escrita

Índices invertidos não são grátis: cada INSERT/UPDATE/DELETE precisa atualizar postings. Em catálogos com escrita intensa, meça o overhead; em buscas muito mais frequentes que escritas (caso típico de marketplace e helpdesk), o trade-off costuma ser favorável.

Problema comum e solução

Problema: criar a coluna/MATCH sem o índice correspondente e concluir que “full-text também é lento”.

Solução: verificar o plano. Sem GIN/FULLTEXT materializado, o PostgreSQL pode calcular to_tsvector em cada linha (sequential scan). Sem índice FULLTEXT no MySQL, MATCH nem sequer é o caminho correto. Sempre confirme o índice e o EXPLAIN.

Como analisar

-- PostgreSQL: deve aparecer Bitmap Index Scan no GIN
EXPLAIN (ANALYZE, BUFFERS)
SELECT sku FROM produtos
WHERE search_vector @@ to_tsquery('portuguese', 'torquimetro & digital');

-- MySQL: type deve refletir uso de fulltext
EXPLAIN
SELECT sku FROM produtos
WHERE MATCH(nome, descricao) AGAINST ('torquimetro digital');

Se ainda houver Seq Scan / ALL com custo alto, o índice não está sendo usado (expressão diferente, coluna errada, estatísticas, ou índice ausente).

Resumo

• Índice invertido: termo → lista de documentos (postings)
• A busca resolve tokens e opera em conjuntos, sem varrer a tabela inteira
• MySQL FULLTEXT e PostgreSQL GIN são materializações dessa ideia
• Escritas pagam a atualização do índice; são as leituras de busca que se beneficiam