揭秘Velox高性能哈希表核心优化

HashTable

Velox 的 HashTable 是其执行引擎的核心组件之一，性能表现非常出色。它的设计哲学是最大化利用现代 CPU 的特性，如 SIMD（单指令多数据流）、缓存层次结构和多核并行。

SIMD 友好的内存布局（受 F14 HashTable 启发）

Velox 的 HashTable 在内存布局上借鉴了 Facebook 开源的 F14 HashTable 的思想，使其对 SIMD 操作极为友好。

• Bucket-Slot 结构: HashTable 被组织成一个 Bucket 数组。每个 Bucket 大小为 128 字节（通常对应两个 CPU 缓存行），内部包含 16 个 slot。
• Tag 和 Pointer分离: 每个 slot 包含一个 7-bit 的 tag 和一个指向实际数据行（RowContainer 中）的指针。在一个 Bucket 内部，16 个 tag 连续存储，然后是 16 个指针连续存储。
• 16路并行比较: 这种布局允许 CPU 使用一条 SIMD 指令（如 AVX2/NEON）一次性加载 16 个 tag，然后用另一条 SIMD 指令将这 16 个 tag 与目标 key 的 tag 进行并行比较。这极大地加速了查找过程，因为大部分不匹配的 slot 可以在一次 SIMD 比较中就被过滤掉，只有当 tag 匹配时，才需要进行昂贵的指针解引用和完整的 key 比较。

ProbeState 类完美地体现了这一点：

HashTable.cpp

// ... existing code ...
  // Use one instruction to make 16 copies of the tag being searched for
  template <typename Table>
  inline void preProbe(const Table& table, uint64_t hash, int32_t row) {
    row_ = row;
    bucketOffset_ = table.bucketOffset(hash);
    const auto tag = BaseHashTable::hashTag(hash);
    wantedTags_ = BaseHashTable::TagVector::broadcast(tag);
    group_ = nullptr;
// ... existing code ...
  }

  // Use one instruction to load 16 tags. Use another one instruction
  // to compare the tag being searched for to 16 tags.
  // If there is a match, load corresponding data from the table.
  template <Operation op = Operation::kProbe, typename Table>
  inline void firstProbe(const Table& table, int32_t firstKey) {
    tagsInTable_ = BaseHashTable::loadTags(
        reinterpret_cast<uint8_t*>(table.table_), bucketOffset_);
    table.incrementTagLoads();
    hits_ = simd::toBitMask(tagsInTable_ == wantedTags_);
    if (hits_) {
      loadNextHit<op>(table, firstKey);
    }
  }
// ... existing code ...

wantedTags_ 通过 broadcast 指令将单个 tag 复制 16 份，loadTags 加载 16 个 table 内的 tag，tagsInTable_ == wantedTags_ 是一次 SIMD 比较，simd::toBitMask 将比较结果转换为一个位掩码 hits_，快速定位匹配的 slot。

向量化（Vectorized）的探查与插入

Velox 的核心思想是向量化执行，HashTable 也不例外。它不是一次处理一个 key，而是一次处理一批 key。

• 批处理: groupProbe 和 joinProbe 等函数接收一个 HashLookup 对象，该对象包含了对一批行的引用（lookup.rows）。
• 指令级并行 (ILP): 在 groupProbe 的主循环中，它一次处理 4 个 key（state1 到 state4）。通过将多个独立 key 的探查操作交织在一起，可以更好地利用 CPU 的超标量和乱序执行能力，隐藏内存访问延迟，提高指令吞吐率。

// ... existing code ...
  ProbeState state1;
  ProbeState state2;
  ProbeState state3;
  ProbeState state4;
  int32_t probeIndex = 0;
  int32_t numProbes = lookup.rows.size();
  auto rows = lookup.rows.data();
  for (; probeIndex + 4 <= numProbes; probeIndex += 4) {
    int32_t row = rows[probeIndex];
    state1.preProbe(*this, lookup.hashes[row], row);
    row = rows[probeIndex + 1];
    state2.preProbe(*this, lookup.hashes[row], row);
// ... existing code ...
    state4.preProbe(*this, lookup.hashes[row], row);

    state1.firstProbe<ProbeState::Operation::kInsert>(*this, 0);
    state2.firstProbe<ProbeState::Operation::kInsert>(*this, 0);
// ... existing code ...
    state4.firstProbe<ProbeState::Operation::kInsert>(*this, 0);

    fullProbe<false>(lookup, state1, false);
    fullProbe<false>(lookup, state2, true);
// ... existing code ...
  }
