Velox HashTable

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。

由此推出的诉求：

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

2.3 Join 场景对表的诉求

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

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

由此推出的诉求：

1. 同一 key 允许多行——build 侧可能有多行 key 相同（一对多 join）。表里同 key 的多行用行内 next 指针串成链表（§4.3 中的 next row ptr），probe 命中后顺着链表吐出所有匹配行。
2. build 与 probe 分离让 build 阶段可以并行——多个线程各建一块再合并（§9 并行 Join Build）。聚合的 build/probe 合一就难以这样切。
3. probe 侧只读不写——probe 阶段不改表，这让多线程 probe 天然无竞争。
4. 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 模式枚举与触发条件

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，逐列比较）

决策流程图：

Fig.　decideHashMode() — 阈值递降:能 array 就 array,不行退 normalized-key,最后才 hash

3.2 kArray 模式

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

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

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：

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 思想：

Fig.　Bucket = 128 bytes = 2 × cache line:tags 与 pointers 各 16 槽,SIMD 扫 tags

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

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

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

hashTag() 实现：

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]，恰好覆盖了两个特殊标记的完整值域：

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

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

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

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 的事实：

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 模式）

Fig.　RowContainer 行布局:normalized_key 在负偏移,join build 末尾挂 next-row 指针

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 模式下整个数据通路其实是三种不同布局的拼接，而不是单一的"行存"或"列存"。这是这套设计最值得玩味的地方。

Fig.　列 → 索引 → 行:列存算 hash、Bucket 数组做目录、RowContainer 存行

关键认知：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

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

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

1. 进表要快——输入是列存，hash 计算能向量化（诉求：批量、向量化）。
2. 找得要快——目录是紧凑的 tag 索引，探测能 SIMD 过滤且 cache 命中率高（诉求：高频随机访问下少碰内存）。
3. 用得要快——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）：

value_id = (int64_value - min_) + 1

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

Distinct 模式（uniqueValues_ 哈希表）：

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，否则该行一定不命中，可以提前剪枝：

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 合并到主表：

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 汇编等价：

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);
    }
};

步长公式推导：

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）为例：

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

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

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 本质上是把每字节最高位提取出来：

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 槽中：

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

// 遍历 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 并行度与同步

主线程：负责第 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）：

// 不释放 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 722 选 bucket、bit 3844 做 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) 交错放：

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

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

分离存放：

[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 是教科书级例子：

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 一路降级，永不回头：

// setHashMode 没有 kHash → kArray 的路径

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

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

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

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

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

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

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

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

ProbeState 切成三个阶段：

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++ 类，但永远不在堆上分配：

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

位图：

Fig.　64-bit hash 位域:同一个 hash 切出 tag / bucket / slot 三段

为什么 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 的幂，这是位操作能用的根本前提：

VELOX_CHECK(bits::isPowerOfTwo(size));

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

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

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

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

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

14.2.3 bits::nextPowerOfTwo 与 popcount

sizeBits_ = __builtin_popcountll(sizeMask_);

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

14.2.4 isPowerOfTwo 的位操作判定

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 的幂：

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

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

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 的场景。

对比简单写入：

*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 迭代

调试建议：

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

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

3. 位段提取永远写成命名函数（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），体现了"不假设硬件，去测量硬件"的务实品味：

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（并行）：按 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 五维一体：一个决策的五个投影

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

Fig.　五维一体:一个"贴合硬件"的决策在五个维度上的投影

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

• 没有 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 有两个显式实例：

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

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