feat(vsjoin): Mechanism IV — Hardware-Conscious Execution (Cache/SIMD/NUMA)

[ZeroJustMe]

Mechanism IV: Hardware-Conscious Execution for VSJoin

1. Motivation

VSJoin 在 P=4~16 已经通过 lock-free 分区架构实现了相比 BruteForce 2x 的 join time 提升。但 benchmark 显示：

• P=32 时 VSJoin 反而比 BruteForce 慢 2x（51s vs 23s）
• 所有方法在 P>1 时 join_time 显著增长（BF P=1: 5.4s → P=32: 23.1s，4.3x 退化）
• Fanout 实验证明 recall loss 不来自路由覆盖，而来自 IVF Global Index 近似性

根因分析：性能瓶颈不在锁竞争（已解决），而在 cache miss 和 内存带宽：

操作	访问模式	Cache 行为
Local Index BruteForce scan	顺序扫描窗口记录	窗口超过 L2 → DRAM miss
Global Index IVF query	随机跳转 posting list	几乎 100% cache miss
距离计算 (dim=128)	AoS 结构中跳跃读取 float	Cache line 利用率 ~50%

在现代多核处理器上：

• L1 hit: ~1ns, L2 hit: ~3ns, L3 hit: ~10ns, DRAM: ~50ns（50x slower than L1）
• 窗口 1000 条 × 512 bytes/record = 512KB，刚好在 L2（256KB~1MB）边缘
• 并行度越高，每个 core 的 L2 竞争越激烈（shared L3 thrashing）

2. Literature Survey

2.1 Cache-Conscious Partitioned Join

论文	会议	核心思想	与 VSJoin 的关联
Balkesen et al. "Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited"	PVLDB 2013 (Vol.7)	Radix Join: 多趟分区使每个 partition 精确放进 L2 cache；probe 时近零 cache miss	VSJoin 的 Local Index scan 可类比 probe 阶段
Kim et al. "Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs"	PVLDB 2009 (Vol.2)	证明 cache-conscious radix partitioning 比 no-partition 快 2~4x	直接适用于窗口大小 > L2 的场景
Hammoud et al. "PolyHJ: A Polymorphic Main-Memory Hash Join Paradigm"	SIGMOD 2024	In-place Cache-Aware Partitioning (ICP): 原地分区避免额外内存拷贝；Collaborative Building & Probing (ColBP): 多核协作构建+探测，减少跨 socket 流量	ICP 可移植到 WindowState 的存储布局
SIGMOD 2025 Programming Competition (4th place)	SIGMOD 2025	Lock-free cache-aware hash pipeline，630x speedup over baseline	验证了 cache-aware + lock-free 的组合潜力

2.2 NUMA-Aware Stream Processing

论文	会议	核心思想	与 VSJoin 的关联
Teubner & Mueller, "How Soccer Players Would do Stream Joins" (Handshake Join)	VLDB 2011	Cell-based 分解：每个 core 持有一个 cell，数据在 core 之间"握手"传递，天然 NUMA-local	VSJoin 的分区已类似 cell，可直接映射 NUMA node
Roy et al. "Low-Latency Handshake Join"	PVLDB 2014 (Vol.7)	优化 Handshake Join 延迟：pipelining + 异步传播	管线化思想可用于 insert/query 重叠
Zhang et al. "BriskStream: Scaling Data Stream Processing on Shared-Memory Multicore Architectures"	SIGMOD 2019	RLAS 调度: 根据 NUMA 距离优化算子放置，减少跨 socket 数据传输。30% throughput gain on 4-socket	直接指导 subtask → NUMA node 映射
Psaroudakis et al. "Adaptive NUMA-aware Data Placement and Task Scheduling"	PVLDB 2016 (Vol.10)	列存中自适应 NUMA 数据放置：根据工作负载动态迁移数据到本地 socket	Global Index replica 策略

2.3 Vector Search Hardware Optimization

论文/系统	来源	核心思想	与 VSJoin 的关联
Faiss (Meta Research)	工业系统	SIMD 距离计算 (AVX2/AVX512)、PQ 量化降维、prefetch 流水线	已有 simd_distance.h 可进一步优化
KScaNN (Kunpeng ANN)	arXiv 2024	ARM NEON SIMD + 软件 prefetch + memory pool 优化 ANN 搜索	Prefetch 策略可移植
Xie et al. "Fast Approximate Similarity Join in Vector Databases"	SIGMOD 2025	基于 graph 的向量 similarity join，batch query 优化 cache locality	Batch query 思想用于 Global Index
Polychroniou et al. "Rethinking SIMD Vectorization for In-Memory Databases"	SIGMOD 2015	Hash 分区 + 距离计算的全面 SIMD 向量化；SoA 布局使 SIMD 利用率最大化	SoA 布局是关键 enabler

