Velox HashTable

duanmeng

2026-05-30

1. 整体架构与核心类设计

1.1 类层次

BaseHashTable  (抽象基类，HashTable.h:129)
    │
    └── HashTable<bool ignoreNullKeys>  (模板实现，HashTable.h:544)
            │
            ├── RowContainer rows_            // payload 存储
            ├── VectorHasher[] hashers_       // key 编码器（每列一个）
            ├── char** table_                 // hash 槽数组
            ├── ProbeState                    // probe 状态机（内部类）
            └── HashTable[] otherTables_      // 并行 build 子表

模板参数 ignoreNullKeys：

true：聚合 / Inner Join，null key 直接忽略（deselectRowsWithNulls）
false：null-aware Join（Anti Join、Left Semi Project），null key 参与探测

两个工厂方法：

// 聚合专用
HashTable::createForAggregation(hashers, accumulators, pool);

// Join build 专用
HashTable::createForJoin(hashers, dependentTypes, allowDuplicates,
                         hasProbedFlag, hasCountFlag,
                         minTableSizeForParallelJoinBuild, pool,
                         bloomFilterMaxSize);

1.2 ProbeState：单次探测的状态机

ProbeState（HashTable.cpp:90）是 probe/insert/erase 三种操作的统一内核，以 值语义 存在于栈上，不含堆分配，可在寄存器中缓存关键字段：

class ProbeState {
    char*      group_;           // 当前命中的行指针
    TagVector  wantedTags_;      // broadcast(target_tag) — 16 份 tag 广播
    TagVector  tagsInTable_;     // 当前 bucket 的 16 个 tag
    int32_t    row_;             // 当前处理的输入行号
    int64_t    bucketOffset_;    // 当前 bucket 在 table_ 中的字节偏移
    MaskType   hits_;            // 16bit bitmask，每 bit 代表一个 slot 是否命中
    uint8_t    indexInTags_;     // erase 时记录命中位置；insert 时记录第一个 tombstone
};

三个阶段的 API 设计分离了计算和内存访问，是实现软流水线的基础：

方法	做什么	访存特点
`preProbe(hash, row)`	计算 `bucketOffset`，广播 tag，触发 prefetch	无读
`firstProbe(firstKey)`	加载 16 个 tag，SIMD 比较得到 `hits_`	1 次 cache line 读
`fullProbe<op>(...)`	遍历 `hits_`，跨 bucket 线性探测	按需读 row payload

1.3 HashLookup：probe 的输入输出载体

struct HashLookup {
    const vector<VectorHasher*>& hashers;   // key 编码器（不拥有）
    raw_vector<vector_size_t>    rows;       // 本批次需处理的行号列表
    raw_vector<uint64_t>         hashes;    // 行号 → hash/value_id，index=行号
    raw_vector<char*>            hits;       // 行号 → 命中的行指针，index=行号
    vector<vector_size_t>        newGroups;  // groupProbe 新分配的行号
    raw_vector<uint64_t>         normalizedKeys; // normalized key 缓存
};

hashes 和 hits 都以行号为下标，而非连续下标。这样 rows 可以是稀疏的（跳过 null key 行），不需要 gather/scatter。

2. 应用场景：聚合与 Join 如何使用 HashTable

后面的章节会深入内存布局（§4）、SIMD（§6）、tombstone（§11）、next 指针链等一系列设计。这些设计不是凭空的优化，而是被两类上层算子的诉求逼出来的：HashAggregation 和 HashJoin。本章先站在调用方的角度，讲清”谁在用这张表、用它来干什么、对它有什么要求”，后续每一处设计就都有了归属。

本章是概览，聚焦”各场景对表的诉求”。聚合与 Join 的具体探测代码走读见 §7、§8。

2.1 两类调用方的根本差异

HashTable 同时服务两个形态迥异的算子。理解它们的差异，是理解整张表为什么”一表多用”的钥匙：

维度	HashAggregation（聚合）	HashJoin（连接）
表里存什么	group-by key + accumulator（聚合中间态）	build 侧的 key + 需要带出的 payload 列
build 与 probe	合一：每来一行就 probe，未命中则插入，命中则更新 accumulator	分离：先用 build 侧全量建表，再用 probe 侧逐行查
一个 key 对应几行	恰好一行（同 key 聚到一起）	可能多行（build 侧同 key 多行都要保留）
是否需要遍历全表	是，最后要吐出所有 group	取决于 join 类型（right/full 要遍历未命中行）
删除需求	基本没有	spill 时要 erase 已落盘的行 → 需要 tombstone

这张表里几乎每一行差异，都对应后面一个设计决策。下面分别展开。

2.2 聚合场景对表的诉求

聚合的核心循环是”probe-or-insert“：对输入每一行，用 group-by key 查表——

未命中 → 插入一行，在 payload 区为这一行分配一组 accumulator（如 sum/count/avg 的中间状态）。
命中 → 拿到已存在的行，把当前输入累加进它的 accumulator。

由此推出的诉求：

同一 key 必须唯一——不能像 join 那样允许同 key 多行，否则聚合结果会分裂。所以聚合用表时不挂 next 指针链。
payload 是可变的 accumulator，命中后要原地更新——这要求 payload 行存、且能高效随机定位（§4.3 行布局、§2.3 指针索引）。
最后要全表遍历吐出所有 group——RowContainer 顺序扫描即可，不依赖 hash 表顺序。
低基数 key 极其常见（如按国家、按状态码聚合）——这是 kArray 完美哈希模式（§3.1）的主要受益场景：value_id 直接当数组下标，连 tag 比较都省了。

2.3 Join 场景对表的诉求

Join 把表的使用拆成两个阶段：

1 2	Build 阶段：扫描 build 侧（通常是小表），把每一行插入 HashTable Probe 阶段：扫描 probe 侧（通常是大表），逐行查表，按 join 类型决定输出

由此推出的诉求：

同一 key 允许多行——build 侧可能有多行 key 相同（一对多 join）。表里同 key 的多行用行内 next 指针串成链表（§4.3 中的 next row ptr），probe 命中后顺着链表吐出所有匹配行。
build 与 probe 分离让 build 阶段可以并行——多个线程各建一块再合并（§9 并行 Join Build）。聚合的 build/probe 合一就难以这样切。
probe 侧只读不写——probe 阶段不改表，这让多线程 probe 天然无竞争。
spill 要能删行——内存不够时部分 build 行要落盘，对应的表项要标记删除但不能破坏探测序列 → 这正是 tombstone（0x7F） 存在的理由（§11）。

2.4 不同 Join 模式对表的诉求

“join”不是一种操作，而是一族语义。它们共用同一张 build 表，但对命中/未命中分别要做什么有不同要求——这解释了为什么 HashTable 既要支持”查到就输出”，又要支持”记录谁没查到”：

Join 模式	probe 行命中时	probe 行未命中时	对表的额外诉求
Inner	输出所有匹配（走 next 链）	丢弃	无
Left (outer)	输出所有匹配	输出 probe 行 + build 侧填 null	无（未命中由 probe 侧逻辑处理）
Right / Full	输出匹配，并标记该 build 行已被命中	（Full）输出 null + probe 行	build 行需要一个”是否被命中过“的标记位，最后遍历全表找未命中行输出
Semi	输出 probe 行一次（不展开 next 链）	丢弃	命中即可，无需遍历整条链
Anti	丢弃	输出 probe 行	只关心”有没有”，对 null 敏感
Null-aware Anti	——	需区分”无匹配”与”因 null 无法判定”	key 含 null 时语义特殊 → `HashTable<ignoreNullKeys=false>` 模板特化（§3.2 与 §14.3）

两个关键观察：

Right/Full join 需要”build 行被命中过”的标记，这是聚合场景完全不需要的能力，也是为什么 probe 不总是”只读”——某些模式下要回写命中标记，再在 probe 结束后遍历全表捞未命中行。
Null-aware 模式让 ignoreNullKeys 成为 HashTable 的模板参数而非运行时分支——聚合和 inner join 用 ignoreNullKeys=true，null-aware join 用 false，编译期就把两条语义分开（§14.3 模板单态化）。

2.5 一张表如何承载这么多诉求

把上面的诉求归一下，就能看出整张表的设计骨架是被”用法“决定的：

诉求                                         → 设计响应
─────────────────────────────────────────────────────────
低基数 key 要极致快（聚合常见）               → kArray 完美哈希模式（§3）
高基数/多列 key 要通用                        → kNormalizedKey / kHash 模式（§3）
payload 命中后随机读写                        → RowContainer 行存 + 指针索引（§4）
高频探测要少碰内存                            → tag 索引 + SIMD 过滤（§6）
join 同 key 多行                              → 行内 next 指针链（§4.3）
build 要并行                                  → 分区建表再合并（§9）
right/full 要找未命中行                        → build 行命中标记 + 全表遍历
null-aware 语义                               → ignoreNullKeys 模板参数（§14.3）
spill 要删行                                  → tombstone 标记（§11）

带着这张”诉求 → 设计”映射往下读，后面每一章都是在回答”上层的哪个需求”。 这也是本文档把场景概览前置到这里的原因：先建立动机，再看实现，就不会迷失在 SIMD 和位操作的细节里。

3. 三种 Hash 模式

3.1 模式枚举与触发条件

1	enum class HashMode { kArray, kNormalizedKey, kHash };

decideHashMode()（HashTable.cpp:1751）在每次插入前评估当前 key 的统计信息，自适应地选择最优模式：

rangeSizeProduct < 2M (kArrayHashMaxSize)
    → kArray（所有 key 都用 range 编码）

bestSizeProduct < 2M
    → kArray（部分 key 用 distinct 编码，部分用 range）

rangesProduct 不溢出 uint64（< kRangeTooLarge）
    → kNormalizedKey（全部用 range 编码，拼接进 64bit）

distinctsProduct < 2M
    → kArray（全用 distinct 编码）

distinctsProduct 不溢出 uint64
    → kNormalizedKey（range/distinct 混合编码拼入 64bit）

以上皆否
    → kHash（通用 MurmurHash，逐列比较）

决策流程图：

┌─────────────────────────────────────────────────┐
│            decideHashMode()                     │
└─────────────────┬───────────────────────────────┘
                  │  analyze() 收集 range/distinct 统计
                  ▼
   rangeProd < 2M ? ──YES──► kArray (range)
                  │
   bestProd < 2M  ? ──YES──► kArray (mixed)
                  │
   rangeProd fits64? ──YES──► kNormalizedKey (range)
                  │
   distProd < 2M  ? ──YES──► kArray (distinct)
                  │
   distProd fits64? ──YES──► kNormalizedKey (distinct/mixed)
                  │
                  └─────────► kHash

3.2 kArray 模式

适用场景：key 为低基数整数，例如 country_id（< 200 个值）、day_of_week（7 个值）、boolean 列。

存储结构：table_ 是一个简单的指针数组，下标直接是 value_id：

1	table_[value_id] → char* row

优势：

O(1) 完美哈希，无碰撞，无需线性探测
可直接用 AVX2 _mm256_i64gather_epi64 批量 gather
内存访问极其 cache friendly（顺序扫描）

局限：value_id 空间必须 < 2M（约 16 MB）

3.3 kNormalizedKey 模式

适用场景：多列 key，每列基数不高，但合并后仍能 fit 64 bit。例如 (year, month, day) = 50 × 12 × 31 ≈ 18600 个组合。

核心思想：把多列 key 的 value_id 通过乘法编码进一个 64 bit 整数：

normalized_key = id₁ × 1
              + id₂ × range₁
              + id₃ × range₁ × range₂
              + ...

这个 normalized_key 既作为 hash 的输入（经过 mixNormalizedKey 扰动），也被缓存在 row 起始地址的前 8 字节（负偏移 -8），避免 probe 时重新解码所有列：

RowContainer 内存布局（kNormalizedKey 模式）:
  [row - 8]  normalized_key_t（8 字节缓存）
  [row + 0]  key 列 1
  [row + N]  key 列 2
  ...        payload 列

mixNormalizedKey（HashTable.cpp:442）用 folly::hasher<uint64_t> 把连续分布的 normalized_key 扰动成随机分布，防止大量数据落在相邻 bucket：

1
2
3

inline uint64_t mixNormalizedKey(uint64_t k, uint8_t bits) {
    return folly::hasher<uint64_t>()(k);
}

3.4 kHash 模式

适用场景：高基数 key（如 UUID、字符串、多列大范围整数）。

存储结构：标准开放地址 hash 表，每个 bucket 16 个 slot（见第 3 节）。

Key 比较：每次命中时调用 compareKeys()（HashTable.cpp:358），逐列调用 RowContainer::compare()，支持字符串、complex type 的语义比较。

3.5 模式切换

模式切换是单向的：kArray → kHash，kNormalizedKey → kHash，永远不会回退。一旦遇到无法编码的 value（value_id 映射失败），立即切换到 kHash：

// hashRows() 中
if (!hasher->computeValueIdsForRows(..., hashes)) {
    return false;  // 触发上层调用 setHashMode(kHash)
}

4. 内存布局详解

4.1 kArray 模式

table_:  [ ptr₀ | ptr₁ | ptr₂ | ... | ptrN ]
              ↑                         ↑
          value_id=0               value_id=N
每个条目：8 bytes（一个 char*）
总大小  ：capacity_ × 8 bytes

空槽：nullptr。插入时直接 table_[value_id] = row_ptr。

4.2 kHash / kNormalizedKey 模式：Bucket 结构

这是 Velox HashTable 设计中最精彩的部分，直接借鉴了 F14（folly）的 bucket 思想：

