Execução Vetorizada e SIMD: Acelerando Motores de Consulta com DuckDB e Velox

A execução vetorizada processa blocos contíguos de dados em cache L1 para saturar a vazão de instruções da CPU.

Esse paradigma elimina o overhead de chamadas virtuais por registro e viabiliza aceleração nativa via SIMD.

Em cargas analíticas e varreduras de código, os bancos tradicionais perdem tempo em paradas de hardware.

O modelo clássico de iteração tupla a tupla degrada a predição de desvios da CPU.

Sistemas modernos como DuckDB, Meta Velox e ClickHouse reestruturam o fluxo de execução em vetores colunares. Essa abordagem transforma varreduras pesadas em operações matemáticas lineares de alta velocidade.

Por que o modelo Volcano tradicional falha no hardware moderno?

O modelo iterador Volcano falha porque trata cada linha individualmente, destruindo a localidade da cache de instruções.

Cada tupla processada exige chamadas a métodos virtuais que impedem a vetorização pelo compilador.

No modelo concebido por Goetz Graefe em 1994, cada operador implementa a interface com open(), next() e close(). Quando uma consulta analisa cem milhões de linhas com quatro operadores encadeados, a CPU executa quatrocentos milhões de despachos dinâmicos polimórficos.

As CPUs modernas dependem de pipelines profundos de quinze a vinte estágios e de preditores de salto sofisticados. O despacho virtual constante gera trocas frequentes no cache L1i e erros de branch prediction caros.

Modelo Volcano (Tuple-at-a-Time):
[Scan] -> next() -> [Filter] -> next() -> [Aggregate] -> next() -> [Output]
(1 chamada virtual por operador para CADA registro processado)

Modelo Vetorizado (Block-Oriented):
[Scan] -> next_vector() -> [Filter Vector] -> [Aggregate Vector] -> [Output]
(1 chamada virtual a cada 1024 ou 2048 registros em lote contíguo)

Além disso, o layout orientado a linhas (Row-Store) carrega colunas desnecessárias para as linhas de cache de 64 bytes da memória. Ler apenas duas colunas em uma tabela de cinquenta campos desperdiça mais de 90% da largura de banda do barramento DRAM.

A pesquisa de Peter Boncz e sua equipe no projeto MonetDB/X100 demonstrou essa ineficiência microarquitetural. O processador passa mais de 70% dos ciclos ocioso aguardando dados da memória principal.

Como funciona a execução vetorizada orientada a blocos?

A execução vetorizada opera sobre vetores contíguos de 1024 a 2048 elementos mantidos integralmente na cache L1 de dados.

Essa estrutura reduz o custo de despacho virtual por um fator proporcional ao tamanho do bloco.

Em vez de devolver uma única linha, o método next() do operador entrega um vetor homogêneo de tipo primitivo. Um bloco com 1024 inteiros de 32 bits consome apenas 4 KB de memória, cabendo confortavelmente nos 32 KB a 48 KB da cache L1D.

// Exemplo de loop de filtro vetorizado em array contíguo primitivo
void filter_greater_than_i32(
    const int32_t* __restrict src,
    uint16_t* __restrict sel_out,
    uint16_t count,
    int32_t threshold,
    uint16_t& match_count
) {
    uint16_t matches = 0;
    for (uint16_t i = 0; i < count; ++i) {
        if (src[i] > threshold) {
            sel_out[matches++] = i;
        }
    }
    match_count = matches;
}

O compilador C++ ou Rust consegue desenrolar esse laço interno homogêneo e aplicar auto-vetorização imediata. Não ocorrem chamadas de funções externas dentro do laço de processamento de elementos.

O tratamento de valores nulos ocorre por meio de máscaras de bits compactadas (validity bitmaps). Isso evita a alocação de flags booleanas de 1 byte por campo, reduzindo o tráfego de memória em até oito vezes.

Qual é o papel das instruções SIMD no processamento colunar?

Instruções SIMD processam múltiplos elementos em registradores largos de 256 ou 512 bits em um único ciclo de clock.

As extensões modernas executam filtros, conversões e agregações em paralelismo aritmético massivo.

Com AVX-512, registradores ZMM guardam dezesseis inteiros de 32 bits.