3. Design: Three Sub-Mechanisms

3.1 Sub-Mechanism IV-A: Tile-Based Cache-Conscious Local Scan

来源: Radix Join (Balkesen 2013) + SIMD vectorization (Polychroniou 2015)

问题: Local Index BruteForce scan 在窗口 > L2 cache 时产生大量 cache miss。

方案: 将 WindowState 的记录按 tile 组织，每个 tile 大小 = L2 cache size / 2（约 128KB，可容纳约 256 条 dim=128 的记录）。

WindowState partition[i]:
  ┌─────────────┬─────────────┬─────────────┐
  │  Tile 0     │  Tile 1     │  Tile 2     │
  │  (~256 vecs)│  (~256 vecs)│  (~256 vecs)│
  │  128KB      │  128KB      │  128KB      │
  └─────────────┴─────────────┴─────────────┘

关键改变: 从 AoS (Array of Structures) 改为 SoA (Structure of Arrays) 存储：

AoS (当前):
  record[0]: [uid, timestamp, dim0, dim1, ..., dim127]
  record[1]: [uid, timestamp, dim0, dim1, ..., dim127]
  → 每条记录 512+ bytes，SIMD 加载一条记录时浪费 cache line 空间

SoA (提议):
  tile.uids[0..N]         = [uid0, uid1, uid2, ...]
  tile.timestamps[0..N]   = [ts0, ts1, ts2, ...]
  tile.dims[0][0..N]      = [rec0.dim0, rec1.dim0, rec2.dim0, ...]
  tile.dims[1][0..N]      = [rec0.dim1, rec1.dim1, rec2.dim1, ...]
  ...
  tile.dims[127][0..N]    = [rec0.dim127, rec1.dim127, ...]
  → SIMD 可一次加载 8 条记录的同一维度 (AVX2 __m256)

距离计算优化（SoA 解锁的 SIMD 并行度）:

// 一次计算 query 与 8 条记录的 L2 距离
__m256 sum = _mm256_setzero_ps();
for (int d = 0; d < dim; ++d) {
    __m256 q = _mm256_broadcast_ss(&query[d]);
    __m256 c = _mm256_load_ps(&tile.dims[d][base]);  // 8 records
    __m256 diff = _mm256_sub_ps(q, c);
    sum = _mm256_fmadd_ps(diff, diff, sum);  // FMA
}
// sum 包含 8 个 L2 距离

tile scan 流程:

1. 加载 Tile 0 到 L2（顺序读取，硬件 prefetcher 友好）
2. 对 tile 内所有记录用 SIMD batch 计算距离（全部 L2 hit）
3. 释放 Tile 0，加载 Tile 1（prefetch 重叠计算）

3.2 Sub-Mechanism IV-B: Software Prefetch Pipeline

来源: Group prefetch (Chen et al. 2004, database hash join) + KScaNN (2024)

问题:

• Local scan: 下一个 tile 的首次访问是 cold miss
• Global IVF query: posting list 访问完全随机（scatter access pattern）

方案 A — Local Scan Prefetch:

for (size_t t = 0; t < num_tiles; ++t) {
    // Prefetch next tile's first cache lines while computing current tile
    if (t + 1 < num_tiles) {
        const size_t prefetch_stride = 64;  // cache line size
        for (size_t j = 0; j < tile_bytes; j += prefetch_stride * 4) {
            __builtin_prefetch(&tile_data[t+1][j], 0, 1);  // L2 prefetch hint
        }
    }
    simd_batch_distance(query, tile_data[t], tile_size, results);
}

方案 B — Global Index Group Prefetch (batch query amortization):

当多条 query record 到达同一个 subtask 时（multicast routing），将它们打包成 batch，交错执行 prefetch 和计算：

// Interleaved prefetch: while computing query[i]'s candidate,
// prefetch query[i+1]'s candidate (pipeline depth = 2~4)
constexpr size_t kPipelineDepth = 4;
for (size_t step = 0; step < max_steps; ++step) {
    for (size_t q = 0; q < batch_size; ++q) {
        // Prefetch next candidate for this query
        __builtin_prefetch(next_candidate_ptr[q], 0, 0);  // L1 prefetch
        // Process current candidate (data already in cache from previous iteration)
        compute_distance_and_check(query[q], current_candidate[q]);
        advance_to_next(q);
    }
}

3.3 Sub-Mechanism IV-C: NUMA-Aware Partition Affinity

来源: BriskStream (SIGMOD 2019) + Handshake Join (VLDB 2011) + Psaroudakis (PVLDB 2016)