每个 Bucket = 128 bytes = 2 个 CPU cache line

 Offset 0                                               Offset 127
  ┌──────────────────┬──────────────────────────────────┬──────────┐
  │   tags[16]       │      pointers[16]                │ padding  │
  │  (16 × uint8_t)  │      (16 × 6 bytes)              │ (16 B)   │
  └──────────────────┴──────────────────────────────────┴──────────┘
  ↑                  ↑                                  ↑
 16 bytes           96 bytes                           16 bytes

tags 数组（16 字节，对齐到 128 字节边界）：

每个 tag 是 1 字节，编码规则：

1
2
3

tag = 0x00        → 空槽（kEmptyTag）
tag = 0x7F        → 已删除（kTombstoneTag，高位=0，与空槽可区分）
tag = hash >> 38 | 0x80  → 有效槽（高位强制为 1，7bit 有效位）

hashTag() 实现：

1
2
3

static uint8_t hashTag(uint64_t hash) {
    return static_cast<uint8_t>(hash >> 38) | 0x80;
}

取 hash 的第 38-44 位（7 bits）作为 tag，原因：

hash 的低位用于定位 bucket（bucketOffset = hash & bucketOffsetMask_）
tag 取高位，与 bucket 索引的位域正交，减少 tag 碰撞概率

为什么 | 0x80 是必须的，而非可选的

hash >> 38 提取的是原始 7-bit 值，范围 [0x00, 0x7F]，恰好覆盖了两个特殊标记的完整值域：

1 2	hash >> 38 原始值： 0x00 ←→ kEmptyTag (会误判为空槽) 0x7F ←→ kTombstoneTag (会误判为已删除)

若不施加任何约束，当某个 key 的 hash 恰好使 (hash >> 38) == 0x00 或 == 0x7F，写入的 tag 就与特殊标记混淆，探测时会错误地把有效槽当作空槽终止或当作墓碑跳过。

| 0x80 把有效 tag 的值域强制推入 [0x80, 0xFF]，与 [0x00, 0x7F] 完全不相交：

1
2
3

0x00        = 0000_0000  →  kEmptyTag      (bit7 = 0)
0x7F        = 0111_1111  →  kTombstoneTag  (bit7 = 0)
0x80~0xFF   = 1xxx_xxxx  →  有效 tag       (bit7 = 1，由 | 0x80 保证)

三种状态由 bit7 一刀切分：tag & 0x80 != 0 等价于”槽有效”。探测的正确性完全依赖这个不变式：

遇到值	判断	动作
`0x00`	空槽	终止探测，返回 miss
`0x7F`	Tombstone	跳过，继续向后探测
`≥ 0x80`	有效	比较实际 key

连锁收益：该不变式使 §6.9 中 SSE2 的 PMOVMSKB 优化成为可能——PMOVMSKB 本质上提取每字节的最高位，bit7 = 0 表示空/tombstone，bit7 = 1 表示有效，省去一次显式 PCMPEQB 比较。

pointers 数组（96 字节）：

每个指针 6 字节（48 bit），利用 x86-64 用户空间地址只用低 48 bit 的事实：

1
2
3

static constexpr uint8_t  kPointerSignificantBits = 48;
static constexpr uint64_t kPointerMask = bits::lowMask(48);  // 0x0000FFFFFFFFFFFF
static constexpr int32_t  kPointerSize = 6;

读取指针：

char* pointerAt(int32_t slotIndex) {
    return reinterpret_cast<char*>(
        *reinterpret_cast<uintptr_t*>(&pointers_[kPointerSize * slotIndex])
        & kPointerMask);
}

直接从 6 字节起始地址读取一个 8 字节 uintptr_t（越界读高 2 字节），然后用 & kPointerMask 屏蔽掉不属于本指针的高位。这是一个合法的”越界读”优化——因为 padding 的存在，这 2 个额外字节始终在同一分配内。

写入指针时保留非指针位（为未来扩展预留）：

void setPointer(int32_t slotIndex, void* pointer) {
    auto* slot = reinterpret_cast<uintptr_t*>(&pointers_[slotIndex * kPointerSize]);
    *slot = (*slot & ~kPointerMask) | reinterpret_cast<uintptr_t>(pointer);
}

内存节省计算：

标准布局：16 槽 × 8 字节指针 = 128 字节指针
Velox 布局：16 字节 tag + 96 字节指针 + 16 字节 padding = 128 字节
等效：每槽从 8 字节压缩到 8 字节（tag + pointer 合计），但 tag 独立存放使 SIMD 一次扫描 16 个 tag 成为可能

bucket 在 table_ 中的寻址：

// hash → bucket 字节偏移
int64_t bucketOffset(uint64_t hash) const {
    return hash & bucketOffsetMask_;
    // bucketOffsetMask_ = sizeMask_ & ~(kBucketSize - 1)
    //                   = (capacity_*8 - 1) & ~127
}

// slot 在 bucket 内的索引（0-15）
int32_t slotIndex = index & (sizeof(TagVector) - 1);  // index & 15

整体 table_ 内存示意（假设 4 个 bucket）：

table_:
 Bucket 0 [128B]: tags[16] | ptrs[16] | pad
 Bucket 1 [128B]: tags[16] | ptrs[16] | pad
 Bucket 2 [128B]: tags[16] | ptrs[16] | pad
 Bucket 3 [128B]: tags[16] | ptrs[16] | pad

4.3 RowContainer 中的行布局（kNormalizedKey 模式）

低地址
  ┌─────────────────┐  ← row - sizeof(normalized_key_t)
  │  normalized_key │  8 字节，由 insertEntry() 写入
  ├─────────────────┤  ← row (RowContainer 分配的起点)
  │  null flags     │  每列 1bit，packed bytes
  ├─────────────────┤
  │  key col 0      │  fixed-width: inline；variable: StringView + arena
  ├─────────────────┤
  │  key col 1      │
  ├─────────────────┤
  │  payload col 0  │
  ├─────────────────┤
  │  ...            │
  ├─────────────────┤
  │  next row ptr   │  仅 join build（nextOffset_ > 0）：指向同 key 的下一行
  └─────────────────┘

RowContainer::normalizedKey() 静态方法：

static inline normalized_key_t& normalizedKey(char* group) {
    return *reinterpret_cast<normalized_key_t*>(
        group - sizeof(normalized_key_t));
}

4.4 全局视角：列 → 索引 → 行的三段式混合布局

把前三小节拼起来看，kNormalizedKey / kHash 模式下整个数据通路其实是三种不同布局的拼接，而不是单一的”行存”或”列存”。这是这套设计最值得玩味的地方。

① 输入：列存（Columnar Vector）
   ┌──────┬──────┬──────┐
   │ col0 │ col1 │ col2 │   每列连续存放，SIMD 友好
   └──────┴──────┴──────┘
        │  VectorHasher 向量化算 hash（§5）
        ▼
② 目录：指针索引（Bucket 数组，bucket 内 tag 用 SoA 打包）
   Bucket = [ t0 t1 … t15 ][ ptr0 ptr1 … ptr15 ]
              └─16B tag 区─┘ └──96B 指针区──────┘
        │  SIMD 扫 tag 命中后，解引用指针
        ▼
③ Payload：行存（RowContainer）
   row = [ normKey ][ null flags ][ key0 key1 … ][ payload0 … ]
          每行所有列物理相邻

关键认知：hash 表目录里不存任何列数据，它只存 (tag, 6 字节指针)。 真正的 payload 永远在 RowContainer 的行里。所以”hash 表是列式的”这个说法并不准确——它是一个指针索引；唯一沾”列式”边的是 bucket 内部把 16 个 tag 打包在一起的 SoA 微布局，那是为 SIMD 服务的，不是一个列存数据模型。

为什么每一段要用不同的布局？

核心原则一句话：每一段都用最贴合它自身访问模式的布局（§16.6 “让数据结构贴合硬件脾气”在布局上的具体落地）。

段	布局	访问模式	为什么这样选
① 输入	列存 Vector	对一整列做同一个 hash 运算	列存让同类型数据连续，`VectorHasher` 能向量化批量算 hash / value_id；若此处是行存，算 hash 要跨行跳读，SIMD 用不上
② 目录	指针索引 + tag SoA	高频探测，先快速否决再确认	tag 打包让一条 `PCMPEQB` 扫 16 个槽（§6.2）；只存指针而非整行，让目录足够小、能整体驻留 cache，探测时少碰内存
③ Payload	行存 RowContainer	命中后整行读写（聚合更新 / join 输出）	同一 key 的所有列物理相邻，命中后一次性读出整行只需少量 cache line；若此处是列存，读一行要从 N 个列数组各取一格，N 次 cache miss

这套混合布局解决了什么根本矛盾

它同时满足了三个本来互相冲突的诉求：

进表要快——输入是列存，hash 计算能向量化（诉求：批量、向量化）。
找得要快——目录是紧凑的 tag 索引，探测能 SIMD 过滤且 cache 命中率高（诉求：高频随机访问下少碰内存）。
用得要快——payload 行存，命中后整行读写局部性最优（诉求：随机单点访问整条记录）。

如果强行统一成单一布局，必然在某一环付出代价：

全列存：命中后读一行要跨 N 个列数组 → N 次 cache miss，聚合 / join 输出会很慢。
全行存：算 hash 时跨行跳读 → 向量化失效，进表变慢；且若把整行塞进 bucket，bucket 装不下 16 个槽，SIMD 扫 tag 也就无从谈起。

所以”行列混合”不是妥协，而是主动地在数据生命周期的每个阶段切换到当下最优的布局。 列存负责”算”，索引负责”找”，行存负责”用”——三者各司其职，靠 ② 这层薄薄的指针索引粘合起来。这也是为什么 tag 要压到 8-bit、指针要压到 6-bit（§4.2）：目录越小，第 ② 段就越能整体待在 cache 里，”找”才足够快。

5. VectorHasher：Key 编码引擎

VectorHasher（velox/exec/VectorHasher.h）是 HashTable 和向量化数据之间的桥梁，每个 key 列对应一个 VectorHasher 实例。

5.1 两种编码模式

Range 模式（hasRange_ = true）：

1	value_id = (int64_value - min_) + 1

适用于连续或近似连续的整数。min_/max_ 在 analyze() 时扫描 RowContainer 得到。

Distinct 模式（uniqueValues_ 哈希表）：

1	value_id = uniqueValues_.find(value).id // 从 1 开始

适用于稀疏整数、小基数整数。用内部 F14FastSet 维护 value → sequential_id 的映射。

5.2 `computeValueIds()`：向量输入 → value_id 数组

在 prepareForGroupProbe() 中调用：

for (auto i = 0; i < hashers.size(); ++i) {
    if (mode != kHash) {
        hasher->computeValueIds(rows, lookup.hashes);  // 直接写 hash 数组
    } else {
        hasher->hash(rows, i > 0, lookup.hashes);     // 混入前面列的 hash
    }
}

当多列 key 都用 value_id 时，各列的 value_id 通过 multiplier_ 进行位置编码：

hash[row] = id_col0 * 1
           + id_col1 * range_col0
           + id_col2 * range_col0 * range_col1
           + ...

multiplier_ 在 enableValueRange / enableValueIds 时被设置为前面所有列的 range 乘积，实现了多列 key 的无碰撞编码。

5.3 `lookupValueIds()`：join probe 专用

join probe 时，probe 侧的 key 值必须能映射到 build 侧已知的 value_id，否则该行一定不命中，可以提前剪枝：

1	hashers_[i]->lookupValueIds(*key, rows, lookup.scratchMemory, lookup.hashes);

如果某个 probe key 的值在 build 侧 uniqueValues_ 中找不到，该行会从 rows 中移除，完全跳过 hash 探测。这是 kNormalizedKey 模式下的提前剪枝优化。

5.4 `merge()`：并行 build 后的 VectorHasher 合并

并行 build 时，每个子表的 VectorHasher 独立收集 uniqueValues_，prepareJoinTable() 时调用 merge() 把所有子表的 VectorHasher 合并到主表：

1
2
3

for (auto& other : otherTables_) {
    hashers_[i]->merge(*other->hashers_[i], vectorHasherMaxNumDistinct);
}

合并后重新分配 value_id，触发完整的 decideHashMode()。

6. SIMD 技巧专章

6.1 平台抽象：TagVector

Velox 通过 xsimd 抽象了 SSE2 / NEON 差异：

#if XSIMD_WITH_SSE2
using TagVector = xsimd::batch<uint8_t, xsimd::sse2>;   // 128bit，16×uint8
#elif XSIMD_WITH_NEON
using TagVector = xsimd::batch<uint8_t, xsimd::neon>;   // 128bit，16×uint8
#endif
using MaskType = uint16_t;  // 16 slots → 16 bit mask

loadTags()（HashTable.h:487）有意禁用 TSAN，因为并行 build 阶段不同线程写入不相交的 bucket 范围，但 TSAN 无法分析这种模式：

__attribute__((__no_sanitize__("thread")))
static TagVector loadTags(uint8_t* tags, int64_t tagIndex) {
    auto src = tags + tagIndex;
#if XSIMD_WITH_SSE2
    return TagVector(_mm_loadu_si128(reinterpret_cast<__m128i const*>(src)));
#elif XSIMD_WITH_NEON
    return TagVector(vld1q_u8(src));
#endif
}

6.2 技巧 1：16-way Tag 并行比较（核心 SIMD 优化）

问题：传统开放地址 hash 表每次 probe 需要逐个检查 slot 的 tag，单次 probe 最坏需要 16 次比较（一个满 bucket）。