// ... existing code ...

多种哈希模式 (HashMode) 的自适应选择

Velox HashTable 能够根据 key 的数据特性选择不同的工作模式，以达到最优性能。

• HashMode::kHash: 通用的哈希模式，使用我们上面讨论的 SIMD 优化的开放寻址哈希表。适用于任意类型的 key。
• HashMode::kArray: 当 key 是一个范围较小的整数时（例如，经过字典编码后的 ID），此模式会退化成一个简单的数组。它直接使用 key 的值作为索引来访问 table_ 数组，完全避免了哈希计算和冲突处理，速度极快。
• HashMode::kNormalizedKey: 当组合 key 由多个定长类型（如 BIGINT, INTEGER）组成时，可以将它们拼接成一个 64 位的 normalizedKey。在探查时，首先比较这个 64 位的 normalizedKey，如果匹配，再进行完整的、逐字段的详细比较。这大大减少了在 tag 匹配后进行昂贵比较的次数。

// ... existing code ...
template <bool ignoreNullKeys>
template <bool isJoin, bool isNormalizedKey>
FOLLY_ALWAYS_INLINE void HashTable<ignoreNullKeys>::fullProbe(
    HashLookup& lookup,
    ProbeState& state,
    bool extraCheck) {
// ... existing code ...
  if constexpr (isNormalizedKey) {
    // NOLINT
    lookup.hits[state.row()] = state.fullProbe<op>(
        *this,
        -static_cast<int32_t>(sizeof(normalized_key_t)),
        [&](char* group, int32_t row) INLINE_LAMBDA {
          return RowContainer::normalizedKey(group) ==
              lookup.normalizedKeys[row];
        },
// ... existing code ...
}

底层性能优化

• 内存预取 (Prefetching): 在探查逻辑的关键路径上，显式地使用了 __builtin_prefetch。例如，在 preProbe 中预取 bucket 的内存，在 loadNextHit 中预取可能匹配的数据行（group_）的内存。这可以提前将数据加载到 CPU 缓存中，从而隐藏内存访问延迟。

// ... existing code ...
  inline void preProbe(const Table& table, uint64_t hash, int32_t row) {
// ... existing code ...
    indexInTags_ = kNotSet;
    __builtin_prefetch(
        reinterpret_cast<uint8_t*>(table.table_) + bucketOffset_);
  }
// ... existing code ...
  template <Operation op, typename Table>
  inline void loadNextHit(Table& table, int32_t firstKey) {
// ... existing code ...
    }
    group_ = table.row(bucketOffset_, hit);
    __builtin_prefetch(group_ + firstKey);
    table.incrementRowLoads();
  }
// ... existing code ...

• 模板元编程: 大量使用模板（如 HashTable<ignoreNullKeys>，fullProbe<isJoin, isNormalizedKey>）在编译期生成针对特定场景（如 GroupBy vs. Join, 普通 Key vs. Normalized Key）高度优化的代码，避免了运行时的分支判断开销。

并行构建 (Parallel Join Build)

对于大规模的 Hash Join，构建（Build）阶段可能成为瓶颈。Velox 支持并行构建 HashTable。

• 它会将输入数据分区（Partition），然后启动多个线程，每个线程负责构建自己分区内的数据。
• 每个线程在 HashTable 的一个独立区域内工作，减少了线程间的同步开销。
• 这充分利用了现代多核 CPU 的处理能力，显著加快了大数据量下的 Join 操作。parallelJoinBuild() 和 buildJoinPartition() 等函数就是为此设计的。

总结

Velox HashTable 的精妙之处在于它是一个综合性的、多层次的优化集合。它不仅仅是单个算法的优化，而是从内存布局、指令级并行、算法自适应选择、底层硬件特性利用到多核并行等多个维度进行了深度设计和优化，使其成为一个非常高效的数据结构，为 Velox 引擎的整体高性能奠定了坚实的基础。