问题: 在多 socket 系统上，subtask 访问非本地 NUMA node 的内存延迟 2~3x。

方案: 将 VSJoin 的分区拓扑映射到 NUMA 拓扑：

NUMA Node 0 (socket 0, cores 0-7):
  ┌─────────────────────────────────────┐
  │ subtask 0: Local L/R + WindowState  │  ← 本地内存分配
  │ subtask 1: Local L/R + WindowState  │  ← 本地内存分配
  │ Global Index Replica (read-only)    │  ← 本地副本
  └─────────────────────────────────────┘

NUMA Node 1 (socket 1, cores 8-15):
  ┌─────────────────────────────────────┐
  │ subtask 2: Local L/R + WindowState  │  ← 本地内存分配
  │ subtask 3: Local L/R + WindowState  │  ← 本地内存分配
  │ Global Index Replica (read-only)    │  ← 本地副本
  └─────────────────────────────────────┘

三层实现：

1. Memory Allocation: WindowState::addRecord() 使用 NUMA-local allocator（numa_alloc_onnode 或 mmap + mbind）
2. Thread Pinning: Execution graph 的 subtask 线程 pthread_setaffinity_np 到对应 NUMA node 的 core set
3. Global Index Replication: Rebuild 时每个 NUMA node 构建独立副本，query 只访问本地副本

4. Expected Performance Gains

优化	预期 Speedup	依据	影响范围
SoA tile scan (L2 cache fit)	1.5~2x on Local scan	Balkesen 2013: radix join 2~3x over no-partition	所有 P
SIMD 8-way batch distance (SoA)	2~4x on distance compute	当前 AoS 只能 1-way SIMD；SoA 解锁 8-way	所有 P
Software prefetch pipeline	1.3~1.5x on Global query	Chen 2004: prefetch hides 60~80% miss latency	P≥4
NUMA affinity + Global replica	1.2~1.5x on multi-socket	BriskStream 2019: RLAS 30% gain on 4-socket	P≥16, multi-socket

综合预期: 在 P=8~16 的 sweet spot，join_time 从 10~16s 降到 4~7s，与 BF baseline 的差距从 2x 扩大到 3~5x。P=32 的退化也会缓解（从 51s 降到 20~30s）。

5. Implementation Plan

Phase 1: SoA Tile Layout + SIMD Batch Distance (最高优先级)

改动文件:

• include/state/partitioned_window_state.h — 新增 TiledVectorStorage 类
• src/state/partitioned_window_state.cpp — tile 管理（添加、evict、snapshot）
• include/compute_engine/simd_distance.h — 新增 batch_l2_distance_soa() 8-way AVX2
• src/operator/join_operator_methods/vsjoin_method.cpp — Local scan 使用 tile iterator

数据结构:

struct TiledVectorStorage {
    static constexpr size_t kTileCapacity = 256;  // records per tile
    static constexpr size_t kTileBytes = kTileCapacity * sizeof(float) * dim;
    
    struct Tile {
        alignas(64) float dims[kMaxDim][kTileCapacity];  // SoA layout, cache-aligned
        alignas(64) uint64_t uids[kTileCapacity];
        alignas(64) int64_t timestamps[kTileCapacity];
        size_t count = 0;
    };
    
    std::vector<std::unique_ptr<Tile>> tiles_;
    // ...
};

验证: 对比 BruteForce baseline 的 join_time，SoA 应该在 P=1 就体现出距离计算加速。

Phase 2: Software Prefetch

改动文件:

• src/operator/join_operator_methods/vsjoin_method.cpp — tile 间 prefetch
• src/index/knn.cpp — IVF posting list group prefetch

验证: VTune hotspot 分析对比 prefetch 前后的 cache miss rate。

Phase 3: NUMA Affinity

改动文件:

• src/execution/execution_graph.cpp — 线程 NUMA pinning
• src/operator/utils/join_strategy_factory.cpp — numa_alloc_onnode for Local Index
• src/operator/join_operator.cpp — Global Index per-NUMA-node replica

依赖: libnuma（apt install libnuma-dev），CMake 加 find_package(NUMA)

验证: 在多 socket 机器上对比跨 socket vs 本地访问的 throughput。

Phase 4: Paper Integration

在论文中作为 Section 5: Hardware-Conscious Execution 或 Mechanism IV，包含：

• 问题分析（cache miss profiling 数据）
• 三个子机制的设计
• Microbenchmark：tile size sweep、prefetch depth、NUMA locality
• End-to-end：对比 Mechanism IV on/off 的 throughput 和 p95 latency

6. Risks and Mitigations

