Velox HashTable

Velox 的 HashTable 把三件事分开处理：把输入 key 编码、在索引中定位、在 RowContainer 中保存和访问行。聚合和 Join 共用这些能力，但建表时机、重复 key 和 NULL 的处理由调用方决定。可以沿着输入 key 到输出行的路径，依次理解这三个层次。

执行流程与相关实现核对于 2026-09-29，Velox 源码版本为 48883e8521b2。下文源码节选、历史资料和宿主集成引用各自注明版本；教学输入用于解释状态变化，未作为性能基准运行。

1. HashTable 的职责、输入输出与使用方式

Velox 的 exec::HashTable 是聚合与 HashJoin 使用的 key 索引。它把输入向量中的 key 映射到 RowContainer 中的行：聚合查到的是某个 group 的状态位置，Join 查到的是匹配的 build 行及重复链。聚合函数怎样更新状态、Join 怎样执行 filter 和输出补行，由相应算子负责。

从内存结构上看，桶式 HashTable 是一块连续的 bucket 数组，每个 bucket 中先放 tags，再放指向行的 pointers；真实 key、Join payload 和聚合状态放在 RowContainer。官方 Hash Table 文档用这个布局解释插入和扩容，很适合作为后面 SIMD 与 ProbeState 分析的起点。它借鉴 F14 一类表的 tag 筛选思路，同时提供面向一批向量行的插入与查找接口，让解码、hash、预取和探测可以分阶段组织。

除 HashJoin 和 HashAggregation 外，RowNumber、TopNRowNumber、MarkDistinct 也使用这类 key → 行或状态的索引。对于普通 HashJoin，HashBuild 建立索引，HashProbe 只查找并展开结果，不向 build 索引插入新 key，也不会因 probe 行数增多触发这张表扩容。聚合则会一边查找一边创建新 group，因此同样的布局在两类调用方中有不同的增长行为。

层次	输入与输出	负责的事情
调用方	key 列、批次、join 或聚合语义	决定查找、插入、结果展开和状态更新
VectorHasher	列值 → hash 或 value ID	统计数据分布、编码 key，支持表示选择
HashTable 索引	编码后的 key → 行指针或未命中	探测、插入、删除，以及重复 key 的关联
RowContainer	行及其字段、状态 → 稳定的行访问位置	保存 payload，供 key 比较、结果物化和状态操作使用

kArray、kNormalizedKey、kHash 是同一个索引职责的不同实现路径。kArray 使用 value ID 直接定位；kNormalizedKey 用可组合的紧凑 key 降低比较成本；kHash 提供通用查找。选择哪条路径取决于数据统计和编码是否有效，不能把某条快路径当作所有表的默认行为。

理解接口时要把两个结果分开：找到行位置与完成上层运算。GROUP BY 找到 group 后还要初始化或更新 accumulator；Join 找到 key 后还可能遍历重复行、应用 join filter、控制输出批次。下面先比较这些使用场景，再进入 ProbeState、布局、编码、SIMD 和并行实现。

图 1：输入列经过 VectorHasher 编码，索引返回行指针；聚合状态与 Join payload 都保存在 RowContainer。打开原图

本文对照 Velox 1d1b765678702e6b5d1b3c582373c618813c3c85（2026-09-17），于 2026-09-19 复核。源码链接固定到这一提交。标注“源码摘录”的代码来自该版本；标注“流程示意”的代码省略了错误处理、统计或分支，不可直接替换实现。

代码片段分别标明源码节选或流程示意；流程示意省略统计、异常包装与无关分支，不是可独立编译的程序。历史资料与宿主集成保留各自版本，不能据此推断它们组成了经过构建验证的发行版本。

2. 一批输入怎样变成 group 状态与 Join 结果

先用同一批 key 观察两个调用方。聚合输入 (k,v)=[(A,10),(B,7),(A,5)]，查表结果是 hits=[rowA,rowB,rowA]，newGroups=[0,1]；GroupingSet 初始化两个新 group，再更新 sum，最终得到 (A,15)、(B,7)。HashTable 只负责找到或创建状态位置，sum 的更新由 aggregate 完成。

阶段	数据怎样变化	对应模块
选择输入	SelectivityVector 给出有效输入行号；NULL 是否剔除由调用方语义决定	GroupingSet / HashBuild / HashProbe
准备 key	VectorHasher 解码 key，计算 value ID / normalized key 或通用 hash	prepareForGroupProbe / prepareJoinProbe
定位候选	kArray 直接寻址；桶式路径先比较 tag，再访问候选行验证完整 key	HashTable / ProbeState
创建或命中	聚合未命中时分配 RowContainer 行并写 key；第三条 A 复用 rowA	insertEntry、lookup.hits、lookup.newGroups
执行上层语义	聚合初始化和更新 accumulator；Join 展开重复链、执行 join filter、组织输出	GroupingSet / HashProbe
完成与资源释放	输出按 RowContainer 或 Join 迭代器访问；清理索引、行与相关状态	调用算子与 HashTable::clear

若 build 输入为 [(A,p0),(A,p1),(B,p2)]，probe 输入只有 [A]，Join 应枚举两个 A 候选；它不能复用聚合“一个 key 只建一行状态”的语义。桶内 tag 与 pointer 只是入口，完整 key、payload、next 链以及 probed flag 都在行侧。这个区别解释了后面的布局、模板参数与 build/probe 接口。

主线入口：prepareForGroupProbe、groupProbe、GroupingSet。

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

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

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

3.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 要遍历未命中行）
删除需求	基本没有	HashTable 提供 erase/tombstone 能力；当前主要 HashBuild/HashProbe spill reclaim 路径使用 clear(true) 清整表，不能把单项 erase 写成当前 spill 的必经步骤。

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

3.2 聚合场景对表的诉求

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

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

由此推出的诉求：

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

3.3 Join 场景对表的诉求

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

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

由此推出的诉求：

同一 key 允许多行——build 侧可能有多行 key 相同（一对多 join）。表里同 key 的多行用行内 next 指针串成链表（§6.4 中的 next row ptr），probe 命中后顺着链表吐出所有匹配行。
build 与 probe 分离让 build 阶段可以并行——多个线程各建一块再合并（§11 并行 Join Build）。聚合的 build/probe 合一就难以这样切。
候选查找通常读取既有索引，但 right/full 等 join 会更新 build 行的 probed 标志，reclaim 还会协调状态转换。不能把整个 probe 阶段概括为所有数据只读、天然无需同步。
删除接口需要保持开放地址探测链不被空洞截断，这解释了 tombstone 的作用。当前 spill 回收走整表 clear(true) 的路径应另行分析；不能由 erase 接口存在反推一定按分区逐条删除。

