Construindo uma busca por filtros: contar facetas

O candidato agora consegue representar predicados como conjuntos. Intersectar categoria=celular, marca=A e cor=azul produz os IDs que atendem à consulta.

Mas uma interface de busca facetada pede algo diferente. Enquanto marca=A está selecionada, ela pode mostrar:

Marca
[x] A  (7)
[ ] B  (3)
[ ] C  (0)

Esses números não são contagens do resultado atual. O resultado já contém somente a marca A; intersectá-lo com B sempre daria zero. Para contar alternativas de marca, precisamos preservar todos os outros filtros e retirar temporariamente o grupo marca.

Encontrar usa todos os filtros. Contar uma faceta usa todos, menos ela mesma.

Primeiro, agrupar a query

Chamemos de G_f o conjunto produzido por uma faceta f. Se a mesma faceta aceita múltipla escolha, ela combina seus valores com OR:

G_cor = azul OR verde
G_marca = A
G_categoria = celular

O resultado atual é:

R = live AND G_cor AND G_marca AND G_categoria

Para contar alternativas de marca, usamos uma base sem G_marca:

B_marca = live AND G_cor AND G_categoria

Então cada valor é contado por:

count(marca=v) = popcount(B_marca AND bitmap(marca=v))

A regra vale para qualquer faceta. É conhecida em interfaces de busca como navegação lateral ou drill sideways, mas não precisamos de um componente pronto para derivá-la. Precisamos apenas retirar um grupo da interseção e contar alternativas sobre a base restante.

A implementação ingênua repete trabalho

Com m facetas ativas, podemos recalcular B_f do zero para cada uma. Isso realiza aproximadamente m × (m - 1) interseções de bitmaps antes mesmo de contar os valores.

A query é pequena quando há três filtros. Com dezenas de grupos ativos, bitmaps grandes e milhares de consultas simultâneas, repetir a mesma interseção se torna desperdício previsível.

Uma forma de reutilização é construir prefixos e sufixos:

P[i] = live AND G[0] AND ... AND G[i-1]
S[i] = G[i+1] AND ... AND G[m-1]

B[i] = P[i] AND S[i]

Para os grupos A, B, C, D:

sem A = live ∩ B ∩ C ∩ D
sem B = live ∩ A ∩ C ∩ D
sem C = live ∩ A ∩ B ∩ D
sem D = live ∩ A ∩ B ∩ C

Prefixos acumulam a esquerda; sufixos, a direita. Depois de duas passagens lineares, cada base “todos menos um” exige uma interseção adicional, não uma nova travessia completa dos grupos.

Isso troca memória temporária por menos trabalho repetido. Não é sempre o melhor plano: com poucos grupos ou um resultado que fica vazio cedo, ordenar por seletividade e interromper pode ser mais barato. O ponto é que a álgebra permite um planejador, em vez de obrigar uma sequência fixa.

A ordem das interseções importa

AND é comutativo no resultado, mas não no custo intermediário. Começar pelo conjunto mais seletivo pode produzir rapidamente poucos candidatos. Representações comprimidas também têm custos diferentes conforme densidade e layout. A literatura de interseção adaptativa reforça que a dificuldade depende da instância e da distribuição, não apenas da soma das cardinalidades.[3]

Podemos manter estatísticas por conjunto:

• cardinalidade;
• bytes ocupados;
• densidade por bloco;
• custo recente de interseção;
• frequência de uso;
• idade da estatística.

Esses números ajudam a escolher ordem e operador, mas não alteram a semântica. Uma estimativa errada pode tornar a query lenta; não pode torná-la incorreta.

Contar pelos resultados ou pelos índices

Depois de construir a base de uma faceta, ainda há duas estratégias físicas.

Quando a base é pequena, percorremos os documentos e usamos o índice direto:

para cada documento em B_f:
    para cada faceta solicitada:
        para cada valor do documento:
            contador[faceta][valor]++

Quando a base é grande, intersectar com postings e aplicar popcount pode ser mais barato. O planejador escolhe usando cardinalidade, quantidade de facetas, representação dos conjuntos e custo observado. A semântica é a mesma; muda o caminho para obter os contadores.

Esse detalhe também reforça por que contamos documentos distintos. Um documento multivalorado pode incrementar vários buckets da mesma faceta, mas não pode entrar duas vezes no mesmo bucket.