解法：将 16 个 tag 打包成 16 字节向量，用一条 SIMD 指令同时比较 16 个：

// preProbe: 将目标 tag 广播成 16 份
wantedTags_ = BaseHashTable::TagVector::broadcast(hashTag(hash));

// firstProbe: 加载 16 个 tag，一次比较
tagsInTable_ = loadTags(table_, bucketOffset_);
hits_ = simd::toBitMask(tagsInTable_ == wantedTags_);
//       ↑ 一条 PCMPEQB + PMOVMSKB 指令（SSE2）
//         结果是 16bit bitmask，第 i bit = 1 表示 slot i 的 tag 匹配

x86 SSE2 汇编等价：

1 2	PCMPEQB xmm1, xmm0 ; 16字节并行比较，生成 0xFF/0x00 掩码 PMOVMSKB eax, xmm1 ; 提取每字节最高位 → 16bit 整数

处理命中的 bitmask：

while (hits_ > 0) {
    const int32_t hit = bits::getAndClearLastSetBit(hits_);
    // hit = trailing zero count = 命中的 slot 索引
    group_ = table.row(bucketOffset_, hit);
    __builtin_prefetch(group_ + firstKey);  // 立即 prefetch payload
}

getAndClearLastSetBit() 对应 BSF（Bit Scan Forward）+ BTC 指令，极快。

6.3 技巧 2：4-路 ProbeState 软流水线

问题：单个 probe 的瓶颈是 DRAM 延迟（prefetch 到结果可用有 ~100 cycle 的延迟）。

解法：创建 4 个独立的 ProbeState，把”触发 prefetch”和”使用数据”分离到不同 probe 的执行中：

// groupProbe() 中的 4-路流水：
for (; probeIndex + 4 <= numProbes; probeIndex += 4) {
    // 阶段1：4个 probe 同时 preProbe（触发4个 prefetch）
    state1.preProbe(*this, lookup.hashes[rows[probeIndex+0]], rows[probeIndex+0]);
    state2.preProbe(*this, lookup.hashes[rows[probeIndex+1]], rows[probeIndex+1]);
    state3.preProbe(*this, lookup.hashes[rows[probeIndex+2]], rows[probeIndex+2]);
    state4.preProbe(*this, lookup.hashes[rows[probeIndex+3]], rows[probeIndex+3]);
    // ↑ 此时4个 bucket 的 cache line 开始并发加载

    // 阶段2：4个 probe 同时 firstProbe（此时 cache line 已返回）
    state1.firstProbe<kInsert>(*this, 0);
    state2.firstProbe<kInsert>(*this, 0);
    state3.firstProbe<kInsert>(*this, 0);
    state4.firstProbe<kInsert>(*this, 0);

    // 阶段3：完整 probe（可能跨 bucket）
    fullProbe<false>(lookup, state1, false);
    fullProbe<false>(lookup, state2, true);   // extraCheck=true：重新加载
    fullProbe<false>(lookup, state3, true);
    fullProbe<false>(lookup, state4, true);
}

时序示意图：

cycle:  0   10   20   30   40   50   60   70   80   90  100  110
        ├────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┤
state1: │pre │    │    │    │    │1st │full│    │    │    │    │
state2: │pre │    │    │    │    │1st │    │full│    │    │    │
state3: │pre │    │    │    │    │1st │    │    │full│    │    │
state4: │pre │    │    │    │    │1st │    │    │    │full│    │
         ↑4个prefetch同时发出                   ↑数据已在L1

6.4 技巧 3：64-路 prefetch（Normalized Key / Join Insert）

kNormalizedKey 模式的 join probe 和 insert 使用更大的批次（64路）：

constexpr int32_t kPrefetchSize = 64;
ProbeState states[kPrefetchSize];  // 栈上 64 个状态

for (; probeIndex + kPrefetchSize <= numProbes; probeIndex += kPrefetchSize) {
    // 批次1：64个 preProbe，64个 prefetch 同时发射
    for (int32_t i = 0; i < kPrefetchSize; ++i) {
        states[i].preProbe(*this, hashes[rows[probeIndex + i]], rows[probeIndex + i]);
    }
    // 批次2：64个 firstProbe
    for (int32_t i = 0; i < kPrefetchSize; ++i) {
        states[i].firstProbe(*this, kKeyOffset);
    }
    // 批次3：64个 fullProbe
    for (int32_t i = 0; i < kPrefetchSize; ++i) {
        hits[states[i].row()] = states[i].joinNormalizedKeyFullProbe(*this, keys);
    }
}

64-路比 4-路更适合 normalized key 场景，因为 normalized key 的比较在 row payload 的负偏移 -8 处，该地址通常不在 tag 的 cache line 内，需要额外一次内存访问，更长的 in-flight 深度才能有效隐藏延迟。

6.5 技巧 4：AdaptivePrefetch（自适应预取步长）

hashRows() 在 kNormalizedKey 模式下重新哈希已有行时，读取 RowContainer::normalizedKey(rows[i])，地址分布随机，需要预取：

AdaptivePrefetch prefetch(numRows);
for (int32_t i = 0; i < numRows; ++i) {
    if (auto ahead = prefetch.lookAhead()) {
        __builtin_prefetch(rows[i + ahead] - sizeof(normalized_key_t));
    }
    hashes[i] = mixNormalizedKey(RowContainer::normalizedKey(rows[i]), sizeBits_);
}

为什么不用固定步长？ 预取步长的最优值取决于 DRAM 延迟与循环体执行速度的比值。working set 全在 L2 cache 时步长 4 就够；数据完全 cold、每次读都 DRAM miss 时需要更大步长才能把延迟隐藏住。不同机器、不同数据规模下最优值差异很大，固定步长必然在某些场景下过短（延迟未被隐藏）或过长（浪费预取带宽）。

算法：前 16 次迭代计时，一次性定出步长

AdaptivePrefetch（AdaptivePrefetch.h）的实现分两个阶段：

class AdaptivePrefetch {
    static constexpr int32_t kMeasurementIterations = 16;   // 采样迭代次数
    static constexpr int32_t kMinLookAhead = 4;             // 步长下限
    static constexpr int32_t kMaxLookAhead = 32;            // 步长上限
    static constexpr int64_t kAssumedDramLatencyNs = 100;   // 假设 DRAM 延迟 100ns
    static constexpr int64_t kCoefficient = 4;              // 并发飞行的 miss 数

    int32_t lookAhead() {
        if (iteration_ == kMeasurementIterations) {
            computeLookAhead();   // 第 16 次时计算步长，之后固定
        }
        ++iteration_;
        if (iteration_ + lookAhead_ > numIterations_) {
            return 0;             // 接近末尾时归零，防止越界 prefetch
        }
        return lookAhead_;
    }

    void computeLookAhead() {
        auto elapsedNs = /* 从构造到现在的纳秒数 */;
        lookAhead_ = std::clamp(
            kCoefficient * kAssumedDramLatencyNs * kMeasurementIterations / elapsedNs,
            kMinLookAhead, kMaxLookAhead);
    }
};

步长公式推导：

1 2	lookAhead = kCoefficient × kAssumedDramLatencyNs × kMeasurementIterations / elapsed_ns = 4 × 100ns × 16 / elapsed_ns

elapsed_ns / kMeasurementIterations：每次迭代的平均耗时（ns）
kAssumedDramLatencyNs / 每次迭代耗时：一次 DRAM miss 期间能执行多少次迭代，即”最少需要多大步长才能让 prefetch 及时到位”
× kCoefficient：保证同时有 4 个 miss 在 in-flight，以充分利用内存带宽

以每次迭代耗时 25ns（running fast, data in L2）为例：

1	lookAhead = 4 × 100 × 16 / (25 × 16) = 4 × 100 / 25 = 16

以每次迭代耗时 100ns（严重 DRAM miss）为例：

1	lookAhead = 4 × 100 × 16 / (100 × 16) = 4 × 100 / 100 = 4 → clamp 到 kMinLookAhead=4

结果始终被 clamp 在 [4, 32]，避免步长过小（prefetch 无效）或过大（prefetch 过于激进占用带宽）。

6.6 技巧 5：kArray 模式下的 AVX2 Gather

arrayGroupProbe() 在 AVX2 可用且行号连续时走向量化快路径：

if (process::hasAvx2() && simd::isDense(rows, numProbes)) {
    constexpr int32_t kWidth = xsimd::batch<int64_t>::size;  // 4（AVX2）
    for (i = start; i <= end; i += kWidth) {
        // hashes[i..i+3] 中存放了 value_id（array 下标）
        // 用 gather 一次从 table_[] 加载 4 个指针
        auto loaded = simd::gather(
            reinterpret_cast<const int64_t*>(table_),
            reinterpret_cast<const int64_t*>(hashes + i));
        loaded.store_unaligned(reinterpret_cast<int64_t*>(groups + i));

        // 检测哪些是 nullptr（miss）
        auto misses = simd::toBitMask(loaded == allZero);
        // ...处理 miss
    }
}

等价于 _mm256_i64gather_epi64，4 个随机地址一次性发起，让 CPU 的内存子系统并发处理。

6.7 技巧 6：listJoinResults 快路径的 SIMD Filter

当 join 无重复 key（!hasDuplicates_）且行大小可估算时，走 listJoinResultsFastPath()：

constexpr int32_t kWidth = xsimd::batch<int64_t>::size;

for (; i + kWidth <= numRows && numOut < simdOutLimit; i += kWidth) {
    // gather：按 sourceRows[i..i+3] 的行号，从 hits[] 数组中取出命中指针
    auto indices  = simd::loadGatherIndices<int64_t, int32_t>(sourceRows + i);
    auto hitWords = simd::gather(sourceHits, indices);

    // 检测 miss（nullptr）
    auto misses = includeMisses ? 0 : simd::toBitMask(hitWords == 0);

    if (!misses) {
        // 全部命中：直接 store，无分支
        hitWords.store_unaligned(resultHits + numOut);
        indices.store_unaligned(resultRows + numOut);
        numOut += kWidth;
    } else {
        // 有 miss：用 simd::filter 压缩（PSHUFB 实现）
        auto matches = misses ^ bits::lowMask(kWidth);
        simd::filter<int64_t>(hitWords, matches, ...).store_unaligned(...);
        simd::filter<int32_t>(indices, matches, ...).store_unaligned(...);
        numOut += __builtin_popcount(matches);
    }
}

simd::filter 是 PSHUFB/vpermps 指令的封装，实现了无分支的向量压缩（compress）操作。

6.8 技巧 7：SIMD 查找并行 Build 的分区边界

findPartition()（HashTable.cpp:1208）用 SIMD 在 buildPartitionBounds_ 中二分查找某行所属的分区：

constexpr int32_t kBatch = xsimd::batch<PartitionBoundIndexType>::size;
auto indexVector = xsimd::batch<PartitionBoundIndexType>::broadcast(index);
for (auto i = 1; i < numPartitions; i += kBatch) {
    auto bits = simd::toBitMask(
        indexVector < xsimd::batch<PartitionBoundIndexType>::load_unaligned(bounds + i));
    if (bits) {
        return i + __builtin_ctz(bits) - 1;
    }
}

一次比较 kBatch（4~8）个边界值，用 ctz（count trailing zeros）立即得到第一个大于 index 的位置。

6.9 技巧 8：insertForGroupBy 中针对 SSE2 vs 非 SSE2 的编译期分支

rehash 期间 insertForGroupBy()（HashTable.cpp:1327）的空槽检测有一个微妙的平台差异：

MaskType free =
    ~simd::toBitMask(
#if XSIMD_WITH_SSE2
        // SSE2 上 PMOVMSKB 直接提取每字节最高位（0=empty, 因为 tag=0）
        // 无需构造 batch_bool，直接从 TagVector 提取 bitmask 更快
        BaseHashTable::TagVector::batch_bool_type(tagsInTable)
#else
        // 其他架构用显式比较
        tagsInTable != TagVector::broadcast(ProbeState::kEmptyTag)
#endif
    ) & ProbeState::kFullMask;

在 SSE2 上，PMOVMSKB 本质上是把每字节最高位提取出来：

1
2
3

tag = 0x00  → bit7 = 0  → 空槽
tag = 0x7F  → bit7 = 0  → Tombstone
tag ≥ 0x80  → bit7 = 1  → 有效槽

这之所以成立，根本原因在于 §4.2 分析的 | 0x80 约束：有效 tag 的值域被强制推入 [0x80, 0xFF]，bit7 恒为 1；而两个特殊标记 0x00 和 0x7F 的 bit7 均为 0。因此 PMOVMSKB 提取最高位得到的 bitmask 直接等同于”哪些槽有效”，无需再做一次 PCMPEQB(tags, 0x00) 的显式比较。

注释中还说明：rehash 时表中只有空槽和有效槽，永远没有 tombstone（新表刚分配，所有槽先清零，只会 insert 不会 erase），因此连 0x7F 的情况也可以忽略，进一步简化了逻辑。

6.10 技巧 9：`hits_` 与 `free` —— 同一 TagVector 的两种 bitmask 用法

对同一个 16 字节 TagVector，SIMD 可以同时提取两类信息，分别服务于探测和插入：

TagVector tagsInTable_  ←  loadTags(bucket)   // 一次读 16 个 tag
     │
     ├── == wantedTags_  →  hits_   bitmask    // 哪些 slot 的 tag 与目标匹配
     └── == kEmptyTag    →  free    bitmask    // 哪些 slot 是空的（可写入）

hits_：探测/删除时使用

