Visão geral da arquitetura

Versão da documentação do nosso artigo da VLDB 2024

Esta é a versão web do nosso artigo científico da VLDB 2024. Também publicamos um post no blog sobre o contexto e a trajetória do artigo, e recomendamos assistir à apresentação da VLDB 2024 de Alexey Milovidov, CTO e criador do ClickHouse:

​

RESUMO

Nas últimas décadas, a quantidade de dados armazenados e analisados aumentou exponencialmente. Empresas de diferentes indústrias e setores passaram a depender desses dados para aprimorar produtos, avaliar desempenho e tomar decisões críticas para o negócio. No entanto, à medida que os volumes de dados passaram a atingir escala de internet, as empresas precisaram gerenciar dados históricos e novos de forma econômica e escalável, ao mesmo tempo em que os analisavam com um grande número de consultas simultâneas e com exigência de latências em tempo real (por exemplo, menos de um segundo, dependendo do caso de uso).

Este artigo apresenta uma visão geral do ClickHouse, um popular banco de dados OLAP de código aberto projetado para análises de alto desempenho sobre conjuntos de dados em escala de petabytes com altas taxas de ingestão. Sua camada de armazenamento combina um formato de dados baseado em árvores log-structured merge (LSM) tradicionais com técnicas inovadoras para a transformação contínua (por exemplo, agregação, arquivamento) de dados históricos em segundo plano. As consultas são escritas em um dialeto SQL prático e processadas por um mecanismo de execução vetorizada de consultas de última geração com compilação de código opcional. O ClickHouse faz uso intensivo de técnicas de poda para evitar o processamento de dados irrelevantes nas consultas. Outros sistemas de gerenciamento de dados podem ser integrados no nível de função de tabela, mecanismo de tabela ou mecanismo de banco de dados. Benchmarks em cenários reais demonstram que o ClickHouse está entre os bancos de dados analíticos mais rápidos do mercado.

​

1 INTRODUÇÃO

Este artigo descreve o ClickHouse, um banco de dados OLAP colunar projetado para consultas analíticas de alto desempenho em tabelas com trilhões de linhas e centenas de colunas. O ClickHouse começou em 2009 como um operador de filtro e agregação para dados de arquivos de log em escala web e se tornou open source em 2016. A Figura 1 ilustra quando os principais recursos descritos neste artigo foram introduzidos no ClickHouse.

O ClickHouse foi projetado para enfrentar cinco desafios centrais do gerenciamento moderno de dados analíticos:

1. Conjuntos de dados enormes com altas taxas de ingestão. Muitas aplicações orientadas por dados em setores como web analytics, finanças e comércio eletrônico são caracterizadas por volumes de dados enormes e em crescimento contínuo. Para lidar com grandes conjuntos de dados, os bancos de dados analíticos não devem apenas oferecer estratégias eficientes de indexação e compressão, mas também permitir a distribuição de dados entre vários nós (scale-out), já que um único servidor é limitado a algumas dezenas de terabytes de armazenamento. Além disso, dados recentes costumam ser mais relevantes para insights em tempo real do que dados históricos. Como resultado, bancos de dados analíticos devem ser capazes de fazer a ingestão de novos dados de forma consistente em altas taxas ou em rajadas, bem como “despriorizar” continuamente os dados históricos (por exemplo, agregando-os ou arquivando-os) sem desacelerar as consultas de relatórios executadas em paralelo.

2. Muitas consultas simultâneas com expectativa de baixa latência. Em geral, as consultas podem ser categorizadas como ad hoc (por exemplo, análise exploratória de dados) ou recorrentes (por exemplo, consultas periódicas de dashboard). Quanto mais interativo for um caso de uso, menores serão as latências de consulta esperadas, o que traz desafios de otimização e execução de consultas. Consultas recorrentes também oferecem a oportunidade de adaptar o layout físico do banco de dados à carga de trabalho. Como resultado, os bancos de dados devem oferecer técnicas de poda que permitam otimizar consultas frequentes. Dependendo da prioridade da consulta, os bancos de dados também devem conceder acesso igualitário ou priorizado a recursos compartilhados do sistema, como CPU, memória, disco e E/S de rede, mesmo quando um grande número de consultas é executado simultaneamente.

3. Ambientes diversos de armazenamentos de dados, locais de armazenamento e formatos. Para se integrarem a arquiteturas de dados existentes, os bancos de dados analíticos modernos devem apresentar um alto grau de abertura para ler e gravar dados externos em qualquer sistema, local ou formato.

4. Uma linguagem de consulta prática com suporte à introspecção de desempenho. O uso de bancos de dados OLAP no mundo real impõe requisitos “mais brandos” adicionais. Por exemplo, em vez de uma linguagem de programação de nicho, os usuários frequentemente preferem interagir com bancos de dados por meio de um dialeto SQL expressivo com tipos de dados aninhados e uma ampla variedade de funções regulares, de agregação e de janela. Bancos de dados analíticos também devem fornecer ferramentas sofisticadas para inspecionar o desempenho do sistema ou de consultas individuais.

5. Robustez de nível industrial e implantação versátil. Como hardware comum não é confiável, os bancos de dados devem fornecer replicação de dados para garantir robustez contra falhas de nós. Além disso, os bancos de dados devem funcionar em qualquer hardware, de laptops antigos a servidores poderosos. Por fim, para evitar a sobrecarga da coleta de lixo em programas baseados em JVM e permitir desempenho bare-metal (por exemplo, SIMD), o ideal é que os bancos de dados sejam implantados como binários nativos para a plataforma de destino.

Figura 1: Linha do tempo do ClickHouse.

​

2 ARQUITETURA

Figura 2: A arquitetura de alto nível do mecanismo de banco de dados ClickHouse.

Como mostra a Figura 2, o mecanismo do ClickHouse é dividido em três camadas principais: a camada de processamento de consultas (descrita na Seção 4), a camada de armazenamento (Seção 3) e a camada de integração (Seção 5). Além delas, uma camada de acesso gerencia as sessões de usuário e a comunicação com aplicações por diferentes protocolos. Há também componentes ortogonais para threads, cache, controle de acesso baseado em funções, backups e monitoramento contínuo. O ClickHouse é desenvolvido em C++ como um único binário com vinculação estática, sem dependências.

O processamento de consultas segue o paradigma tradicional de analisar as consultas recebidas, criar e otimizar planos lógicos e físicos de consulta e executá-los. O ClickHouse usa um modelo de execução vetorizado semelhante ao MonetDB/X100 ^[11], em combinação com compilação oportunista de código ^[53]. As consultas podem ser escritas em um dialeto SQL rico em recursos, em PRQL ^[76] ou em KQL do Kusto ^[50].

A camada de armazenamento consiste em diferentes motores de tabela que encapsulam o formato e a localização dos dados da tabela. Os motores de tabela se dividem em três categorias: a primeira é a família MergeTree* de motores de tabela, que representa o principal formato de persistência no ClickHouse. Com base na ideia de árvores LSM ^[60], as tabelas são divididas em partes horizontais e ordenadas, que são continuamente mescladas por um processo em segundo plano. Os motores de tabela MergeTree* individuais diferem na forma como a mesclagem combina as linhas de suas partes de entrada. Por exemplo, as linhas podem ser agregadas ou substituídas, caso estejam desatualizadas.

A segunda categoria é a de motores de tabela de propósito específico, usados para acelerar ou distribuir a execução de consultas. Essa categoria inclui motores de tabela em memória do tipo chave-valor chamados dicionários. Um Dicionário armazena em cache o resultado de uma consulta executada periodicamente em uma fonte de dados interna ou externa. Isso reduz significativamente as latências de acesso em cenários em que certo grau de desatualização dos dados pode ser tolerado. Outros exemplos de motores de tabela de propósito específico incluem um motor puramente em memória usado para tabelas temporárias e o motor de tabela Distributed para fragmentação transparente de dados (veja abaixo).

A terceira categoria de motores de tabela é a de motores de tabela virtuais para troca bidirecional de dados com sistemas externos, como bancos de dados relacionais (por exemplo, PostgreSQL, MySQL), sistemas publish/subscribe (por exemplo, Kafka, RabbitMQ ^[24]) ou armazenamentos de chave/valor (por exemplo, Redis). Os motores virtuais também podem interagir com lagos de dados (por exemplo, Iceberg, DeltaLake, Hudi ^[36]) ou arquivos em armazenamento de objetos (por exemplo, AWS S3, Google GCP).

ClickHouse oferece suporte a sharding e replicação de tabelas em vários nós de um cluster para escalabilidade e disponibilidade. O sharding particiona uma tabela em um conjunto de shards de tabela de acordo com uma expressão de sharding. Os shards individuais são tabelas mutuamente independentes e normalmente ficam em nós diferentes. Os clientes podem ler e gravar shards diretamente, ou seja, tratá-los como tabelas separadas, ou usar o mecanismo de tabela especial Distributed, que fornece uma visão global de todos os shards da tabela. O principal objetivo do sharding é processar conjuntos de dados que excedem a capacidade de nós individuais (normalmente, algumas dezenas de terabytes de dados). Outro uso do sharding é distribuir a carga de leitura e escrita de uma tabela entre vários nós, isto é, fazer balanceamento de carga. Independentemente disso, um shard pode ser replicado em vários nós para tolerância a falhas de nós. Para isso, cada mecanismo de tabela Merge-Tree* tem um mecanismo ReplicatedMergeTree* correspondente, que usa um esquema de coordenação multi-master baseado no consenso Raft ^[59] (implementado pelo Keeper, um substituto drop-in para o Apache Zookeeper escrito em C++) para garantir que cada shard tenha, a todo momento, um número configurável de réplicas. A Seção 3.6 discute o mecanismo de replicação em detalhes. Como exemplo, a Figura 2 mostra uma tabela com dois shards, cada um replicado em dois nós.

Por fim, o mecanismo de banco de dados ClickHouse pode ser operado nos modos on-premise, cloud, standalone ou in-process. No modo on-premise, os usuários configuram o ClickHouse localmente como um único servidor ou cluster multinó com sharding e/ou replicação. Os clientes se comunicam com o banco de dados por meio dos wire protocols binários nativo, do MySQL e do PostgreSQL, ou de uma API HTTP REST. O modo cloud é representado pelo ClickHouse Cloud, uma oferta de DBaaS totalmente gerenciada e com autoscaling. Embora este artigo se concentre no modo on-premise, planejamos descrever a arquitetura do ClickHouse Cloud em uma publicação futura. O modo standalone transforma o ClickHouse em um utilitário de linha de comando para analisar e transformar arquivos, tornando-o uma alternativa baseada em SQL a ferramentas Unix como cat e grep. Embora isso não exija configuração prévia, o modo standalone é restrito a um único servidor. Recentemente, foi desenvolvido um modo in-process chamado chDB ^[15] para casos de uso de análise interativa de dados, como Jupyter notebooks ^[37] com DataFrames do Pandas ^[61]. Inspirado pelo DuckDB ^[67], o chDB incorpora o ClickHouse como um mecanismo OLAP de alto desempenho em um processo hospedeiro. Em comparação com os outros modos, isso permite transferir dados de origem e de resultado entre o mecanismo de banco de dados e a aplicação com eficiência, sem cópia, já que ambos são executados no mesmo espaço de endereçamento.

​

3 CAMADA DE ARMAZENAMENTO

Esta seção aborda os motores de tabela MergeTree* como o formato de armazenamento nativo do ClickHouse. Descrevemos sua representação em disco e discutimos três técnicas de poda de dados no ClickHouse. Em seguida, apresentamos estratégias de merge que transformam continuamente os dados sem afetar as inserções simultâneas. Por fim, explicamos como atualizações e exclusões são implementadas, bem como a desduplicação de dados, a replicação de dados e a conformidade com ACID.

​

3.1 Formato em disco

