Construindo uma busca por filtros: a pergunta

Tenho certa implicância com perguntas de system design que terminam assim que alguém menciona o nome de uma tecnologia.

Durante algum tempo, usei uma pergunta que parecia simples: como construir uma busca por filtros parecida com a de um grande marketplace?

O candidato podia escolher qualquer linguagem. Também tinha servidores, discos, memória, processadores, switches e roteadores à disposição. O que ele não tinha era um produto pronto de busca ou banco de dados para encerrar a conversa com um nome. A restrição não é realista para um projeto comercial; ela remove a resposta automática e deixa exposto o que acontece por baixo das ferramentas.

Eu começava pequeno. Uma tabela, alguns itens e meia dúzia de filtros. Depois aumentava as restrições, uma de cada vez, até que a solução precisasse lidar com dezenas ou centenas de milhões de itens, centenas de filtros, atualizações contínuas e dezenas de milhares de consultas por segundo.

Cada degrau preserva o problema anterior e remove uma simplificação.

A primeira versão ainda cabe numa consulta SQL:

SELECT id
FROM items
WHERE category = ?
  AND brand = ?
  AND price BETWEEN ? AND ?;

Isso não é uma resposta ruim. Para um catálogo pequeno, talvez seja exatamente a resposta correta. Atributos multivalorados podem viver numa relação item_value; uma consulta pode usar joins, agrupamentos e COUNT(DISTINCT item_id) para impedir que o mesmo item seja contado duas vezes. Sob uma leitura por snapshot, itens, ordenação e agregações também podem permanecer coerentes.

O limite não aparece porque “SQL não escala” como slogan. Ele aparece no plano físico: quantas linhas de associação os joins produzem, quanto custa eliminar duplicatas, quantos grupos precisam ser contados, quando uma ordenação derrama para disco e como skew ou uma página profunda alteram a cauda. A tradição de otimização baseada em custo do System R já separava a expressão declarativa da escolha de access paths e ordem de joins.[1] O problema começa quando cada página precisa informar centenas de facetas enquanto o catálogo muda e milhares de combinações diferentes chegam a cada segundo.

A parte útil para esta série não é abandonar o banco de dados por princípio. É explicar qual contrato deixou de caber no orçamento e reconstruir, usando estruturas mais simples, um caminho diferente.

Antes do índice, o que é pesquisável?

Imagine um anúncio com duas variações:

Se o anúncio inteiro virar um único documento, ele terá cores={vermelho, azul} e tamanhos={P, M}. Uma busca por cor=vermelho E tamanho=M retornará o anúncio, embora nenhuma variação possua essa combinação.

O documento pesquisável deve preservar a correlação entre atributos.

A granularidade incorreta produz uma resposta logicamente errada antes de qualquer discussão sobre escala. Por isso, eu definiria documento pesquisável como a menor unidade cujos atributos possam ser combinados independentemente.

Nesse exemplo, cada variação vira um documento. A busca encontra variações; a camada de apresentação pode agrupá-las novamente pelo anúncio. O mesmo raciocínio vale para ofertas de vendedores diferentes, localidades, condições de entrega e preços.

Essa decisão também define a contagem. Se três variações do mesmo anúncio satisfazem a consulta, a interface conta três documentos, um anúncio ou uma oferta? O índice não deveria adivinhar. A unidade de cardinalidade pertence ao contrato.

Um filtro como “marca = X” divide o catálogo em dois conjuntos: itens que pertencem e itens que não pertencem a X. “Entrega amanhã”, “cor azul” e “preço entre 100 e 200” fazem a mesma coisa.

Uma consulta com vários filtros é uma interseção de conjuntos. Uma faceta é uma contagem sobre interseções alternativas. Vista assim, a busca deixa de ser primeiro um problema de banco de dados e passa a ser um problema de representação: como guardar, combinar, atualizar e distribuir conjuntos com centenas de milhões de posições?

Esta série reconstrói essa conversa. Não para chegar ao nome de uma tecnologia, mas para derivar as estruturas de dados, os algoritmos e os protocolos que tornam essa busca possível — e os problemas novos que cada solução introduz.

O contrato antes da arquitetura

Antes de escolher uma estrutura, precisamos dizer o que “buscar” significa. Nosso mecanismo receberá filtros estruturados, como:

• igualdade: categoria = celular;
• múltipla escolha dentro da mesma faceta: cor = azul OU verde;
• combinação entre facetas: categoria = celular E marca = A;
• faixa: 100 <= preço < 200;
• ordenação por uma chave conhecida, com desempate estável;
• paginação sem materializar todos os resultados;
• contagem das alternativas de cada faceta.