Contar todos os valores pode dominar a consulta

Suponha que B_marca esteja pronto. Ainda precisamos intersectá-lo com cada marca que a interface pretende mostrar.

Para uma faceta pequena, isso é barato. Para seller_id com milhões de valores, “contar tudo” não é uma operação razoável. O contrato da API precisa limitar a pergunta:

• mostrar somente valores configurados para a categoria;
• retornar os primeiros k valores por contagem ou por uma ordem estável;
• usar um dicionário de valores candidatos antes de calcular counts;
• não oferecer facet count para campos cuja cardinalidade não fecha o orçamento.

Embora o catálogo tenha centenas de atributos, a página normalmente exibe apenas os relevantes para a categoria e para aquele estágio da navegação. Pedir quinze facetas é um protocolo diferente de pedir todas. “Mostrar mais” também pode disparar uma segunda consulta em vez de cobrar o custo máximo em toda resposta.

Para uma consulta muito ampla, o produto pode aceitar amostragem estratificada ou outro estimador. Nesse caso, a resposta precisa separar exact de approximate e carregar erro, confiança ou limite aplicável. Resultado aproximado apresentado como exato não é otimização; é mudança silenciosa de contrato.

Essa não é uma limitação acidental da implementação. Uma interface com centenas de filtros não precisa pedir milhões de contagens em toda consulta. Produto e protocolo de busca precisam concordar sobre quais facetas são navegáveis, em qual contexto e com que limite.

Múltipla escolha muda o significado da contagem

Quando o usuário seleciona azul OU verde, o número mostrado ao lado de vermelho pode significar pelo menos duas coisas:

1. quantos resultados haveria se vermelho substituísse a seleção atual;
2. quantos resultados haveria se vermelho fosse acrescentado à seleção.

Na segunda semântica:

count_adicionar(vermelho)
=
popcount(B_cor AND (G_cor OR vermelho))

Na primeira:

count_substituir(vermelho)
=
popcount(B_cor AND vermelho)

As duas respostas são defensáveis. Misturá-las é bug de contrato. Esse ponto força a conversa a sair de “qual índice usar?” e voltar para “o que a interface promete?”. Modelos mais ricos também podem preservar correlação entre facetas, em vez de tratá-las sempre como dimensões independentes.[4]

Cache ajuda, mas não fecha o problema

Consultas populares podem ser memorizadas por uma chave canônica que inclua:

filtros normalizados
+ ordenação
+ geração do índice
+ versão da semântica de facetas

Sem geração, o cache pode servir counts de um catálogo antigo. Sem normalização, A AND B e B AND A ocupam entradas diferentes. Sem limite, a diversidade de combinações destrói a taxa de acerto.

Cache reduz repetição entre queries. Prefixos, sufixos e ordem de interseção reduzem repetição dentro de uma query. São camadas diferentes.

O contrato desta etapa

Ao final, uma máquina consegue:

• transformar valores selecionados em grupos de conjuntos;
• encontrar o conjunto atual;
• retirar uma faceta sem refazer todo o trabalho;
• contar alternativas limitadas por configuração;
• distinguir adicionar de substituir em múltipla escolha;
• vincular resultados e cache a uma geração.

Tudo isso ainda assume um catálogo quase imóvel. Limpar um bit parece simples, mas um update precisa saber quais bits antigos remover, preservar leitores que já começaram e impedir que metade dos índices pertença a uma versão e metade a outra.

A próxima parte introduz mutabilidade sem editar no lugar o estado que uma consulta já está lendo.

Referências

1. Chee-Yong Chan e Yannis E. Ioannidis. Bitmap Index Design and Evaluation, SIGMOD 1998.
2. Samy Chambi, Daniel Lemire, Owen Kaser e Robert Godin. Better Bitmap Performance with Roaring Bitmaps, 2016.
3. Erik D. Demaine, Alejandro López-Ortiz e J. Ian Munro. Adaptive Set Intersections, Unions, and Differences, SODA 2000.
4. Ori Ben-Yitzhak et al. Beyond Basic Faceted Search, WSDM 2008.

Parte anterior: Filtros como conjuntos

Próxima parte: Atualizar o índice sem interromper a busca