风险	影响	缓解
SoA 布局增加 insert 开销（需要 scatter 到多个数组）	insert 慢 10~20%	Tile 内维护 append-only 指针，batch insert amortize
Prefetch 在小窗口下无效（数据已在 cache）	无收益	只在 window_size > L2 时启用
NUMA API 不可移植（macOS 无 libnuma）	CI/CD 兼容性	编译期 #ifdef + fallback to default allocator
SoA 与现有 VectorRecord 接口不兼容	改动面大	TiledVectorStorage 作为 opt-in 替代，不改 VectorRecord

[ZeroJustMe]

⚠️ 根因分析修正 — 基于实验数据

原 issue 声称"性能瓶颈不在锁竞争而在 cache miss"，这是错误的。实际 profiling 数据如下：

BF/IVF P=32 瓶颈：锁竞争（93.6%）

Phase	All-thread Total	Per-thread	%
lock_wait	290.2s	9.07s	93.6%
candidate_fetch	13.2s	0.41s	4.3%
emit	5.1s	0.16s	1.6%
similarity	1.7s	0.05s	0.5%

BF/IVF 用 shared RW lock (IQ 策略)。P=32 时每线程等锁 9s，实际计算只要 0.46s。锁竞争是它们的唯一瓶颈。

VSJoin P=32 瓶颈：Work Amplification（96%）

Phase	All-thread Total	Per-thread	%
candidate_fetch	765.0s	23.9s	61.9%
index_insert	421.1s	13.2s	34.1%
emit	35.9s	1.1s	2.9%
similarity	12.7s	0.4s	1.0%
lock_wait	0s	0s	0%

VSJoin lock=0（lock-free 生效），但 fanout=12 导致每条记录执行 13 次 insert + 13 次 query = 26 次索引操作，比 BF 的 2 次（1 insert + 1 query）多 13x。

VSJoin P=8 表现良好

Phase	Per-thread	%
candidate_fetch	3.14s	44.7%
emit	3.55s	50.5%
lock_wait	0s	0%

P=8 fanout=5，work amplification 可控，lock-free 优势明显。

结论

1. VSJoin P=32 慢于 BF 不是因为 cache miss，而是因为 multicast fanout 的 work amplification
2. Cache-friendly 优化（SoA/tile/prefetch）对 candidate_fetch 的加速效果取决于 index query 是否 cache-bound — 需要更精细的实验（需要 perf stat 硬件计数器，当前环境不可用）
3. 最有效的优化方向是降低 work amplification：减小 fanout、或在高 P 时切换到更高效的 cross-partition query 策略
4. Mechanism IV 的 NUMA affinity 和 SoA 优化仍然有价值，但它们的优先级低于解决 work amplification 问题

数据来源: scripts/perf_breakdown.py，覆盖 BF/IVF/VSJoin × P=1,8,32 × data_size=1K,2K,5K

[ZeroJustMe]

实验补充：Cache Micro-Benchmark（无需 PMU）

perf stat 因容器无 CAP_PERFMON 不可用。改用程序内时间差 micro-benchmark（test/benchmark/cache_microbench.cpp）。

实验 1：SoA vs AoS 布局（相同计算量，不同内存布局）

N_recs	Data Size	AoS-Seq	SoA-Seq	SoA Speedup
256	128KB	36.3µs	26.9µs	1.35x
1,024	512KB	142.2µs	104.9µs	1.36x
4,096	2MB	569.5µs	413.6µs	1.38x
16,384	8MB	2,272µs	1,176µs	1.93x
65,536	32MB	6,457µs	4,697µs	1.37x

→ SoA 全面优于 AoS，在 L3 压力区（8MB）达到 1.93x

实验 2：Random vs Sequential（cache miss penalty）

N_recs	Data Size	Sequential	Random	Penalty
256	128KB	36.3µs	36.6µs	1.01x（无）
4,096	2MB	569.5µs	717.0µs	1.26x
16,384	8MB	2,272µs	3,059µs	1.35x
65,536	32MB	6,457µs	8,453µs	1.31x

→ 2MB 以上数据 random access 有 26-35% penalty，证明 cache miss 在大窗口下确实有影响

实验 3：多线程 scaling

P=32 parallel efficiency 70-80%，中等 cache 竞争。

结论修正

1. Cache miss 在当前小窗口（1K 条=512KB）下影响不大（random penalty 仅 4%）
2. 窗口 >4K 条（2MB+）时 cache miss 变得显著（26-35% penalty）
3. SoA 布局在所有规模下都有稳定收益（1.35-1.93x），且不需要改算法逻辑
4. 之前的结论"VSJoin P=32 慢的主因是 work amplification"仍然成立（96% 时间在 candidate_fetch + index_insert）
5. SoA 优化可以把 candidate_fetch 加速 1.35x，在 work amplification 之上叠加收益