// ProbeState::firstProbe()
hits_ = simd::toBitMask(tagsInTable_ == wantedTags_);
// 作用：找出 tag 匹配的 slot，候选命中集合
// 后续：遍历 hits_，逐个加载 row 指针比较 key
while (hits_ > 0) {
    int32_t slot = bits::getAndClearLastSetBit(hits_);  // BSF 取最低 bit
    group_ = table.row(bucketOffset_, slot);
    // ... compareKeys(group_)
}

free：插入时使用

// fullProbe<kInsert> 中
MaskType free = ~simd::toBitMask(tagsInTable_ != kEmpty) & kFullMask;
// 作用：找出空槽，确定可以写入的位置
if (free) {
    int32_t slot = bits::getAndClearLastSetBit(free);  // 取第一个空槽
    // 先处理 hits_（有无重复 key）
    // 若无重复，写入 tag + pointer 到 slot
    table.bucketAt(bucketOffset_)->setTag(slot, tag);
    table.bucketAt(bucketOffset_)->setPointer(slot, newRow);
} else {
    // bucket 全满 → nextBucketOffset() 跳下一个 bucket 继续探测
}

两者在同一次 fullProbe 中协同工作：

对每个 bucket 循环：
  1. SIMD 加载 tagsInTable_
  2. 计算 hits_  = PCMPEQB(tagsInTable_, wantedTags_)  → 找重复 key（join 防重）
  3. 计算 free   = ~PMOVMSKB(tagsInTable_) & mask       → 找可写入空槽
  4. 遍历 hits_：比较 key，处理重复（pushNext 或 upsert）
  5. 若 free 非零：写入新行，结束
  6. 若 free 为零（bucket 全满）：advance 到下一个 bucket，重复

free 同时也是探测终止条件：在 probe（而非 insert）时，free != 0 说明 bucket 内有空槽，一定不存在从更早 bucket 溢出到此的同 key 行——因此 free 可以提前终止跨 bucket 探测链，避免不必要的继续扫描。

对比小结：

bitmask	来源	语义	使用场景
`hits_`	`tagsInTable_ == wantedTags_`	“tag 与目标相同的 slot”	probe / erase：找候选命中
`free`	`~(tagsInTable_ != kEmpty)`	“tag 为 0x00 的 slot”	insert：找可写入空槽；probe：判断探测链终止

两者都通过 getAndClearLastSetBit()（BSF）逐个取出，共享同一套 bitmask 迭代基础设施。

7. 聚合场景：Group Probe

7.1 全生命周期

SQL: SELECT k, sum(v) FROM t GROUP BY k
         ↓
GroupingSet::addInput(batch)
    ↓
prepareForGroupProbe(lookup, input, rows, spillBit)
    ├── 解码 key 列（VectorHasher::decode）
    ├── 过滤 null key（ignoreNullKeys=true 时）
    └── 计算 hash / value_id → lookup.hashes[]
         ↓
groupProbe(lookup, spillBit)
    ├── kArray  → arrayGroupProbe()
    ├── kNormalizedKey → groupNormalizedKeyProbe()
    └── kHash   → 4-路流水 ProbeState
         ↓
对 lookup.newGroups 中的新行初始化 accumulator
对所有命中行更新 accumulator（sum/count/...）

7.2 prepareForGroupProbe 详解

void HashTable<ignoreNullKeys>::prepareForGroupProbe(...) {
    // Step 1: 解码 key 列（延迟解码，只 decode 被 rows 选中的行）
    for (auto& hasher : hashers) {
        hasher->decode(*input->childAt(hasher->channel()), rows);
    }

    // Step 2: 过滤 null key（仅 ignoreNullKeys=true）
    if constexpr (ignoreNullKeys) {
        deselectRowsWithNulls(hashers, rows);
    }

    // Step 3: 计算 hash
    bool rehash = false;
    for (auto& hasher : hashers) {
        if (mode != kHash) {
            if (!hasher->computeValueIds(rows, lookup.hashes)) {
                rehash = true;  // 出现新的 value，value_id 空间不够
            }
        } else {
            hasher->hash(rows, i > 0, lookup.hashes);  // MurmurHash 混入
        }
    }

    // Step 4: 如需 rehash，重新决定 hash mode 并递归调用
    if (rehash || capacity() == 0) {
        decideHashMode(input->size(), spillBit);
        prepareForGroupProbe(lookup, input, rows, spillBit);  // 递归（最多一次）
        return;
    }

    populateLookupRows(rows, lookup.rows);
}

7.3 arrayGroupProbe：kArray 快路径

void HashTable<ignoreNullKeys>::arrayGroupProbe(HashLookup& lookup) {
    // AVX2 快路径：行号连续 + AVX2 可用
    if (process::hasAvx2() && simd::isDense(rows, numProbes)) {
        for (i = start; i <= end; i += kWidth) {
            auto loaded = simd::gather(table_, hashes + i);  // 按 value_id gather
            loaded.store_unaligned(groups + i);
            auto misses = simd::toBitMask(loaded == allZero);
            if (LIKELY(!misses)) continue;
            // 处理 miss：insertEntry() 新建行
            for (auto miss = 0; miss < kWidth; ++miss) {
                if (!groups[i + miss]) {
                    groups[i + miss] = insertEntry(lookup, hashes[i+miss], i+miss);
                }
            }
        }
    }
    // 标量尾处理
    for (; i < numProbes; ++i) {
        uint64_t index = hashes[rows[i]];
        char* group = table_[index];
        if (UNLIKELY(!group)) {
            group = insertEntry(lookup, index, rows[i]);
        }
        groups[rows[i]] = group;
    }
}

7.4 groupProbe kHash 路径

kHash 模式下，fullProbe<false> 模板参数 isJoin=false，insert 时调用 insertEntry()：

char* HashTable<ignoreNullKeys>::insertEntry(
    HashLookup& lookup, uint64_t index, vector_size_t row) {
    char* group = rows_->newRow();          // 从 RowContainer 分配新行
    lookup.hits[row] = group;
    storeKeys(lookup, row);                 // 把 key 列写入行
    storeRowPointer(index, lookup.hashes[row], group);  // 写 tag + 指针到 bucket
    if (hashMode_ == kNormalizedKey) {
        RowContainer::normalizedKey(group) = lookup.normalizedKeys[row];
    }
    ++numDistinct_;
    lookup.newGroups.push_back(row);        // 记录新行，供上层初始化 accumulator
    return group;
}

7.5 newGroups 的语义

lookup.newGroups 是 groupProbe 相对 joinProbe 独有的输出。上层（GroupingSet::addInput）用它区分：

newGroups 中的行：需要用当前 batch 的值初始化 accumulator（比如 sum 初始化为第一个值）
其余命中行：在已有 accumulator 上累加

8. Join 场景：Build 与 Probe

8.1 Join Build 全流程

HashBuild::addInput(batch)
    → rows_->store(keys + payloads)   // 全量写入 RowContainer，不建 hash index
         ↓
HashBuild::noMoreInput() → HashJoinBridge::setHashTable()
    → prepareJoinTable(otherTables, spillBit, maxDistinct)
         ├── 合并子表 VectorHasher（merge）
         ├── decideHashMode()
         └── rehash() → insertForJoin()

与聚合不同，join build 阶段先存储所有行，最后才建索引。这是因为直到所有行到来前，无法确定 VectorHasher 的完整 value_id 映射，而 kArray/kNormalizedKey 模式要求稳定的映射。

8.2 insertForJoin：重复 key 的链表处理

void HashTable<ignoreNullKeys>::insertForJoin(
    char** groups, const uint64_t* hashes, int32_t numGroups,
    TableInsertPartitionInfo* partitionInfo) {

    if (hashMode_ == kArray) {
        for (auto i = 0; i < numGroups; ++i) {
            arrayPushRow(groups[i], hashes[i]);  // 可能形成链表
        }
        return;
    }
    // kNormalizedKey 或 kHash：带 prefetch 的 buildFullProbe
    if (hashMode_ == kNormalizedKey) {
        insertForJoinWithPrefetch<true>(groups, hashes, numGroups, partitionInfo);
    } else {
        insertForJoinWithPrefetch<false>(groups, hashes, numGroups, partitionInfo);
    }
}

arrayPushRow()（HashTable.cpp:1394）处理 kArray 模式下的重复 key：

bool HashTable<ignoreNullKeys>::arrayPushRow(char* row, int32_t index) {
    auto existing = table_[index];
    if (nextOffset_) {
        // allowDuplicates=true：头插法建链表
        nextRow(row) = existing;      // 新行的 next → 旧行
        if (existing) hasDuplicates_.set();
    } else if (existing) {
        // allowDuplicates=false（left semi / anti join）：直接计数或丢弃
        if (rows_->countOffset() > 0) {
            rows_->addCount(existing, rows_->count(row));
        }
        return false;
    }
    table_[index] = row;  // 新行成为链表头
    return existing == nullptr;
}

pushNext()（kHash/kNormalizedKey 的重复处理）：

void HashTable<ignoreNullKeys>::pushNext(char* row, char* next) {
    hasDuplicates_.set();
    auto previousNext = nextRow(row);  // row 原来的 next
    nextRow(row) = next;               // row → next（头插到 row 之后）
    nextRow(next) = previousNext;      // next → 原来的 next
}

重复 key 形成单链表，链表头存储在 hash 槽中：

1	hash slot → row_A ─next→ row_B ─next→ row_C ─next→ nullptr

8.3 prepareForJoinProbe：probe 侧的快速剪枝

void HashTable<ignoreNullKeys>::prepareForJoinProbe(...) {
    // Step 1: 解码 + 去 null（可选，首次调用时做）
    if (decodeAndRemoveNulls) {
        for (auto& hasher : hashers) hasher->decode(*key, rows);
        deselectRowsWithNulls(hashers, rows);
    }

    // Step 2: 计算 hash 或 value_id
    for (auto i = 0; i < hashers.size(); ++i) {
        if (mode != kHash) {
            // lookupValueIds：如果 probe 值不在 build 侧 value_id 集合中
            // 则直接将该行从 rows 移除（剪枝）
            hashers_[i]->lookupValueIds(*key, rows, scratchMemory, lookup.hashes);
        } else {
            hasher->hash(rows, i > 0, lookup.hashes);
        }
    }
    populateLookupRows(rows, lookup.rows);
}

lookupValueIds 的剪枝效果在 TPCH Q3/Q5 等 selective join 场景非常显著——build 侧只有特定日期范围的订单，probe 侧日期范围不在其中的行可以立即跳过。

8.4 joinProbe 与 listJoinResults

joinProbe() 只填 hits[]，不处理链表（一个 probe key 可能匹配多行）：

void HashTable<ignoreNullKeys>::joinProbe(HashLookup& lookup) {
    // 每种模式找第一个命中行，存入 hits[row]
    // 链表的后续节点由 listJoinResults 负责遍历
}

listJoinResults()（HashTable.cpp:2085）分批生成输出，支持流量控制（maxBytes）：

int32_t HashTable<ignoreNullKeys>::listJoinResults(
    JoinResultIterator& iter, bool includeMisses,
    folly::Range<vector_size_t*> inputRows,
    folly::Range<char**> hits, uint64_t maxBytes) {

    // 无重复 key + 行大小可估算 → 走 SIMD 快路径
    if (iter.estimatedRowSize.has_value() && !hasDuplicates_) {
        return listJoinResultsFastPath(...);
    }

    while (iter.lastRowIndex < iter.rows->size()) {
        if (!iter.nextHit) {
            iter.nextHit = (*iter.hits)[row];  // 从 hits[] 取链表头
            if (!iter.nextHit) {
                if (includeMisses) { /* LEFT JOIN: 输出 null */ }
                continue;
            }
        }
        while (iter.nextHit) {
            // prefetch 下一个链表节点
            if (nextOffset_) {
                auto next = nextRow(iter.nextHit);
                if (next) __builtin_prefetch(next + nextOffset_);
            }
            // 输出当前命中
            inputRows[numOut] = row;
            hits[numOut]      = iter.nextHit;
            iter.nextHit      = nextRow(iter.nextHit);  // 跟链表前进
            ++numOut;
            if (numOut >= maxOut || totalBytes >= maxBytes) return numOut;
        }
    }
}

includeMisses 的语义：true 对应 LEFT/RIGHT OUTER JOIN（需要输出无匹配行），false 对应 INNER JOIN（跳过无匹配行）。

8.5 Right/Full Outer Join：listNotProbedRows

1 2	// 遍历 RowContainer，返回没有被 probe 过的行（build 侧无匹配行） int32_t listNotProbedRows(RowsIterator* iter, int32_t maxRows, ...);

hasProbedFlag 在 RowContainer 每行预留 1 bit，joinProbe 命中时设置该 bit。listNotProbedRows 通过 RowContainer::ProbeType::kNotProbed 过滤返回。

9. 并行 Join Build

9.1 触发条件

bool HashTable<ignoreNullKeys>::canApplyParallelJoinBuild() const {
    return isJoinBuild_                          // 必须是 join build
        && buildExecutor_ != nullptr            // 有可用的线程池
        && hashMode_ != kArray                  // array 模式无需并行（本身就是 O(1)）
        && !otherTables_.empty()               // 有多个子表（多线程 build 时）
        && (capacity_ / (1 + otherTables_.size())) > minTableSizeForParallelJoinBuild_;
        // 每个分区足够大才值得并行（默认 1000 行）
}

9.2 三阶段并行协议

阶段一：行分区（并行）