Cada tabela com table engine MergeTree* é organizada como uma coleção de partes imutáveis da tabela. Uma parte é criada sempre que um conjunto de linhas é inserido na tabela. As partes são autocontidas no sentido de que incluem todos os metadados necessários para interpretar seu conteúdo sem consultas adicionais a um catálogo central. Para manter baixo o número de partes por tabela, um processo de merge em segundo plano combina periodicamente várias partes menores em uma parte maior até atingir um tamanho de parte configurável (150 GB por padrão). Como as partes são ordenadas pelas colunas da chave primária da tabela (consulte a Seção 3.2), usa-se uma ordenação por intercalação k-way eficiente ^[40] para o merging. As partes de origem são marcadas como inativas e acabam sendo excluídas assim que sua contagem de referências cai para zero, ou seja, quando nenhuma consulta mais as lê.

As linhas podem ser inseridas em dois modos: no modo de inserção síncrona, cada instrução INSERT cria uma nova parte e a adiciona à tabela. Para minimizar a sobrecarga dos merges, recomenda-se que os clientes do banco de dados insiram tuplas em massa, por exemplo, 20.000 linhas de uma só vez. No entanto, atrasos causados pelo batching no lado do cliente costumam ser inaceitáveis quando os dados precisam ser analisados em tempo real. Por exemplo, casos de uso de observabilidade frequentemente envolvem milhares de agentes de monitoramento enviando continuamente pequenas quantidades de dados de eventos e métricas. Esses cenários podem usar o modo de inserção assíncrona, no qual o ClickHouse armazena em buffer linhas de vários INSERTs recebidos na mesma tabela e cria uma nova parte somente depois que o tamanho do buffer excede um limite configurável ou um timeout expira.

Figura 3: Inserts e merges para tabelas com engine MergeTree*.

A Figura 3 ilustra quatro inserts síncronos e dois assíncronos em uma tabela com engine MergeTree*. Dois merges reduziram o número de partes ativas de cinco, inicialmente, para duas.

