o problema
Protocol buffers e JSON descrevem registros em árvore: um Advertiser tem vários Campaigns, cada Campaign tem vários WordSets e vários Clicks. SQL, por outro lado, quer linhas. A ponte óbvia é o flattening: escolher, de todas as formas possíveis e independentemente em cada nível, uma ocorrência de cada grupo repetido. O resultado é um produto cartesiano. Um registro com centenas de Words e milhares de Clicks vira uma relação centenas de vezes maior que a árvore que a originou — e é isso que uma consulta que toca duas colunas teria de materializar.
Pior que o custo é a semântica. Considere um esquema com raiz A e dois filhos repetidos, B com valores 10 e 20 e C com valores 5, 15 e 25, e a consulta SELECT B, C FROM A WHERE B<C. O resultado sobre o dado achatado é (10,15), (10,25) e (20,25). Nenhuma árvore daquele esquema achata nisso: uma árvore com B em {10,20} e C em {15,25} produziria também (20,15). O Dremel processa consultas podando nós das árvores existentes, nunca criando árvores novas — é o que evita a explosão de tamanho. Então a pergunta que este paper responde não é como executar SQL sobre árvore, e sim para quais consultas podar e achatar comutam.
a ideia
A resposta é uma relação sintática sobre o esquema, não sobre o dado. Um caminho de um ancestral A até um descendente D é star free se nenhum nó do caminho, exceto possivelmente o próprio A, é repetido. O atributo A domina B se o caminho de A até o ancestral comum mais baixo de A e B é star free. A consequência é a única que importa: dentro de qualquer subárvore enraizada numa ocorrência do ancestral comum, existe exatamente uma ocorrência de A. Comparar A com B vira, então, uma decisão local por nó de B — passa ou some.
No esquema do paper, Budget domina Fee, porque de Budget até Campaign não há estrela. Por isso WHERE Budget < Fee roda podando: basta apagar os Clicks cujo Fee não passa. Já Bid e Fee não se dominam — cada um cruza uma estrela (WordSet e Clicks) antes de chegar a Campaign — e WHERE Bid < Fee deixaria sobreviver combinações que nenhuma árvore representa.
como funciona
O algoritmo de poda aceita filtros que são AND de comparações, cada uma sobre um único atributo ou sobre dois em que um domina o outro. Apaga-se o nó dominado que falha; depois a deleção propaga para cima: se o nó apagado era filho required, o pai inteiro cai; se todos os filhos de um atributo required-and-repeated caíram, o pai cai também. O Teorema 5.5 garante que achatar depois de podar dá o mesmo que podar depois de achatar. Para isso funcionar, o paper usa duas ficções: a ocorrência dummy, um filho fantasma com folhas NULL que impede anomalias de deleção, e o desvio do padrão SQL em que UNKNOWN é suficientemente verdadeiro para a linha passar.
O semi-flattening é o modelo do que o Dremel realmente lê. Em vez do produto cartesiano das sub-relações, faz-se concatenação horizontal linha a linha, com padding de NULL nas tabelas mais curtas e repetição do valor quando o caminho até a raiz corrente é star free. O repetition context de uma folha V é o conjunto de folhas que dominam V; esse conjunto é totalmente ordenado pela dominância, o subesquema correspondente é linear, e sobre esquema linear flattening e semi-flattening coincidem. Consulta confinada a um contexto, portanto, dá a resposta exata sobre a forma compacta.
No armazenamento colunar, cada valor carrega o repetition level — o nome do ancestral comum entre ele e o valor anterior da mesma coluna — e o definition level, que conta quantas subárvores intermediárias têm zero ocorrências e assim evita gravar NULL. O leitor decide, coluna a coluna, se emite o valor atual ou avança, comparando repetition levels entre atributos que se dominam. Antes de avançar num atributo required ele emite uma linha extra com NULLs à direita: sem ela, um Campaign cujos Bids todos falham o filtro sumiria do resultado. Agregações exigem que todo atributo agregado seja dominado por todos os de agrupamento, e um bit de Tag marca a primeira aparição de cada folha, porque a mesma folha aparece em várias linhas e SUM contaria duas vezes.
o que isso custou
A classe de consultas é estreita e o paper não disfarça. WHERE CID <> Word AND Budget <> Fee pode ser executada por poda, condição a condição, mas não a partir do semi-flattening: Word e Fee estão em contextos diferentes e a interseção dos dois contextos não é nenhum deles. O emparelhamento entre colunas de contextos distintos no semi-flattening é arbitrário — b1 caiu na mesma linha de c1, mas poderia ter caído com c2. Múltiplos contextos só são suportados se forem dois a dois disjuntos.
O desvio de UNKNOWN quebra a compatibilidade com o padrão SQL num ponto que um usuário vindo de outro banco não espera. O repetition level sozinho só reconstrói a árvore sob a hipótese de que toda ocorrência de um atributo tem ao menos uma ocorrência de cada filho; fora disso, é preciso o definition level. E os ganhos medidos dependem inteiramente de quantos contextos a consulta atravessa: 1,3:1 num filtro onde as duas representações coincidem, contra 250:1 com cinco contextos em logs de produção.
onde isso aparece hoje
Este é o complemento formal de Dremel: Interactive Analysis of Web-Scale Datasets, que tratou da parte de sistema; aqui está o contrato que a linguagem cumpre. O mesmo casamento de esquema em árvore com dialeto de SQL aparece em F1, citado como sistema irmão. Fora do Google, o par repetition level e definition level virou a forma padrão de guardar estrutura aninhada em formato colunar — é o que o Parquet usa para representar campos repetidos sem materializar o achatamento — e o Dremel é a base pública do BigQuery.