10.1 向量化执行、Selection Vector 与数据表示

向量化执行首先是一种 engine interface：operators 每次处理一批 typed values，而不是一次一行。它可以降低调度开销、改善 cache locality，并为 compiler/SIMD 暴露紧凑循环；但“批处理”本身不保证最终使用任何特定 SIMD instruction。

本课目标

• 区分 vectorized execution 与 hardware SIMD；
• 理解 DataChunk、column vector、validity mask 与 selection vector；
• 比较 flat、constant、dictionary/sequence representation；
• 分析 filter、projection、aggregate 的批处理路径；
• 选择 batch size 时权衡 cache、latency 与 memory。

Row-at-a-time 与 batch-at-a-time

// row-at-a-time
bool next(Row& row);

// batch-at-a-time
bool next_batch(Batch& batch);

若 batch 有 2048 rows，一次 operator call 可以 amortize 2048 次调度；typed arrays 还让 inner loop 更简单。

Batch
  column item_type_id: int32[capacity]
  column value_cents:  int64[capacity]
  validity bitmaps
  cardinality
  optional selection/index indirection

这里的 batch 是 horizontal rows slice，由多个等长 column vectors 组成。

为什么 vector 适合 CPU

• contiguous values 减少 pointer chasing；
• type dispatch 从每 value 降到每 batch/kernel；
• validity 可用 bitmask 批量处理；
• filter 产生 positions/mask，后续 operators 可避免复制；
• compact loops 更容易 auto-vectorize；
• prefetch/cache line 更可预测。

字符串、nested values、UDF、hash-table random access 仍可能破坏连续性。

Selection vector

filter value_cents >= 50000：

values:    [12000, 8000, 95000, 180000, 5000]
selected:  [2, 3]

后续 operator 可以迭代 selected positions，不立即把每列 compact copy：

std::size_t select_ge(
    const std::int64_t* values,
    const std::uint64_t* validity,
    std::size_t count,
    std::int64_t threshold,
    std::uint32_t* selected);

这里 selectivity 指匹配行占输入的比例；比例很高时，indirection 的 gather/branch 可能比 dense loop 更贵；engine 可以在 selection vector、bitmask、physical compaction 之间选择。

NULL validity

SQL predicate 对 NULL 产生 UNKNOWN。filter 只保留 TRUE：

validity: [1, 0, 1, 1]
values:   [9, ?, 3, 12]
value>5:  [T, U, F, T]
selected: [0, 3]

kernel 可以先计算 comparison mask，再与 validity mask AND。AND/OR/NOT 的三值逻辑更复杂，不能把 NULL 一律视为 false 后参与所有 expression。

多种 vector representation

Flat

连续 values array + validity，最容易进入 SIMD kernel。

Constant

一个 value 逻辑重复 N 次。函数可只算一次，再产生 constant result；但 NULL/volatile function 语义需注意。

Dictionary

base values: [device, spare_part, consumable]
indices:     [0, 0, 1, 2, 0]

可保持 encoded/filtered view，避免立即 materialize strings。多层 dictionary/selection indirection 会增加 lookup，engine 可 flatten/normalify。

Sequence

start + row_index × increment，适合 row IDs 等。某些 predicates 可直接计算 matching interval 而非逐项生成。

Run-length / compressed

aggregate/filter 可直接在 runs 上执行，例如 COUNT 按 run length 累加。compressed execution 的收益取决于 operator 能否理解 representation。

DuckDB 的准确定位

DuckDB 官方文档描述 vectorized execution；Vector 是 column values container，DataChunk 是一组 vectors。它支持 flat、constant、dictionary、sequence 等 formats，并通过 unified vector format 给 generic operators 一致视图。

当前文档中的常见 standard vector size 是 2048，但这是实现参数，不是“所有向量引擎必须 2048”。调用公开接口时可查询 vector size，不应在 extension 中硬编码。

• DuckDB Execution Format
• DuckDB Internals Overview

Batch filter

下面是 C++17 的函数实现片段（partial）。调用者提供 count 个输入值、至少 ceil(count/64) 个有效位字，以及 count 个输出索引槽位，三块存储在调用期间都必须有效。用 32 位 selection index 时必须限制 count，避免强制转换悄悄截断：

#include <cstddef>
#include <cstdint>
#include <limits>
#include <stdexcept>

std::size_t filter_values(
    const std::int64_t* values,
    const std::uint64_t* validity_words,
    std::size_t count,
    std::int64_t threshold,
    std::uint32_t* selected) {

    if (count > std::numeric_limits<std::uint32_t>::max()) {
        throw std::length_error("selection index exceeds uint32_t");
    }
    std::size_t output = 0;
    for (std::size_t i = 0; i < count; ++i) {
        const bool valid =
            (validity_words[i / 64] >> (i % 64)) & std::uint64_t{1};
        if (valid && values[i] >= threshold) {
            selected[output++] = static_cast<std::uint32_t>(i);
        }
    }
    return output;
}

可用 values={9,0,3,12}、validity_words={0b1101}、threshold=5 验证：返回 2，前两个 selected 为 {0,3}。位置 1 虽然有占位值 0，但有效位为 0，不参与比较。再检查 count 为 0、64、65 时是否正确跨过位图字边界。

compiler 可能 vectorize comparison，却未必能高效 vectorize sparse position compaction。AVX-512 有 mask/compress support，AVX2 通常需要 lookup/permute 或 scalar extraction；engine 可能直接保留 bitmask。

Batch aggregate

struct SumState {
    __int128 total = 0;
    std::uint64_t non_null_count = 0;
};

这里的 __int128 是 GCC/Clang 在支持目标上的扩展，并非标准 C++17 类型；其他编译器需要等价宽整数实现。non_null_count=0 时，SQL SUM 通常应输出 NULL，而不是直接输出初始的 0。对 integer cents，accumulator 仍必须定义溢出策略。SQL SUM 返回 type 由数据库规则决定，不能用 int64_t wraparound 替代。

AVG 通常维护 (sum, count)，NULL 不增加 count。parallel aggregate 需要 merge partial states，并保证 decimal/floating semantics。

Hash 与 vectorization

batch hash join/aggregate 可以：

1. 批量计算 hashes；
2. prefetch candidate buckets；
3. 批量 probe；
4. 生成 match selection；
5. 晚些 materialize payload。

但 hash table access 是 data-dependent/random，常被 memory latency 限制。SIMD 计算 hash 快不代表 whole join 成比例加速；collision、skew 和 resize 仍需处理。

Batch size

太小：operator-call amortization 不够，SIMD setup/dispatch 占比高。

太大：

• working set 超出 L1/L2；
• selection/validity/intermediate memory 增加；
• first-row/cancellation latency 上升；
• skewed operator 独占线程更久；
• cache pollution。

合适 size 取决于 row width、kernel、cache、ISA 与 engine pipeline。固定 1024/2048 只是实现选择，不是硬件定律。

Late materialization

vector engine 可先处理 predicate keys、selection，再取 output columns。但对 compressed file，按 sparse positions 读取仍可能解码整 pages；对 row store，定位额外 columns 可能 random gather。

optimizer 要比较 early materialization 的 sequential work 与 late materialization 的 indirection/gather。匹配比例低通常更利于延迟，匹配比例高时 dense processing 可能更好。

本课小结

向量化执行通过批量接口与 typed representations 降低调度和 materialization。selection、constant/dictionary vectors 与 validity mask 能避免很多无用工作，但最终性能仍受 cache、branch、gather 和 memory bandwidth 限制。下一课进入硬件 SIMD，写出安全 tail、runtime dispatch 与 SQL 数值语义。