每个子表分配 RowPartitions（per-row uint8_t 数组）
并行线程：各子表 partitionRows() → 对每行计算 bucketOffset → 确定 partition 编号
          hash(row) → bucketOffset → findPartition(bucketOffset, bounds)
                                       ↑ SIMD 搜索分区边界数组
结果：rowPartitions[i][j] = row j 属于第几号分区

分区划分原则：

for (auto i = 0; i < numPartitions; ++i) {
    buildPartitionBounds_[i] =
        bits::roundUp(((sizeMask_ + 1) / numPartitions) * i, kBucketSize);
}

每个分区的 bucket 范围大小相等，且对齐到 kBucketSize（128 字节，即一个 bucket），确保不同分区的线程不会写同一个 bucket。

阶段二：分区内 build（并行）

每个线程处理属于自己 partition 的所有行（来自所有子表）:
    for each subtable:
        listPartitionRows(partition, ...) → 按 partition 枚举本分区的行
        insertForJoin(rows, hashes, &partitionInfo)
            └── buildFullProbe()
                    ├── bucket 在 partitionInfo 范围内 → 直接写槽
                    └── bucket 超出范围（overflow） → 加入 overflow 列表（保留 hash）

线程安全保证：同一时刻，对 hash 槽的写操作严格在各自的 bucket 范围内，天然无竞争。

阶段三：overflow 串行回填

for (auto i = 0; i < numPartitions; ++i) {
    auto& overflows = overflowPerPartition[i];
    auto& overflowHashes = overflowHashesPerPartition[i];
    // 复用阶段二保存的 hash，不重新计算
    insertForJoin(overflows.data(), overflowHashes.data(), overflows.size(), nullptr);
}

overflow 的产生原因：线性探测时，某个 key 的冲突链延伸超过了本分区的 bucket 范围边界。这些行必须等所有分区都完成后才能串行插入，以避免跨分区写冲突。

9.3 Bloom Filter 并行构建（可选）

当满足条件时（bloomFilterMaxSize_ > 0，key 列为整数类型），并行 build 还会额外构建每列的 Bloom filter：

阶段1（并行）：对每个子表的每列，按 bloom filter 分区枚举行
              → 写入 partitionBloomFilterRows（复用 rowPartitions）

阶段2（并行）：每个分区线程读本分区行的 key 值
              → buildBloomFilter() → 写入 BigintValuesUsingBloomFilter

完成后：VectorHasher::setBloomFilter(filter) 供 probe 侧提前过滤

Bloom filter 在 probe 侧的 lookupValueIds 之前做预判，在 build 侧 key 分布稀疏时（如日期 join）极大减少 probe 的无效工作。

9.4 并行度与同步

1
2
3

主线程：负责第 numPartitions-1 号分区（最后一个），不浪费当前线程
其余分区：由 buildExecutor_ 线程池异步执行
同步：folly::makeGuard + syncWorkItems() 等待所有 AsyncSource 完成

每个异步任务包装为 AsyncSource<bool>，主线程在 sync guard 析构时统一等待，并收集 CpuWallTiming。

10. Rehash 机制

10.1 触发时机

void HashTable<ignoreNullKeys>::checkSize(
    int32_t numNew, bool initNormalizedKeys, int8_t spillBit) {

    const int64_t newNumDistincts = numNew + numDistinct_;

    if (table_ == nullptr || capacity_ == 0) {
        // 首次分配：预估初始大小
        const auto newSize = newHashTableEntries(numDistinct_, numNew);
        allocateTables(newSize, spillBit);
        if (numDistinct_ > 0) rehash(initNormalizedKeys, spillBit);

    } else if (newNumDistincts > rehashSize()) {
        // 超过负载因子：扩容
        const auto newCapacity = bits::nextPowerOfTwo(
            std::max(newNumDistincts, capacity_ - numTombstones_) + 1);
        allocateTables(newCapacity, spillBit);
        rehash(initNormalizedKeys, spillBit);
    }
}

负载因子：kHashTableLoadFactor = 0.7，即 rehashSize = capacity * 0.7 - numTombstones。

tombstone 槽计入负载是因为它们会减慢 probe（必须跳过），累积过多时应触发 rehash 清除。

初始大小估算：

static uint64_t newHashTableEntries(uint64_t numDistincts, uint64_t numNew) {
    auto numNewEntries = std::max(
        (uint64_t)2048,
        bits::nextPowerOfTwo(numNew * 2 + numDistincts));  // 初始预估 2×
    if (numDistincts + numNew > rehashSize(numNewEntries)) {
        numNewEntries *= 2;
    }
    return numNewEntries;
}

最小 2048 槽（避免频繁 rehash），新批次数据量的 2 倍作为初始预估（假设下一批次数据量相当）。

10.2 allocateTables：表内存管理

void HashTable<ignoreNullKeys>::allocateTables(uint64_t size, int8_t spillBit) {
    VELOX_CHECK(bits::isPowerOfTwo(size));  // 必须是 2 的幂
    capacity_ = size;
    const uint64_t byteSize = capacity_ * tableSlotSize();  // capacity_ * 8
    VELOX_CHECK_EQ(byteSize % kBucketSize, 0);  // 必须是 bucket 大小的整数倍

    numTombstones_ = 0;          // 新表无 tombstone
    sizeMask_ = byteSize - 1;
    numBuckets_ = byteSize / kBucketSize;
    sizeBits_ = __builtin_popcountll(sizeMask_);  // 有效 bit 数（用于 mix）
    checkHashBitsOverlap(spillBit);   // 检查 bucket index 位域不与 spill 位域重叠

    bucketOffsetMask_ = sizeMask_ & ~(kBucketSize - 1);

    // 从 MemoryPool 分配 contiguous 内存（整页对齐）
    const auto numPages = memory::AllocationTraits::numPages(size * tableSlotSize());
    rows_->pool()->allocateContiguous(numPages, tableAllocation_);
    table_ = tableAllocation_.data<char*>();
    ::memset(table_, 0, capacity_ * sizeof(char*));  // 清零（全部空槽）
}

Spill 位域不重叠检查：

当 spill 启用时，hash 值的高位用于分区（spillInputStartPartitionBit 指定起始 bit），bucket 索引用低位。两者重叠会导致同一 spill 分区的数据只落入少数 bucket，造成严重不均匀：

void HashTable<ignoreNullKeys>::checkHashBitsOverlap(int8_t spillBit) {
    if (spillBit != kNoSpillInputStartPartitionBit && hashMode() != kArray) {
        VELOX_CHECK_LT(sizeBits_ - 1, spillBit,
            "size bits must be lower than spill partition bits");
    }
}

10.3 rehash 过程

void HashTable<ignoreNullKeys>::rehash(bool initNormalizedKeys, int8_t spillBit) {
    ++numRehashes_;

    // 优先走并行 build
    if (canApplyParallelJoinBuild()) {
        parallelJoinBuild();
        return;
    }

    raw_vector<uint64_t> hashes(pool_);
    hashes.resize(kHashBatchSize);
    char* groups[kHashBatchSize];

    // 遍历所有子表（this + otherTables_）的 RowContainer
    for (int32_t i = 0; i <= otherTables_.size(); ++i) {
        RowContainerIterator iterator;
        int32_t numGroups;
        auto* table = tableAt(i);
        do {
            numGroups = table->rows()->listRows(&iterator, kHashBatchSize, groups);
            if (!insertBatch(groups, numGroups, hashes,
                             initNormalizedKeys || i != 0)) {
                // value_id 映射失败 → 强制切换到 kHash
                VELOX_CHECK_NE(hashMode_, kHash);
                setHashMode(kHash, 0, spillBit);
                return;  // setHashMode 内部会重新 checkSize + rehash
            }
        } while (numGroups > 0);
    }
}

initNormalizedKeys 的含义：

true：重新从 key 列计算 normalized_key 并写入 row[-8]（例如 hashMode 刚切换时）
false：直接从 row[-8] 读取缓存的 normalized_key，用 mixNormalizedKey 得到 hash（更快）

第 2 个及以后的子表（i != 0）始终 initNormalizedKeys=true，因为它们的 VectorHasher 映射已合并到主表，需要重新编码。

10.4 模式切换引发的 rehash 链

setHashMode(kArray):
    allocateTables(capacity_)     // 用已有 capacity_（kArray 下是 value_id 数量）
    rehash(initNormalizedKeys=true)

setHashMode(kHash):
    for hasher: hasher.resetStats()  // 清空所有 value_id 映射
    rows_->disableNormalizedKeys()   // 释放 row[-8] 空间
    capacity_ = 0                    // 强制重新分配
    checkSize(numNew, ...)           // 按 kHash 大小重分配 + rehash

setHashMode(kNormalizedKey):
    capacity_ = 0
    checkSize(numNew, ...)

11. Erase 与 Tombstone

11.1 tombstone 的必要性

开放地址 hash 表中，删除一个已有条目不能简单地置空，因为这会截断正在查找的探测链。标准做法是写入 tombstone（逻辑删除标记）：

tag 值	语义	probe 行为	insert 行为
0x00	空槽	停止探测（miss）	可写入
0x7F	tombstone	跳过继续探测	记录位置，探测结束时写入
≥0x80	有效	比较 key	若 key 相同则更新

tombstone 的高位为 0（与有效 tag 的高位 1 区分），但不等于 0x00（与空槽区分）。

11.2 eraseHit：写入 tombstone 或直接清空

template <typename Table>
void ProbeState::eraseHit(Table& table, int64_t& numTombstones) {
    const auto kEmptyGroup = BaseHashTable::TagVector::broadcast(kEmptyTag);
    // 检查当前 bucket 是否有空槽
    const bool hasEmptyGroup = simd::any(tagsInTable_ == kEmptyGroup);

    table.bucketAt(bucketOffset_)->setTag(
        indexInTags_,
        hasEmptyGroup ? 0 : kTombstoneTag);  // 有空槽→置空，无空槽→tombstone
    numTombstones += !hasEmptyGroup;
}

关键优化：如果 bucket 内已有空槽，说明这条探测链在这里可以”自然终止”，此时删除后的槽可以直接置空（而非 tombstone）——因为任何从这个 bucket 之前开始的探测，遇到空槽都会停止，不存在被截断的链。

11.3 erase 完整流程

void HashTable<ignoreNullKeys>::erase(folly::Range<char**> rows) {
    // Step 1: 重新计算被删除行的 hash
    for (int32_t i = 0; i < hashers_.size(); ++i) {
        if (hashMode_ == kHash) {
            rows_->hash(i, rows, i > 0, hashes.data());
        } else {
            hasher->computeValueIdsForRows(..., hashes);
        }
    }

    // Step 2: 对 kNormalizedKey 模式，mix hash
    if (hashMode_ == kNormalizedKey) {
        for (auto i = 0; i < numRows; ++i) {
            hashes[i] = mixNormalizedKey(hashes[i], sizeBits_);
        }
    }

    // Step 3: 通过 ProbeState::kErase 操作找到并删除 hash 槽
    ProbeState state;
    for (auto i = 0; i < numRows; ++i) {
        state.preProbe(*this, hashes[i], i);
        state.firstProbe<kErase>(*this, 0);
        state.fullProbe<kErase>(*this, 0,
            [&](const char* group, int32_t row) { return rows[row] == group; },
            ...);
    }

    numDistinct_ -= numRows;

    // Step 4: 从 RowContainer 删除行（释放 payload 内存）
    rows_->eraseRows(rows);
}

erase 主要用于 spill 场景：当内存压力触发 spill 时，HashBuild 把属于某个 spill 分区的行逐出到磁盘，同时从 hash 表中 erase 这些行。

12. 与上层算子的接口

12.1 聚合算子（GroupingSet / HashAggregation）

GroupingSet::addInput(batch)
    prepareForGroupProbe(lookup, batch, rows, spillBit)
    groupProbe(lookup, spillBit)
    → 对 lookup.hits[row] 更新 accumulator
    → 对 lookup.newGroups 初始化 accumulator

GroupingSet::extractResult()
    HashTable::listAllRows() → 枚举全部行
    → 提取 key 列 + accumulator 结果

部分 flush（partial group by）：

1 2	// 不释放 table_，仅清空 RowContainer 内容和 numDistinct_ hashTable_->clear(/freeTable=/false);

12.2 Join Build 算子（HashBuild）

HashBuild::addInput(batch)
    rows_->store(batch)   // 仅追加到 RowContainer，不建索引
    （对 left-semi/anti join：allowDuplicates_=false 时也在此建部分索引去重）

HashBuild::noMoreInput()
    HashJoinBridge::setHashTable(table_, otherTables)
    prepareJoinTable(otherTables, spillBit, maxDistinct, dropDuplicates)
        merge VectorHashers → decideHashMode → rehash/parallelJoinBuild

HashBuild::addRuntimeStats()  // 上报 hashtable.capacity 等指标

12.3 Join Probe 算子（HashProbe）

HashProbe::addInput(batch)
    prepareForJoinProbe(lookup, batch, rows, decodeAndRemoveNulls)
        → VectorHasher::lookupValueIds (kArray/kNormalizedKey: 剪枝)
        → VectorHasher::hash (kHash)
    joinProbe(lookup)
        → lookup.hits[row] = 第一个命中的 build 侧行指针

HashProbe::getOutput()
    listJoinResults(iter, includeMisses, ...)  // 按 maxBytes 分批
        → 遍历 next 链表，支持 1:N
    → 输出 probe 列 + build 列

// RIGHT / FULL OUTER JOIN 的额外阶段:
HashProbe::getOutput() after probe done:
    listNotProbedRows(iter, ...)  // 枚举 build 侧未被 probe 到的行
    → 输出 null probe 列 + build 列