3.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>` 模板特化（§5.3 与 §15.3）

两个关键观察：

Right/Full join 需要"build 行被命中过"的标记，这是聚合场景完全不需要的能力，也是为什么 probe 不总是"只读"——某些模式下要回写命中标记，再在 probe 结束后遍历全表捞未命中行。
模板参数提供是否跳过 null key 的实现分支，但调用方必须按 SQL 语义选择。普通聚合要保留 NULL 分组；join 是否丢弃 null build 行取决于 join 类型及输出需求，null-aware 匹配也不是简单切换一个模板就全部完成。

3.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）
单项 erase 要保持探测链连续                   → tombstone；当前 spill 主路径另走 clear(true)

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

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

4.1 先建立整体模型：编码、索引、行容器

BaseHashTable 定义聚合和 Join 使用的接口，HashTable<ignoreNullKeys> 实现具体表结构。每个 key 列有一个 VectorHasher；rows_ 拥有一个 RowContainer；合并 Join Build 后，otherTables_ 继续拥有其他构建线程的行容器。索引里的指针可以指向其中任意一个行容器，合并时继续保留各行容器的所有权。

4.1.1 两类调用方，共用一套定位能力

问题	聚合：GroupingSet	Join：HashBuild / HashProbe
每个 key 要留下什么	一个 group，包含分组 key 和 accumulator	build 行；可能是重复行链，也可能去重或保存计数
输入时做什么	`prepareForGroupProbe` → `groupProbe`，未命中就建 group	常规路径先保存行和统计；去重路径也会边输入边建立索引
查到行以后	先初始化新 group 的 accumulator，再累加输入	先得到匹配链的入口，再枚举结果、执行 Join filter 和输出
如何扫描结果	遍历 RowContainer，提取 key 和聚合结果	按 probe 行枚举；某些 Join 还要扫描 build 行的 probed 标志

HashTable 的 groupProbe 不负责执行 SUM，joinProbe 也不负责完整的 SQL Join 语义。前者返回可更新的 group，后者返回匹配入口；运算和输出仍在上层算子中完成。

4.1.2 NULL 的处理由调用方语义决定

HashTable<true> 表示使用忽略 NULL key 的路径；HashTable<false> 允许行容器保存 NULL key，并使用能处理 NULL 的比较路径。调用方根据聚合配置或 Join 语义选择模板实例。

聚合由 GroupingSet::ignoreNullKeys_ 选择模板实例。普通 SQL GROUP BY 要把 NULL 归入相应分组，不能默认丢弃。
Join Build 为 right/full、right semi project、right anti 等场景保留 NULL build 行，因为这些行即使不匹配也可能影响最终输出。nullAsValue_ 和带 filter 的部分 null-aware Join 也会影响实例选择。
Join Probe 是否从输入中移除 NULL，还受到 prepareForJoinProbe(..., decodeAndRemoveNulls) 及上层 Join 语义控制。保留 NULL build 行不意味着普通等值 Join 中 NULL = NULL 为真。

源码：接口与成员、GroupingSet::createHashTable、HashBuild 创建表、prepareForJoinProbe。

4.2 类层次

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：

ignoreNullKeys=true 表示该表的相关路径跳过 null key；是否采用它由调用方语义决定。普通 GROUP BY 必须保留 NULL 分组，不能归到统一忽略 null 的这一类。
ignoreNullKeys=false 允许保留需要参与分组或 join 语义处理的 null 行。保留 build 行与把 NULL 当作普通等值可匹配值是两件事，null-aware、outer、semi/anti 仍由上层按 SQL 语义处理。

两个工厂方法：

流程化代码节选：省略外围声明与非主线分支；实现位置以相邻固定版本源码链接为准。

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

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

4.3 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

4.4 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。

5. 三种 Hash 模式

5.1 从 key 到三种表表示

5.1.1 Value ID 是表内部的编码

VectorHasher 有两种 value ID 来源：

Range 编码：在已选定范围内，非 NULL 整数可编码为 value - min + 1，0 留给 NULL。
Distinct 编码：维护 value → id 的映射，非 NULL 值从 1 开始编号。普通类型使用 F14 集合，HUGEINT 有专用映射。低基数字符串也可能使用这种编码。

多列 key 使用混合进制组合。例如第一列的编码空间是 4，第二列是 3，那么 (id0=2, id1=1) 的组合值为 2 + 4 × 1 = 6。这里的 4、3 是包括 NULL 槽和必要预留量的编码空间，不是简单的非 NULL distinct 个数。

流程示意：
normalizedKey = id0 + R0 * id1 + R0 * R1 * id2 + ...
0 <= idi < Ri

在这一组映射及其空间约束内，组合值可以无碰撞地表示 key 元组。它不是跨表稳定的 ID，也不等于原始 key 的排序编码。映射改变后，已有行需要重新编码。

computeValueIds 可以收集输入统计、扩展 distinct 集合，并返回当前编码是否仍适用。Join Probe 的 lookupValueIds 使用 build 端已确定的映射：某列值不存在时可以提前排除该 probe 行；range 编码只能据范围排除，范围内的“空洞”仍要由索引确认。该剪枝同时适用于 kArray 和 kNormalizedKey。

源码：支持的 key 类型、enableValueIds / enableValueRange、prepareForGroupProbe。

5.1.2 三种模式分别省掉了哪一步

模式	索引方式	最终如何确认 key 相同	主要成本
`kArray`	组合 value ID 直接索引 `char*` 数组	编码本身无碰撞，无需再比较 key	编码空间对应的整个指针数组
`kNormalizedKey`	对组合 ID 混合后，用 bucket 探测	比较行前缓存的 64-bit normalized key	bucket、指针跳转和 normalized key 读取
`kHash`	按 key 类型计算并组合 hash，用 bucket 探测	通过 RowContainer 逐列比较实际 key	通用 hash、候选行访问和 key 比较

kArray 可以接收 distinct 编码后的字符串；kHash 通过 VectorHasher 和各类型的 hash 实现处理 key。

kArray 的访存局部性取决于输入 ID 顺序，随机 ID 仍会造成随机索引访问。kNormalizedKey 的编码虽无碰撞，索引 bucket 和 tag 仍会碰撞，所以仍需探测及比较。

5.1.3 decideHashMode 的决策顺序

函数按 range / distinct 统计选择表示；聚合及输入阶段去重的 Join 留出增长空间。当前 reservePct() 在 isJoinBuild_ && allowDuplicates_ 时返回 0，否则返回 50。类型不支持 value ID 时，构造函数就会选择 kHash。

下面按源码顺序概括分支。R 是所有 range 编码空间的乘积，D 是所有 distinct 编码空间的乘积，B 是按启发式选取 range/distinct 后的乘积；它们已包含预留，乘法溢出用 kRangeTooLarge 表示。

顺序	条件	选择
1	`R < 2^21` 且未禁止 range array 路径	全 range 的 `kArray`
2	`B < 2^21`，或禁止 range array 后仍满足 `B < numDistinct_ × 2`	混合编码的 `kArray`
3	`R` 能放入 64 bit	全 range 的 `kNormalizedKey`
4	单列 key，且 `D > 10000`	`kHash`
5	`D < 2^21`	distinct 编码的 `kArray`，BOOLEAN 仍走 range
6	`D`、`R` 都不可用	`kHash`
7	其余可编码情况	`kNormalizedKey`，尽可能使用 range

选取 B 时，源码倾向于使用代价不超过 distinct 空间约 20 倍的 range 编码。这里是在权衡编码查找成本与空间，而非仅按 key 基数分三档。kArrayHashMaxSize = 2 << 20 对应常规分支约 16 MiB 的指针数组阈值；第二个分支另有与当前行数比较的条件，因此实际 Array 容量也可能超过该阈值。

5.1.4 编码失效后会重新决策，不一定马上进入 kHash

图 2：Array 与 NormalizedKey 可以在重新编码后重新选择；进入 kHash 后不再切回 value ID 模式。打开原图

prepareForGroupProbe 在当前编码失败或首次分配时调用 decideHashMode，并重新准备本批输入。setHashMode 只禁止从已经处于 kHash 的状态再次切换；它并没有禁止 kNormalizedKey → kArray。HashTableTest.arrayProbeNormalizedKey 覆盖了编码变化后的重建与探测。

因此应记住的不变量是：**kHash 是退出 value ID 编码后的终态；Array / NormalizedKey 在重决策时都可能被选中。** 重新编码可能触发 rehash；重建已有行时若仍无法得到 ID，rehash 才会回退到通用模式。

源码：decideHashMode、reservePct、setHashMode、相关模式测试。

5.1.5 把官方示例还原为编码空间

官方文档用稠密整数、稀疏整数和字符串说明三种模式。需要区分有多少输入行、有多少实际不同 key 元组、各列可编码空间的乘积：两列分别只出现 500 个值，即使输入只有 500 行，直接索引仍可能需要覆盖约 500 × 500 的组合空间，因为编码是按列组合，而不是为每个实际出现的元组再建一张独立字典。

输入示例	为什么选这条路径	对应测试
两列 BIGINT，取值较稠密，各约 500 个值	range 编码的组合空间足够小，可用 kArray	int2DenseArray
一列 VARCHAR，约 500 个不同字符串	字符串先映射为连续 ID，组合空间仍小，可用 kArray	string1DenseArray
两列 BIGINT，各约 500 个值，但间隔 1000	range 空间很稀疏；distinct 编码后仍可用 kArray	int2SparseArray
两列 VARCHAR，各约 5000 个值	组合空间已不适合普通小数组，但可放进 64 bit，使用 kNormalizedKey	string2Normalized
两列 BIGINT，约 10000 行、间隔 1000	范围组合超出常规数组阈值，仍可进行 normalized-key 编码	int2SparseNormalized
一个 ROW 类型 key，或多列组合空间溢出	无法使用有效 value ID 编码，回退 kHash	structKey / mixed6Sparse

这些数量用于解释趋势，精确数组容量还包括 NULL 和预留。当前非 NULL range ID 是 value - min + 1，distinct ID 从 1 开始，0 给 NULL；rangeSize 是 max - min + 2，distinct 空间也加一个 NULL 槽。假设无额外 reserve、两列值域都是 0..499，那么每列空间是 501，组合空间是 501² = 251001，而非精确的 250000；聚合等增长路径还会按 reservePct() 扩展空间。因此不能把官方简化示意里的“apple → 0”原样当成当前存储编号。

官方模式总览中的“避免 hash / bucket probing”需要分别理解：kArray 确实绕过桶式索引；kNormalizedKey 仍对编码后的 key 进行 hash 混合、tag 筛选和 bucket 探测，只把最终逐列 key 比较换成完整的 64-bit normalized key 比较。当前对应分支在 normalized key 相等时就确认 key 匹配，不是总要再逐列比较一次。这个编码在有效映射内表示整个 key 元组，与仅用于筛候选的 7-bit tag 不同。

文档中的支持类型列表和 2M 上限也应以快照为准：当前 typeSupportsValueIds() 还包括 HUGEINT 的 distinct 路径，并先排除提供自定义比较语义的类型；decideHashMode() 有禁用 range array 后按当前 distinct 数量比较的额外分支，所以 2²¹ 是常规选择阈值，不能解释成所有 kArray 实例不可超过的绝对上限。上面 4.1.3 保留完整分支顺序。

源码与用例：支持类型、NULL 与 reserve、normalized-key 匹配、HashTableTest 示例组。这些是阅读现有测试得到的说明，不代表本次重跑了测试。

5.2 模式枚举与触发条件

流程化代码节选：省略外围声明与非主线分支；实现位置以相邻固定版本源码链接为准。

enum class HashMode { kArray, kNormalizedKey, kHash };

decideHashMode 在需要建立或重新选择表示时读取 range/distinct 统计，按源码中的条件顺序选择可用模式；不是每个 key 插入前都完整计算一次“最优模式”。新的数据让编码失败时，也可能先重新编码再重新选择。

// decideHashMode 的当前分支顺序摘要；值包含 reservePct 的预留估计。
更新 disableRangeArrayHash_；特定已建状态先 analyze，失败 -> Hash
计算每列 range / distinct 大小以及 ranges、distincts、best 的安全乘积
1. ranges < kArrayHashMaxSize 且未禁用 range Array -> Array（全 range）
2. best < kArrayHashMaxSize，或禁用 range Array 且 best < numDistinct*2
   -> Array（按 useRange 选择编码）
3. ranges 可表示 -> NormalizedKey（全 range）
4. 单 key 且 distinctsWithReserve > 10000 -> Hash
5. distincts < kArrayHashMaxSize -> Array（全 distinct）
6. distincts 与 ranges 都不可表示 -> Hash
7. 其余 -> 根据可表示性选择编码，使用 NormalizedKey
// kArrayHashMaxSize = 2L << 20；不能仅按实际行数画固定三档阈值。

决策流程图：

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

5.3 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
Array 表移除了 tag 比较与冲突链，但按 value ID 的查找仍可能是随机访问。工作集大小与 ID 分布决定缓存行为，不能把数组寻址直接等同于顺序扫描。

Array 模式受可编码空间、范围/基数估算、内存比例和相关配置条件共同约束。2M 是决策中的一个阈值分支，不能把它当成所有 Array 表的绝对上限；完整决策顺序见本节当前实现补充。

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

5.5 kHash 模式

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

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

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

5.6 模式切换

Array 和 NormalizedKey 的编码失效后可以先重新分析、重新编码并选择表示，不一定立刻进入 Hash。进入 kHash 后才不再回到 value ID 表示。状态图应区分“重新选择仍可编码模式”和“放弃编码进入 Hash”两件事。

流程化代码节选：省略外围声明与非主线分支；实现位置以相邻固定版本源码链接为准。

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

6. 内存布局详解

6.1 索引与 payload：内存实际怎么排

6.1.1 字节 Bucket

kHash 和 kNormalizedKey 共用 bucket 布局：16 字节 tag、16 个 6 字节行指针、16 字节 padding，共 128 字节。static_assert(sizeof(Bucket) == 128) 固化这一大小。在 64 字节 cache line 的平台上，一个 bucket 对应两条 cache line；这不意味着一次 probe 必须读取全部 128 字节。

图 4：Bucket 的字节布局及 6-byte 指针访问。读取 tag 筛候选，随后按需要取行指针和 payload。打开原图

tag 的编码为：

// 源码摘录：BaseHashTable::hashTag
return static_cast<uint8_t>(hash >> 38) | 0x80;

0x00：empty，当前 bucket 中的候选比较完后可终止继续探测。
0x7f：tombstone，不能当作 empty 终止探测。
0x80..0xff：有效 tag，携带 hash 的 bit 38..44。转为 uint8_t 会留下 8 bit，其中最高位被强制设为 1，因此最终只有 7 bit 来自 hash。

Tag 相同只表示候选命中，仍要比较 normalized key 或原始 key。把 tag 连续存放的价值是能一次载入 16 个 tag，再用 SIMD 比较生成候选 mask。候选指针可能与 tag 同处第一条 cache line，也可能在第二条。实际传输仍以平台的 cache line 为单位。

6.1.2 字节指针为什么要保留相邻两字节

// 源码摘录：Bucket::pointerAt
return reinterpret_cast<char*>(
    *reinterpret_cast<uintptr_t*>(&pointers_[kPointerSize * slotIndex]) &
    kPointerMask);

// 源码摘录：Bucket::setPointer
auto* const slot =
    reinterpret_cast<uintptr_t*>(&pointers_[slotIndex * kPointerSize]);
*slot = (*slot & ~kPointerMask) | reinterpret_cast<uintptr_t>(pointer);

实现从 6 字节槽的起点读写一个 8 字节 word。高两字节通常属于下一个指针槽；最后一槽的高两字节落在 padding 内。读取后 mask 掉它们，写入时保留它们。写入时保留高位，保护了相邻槽的内容。

这种布局依赖当前实现的 48-bit 指针表示及目标平台的访问约定。移植到其他地址布局时，需要重新核对这些假设。

6.1.3 Bucket 地址和 slot 编号来自不同的计算

流程示意：
byteSize         = capacity * 8
bucketOffsetMask = (byteSize - 1) & ~127
bucketOffset(h)  = h & bucketOffsetMask
nextBucket       = (bucketOffset + 128) & (byteSize - 1)

桶式索引的容量按 2 的幂分配。低 7 bit 被清零以得到 128 字节对齐的字节偏移；例如 capacity 为 2^20 时，索引用到 hash 的 bit 7..22。

插入位置中的 slotIndex = index & 15 解码的是 bucketOffset + slot。这个 slot 由 tag mask、empty mask 或 tombstone 处理选出，不是直接从原始 hash 的低 4 bit 选槽。Array 模式的容量则由编码空间决定，不受同一套 bucket 容量规则约束。

6.1.4 RowContainer 才保存真实 key 和 payload

行布局取决于 key 类型、是否可空、accumulator 对齐和可选字段。下面仅表示字段顺序，不表示各块等宽：

可选 normalized-key 前缀（访问值的位置是 row - 8）
row → key 字段
      flags：NULL / accumulator initialized / probed / free 等
      accumulators（聚合）
      dependent 字段（Join 的非 key 列）
      可选 variable-size 计数
      可选 next-row 指针
      可选 counting-join 计数
      对齐填充

长字符串、复杂类型及可变大小聚合状态还可能引用行外内存。一次命中后的访存成本因此还取决于 payload 类型和行外数据的位置。

Normalized key 的值通过 reinterpret_cast<normalized_key_t*>(row)[-1] 访问，分配的前缀空间还要满足 alignment。进入 kHash 时，disableNormalizedKeys() 将后续分配的前缀大小置为 0，不会移动或逐行回收已有行的前缀；已有行指针继续有效。

源码：Bucket 与容量、hashTag、RowContainer 构造布局、normalizedKey / disableNormalizedKeys。

6.1.5 从整张索引到一个 bucket：跟着数字走一遍

官方文档将桶式索引画成一维数组，这个视角有助于区分容量与地址。capacity 是槽位总数，numBuckets = capacity / 16；一个 bucket 是 128 字节，所以索引字节数为 capacity × 8。容量为 2²⁰ 时，有 65536 个 bucket，索引占 8 MiB。这里计算的是索引本体，不包括 RowContainer、VectorHasher 字典、重复链 payload 和分配管理开销；也不适用于不使用 bucket 的 kArray 布局。

图 5：布局导读：容量、bucket 字节偏移、tag 与行指针各表达不同的信息。打开 SVG 原图

每个容量槽摊销 8 字节，来自 1 字节 tag、6 字节压缩指针和均摊的 1 字节 padding。16 字节 padding 让 bucket 满足 128 字节布局，也保证最后一个 6 字节指针槽从槽起点进行 8 字节访问时仍落在 bucket 内。它不是存业务 key 的空间。若没有 tombstone，按约 70% 占用估算，每个 distinct key 的索引摊销约为 8 / 0.7 ≈ 11.43 字节；重复 Join 行还会占 RowContainer，只是不会各自消耗一个新的 distinct-key 索引槽。

用官方给出的 hash 数值 0x5bca7c69b794f8ce 做一次计算，tag 是 0xf1，bucket 的字节偏移是 1374336，bucket 编号才是 10737。本文统一把最低有效位编号为 bit 0：容量 2²⁰ 时，bucketOffsetMask 是 0x7fff80，使用 hash bit 7..22。文档所说从“第 8 位”取 bucket 位，在这个例子中应理解为把最低位叫第 1 位；不能在 C++ 代码中机械改成右移 8 位。

C++ 数值示例：仅验证布局寻址算术，使用 static_assert 做编译期检查。

#include <cstdint>

constexpr uint64_t capacity = uint64_t{1} << 20;
constexpr uint64_t byteSize = capacity * 8;
constexpr uint64_t hash = 0x5bca7c69b794f8ceULL;
constexpr uint64_t bucketMask = (byteSize - 1) & ~uint64_t{127};
constexpr uint64_t offset = hash & bucketMask;
constexpr uint64_t bucket = offset / 128;
constexpr uint8_t tag = static_cast<uint8_t>(hash >> 38) | 0x80;

static_assert(byteSize == 8388608);  // 8 MiB, index only
static_assert(bucketMask == 0x7fff80);
static_assert(offset == 1374336);
static_assert(bucket == 10737);
static_assert(tag == 0xf1);

得到 bucket 后，slot 仍需通过当前 tags 的候选和空位 mask 选择。原 hash 不能独立决定某 key 最后落在第几个槽：碰撞、已有 key、tombstone 和先前插入顺序都会影响结果。低 7 位被地址掩码清零，是为了得到 128 字节对齐的字节偏移，不是在为这个 key 预先分配桶内 slot。

6.1.6 空桶、半满桶、满桶：布局怎样参与插入

先看没有删除历史、没有并行分区边界干扰的基础过程。这与官方文档的三种插入情形对应，后面的 ProbeState、tombstone 和 parallel build 章节再补齐工程分支。

图 6：插入导读：先做 tag 与 key 的候选检查，再决定复用行、使用空槽或前往下一桶。打开 SVG 原图

空桶：16 个 tag 都是 empty，没有候选 key，新项放进可用槽，同时写入 tag 与指向 RowContainer 的指针。真正的 key 和 payload 在索引外保存，因此扩容时可重新安排索引，而不必跟着迁移全部行。

半满桶：先用 SIMD 比较 tags。没有相同 tag，就不用访问那些行的 key；有一个或多个 tag 相同，就逐个取指针并进行真正的 key 比较。所有候选都不匹配，才能使用空槽。对于聚合，找到相同 key 返回已有 group，后续更新 accumulator；对于允许重复的 Join build，通常将重复行关联到已有 key 的链上。Semi / Anti 等可选择去重或其他重复处理，不能把“相同 key 一律挂链”作为所有表的通则。

满桶：满不代表这次插入必须立即去下一桶，仍可能在本桶找到相同 key。只有确认没有匹配且没有终止用的 empty，才沿 nextBucketOffset 以 128 字节为步长前进，末尾回绕。保留空槽不仅为新 key 预留空间，也让未命中探测能结束，避免持续遍历整个索引。

官方的“从左往右填满”适合刚建表、无删除的示意；有 erase 后槽位可能出现 tombstone 或 empty 洞，不能依赖“前 N 个必定有效”的永久不变量。当前 ProbeState 会先处理本桶候选，再检查 empty；经过 tombstone 时先记住可复用位置，还要继续查找重复 key。这样才能避免同一个 key 在后面的桶里已有索引项，却又在前面的 tombstone 上插入一项。

源码：Bucket 布局、寻址与回绕、ProbeState::fullProbe。相邻章节保留了 6 字节指针读写、SIMD mask、四路交错探测和完整重复链实现。

6.2 kArray 模式

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

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

6.3 kHash / kNormalizedKey 模式：Bucket 结构

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

图 7：Bucket 的 128 字节布局。已按当前实现修正标注，具体约束见相邻正文。

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 是必须的，而非可选的

hashTag 先右移，再转换为 uint8_t，最后置 bit 7；最终可变的低 7 位来自原 hash 的 bit 38..44。右移本身并没有截成 7 位，类型截断与高位 OR 都是最终编码的一部分。

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

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

pointers 数组（96 字节）：

每个槽保存 6 字节指针位型，代码据此截取低 48 位。这个紧凑表示依赖其支持的分配地址范围，不能推广成所有 x86-64 用户地址永远只有低 48 位；启用更宽虚拟地址空间时仍需满足实现的地址约束。

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 字节 word：前 15 个槽的高两字节通常属于下一个指针槽，最后一个槽则落在 padding。掩码去掉本槽之外的位；这依赖特定布局与目标平台，不是允许普通 C++ 程序任意跨对象或未对齐访问的通用规则。

写入时必须保留所访问 word 的高两字节，因为它们通常是下一个指针槽的内容；最后一槽才对应 padding。这是保护当前相邻数据的必要操作，不只是为未来扩展预留。

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

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

图 8：RowContainer 行内布局。已按当前实现修正标注，具体约束见相邻正文。

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

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

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

图 9：列输入、目录与行 Payload。已按当前实现修正标注，具体约束见相邻正文。

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

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

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

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

段	布局	访问模式	为什么这样选
① 输入	列存 Vector	对一整列做同一个 hash 运算	列向量有利于按列批量计算 hash/value ID，具体收益还受编码和选中行影响。行存也能通过 gather、提取或转换使用 SIMD，只是访问与重排成本不同，不能说 SIMD 完全用不上。
② 目录	指针索引 + tag SoA	高频探测，先快速否决再确认	紧凑目录减少同样槽数下的工作集，使更多条目可能留在缓存；表大时仍会超出缓存，tag 命中也只是候选，随后可能访问行和变长 payload。
③ Payload	行存 RowContainer	命中后整行读写（聚合更新 / join 输出）	跨列读取一行会访问多个数据区域，但是否 cache miss 取决于工作集和既有缓存状态。行式 payload 有利于相关字段的空间局部性，不能保证恰好减少 N 次 miss，变长值也未必与行内字段物理相邻。

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

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

进表要快——输入是列存，hash 计算能向量化（诉求：批量、向量化）。
找得要快——目录是紧凑的 tag 索引，探测能 SIMD 过滤且 cache 命中率高（诉求：高频随机访问下少碰内存）。
行布局把一次匹配常用的 key 与 payload 放在同一行记录中，有利于这些访问一起发生时的局部性；代价是批量按单列处理时可能需要 gather 或列提取。具体优劣取决于字段宽度、投影比例与缓存命中情况。

向量与行记录服务于不同访问粒度：前者适合批量列计算，后者适合按 key 定位状态。保留两种布局增加了写行、提取与编码转换成本，但可以让各条路径使用合适的结构；是否胜过统一布局需要在具体工作负载上比较。

跨列读取一行会访问多个数据区域，但是否 cache miss 取决于工作集和既有缓存状态。行式 payload 有利于相关字段的空间局部性，不能保证恰好减少 N 次 miss，变长值也未必与行内字段物理相邻。
全行存：算 hash 时跨行跳读 → 向量化失效，进表变慢；且若把整行塞进 bucket，bucket 装不下 16 个槽，SIMD 扫 tag 也就无从谈起。

这里压缩的是 6-byte，即 48-bit 指针表示。列式输入、紧凑目录和行式 payload 各自匹配不同访问模式；压缩目录降低工作集，但不保证全部驻留 cache。

7. VectorHasher：Key 编码引擎

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

7.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 的映射。

7.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 的无碰撞编码。

7.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 模式下的提前剪枝优化。

7.4 merge()：并行 build 后的 VectorHasher 合并

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

流程化代码节选：省略外围声明与非主线分支；实现位置以相邻固定版本源码链接为准。

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

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

8. SIMD 技巧专章

8.1 一次探测怎样执行，怎样重叠访存

8.1.1 HashLookup 中哪些数组按输入行号索引

rows 是本批要处理的输入行号列表，可能稀疏；hashes、hits、normalizedKeys 都以原始输入行号为下标。newGroups 记录 groupProbe 本次新建 group 对应的输入行号，Join Probe 不使用它。

例如 rows = [2, 5] 时，读取 hashes[2]、hashes[5] 并写回 hits[2]、hits[5]，而不是把结果紧密写到下标 0、1。结果输出时才由 listJoinResults 整理为连续的 (probe row, build row*) 数组。

8.1.2 ProbeState 的三个阶段

阶段	做什么	关键点
`preProbe`	算 bucket offset、广播目标 tag、发出 bucket prefetch	初始化一个 probe 的状态
`firstProbe`	加载 tags 并得到匹配 mask；有候选时先取一个行指针并预取 key	不只是比较 tags，还可能加载候选指针
`fullProbe`	比较候选 key，必要时加载下一 bucket，或插入 / 删除	操作由模板参数区分

ProbeState 是 .cpp 中的辅助类。调用点创建栈对象或栈数组，没有为每次 probe 单独分配堆内存；字段的寄存器分配由编译器决定。

对桶式探测，可以按下面的顺序阅读 fullProbe：

检查 firstProbe 预先取出的候选行。
遍历其余 tag 命中的 slot，比较真实 key。
当前 bucket 的候选耗尽后，再处理 empty。查询返回 miss；插入可以结束查找并使用空槽或之前记下的 tombstone。
没有 empty 时，插入操作记住遇到的第一个 tombstone，再走下一 bucket。

不能一看到某个 empty tag 就跳过同 bucket 的其他候选，也不能在遇到第一个 tombstone 时立即插入。 后面可能仍有相同 key。

8.1.3 路 / 64 路流水线是指令交错，不是线程

图 10：先为多行发出预取，再分阶段推进 probe；图中位置表达程序顺序，不表示实测 cycle 或缓存命中时刻。打开原图

当前通用聚合和 normalized-key 聚合统一调用 groupProbeWithPrefetch<isNormalizedKey>，窗口上限 kPrefetchSize=64。Normalized-key Join Probe 与桶式 Join Build 也使用 64 状态窗口；通用 Join Probe 仍有四状态交错路径。窗口大小是软件一次组织多少独立查找，不是 SIMD lane 数、线程数或 CPU 保证同时在途的 cache miss 数。

这样做给其他独立访问留下执行窗口，以期重叠内存延迟。实际能够重叠的请求数及缓存命中情况，取决于编译器、处理器和数据分布。

8.1.4 extraCheck 修复同一批插入造成的过期观察

假设本批两个输入行有相同 key。两者先执行 firstProbe，都观察到尚未插入该 key；第一个 fullProbe 随后创建 group。第二个 fullProbe 必须重新加载 tags，才能看到刚创建的 group，而不是再插入一个重复 group。

源码在这种插入流水线中，对首个状态传 extraCheck=false，对后续状态传 true。这是同线程分阶段执行导致的可见状态变化，不是一把解决跨线程写冲突的锁。Join Probe 不插入索引，不需要这类重新检查。

Array 聚合路径有相似细节：SIMD gather 得到 miss 后，逐一处理 miss 时会再读 table_[index]，避免前面 lane 刚插入的 group 被重复创建。

8.1.5 SIMD 与预取的适用范围

TagVector 固定包含 16 个 byte，通过 SSE2 / NEON 实现。SSE2 上 tag 比较及 mask 提取可对应 PCMPEQB 和 PMOVMSKB；这只是探测的一部分。
insertForGroupBy 重建一个没有 tombstone 的新索引时，可利用有效 tag 最高位为 1 的性质寻找空槽；**有 tombstone 的通用探测仍须区分 0x00 与 0x7f**。
当前 Array 聚合入口使用 process::hasSimd() 和 dense row 检查。批宽来自 xsimd::batch<int64_t>::size，随目标 SIMD 架构变化。
AdaptivePrefetch 统计前 16 次循环的总耗时，再固定 look-ahead，范围为 [4, 32]。公式是 clamp(4 × 100ns × 16 / elapsedNs, 4, 32)；100ns 是代码中的假设，测量的是循环耗时，而不是直接测出机器的 DRAM latency。

源码：HashLookup、ProbeState、groupProbe / Array probe、Join Probe、Join 插入预取、AdaptivePrefetch。

8.2 平台抽象：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
}

8.3 技巧 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/TZCNT 与清位指令或等价序列，取决于目标 ISA 和优化。源码算法不保证固定生成 BSF+BTC，也不提供固定周期数。

8.4 技巧 2：聚合预取窗口与同窗口插入一致性

当前实现把同一窗口分成 preProbe、firstProbe、fullProbe 三轮；不足 64 条的尾部用 numStates 限制。下面是当前源码的连续节选，省略外围类声明，未作为独立程序编译。

template <bool ignoreNullKeys>
template <bool isNormalizedKey>
void HashTable<ignoreNullKeys>::groupProbeWithPrefetch(HashLookup& lookup) {
  constexpr int32_t kKeyOffset =
      isNormalizedKey ? -static_cast<int32_t>(sizeof(normalized_key_t)) : 0;
  ProbeState states[kPrefetchSize];
  const int32_t numProbes = lookup.rows.size();
  const vector_size_t* rows = lookup.rows.data();
  const uint64_t* hashes = lookup.hashes.data();
  for (int32_t probeIndex = 0; probeIndex < numProbes;
       probeIndex += kPrefetchSize) {
    const int32_t numStates = std::min(kPrefetchSize, numProbes - probeIndex);
    for (int32_t i = 0; i < numStates; ++i) {
      const auto row = rows[probeIndex + i];
      states[i].preProbe(*this, hashes[row], row);
    }
    for (int32_t i = 0; i < numStates; ++i) {
      states[i].firstProbe<ProbeState::Operation::kInsert>(*this, kKeyOffset);
    }
    // Tags loaded by firstProbe() go stale once an earlier state in this
    // window inserts a new group, possibly with the same key.
    const auto numDistinctBefore = numDistinct_;
    for (int32_t i = 0; i < numStates; ++i) {
      fullProbe<false, isNormalizedKey>(
          lookup, states[i], numDistinct_ != numDistinctBefore);
    }
  }
}

关键不是把 4 改成 64，而是窗口内会发生插入：firstProbe 批量读出的 tags 可能因前面的状态插入新 group 而过时。numDistinctBefore 记录窗口开始完整探测前的基数，只要 numDistinct_ 改变，后续 fullProbe 就启用 extraCheck。以 [A,B,A] 为例，最后一个 A 必须看见窗口内刚插入的 rowA，不能基于旧的空槽观察再造一个 A。normalized-key 路径仅用模板选择比较方式与行前 key 偏移，复用同一套调度。

下面保留早期四状态展开写法，便于逐条对照 preProbe / firstProbe / fullProbe 的指令交错；它是历史实现与教学展开，不是当前聚合函数。当前尾部统一走 numStates，旧例的 state2～state4 无条件 extraCheck 则已由窗口内实际插入检测替代。

单次 probe 可能受缓存未命中与依赖链限制。预取到可使用数据的时间取决于缓存层级、CPU、内存系统和请求排队；下面时序只表示程序依赖，不表示实测的固定 cycle。

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

流程化代码节选：省略外围声明与非主线分支；实现位置以相邻固定版本源码链接为准。

历史四状态实现：对应旧版本 groupProbe，保留用于对照指令交错。

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

时序示意图：

// 仅画程序顺序；每列不代表固定 CPU cycle 或数据必然到达 L1。
阶段       A                 B                      C
state1    preProbe           firstProbe             fullProbe
state2    preProbe           firstProbe                  fullProbe
state3    preProbe           firstProbe                       fullProbe
state4    preProbe           firstProbe                            fullProbe
          发出独立预取请求   检查首个 bucket        必要时验证 / 继续探测
实际能重叠多少延迟，取决于缓存、依赖链和 CPU 可并行处理的内存请求。

8.5 技巧 3：Join Probe 与 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);
    }
}

normalized key 的比较需要访问行指针负偏移处保存的编码，可能引入 bucket 之外的访存。较长预取窗口为这些访问提供重叠机会，但其收益依赖缓存、行布局和 CPU；不能只凭 key 模式断言 64 路普遍优于 4 路。当前聚合已经把通用 key 与 normalized key 都放进 64 状态窗口。

8.6 技巧 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_);
}

预取距离随循环耗时、数据局部性和微架构变化。AdaptivePrefetch 用短窗口计时配合假设延迟估算距离，再限制范围；它不是直接检测当前数据位于 L2，也不保证某层缓存对应固定最优步长。

算法：前 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 放大根据假设 DRAM 延迟与测得循环耗时估算的预取距离。它不能保证硬件恰好维持四个在途 miss；硬件可并发请求数、缓存命中和循环依赖都会影响结果。

以每次迭代耗时 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 过于激进占用带宽）。

8.7 技巧 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 的内存子系统并发处理。

8.8 技巧 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 按有效元素 mask 组织紧凑输出，其实现随元素宽度和目标架构选择 shuffle/permute 等操作。它不是所有目标上一条固定指令的别名，也不能只凭接口名推断整个循环无分支。

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

findPartition 用 SIMD 成批比较边界并从比较位图找到目标分区。它使用的是向量边界扫描/选择逻辑，不能仅因要找一个区间就称作传统二分查找。

流程化代码节选：省略外围声明与非主线分支；实现位置以相邻固定版本源码链接为准。

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 的位置。

8.10 技巧 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  → 有效槽

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

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

8.11 技巧 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，重复

探测必须先检查当前 bucket 的候选；遇到真正空槽后，可以按插入不变量终止继续搜索更后面的 bucket。当前 bucket 本身仍可能包含从更早 bucket 溢出的匹配行，所以不能在检查候选前直接返回 miss。

对比小结：

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

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

9. 聚合场景：Group Probe

9.1 聚合：定位 group，再初始化和更新状态

流程示意：GroupingSet::addInputForActiveRows
  prepareForGroupProbe
    解码 key → 按配置移除 NULL → 计算 ID/hash
    编码失效时重新选择模式、重建并重新准备输入
  groupProbe
    命中：hits[row] 指向已有 group
    未命中：newRow → storeKeys → 写索引 → 记录 newGroups
  initializeNewGroups
  对有效输入更新 accumulator

insertEntry 负责分配 RowContainer 行、存 key、建立索引；normalized-key 模式还会写入行前的组合 ID。聚合函数的初始化与更新由 GroupingSet 接着完成，顺序不能反过来。

以输入 key [A, B, A] 为例，空表处理后可能得到 hits = [rowA, rowB, rowA]，newGroups = [0, 1]。第三个输入更新 rowA，而不是新建第三个 group。对于稀疏选择集，以上下标仍是输入行号。

输出通常遍历 RowContainer，而不是扫描 bucket。部分聚合 flush 可以调用 clear(false) 复用索引分配，但该操作仍会把索引内容清零；它不是保留旧的 key → row 映射。

源码：GroupingSet 输入处理、insertEntry、clear。

9.2 全生命周期

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 → groupProbeWithPrefetch<true>()
    └── kHash   → groupProbeWithPrefetch<false>()，最多 64 状态窗口
         ↓
对 lookup.newGroups 中的新行初始化 accumulator
对所有命中行更新 accumulator（sum/count/...）

9.3 prepareForGroupProbe 详解

当前源码摘录（1d1b76567870）：velox/exec/HashTable.cpp:2633。省略外围声明；此片段未作为独立程序编译。

void HashTable<ignoreNullKeys>::prepareForGroupProbe(
    HashLookup& lookup,
    const RowVectorPtr& input,
    SelectivityVector& rows,
    int8_t spillInputStartPartitionBit) {
  checkHashBitsOverlap(spillInputStartPartitionBit);
  auto& hashers = lookup.hashers;

  for (auto& hasher : hashers) {
    auto key = input->childAt(hasher->channel())->loadedVector();
    hasher->decode(*key, rows);
  }

  if constexpr (ignoreNullKeys) {
    // A null in any of the keys disables the row.
    deselectRowsWithNulls(hashers, rows);
  }

  lookup.reset(rows.end());

  bool rehash = false;
  const auto mode = hashMode();
  for (auto i = 0; i < hashers.size(); ++i) {
    auto& hasher = hashers[i];
    if (mode != BaseHashTable::HashMode::kHash) {
      if (!hasher->computeValueIds(rows, lookup.hashes)) {
        rehash = true;
      }
    } else {
      hasher->hash(rows, i > 0, lookup.hashes);
    }
  }

  if (rehash || capacity() == 0) {
    if (mode != BaseHashTable::HashMode::kHash) {
      decideHashMode(input->size(), spillInputStartPartitionBit);
      // Do not forward 'ignoreNullKeys' to avoid redundant evaluation of
      // deselectRowsWithNulls.
      prepareForGroupProbe(lookup, input, rows, spillInputStartPartitionBit);
      return;
    }
  }

  populateLookupRows(rows, lookup.rows);
}

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

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

9.6 newGroups 的语义

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

newGroups 标出本批新建的 group 行，GroupingSet 先调用 aggregate 的初始化接口建立合法中间态，再按批次执行更新。不能将全部 aggregate 的初始化统一说成直接写入当前输入的第一个值；null、count、复杂中间态各有规则。
其余命中行：在已有 accumulator 上累加

10. Join 场景：Build 与 Probe

10.1 Join：保存行、建立索引、展开重复链

10.1.1 常规建表与输入阶段去重

常规 Join Build 先把各输入批次写入自己的 RowContainer，并收集 key 的 range / distinct 统计。收齐输入后，最后一个 build driver 收集其他表，执行 prepareJoinTable，合并必要的 VectorHasher 信息、选择模式并建立索引，最后通过 HashJoinBridge::setHashTable 发布。

这种批量建表方式减少了输入过程中的扩容和编码调整。Join 的输入阶段还支持去重：

可以丢弃重复 key 的场景，会通过 prepareForGroupProbe / groupProbe 在 addInput 中去重。
普通去重收益不足时可以放弃这条路径，退回保存输入行。
Counting Join 必须正确维护重复计数，源码明确不允许因收益低而放弃必要的去重。

是否允许丢弃重复行由 Join 语义及 filter 等条件决定，不能简单等同于所有 semi / anti Join。

源码：HashBuild::addInput 中的去重、prepareJoinTable、建表与发布的先后顺序。

10.1.2 两种重复链插入位置

allowDuplicates=true 时，行可以带 next 指针：

Array：新行替换索引入口
  插入前：slot → A → B
  插入 C：slot → C → A → B

Bucket：保留入口，把新行插到入口之后
  插入前：slot → A → B
  插入 C：slot → A → C → B

对应函数是 arrayPushRow 和 pushNext。没有 next 字段时，重复 key 不再形成链；counting 场景还会合并 count。链内插入顺序属于实现细节，SQL 输出排序仍需 ORDER BY。

源码：arrayPushRow / pushNext。

10.1.3 找到入口不等于已经生成 Join 结果

prepareForJoinProbe 准备 ID/hash，joinProbe 给每个选中的输入行写入第一个匹配的 build 行指针。随后 listJoinResults 展开结果，并受输出数组容量和 maxBytes 控制。

当前 listJoinResults 有三条路径：

// 源码摘录：分发条件；参数列表省略
if (iter.estimatedRowSize.has_value() && !hasDuplicates_) {
  return listJoinResultsFastPath(...);
}
if (nextOffset_ == 0 || !hasDuplicates_) {
  return listJoinResultsSingleHit(...);
}
return listJoinResultsInterleaved(...);

第一条路径对命中指针进行批量 gather / filter；第二条处理每个 probe 行至多一个结果的情况；第三条才负责重复链。行大小预算依据投影的 build 列大小计算，不能直接等同于最终序列化输出的总字节数。

10.1.4 重复链的 8 路交错遍历

图 11：以 3 条链示意最多 8 条链的交错访问：只有当前头 slot 直接输出，其余 slot 最多暂存 8 个结果，依次轮到它们输出。打开原图

2026-08-19 的实现改动把单链 nextHit 循环替换成 InterleavedWalkerState：

最多装入 8 个待处理 probe 行及其链入口，分别保存 cursor。
当前 head slot 直接发出结果；后面的 slot 同时向前走，把结果存进各自最多 8 项的 buffer。
非 head buffer 满时暂停那条链，避免无限超前。
head 完成后推进到下一 slot，先排空已有 buffer，再继续该链。
输出批次用完时保留 cursor、buffer 和排空位置，下次调用接着处理。

这里并行的是同一线程中多条独立指针链的内存访问。实现保持 lookup.rows 的 probe 行遍历顺序，借助 per-slot buffer 防止后面的 probe 行提前输出；它不提供 SQL ORDER BY 保证。atEnd() 还必须检查未排空的 walker，不能只判断 lastRowIndex 是否到末尾。

10.1.5 Miss、Join filter 和 probed 标志

includeMisses=true 表示在枚举结果时为没有匹配的 probe 行生成 (probe row, nullptr)。它不是“输出 right join 未匹配 build 行”的开关。Right/full 等场景的 build 侧补输出，要等 probe 阶段完成后扫描 listNotProbedRows 等接口。

上层 HashProbe 在 evalFilter 后，才按需要调用 setProbedFlag。仅仅 equality key 命中但 Join filter 不通过，不能提前把 build 行标记为最终已匹配。因此可以说索引在常规 probe 期间不再插入 key，但不能说整个表及行状态完全只读。

源码：结果分发与交错遍历、JoinResultIterator 状态、filter 后设置 probed flag、交错遍历测试。

10.2 Join Build 全流程

// 常规 Join build 主干；去重 / counting 分支另有输入期索引处理。
HashBuild::addInput -> 通过 RowContainer 保存 keys 与 payload
HashBuild::noMoreInput -> peer barrier -> 最后到达者 finishHashBuild
  合并 peer 的 partial table / 行状态
  table_->prepareJoinTable：合并 hasher 统计、选模式、构建最终索引
  joinBridge_->setHashTable：发布已准备好的表，通知 probe
// prepareJoinTable 在发布之前执行，不是 setHashTable 内部负责建表。

常规 Join build 先保存输入行，收齐 peer 状态后统一分析编码并构造最终索引，有利于利用完整分布信息。某些去重和 counting 路径在输入阶段就建立相应状态；“必须收齐才能建立任何索引”并不是接口的普遍限制。

10.3 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

10.4 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 侧日期范围不在其中的行可以立即跳过。

10.5 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 控制结果枚举是否保留未命中的 probe 行；它支持 left/full 等需要 probe 补行的上层逻辑。Right join 的未匹配 build 行通过另外的 build 侧扫描产生，不能把 includeMisses 直接等同于 LEFT/RIGHT OUTER 的统一开关。

10.6 Right/Full Outer Join：listNotProbedRows

流程化代码节选：省略外围声明与非主线分支；实现位置以相邻固定版本源码链接为准。

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

probed 标志需要在 key 候选通过额外 join filter、满足相应 join 匹配条件后设置。仅有哈希/键查找命中不等于最终匹配；过早标记会让 right/full 的未匹配 build 行漏输出。

11. 并行 Join Build

11.1 并行 Join Build：分区写同一张索引

有 executor、多个输入行容器、处于非 Array 模式，且每个分区的容量估计足够大时，rehash 可进入 parallelJoinBuild。判断使用 capacity_ / (1 + otherTables_.size()) 与配置阈值比较，不是直接统计每个分区实际行数。Array 在当前实现中不走这条路径；这并不等于 O(1) 寻址的数据结构没有并行化空间。

图 12：不同任务写入同一索引的不相交 bucket 区间，越界探测的行暂存为 overflow，等待所有分区完成后串行补入。打开原图

11.1.1 阶段一：按目标 bucket 区间给行做标记

先在共享索引的 bucket 地址空间上划出 [start, end) 区间，边界按 128 字节对齐。每个输入 RowContainer 的行计算 hash，再通过 bucketOffset(hash) 找到其所属区间，记录为 row partition。

这里的分区坐标是 bucket 偏移，与 spill 使用的 hash 位域不同。findPartition 以 SIMD batch 顺序扫描边界数组，找到第一个大于目标 offset 的边界。

11.1.2 阶段二：每个任务独占一个 bucket 区间

每个分区任务遍历所有输入行容器中属于该分区的行，在共享索引的自己区间内执行插入。Tag 和压缩指针都在 bucket 内，这也让相邻指针 word 的读改写不跨分区竞争。

线性探测需要走出本区间或发生受限的回绕时，插入停止，将 (row*, hash) 保存到该分区的 overflow 列表。不能越界写入别的任务负责的 bucket。

11.1.3 阶段三：同步后串行插入 overflow

等待分区构建完成后，主线程用保存的 hash 再插入 overflow，此时没有分区范围限制。该版本复用了 overflow hash，避免串行补入阶段重复计算。

每一阶段都有 syncWorkItems 同步；最后一个分区可以在当前线程执行，异常退出还有 guard 负责等待未结束的工作。因此准确的说法是“插入主路径用分区所有权避免逐槽锁竞争”。Overflow 的比例取决于数据和冲突分布。

可选 Bloom filter 还有单独的分区与构建阶段。它要求 HashTable<true>、非零且足够的大小预算、至少一列支持 Bloom filter；结果挂到 VectorHasher 上供上层动态过滤使用。它的消费位置在上层动态过滤路径，与表内的 value ID lookup 分开。

源码：并行入口与同步、findPartition / partitionRows、分区插入、Bloom filter 条件。

11.2 触发条件

流程化代码节选：省略外围声明与非主线分支；实现位置以相邻固定版本源码链接为准。

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 行）
}

11.3 三阶段并行协议

阶段一：行分区（并行）

每个子表分配 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 范围边界。这些行必须等所有分区都完成后才能串行插入，以避免跨分区写冲突。

11.4 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 的无效工作。

11.5 并行度与同步

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

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

12. Rehash 机制

12.1 扩容、重新编码与删除是三件不同的事

12.1.1 Rehash 重建索引，不搬动 payload

allocateTables 从 MemoryPool 分配连续的索引内存并清零，按容量计算 mask 和 bucket 数。rehash 遍历当前表及其他行容器，重新把行指针放入索引；已有 payload 行不因索引扩容而迁移。

initNormalizedKeys=true 表示从真实 key 重新计算组合 ID；为 false 且仍处于 normalized-key 模式时可以使用行前缓存。合并后的其他行容器需要服从主表的编码，不能直接使用各自曾经建立的 ID 映射。

如果启用了 spill，bucket index 使用的位还要与 spill partition 位域分开。源码的 checkHashBitsOverlap 检查这件事，避免同一 spill 分区只覆盖索引中的一小段位置。

12.1.2 扩容阈值要把括号写对

源码是：

// 源码摘录，两个重载组合起来使用
static uint64_t rehashSize(int64_t size) {
  return size * kHashTableLoadFactor;
}

uint64_t rehashSize() const {
  return rehashSize(capacity_ - numTombstones_);
}

即约为 **0.7 × (capacity - tombstones)**，返回整数时发生转换；不是 0.7 × capacity - tombstones。checkSize 比较新 distinct 估计与该阈值，再分配新索引并重建。初始索引至少 2048 槽，结合已有规模和新批次做预估。

12.1.3 Tombstone 保护跨 bucket 的探测链

删除时先通过 hash 定位到目标行指针。若所在 bucket 已经有 empty，eraseHit 可把该槽设为 empty；否则设成 0x7f，让可能越过该 bucket 的查找继续前进。判断单位是整个 tag group，不是只看被删除槽的相邻一个位置。

插入遇到 tombstone 后要先记住它，继续查找同 key；直到能确认没有匹配时才复用它。这避免把一个原本已有的 key 插成两个索引项。

Array 模式直接清空对应指针槽。桶式模式删除索引后，eraseWithHashes 还把行从所属 RowContainer 中移除；组合表会按实际所属行容器分派。这不是任意删掉重复链内部节点的通用接口。

12.1.4 当前 spill reclaim 路径

ProbeState 注释提到删除与 spill 的关联，但当前检查到的 HashBuild / HashProbe reclaim 路径是先 spill，再 table_->clear(true)。这条调用链以整表释放完成 reclaim。

clear(false) 清空行容器和索引内容但复用索引分配；clear(true) 还释放连续索引内存。它们与单项 erase、tombstone 复用、重新选择编码各有不同目的。

源码：allocateTables / checkSize、rehash 与 setHashMode、rehashSize、erase、HashBuild reclaim、HashProbe reclaim。

12.1.5 官方的“70% 后翻倍”对应哪段实际控制流

官方文档用“负载超过 0.7，分配双倍索引并重新插入”解释扩容。这是很好的入门模型，但当前代码以已有 distinct、这一批可能新增的项数、tombstone 数共同决定容量。checkSize 的阈值约为 0.7 × (capacity - numTombstones)，新容量来自 nextPowerOfTwo(max(newNumDistincts, capacity - numTombstones) + 1)。常见渐进增长会表现为翻倍；一批输入很大时可以跨过多个容量档，有较多 tombstone 时也不应把 rehash 理解成必然双倍增长。

重建时遍历已经保存的行、重新计算或读取 key 编码，再把行指针插入新索引。原表已经区分过 distinct keys，因此合适的重建路径可以省去正常插入中的重复 key 判定；但这里仍有模式切换、normalized key 初始化和关联行容器等分支，不能把整段实现简化成只复制旧 bucket 字节。索引位置变化，RowContainer 中的 payload 地址继续作为定位依据。

这一差别也说明为什么 HashProbe 与聚合的扩容行为不同：Join probe 只读已建好的索引；聚合在批次推进中可能不断发现新 group，要在插入前为潜在增长留余量。桶大小、负载阈值、预取和批量 API 应作为同一个访存设计看待，而不是彼此独立的常量。

源码：checkSize、初始容量估算。

12.2 触发时机

流程化代码节选：省略外围声明与非主线分支；实现位置以相邻固定版本源码链接为准。

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

当前阈值约为 0.7 × (capacity − numTombstones)，注意 tombstone 在括号内。Tombstone 占据探测路径且影响有效槽空间，重建会清理它；数值比较应按源码的整数计算和边界处理读取。

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 倍作为初始预估（假设下一批次数据量相当）。

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

12.4 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 映射已合并到主表，需要重新编码。

12.5 模式切换引发的 rehash 链

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

setHashMode(kHash):
    for hasher: hasher.resetStats()  // 清空所有 value_id 映射
    rows_->disableNormalizedKeys()   // 停用 normalized key 表示；不等于逐行搬移并回收前缀字节
    capacity_ = 0                    // 强制重新分配
    checkSize(numNew, ...)           // 按 kHash 大小重分配 + rehash

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

13. Erase 与 Tombstone

13.1 tombstone 的必要性

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

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

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

13.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 之前开始的探测，遇到空槽都会停止，不存在被截断的链。

13.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 是维护单项删除与探测链的能力。当前 HashBuild 和 HashProbe 的主要 spill reclaim 路径使用 clear(true) 清理整张索引及相应状态；本节保留 erase 的算法分析，但不把它当成当前分区 spill 的调用事实。

14. 与上层算子的接口

14.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);

14.2 Join Build 算子（HashBuild）

HashBuild::addInput(batch)
  保存输入行；是否同时建立去重 / counting 状态取决于 join 模式
HashBuild::noMoreInput / finishHashBuild
  peer barrier -> 协调者合并局部状态
  prepareJoinTable(otherTables, ...) -> 合并 VectorHasher / decideHashMode
    -> rehash 或满足条件时 parallelJoinBuild
  HashJoinBridge::setHashTable -> 发布完成的表
HashBuild::addRuntimeStats -> 上报容量、构建与编码统计

14.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 列

14.4 Runtime 统计指标

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

指标名	含义
`hashtable.capacity`	hash 槽总数
`hashtable.numDistinct`	numDistinct 的含义取决于更新路径。聚合通常对应 group 数；普通 Join build 的 numDistinct_ 初始会累加保留行数，因此不能仅凭字段名把所有场景都解释成已去重 key 数。
`hashtable.numRehashes`	rehash 发生次数
`hashtable.numTombstones`	当前 tombstone 槽数
`hashtable.hashMode`	当前枚举值为 0=kHash、1=kArray、2=kNormalizedKey；解读 profile 必须按当前枚举，而不是按本文章节顺序编号。
`hashtable.buildWallNanos`	build 阶段耗时
`hashtable.parallelJoinBuildWallNanos`	并行 build 耗时
`hashtable.cacheHit` / `cacheMiss`	HashTableCache 命中情况

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

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

15.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 永远为真？通过类型/编码层面把不可能性"焊死"，是最经济的"检查"。

15.2 单向状态转移

模式并非固定三级单向降级链。Array/NormalizedKey 可在重新分析与编码后重新选择；进入 Hash 才退出 value ID 优化并不再切回。应把这一终态约束与可重新决策的编码阶段分开建模。

流程化代码节选：省略外围声明与非主线分支；实现位置以相邻固定版本源码链接为准。

// setHashMode 没有 kHash → kArray 的路径

简化点是进入 Hash 后无需维持回到编码模式的路径；Array 与 NormalizedKey 之间及重新编码的条件仍需完整分析，不能用一个假定的三条单向边图替代实际决策。

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

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

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

流程化代码节选：省略外围声明与非主线分支；实现位置以相邻固定版本源码链接为准。

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

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

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

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

ProbeState 切成三个阶段：

流程化代码节选：省略外围声明与非主线分支；实现位置以相邻固定版本源码链接为准。

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

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

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

15.5 值语义的状态机栈对象

当前相关批量探测路径将 ProbeState 放在局部对象或固定大小局部数组中，保存 key、bucket 地址及探测中间态，以便分阶段推进。这里的分配方式属于调用点，不是 ProbeState 类型天然保证永不分配在堆上的性质。

流程化代码节选：省略外围声明与非主线分支；实现位置以相邻固定版本源码链接为准。

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

ProbeState 把单次探测状态集中在局部对象中，避免为每次探测单独分配堆对象。字段的寄存器分配由编译器决定，多路交错和寄存器压力可能导致部分状态在栈上；不能仅用 sizeof 推断全部字段始终放在寄存器。

15.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."——代码也一样，每个函数名应该读起来像一个动作。

15.7 注释只解释"为什么"，不解释"什么"

最典型的例子：

流程化代码节选：省略外围声明与非主线分支；实现位置以相邻固定版本源码链接为准。

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

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

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

15.8 小类一事一做

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

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

15.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;

kBucketSize、kHashTableLoadFactor 和 kAssumedDramLatencyNs 等命名常量让布局、阈值与假设更清楚。它们是值得学习的具体写法，不应扩大成整个文件绝不存在数字字面量的保证；尤其 Assumed 明确表示估计值而非硬件实测。

15.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 是最诚实的接口。

15.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 的地方失去信号。

CHECK/DCHECK 同时承担内部不变量、输入边界和状态诊断；选择位置需要平衡后果、可观察性与热路径成本，不能概括为发布版 CHECK 永远不出现在内部热路径。

15.12 if constexpr 让特性"消失"而非"禁用"

流程化代码节选：省略外围声明与非主线分支；实现位置以相邻固定版本源码链接为准。

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

if constexpr 可按 ignoreNullKeys 的模板值移除另一分支；在 ignoreNullKeys=true 路径中，跳过 null 的逻辑恰好是需要保留的部分。是否最终产生独立函数调用还受内联与优化影响，不能把 true 特化解释成删除 deselectRowsWithNulls。

15.13 一句话总结

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

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

16. 位操作精解

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

16.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 的不同位段，统计独立。

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

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

流程化代码节选：省略外围声明与非主线分支；实现位置以相邻固定版本源码链接为准。

VELOX_CHECK(bits::isPowerOfTwo(size));

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

流程化代码节选：省略外围声明与非主线分支；实现位置以相邻固定版本源码链接为准。

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

对无符号值及非零的 2 的幂除数，x % n 可等价写为 x & (n−1)。编译器知道常量 n 时常会自动做这个变换；变量除法与位与的实际延迟依赖 CPU，不能对所有 % 表达式赋予固定周期。

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

流程化代码节选：省略外围声明与非主线分支；实现位置以相邻固定版本源码链接为准。

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

16.2.3 bits::nextPowerOfTwo 与 popcount

流程化代码节选：省略外围声明与非主线分支；实现位置以相邻固定版本源码链接为准。

sizeBits_ = __builtin_popcountll(sizeMask_);

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

16.2.4 isPowerOfTwo 的位操作判定

流程化代码节选：省略外围声明与非主线分支；实现位置以相邻固定版本源码链接为准。

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

对无符号 x，判断 2 的幂必须同时满足 x != 0 与 (x & (x−1)) == 0；只检查后一项会把 0 也接纳。减一及移位例子应明确类型宽度，避免在普通 C++ 中引入有符号溢出或超宽移位。

16.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);

16.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);   // ✅ 但每次走函数调用

表达式读取并保留高两字节，合并新指针后还需写回。实际汇编可折叠内存操作，取决于编译器与目标；不能仅数 load/and/or 而遗漏 store，也不能没有测量就宣称最快。

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

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

流程化代码节选：省略外围声明与非主线分支；实现位置以相邻固定版本源码链接为准。

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

16.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）。

16.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 调度），少一个数据依赖。

16.4.3 硬件指令对应

内建函数	x86	ARM	cycle
`__builtin_ctz`	BSF / TZCNT (BMI1)	RBIT + CLZ	3-4
`__builtin_clz`	BSR / LZCNT	CLZ	3-4
`__builtin_popcount`	POPCNT（独立 CPU 特性）	CNT (NEON)	3

位扫描和 popcount 可减少逐位循环工作，但速度取决于位宽、数据分布、目标指令和上下文。POPCNT 是独立 CPU 特性，并非 SSE4.2 所保证；这里只说明语义与可能映射，不给未经测量的数量级收益。

16.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 的显式比较（§8.10 的优化）。

16.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 直接区分有效/无效

最高位可承载一个标记，但前提是表示中确实有可借用的位，且不会与有效数据冲突。& 0x80、无符号右移和有符号比较可以表达相应测试；它们的生成指令、延迟和吞吐随类型、编译器、目标 CPU 及上下文变化，不能统一承诺只需 1 cycle。

16.7 散落的位掩码构造

bits::lowMask(n) 表达低 n 位为一的 mask；手写 (1ULL << n)−1 时必须处理 n 等于类型宽度等边界，不能对 uint64_t 执行移位 64。库函数的边界契约应以其实现为准。
kPointerMask = bits::lowMask(48) = 0x0000FFFFFFFFFFFF：6 字节指针的有效位掩码
kFullMask = (1 << kSlotsPerBucket) - 1 = 0xFFFF：16 个 slot 的全 1 掩码，限定 bitmask 范围

16.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 固化语义：

流程化代码节选：省略外围声明与非主线分支；实现位置以相邻固定版本源码链接为准。

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

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

17. 设计哲学与架构精髓

前面的实现章节逐层拆解了数据结构、执行路径与工程细节。本章自上而下回到设计层面，回答一个核心问题：为什么是这套架构而不是别的？

17.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）

布局需要权衡 metadata 扫描、随机访存和 payload 读取。非 Array 模式的 Bucket 是 128B；在 64B cache line 平台上占两条线，16B tag 可批量比较，候选行指针按需使用。Rehash 的 kHashBatchSize 为 1024，批量处理行指针有助于组织扫描和预取；cache miss 的代价却取决于命中的缓存层级、CPU、NUMA 和排队，不能统一写成 100ns。

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

访存延迟既可以通过减少访问次数降低，也可以通过交错独立请求隐藏。从 bucket 预取、ProbeState 分阶段探测，到当前聚合 64 状态窗口与 AdaptivePrefetch 的距离调整，目标都是在等待期间推进其他工作。早期四状态展开有助于说明机制；软件窗口并不保证所有请求已返回 L1，也不代表固定倍数的性能收益。

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

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

（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，当前 HashTable 的 payload 则由 RowContainer 保存成行，便于按 key 取得同一行的多个字段和稳定行地址。VectorHasher 负责 key 的 hash、value_id 与编码统计；保存输入行由 HashBuild / GroupingSet 等调用方与 RowContainer 完成。行式 payload 是本实现为 Join / Aggregation 选择的布局，并不是所有 hash table 必须满足的条件；其他设计也可分离 key、payload 或采用列式存储。

17.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 融合

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

17.3 几个核心决策的"为什么"

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

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

链表型索引需要额外链接及间接访问，但也可以使用 arena/slab 批量分配，并不必然每个 entry 单独 malloc。开放地址的紧凑目录改善候选扫描局部性，真实缓存代价应按分配方式和工作集比较。
链表节点本身有 next 指针的额外开销
难以向量化

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

同一 bucket 的所有候选 slot 连续 → cache 友好
与硬件 prefetcher 顺序访问模式协同
Bucket 化和 SIMD 减少每组 tag 检查的指令开销，但 cluster 仍会增加扫描 bucket 数和 key/payload 访问，退化代价不会接近零。负载、hash 分布和 tombstone 策略仍然重要。

17.3.2 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

PCMPEQB 与 PMOVMSKB 可以完成 tag 比较和位图提取，但一次完整 bucket 探测还包含加载、mask 处理、候选迭代和可能的 key 比较。16 槽与 128-bit 标签向量相配是合理布局取舍，不等于整次探测只有两条指令。

17.3.3 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 完全沿用并向量化。

17.3.4 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	浪费物理地址空间

6-byte 表示要求所保存指针落在实现允许的低 48 位地址范围。x86-64 可存在更宽的虚拟地址空间，5-level paging 也不会自动使高于 48 位的用户地址消失；这里描述的是该数据结构的地址假设，不是架构永远保证高 16 位为零。

17.3.5 E. 为什么 hashMode 需要三档？

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

模式           关键条件 / 收益
Array          编码域和空间估计合适时直接寻址
NormalizedKey  64 位编码可表示时简化 key 比较
Hash           通用 key 处理，或命中成本启发式分支
实际选择还涉及 range / distinct 的乘积、预留比例和已有状态。
相同行数可对应完全不同分布；维度表 / 事实表也不是模式判断条件。

一档（只有 kHash）：低基数列也走通用 MurmurHash，多列也要逐列比较，每次 probe 都是 cache miss + 函数调用
两档（kArray + kHash）：跨过 2M 阈值就跌到 kHash，损失多列融合的中等基数场景
三种模式：Array 避免常规 bucket 探测，NormalizedKey 用可编码的 64 位 key 简化比较，Hash 提供通用后备。选择由范围、distinct 编码能力、空间估计及启发式共同决定，不能承诺覆盖所有分布下的最优方案。

模式分析可能在建表和编码失效后的重新选择时发生，聚合输入变化也会触发相关路径。其成本通常可被大量查找摊销，但不能保证每张表全生命周期只执行一次。

17.3.6 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 仍然足够低。

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

如果在 addInput 时立即建索引：

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

延迟到 noMoreInput 才 prepareJoinTable：

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

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

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

共享插入可采用锁或原子协调，性能取决于争用与算法；不能用一个固定 CAS 纳秒数证明它普遍不可行。当前实现按 bucket 范围划分写入所有权，减少主插入路径的共享同步，代价是分区标记、结果汇合和 overflow 串行回填。

Partition 方案（§11.3）：

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

代价包括 partition 标记、实际写入两次组织工作及 overflow 收尾。收益是在拥有独占 bucket 区间的正常插入阶段减少共享锁争用；准备、任务调度、等待与最终回填仍需要同步，整个 build 不是无锁算法。

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

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

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

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

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

层次	机制	时间尺度	相关章节
指令级（SIMD）	PCMPEQB 一条指令 16-way 比较	依微架构和指令形式而定，本文未测量周期	§8.3
微架构（OoO + prefetch）	`__builtin_prefetch` 让 cache 加载与计算并行	~10 cycle	§8.3
循环级（软流水线）	4-way / 64-way ProbeState 交错三阶段	~100 cycle	§8.4, §8.5
线程级（partition）	多线程 build 不相交 bucket 范围	ms 级	§11
算子级（异步）	HashBuild ↔ HashProbe 通过 HashJoinBridge 异步衔接	s 级	§14

这些机制可在不同层次配合，但收益不能相乘或预设固定倍数。瓶颈可能转移到带宽、重排、分区不均或结果物化；端到端加速需要固定 CPU、数据、查询和基线的实测。

17.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：按 bucket 区间划分写入所有权，正常插入避免跨线程写同一个 bucket；随后收集任务并处理 overflow。
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）局部化复杂度

17.6 一句话总结

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

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

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

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

18.1 读代码时应保留的边界与验证入口

18.1.1 把正确性不变量和性能推断分开

设计	源码保证的性质	仍需数据和测量判断的部分
Value ID	映射有效时可以无碰撞组合 key	range / distinct 的空间成本、重新编码频率
Tag SIMD	一批过滤 16 个候选 slot	候选误命中率、真实 key 比较成本
Payload 与索引分离	rehash 不搬动真实行	指针跳转、变长字段、cache miss 数量
分阶段预取	提供交错独立访问的程序窗口	实际隐藏多少延迟、最合适批宽
Bucket 分区所有权	正常并行插入不越过各自区间	分区倾斜、overflow 比例、同步成本
多链交错遍历	buffer 有界并保持 probe 行遍历顺序	不同链长和输出预算下的吞吐收益

端到端收益取决于各段实际占比及其相互影响，需要结合 workload 测量。if constexpr (ignoreNullKeys) 为 true 时保留 NULL 过滤代码，为 false 时移除该代码；它在编译期选择 NULL 处理路径，探测本身仍有候选比较、命中和 miss 等运行时分支。

pushNext 通过 VELOX_CHECK_GT(nextOffset_, 0) 检查 next 字段存在，再执行重复链插入。

18.1.2 统计值不能脱离更新位置解释

hashtable.hashMode 是 enum 的整数值：0 = kHash，1 = kArray，2 = kNormalizedKey。numDistinct_ 在聚合插入时随新 group 增长，但常规 prepareJoinTable 会先设成所有保留 build 行数之和，并用它估算容量。因此 Join Build 中该指标可作为容量估计基数，具体含义需要结合更新阶段解释。

排查性能时可以先看所选模式、capacity、rehash 次数和 tombstone，再结合 VectorHasher merge、分区、并行 build 及 cache 的算子统计。具体含义由统计更新点决定。

18.1.3 已有测试提供的阅读入口

本文对照了以下测试源码；这里列的是测试覆盖内容，不表示本文重新运行了 Velox 的完整 C++ 测试集。

测试	用来核对什么
`string1DenseArray`、`string2Normalized`	字符串也能进入 value ID 模式
`bestWithReserveOverflow`、`enableRangeWhereCan`	编码空间及 range / distinct 选择的边界
`arrayProbeNormalizedKey`	模式重新选择及已有行重建
`listJoinResultsSize`	输出行数与字节预算
`listJoinResultsInterleaved`	超过 ahead window 的链、跨批恢复、miss、probe 行顺序
`nextBucketOffset`、`groupBySpill`	桶式探测边界与 spill 相关场景

源码：runtime stats、模式与尺寸测试、交错结果测试。

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

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

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

18.2 位操作（Bit Operations）

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

HashTable 不把"这个 slot 是空 / 满 / 删除"存成一个 enum（4 字节），而是压进一个 8-bit 的 tag（§6.3）。理由是带宽：16 个 tag 打包成 16 字节正好能被一条 SSE 指令一次性吃进寄存器（§8.3）。指针压到 6 字节而非 8 字节（§6.3），是因为实现要求这些指针可用低 48 位表示；并非所有 x86-64 地址模式都天然满足——省下的 2 字节 × 16 让整个 Bucket 卡进 128 字节边界。位操作在这里不是抠门，是为了让数据结构整体落进"2 cache line"这个硬性预算。

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

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

贯穿的工程纪律：最高位（MSB）被复用为"类型标签"（§16.6）——tag 的 bit 7、PMOVMSKB 的结果都把 MSB 当作"有效/无效"的开关，这让 SIMD→scalar 的桥接（§8.10）用 movemask 提取位图；它仍有指令与依赖成本。

18.3 内存布局（Memory Layout）

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

Bucket = 128 字节 = 2 cache line，是整个数据结构的"原子"（§6.3）。关键决策是 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 固化（§16.7）：mask 不许碰高 16 位、Bucket 大小必须是 2 的幂——把不变量写进编译期，而不是寄望于 code review 发现。

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

18.4 访存模式（Memory Access Patterns）

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

HashTable 通过多条独立查找重叠访存等待。代价要区分 L1 / L2 / LLC miss 与真正访问 DRAM；以下是源码中的处理层次，不是固定延迟或加速倍数的测量：

单条预取   →  __builtin_prefetch(下一个 bucket)
4-路流水线  →  ProbeState 同时推进 4 个 key 的探测（§6.3）
64-路流水线 →  normalized key probe 一次发射 64 个预取（§6.4）
自适应步长  →  AdaptivePrefetch 测前 16 轮耗时、结合 100ns 假设选定 lookAhead ∈ [4,32]（§6.5）

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

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

preProbe / firstProbe / fullProbe 拆开地址计算、预取与候选验证，使调用方可以交错推进不同 key。AdaptivePrefetch 则测量前 16 次循环总耗时，并结合固定的 100ns DRAM 延迟假设计算 lookAhead，限制在 [4,32]，随后固定该距离。它适应的是循环速度，既没有直接测量硬件 DRAM 延迟，也没有搜索或保证最优预取距离。

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

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

18.5 SIMD（数据并行）

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

标量哈希表探测内层是"逐 slot 比较 + 分支"，每次比较都可能分支误判。HashTable 把一个 Bucket 的 16 个 tag 一次性载入 XMM 寄存器，用 PCMPEQB 做 16 路并行字节比较，再用 PMOVMSKB 压成一个 16-bit mask（§8.3）。16 次比较 + 16 次分支，比较与位图提取可用两条核心指令表达，此外仍有加载、候选迭代、key 比较及控制流。

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

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

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

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

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

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

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

这是经典的无共享并行（shared-nothing）思路：把竞争消灭在数据划分阶段，而不是在访问阶段用锁去仲裁。绝大部分工作（阶段 1、2）完全并行，只有少量边界 case（阶段 3）退回串行——用将大部分正常分区内插入并行化，再串行处理 overflow；比例取决于分布和负载，此处没有固定 95%/5% 的测量。

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

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

与访存模式的耦合：分区的另一个收益是局部性——索引写入按 bucket 范围隔离；行读取、共享元数据和 cache 边界仍需分析，不能保证完全没有共享或 cache 干扰。多线程范式和访存模式在这里是同一个决策的两面：分区既消除竞争，又改善局部性。

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

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

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、并发这五件事被设计成互相成全——每个决策都同时在多个维度上买单和收益。这是"系统级品味"区别于"局部优化"的根本所在。

19. 从探测成本回看表示选择与复杂度

前面的位操作、SIMD、预取和分区协议，分别改变一次查找中的不同成本。评价它们需要先明确目标：减少无效候选、减少真实 key 与 payload 的访问、重叠独立访存，或减少并行建表的写入争用。代码短、分支少或技巧多，本身都不是性能结论。

设计选择	它依赖的条件与收益	同时承担的代价
按数据选择三种表示	合适的基数与范围让直接定位或紧凑 key 有利可图	需要统计、编码有效性检查及必要的重建；收益取决于数据分布
索引与行 payload 分离	目录可重新组织，行数据不必随每次索引扩容整体搬动	真实比较与物化仍有间接访问，宽行成本不会因 tag SIMD 消失
tag 筛选后再比较 key	大量候选可在紧凑标签区被排除	tag 会误命中；负载、hash 分布和 tombstone 影响扫描长度
软件流水线与预取	有足够独立查找时可以重叠访存等待	增加在途状态与代码复杂度，也可能带来无效预取和带宽压力
按 bucket 范围分配并行写入	主插入阶段可以减少共享写入协调	需要分区准备、完成汇合和 overflow 处理，倾斜会影响收益

这里值得借鉴的代码组织，是把优化所需的状态和约束放到明确的位置：ProbeState 保存一次探测的进度，VectorHasher 管编码有效性，RowContainer 管 payload，调用方管理运算语义。抽象边界使一个优化的前提能够被检查，也使通用回退仍有清楚的落点。

这些选择没有共同的固定加速倍数。应分别观察 probe 次数、候选比较、工作集、输出行数、编码重建和并行分区成本，再用实际负载判断组合收益。前面保留的设计与工程实例提供分析对象；其中关于缓存、地址范围和吞吐的概括，都应受相应实现前提和测量条件约束。

同窗口插入检查把性能与正确性连接起来：提前读 tags 可以重叠延迟，却引入观察过时的可能。用 numDistinct_ 是否变化选择 extraCheck，使纯命中窗口保留较轻路径，又让新 group 对窗口中后续重复 key 可见。分析软件流水线时应同时问“隐藏了什么等待”和“前置读取在哪些修改后失效”，不能只数预取指令。

20. 附录：关键常量速查

20.1 附录：源码阅读路线与常量

推荐按以下顺序在固定版本中阅读：

HashLookup 与接口：确定输入、输出和所有权。
GroupingSet / HashBuild / HashProbe：先看调用方如何使用表。
VectorHasher、decideHashMode：理解 key 的表示及何时重建。
Bucket、ProbeState：对照字节布局读探测循环。
listJoinResults、parallelJoinBuild：分别追重复链和并行建表。

常量	该版本的值	作用
`kHashTableLoadFactor`	0.7	桶式表 rehash 阈值
`kArrayHashMaxSize`	`2 << 20`	常规 Array 选择分支的空间阈值
`sizeof(Bucket)`	128 B	16 tags + 96 B pointers + 16 B padding
`kPointerSize`	6 B	索引中的压缩行指针
`kEmptyTag` / `kTombstoneTag`	`0x00` / `0x7f`	空与已删除状态
`kHashBatchSize`	1024	行容器扫描与重建批次
`kPrefetchSize`	64	桶式 Join 插入及 normalized-key Join Probe 批次
`kNumParallelChains` / `kAheadWindow`	8 / 8	重复链交错数与非 head 缓冲上限

这条阅读路线的核心是先分清索引定位、行的生命周期、SQL 输出语义，再分析 SIMD、预取和分区对各段成本的影响。

布局和插入的入门图解还可对照官方开发文档：Hash Table。本文已把它的布局、寻址示例、三种桶状态、模式用例与调用方介绍整合到相应章节，并按固定源码修正 NULL 编码、类型支持、容量边界和扩容概括。图为重新绘制的 SVG；原有实现、SIMD、位操作、并行 build 和设计分析全部保留。

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

21. 附录：类型模板实例化

HashTable 有两个显式实例：

流程化代码节选：省略外围声明与非主线分支；实现位置以相邻固定版本源码链接为准。

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

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

源码核对（2026-09-20）：本轮按 Velox 1d1b76567870 核对关键接口、控制流、默认值与边界条件。当前源码摘录附固定版本链接；流程伪代码用于说明分支，不是可直接编译的程序。未对全文示例做独立编译或性能复测。涉及宿主集成与历史实验的数据，按各节标注的来源理解。

1. HashTable 的职责、输入输出与使用方式

2. 一批输入怎样变成 group 状态与 Join 结果

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

3.1 两类调用方的根本差异

3.2 聚合场景对表的诉求

3.3 Join 场景对表的诉求

3.4 不同 Join 模式对表的诉求

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

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

4.1 先建立整体模型：编码、索引、行容器

4.1.1 两类调用方，共用一套定位能力

4.1.2 NULL 的处理由调用方语义决定

4.2 类层次

4.3 ProbeState：单次探测的状态机

4.4 HashLookup：probe 的输入输出载体

5. 三种 Hash 模式

5.1 从 key 到三种表表示

5.1.1 Value ID 是表内部的编码

5.1.2 三种模式分别省掉了哪一步

5.1.3 decideHashMode 的决策顺序

5.1.4 编码失效后会重新决策，不一定马上进入 kHash

5.1.5 把官方示例还原为编码空间

5.2 模式枚举与触发条件

5.3 kArray 模式

5.4 kNormalizedKey 模式

5.5 kHash 模式

5.6 模式切换

6. 内存布局详解

6.1 索引与 payload：内存实际怎么排

6.1.1 字节 Bucket

6.1.2 字节指针为什么要保留相邻两字节

6.1.3 Bucket 地址和 slot 编号来自不同的计算

6.1.4 RowContainer 才保存真实 key 和 payload

6.1.5 从整张索引到一个 bucket：跟着数字走一遍

6.1.6 空桶、半满桶、满桶：布局怎样参与插入

6.2 kArray 模式

6.3 kHash / kNormalizedKey 模式：Bucket 结构

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

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

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

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

7. VectorHasher：Key 编码引擎

7.1 两种编码模式

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

7.3 lookupValueIds()：join probe 专用

7.4 merge()：并行 build 后的 VectorHasher 合并

8. SIMD 技巧专章

8.1 一次探测怎样执行，怎样重叠访存

8.1.1 HashLookup 中哪些数组按输入行号索引

8.1.2 ProbeState 的三个阶段

8.1.3 路 / 64 路流水线是指令交错，不是线程

8.1.4 extraCheck 修复同一批插入造成的过期观察

8.1.5 SIMD 与预取的适用范围

8.2 平台抽象：TagVector

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

8.4 技巧 2：聚合预取窗口与同窗口插入一致性

8.5 技巧 3：Join Probe 与 Join Insert 的批量预取

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

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

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

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

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

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

9. 聚合场景：Group Probe

9.1 聚合：定位 group，再初始化和更新状态

9.2 全生命周期

9.3 prepareForGroupProbe 详解

9.4 arrayGroupProbe：kArray 快路径

9.5 groupProbe kHash 路径

9.6 newGroups 的语义

10. Join 场景：Build 与 Probe

10.1 Join：保存行、建立索引、展开重复链

10.1.1 常规建表与输入阶段去重

10.1.2 两种重复链插入位置

10.1.3 找到入口不等于已经生成 Join 结果

10.1.4 重复链的 8 路交错遍历

10.1.5 Miss、Join filter 和 probed 标志

10.2 Join Build 全流程

10.3 insertForJoin：重复 key 的链表处理

10.4 prepareForJoinProbe：probe 侧的快速剪枝

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