Construindo uma busca por filtros: ordenar e paginar

O resultado de uma interseção é um conjunto. A interface, porém, pede uma sequência: menor preço, mais recente, distância, popularidade ou outra chave conhecida.

Ordenar todos os candidatos a cada consulta funciona no catálogo pequeno. Em escala, precisamos parar assim que encontramos os primeiros k itens e evitar refazer o começo da sequência para buscar a página seguinte.

O cursor não é apenas uma posição: ele identifica a ordem e o snapshot observados.

Toda ordenação precisa ser total

“Ordenar por preço” não define o que fazer com dois itens de mesmo preço. Sem desempate, réplicas ou execuções diferentes podem inverter os itens e produzir páginas instáveis.

Acrescentamos um identificador único:

(preço ASC, item_id ASC)

Para mais recentes:

(created_at DESC, item_id DESC)

A última chave nunca empata. Isso cria uma ordem total e permite dizer com precisão o que vem depois de um resultado.

Dois caminhos para obter top k

Suponha que o bitmap final tenha n candidatos e a página peça k = 20.

Materializar os candidatos

Quando n é pequeno:

1. enumerar os bits ligados;
2. buscar a chave de ordenação de cada item;
3. manter um heap de tamanho k ou aplicar seleção parcial;
4. ordenar somente os vencedores.

O custo acompanha a quantidade de candidatos, não o catálogo inteiro.

Percorrer a ordem

Quando o resultado é amplo e existe uma sequência pré-construída para a ordenação:

1. percorrer pares (sort_key, item_id) na ordem;
2. testar membership no bitmap final;
3. coletar matches;
4. parar após k resultados.

Esse caminho é bom quando encontramos matches cedo. Pode ser ruim para um conjunto muito seletivo: percorrer milhões de entradas para achar vinte bits ligados troca uma ordenação cara por um scan caro.

A sequência pode ser dividida em blocos com um resumo dos IDs presentes. Antes de percorrer um bloco de preço, testamos se seu resumo possui alguma interseção com o conjunto de candidatos. Blocos sem candidatos são pulados inteiros. O mesmo princípio de min/max ajuda a podar blocos em faixas numéricas.

Nenhum caminho vence sempre. O planejador pode usar popcount, estatísticas de seletividade e amostras recentes para escolher. A decisão afeta custo, não resultado.

Quando a ordenação depende da query

Até aqui, a ordem vem de uma chave estruturada conhecida, como preço ou data. Se ela passar a depender da consulta — relevância textual, popularidade contextual, personalização ou combinação de sinais — percorrer todos os candidatos para calcular score pode dominar o custo.

O WAND usa limites superiores para decidir quais documentos merecem avaliação completa.[1] Block-Max WAND leva essa ideia aos blocos das posting lists: cada bloco registra um máximo e pode ser ignorado com segurança quando não consegue superar o pior item já presente no top k.[2]

Esses algoritmos não são necessários para a busca booleana descrita nesta série. Eles marcam a fronteira seguinte: ranking dependente da query com terminação antecipada segura.

Ordenações também pertencem ao snapshot

Se preço muda, a posição do item muda. O segmento precisa publicar juntos:

• os bitmaps de filtros;
• as colunas necessárias para exibição;
• as estruturas das ordenações suportadas;
• o mapa de IDs;
• o manifesto da geração.

Publicar o bitmap novo com a ordem antiga cria uma resposta que nunca existiu em um snapshot consistente. O mesmo protocolo de geração usado nas atualizações precisa cobrir as estruturas de ordenação.

Isso também limita o número de ordenações. Uma interface pode permitir preço, data e popularidade, mas “ordenar arbitrariamente por qualquer expressão” é outro contrato. Cada ordem materializada consome build, memória, atualização e verificação.

Por que offset se degrada

Uma paginação por offset pede algo como “ignore os primeiros 100 mil matches e devolva vinte”. Mesmo com uma sequência ordenada, o sistema precisa localizar e descartar os matches anteriores. O trabalho cresce com a profundidade.

Além disso, inserts e deletes antes do offset movem a janela. O usuário pode ver um item duas vezes ou pular outro.

Um cursor guarda a última chave observada:

{
  "generation": 42,
  "sort": "price_asc",
  "last_key": 95,
  "last_item_id": "72"
}

A próxima página procura valores estritamente posteriores a (95, 72) na mesma ordem. O cursor deve ser opaco para o cliente e autenticado ou validado para impedir combinações impossíveis.

O cursor precisa escolher uma política temporal

Há duas políticas principais.

Snapshot estável

O cursor fixa a geração 42. Todas as páginas seguintes leem a mesma fotografia. Isso evita duplicações causadas por updates, mas obriga o sistema a reter a geração por algum tempo.

O cursor precisa expirar. Depois da expiração, o cliente reinicia a busca ou aceita uma política de retomada explícita.

Catálogo mais recente

Cada página usa a geração atual e a última chave como âncora. O sistema evita voltar na ordem, mas itens que mudaram de posição podem aparecer novamente ou deixar de aparecer. Essa política usa menos retenção e entrega mais freshness, ao custo de uma sessão menos estável.

Nenhuma é universalmente correta. Uma navegação de compras pode aceitar pequenas mudanças; uma exportação ou auditoria talvez exija snapshot fixo. O protocolo precisa declarar a escolha.

Mudanças na chave de ordenação

Imagine um item visto na página 1 com preço 100. Antes da página 2, seu preço cai para 80.

• num snapshot estável, ele permanece onde estava;
• na geração mais recente, ele ficou antes do cursor e não reaparece;
• se o preço sobe para 120, pode reaparecer depois do cursor.

O cursor não consegue resolver sozinho a mudança de universo. Ele apenas torna a política verificável.

Combinar segmentos

Enquanto há múltiplos segmentos, cada um pode produzir seu top k local. Um heap de merge escolhe os menores elementos entre as cabeças das sequências locais:

segmento 0:  89, 95, 130...
segmento 1:  91, 92, 140...
segmento 2:  89, 97, 110...

merge:       89, 89, 91, 92, 95...

Tombstones e o conjunto live eliminam itens mortos durante a leitura. O mesmo mecanismo será usado entre máquinas na próxima parte.

Retornar k candidatos por segmento é suficiente para top k quando cada documento conta independentemente. Se a apresentação agrupa variações por anúncio ou limita resultados por vendedor, candidatos locais podem colapsar no merge. Nesse caso, cada segmento precisa devolver margem adicional ou executar agrupamento antes de afirmar que o top global está completo.

Invariantes

• toda ordenação possui desempate único;
• bitmap, chave e mapa de IDs pertencem à mesma geração;
• o cursor inclui versão da semântica e da ordenação;
• uma página nunca combina resultados de gerações diferentes sem declarar isso;
• top k local preserva informação suficiente para construir top k global;
• expiração de cursor é um estado normal do protocolo;
• o sistema limita profundidade, tamanho de página e trabalho máximo.

Agora uma máquina consegue filtrar, contar, ordenar, atualizar e paginar. Antes de distribuir, deveríamos medir se ela realmente não basta. Quando a memória, CPU, bandwidth de memória ou disponibilidade exigirem várias máquinas, a consulta deixará de ser uma operação local e se tornará um protocolo scatter-gather.

Referências

1. Andrei Z. Broder et al. Efficient Query Evaluation Using a Two-Level Retrieval Process, CIKM 2003.
2. Shuai Ding e Torsten Suel. Faster Top-k Document Retrieval Using Block-Max Indexes, SIGIR 2011.

Parte anterior: Atualizar sem interromper

Próxima parte: Quando uma máquina não basta