Construindo uma busca por filtros: filtros como conjuntos

Na primeira parte, a consulta SQL funcionava. O problema não era sua correção, mas o trabalho que crescia junto com o catálogo, a variedade de filtros e as contagens de facetas.

O próximo passo do candidato é mudar a unidade do problema. Em vez de perguntar “como consultar uma tabela mais depressa?”, ele pergunta “como representar o conjunto de itens que satisfaz cada predicado?”.

O índice troca valores repetidos por conjuntos de identidades internas.

Uma identidade externa e outra interna

O identificador público de um anúncio não precisa ser a posição usada pelo índice. IDs públicos podem ser grandes, esparsos e distribuídos sem qualquer relação com a memória de uma máquina.

Para operar sobre bits, cada partição atribui um identificador interno denso:

item público 8f2…  → doc 0
item público a17…  → doc 1
item público 44c…  → doc 2

Essa tradução é parte do contrato, não um detalhe. Todos os conjuntos de uma geração precisam concordar que a posição i representa o mesmo item. Se um índice interpretar i como um item e outro como outro, uma operação lógica produzirá uma resposta perfeitamente rápida e silenciosamente errada.

Podemos manter um mapa public_id → internal_id e outro caminho para recuperar os dados de exibição. Por enquanto, os IDs internos não são reutilizados. Espaço perdido será um problema da etapa de compactação.

Strings repetidas também não precisam ocupar os postings. Dicionários versionados traduzem nomes de campos e valores para inteiros compactos.[1]

marca      → field_id 10
cor        → field_id 11
smartphone → value_id 19

Uma chave do índice passa a ser (field_id, value_id). O dicionário pertence à mesma geração dos conjuntos; combinar um bitmap com o dicionário errado é outra forma de produzir uma resposta rápida e incorreta.

As duas direções do índice

O caminho invertido responde, seguindo a organização clássica de dicionário e posting lists:[1]

(marca, A) → {12, 42, 91, ...}

Mas a consulta também precisa responder “qual é o preço atual do documento 42?” ou recuperar os poucos campos usados para montar o resultado. Por isso, manteria um índice direto:

document_id → atributos atuais e projeção de exibição

As duas direções permitem alternar entre gerar candidatos e verificar os que já restaram.

Os dados grandes ou transacionais não precisam estar inteiros no nó de busca. Depois de descobrir o top k, a aplicação pode buscar detalhes apenas para os itens exibidos. O índice deve carregar a projeção mínima necessária para filtrar, ordenar e apresentar a primeira resposta.

Um conjunto por valor

Considere seis itens:

id  marca  cor
0   A      azul
1   B      verde
2   A      verde
3   A      azul
4   C      azul
5   B      azul

O valor marca=A vira o conjunto {0, 2, 3}. Como bitmap:

marca=A    1 0 1 1 0 0
cor=azul   1 0 0 1 1 1

Uma consulta com marca=A E cor=azul é a interseção:

             1 0 1 1 0 0
AND          1 0 0 1 1 1
             -----------
             1 0 0 1 0 0  → itens 0 e 3

O processador não precisa examinar um item por vez. Ele combina palavras inteiras com AND, OR, XOR e NOT. Para contar os resultados, usa uma operação de population count: quantos bits 1 existem no conjunto final.

A semântica da interface precisa aparecer na álgebra. Valores selecionados dentro da mesma faceta normalmente usam OR; facetas diferentes usam AND:

(cor=azul OR cor=verde)
AND
(marca=A)
AND
(disponível)

Não é uma regra universal de produto. É uma decisão que precisa ser explícita para que índice, API e interface contem a mesma coisa.

O bitmap denso não é gratuito

Com 100 milhões de posições, um bitmap denso ocupa 100 milhões de bits: 12,5 MB. A interseção é previsível e amigável ao hardware, mas um bitmap por valor distinto pode crescer depressa.

O ponto importante é distinguir campos de valores indexados. Cem campos não significam cem bitmaps:

• condição pode ter 3 valores;
• marca, dezenas de milhares;
• cidade, milhares;
• seller_id, milhões;
• preço não possui um conjunto pequeno de valores estáveis.

Dez mil bitmaps densos sobre 100 milhões de itens ocupariam 125 GB antes de compressão, metadados, réplicas e versões simultâneas. A conta não condena bitmaps. Ela mostra que “um bitmap denso para tudo” não fecha o contrato.

Representações diferentes para densidades diferentes

Um conjunto denso favorece palavras de bits. Um conjunto com poucos IDs pode ser menor como uma lista ordenada. Entre os extremos, podemos dividir o espaço de IDs em blocos de 65.536 posições, usando os 16 bits superiores como chave de container, como no desenho original dos Roaring bitmaps.[3]

O ID se separa em:

block_id = parte alta do document ID
offset   = posição dentro do bloco

Cada predicado guarda somente os blocos nos quais possui documentos. Um bloco pode usar:

• lista ordenada de offsets, quando há poucos elementos;
• bitmap, quando a densidade torna operações por palavra mais baratas;
• intervalos [início, comprimento], quando aparecem sequências longas.

Essa escolha é um algoritmo e um formato, não a adoção de um produto. O operador de interseção escolhe o caminho pelo par concreto:

lista ∩ lista       → dois ponteiros
lista ∩ bitmap      → testar cada offset no bitmap
bitmap ∩ bitmap     → AND por palavra
intervalo ∩ intervalo → avanço pelas fronteiras