12.4 Runtime 统计指标

HashTable 向算子暴露以下运行时指标（addRuntimeStats()）：

指标名	含义
`hashtable.capacity`	hash 槽总数
`hashtable.numDistinct`	实际存储的不重复 key 数
`hashtable.numRehashes`	rehash 发生次数
`hashtable.numTombstones`	当前 tombstone 槽数
`hashtable.hashMode`	当前模式（0=kArray, 1=kNormalizedKey, 2=kHash）
`hashtable.buildWallNanos`	build 阶段耗时
`hashtable.parallelJoinBuildWallNanos`	并行 build 耗时
`hashtable.cacheHit` / `cacheMiss`	HashTableCache 命中情况

13. 设计哲学与架构精髓

前文 11 章自下而上拆解了实现细节。本章自上而下回到设计层面，回答一个核心问题：为什么是这套架构而不是别的？

13.1 六条贯穿全局的设计原则

（1）数据驱动的特化（Adaptive Specialization）

不为通用性付出不必要的代价。HashTable 维护三套并存的实现路径——kArray（完美哈希）、kNormalizedKey（多列融合）、kHash（通用兜底），decideHashMode() 根据当次数据的 range / distinct 统计在运行时选择。低基数列享受 O(1) 数组寻址，高基数列回退到通用哈希。这种”按需付费”的思路贯穿全表（VectorHasher 的 range vs distinct、fullProbe<op> 的 probe vs insert vs erase 模板分发都是相同思路的体现）。

（2）缓存意识（Cache-Conscious Layout）

一切布局决策围绕”一次 cache miss ≈ 100ns ≈ 数百 cycle”展开。一个 Bucket 恰好 128B = 2 cache line（§4.2），tag 区独立打包成 16B 让 SIMD 一次扫完，pointer 区延迟到确认命中才读。Rehash 以 1024 行为批次（kHashBatchSize）也是为了让 RowContainer 的扫描局部性化。

（3）延迟隐藏（Latency Hiding via Pipelining）

DRAM 延迟无法消除，只能掩盖。从最细粒度的 __builtin_prefetch 到 4-路 ProbeState 软流水线（§6.3），再到 64-路 normalized key probe（§6.4），最后到 AdaptivePrefetch 自适应步长（§6.5）——多个层次同时在尝试让”等内存”的时间被有用工作填满。

（4）位级精细化（Bit-Level Discipline）

每一个 bit 都有用途、有理由。Hash 值的位域被精确切分：bit 7~~22 选 bucket、bit 38~~44 做 tag（§4.2）；| 0x80 强制 tag bit 7 = 1 与特殊标记错开（§4.2）；指针压缩到 6 字节是因为 x86-64 用户态地址只用 48 bit（§4.2）。每一处都是为了榨干硬件的最后一点效率。

（5）统一核心，多用途分发（One Core, Many Uses）

ProbeState::fullProbe<op> 模板是 probe / insert / erase 三种操作的共享内核。<op> 模板参数让编译器为每种用途生成独立的二进制路径，但源码只有一份。HashTable<ignoreNullKeys> 通过模板让 null-aware join 与普通 join 在编译期完全分离，if constexpr (ignoreNullKeys) 让无关分支彻底消失。

（6）列向量 ↔ 行容器的桥接（Vector/Row Bridge）

数据进入时是列存（Vector），但 hash 表必须是行存（同一 key 的所有列需要在邻近内存）。VectorHasher（§5）承担这个桥接：probe 路径上做向量化 value_id 计算，build 路径上做 row 写入和 normalized key 编码。它的存在让 hash 表既能与 Velox 的向量化执行框架无缝衔接，又能在内部走最优的行式探测。

13.2 决定整体结构的几个关键约束

约束	直接结果
Key 类型差异巨大（int/string/struct）	必须有通用兜底 → kHash 模式
数据库 workload key 基数双峰分布	必须为低基数特化 → kArray / kNK 模式
现代 CPU 缓存层次	Bucket 必须对齐 cache line
DRAM 延迟 ~100ns >> L1 hit ~1ns	必须隐藏延迟 → prefetch + 软流水线
数据库表行数动辄上亿	必须并行 build → partition 化
Spill 场景需从 hash 表逐出行	必须支持 erase → tombstone
多列 key 是常态	必须支持多 hasher 协同 → VectorHasher 融合

每一个约束都映射到一个或多个具体设计点，反过来也能从设计点逆向理解约束。

13.3 几个核心决策的”为什么”

A. 为什么选开放地址，而非链表法？

链表法（每个 hash 槽 → entry 链表）：

每个新 entry 单独 malloc → 散落堆上 → 几乎每次链表遍历都 cache miss
链表节点本身有 next 指针的额外开销
难以向量化

开放地址（所有 entry 都在 hash 表数组内部）：

同一 bucket 的所有候选 slot 连续 → cache 友好
与硬件 prefetcher 顺序访问模式协同
唯一缺点是 cluster 时退化为线性扫描——但 bucket 化把扫描单位变成 16 个 slot 一组，配合 SIMD 后退化代价被压到接近零

B. 为什么 “Bucket = 16 slot” 而非 8 或 32？

Bucket size	tag 区	SIMD 寄存器	cache line
8 slot	8B	浪费 xmm 一半	1 cache line
16 slot	16B	正好填满 xmm（128bit）	2 cache line
32 slot	32B	需要 ymm（AVX2）	4 cache line

16 是与 SSE2 xmm 寄存器宽度（128bit）对齐的最自然选择，同时让 bucket = 2 cache line（128B）保持紧凑。32 需要 AVX2、内存放大率更高，且 16 路已经把 single-bucket 探测降到 2 条指令（PCMPEQB + PMOVMSKB），再扩大收益边际递减。

C. 为什么 tag 和 pointer 分离存储？

如果把 (tag, pointer) 交错放：

1	[tag0\|ptr0][tag1\|ptr1]...[tag15\|ptr15] // 交错布局

读 16 个 tag 需要 16 次步长为 7 的离散访问，无法 SIMD 一次性加载。

分离存放：

1	[tag0,tag1,...,tag15] [ptr0,ptr1,...,ptr15] [padding] // 分区布局

读 16 个 tag 是一次连续 _mm_loadu_si128（16B），pointer 加载推迟到确认 tag 匹配后才发生——既让 SIMD 比较成为可能，又减少了无用的内存读。

这是 F14 / Swiss table 的核心创新，Velox 完全沿用并向量化。

D. 为什么用 6-byte（48-bit）指针？

指针宽度	16 指针总大小	bucket 总大小	cache line
8 byte	128B	16B tag + 128B ptr = 144B	跨 3 cache line
6 byte	96B	16B + 96B + 16B pad = 128B	整齐 2 cache line
4 byte	64B	16B + 64B = 80B	浪费物理地址空间

x86-64 用户空间虚拟地址只用低 48 bit，高 16 bit 必为 0（5-level paging 也只用到 57 bit）。压缩到 6 byte 在不丢信息的前提下让 bucket 完美对齐 128B。

E. 为什么 hashMode 需要三档？

数据库 group by / join 的 key 基数分布是典型的双峰：

基数： 1 ──── 100K ──────── 10M+
       ↑        ↑              ↑
    维度表    中等基数        事实表
       ↓        ↓              ↓
   kArray  kNormalizedKey   kHash

一档（只有 kHash）：低基数列也走通用 MurmurHash，多列也要逐列比较，每次 probe 都是 cache miss + 函数调用
两档（kArray + kHash）：跨过 2M 阈值就跌到 kHash，损失多列融合的中等基数场景
三档：覆盖所有典型 workload，每档都贴近其最优实现

代价是 decideHashMode() 的 7 步决策逻辑（§3.1），但这部分代码只在 build 阶段执行一次，摊销到亿级 probe 上忽略不计。

F. 为什么是 7-bit tag 而非 8-bit？

8-bit tag 意味着 256 个可能值都”有效”，无法保留特殊标记。

7-bit + 高位 1 给了 128 个有效值（0x80~0xFF），同时让 0x00（empty）和 0x7F（tombstone）有完整不冲突的特殊值域 [0x00, 0x7F]。

代价是 tag 碰撞率从 1/256 升到 1/128 —— 但 tag 碰撞只触发一次 row 加载和 key 比较，是性能而非正确性问题，且 1/128 仍然足够低。

G. 为什么 Join Build 要分”先 store 后 index”两阶段？

如果在 addInput 时立即建索引：

此时还不知道全量数据 → 无法决定 hashMode → 只能走 kHash 兜底
但 kHash 对低基数 join 性能差，错失 kArray / kNK 的优化机会

延迟到 noMoreInput 才 prepareJoinTable：

已收集所有 VectorHasher 的 range / distinct 统计
可以正确选择 kArray / kNormalizedKey
代价是 RowContainer 临时占用更多内存（但反正最终也要存）

这是用空间换最优形态的典型例子。

H. 为什么并行 Build 用 partition-then-merge？

锁方案在亿级行规模下不可行（每行至少一次 atomic CAS ≈ 数十 ns × 10⁸ ≈ 数秒纯开销）。

Partition 方案（§9.2）：

预处理：把 bucket 地址范围划分为 N 个 partition，每 partition 一个线程
执行  ：每个线程只写自己 partition 内的 bucket → 零同步
边界  ：跨 partition 探测溢出的行进入 overflow 列表
回填  ：所有 partition 完成后，主线程串行处理 overflow（量小）

代价是分两次扫描（partition 标记 + 实际写入）和 overflow 处理的复杂度，但换来主路径完全无锁。

I. 为什么 erase 写 Tombstone 而非置空？

开放地址表中，key A 探测时可能因 bucket 满而跨入下一个 bucket。如果中间某个槽（含 key B）被简单置空，A 的探测在这里就误判为 miss —— 即使 A 实际存在于更远的 bucket。

Tombstone 是”已删除但探测应继续”的标记。eraseHit() 的优化是：如果当前 bucket 还有空槽，说明探测链本来就在这个 bucket 内自然终止，删除后置空与置 tombstone 等价——此时选择置空，避免 tombstone 累积（§11.2）。

13.4 多层并发：从指令级到任务级

Velox HashTable 的”并行”在五个层次同时展开，每层独立优化、互不冲突：

层次	机制	时间尺度	相关章节
指令级（SIMD）	PCMPEQB 一条指令 16-way 比较	1 cycle	§6.2
微架构（OoO + prefetch）	`__builtin_prefetch` 让 cache 加载与计算并行	~10 cycle	§6.2
循环级（软流水线）	4-way / 64-way ProbeState 交错三阶段	~100 cycle	§6.3, §6.4
线程级（partition）	多线程 build 不相交 bucket 范围	ms 级	§9
算子级（异步）	HashBuild ↔ HashProbe 通过 HashJoinBridge 异步衔接	s 级	§12

单线程内的 SIMD / 软流水线在每个并行 partition 内部仍然有效——五层叠加而非互斥。任何单层只能贡献 2-3x 加速，但五层组合后端到端可达数十倍。

13.5 借鉴、创新与权衡

直接借鉴：

**F14 (Folly)**：bucket 化布局、tag / pointer 分区
**Swiss tables (Abseil)**：7-bit tag + 高位标志位 + SIMD 比较
学术 hash join 论文（Schuhknecht / Balkesen 等）：软件流水线 prefetch

Velox 在此之上的创新：

三模式自适应：根据数据分布在运行时选择 kArray / kNK / kHash，业界少见
VectorHasher 桥接：把”列向量批处理”与”行表 hash 索引”无缝衔接
64-way join probe prefetch：在 normalized key 场景把流水线深度推到 64
partition-then-merge 并行 build：完全无锁的多线程 build
lookupValueIds 剪枝：probe 侧在 hash 之前用 build 侧的 value_id 集合过滤一遍，在 selective join 中能提前丢掉大量行

关键权衡：

内存 vs 速度：tag + 6-byte 压缩指针保持单 slot 8 字节无放大；但 kNK 的 normalized_key 缓存占用 row 前 8 字节
简单性 vs 灵活性：模式切换不可回退（kArray → kHash 后无法回到 kArray），换取状态机简洁
吞吐 vs 内存：Tombstone 占用槽位拖累 probe，通过把 numTombstones 计入负载因子触发 rehash 来限制累积
代码复杂度 vs 性能：软流水线增加代码复杂度，用模板和 helper 类（ProbeState）局部化复杂度

13.6 一句话总结

数据决定形态，硬件决定布局，组合决定性能。

数据决定形态：kArray / kNormalizedKey / kHash 三态由数据分布自适应选择
硬件决定布局：Bucket = 2 cache line、tag 16B 对齐 xmm、指针 48bit 对齐物理地址空间
组合决定性能：SIMD + 软流水线 + prefetch + partition 并行，五层叠加才是最终吞吐

每一项决策单看都是已知技巧，但能够把六条设计原则、五个并发层次、三种 hash 模式、九项 SIMD 技巧正交地组合在一份不到 3000 行的实现里——这才是 Velox HashTable 真正优雅的地方。

14. 代码品味：值得学习的工程细节

前面 12 章讲了做什么和为什么。本章只谈怎么写——从代码 craft 的角度，挑出 Velox HashTable 实现中最值得学习的写法习惯，每条都对应到源码中的具体位点。

14.1 使非法状态不可表达（make illegal states unrepresentable）

hashTag() 的 | 0x80 是教科书级例子：

1	return static_cast<uint8_t>(hash >> 38) \| 0x80;