Em comparação com árvores LSM ^[58] e sua implementação em vários bancos de dados ^{[13, 26, [56]](#page-13-8)}, o ClickHouse trata todas as partes como equivalentes, em vez de organizá-las em uma hierarquia. Como resultado, os merges deixam de ficar limitados a partes no mesmo nível. Como isso também abre mão da ordenação cronológica implícita das partes, são necessários mecanismos alternativos para atualizações e exclusões que não se baseiem em tombstones (consulte a Seção 3.4). O ClickHouse grava inserts diretamente no disco, enquanto outros armazenamentos baseados em árvore LSM normalmente usam write-ahead logging (consulte a Seção 3.7)).

Uma parte corresponde a um diretório em disco, contendo um arquivo para cada coluna. Como otimização, as colunas de uma parte pequena (menor que 10 MB por padrão) são armazenadas consecutivamente em um único arquivo para aumentar a localidade espacial de leituras e gravações. As linhas de uma parte são ainda divididas logicamente em grupos de 8192 registros, chamados grânulos. Um grânulo representa a menor unidade indivisível de dados processada pelos operadores de varredura e lookup de índice no ClickHouse. No entanto, as leituras e gravações de dados em disco não são realizadas no nível do grânulo, mas na granularidade de blocos, que combinam vários grânulos vizinhos dentro de uma coluna. Novos blocos são formados com base em um tamanho, em bytes, configurável por bloco (1 MB por padrão), ou seja, o número de grânulos em um bloco é variável e depende do tipo de dado e da distribuição da coluna. Além disso, os blocos são comprimidos para reduzir seu tamanho e os custos de I/O. Por padrão, o ClickHouse emprega LZ4 ^[75] como algoritmo de compressão de uso geral, mas os usuários também podem especificar codecs especializados, como Gorilla ^[63] ou FPC ^[12], para dados de ponto flutuante. Algoritmos de compressão também podem ser encadeados. Por exemplo, é possível primeiro reduzir a redundância lógica em valores numéricos usando codificação delta ^[23], depois aplicar uma compressão mais pesada e, por fim, criptografar os dados usando um codec AES. Os blocos são descomprimidos dinamicamente quando são carregados do disco para a memória. Para permitir acesso aleatório rápido a grânulos individuais apesar da compressão, o ClickHouse também armazena, para cada coluna, um mapeamento que associa cada id de grânulo ao deslocamento do bloco comprimido que o contém no arquivo da coluna e ao deslocamento do grânulo no bloco descomprimido.

As colunas também podem ser codificadas por dicionário ^{[2, 77, [81]](#page-13-12)} ou tornadas anuláveis usando dois tipos de dados wrapper especiais: LowCardinality(T) substitui os valores originais da coluna por ids inteiros e, assim, reduz significativamente a sobrecarga de armazenamento para dados com poucos valores únicos. Nullable(T) adiciona um bitmap interno à coluna T, indicando se os valores da coluna são NULL ou não.

Por fim, as tabelas podem ser particionadas por intervalo, hash ou round-robin usando expressões de particionamento arbitrárias. Para permitir partition pruning, o ClickHouse também armazena os valores mínimo e máximo da expressão de particionamento para cada partição. Os usuários podem, opcionalmente, criar column statistics mais avançadas (por exemplo, estatísticas de HyperLogLog ^[30] ou t-digest ^[28]) que também fornecem estimativas de cardinalidade.

​

3.2 Poda de dados

Na maioria dos casos de uso, varrer petabytes de dados apenas para responder a uma única consulta é lento e caro demais. O ClickHouse oferece suporte a três técnicas de poda de dados que permitem ignorar a maior parte das linhas durante as buscas e, assim, acelerar significativamente as consultas.

Primeiro, os usuários podem definir um índice de chave primária para uma tabela. As colunas da chave primária determinam a ordem de classificação das linhas dentro de cada parte, ou seja, o índice é clusterizado localmente. Além disso, o ClickHouse armazena, para cada parte, um mapeamento entre os valores da coluna de chave primária da primeira linha de cada grânulo e o id do grânulo, ou seja, o índice é esparso ^[31]. A estrutura de dados resultante normalmente é pequena o suficiente para permanecer inteiramente em memória; por exemplo, apenas 1000 entradas são necessárias para indexar 8,1 milhões de linhas. O principal objetivo de uma chave primária é avaliar predicados de igualdade e de intervalo em colunas filtradas com frequência usando busca binária em vez de varreduras sequenciais (Seção 4.4). A ordenação local também pode ser explorada para mesclagem de partes e otimização de consultas, por exemplo, agregação baseada em ordenação ou remoção de operadores de ordenação do plano físico de execução quando as colunas da chave primária formam um prefixo das colunas de ordenação.

A Figura 4 mostra um índice de chave primária na coluna EventTime para uma tabela com estatísticas de impressões de página. Os grânulos que correspondem ao predicado de intervalo na consulta podem ser encontrados por busca binária no índice de chave primária, em vez de percorrer EventTime sequencialmente.

Figura 4: Avaliação de filtros com um índice de chave primária.

Segundo, os usuários podem criar projeções de tabela, ou seja, versões alternativas de uma tabela que contêm as mesmas linhas ordenadas por uma chave primária diferente ^[71]. As projeções permitem acelerar consultas que filtram por colunas diferentes da chave primária da tabela principal, ao custo de maior sobrecarga para inserções, mesclagens e consumo de espaço. Por padrão, as projeções são preenchidas de forma preguiçosa apenas a partir de partes recém-inseridas na tabela principal, mas não a partir de partes existentes, a menos que o usuário materialize a projeção por completo. O otimizador de consultas escolhe entre ler da tabela principal ou de uma projeção com base nos custos estimados de I/O. Se não existir nenhuma projeção para uma parte, a execução da consulta recorre à parte correspondente da tabela principal.

Terceiro, os índices de skipping oferecem uma alternativa leve às projeções. A ideia dos índices de skipping é armazenar pequenas quantidades de metadados no nível de vários grânulos consecutivos, o que permite evitar a varredura de linhas irrelevantes. Índices de skipping podem ser criados para expressões de índice arbitrárias e com granularidade configurável, ou seja, o número de grânulos em um bloco de índice de skipping. Os tipos de índice de skipping disponíveis incluem: 1. Índices min-max ^[51], que armazenam os valores mínimo e máximo da expressão de índice para cada bloco de índice. Esse tipo de índice funciona bem para dados clusterizados localmente com pequenos intervalos absolutos, por exemplo, dados pouco ordenados. 2. Índices Set, que armazenam um número configurável de valores únicos por bloco de índice. Esses índices são mais adequados para dados com baixa cardinalidade local, ou seja, valores “agrupados”. 3. Índices de filtro de Bloom ^[9] criados para valores de linha, token ou n-gram com uma taxa de falso positivo configurável. Esses índices oferecem suporte à busca textual ^[73], mas, diferentemente dos índices min-max e Set, não podem ser usados para predicados de intervalo ou negativos.

​

3.3 Transformação de dados durante a mesclagem

Casos de uso de inteligência de negócios e observabilidade frequentemente precisam lidar com dados gerados em taxas constantemente altas ou em picos. Além disso, dados gerados recentemente costumam ser mais relevantes para obter insights significativos em tempo real do que dados históricos. Esses casos de uso exigem que os bancos de dados sustentem altas taxas de ingestão de dados enquanto reduzem continuamente o volume de dados históricos por meio de técnicas como agregação ou expiração de dados. O ClickHouse permite a transformação incremental contínua dos dados existentes usando diferentes estratégias de mesclagem. A transformação de dados durante a mesclagem não compromete o desempenho das instruções INSERT, mas não pode garantir que as tabelas nunca contenham valores indesejados (por exemplo, desatualizados ou não agregados). Se necessário, todas as transformações durante a mesclagem podem ser aplicadas no momento da consulta especificando a palavra-chave FINAL em instruções SELECT.

Mesclagens de substituição mantêm apenas a versão de uma tupla inserida mais recentemente, com base no timestamp de criação da parte que a contém; as versões mais antigas são excluídas. As tuplas são consideradas equivalentes se tiverem os mesmos valores nas colunas da chave primária. Para controlar explicitamente qual tupla é preservada, também é possível especificar uma coluna de versão especial para comparação. Mesclagens de substituição são comumente usadas como mecanismo de atualização durante a mesclagem (normalmente em casos de uso em que atualizações são frequentes) ou como alternativa à desduplicação de dados no momento da inserção (Seção 3.5).

Mesclagens de agregação colapsam linhas com os mesmos valores nas colunas da chave primária em uma linha agregada. As colunas que não fazem parte da chave primária devem ser de um estado de agregação parcial que contenha os valores resumidos. Dois estados de agregação parciais, por exemplo, uma soma e uma contagem para avg(), são combinados em um novo estado de agregação parcial. Mesclagens de agregação são normalmente usadas em visões materializadas em vez de tabelas normais. Visões materializadas são preenchidas com base em uma consulta de transformação sobre uma tabela de origem. Ao contrário de outros bancos de dados, o ClickHouse não atualiza visões materializadas periodicamente com todo o conteúdo da tabela de origem. Em vez disso, visões materializadas são atualizadas incrementalmente com o resultado da consulta de transformação quando uma nova parte é inserida na tabela de origem.

A Figura 5 mostra uma visão materializada definida sobre uma tabela com estatísticas de impressões de página. Para novas partes inseridas na tabela de origem, a consulta de transformação calcula as latências máxima e média, agrupadas por região, e insere o resultado em uma visão materializada. As funções de agregação avg() e max() com a extensão -State retornam estados de agregação parciais em vez de resultados finais. Uma mesclagem de agregação definida para a visão materializada combina continuamente estados de agregação parciais em diferentes partes. Para obter o resultado final, os usuários consolidam os estados de agregação parciais na visão materializada usando avg() e max()) com a extensão -Merge.

Figura 5: Mesclagens de agregação em visões materializadas.

Mesclagens TTL (time-to-live) fornecem expiração para dados históricos. Diferentemente das mesclagens de exclusão e agregação, as mesclagens TTL processam apenas uma parte por vez. Mesclagens TTL são definidas em termos de regras com gatilhos e ações. Um gatilho é uma expressão que calcula um timestamp para cada linha, que é comparado com o momento em que a mesclagem TTL é executada. Embora isso permita que os usuários controlem ações na granularidade da linha, verificamos que é suficiente checar se todas as linhas satisfazem uma determinada condição e executar a ação sobre a parte inteira. As ações possíveis incluem 1. mover a parte para outro volume (por exemplo, armazenamento mais barato e mais lento), 2. recomprimir a parte (por exemplo, com um codec mais pesado), 3. excluir a parte e 4. fazer roll-up, isto é, agregar as linhas usando uma chave de agrupamento e funções de agregação.

Como exemplo, considere a definição da tabela de logging na Listagem 1. O ClickHouse moverá partes com valores na coluna de timestamp mais antigos que uma semana para armazenamento de objetos S3 lento, porém barato.

1 CREATE TABLE tab ( ts DateTime , msg String )
2 ENGINE MergeTree PRIMARY KEY ts
3 TTL ( ts + INTERVAL 1 WEEK ) TO VOLUME 's3 '

Listagem 1: Mover a parte para o armazenamento de objetos após uma semana.

​

3.4 Atualizações e Exclusões

O design dos motores de tabela MergeTree* favorece cargas de trabalho append-only, mas alguns casos de uso exigem modificar dados existentes ocasionalmente, por exemplo, para conformidade regulatória. Existem duas abordagens para atualizar ou excluir dados, e nenhuma delas bloqueia inserções paralelas.

Mutações reescrevem todas as partes de uma tabela in-place. Para evitar que uma tabela (exclusão) ou coluna (atualização) dobre temporariamente de tamanho, essa operação não é atômica, ou seja, instruções SELECT paralelas podem ler partes mutadas e não mutadas. As mutações garantem que os dados sejam alterados fisicamente ao final da operação. As mutações de exclusão ainda são caras, pois reescrevem todas as colunas em todas as partes.

Como alternativa, exclusões leves atualizam apenas uma coluna interna de bitmap, indicando se uma linha foi excluída ou não. O ClickHouse acrescenta às consultas SELECT um filtro adicional na coluna de bitmap para excluir as linhas removidas do resultado. As linhas excluídas são removidas fisicamente apenas por mesclagens regulares, em algum momento futuro não especificado. Dependendo da quantidade de colunas, exclusões leves podem ser muito mais rápidas do que mutações, ao custo de SELECTs mais lentos.

Espera-se que operações de atualização e exclusão na mesma tabela sejam raras e serializadas para evitar conflitos lógicos.

​

3.5 Inserções idempotentes

Um problema que ocorre com frequência na prática é como os clientes devem lidar com timeouts de conexão após enviar dados ao servidor para inserção em uma tabela. Nessa situação, é difícil para os clientes determinar se os dados foram inseridos com sucesso ou não. Tradicionalmente, esse problema é resolvido reenviando os dados do cliente para o servidor e contando com a chave primária ou com restrições de unicidade para rejeitar inserts duplicados. Os bancos de dados realizam rapidamente as consultas pontuais necessárias usando estruturas de índice baseadas em árvores binárias ^{[39, [68]](#page-13-16)}, árvores radix ^[45] ou tabelas hash ^[29]. Como essas estruturas de dados indexam cada tupla, sua sobrecarga de espaço e de atualização se torna proibitiva para grandes volumes de dados e altas taxas de ingestão.

O ClickHouse oferece uma alternativa mais leve baseada no fato de que cada insert acaba criando uma parte. Mais especificamente, o servidor mantém hashes das N últimas partes inseridas (por exemplo, N=100) e ignora reinserções de partes com hash conhecido. Os hashes de tabelas não replicadas e replicadas são armazenados localmente e no Keeper, respectivamente. Como resultado, os inserts se tornam idempotentes, ou seja, os clientes podem simplesmente reenviar o mesmo lote de linhas após um timeout e presumir que o servidor cuida da desduplicação. Para ter mais controle sobre o processo de desduplicação, os clientes podem, opcionalmente, fornecer um token de insert que atua como hash da parte. Embora a desduplicação baseada em hash gere uma sobrecarga associada ao cálculo do hash das novas linhas, o custo de armazenar e comparar hashes é insignificante.

​

3.6 Replicação de dados

A replicação é um pré-requisito para alta disponibilidade (tolerância a falhas de nós), mas também é usada para balanceamento de carga e upgrades sem indisponibilidade ^[14]. No ClickHouse, a replicação se baseia no conceito de estados da tabela, que consistem em um conjunto de partes da tabela (Seção 3.1) e metadados da tabela, como nomes de colunas e tipos. Os nós fazem o estado de uma tabela avançar usando três operações: 1. inserções adicionam uma nova parte ao estado, 2. mesclagens adicionam uma nova parte e removem partes existentes do estado, 3. mutações e instruções DDL adicionam partes, e/ou removem partes, e/ou alteram os metadados da tabela, dependendo da operação específica. As operações são executadas localmente em um único nó e registradas como uma sequência de transições de estado em um log global de replicação.

O log de replicação é mantido por um conjunto de, normalmente, três processos do ClickHouse Keeper, que usam o algoritmo de consenso Raft ^[59] para fornecer uma camada de coordenação distribuída e tolerante a falhas para um cluster de nós do ClickHouse. Inicialmente, todos os nós do cluster apontam para a mesma posição no log de replicação. Enquanto os nós executam localmente inserções, mesclagens, mutações e instruções DDL, o log de replicação é reproduzido de forma assíncrona em todos os outros nós. Como resultado, tabelas replicadas são apenas eventualmente consistentes, ou seja, os nós podem temporariamente ler estados antigos da tabela enquanto convergem para o estado mais recente. A maioria das operações mencionadas acima também pode ser executada de forma síncrona até que um quórum de nós (por exemplo, a maioria dos nós ou todos os nós) adote o novo estado.

Como exemplo, a Figura 6 mostra uma tabela replicada inicialmente vazia em um cluster de três nós do ClickHouse. O Nó 1 primeiro recebe duas instruções de inserção e as registra ( 1 2 ) no log de replicação armazenado no conjunto do Keeper. Em seguida, o Nó 2 reproduz a primeira entrada do log buscando-a ( 3 ) e baixando a nova parte do Nó 1 ( 4 ), enquanto o Nó 3 reproduz ambas as entradas do log ( 3 4 5 6 ). Por fim, o Nó 3 faz merge das duas partes em uma nova parte, remove as partes de entrada e registra uma entrada de merge no log de replicação ( 7 ).

Figura 6: Replicação em um cluster de três nós.

Existem três otimizações para acelerar a sincronização: primeiro, novos nós adicionados ao cluster não reproduzem o log de replicação do zero; em vez disso, eles simplesmente copiam o estado do nó que gravou a última entrada do log de replicação. Segundo, as mesclagens são reproduzidas repetindo-as localmente ou buscando a parte resultante em outro nó. O comportamento exato é configurável e permite equilibrar o consumo de CPU e a E/S de rede. Por exemplo, a replicação entre data centers normalmente prefere mesclagens locais para minimizar os custos operacionais. Terceiro, os nós reproduzem em paralelo entradas mutuamente independentes do log de replicação. Isso inclui, por exemplo, fetches de novas partes inseridas consecutivamente na mesma tabela ou operações em tabelas diferentes.

​

3.7 Conformidade com ACID

Para maximizar o desempenho de operações concorrentes de leitura e escrita, o ClickHouse evita ao máximo o uso de travas. As consultas são executadas sobre um snapshot de todas as partes de todas as tabelas envolvidas, criado no início da consulta. Isso garante que novas partes inseridas por INSERTs paralelos ou mesclagens (Seção 3.1) não participem da execução. Para evitar que as partes sejam modificadas ou removidas ao mesmo tempo (Seção 3.4), a contagem de referências das partes processadas é incrementada durante toda a consulta. Formalmente, isso corresponde ao isolamento por snapshot implementado por uma variante de MVCC ^[6] baseada em partes versionadas. Como resultado, as instruções em geral não são compatíveis com ACID, exceto no caso raro em que escritas concorrentes, no momento em que o snapshot é obtido, afetam cada uma apenas uma única parte.

Na prática, a maioria dos casos de uso do ClickHouse com alta intensidade de escrita para tomada de decisão tolera até mesmo um pequeno risco de perda de dados novos em caso de queda de energia. O banco de dados tira proveito disso ao não forçar, por padrão, um commit (fsync) das partes recém-inseridas em disco, permitindo que o kernel agrupe as gravações em lote, ao custo de abrir mão da atomicidade.

​

4 CAMADA DE PROCESSAMENTO DE CONSULTAS

Figura 7: Paralelização entre unidades SIMD, núcleos e nós.

Como ilustrado na Figura 7, o ClickHouse paraleliza consultas no nível dos elementos de dados, dos fragmentos de dados e dos shards da tabela. Vários elementos de dados podem ser processados de uma só vez dentro dos operadores usando instruções SIMD. Em um único nó, a engine de consulta executa operadores simultaneamente em múltiplas threads. O ClickHouse usa o mesmo modelo de vetorização do MonetDB/X100 ^[11], ou seja, os operadores produzem, transferem e consomem múltiplas linhas (fragmentos de dados) em vez de linhas individuais, para minimizar a sobrecarga das chamadas de função virtual. Se uma tabela de origem for dividida em shards distintos, múltiplos nós poderão examinar os shards simultaneamente. Como resultado, todos os recursos de hardware são plenamente utilizados, e o processamento de consultas pode escalar horizontalmente com a adição de nós e verticalmente com a adição de núcleos.

O restante desta seção primeiro descreve, em mais detalhes, o processamento paralelo na granularidade de elementos de dados, fragmentos de dados e shards. Em seguida, apresentamos algumas otimizações importantes para maximizar o desempenho das consultas. Por fim, discutimos como o ClickHouse gerencia recursos compartilhados do sistema na presença de consultas simultâneas.

​

4.1 Paralelização SIMD

A passagem de várias linhas entre operadores cria uma oportunidade para vetorização. A vetorização pode se basear em intrínsecos escritos manualmente ^{[64, [80]](#page-13-19)} ou na autovetorização do compilador ^[25]. O código que se beneficia da vetorização é compilado em diferentes kernels de computação. Por exemplo, o loop interno mais crítico de um operador de consulta pode ser implementado em termos de um kernel não vetorizado, um kernel AVX2 autovetorizado e um kernel AVX-512 vetorizado manualmente. O kernel mais rápido é selecionado em tempo de execução com base na instrução cpuid. Essa abordagem permite que o ClickHouse rode em sistemas com até 15 anos de idade (exigindo SSE 4.2 como requisito mínimo), ao mesmo tempo que ainda oferece ganhos significativos de desempenho em hardware recente.

​

4.2 Paralelização Multicore

Figura 8: Um plano de operadores físicos com três faixas.

O ClickHouse segue a abordagem convencional ^[31] de transformar consultas SQL em um grafo direcionado de operadores do plano físico. A entrada do plano de operadores é representada por operadores source especiais que leem dados no formato nativo ou em qualquer um dos formatos de terceiros compatíveis (consulte a Seção 5). Da mesma forma, um operador sink especial converte o resultado para o formato de saída desejado. O plano de operadores físicos é expandido, no momento da compilação da consulta, em faixas de execução independentes com base em um número máximo configurável de threads de trabalho (por padrão, o número de núcleos) e no tamanho da tabela de origem. As faixas dividem os dados a serem processados por operadores paralelos em intervalos sem sobreposição. Para maximizar as oportunidades de processamento paralelo, as faixas são mescladas o mais tarde possível.

Como exemplo, o quadro do Nó 1 na Figura 8 mostra o grafo de operadores de uma consulta OLAP típica sobre uma tabela com estatísticas de impressões de página. No primeiro estágio, três intervalos distintos da tabela de origem são filtrados simultaneamente. Um operador de exchange Repartition encaminha dinamicamente os fragmentos de resultado entre o primeiro e o segundo estágios para manter as threads de processamento uniformemente ocupadas. As faixas podem ficar desequilibradas após o primeiro estágio se os intervalos examinados tiverem seletividades significativamente diferentes. No segundo estágio, as linhas que passaram pelo filtro são agrupadas por RegionID. Os operadores Aggregate mantêm grupos de resultados locais com RegionID como coluna de agrupamento e uma soma e contagem por grupo como estado parcial de agregação para avg(). Os resultados da agregação local acabam sendo mesclados por um operador GroupStateMerge em um resultado de agregação global. Esse operador também é um pipeline breaker, ou seja, o terceiro estágio só pode começar quando o resultado da agregação tiver sido totalmente calculado. No terceiro estágio, os grupos de resultados são primeiro divididos por um operador de exchange Distribute em três partições distintas de mesmo tamanho, que então são ordenadas por AvgLatency. A ordenação é realizada em três etapas: primeiro, os operadores ChunkSort ordenam os fragmentos individuais de cada partição. Em seguida, os operadores StreamSort mantêm um resultado local ordenado, que é combinado com os fragmentos ordenados recebidos usando ordenação por mesclagem de duas vias. Por fim, um operador MergeSort combina os resultados locais usando ordenação de k vias para obter o resultado final.

Os operadores são máquinas de estado e estão conectados entre si por meio de portas de entrada e saída. Os três estados possíveis de um operador são need-chunk, ready e done. Para passar de need-chunk para ready, um fragmento é colocado na porta de entrada do operador. Para passar de ready para done, o operador processa o fragmento de entrada e gera um fragmento de saída. Para passar de done para need-chunk, o fragmento de saída é removido da porta de saída do operador. A primeira e a terceira transições de estado em dois operadores conectados só podem ser executadas em uma etapa combinada. Operadores source (operadores sink) têm apenas os estados ready e done (need-chunk e done).

As threads de trabalho percorrem continuamente o plano de operadores físicos e executam transições de estado. Para manter os caches da CPU aquecidos, o plano contém indicações de que a mesma thread deve processar operadores consecutivos na mesma faixa. O processamento paralelo acontece tanto horizontalmente entre entradas distintas dentro de um estágio (por exemplo, na Figura 8, os operadores Aggregate são executados de forma concorrente) quanto verticalmente entre estágios não separados por pipeline breakers (por exemplo, na Figura 8, os operadores Filter e Aggregate na mesma faixa podem ser executados simultaneamente). Para evitar sobre e subutilização quando novas consultas começam ou consultas concorrentes terminam, o grau de paralelismo pode ser alterado no meio da consulta entre um e o número máximo de threads de trabalho para a consulta especificado no início da execução (consulte a Seção 4.5)).

Os operadores também podem afetar a execução da consulta em tempo de execução de duas maneiras. Primeiro, os operadores podem criar e conectar dinamicamente novos operadores. Isso é usado principalmente para alternar para algoritmos de agregação externa, ordenação ou junção, em vez de cancelar uma consulta quando o consumo de memória excede um limite configurável. Segundo, os operadores podem solicitar que threads de trabalho passem para uma fila assíncrona. Isso proporciona um uso mais eficiente das threads de trabalho ao aguardar dados remotos.

O mecanismo de execução de consultas do ClickHouse e o paralelismo orientado por morsels ^[44] são semelhantes no sentido de que as lanes normalmente são executadas em núcleos / sockets NUMA diferentes e de que threads de trabalho podem roubar tarefas de outras lanes. Além disso, não há um componente central de escalonamento; em vez disso, as threads de trabalho selecionam suas tarefas individualmente ao percorrer continuamente o plano de operadores. Diferentemente do paralelismo orientado por morsels, o ClickHouse incorpora o grau máximo de paralelismo ao plano e usa faixas muito maiores para particionar a tabela de origem, em comparação com os tamanhos padrão de morsel de aprox. 100.000 linhas. Embora isso possa, em alguns casos, causar bloqueios (por exemplo, quando o tempo de execução dos operadores de filtro em diferentes lanes varia muito), verificamos que o uso generoso de operadores exchange, como Repartition, ao menos evita que esses desequilíbrios se acumulem ao longo dos estágios.

​

4.3 Paralelização em Múltiplos Nós

Se a tabela de origem de uma consulta estiver distribuída em shards, o otimizador de consultas no nó que recebeu a consulta (nó iniciador) tenta executar o máximo possível do trabalho em outros nós. Os resultados desses outros nós podem ser integrados em diferentes pontos do plano da consulta. Dependendo da consulta, os nós remotos podem 1. transmitir colunas brutas da tabela de origem para o nó iniciador, 2. filtrar as colunas de origem e enviar as linhas restantes, 3. executar etapas de filtro e agregação e enviar grupos de resultados locais com estados de agregação parciais, ou 4. executar a consulta inteira, incluindo filtros, agregação e ordenação.

Os nós 2 … N na Figura 8 mostram fragmentos do plano executados em outros nós que armazenam shards da tabela hits. Esses nós filtram e agrupam os dados locais e enviam o resultado ao nó iniciador. O operador GroupStateMerge no nó 1 combina os resultados locais e remotos antes de os grupos de resultados serem finalmente ordenados.

​

4.4 Otimização Holística de Desempenho

Esta seção apresenta otimizações de desempenho importantes aplicadas a diferentes estágios da execução de consultas.

Otimização de consultas. O primeiro conjunto de otimizações é aplicado sobre uma representação semântica da consulta obtida a partir da AST da consulta. Exemplos dessas otimizações incluem constant folding (por exemplo, concat(lower(‘a’),upper(‘b’)) se torna ‘aB’), extração de escalares de certas funções de agregação (por exemplo, sum(a2) se torna 2 * sum(a)), eliminação de subexpressões comuns e transformação de disjunções de filtros de igualdade em listas IN (por exemplo, x=c OR x=d se torna x IN (c,d)). Em seguida, a representação semântica otimizada da consulta é transformada em um plano lógico de operadores. As otimizações sobre o plano lógico incluem pushdown de filtros, reordenação da avaliação de funções e das etapas de ordenação, dependendo de qual delas é estimada como mais custosa. Por fim, o plano lógico da consulta é transformado em um plano físico de operadores. Essa transformação pode explorar as particularidades dos motores de tabela envolvidos. Por exemplo, no caso de um motor de tabela MergeTree, se as colunas de ORDER BY formarem um prefixo da chave primária, os dados podem ser lidos na ordem do disco, e os operadores de ordenação podem ser removidos do plano. Além disso, se as colunas de agrupamento em uma agregação formarem um prefixo da chave primária, o ClickHouse pode usar agregação por ordenação ^[33], isto é, agregar diretamente sequências com o mesmo valor nas entradas pré-ordenadas. Em comparação com a agregação por hash, a agregação por ordenação consome significativamente menos memória, e o valor agregado pode ser passado ao próximo operador imediatamente após o processamento de uma sequência.

Compilação de consultas. O ClickHouse emprega compilação de consultas baseada em LLVM para fundir dinamicamente operadores adjacentes do plano ^{[38, [53]](#page-13-0)}. Por exemplo, a expressão a * b + c + 1 pode ser combinada em um único operador em vez de três operadores. Além de expressões, o ClickHouse também usa compilação para avaliar várias funções de agregação de uma só vez (isto é, para GROUP BY) e para ordenação com mais de uma chave de ordenação. A compilação de consultas reduz o número de chamadas virtuais, mantém os dados em registradores ou caches de CPU e ajuda o preditor de desvios, já que menos código precisa ser executado. Além disso, a compilação em tempo de execução possibilita um amplo conjunto de otimizações, como otimizações lógicas e otimizações peephole implementadas em compiladores, e dá acesso às instruções de CPU mais rápidas disponíveis localmente. A compilação é iniciada apenas quando a mesma expressão regular, de agregação ou de ordenação é executada por diferentes consultas mais do que um número configurável de vezes. Os operadores de consulta compilados são armazenados em cache e podem ser reutilizados por consultas futuras.[7]

Avaliação do índice de chave primária. O ClickHouse avalia condições WHERE usando o índice de chave primária se um subconjunto de cláusulas de filtro na forma normal conjuntiva da condição constituir um prefixo das colunas da chave primária. O índice de chave primária é analisado da esquerda para a direita em intervalos lexicograficamente ordenados de valores de chave. As cláusulas de filtro correspondentes a uma coluna da chave primária são avaliadas usando lógica ternária - todas verdadeiras, todas falsas ou uma mistura de verdadeiro e falso para os valores no intervalo. Neste último caso, o intervalo é dividido em subintervalos, que são analisados recursivamente. Há otimizações adicionais para funções em condições de filtro. Primeiro, as funções têm características que descrevem sua monotonicidade; por exemplo, toDayOfMonth(date) é monotônica por partes dentro de um mês. Essas características de monotonicidade permitem inferir se uma função produz resultados ordenados sobre intervalos ordenados de valores de chave de entrada. Segundo, algumas funções podem calcular a pré-imagem de um determinado resultado de função. Isso é usado para substituir comparações de constantes com chamadas de função nas colunas de chave por comparações do valor da coluna de chave com a pré-imagem. Por exemplo, toYear(k) = 2024 pode ser substituído por k >= 2024-01-01 && k < 2025-01-01.

Data skipping. O ClickHouse tenta evitar leituras de dados em tempo de execução da consulta usando as estruturas de dados apresentadas na Seção 3.2. Além disso, filtros em diferentes colunas são avaliados sequencialmente em ordem decrescente de seletividade estimada, com base em heurísticas e estatísticas de coluna (opcionais). Somente fragmentos de dados que contenham pelo menos uma linha correspondente são passados ao próximo predicado. Isso reduz gradualmente a quantidade de dados lidos e o número de cálculos a serem realizados de predicado para predicado. A otimização só é aplicada quando pelo menos um predicado altamente seletivo está presente; caso contrário, a latência da consulta pioraria em comparação com a avaliação paralela de todos os predicados.

Tabelas hash. As tabelas hash são estruturas de dados fundamentais para agregação e junções hash. Escolher o tipo certo de tabela hash é essencial para o desempenho. O ClickHouse instancia várias tabelas hash (mais de 30 em março de 2024) a partir de um modelo genérico de tabela hash, tendo como pontos de variação a função hash, o alocador, o tipo de célula e a política de redimensionamento. Dependendo do tipo de dado das colunas de agrupamento, da cardinalidade estimada da tabela hash e de outros fatores, a tabela hash mais rápida é selecionada individualmente para cada operador de consulta. Outras otimizações implementadas para tabelas hash incluem:

• um layout em dois níveis com 256 subtabelas (com base no primeiro byte do hash) para dar suporte a conjuntos de chaves enormes,
• tabelas hash de string ^[79] com quatro subtabelas e diferentes funções hash para diferentes comprimentos de string,
• tabelas de lookup que usam a chave diretamente como índice do bucket (isto é, sem hashing) quando há poucas chaves,
• valores com hashes incorporados para resolver colisões mais rapidamente quando a comparação é cara (por exemplo, strings, ASTs),
• criação de tabelas hash com base em tamanhos previstos a partir de estatísticas de execução para evitar redimensionamentos desnecessários,
• alocação de várias tabelas hash pequenas com o mesmo ciclo de vida de criação/destruição em uma única slab de memória,
• limpeza instantânea de tabelas hash para reutilização usando contadores de versão por tabela hash e por célula,
• uso de prefetch de CPU (__builtin_prefetch) para acelerar a recuperação de valores após calcular o hash da chave.

Junções. Como o ClickHouse originalmente oferecia suporte a junções apenas de forma rudimentar, muitos casos de uso recorreram historicamente a tabelas desnormalizadas. Hoje, o banco de dados oferece todos os tipos de join disponíveis em SQL (inner, left- /right/full outer, cross, as-of), bem como diferentes algoritmos de join, como hash join (ingênuo, Grace), sort-merge join e index join para motores de tabela com lookup rápido de chave-valor (geralmente dicionários).

Como as junções estão entre as operações de banco de dados mais caras, é importante oferecer variantes paralelas dos algoritmos clássicos de join, idealmente com trade-offs de espaço/tempo configuráveis. Para junções hash, o ClickHouse implementa o algoritmo não bloqueante de partição compartilhada de ^[7]. Por exemplo, a consulta na Figura 9 calcula como os usuários se movem entre URLs por meio de uma autorjunção em uma tabela de estatísticas de acessos a páginas. A fase de compilação do join é dividida em três vias, cobrindo três intervalos disjuntos da tabela de origem. Em vez de uma tabela hash global, usa-se uma tabela hash particionada. As threads de trabalho (normalmente três) determinam a partição de destino para cada linha de entrada do lado de compilação calculando o módulo de uma função hash. O acesso às partições da tabela hash é sincronizado usando operadores de exchange Gather. A fase de probe encontra de forma semelhante a partição de destino de suas tuplas de entrada. Embora esse algoritmo introduza dois cálculos de hash adicionais por tupla, ele reduz bastante a contenção em latches na fase de compilação, dependendo do número de partições da tabela hash.

Figura 9: Hash join paralelo com três partições de tabela hash.

​

4.5 Isolamento de carga de trabalho

O ClickHouse oferece controle de concorrência, limites de uso de memória e escalonamento de I/O, permitindo que os usuários isolem consultas em classes de carga de trabalho. Ao definir limites para recursos compartilhados (núcleos de CPU, DRAM e I/O de disco e de rede) para classes específicas de carga de trabalho, ele garante que essas consultas não afetem outras consultas críticas para o negócio.

O controle de concorrência evita a superalocação de threads em cenários com um grande número de consultas concorrentes. Mais especificamente, o número de threads de trabalho por consulta é ajustado dinamicamente com base em uma proporção especificada em relação ao número de núcleos de CPU disponíveis.

O ClickHouse rastreia os tamanhos, em bytes, das alocações de memória nos níveis de servidor, usuário e consulta e, assim, permite definir limites flexíveis de uso de memória. O overcommit de memória permite que as consultas usem memória livre adicional além da memória garantida, ao mesmo tempo que assegura limites de memória para outras consultas. Além disso, o uso de memória para cláusulas de agregação, sort e join pode ser limitado, fazendo com que o sistema recorra a algoritmos externos quando o limite de memória for excedido.

Por fim, o escalonamento de I/O permite que os usuários restrinjam acessos a discos locais e remotos para classes de carga de trabalho com base em largura de banda máxima, requisições em andamento e política (por exemplo, FIFO, SFC ^[32]).

​

5 CAMADA DE INTEGRAÇÃO

Aplicações de tomada de decisão em tempo real frequentemente dependem de acesso eficiente e de baixa latência a dados distribuídos em vários locais. Existem duas abordagens para disponibilizar dados externos em um banco de dados OLAP. No acesso a dados baseado em envio, um componente de terceiros faz a ponte entre o banco de dados e armazenamentos de dados externos. Um exemplo disso são ferramentas especializadas de extract-transform-load (ETL), que enviam dados remotos para o sistema de destino. No modelo baseado em extração, o próprio banco de dados se conecta a fontes de dados remotas e extrai dados para consulta em tabelas locais ou exporta dados para sistemas remotos. Embora as abordagens baseadas em envio sejam mais versáteis e comuns, elas implicam maior complexidade arquitetural e um gargalo de escalabilidade. Em contraste, a conectividade remota diretamente no banco de dados oferece recursos interessantes, como junções entre dados locais e remotos, ao mesmo tempo em que mantém a arquitetura geral simples e reduz o tempo para obtenção de insights.

O restante da seção explora métodos de integração de dados baseados em extração no ClickHouse, voltados ao acesso a dados em locais remotos. Observamos que a ideia de conectividade remota em bancos de dados SQL não é nova. Por exemplo, o padrão SQL/MED ^[35], introduzido em 2001 e implementado pelo PostgreSQL desde 2011 ^[65], propõe foreign data wrappers como uma interface unificada para gerenciar dados externos. A máxima interoperabilidade com outros armazenamentos de dados e formatos de armazenamento é um dos objetivos de projeto do ClickHouse. Em março de 2024, o ClickHouse oferece, até onde sabemos, o maior número de opções nativas de integração de dados entre todos os bancos de dados analíticos.

Conectividade externa. O ClickHouse fornece 50+ funções de tabela e motores de integração para conectividade com sistemas externos e locais de armazenamento, incluindo ODBC, MySQL, PostgreSQL, SQLite, Kafka, Hive, MongoDB, Redis, armazenamentos de objetos S3/GCP/Azure e vários lagos de dados. Nós as dividimos ainda mais nas categorias mostradas na figura bônus a seguir (não faz parte do artigo original da VLDB).

Figura bônus: opções de interoperabilidade do ClickBench.

Acesso temporário com funções de tabela de integração. As funções de tabela podem ser invocadas na cláusula FROM de consultas SELECT para ler dados remotos em consultas exploratórias ad hoc. Como alternativa, podem ser usadas para gravar dados em armazenamentos remotos com instruções INSERT INTO TABLE FUNCTION.

Acesso persistente. Existem três métodos para criar conexões permanentes com armazenamentos de dados remotos e sistemas de processamento.

Primeiro, os motores de tabela de integração representam uma fonte de dados remota, como uma tabela MySQL, como uma tabela local persistente. Os usuários armazenam a definição da tabela usando a sintaxe CREATE TABLE AS, combinada com uma consulta SELECT e a função de tabela. É possível especificar um schema personalizado, por exemplo, para referenciar apenas um subconjunto das colunas remotas, ou usar inferência de esquema para determinar automaticamente os nomes das colunas e os tipos equivalentes no ClickHouse. Também distinguimos entre comportamento passivo e ativo em tempo de execução: motores de tabela passivos encaminham consultas ao sistema remoto e preenchem uma tabela proxy local com o resultado. Em contraste, motores de tabela ativos extraem periodicamente dados do sistema remoto ou assinam mudanças remotas, por exemplo, por meio do protocolo de replicação lógica do PostgreSQL. Como resultado, a tabela local contém uma cópia completa da tabela remota.

Segundo, os motores de banco de dados de integração mapeiam todas as tabelas de um schema em um armazenamento de dados remoto para o ClickHouse. Diferentemente do primeiro caso, eles geralmente exigem que o armazenamento de dados remoto seja um banco de dados relacional e, além disso, fornecem suporte limitado a instruções DDL.

Terceiro, dicionários podem ser preenchidos com consultas arbitrárias em praticamente qualquer fonte de dados para a qual exista uma função de tabela ou motor de integração correspondente. O comportamento em tempo de execução é ativo, já que os dados são extraídos em intervalos constantes do armazenamento remoto.

Formatos de dados. Para interagir com sistemas de terceiros, bancos de dados analíticos modernos também devem ser capazes de processar dados em qualquer formato. Além de seu formato nativo, o ClickHouse oferece suporte a 90+ formatos, incluindo CSV, JSON, Parquet, Avro, ORC, Arrow e Protobuf. Cada formato pode ser um formato de entrada (que o ClickHouse pode ler), um formato de saída (que o ClickHouse pode exportar) ou ambos. Alguns formatos voltados a analytics, como Parquet, também são integrados ao processamento de consultas, isto é, o otimizador pode explorar estatísticas incorporadas, e os filtros são avaliados diretamente sobre dados comprimidos.

Interfaces de compatibilidade. Além de seu protocolo wire binário nativo e HTTP, os clientes podem interagir com o ClickHouse por meio de interfaces compatíveis com o wire protocol do MySQL ou PostgreSQL. Esse recurso de compatibilidade é útil para viabilizar o acesso a partir de aplicações proprietárias (por exemplo, certas ferramentas de inteligência de negócios), nas quais os fornecedores ainda não implementaram conectividade nativa com o ClickHouse.

​

6 DESEMPENHO COMO RECURSO

Esta seção apresenta ferramentas integradas para análise de desempenho e avalia o desempenho com consultas de uso real e de benchmark.

​

6.1 Ferramentas integradas de análise de desempenho

Há uma ampla variedade de ferramentas disponível para investigar gargalos de desempenho em consultas individuais ou operações em segundo plano. Os usuários interagem com todas as ferramentas por meio de uma interface uniforme baseada em tabelas de sistema.

Métricas do servidor e da consulta. Estatísticas no nível do servidor, como a contagem de partes ativas, a vazão da rede e as taxas de acerto de cache, são complementadas por estatísticas por consulta, como o número de blocos lidos ou estatísticas de uso de índice. As métricas são calculadas de forma síncrona (mediante solicitação) ou assíncrona, em intervalos configuráveis.

Profiler por amostragem. As pilhas de chamadas das threads do servidor podem ser coletadas usando um profiler por amostragem. Os resultados também podem ser exportados para ferramentas externas, como visualizadores de flamegraph.

Integração com OpenTelemetry. OpenTelemetry é um padrão aberto para rastreamento de linhas de dados em vários sistemas de processamento de dados ^[8]. O ClickHouse pode gerar spans de log do OpenTelemetry com granularidade configurável para todas as etapas do processamento de consultas, bem como coletar e analisar spans de log do OpenTelemetry de outros sistemas.

EXPLAIN da consulta. Como em outros bancos de dados, consultas SELECT podem ser precedidas por EXPLAIN para fornecer insights detalhados sobre a AST de uma consulta, os planos lógicos e físicos dos operadores e o comportamento em tempo de execução.

​

6.2 Benchmarks

Embora a prática de benchmarking tenha sido criticada por não ser realista o suficiente ^{[10, 52, 66, [74]](#page-13-24)}, ela ainda é útil para identificar os pontos fortes e fracos dos bancos de dados. A seguir, discutimos como os benchmarks são usados para avaliar o desempenho do ClickHouse.

​

6.2.1 Tabelas desnormalizadas

Consultas de filtro e agregação em tabelas de fatos desnormalizadas representam historicamente o principal caso de uso do ClickHouse. Apresentamos os tempos de execução do ClickBench, uma carga de trabalho típica desse tipo que simula consultas ad hoc e periódicas de relatórios usadas em análise de clickstream e tráfego. O benchmark consiste em 43 consultas sobre uma tabela com 100 milhões de acessos de página anonimizados, oriundos de uma das maiores plataformas de analytics da web. Um dashboard online ^[17] mostra medições (tempos de execução a frio/com cache aquecido, tempo de importação de dados, tamanho em disco) para mais de 45 bancos de dados comerciais e de pesquisa até junho de 2024. Os resultados são enviados por colaboradores independentes com base no conjunto de dados e nas consultas disponíveis publicamente ^[16]. As consultas testam caminhos de acesso por varredura sequencial e por índice e expõem rotineiramente operadores relacionais limitados por CPU, IO ou memória.

A Figura 10 mostra os tempos de execução relativos totais a frio e com cache aquecido para a execução sequencial de todas as consultas do ClickBench em bancos de dados frequentemente usados para analytics. As medições foram feitas em uma instância AWS EC2 c6a.4xlarge de nó único com 16 vCPUs, 32 GB de RAM e disco de 5000 IOPS / 1000 MiB/s. Sistemas comparáveis foram usados para Redshift (ra3.4xlarge, 12 vCPUs, 96 GB de RAM) e Snowfake (warehouse size S: 2x8 vCPUs, 2x16 GB de RAM). O design físico do banco de dados foi ajustado apenas levemente; por exemplo, especificamos chaves primárias, mas não alteramos a compressão de colunas individuais, não criamos projeções nem índices de skipping. Também limpamos o cache de páginas do Linux antes de cada execução de consulta a frio, mas não ajustamos parâmetros do banco de dados nem do sistema operacional. Para cada consulta, o tempo de execução mais rápido entre os bancos de dados é usado como linha de base. Os tempos de execução relativos das consultas para outros bancos de dados são calculados como ( + 10)/(_ + 10). O tempo de execução relativo total de um banco de dados é a média geométrica das razões por consulta. Embora o banco de dados de pesquisa Umbra ^[54] alcance o melhor tempo de execução geral com cache aquecido, o ClickHouse supera todos os outros bancos de dados de nível de produção tanto em execuções com cache aquecido quanto a frio.

Figura 10: Tempos de execução relativos a frio e com cache aquecido do ClickBench.

Para acompanhar, ao longo do tempo, o desempenho de SELECTs em cargas de trabalho mais diversas, usamos uma combinação de quatro benchmarks chamada VersionsBench ^[19]. Esse benchmark é executado uma vez por mês quando um novo lançamento é publicado, para avaliar seu desempenho ^[20] e identificar alterações de código que possam tê-lo degradado: os benchmarks individuais incluem: 1. ClickBench (descrito acima), 2. 15 consultas do MgBench ^[21], 3. 13 consultas sobre uma tabela de fatos desnormalizada do Star Schema Benchmark ^[57] com 600 milhões de linhas. 4. 4 consultas sobre NYC Taxi Rides com 3,4 bilhões de linhas ^[70].

A Figura 11 mostra a evolução dos tempos de execução do VersionsBench para 77 versões do ClickHouse entre março de 2018 e março de 2024. Para compensar as diferenças no tempo de execução relativo de consultas individuais, normalizamos os tempos de execução usando uma média geométrica, com a razão em relação ao menor tempo de execução de cada consulta entre todas as versões como peso. O desempenho do VersionsBench melhorou 1,72 × nos últimos seis anos. As datas dos lançamentos com suporte de longo prazo (LTS) estão marcadas no eixo x. Embora o desempenho tenha se deteriorado temporariamente em alguns períodos, os lançamentos LTS em geral têm desempenho comparável ou melhor do que a versão LTS anterior. A melhora significativa em agosto de 2022 foi causada pela técnica de avaliação de filtros coluna por coluna descrita na Seção 4.4.

Figura 11: tempos de execução relativos com cache aquecido do VersionsBench 2018-2024.

​

6.2.2 Tabelas normalizadas

No data warehousing clássico, os dados costumam ser modelados com esquemas estrela ou snowfake. Apresentamos os tempos de execução de consultas TPC-H (scale factor 100), mas observamos que tabelas normalizadas são um caso de uso emergente para o ClickHouse. A Figura 12 mostra os tempos de execução com cache aquecido das consultas TPC-H com base no algoritmo de hash join paralelo descrito na Seção 4.4. As medições foram realizadas em uma única instância AWS EC2 c6i.16xlarge com 64 vCPUs, 128 GB de RAM e disco de 5000 IOPS / 1000 MiB/s. Foi registrado o mais rápido entre cinco testes. Como referência, realizamos as mesmas medições em um sistema Snowfake de tamanho comparável (warehouse size L, 8x8 vCPUs, 8x16 GB de RAM). Os resultados de onze consultas foram excluídos da tabela: as consultas Q2, Q4, Q13, Q17 e Q20-22 incluem subconsultas correlacionadas, que ainda não têm suporte no ClickHouse v24.6. As consultas Q7-Q9 e Q19 dependem de otimizações estendidas no nível do plano para junções, como reordenação de junções e pushdown de predicados de join (ambas ausentes no ClickHouse v24.6), para alcançar tempos de execução viáveis. A descorrelação automática de subconsultas e um melhor suporte do otimizador para junções estão planejados para implementação em 2024 ^[18]. Das 11 consultas restantes, 5 (6) foram executadas mais rapidamente no ClickHouse (Snowfake). Como as otimizações mencionadas são reconhecidamente críticas para o desempenho ^[27], esperamos que, quando implementadas, melhorem ainda mais os tempos de execução dessas consultas.

Figura 12: Tempos de execução com cache aquecido (em segundos) para consultas TPC-H.

​

7 TRABALHOS RELACIONADOS

Bancos de dados analíticos têm despertado grande interesse acadêmico e comercial nas últimas décadas ^[1]. Sistemas iniciais como Sybase IQ ^[48], Teradata ^[72], Vertica ^[42] e Greenplum ^[47] eram caracterizados por jobs de ETL em lote caros e elasticidade limitada devido à sua natureza on-premise. No início da década de 2010, o surgimento de data warehouses nativos da nuvem e de ofertas de banco de dados como serviço (DBaaS), como Snowfake ^[22], BigQuery ^[49] e Redshift ^[4], reduziu drasticamente o custo e a complexidade das análises para organizações, ao mesmo tempo em que se beneficiavam de alta disponibilidade e dimensionamento automático de recursos. Mais recentemente, kernels de execução analítica (por exemplo, Photon ^[5] e Velox ^[62]) oferecem processamento de dados reutilizável para uso em diferentes aplicações analíticas, de streaming e de aprendizado de máquina.

Os bancos de dados mais semelhantes ao ClickHouse, em termos de objetivos e princípios de projeto, são Druid ^[78] e Pinot ^[34]. Ambos os sistemas são voltados para analytics em tempo real com altas taxas de ingestão de dados. Assim como no ClickHouse, as tabelas são divididas em partes horizontais chamadas segmentos. Enquanto o ClickHouse mescla continuamente partes menores e, opcionalmente, reduz volumes de dados usando as técnicas da Seção 3.3, as partes permanecem imutáveis para sempre no Druid e no Pinot. Além disso, Druid e Pinot exigem nós especializados para criar, modificar e consultar tabelas, enquanto o ClickHouse usa um binário monolítico para essas tarefas.

Snowfake ^[22] é um popular data warehouse proprietário na Cloud baseado em uma arquitetura de disco compartilhado. Sua abordagem de dividir tabelas em micropartições é semelhante ao conceito de partes no ClickHouse. Snowfake usa páginas PAX híbridas ^[3] para persistência, enquanto o formato de armazenamento do ClickHouse é estritamente colunar. Snowfake também enfatiza cache local e poda de dados usando índices leves criados automaticamente ^{[31, [51]](#page-13-14)} como base para um bom desempenho. De forma semelhante às chaves primárias no ClickHouse, os usuários podem opcionalmente criar índices clusterizados para co-localizar dados com os mesmos valores.

Photon ^[5] e Velox ^[62] são motores de execução de consultas projetados para serem usados como componentes em sistemas complexos de gerenciamento de dados. Ambos os sistemas recebem planos de consulta como entrada, que então são executados no nó local sobre arquivos Parquet (Photon) ou Arrow (Velox) ^[46]. O ClickHouse é capaz de consumir e gerar dados nesses formatos genéricos, mas prefere seu formato de arquivo nativo para armazenamento. Embora Velox e Photon não otimizem o plano de consulta (o Velox realiza otimizações básicas de expressões), eles utilizam técnicas adaptativas em tempo de execução, como alternar dinamicamente kernels de processamento dependendo das características dos dados. De forma semelhante, operadores do plano no ClickHouse

podem criar outros operadores em tempo de execução, principalmente para alternar para operadores de agregação externa ou join, com base no consumo de memória da consulta. O artigo do Photon observa que projetos com geração de código ^{[38, 41, [53]](#page-13-0)} são mais difíceis de desenvolver e depurar do que projetos vetorizados interpretados ^[11]. O suporte (experimental) à geração de código no Velox compila e vincula uma biblioteca compartilhada produzida a partir de código C++ gerado em tempo de execução, enquanto o ClickHouse interage diretamente com a API de compilação sob demanda do LLVM.

DuckDB ^[67] também foi projetado para ser incorporado por um processo hospedeiro, mas, além disso, oferece otimização de consultas e transações. Ele foi desenvolvido para consultas OLAP combinadas com instruções OLTP ocasionais. Assim, o DuckDB escolheu o formato de armazenamento DataBlocks ^[43], que emprega métodos de compressão leves, como dicionários que preservam a ordem ou frame-of-reference ^[2], para obter bom desempenho em workloads híbridos. Em contraste, o ClickHouse é otimizado para casos de uso append-only, isto é, sem atualizações e exclusões, ou com elas apenas raramente. Os blocos são comprimidos com técnicas mais pesadas, como LZ4, partindo do pressuposto de que os usuários fazem uso extensivo de pruning de dados para acelerar consultas frequentes e de que os custos de I/O superam os custos de descompressão nas consultas restantes. O DuckDB também oferece transações serializáveis baseadas no esquema MVCC do Hyper ^[55], enquanto o ClickHouse oferece apenas isolamento por snapshot.

​

8 CONCLUSÃO E PERSPECTIVAS

Apresentamos a arquitetura do ClickHouse, um banco de dados OLAP de código aberto e alto desempenho. Com uma camada de armazenamento otimizada para gravação e um mecanismo vetorizado de consultas de última geração em sua base, o ClickHouse viabiliza analytics em tempo real sobre conjuntos de dados na escala de petabytes, com altas taxas de ingestão. Ao mesclar e transformar dados de forma assíncrona em segundo plano, o ClickHouse desacopla com eficiência a manutenção dos dados das inserções paralelas. Sua camada de armazenamento permite uma poda agressiva de dados usando índices primários esparsos, índices de skipping e tabelas de projeção. Descrevemos a implementação, no ClickHouse, de atualizações e exclusões, inserções idempotentes e replicação de dados entre nós para alta disponibilidade. A camada de processamento de consultas otimiza as consultas com uma ampla variedade de técnicas e paraleliza a execução em todos os recursos do servidor e do cluster. Motores de tabela de integração e funções oferecem uma forma conveniente de interagir com outros sistemas de gerenciamento e formatos de dados de maneira transparente. Por meio de benchmarks, demonstramos que o ClickHouse está entre os bancos de dados analíticos mais rápidos do mercado e mostramos melhorias significativas no desempenho de consultas típicas em implantações reais do ClickHouse ao longo dos anos.

Todos os recursos e aprimoramentos planejados para 2024 podem ser encontrados no roadmap público ^[18]. As melhorias planejadas incluem suporte a transações de usuário, PromQL ^[69] como linguagem de consulta alternativa, um novo tipo de dado para dados semi-estruturados (por exemplo, JSON), melhores otimizações de junções no nível do plano, bem como uma implementação de atualizações leves para complementar exclusões leves.

​

AGRADECIMENTOS

A partir da versão 24.6, SELECT * FROM system.contributors retorna 1994 pessoas que contribuíram para ClickHouse. Gostaríamos de agradecer a toda a equipe de engenharia da ClickHouse Inc. e à incrível comunidade de código aberto do ClickHouse pelo trabalho árduo e pela dedicação na construção conjunta deste banco de dados.

​

REFERÊNCIAS

• ¹ Daniel Abadi, Peter Boncz, Stavros Harizopoulos, Stratos Idreaos e Samuel Madden. 2013. The Design and Implementation of Modern Column-Oriented Database Systems. https://doi.org/10.1561/9781601987556
• ² Daniel Abadi, Samuel Madden e Miguel Ferreira. 2006. Integrating Compression and Execution in Column-Oriented Database Systems. Nos anais da 2006 ACM SIGMOD International Conference on Management of Data (SIGMOD ‘06). 671–682.https://doi.org/10.1145/1142473.1142548
• ³ Anastassia Ailamaki, David J. DeWitt, Mark D. Hill e Marios Skounakis. 2001. Weaving Relations for Cache Performance. Nos anais da 27ª International Conference on Very Large Data Bases (VLDB ‘01). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 169–180.
• ⁴ Nikos Armenatzoglou, Sanuj Basu, Naga Bhanoori, Mengchu Cai, Naresh Chainani, Kiran Chinta, Venkatraman Govindaraju, Todd J. Green, Monish Gupta, Sebastian Hillig, Eric Hotinger, Yan Leshinksy, Jintian Liang, Michael McCreedy, Fabian Nagel, Ippokratis Pandis, Panos Parchas, Rahul Pathak, Orestis Polychroniou, Foyzur Rahman, Gaurav Saxena, Gokul Soundararajan, Sriram Subramanian e Doug Terry. 2022. Amazon Redshift Re-Invented. Em anais da 2022 International Conference on Management of Data (Philadelphia, PA, EUA) (SIGMOD ‘22). Association for Computing Machinery, New York, NY, EUA, 2205–2217. https://doi.org/10.1145/3514221.3526045
• ⁵ Alexander Behm, Shoumik Palkar, Utkarsh Agarwal, Timothy Armstrong, David Cashman, Ankur Dave, Todd Greenstein, Shant Hovsepian, Ryan Johnson, Arvind Sai Krishnan, Paul Leventis, Ala Luszczak, Prashanth Menon, Mostafa Mokhtar, Gene Pang, Sameer Paranjpye, Greg Rahn, Bart Samwel, Tom van Bussel, Herman van Hovell, Maryann Xue, Reynold Xin e Matei Zaharia. 2022. Photon: A Fast Query Engine for Lakehouse Systems (SIGMOD ‘22). Association for Computing Machinery, New York, NY, USA, 2326–2339. https://doi.org/10.1145/3514221. 3526054
• ⁶ Philip A. Bernstein and Nathan Goodman. 1981. Concurrency Control in Distributed Database Systems. ACM Computing Survey 13, 2 (1981), 185–221. https://doi.org/10.1145/356842.356846
• ⁷ Spyros Blanas, Yinan Li e Jignesh M. Patel. 2011. Projeto e avaliação de algoritmos de hash join em memória principal para CPUs multicore. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data (Athens, Greece) (SIGMOD ‘11). Association for Computing Machinery, New York, NY, USA, 37–48. https://doi.org/10.1145/1989323.1989328
• ⁸ Daniel Gomez Blanco. 2023. Practical OpenTelemetry. Springer Nature.
• ⁹ Burton H. Bloom. 1970. Space/Time Trade-Ofs in Hash Coding with Allowable Errors. Commun. ACM 13, 7 (1970), 422–426. https://doi.org/10.1145/362686. 362692
• ¹⁰ Peter Boncz, Thomas Neumann, and Orri Erling. 2014. TPC-H Analyzed: Hidden Messages and Lessons Learned from an Infuential Benchmark. In Performance Characterization and Benchmarking. 61–76. https://doi.org/10.1007/978-3-319- 04936-6_5
• ¹¹ Peter Boncz, Marcin Zukowski e Niels Nes. 2005. MonetDB/X100: Hyper-Pipelining Query Execution. Em CIDR.
• ¹² Martin Burtscher e Paruj Ratanaworabhan. 2007. High Throughput Compression of Double-Precision Floating-Point Data. Na Data Compression Conference (DCC). 293–302. https://doi.org/10.1109/DCC.2007.44
• ¹³ Jef Carpenter e Eben Hewitt. 2016. Cassandra: The Defnitive Guide (2ª ed.). O’Reilly Media, Inc.
• ¹⁴ Bernadette Charron-Bost, Fernando Pedone e André Schiper (Orgs.). 2010. Replication: Theory and Practice. Springer-Verlag.
• ¹⁵ chDB. 2024. chDB - um mecanismo SQL OLAP embutido. Recuperado em 2024-06-20 de https://github.com/chdb-io/chdb
• ¹⁶ ClickHouse. 2024. ClickBench: um benchmark para bancos de dados analíticos. Acessado em 2024-06-20 de https://github.com/ClickHouse/ClickBench
• ¹⁷ ClickHouse. 2024. ClickBench: Comparative Measurements. Recuperado em 2024-06-20 de https://benchmark.clickhouse.com
• ¹⁸ ClickHouse. 2024. Roadmap do ClickHouse 2024 (GitHub). Acessado em 2024-06-20 em https://github.com/ClickHouse/ClickHouse/issues/58392
• ¹⁹ ClickHouse. 2024. Benchmark de versões do ClickHouse. Obtido em 2024-06-20 em https://github.com/ClickHouse/ClickBench/tree/main/versions
• ²⁰ ClickHouse. 2024. Resultados do benchmark de versões do ClickHouse. Acesso em 2024-06-20 em https://benchmark.clickhouse.com/versions/
• ²¹ Andrew Crotty. 2022. MgBench. Obtido em 2024-06-20 de https://github.com/ andrewcrotty/mgbench
• ²² Benoit Dageville, Thierry Cruanes, Marcin Zukowski, Vadim Antonov, Artin Avanes, Jon Bock, Jonathan Claybaugh, Daniel Engovatov, Martin Hentschel, Jiansheng Huang, Allison W. Lee, Ashish Motivala, Abdul Q. Munir, Steven Pelley, Peter Povinec, Greg Rahn, Spyridon Triantafyllis e Philipp Unterbrunner. 2016. The Snowfake Elastic Data Warehouse. In Proceedings of the 2016 International Conference on Management of Data (San Francisco, California, USA) (SIGMOD ‘16). Association for Computing Machinery, New York, NY, USA, 215–226. https: //doi.org/10.1145/2882903.2903741
• ²³ Patrick Damme, Annett Ungethüm, Juliana Hildebrandt, Dirk Habich e Wolfgang Lehner. 2019. From a Comprehensive Experimental Survey to a Cost-Based Selection Strategy for Lightweight Integer Compression Algorithms. ACM Trans. Database Syst. 44, 3, Artigo 9 (2019), 46 páginas. https://doi.org/10.1145/3323991
• ²⁴ Philippe Dobbelaere e Kyumars Sheykh Esmaili. 2017. Kafka versus RabbitMQ: um estudo comparativo de duas implementações de publicação/assinatura de referência do setor: artigo industrial (DEBS ‘17). Association for Computing Machinery, New York, NY, USA, 227–238. https://doi.org/10.1145/3093742.3093908
• ²⁵ Documentação do LLVM. 2024. Auto-Vectorization in LLVM. Acessado em 2024-06-20 em https://llvm.org/docs/Vectorizers.html
• ²⁶ Siying Dong, Andrew Kryczka, Yanqin Jin e Michael Stumm. 2021. RocksDB: Evolução das prioridades de desenvolvimento em um armazenamento chave-valor que atende aplicações em larga escala. ACM Transactions on Storage 17, 4, Artigo 26 (2021), 32 páginas. https://doi.org/10.1145/3483840
• ²⁷ Markus Dreseler, Martin Boissier, Tilmann Rabl e Matthias Ufacker. 2020. Quantificando os pontos de estrangulamento do TPC-H e suas otimizações. Proc. VLDB Endow. 13, 8 (2020), 1206–1220. https://doi.org/10.14778/3389133.3389138
• ²⁸ Ted Dunning. 2021. O t-digest: estimativas eficientes para distribuições. Software Impacts 7 (2021). https://doi.org/10.1016/j.simpa.2020.100049
• ²⁹ Martin Faust, Martin Boissier, Marvin Keller, David Schwalb, Holger Bischof, Katrin Eisenreich, Franz Färber e Hasso Plattner. 2016. Footprint Reduction and Uniqueness Enforcement with Hash Indices in SAP HANA. Em Database and Expert Systems Applications. 137–151. https://doi.org/10.1007/978-3-319-44406- 2_11
• ³⁰ Philippe Flajolet, Eric Fusy, Olivier Gandouet e Frederic Meunier. 2007. HyperLogLog: a análise de um algoritmo de estimativa de cardinalidade quase ótimo. Em AofA: Analysis of Algorithms, Vol. DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07). Discrete Mathematics and Theoretical Computer Science, 137–156. https://doi.org/10.46298/dmtcs.3545
• ³¹ Hector Garcia-Molina, Jefrey D. Ullman e Jennifer Widom. 2009. Database Systems - The Complete Book (2. ed.).
• ³² Pawan Goyal, Harrick M. Vin e Haichen Chen. 1996. Start-time fair queueing: a scheduling algorithm for integrated services packet switching networks. 26, 4 (1996), 157–168. https://doi.org/10.1145/248157.248171
• ³³ Goetz Graefe. 1993. Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25, 2 (1993), 73–169. https://doi.org/10.1145/152610.152611
• ³⁴ Jean-François Im, Kishore Gopalakrishna, Subbu Subramaniam, Mayank Shrivastava, Adwait Tumbde, Xiaotian Jiang, Jennifer Dai, Seunghyun Lee, Neha Pawar, Jialiang Li e Ravi Aringunram. 2018. Pinot: OLAP em tempo real para 530 milhões de usuários. In Proceedings of the 2018 International Conference on Management of Data (Houston, TX, USA) (SIGMOD ‘18). Association for Computing Machinery, New York, NY, USA, 583–594. https://doi.org/10.1145/3183713.3190661
• ³⁵ ISO/IEC 9075-9:2001 2001. Tecnologia da informação — Linguagem de banco de dados — SQL — Parte 9: Gerenciamento de dados externos (SQL/MED). Norma. International Organization for Standardization.
• ³⁶ Paras Jain, Peter Kraft, Conor Power, Tathagata Das, Ion Stoica e Matei Zaharia. 2023. Analyzing and Comparing Lakehouse Storage Systems. CIDR.
• ³⁷ Project Jupyter. 2024. Jupyter Notebooks. Acessado em 2024-06-20 em https: //jupyter.org/
• ³⁸ Timo Kersten, Viktor Leis, Alfons Kemper, Thomas Neumann, Andrew Pavlo e Peter Boncz. 2018. Everything You Always Wanted to Know about Compiled and Vectorized Queries but Were Afraid to Ask. Proc. VLDB Endow. 11, 13 (set. 2018), 2209–2222. https://doi.org/10.14778/3275366.3284966
• ³⁹ Changkyu Kim, Jatin Chhugani, Nadathur Satish, Eric Sedlar, Anthony D. Nguyen, Tim Kaldewey, Victor W. Lee, Scott A. Brandt e Pradeep Dubey. 2010. FAST: fast architecture sensitive tree search on modern CPUs and GPUs. Nos anais da 2010 ACM SIGMOD International Conference on Management of Data (Indianapolis, Indiana, USA) (SIGMOD ‘10). Association for Computing Machinery, New York, NY, USA, 339–350. https://doi.org/10.1145/1807167.1807206
• ⁴⁰ Donald E. Knuth. 1973. The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley.
• ⁴¹ André Kohn, Viktor Leis, e Thomas Neumann. 2018. Adaptive Execution of Compiled Queries. Em 2018 IEEE 34th International Conference on Data Engineering (ICDE). 197–208. https://doi.org/10.1109/ICDE.2018.00027
• ⁴² Andrew Lamb, Matt Fuller, Ramakrishna Varadarajan, Nga Tran, Ben Vandiver, Lyric Doshi e Chuck Bear. 2012. The Vertica Analytic Database: C-Store 7 Years Later. Proc. VLDB Endow. 5, 12 (aug 2012), 1790–1801. https://doi.org/10. 14778/2367502.2367518
• ⁴³ Harald Lang, Tobias Mühlbauer, Florian Funke, Peter A. Boncz, Thomas Neumann e Alfons Kemper. 2016. Data Blocks: Hybrid OLTP and OLAP on Compressed Storage using both Vectorization and Compilation. In Proceedings of the 2016 International Conference on Management of Data (San Francisco, California, USA) (SIGMOD ‘16). Association for Computing Machinery, New York, NY, USA, 311–326. https://doi.org/10.1145/2882903.2882925
• ⁴⁴ Viktor Leis, Peter Boncz, Alfons Kemper e Thomas Neumann. 2014. Morseldriven parallelism: a NUMA-aware query evaluation framework for the manycore age. In Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data (Snowbird, Utah, USA) (SIGMOD ‘14). Association for Computing Machinery, New York, NY, USA, 743–754. https://doi.org/10.1145/2588555. 2610507
• ⁴⁵ Viktor Leis, Alfons Kemper e Thomas Neumann. 2013. A árvore radix adaptativa: indexação ARTful para bancos de dados em memória. Em 2013 IEEE 29th International Conference on Data Engineering (ICDE). 38–49. https://doi.org/10.1109/ICDE. 2013.6544812
• ⁴⁶ Chunwei Liu, Anna Pavlenko, Matteo Interlandi e Brandon Haynes. 2023. Uma análise aprofundada sobre formatos abertos comuns para SGBDs analíticos. 16, 11 (jul 2023), 3044–3056. https://doi.org/10.14778/3611479.3611507
• ⁴⁷ Zhenghua Lyu, Huan Hubert Zhang, Gang Xiong, Gang Guo, Haozhou Wang, Jinbao Chen, Asim Praveen, Yu Yang, Xiaoming Gao, Alexandra Wang, Wen Lin, Ashwin Agrawal, Junfeng Yang, Hao Wu, Xiaoliang Li, Feng Guo, Jiang Wu, Jesse Zhang, e Venkatesh Raghavan. 2021. Greenplum: um banco de dados híbrido para cargas de trabalho transacionais e analíticas (SIGMOD ‘21). Association for Computing Machinery, New York, NY, USA, 2530–2542. https: //doi.org/10.1145/3448016.3457562
• ⁴⁸ Roger MacNicol e Blaine French. 2004. Sybase IQ Multiplex - Projetado para análise. Nos Anais da Trigésima Conferência Internacional sobre Bancos de Dados Muito Grandes - Volume 30 (Toronto, Canadá) (VLDB ‘04). VLDB Endowment, 1227–1230.
• ⁴⁹ Sergey Melnik, Andrey Gubarev, Jing Jing Long, Geofrey Romer, Shiva Shivakumar, Matt Tolton, Theo Vassilakis, Hossein Ahmadi, Dan Delorey, Slava Min, Mosha Pasumansky e Jef Shute. 2020. Dremel: A Decade of Interactive SQL Analysis at Web Scale. Proc. VLDB Endow. 13, 12 (aug 2020), 3461–3472. https://doi.org/10.14778/3415478.3415568
• ⁵⁰ Microsoft. 2024. Kusto Query Language. Recuperado em 2024-06-20 de https: //github.com/microsoft/Kusto-Query-Language
• ⁵¹ Guido Moerkotte. 1998. Pequenos agregados materializados: uma estrutura leve de índice para armazenamento de dados. Em Anais da 24ª Conferência Internacional sobre Bancos de Dados Muito Grandes (VLDB ‘98). 476–487.
• ⁵² Jalal Mostafa, Sara Wehbi, Suren Chilingaryan e Andreas Kopmann. 2022. SciTS: A Benchmark for Time-Series Databases in Scientifc Experiments and Industrial Internet of Things. Nos anais da 34th International Conference on Scientifc and Statistical Database Management (SSDBM ‘22). Artigo 12. https: //doi.org/10.1145/3538712.3538723
• ⁵³ Thomas Neumann. 2011. Compilando planos de consulta com eficiência para hardware moderno. Proc. VLDB Endow. 4, 9 (jun 2011), 539–550. https://doi.org/10.14778/ 2002938.2002940
• ⁵⁴ Thomas Neumann e Michael J. Freitag. 2020. Umbra: um sistema baseado em disco com desempenho em memória. In: 10th Conference on Innovative Data Systems Research, CIDR 2020, Amsterdam, Holanda, 12 a 15 de janeiro de 2020, anais online. www.cidrdb.org. http://cidrdb.org/cidr2020/papers/p29-neumanncidr20.pdf
• ⁵⁵ Thomas Neumann, Tobias Mühlbauer e Alfons Kemper. 2015. Controle de Concorrência Multi-Versão Serializável Rápido para Sistemas de Bancos de Dados em Memória Principal. In Anais da Conferência Internacional ACM SIGMOD de 2015 sobre Gerenciamento de Dados (Melbourne, Victoria, Austrália) (SIGMOD ‘15). Association for Computing Machinery, New York, NY, EUA, 677–689. https://doi.org/10.1145/2723372. 2749436
• ⁵⁶ LevelDB no GitHub. 2024. LevelDB. Acessado em 2024-06-20 em https://github. com/google/leveldb
• ⁵⁷ Patrick O’Neil, Elizabeth O’Neil, Xuedong Chen e Stephen Revilak. 2009. The Star Schema Benchmark and Augmented Fact Table Indexing. In: Performance Evaluation and Benchmarking. Springer Berlin Heidelberg, 237–252. https: //doi.org/10.1007/978-3-642-10424-4_17
• ⁵⁸ Patrick E. O’Neil, Edward Y. C. Cheng, Dieter Gawlick, e Elizabeth J. O’Neil. 1996. The log-structured Merge-Tree (LSM-tree). Acta Informatica 33 (1996), 351–385. https://doi.org/10.1007/s002360050048
• ⁵⁹ Diego Ongaro e John Ousterhout. 2014. Em busca de um algoritmo de consenso compreensível. Nos Anais da Conferência Técnica Anual da USENIX de 2014 (USENIX ATC’14). 305–320. https://doi.org/doi/10. 5555/2643634.2643666
• ⁶⁰ Patrick O’Neil, Edward Cheng, Dieter Gawlick e Elizabeth O’Neil. 1996. The Log-Structured Merge-Tree (LSM-Tree). Acta Inf. 33, 4 (1996), 351–385. https: //doi.org/10.1007/s002360050048
• ⁶¹ Pandas. 2024. DataFrames do Pandas. Recuperado em 2024-06-20 de https://pandas. pydata.org/
• ⁶² Pedro Pedreira, Orri Erling, Masha Basmanova, Kevin Wilfong, Laith Sakka, Krishna Pai, Wei He, e Biswapesh Chattopadhyay. 2022. Velox: Meta’s Unified Execution Engine. Proc. VLDB Endow. 15, 12 (ago 2022), 3372–3384. https: //doi.org/10.14778/3554821.3554829
• ⁶³ Tuomas Pelkonen, Scott Franklin, Justin Teller, Paul Cavallaro, Qi Huang, Justin Meza e Kaushik Veeraraghavan. 2015. Gorilla: A Fast, Scalable, in-Memory Time Series Database. Proceedings of the VLDB Endowment 8, 12 (2015), 1816–1827. https://doi.org/10.14778/2824032.2824078
• ⁶⁴ Orestis Polychroniou, Arun Raghavan e Kenneth A. Ross. 2015. Rethinking SIMD Vectorization for In-Memory Databases. Nos Anais da 2015 ACM SIGMOD International Conference on Management of Data (SIGMOD ‘15). 1493–1508. https://doi.org/10.1145/2723372.2747645
• ⁶⁵ PostgreSQL. 2024. PostgreSQL - Foreign Data Wrappers. Acesso em 2024-06-20 em https://wiki.postgresql.org/wiki/Foreign&#95;data&#95;wrappers
• ⁶⁶ Mark Raasveldt, Pedro Holanda, Tim Gubner e Hannes Mühleisen. 2018. Fair Benchmarking Considered difficult: Common Pitfalls In Database Performance Testing. Nos anais do Workshop on Testing Database Systems (Houston, TX, USA) (DBTest’18). Artigo 2, 6 páginas. https://doi.org/10.1145/3209950.3209955
• ⁶⁷ Mark Raasveldt e Hannes Mühleisen. 2019. DuckDB: An Embeddable Analytical Database (SIGMOD ‘19). Association for Computing Machinery, New York, NY, EUA, 1981–1984. https://doi.org/10.1145/3299869.3320212
• ⁶⁸ Jun Rao and Kenneth A. Ross. 1999. Cache Conscious Indexing for Decision-Support in Main Memory. In Proceedings of the 25th International Conference on Very Large Data Bases (VLDB ‘99). San Francisco, CA, USA, 78–89.
• ⁶⁹ Navin C. Sabharwal and Piyush Kant Pandey. 2020. Working with Prometheus Query Language (PromQL). In Monitoring Microservices and Containerized Applications. https://doi.org/10.1007/978-1-4842-6216-0&#95;5
• ⁷⁰ Todd W. Schneider. 2022. Dados de Táxis e Veículos de Aluguel da Cidade de Nova York. Recuperado em 2024-06-20 de https://github.com/toddwschneider/nyc-taxi-data
• ⁷¹ Mike Stonebraker, Daniel J. Abadi, Adam Batkin, Xuedong Chen, Mitch Cherniack, Miguel Ferreira, Edmond Lau, Amerson Lin, Sam Madden, Elizabeth O’Neil, Pat O’Neil, Alex Rasin, Nga Tran, e Stan Zdonik. 2005. C-Store: A Column-Oriented DBMS. In Proceedings of the 31st International Conference on Very Large Data Bases (VLDB ‘05). 553–564.
• ⁷² Teradata. 2024. Teradata Database. Acessado em 2024-06-20 em https://www. teradata.com/resources/datasheets/teradata-database
• ⁷³ Frederik Transier. 2010. Algorithms and Data Structures for In-Memory Text Search Engines. Tese de doutorado. https://doi.org/10.5445/IR/1000015824
• ⁷⁴ Adrian Vogelsgesang, Michael Haubenschild, Jan Finis, Alfons Kemper, Viktor Leis, Tobias Muehlbauer, Thomas Neumann e Manuel Then. 2018. Get Real: How Benchmarks Fail to Represent the Real World. In Proceedings of the Workshop on Testing Database Systems (Houston, TX, USA) (DBTest’18). Artigo 1, 6 páginas. https://doi.org/10.1145/3209950.3209952
• ⁷⁵ Site do LZ4. 2024. LZ4. Acesso em 2024-06-20 em https://lz4.org/
• ⁷⁶ Site do PRQL. 2024. PRQL. Acessado em 2024-06-20 em https://prql-lang.org ⁷⁷ Till Westmann, Donald Kossmann, Sven Helmer, and Guido Moerkotte. 2000. The Implementation and Performance of Compressed Databases. SIGMOD Rec.
• 29, 3 (set 2000), 55–67. https://doi.org/10.1145/362084.362137 ⁷⁸ Fangjin Yang, Eric Tschetter, Xavier Léauté, Nelson Ray, Gian Merlino e Deep Ganguli. 2014. Druid: A Real-Time Analytical Data Store. In Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data (Snowbird, Utah, USA) (SIGMOD ‘14). Association for Computing Machinery, New York, NY, USA, 157–168. https://doi.org/10.1145/2588555.2595631
• ⁷⁹ Tianqi Zheng, Zhibin Zhang e Xueqi Cheng. 2020. SAHA: A String Adaptive Hash Table for Analytical Databases. Applied Sciences 10, 6 (2020). https: //doi.org/10.3390/app10061915
• ⁸⁰ Jingren Zhou and Kenneth A. Ross. 2002. Implementando operações de banco de dados usando instruções SIMD. In Anais da Conferência Internacional ACM SIGMOD de 2002 sobre Gerenciamento de Dados (SIGMOD ‘02). 145–156. https://doi.org/10. 1145/564691.564709
• ⁸¹ Marcin Zukowski, Sandor Heman, Niels Nes, e Peter Boncz. 2006. Super-Scalar RAM-CPU Cache Compression. In Proceedings of the 22nd International Conference on Data Engineering (ICDE ‘06). 59. https://doi.org/10.1109/ICDE. 2006.150