Eles também processam oito números de ponto flutuante em uma única instrução vetorial. Na arquitetura ARM64, as extensões NEON e SVE2 oferecem benefícios equivalentes com registradores escaláveis.

Ao aplicar uma cláusula de filtro, o processador compara dezesseis valores simultaneamente gerando uma máscara de bits de 16 bits. A instrução _mm512_mask_compressstoreu_epi32 copia apenas os elementos aprovados para a saída sem ramificações condicionais.

#include <immintrin.h>

// Filtragem acelerada por hardware com AVX-512 sem branch condicional
void filter_avx512_i32(
    const int32_t* src,
    int32_t* dest,
    int32_t threshold,
    int count,
    int& out_count
) {
    __m512i v_thresh = _mm512_set1_epi32(threshold);
    int written = 0;

    for (int i = 0; i < count; i += 16) {
        __m512i v_data = _mm512_loadu_si512(reinterpret_cast<const __m512i*>(src + i));
        __mmask16 mask = _mm512_cmpgt_epi32_mask(v_data, v_thresh);
        _mm512_mask_compressstoreu_epi32(dest + written, mask, v_data);
        written += _mm_popcnt_u32(mask);
    }
    out_count = written;
}

A eliminação de saltos condicionais previne completamente penalidades por erro de predição. O código atinge vazão próxima do limite teórico da largura de banda da memória cache L1.

Para strings curtas de até doze bytes, motores modernos utilizam a técnica de strings embutidas (inlined prefix strings). O comparador SIMD avalia o prefixo diretamente nos registradores sem desreferenciar ponteiros na memória heap.

Vetores de seleção: como filtrar dados sem copiar memória?

Vetores de seleção preservam os dados originais intactos e repassam apenas uma lista de índices válidos aos operadores subsequentes.

Essa estratégia evita realocações de memória e cópias redundantes de colunas inteiras durante a execução.

Quando um predicado rejeita 80% das linhas, gerar uma nova coluna física alocada consumiria largura de banda de escrita desnecessária. O motor gera apenas um vetor de inteiros curtos de 16 bits indicando quais posições passaram no teste.

Os operadores seguintes leem o vetor original por meio do array de seleção (src[sel[i]]). Essa indireção leve é absorvida pelo hardware quando os dados residem na cache L2.

Caso múltiplos filtros em cascata reduzam a seletividade para menos de 5%, o motor pode optar por achatar (flatten) o vetor. O custo de compactação passa a ser inferior ao overhead de sucessivas leituras indexadas.

Execução vetorizada vs Compilação JIT: quais são os trade-offs?

A execução vetorizada oferece inicialização instantânea para consultas ad-hoc, enquanto a compilação JIT maximiza a retenção de dados em registradores.

A escolha ideal depende do perfil de latência e da duração das consultas no sistema.

A compilação JIT proposta por Thomas Neumann no HyPer gera código LLVM em tempo real.

O modelo compila o plano inteiro em um único laço de máquina, retendo variáveis em registradores.

Por outro lado, compilar código LLVM introduz uma latência de 15 ms a 300 ms antes de processar o primeiro registro. Em consultas interativas de baixa latência e pipelines de análise em tempo real, esse tempo inicial representa a maior fração do custo.

Sistemas de análise analítica embarcada como o DuckDB priorizam a execução vetorizada pura para garantir latência previsível. Motores híbridos como ClickHouse usam compilação JIT apenas para expressões matemáticas compostas muito repetidas.

O que é Morsel-Driven Parallelism e como ele escala em múltiplos núcleos?

Morsel-Driven Parallelism é um algoritmo de agendamento dinâmico que divide dados em pequenas frações de trabalho processadas por um pool lock-free de threads.

Essa arquitetura elimina gargalos de particionamento estático e equilibra o consumo em topologias NUMA.

O particionamento tradicional divide um milhão de registros em quatro blocos fixos de 250 mil para quatro threads. Se uma partição contiver dados complexos ou encontrar filtros caros, três núcleos ficam ociosos esperando a última thread concluir.

No modelo de Viktor Leis no ACM SIGMOD 2014, o motor fatia a carga em morsels.