不写成 if (tag == 0 || tag == 0x7F) tag = 0x80;——而是让有效 tag 的值域根本不可能与特殊标记重叠。整个 probe 循环里再也不需要”这个 tag 是不是 special 值”的检查，因为类型本身已经保证了。

通用启示：遇到要加 if-check 才能保证正确性的地方，先问：能不能让那个 if 永远为真？通过类型/编码层面把不可能性”焊死”，是最经济的”检查”。

14.2 单向状态转移

HashMode 只能 kArray → kNormalizedKey → kHash 一路降级，永不回头：

1	// setHashMode 没有 kHash → kArray 的路径

代价是某次插入异常后即使数据后来变”好”也回不到 kArray。但状态机从 6 条边降到 3 条边，所有”会不会回退”的边界推理消失。

类似地，hasDuplicates_ 是 once-set flag——一旦发现重复 key 就置 1，再也不清空。读到这种”单调标志”几乎可以放心当不变量用。

14.3 模板单态化代替运行时分支

fullProbe<Operation op>(...) 一份源码，编译期展开成三份独立二进制：

1
2
3

fullProbe<kProbe>(...)
fullProbe<kInsert>(...)
fullProbe<kErase>(...)

源码统一，CPU 上跑的是无分支的特化路径。比 switch(op) 漂亮的是：连分支预测错失的可能性都没有了。

HashTable<bool ignoreNullKeys> 同样手法——if constexpr (ignoreNullKeys) 让无关代码彻底消失，而不是变成永不执行的死分支。Profiler 看到的指令完全是这条路径实际跑的代码，没有死分支干扰分析。

14.4 API 切分匹配硬件，而非代码可读性

ProbeState 切成三个阶段：

1
2
3

preProbe(hash, row);    // 触发 prefetch，不读
firstProbe(firstKey);   // 读 16 个 tag，做 SIMD 比较
fullProbe<op>(...);     // 比 key，可能跨桶

如果只看代码可读性，合并成一个 probe() 调用更短。但这种切分是为了让调用方能在中间插入别的工作——4-路软流水线就是把 state1.preProbe(); state2.preProbe(); ... ; state1.firstProbe(); ... 交错起来。

接口边界要切在能让上层做有用事情的位置，不是切在”代码上看着干净”的位置。

14.5 值语义的状态机栈对象

ProbeState 是个有 7 个字段的 C++ 类，但永远不在堆上分配：

1
2
3

ProbeState state1, state2, state3, state4;  // 全在栈
state1.preProbe(...);
// ...

字段总大小约 40 字节，能完全放进寄存器。用 class 组织相关字段（避免 7 个零散局部变量），又用栈分配 + 值语义避免堆分配开销——是介于”全局可见的复杂类”和”一堆裸局部变量”之间的甜点。

14.6 命名映射动词，读起来像故事

挑几个 method 名：

arrayPushRow         pushNext        eraseHit
loadNextHit          listJoinResults populateNormalizedKeys
preProbe / firstProbe / fullProbe
decideHashMode       canApplyParallelJoinBuild

全是主动态动词 + 直接对象。读 pushNext(row, next) 一眼知道是把 next 插到 row 之后；读 eraseHit() 知道是删除已命中的 entry。

CLAUDE.md 里写过：”Start comments with active verbs.”——代码也一样，每个函数名应该读起来像一个动作。

14.7 注释只解释”为什么”，不解释”什么”

最典型的例子：

__attribute__((__no_sanitize__("thread")))
static TagVector loadTags(uint8_t* tags, int64_t tagIndex) {
  // 并行 build 时各线程写不相交的 bucket 范围，但 TSAN 无法理解这种模式
  ...
}

注释里没有”加载 16 个 tag”——这从函数名就看得出来。注释解释的是 __no_sanitize__ 这个非常规属性为什么必须加。

另一个例子是 6-byte 指针的”越界读”：注释告诉你为什么这看似越界的代码是安全的——这是审稿人最容易标红的代码模式，作者主动给出豁免理由。

14.8 小类一事一做

AdaptivePrefetch.h 全文 71 行，一个类，5 个常量，3 个方法。它没有跑去管”prefetch 什么地址”，调用方自己决定。职责单一到一句话能讲完：根据前 16 次迭代实测耗时，决定一个固定步长。

这种”小到不可分割”的类比一个塞满 helper 方法的 PrefetchUtils.h 强一万倍——CLAUDE.md 里被明确禁止：”Never name a file or class *Utils, *Helpers, or *Common.”

14.9 魔法数字一律命名化

static constexpr int32_t kBucketSize = 128;
static constexpr int32_t kPointerSize = 6;
static constexpr int64_t kAssumedDramLatencyNs = 100;
static constexpr int32_t kPrefetchSize = 64;
static constexpr int32_t kHashBatchSize = 1024;
static constexpr double  kHashTableLoadFactor = 0.7;
static constexpr uint64_t kArrayHashMaxSize = 2L << 20;

代码里没有一处直接写 128 或 0.7。kAssumedDramLatencyNs = 100 这个命名尤其妙——它不仅告诉你”这是 100ns”，还告诉你”这是个假设值”，提醒读者它不是从硬件读出来的真实测量。

14.10 失败模式编码进返回值，而非异常

bool computeValueIds(rows, hashes);
// 返回 false 表示"value_id 空间满了，请切到 kHash"

bool insertBatch(groups, num, hashes, init);
// 返回 false 表示"需要降级 hashMode 重来"

没有抛异常，没有 out-param 错误码——就一个 bool，调用方按”成功 / 该换种思路了”二分处理。

异常在 hot path 上既贵又难以推理；error code 又比 bool 重。当语义就是二元的（成功/换种思路）时，bool 是最诚实的接口。

14.11 不为不存在的情况加防御性代码

pushNext() 的实现：

void pushNext(char* row, char* next) {
  hasDuplicates_.set();
  auto previousNext = nextRow(row);
  nextRow(row) = next;
  nextRow(next) = previousNext;
}

没有 if (row == nullptr) return;，没有 assert(next != row)，没有 VELOX_CHECK(nextOffset_ > 0)。因为调用方上下文已经保证：调到 pushNext 时一定是已经命中了 row，next 是新行，nextOffset_ 一定是正的。

这不是偷懒，而是对调用契约的尊重。每一个不必要的 check 都是在告诉读者”这里其实不放心”，反而让真正需要 check 的地方失去信号。

VELOX_CHECK 在 Velox 代码里只出现在跨模块边界和侵蚀性 bug 的早期捕获，不出现在内部 hot path。

14.12 `if constexpr` 让特性”消失”而非”禁用”

template <bool ignoreNullKeys>
void prepareForGroupProbe(...) {
  if constexpr (ignoreNullKeys) {
    deselectRowsWithNulls(hashers, rows);
  }
  // ...
}

if (ignoreNullKeys_) 也能工作，但生成的二进制里那条分支永远存在。if constexpr 在编译期就消除了整个分支——HashTable<true> 的二进制里根本看不到 deselectRowsWithNulls 的调用。

14.13 一句话总结

品味好的代码不是没有 trick，而是每个 trick 都有一行能写下的理由。

Velox HashTable 用了大量看似”花哨”的手法（template 单态化、越界读 + mask、模式不可回退、栈上状态机）。但每一处都能用一行话讲清楚为什么这么写、不这么写会失去什么。不存在”反正能 work”的代码，也不存在”以防万一”的代码——这是它真正值得学习的地方。

15. 位操作精解

HashTable 的实现里位操作出现频率极高——hash 切片、容量掩码、bitmask 迭代、压缩指针读写都靠位操作支撑。本章把分散在各处的位技巧梳理成 6 类，每类从源码找具体调用点对照。

15.1 位域提取：从单个整数切出多块信息

64-bit hash 同时承载 tag 和 bucket 索引两份信息：

// 取 hash 的 bit 38-44 做 tag
static uint8_t hashTag(uint64_t hash) {
    return static_cast<uint8_t>(hash >> 38) | 0x80;
}

// 取 hash 的低位（bit 7~22 当 capacity=2^20）做 bucket 偏移
int64_t bucketOffset(uint64_t hash) const {
    return hash & bucketOffsetMask_;
}

// 取 bucket 内的 slot 索引（bit 0-3）
int32_t slotIndex = index & (sizeof(TagVector) - 1);  // & 15

位图：

bit:  63          44   38         22         7  3      0
      ┌──────────┬─────┬──────────┬──────────┬──┬──────┐
hash: │  unused  │ tag │  unused  │  bucket  │..│ slot │
      └──────────┴─────┴──────────┴──────────┴──┴──────┘
                   ↓                 ↓             ↓
              >>38 | 0x80    & bucketOffsetMask  & 15

为什么 tag 与 bucket 必须用不同位段？

如果都用同一段 bit：bucket 内 16 个 slot 的 tag 高度相关（最坏全相同）→ SIMD 比较退化为”几乎全命中”→ 每次 probe 都要逐个加载 row 比 key → SIMD 加速失效。

取 bit 38-44 与 bit 7-22 让 tag 和 bucket 落在 hash 的不同位段，统计独立。

15.2 2 的幂技巧：模运算的零开销实现

整张 hash 表的容量始终是 2 的幂，这是位操作能用的根本前提：

1	VELOX_CHECK(bits::isPowerOfTwo(size));

14.2.1 `x & (n - 1)` 等价于 `x % n`（当 n 是 2 的幂）

1 2	sizeMask_ = byteSize - 1; // 全 1 mask int32_t slotIndex = index & 15; // 对 16 取模

% 在 CPU 上要 20+ cycle（除法器）；& 是 1 cycle。

14.2.2 `x & ~(N - 1)` 等价于”向下对齐到 N 的倍数”

1 2	bucketOffsetMask_ = sizeMask_ & ~(kBucketSize - 1); // 等价于：抹掉低 7 bit，保留 128 字节对齐

14.2.3 `bits::nextPowerOfTwo` 与 `popcount`

1	sizeBits_ = __builtin_popcountll(sizeMask_);

sizeMask_ 是全 1，popcount 等于有效 bit 数（如 capacity=2^20 时 sizeBits_=23）。这个值用在 mixNormalizedKey 里做位混淆。

14.2.4 `isPowerOfTwo` 的位操作判定

1	bool isPowerOfTwo(uint64_t x) { return x && !(x & (x - 1)); }

x 是 2 的幂 ⇔ 二进制只有一个 1 bit ⇔ x & (x-1) 清掉那个 bit 后等于 0。

14.2.5 向上对齐：`bits::roundUp(x, k)`

当 k 是 2 的幂：

1	roundUp(x, k) = (x + k - 1) & ~(k - 1)

并行 build 的分区边界用它对齐到 kBucketSize：

1	buildPartitionBounds_[i] = bits::roundUp((sizeMask_ + 1) / N * i, kBucketSize);

15.3 位域写入：保留无关位

6 字节指针存储要写 6 字节进 8 字节的空间，但不能破坏隔壁的 2 字节：

void setPointer(int32_t slotIndex, void* pointer) {
    auto* slot = reinterpret_cast<uintptr_t*>(&pointers_[slotIndex * 6]);
    *slot = (*slot & ~kPointerMask) | reinterpret_cast<uintptr_t>(pointer);
    //       ↑保留 mask 外的位          ↑写入 mask 内的位
}

*slot & ~kPointerMask 取出高 2 字节的原始值；| ptr 把指针填进低 6 字节。这是典型的位字段写入模式，适用于任何需要在共享 word 里更新部分 bit 的场景。

对比简单写入：

1 2	*slot = (uintptr_t)pointer; // ❌ 会把隔壁 2 字节写成 0 memcpy(slot, &pointer, 6); // ✅ 但每次走函数调用

位操作版本编译后是 3 条指令：load + and + or，最快。

15.4 Bitmask 迭代：从 SIMD 结果逐个取命中

SIMD 比较返回 16-bit 整数，每 bit 对应一个 slot。逐个取出每个命中 slot 是位操作的密集舞台：

while (hits_ > 0) {
    int32_t hit = bits::getAndClearLastSetBit(hits_);
    // 处理 slot hit
}

14.4.1 `getAndClearLastSetBit` 拆解

template <typename T>
int32_t getAndClearLastSetBit(T& bits) {
    int32_t bit = __builtin_ctzll(bits);  // 找最低 set bit 的位置
    bits &= bits - 1;                      // 清最低 set bit
    return bit;
}

虽然名字是 “last”，实际取的是最低位（ctz = count trailing zeros）。

14.4.2 `bits & (bits - 1)` 清最低 set bit（Kernighan’s trick）

bits     = ...1000   (8 = 1000)
bits - 1 = ...0111   (7 = 0111)
AND      = ...0000   ← 最低 set bit 已清

bits     = ...1010   (10 = 1010)
bits - 1 = ...1001   (9 = 1001)
AND      = ...1000   ← 只清最低 set bit

原理：减 1 把最低 set bit 翻成 0、其右侧所有 0 翻成 1；AND 一下就清掉了那个 bit。

为什么不写 bits ^= (1 << bit)？理论上等价，但 bits & (bits - 1) 不依赖 bit 这个中间变量——CPU 可以与 ctz 的计算并行执行（OoO 调度），少一个数据依赖。

14.4.3 硬件指令对应

内建函数	x86	ARM	cycle
`__builtin_ctz`	BSF / TZCNT (BMI1)	RBIT + CLZ	3-4
`__builtin_clz`	BSR / LZCNT	CLZ	3-4
`__builtin_popcount`	POPCNT (SSE4.2)	CNT (NEON)	3

比循环移位测试快两个数量级。