Quando uma lista é muito menor que a outra, busca exponencial seguida de busca binária pode saltar trechos. Blocos ausentes nos dois lados são ignorados sem decodificação. A interface lógica continua sendo “interseção de conjuntos”; a representação física muda o algoritmo e o custo. Algoritmos adaptativos podem aproximar o custo da dificuldade da instância em vez de assumir apenas o pior caso.[4]

Compressão também não é espaço gratuito. Ela troca bytes por CPU, muda a granularidade de leitura e pode tornar updates mais caros. O custo real depende da codificação, da hierarquia de memória, da velocidade de decodificação e do operador executado sobre os inteiros comprimidos.[2][6][7]

E os filtros de faixa?

Preço, quilometragem ou ano não cabem confortavelmente em “um conjunto por valor” quando o domínio é amplo.

Há pelo menos três famílias de construção:

1. igualdade: manter conjuntos por valor ou bucket e unir os que caem na faixa;
2. faixa cumulativa: manter conjuntos como preço <= limite, permitindo responder uma faixa por diferença entre limites;
3. bits do valor: decompor o número em posições binárias e avaliar comparações por um pequeno circuito de operações lógicas.

Buckets economizam estruturas, mas aproximam a fronteira e podem exigir refinamento. Faixas cumulativas aceleram certas comparações ao custo de update amplification. Decomposição em bits reduz a quantidade de conjuntos, mas torna o algoritmo de comparação mais elaborado.

A resposta correta depende do mix de igualdade, faixa, memória e atualização. O paper de Chan e Ioannidis é valioso não por fornecer um vencedor, mas por tratar essa escolha como uma fronteira espaço–tempo, e não como uma opção booleana chamada “índice bitmap”.[2]

Também podemos manter pares (valor, document_id) em blocos ordenados com mínimo, máximo e quantidade de documentos. Uma busca binária localiza os limites da faixa. Depois, o planejador escolhe entre dois caminhos:

• intervalo como gerador: se a faixa for seletiva, produzir seus IDs e intersectar com os outros filtros;
• intervalo como verificador: se outros filtros já deixaram poucos candidatos, ler preço[id] no índice direto e testar somente esses documentos.

A segunda opção evita construir um conjunto grande que será descartado logo depois. O mesmo princípio vale para predicados categóricos caros: estruturas invertidas geram candidatos enquanto são eficientes; o índice direto verifica o restante quando a população ficou pequena.

Um planejador adaptativo

Cada conjunto pode manter cardinalidade, quantidade de blocos e densidade. Assim como no otimizador do System R, o plano usa estimativas para escolher acesso e ordem, sem alterar a expressão lógica pedida pelo usuário.[5] Um plano inicial ordena os grupos mais seletivos primeiro:

grupos = OR dos valores dentro de cada faceta
ordenar grupos por cardinalidade estimada
candidatos = primeiro grupo
para cada grupo restante:
    candidatos = candidatos ∩ grupo
    se candidatos estiver vazio: encerrar

Depois de cada operação, a cardinalidade real fica conhecida. Se restarem poucos IDs, o plano pode abandonar novas materializações e verificar os atributos diretamente. Não existe ordem universalmente ótima: correlação, skew, densidade e cache mudam o custo mesmo quando a álgebra produz o mesmo resultado.

O primeiro mecanismo completo

Em uma máquina, a busca já pode seguir este fluxo:

query estruturada
→ validar operadores e valores
→ buscar conjunto de cada predicado
→ OR entre valores da mesma faceta
→ AND entre facetas
→ AND com o conjunto de itens vivos
→ popcount para total
→ IDs candidatos

Os invariantes mínimos são:

• todos os conjuntos de uma geração usam o mesmo espaço de IDs;
• itens indisponíveis não aparecem no conjunto live;
• ausência de uma faceta não significa conjunto vazio;
• NOT é limitado pelo conjunto de itens vivos, não pelo infinito;
• cada representação implementa a mesma álgebra observável;
• falha na construção de uma nova versão preserva a anterior.

Isso encontra itens. Ainda não calcula corretamente a navegação lateral da interface. Se marca=A já está ativa, contar marca=B sobre o resultado atual produziria zero por definição. A próxima parte remove a própria faceta antes de contar suas alternativas — sem recalcular a consulta inteira centenas de vezes.

Referências

1. Justin Zobel e Alistair Moffat. Inverted Files for Text Search Engines, ACM Computing Surveys, 2006.
2. Chee-Yong Chan e Yannis E. Ioannidis. Bitmap Index Design and Evaluation, SIGMOD 1998.
3. Samy Chambi, Daniel Lemire, Owen Kaser e Robert Godin. Better Bitmap Performance with Roaring Bitmaps, 2016.
4. Erik D. Demaine, Alejandro López-Ortiz e J. Ian Munro. Adaptive Set Intersections, Unions, and Differences, SODA 2000.
5. Patricia G. Selinger et al. Access Path Selection in a Relational Database Management System, SIGMOD 1979.
6. Giulio Ermanno Pibiri e Rossano Venturini. Techniques for Inverted Index Compression, ACM Computing Surveys, 2021.
7. Daniel Lemire, Leonid Boytsov e Nathan Kurz. SIMD Compression and the Intersection of Sorted Integers, 2016.

Parte anterior: A pergunta

Próxima parte: Contar facetas sem repetir a busca