o problema
Um bitmap index gasta um bit por linha para cada valor de atributo, e com isso transforma consulta em operação de palavra: interseção vira AND, união vira OR, e o processador faz 64 linhas por instrução. O preço é memória. Por isso a linha dominante desde o BBC da Oracle foi comprimir com run-length encoding alinhado a palavra. WAH divide o bitmap em palavras de w-1 bits e separa dois tipos: literais, com mistura de zeros e uns, e fills, sequências homogêneas cujo comprimento vai codificado na própria palavra. Em dados esparsos isso degenera: para um conjunto como {0, 2(w-1), 4(w-1), …}, WAH gasta 2w bits por bit setado. Concise corta esse custo pela metade reservando alguns bits da palavra de fill para indicar a posição de um bit dissidente.
O que ninguém contabilizava era o outro custo. Um formato RLE não tem acesso aleatório: checar ou mudar o i-ésimo bit é O(n), então a estrutura representa um conjunto de inteiros sem conseguir responder rápido se um inteiro pertence ao conjunto. E RLE pula mal: num AND onde um lado tem uma corrida longa de zeros, você gostaria de saltar as palavras correspondentes do outro lado, e sem índice auxiliar não dá. Ainda assim, a literatura da época — Colantonio e Di Pietro, entre outros — tratava WAH e Concise como o melhor que havia.
a ideia
Parar de comprimir a sequência e passar a particionar o universo. Os 32 bits do inteiro se quebram em duas metades: os 16 mais significativos viram a chave de um bloco, os 16 menos significativos viram o conteúdo. Cada bloco escolhe sua própria representação conforme a densidade que tem: bloco denso vira um bitmap literal de 65.536 bits, bloco esparso vira um array ordenado dos 16 bits baixos. Densidade quase nunca é uniforme ao longo do universo, e RLE trata o bitmap inteiro com um esquema só.
A ideia não é nova: o RIDBit, de O’Neil e O’Neil, já era uma B-tree de bitmaps que trocava para lista quando o bloco ficava ralo, e apanhou do FastBit, baseado em WAH. O que mudou entre um e outro foi o hardware — o popcnt chegou aos processadores de mesa em 2008, e contar bits deixou de ser table lookup — mais escolhas de algoritmo dentro dos blocos.
como funciona
O primeiro nível é um array dinâmico ordenado pelas chaves de 16 bits; para um milhão de inteiros ele tem no máximo 16 entradas e mora no cache. Presença de x: busca binária pela chave x/65536, depois teste de bit no bitmap ou nova busca binária no array. O limiar entre os dois tipos é 4.096 elementos, e ele garante o teto de 16 bits por inteiro dentro do contêiner: acima disso o bitmap de 65.536 bits sai mais barato que 16 bits por elemento, abaixo o array custa exatamente 16. Cada contêiner guarda sua cardinalidade num contador, o que dá cardinalidade total, rank e select baratos.
Operação lógica é um merge dos dois arrays de chaves, em O(n1+n2), com três casos no segundo nível. Bitmap contra bitmap: 1.024 palavras de 64 bits, OR palavra a palavra e Long.bitCount no resultado. Para a interseção, o caminho é indireto de propósito: primeiro conta os bits do AND, e só com a contagem na mão decide se materializa bitmap ou array — evita produzir um contêiner e convertê-lo depois. Bitmap contra array: itera o array e testa cada valor no bitmap. Array contra array: merge simples quando as cardinalidades diferem por menos de um fator 64, galloping quando um lado é muito menor. Unir centenas de bitmaps usa um min-heap por chave, clona o contêiner de maior cardinalidade e faz ORs in-place, calculando a cardinalidade uma única vez no fim.
A extração dos bits setados, usada em toda conversão de bitmap para array, é o truque clássico do Hacker’s Delight:
enquanto w != 0:
t = w AND -w # isola o bit menos significativo
emite bitCount(t-1) # posição dele
w = w AND (w-1) # apaga esse bito que isso custou
Roaring não comprime corrida de uns. Quando os dados estão ordenados de modo a produzir fills longos, o RLE ganha: no Wikileaks, Concise e WAH ficaram cerca de 30% menores. Em densidade muito baixa o overhead de estrutura domina — o Census2000, com bitmaps de cardinalidade média 30 sobre um universo de 37.019.068, foi excluído do experimento porque Roaring gastava 4 vezes a memória de Concise (embora ainda fosse 4 vezes mais rápido no AND). O próprio texto assume densidade acima de 0,1% e diz que abaixo disso bitmap não é a estrutura certa.
Contra bitmap não comprimido, Roaring perde onde deveria: no CensusIncome e no Weather, o BitSet do Java foi mais que duas vezes mais rápido, gastando três vezes mais memória. Manter a cardinalidade atualizada tira cerca de 30% da vazão dos ORs. E os números vêm de uma medição estreita: uma JVM 1.7, um AMD FX-8150, tudo em memória, só AND e OR. Os autores deixam explicitamente para depois os contêineres de run, o packing dos arrays, o uso de SIMD e operações além de união e interseção.
onde isso aparece hoje
O formato saiu do paper para dentro da infraestrutura de dados aberta. O próprio artigo registra a adoção pela biblioteca Java em Spark e Druid, e o Lucene 5.0 passou a usar um RoaringDocIdSet para comprimir identificadores de documento — o caso de uso mais direto possível, conjuntos de docids que vivem sendo interseccionados. A lição de projeto é mais geral que o formato: a escolha entre bitmap e array por bloco é uma decisão explícita de onde pagar, do tipo que a conjectura RUM formalizaria depois, e ela venceu um esquema que otimizava só espaço.