15.5 SIMD → Scalar 桥接：PMOVMSKB

PMOVMSKB 是 SIMD 比较与 scalar bitmask 之间的桥梁：

__m128i tags  = [t0, t1, ..., t15]     // 16 字节 SIMD 向量
__m128i mask  = [0xFF or 0x00 ...]      // PCMPEQB 比较结果
uint16_t bits = PMOVMSKB(mask)          // 取每字节最高位 → 16-bit scalar
              = 0b...1010               // 哪些 slot 匹配

为什么是”取最高位”？ PCMPEQB 输出 16 个 0xFF / 0x00，每字节要么全 1 要么全 0。最高位（bit 7）已经携带”是否匹配”的完整信息，其余 7 bit 是冗余的。

这正好与 tag 的 | 0x80 设计协同：tag 高位恒为 1 时（有效），PMOVMSKB(tags) 直接给出”哪些 slot 有效”，省去一次与 0x00 的显式比较（§6.9 的优化）。

15.6 最高位作为类型标签

tag & 0x80 / PMOVMSKB 在 Velox HashTable 里至少有三处用法：

// 1. 编码层面保证不变式（§4.2）
return (hash >> 38) | 0x80;          // hashTag 永远 >= 0x80

// 2. SIMD 批量提取所有有效槽（§6.9）
free = ~PMOVMSKB(tags) & kFullMask;

// 3. 与 PCMPEQB 协同：tag 高位恒 1 → PMOVMSKB 直接区分有效/无效

MSB 作为类型标签是位操作中最经济的元数据携带方式：1 bit 信息不占额外存储空间，且 & 0x80、>> 7、< 0（signed）几种测试方式都只要 1 cycle。

15.7 散落的位掩码构造

**bits::lowMask(n)**：(1ULL << n) - 1，得到低 n bit 全 1 的 mask
kPointerMask = bits::lowMask(48) = 0x0000FFFFFFFFFFFF：6 字节指针的有效位掩码
kFullMask = (1 << kSlotsPerBucket) - 1 = 0xFFFF：16 个 slot 的全 1 掩码，限定 bitmask 范围

15.8 位操作小总结

按”频次 × 重要性”排序，HashTable 中最关键的 6 个位操作模式：

模式	代码片段	用途
位段提取	`(x >> shift) & mask` 或 `(x >> shift) \| flag`	hashTag, slotIndex
2 幂取模	`x & (n - 1)`	bucketOffset, slotIndex
向下对齐	`x & ~(N - 1)`	bucketOffsetMask 构造
位字段写入	`(slot & ~mask) \| value`	setPointer
找最低 set bit	`__builtin_ctz(bits)`	bitmask 迭代
清最低 set bit	`bits &= bits - 1`	bitmask 迭代

调试建议：

用 std::bitset<N>(value).to_string() 打印 bit 模式，比 hex 直观
关键 mask 用 static_assert 固化语义：

1 2	static_assert((kPointerMask & 0xFFFF000000000000) == 0, "kPointerMask must not touch high 16 bits");

位段提取永远写成命名函数（hashTag()、bucketOffset()），不在调用点直接写 >> 38 | 0x80——否则一年后没人记得”38”是什么

16. 五个维度的设计品味总览

前面的章节按”实现模块”组织（内存布局、SIMD、并行 build 各自成章）。本章换一个切面，按五个横贯全局的技术维度重新审视，每个维度都从两个角度发问：

架构品味：这个维度上的设计决策，体现了什么样的系统级取舍？
代码品味：落到具体代码，工程师用什么手法把这个决策表达得既正确又优雅？

五个维度不是孤立的——它们最终都收敛到同一句话：让数据结构的形态贴合硬件的脾气。

16.1 位操作（Bit Operations）

架构品味：把”语义”压进”比特”，省下的不只是空间，更是访存带宽。

HashTable 不把”这个 slot 是空 / 满 / 删除”存成一个 enum（4 字节），而是压进一个 8-bit 的 tag（§4.2）。理由是带宽：16 个 tag 打包成 16 字节正好能被一条 SSE 指令一次性吃进寄存器（§6.2）。指针压到 6 字节而非 8 字节（§4.2），是因为 x86-64 用户态地址只有 48 位有效——省下的 2 字节 × 16 让整个 Bucket 卡进 128 字节边界。位操作在这里不是抠门，是为了让数据结构整体落进”2 cache line”这个硬性预算。

代码品味：每一个位域提取都升格成命名函数，魔法数字 38 / 0x80 都有一行能写下的理由。

手法	代码	品味点	详见
位域提取	`hashTag(h) = (h >> 38) \| 0x80`	封装成函数而非裸写移位；`\| 0x80` 把有效 tag 推入 [0x80,0xFF]，与 0x00/0x7F 错开最高位	§4.2
2 的幂取模	`x & (n - 1)`	用位与代替除法，前提（n 是 2 的幂）由 `sizeMask_` 的构造保证	§15.2
位字段写入	`(slot & ~mask) \| value`	写指针时只动低 48 位，高 16 位（可能存 tag）原样保留	§15.3
bitmask 迭代	`__builtin_ctz` + `bits &= bits-1`	Kernighan trick，无分支地遍历命中位	§15.4

贯穿的工程纪律：最高位（MSB）被复用为”类型标签”（§15.6）——tag 的 bit 7、PMOVMSKB 的结果都把 MSB 当作”有效/无效”的开关，这让 SIMD→scalar 的桥接（§6.9）零成本。

16.2 内存布局（Memory Layout）

架构品味：布局不是被动结果，而是主动设计的第一公民。

Bucket = 128 字节 = 2 cache line，是整个数据结构的”原子”（§4.2）。关键决策是 tag 与 pointer 分区存放（SoA 而非 AoS）：16 个 tag 连续打包在前 16 字节，16 个指针连续排在后面。如果按”tag+pointer 交错”（AoS）存，SIMD 扫 tag 时会把一堆无关的指针字节也拽进寄存器，浪费带宽。SoA 让”先扫 tag，命中后才读指针”这个两阶段访问各自局部性最大化。

代码品味：用偏移常量和 reinterpret_cast 把布局表达得无歧义，而非靠 struct padding 碰运气。

// tag 区与 pointer 区的边界由常量精确定义，不依赖编译器 padding：
static constexpr int32_t kBucketSize = 128;
static constexpr uint8_t kSlotsPerBucket = 16;
// tag 在 [0, 16)，pointer 在 [16, 16 + 16*6)，尾部 16 字节 padding 凑齐 128。

布局的”自证”通过 static_assert 固化（§15.7）：mask 不许碰高 16 位、Bucket 大小必须是 2 的幂——把不变量写进编译期，而不是寄望于 code review 发现。

与位操作的耦合：内存布局的”省”全靠位操作的”挤”——指针压缩、tag 打包都是位级手法，二者是一体两面。

16.3 访存模式（Memory Access Patterns）

架构品味：承认 DRAM 延迟无法消除，把全部精力投向”掩盖”它。

一次 cache miss ≈ 100ns ≈ 数百 cycle。HashTable 的访存策略是分层的延迟隐藏（§13.1 原则 3）：

单条预取   →  __builtin_prefetch(下一个 bucket)
4-路流水线  →  ProbeState 同时推进 4 个 key 的探测（§6.3）
64-路流水线 →  normalized key probe 一次发射 64 个预取（§6.4）
自适应步长  →  AdaptivePrefetch 实测延迟动态调 lookAhead ∈ [4,32]（§6.5）

核心洞察是软件流水线：当一个 key 在等内存时，CPU 不应空转，而应去推进另一个 key 的计算。ProbeState 被设计成纯值语义的栈对象（§14.5），正是为了能廉价地”同时持有多个探测状态”。

代码品味：把”等内存”这件事拆成可流水的状态机阶段，而非写成一个阻塞的 while 循环。

ProbeState 的三段式 preProbe / firstProbe / fullProbe<op>（§6.3）不是为了好看——这种切分让调用方能在三段之间插入其他 key 的工作，硬件因此能并行发起多个内存请求。AdaptivePrefetch 把”最优预取距离”做成运行时实测而非硬编码常量（§6.5），体现了”不假设硬件，去测量硬件”的务实品味：

1	lookAhead = clamp(4 × 100ns × 16 / elapsed_ns, 4, 32)

与内存布局的耦合：访存模式之所以高效，前提是布局让”扫 tag”只碰一条 cache line——SoA 布局（§16.2）和预取流水线（本节）配合才有意义。

16.4 SIMD（数据并行）

架构品味：用一条指令的宽度，换探测路径上的分支消除。

标量哈希表探测内层是”逐 slot 比较 + 分支”，每次比较都可能分支误判。HashTable 把一个 Bucket 的 16 个 tag 一次性载入 XMM 寄存器，用 PCMPEQB 做 16 路并行字节比较，再用 PMOVMSKB 压成一个 16-bit mask（§6.2）。16 次比较 + 16 次分支，坍缩成 2 条无分支指令 + 1 次 bitmask 迭代。

代码品味：用 TagVector 抽象屏蔽指令集差异，用编译期分支选择 SSE2/AVX2。

手法	品味点	详见
`TagVector` 抽象	隔离 SSE/AVX/NEON 差异，上层逻辑只见”16 路比较”	§6.1
同一向量两种 mask	`hits_ = PCMPEQB(tags, wanted)`（探测）与 `free = ~PMOVMSKB & kFullMask`（插入），一次载入两种用途	§6.10
`if constexpr` 选指令	编译期决定 SSE2 vs AVX2 路径，无运行时开销	§6.8
AVX2 Gather	向量化收集分散的 row 指针	§6.6

与位操作 / 布局的耦合：SIMD 能成立，根因有两个——tag 的 | 0x80 不变量（§16.1）让 PMOVMSKB 的 MSB 直接区分有效/无效；SoA 布局（§16.2）让 16 个 tag 物理连续，才能一条指令载入。SIMD 是位操作和布局共同喂出来的能力，不是孤立的优化。

16.5 多线程编程范式（Concurrency Paradigm）

架构品味：避免锁，靠”分区 + 合并”把并行 build 拆成无共享的独立子问题。

并行 join build（§9）不在一张共享表上加锁，而是 partition-then-merge：

1
2
3

阶段 1（并行）：按 hash 高位把行分区，每个 partition 互不重叠
阶段 2（并行）：每个线程独占一个 partition 建子表，零竞争
阶段 3（串行）：处理跨分区 overflow，回填少量边界行

这是经典的无共享并行（shared-nothing）思路：把竞争消灭在数据划分阶段，而不是在访问阶段用锁去仲裁。绝大部分工作（阶段 1、2）完全并行，只有少量边界 case（阶段 3）退回串行——用”串行处理 5% 的难例”换”95% 的零锁并行”。

代码品味：用模板把”并行”与”串行”路径在编译期分开，运行期不付多余判断。

HashTable<ignoreNullKeys> 的模板参数（§14.3）和 fullProbe<op> 的操作分发（§6.3）让 build / probe / erase 各自单态化。并行 build 的每个阶段是独立函数，状态通过参数显式传递而非共享可变状态——这让线程边界上的数据流一目了然，也是”值语义优先”（§14.5）在并发场景的延伸。

与访存模式的耦合：分区的另一个收益是局部性——每个线程只碰自己 partition 的内存，cache 不会被其他线程的写入污染。多线程范式和访存模式在这里是同一个决策的两面：分区既消除竞争，又改善局部性。

16.6 五维一体：一个决策的五个投影

最后回到本章开头那句话。五个维度看似独立，实则是同一套”硬件意识”在不同切面上的投影：

                   ┌─────────────────────────┐
                   │  让数据结构贴合硬件脾气   │
                   └─────────────────────────┘
                                │
  ┌──────────┬──────────┬───────┼────────┬──────────────┐
 位操作      内存布局   访存模式    SIMD      多线程范式
  │           │          │         │           │
把语义      2 cache    分层延迟   16 路并行   分区无共享
压进比特    line 预算  隐藏流水线  比较       + 局部性

它们彼此咬合，拆掉任何一环另一环就失去意义：

没有 tag 的位压缩（15.1），16 个 tag 装不进一条 cache line，SIMD 一次比较（15.4）无从谈起；
没有 SoA 布局（15.2），预取流水线（15.3）扫 tag 时会拽进无关字节；
没有分区（15.5），并行 build 既要加锁，又会污染彼此的 cache（15.3）。

一句话总结：HashTable 的优雅不在某一个聪明的技巧，而在于位操作、布局、访存、SIMD、并发这五件事被设计成互相成全——每个决策都同时在多个维度上买单和收益。这是”系统级品味”区别于”局部优化”的根本所在。

附录：关键常量速查

常量	值	含义
`kHashTableLoadFactor`	0.7	负载因子阈值
`kArrayHashMaxSize`	2<<20 = 2097152	kArray 模式最大槽数
`kBucketSize`	128 字节	一个 Bucket 的大小（2 cache line）
`kPointerSize`	6 字节	压缩指针大小
`kTombstoneTag`	0x7F	已删除槽标记
`kEmptyTag`	0x00	空槽标记
`kHashBatchSize`	1024	rehash/build 时每批处理行数
`kPrefetchSize`	64	normalized key 模式预取批次大小

附录：类型模板实例化

HashTable 有两个显式实例：

1 2	template class HashTable<true>; // ignoreNullKeys=true（聚合 / inner join） template class HashTable<false>; // ignoreNullKeys=false（null-aware join）

编译时分离两种路径，null key 的处理逻辑通过 if constexpr (ignoreNullKeys) 完全在编译期消除，无运行时开销。