Cada lote agrupa de 10.000 a 100.000 tuplas.

Uma fila central com ponteiros atômicos distribui os blocos conforme os núcleos ficam disponíveis.

[Morsel Dispatcher Atômico] (Lock-Free)
  ├── Morsel 1 (100k tuplas) ────> Thread Core 0 (Processando)
  ├── Morsel 2 (100k tuplas) ────> Thread Core 1 (Processando)
  ├── Morsel 3 (100k tuplas) ────> Thread Core 2 (Finalizou -> Pega Morsel 4)
  └── Morsel 4 (100k tuplas) ────> Thread Core 2

Em servidores com múltiplos soquetes, a memória é acessada mais rapidamente pelo nó NUMA local correspondente. O agendador prioriza a entrega de morsels alocados no nó de memória onde a thread está fixada.

Quando a carga do nó local termina, o sistema executa work-stealing de outros soquetes para evitar ociosidade. Isso reduz a contenção de barramentos de interconexão entre processadores e estabiliza o tempo de resposta.

Comparativo arquitetural: DuckDB, Meta Velox e ClickHouse

Embora todos adotem a execução colunar em lote, DuckDB, Velox e ClickHouse possuem decisões distintas de pipeline e reutilização.

Cada motor reflete o ambiente para o qual foi desenhado, variando de bibliotecas C++ acopláveis a servidores massivos.

O DuckDB foi projetado como motor analítico embarcado de processo único, sem dependências externas. Ele utiliza estruturas DataChunk compostas por vetores com vetores de seleção nativos e agendamento morsel-driven simplificado.

O Meta Velox unifica os motores de execução de Presto, Spark e PyTorch em C++. O Velox adota um pipeline push-based com vetores flexíveis (FlatVector, DictionaryVector, SequenceVector) e pool de memória hierárquico com arenas dedicadas.

O ClickHouse foi concebido para ingestão contínua em larga escala e agregação em tempo real. Ele processa blocos colunares heterogêneos (IColumn) e implementa algoritmos próprios de ordenação radix e tabelas hash sem travamento otimizadas para instruções AVX2.

Como o MaxVision Code aplica execução vetorizada em indexação de código?

O MaxVision Code emprega processamento vetorizado para analisar árvores sintáticas e grafos de símbolos em milhões de linhas de código.

A abordagem substitui estruturas baseadas em ponteiros na heap por vetores contíguos de nós de sintaxe.

Ao analisar um repositório corporativo inteiro com Tree-sitter, a representação tradicional cria milhões de pequenos objetos alocados individualmente. Isso satura o alocador de memória e fragmenta as caches L1 e L2 do processador.

No mecanismo interno do MaxVision Code, os nós sintáticos de cada módulo são serializados em uma estrutura colunar contígua (Structure of Arrays - SoA). Filtros por tipo de símbolo, declarações públicas e importações rodam em lote com comparadores vetorizados SIMD.

A varredura atinge velocidades superiores a doze milhões de nós de AST analisados por segundo por núcleo. Essa arquitetura permite que agentes inteligentes executem buscas semânticas profundas no código sem bloquear a interface de desenvolvimento.

Fontes primárias consultadas

• MonetDB/X100: Hyper-Pipelining Query Execution — Peter Boncz, Marcin Zukowski, Niels Nes (CIDR 2005).
• Morsel-Driven Parallelism: A NUMA-Aware Query Engine for Multi-Core Architectures — Viktor Leis, Peter Boncz, Alfons Kemper, Thomas Neumann (ACM SIGMOD 2014).
• Efficiently Compiling Efficient Query Plans for Modern Hardware — Thomas Neumann (PVLDB 2011).
• DuckDB: an Embeddable Analytical Database — Mark Raasveldt, Hannes Mühleisen (ACM SIGMOD 2019).
• Velox: Meta's Unified Execution Engine — Pedro Pedreira, Orri Erling et al. (PVLDB 2022).
• Intel 64 and IA-32 Architectures Optimization Reference Manual — Intel Corporation (2024/2026).
• ClickHouse Core Execution Architecture — Documentação Oficial ClickHouse.
• Volcano — An Extensible and Efficient Query Evaluation System — Goetz Graefe (IEEE TKDE 1994).