o problema
Todo DBMS relacional comercial de 2005 guardava os atributos de uma linha contíguos em disco. Faz sentido para OLTP: uma escrita empurra o registro inteiro, e o custo por transação é baixo. Só que a mesma decisão é ruinosa quando a carga é a oposta — carga em lote seguida de um período longo de query ad-hoc sobre agregados. Aí a query toca três colunas de vinte e o sistema arrasta as vinte do disco, porque a unidade física é a linha.
Some a isso duas heranças do mundo write-optimized. Os valores eram guardados no formato nativo, alinhados a byte ou palavra, porque se achava caro demais deslocar bits em memória para processar. E o arsenal de aceleração era índice B-tree, primário ou secundário, sobre tabelas materializadas — estruturas boas para achar poucos registros, ruins para varrer muitos. Data warehouse, CRM, catálogo de biblioteca: aplicação que lê muito e escreve pouco estava pagando o preço de um projeto feito para o caso contrário.
a ideia
O movimento central é uma troca de moeda. CPU está barateando mais rápido que banda de disco, então vale queimar ciclo para ler menos byte. Guardando a coluna contígua, dá para codificar o valor numa forma compacta — estado americano cabe em seis bits, a abreviação de duas letras gasta dezesseis — e empacotar N valores de K bits em N*K bits, sem folga de alinhamento. E dá para ir além: manter o dado comprimido durante a execução da query, descomprimindo só quando o valor precisa sair para a aplicação.
O segundo movimento é mais radical que a coluna. O C-Store não guarda a tabela. Guarda projeções: conjuntos de colunas ancorados numa tabela lógica, cada um ordenado por uma chave, e a mesma coluna pode aparecer em várias projeções com ordenações diferentes. Como a compressão sai barata, cabem muitas ordens no orçamento de espaço — e essa redundância paga duas contas de uma vez, disponibilidade e desempenho.
O terceiro é reconhecer que warehouse também precisa de update. Em vez de escolher entre estrutura boa de leitura e estrutura boa de escrita, o sistema tem as duas: um Writeable Store pequeno, um Read-optimized Store grande, e um tuple mover que migra registros de um para o outro em lote.
como funciona
Uma projeção tem o mesmo número de linhas da tabela âncora e pode incluir colunas de outras tabelas, desde que exista uma cadeia de relações n:1 até elas. Ela é particionada horizontalmente em segmentos por faixa de valor da chave de ordenação. No RS, a storage key de um registro é a posição ordinal dele no segmento — não é armazenada, é calculada. No WS ela é explícita. Join indexes, pares (sid, storage key), ligam projeções ancoradas na mesma tabela e permitem remontar a linha completa.
São quatro codificações no RS, escolhidas pela ordenação da coluna e pela quantidade de valores distintos. Auto-ordenada com poucos valores vira triplas (v, f, n) — valor, primeira posição, repetições — com B-tree densepack sobre o campo de valor. Ordenada por outra coluna com poucos valores vira pares (v, bitmap) com run-length encoding, mais um offset index para achar o i-ésimo valor. Auto-ordenada com muitos valores vira delta por bloco. O quarto caso, ordem estrangeira com muitos valores, fica sem compressão.
O WS é B-tree sobre BerkeleyDB, sem compressão, com a aposta de que ele é pequeno e mora quase todo em memória. O tuple mover roda em background: acha um par (RS, WS), descarta o que foi deletado antes da low water mark, funde o resto num RS’ novo e faz cutover — old-master/new-master, não update-in-place, porque quase todo objeto se move mesmo.
O isolamento vem de epochs. Um site é a timestamp authority, avisa o fim do epoch, espera todo mundo confirmar e publica a nova high water mark. Query read-only escolhe um instante entre a low e a high water mark e lê consultando o insertion vector e o deleted record vector para decidir a visibilidade de cada registro. Escrita usa 2PL estrito, log só de UNDO, e commit sem a fase PREPARE.
o que isso custou
O que está medido é menos do que está desenhado, e os autores dizem isso. Só o storage engine e o executor do RS rodavam; WS e tuple mover estavam em implementação inicial e ficaram fora do benchmark. Não há nenhum número de update. O RS não suportava segmento nem múltiplos nós, então todos os tempos são de uma máquina só. O texto chama os dados de muito preliminares.
Os join indexes são caros de guardar e manter: qualquer modificação numa projeção obriga a atualizar todo join index que aponta para dentro ou para fora dela. A mitigação é indireta — guardar cada coluna em várias projeções para precisar de poucos join indexes. E o problema de design físico (quais projeções, quais chaves, quais join indexes, dentro de um orçamento B e garantindo K-safety) é difícil o bastante para os autores estarem escrevendo uma ferramenta automática, porque não há DBA suficiente no mundo.
O commit sem PREPARE tem uma consequência assumida: um site que recebeu ordem de commit pode cair antes de persistir qualquer coisa, e a recuperação depende de puxar o estado de outras projeções em outros nós. Viagem no tempo arbitrária também está fora — só o intervalo entre as duas marcas d’água, porque o geral seria caro demais. E o benchmark é uma versão simplificada de TPC-H: três tabelas, colunas só INTEGER e CHAR(1), sete queries, esquema afinado à mão para cada sistema. Dando aos concorrentes as mesmas visões materializadas, a vantagem cai de 164 vezes para 6,4 sobre o row store e de 21 para 16,5 sobre o column store — só que aí o row store passa a ocupar 11,900 GB.
onde isso aparece hoje
O pacote inteiro — coluna, compressão pesada, execução sobre o dado comprimido, ordenação múltipla — virou o desenho padrão de warehouse analítico. O C-Store foi comercializado como Vertica, e a arquitetura reaparece nos sistemas de nuvem que vieram depois: The Snowflake Elastic Data Warehouse, Amazon Redshift Re-invented e a proposta de Lakehouse, que leva o formato colunar para arquivo aberto em object storage. Dremel resolve o problema irmão, o de dado aninhado, com a mesma intuição de nunca ler coluna que a query não pediu.
O tuple mover herda explicitamente a ideia de merge-out da LSM-Tree, citada no paper: acumular escrita numa estrutura pequena e fundir em lote com a estrutura grande. E a tensão que o C-Store escolhe resolver de um jeito específico — pagar espaço e custo de escrita para ganhar leitura — é exatamente a que a conjectura RUM formalizaria depois como um triângulo do qual não se escapa.