Os campos podem ser ausentes, nulos ou multivalorados. Precisamos decidir se ausência forma um bucket, se NOT inclui itens sem valor e se uma contagem mede itens distintos ou associações. Um item com três cores continua sendo um item; esquecer essa distinção infla resultados antes de qualquer problema de escala.

A query pode ser representada como uma árvore de predicados. O request carrega essa árvore, a ordenação, as facetas solicitadas, a deadline e, quando houver, o cursor. A resposta carrega itens, total, counts, geração observada e um estado de completude. Falta de shard ou faceta não pode virar zero silencioso.

Busca textual e relevância ficam fora do problema. Elas introduziriam outro modo de recuperar candidatos. Podemos acoplar esse modo depois, mas misturá-lo agora esconderia a estrutura que queremos estudar.

Também precisamos separar três respostas que uma interface costuma apresentar como se fossem uma só:

1. quais itens atendem aos filtros;
2. quais são os primeiros itens segundo a ordenação;
3. quantos itens restariam para cada alternativa de filtro.

A terceira resposta é a que muda a dificuldade. Para mostrar marca A (7), marca B (3) e marca C (0), o sistema não conta somente o resultado já filtrado por marca A. Ele precisa aplicar os demais filtros, retirar temporariamente a própria faceta marca e contar cada alternativa sobre essa base.

Alguns números mudam a conversa

Com 100 milhões de itens, um único bit por item ocupa 12,5 MB sem compressão. Cem desses conjuntos ocupam 1,25 GB; mil ocupam 12,5 GB; dez mil chegam a 125 GB.

“Centenas de filtros” também é uma descrição insuficiente. Um campo marca pode produzir dezenas de valores; cidade, centenas; seller_id, milhões. A quantidade de estruturas depende da cardinalidade dos valores, de sua distribuição e dos operadores que precisamos responder — não apenas da quantidade de campos na interface.

O mesmo vale para as consultas. Dez mil buscas por segundo não significam dez mil operações. Se distribuirmos toda consulta para 64 partições, criamos até 640 mil consultas internas por segundo antes de contar réplicas, retries ou hedging. Distribuir cedo demais pode multiplicar o problema antes de resolvê-lo.

Essas estimativas não escolhem a solução. Elas servem para eliminar respostas que dependem de memória infinita, fan-out gratuito ou manutenção sem custo.

O que eu esperava observar

Eu não esperava que alguém chegasse imediatamente à arquitetura completa. O que eu observava era a progressão do raciocínio.

Um bom começo era transformar o enunciado em perguntas:

• o que exatamente é pesquisável: anúncio, oferta ou variação?
• quais atributos são categóricos, numéricos ou multivalorados?
• quantos atributos um documento realmente possui?
• quais facetas precisam de contagem exata?
• quais ordenações são necessárias?
• qual atraso de indexação é aceitável?
• qual é a taxa de update e delete?

Depois, eu esperava que a resposta mudasse de forma conforme os números aparecessem. A solução específica podia variar; cada decisão precisava vir acompanhada de uma explicação sobre memória, CPU, disco, rede, latência, consistência e complexidade operacional.

A progressão da série

Vamos aumentar o sistema em sete etapas:

1. formular o contrato e reconhecer o limite da primeira consulta SQL;
2. representar filtros como conjuntos e combiná-los com operações lógicas;
3. calcular contagens de facetas sem repetir todo o trabalho;
4. aceitar inserts, updates e deletes sem bloquear leitores;
5. ordenar e paginar resultados sobre um catálogo em mudança;
6. particionar o índice quando uma máquina não basta;
7. fechar o contrato online: replicação, gerações, falhas, backpressure e verificação.

A solução de cada parte será deliberadamente incompleta. O objetivo é preservar o que já funciona e introduzir apenas o mecanismo necessário para a próxima restrição. Foi assim que eu conduzia a pergunta: começar por algo pequeno e aumentar o problema até que o candidato precisasse mudar de modelo, não apenas de ferramenta.

Na próxima parte, a tabela dará lugar a uma coleção de conjuntos. Esse movimento torna interseções baratas, mas cria duas perguntas novas: como representar os conjuntos sem desperdiçar memória e como manter uma identidade posicional estável para itens que entram e saem?

Referências

1. Patricia G. Selinger et al. Access Path Selection in a Relational Database Management System, SIGMOD 1979.

Próxima parte: Filtros como conjuntos