深度解读：QuestDB 如何使 WINDOW JOIN 并行化与向量化

背景

在量化交易等高频数据处理场景中，一种常见的工作负载是：针对每一笔已执行的交易，计算其前后 1 秒窗口内的平均买卖报价（bid/ask）。

在没有专用操作符的传统 SQL 引擎中，实现这一逻辑极其繁琐且低效。它通常需要两个独立的连接操作：首先是一个 ASOF JOIN（非等值连接），用于获取窗口起始时刻的延续报价；其次是一个范围连接（Range Join），用于获取窗口内的所有行。这两个结果通过 UNION ALL 拼接，最后通过 GROUP BY 进行聚合折叠。

这种写法不仅 SQL 代码冗长，更存在严重的性能瓶颈：

1. 重复扫描：ASOF JOIN 和范围连接独立遍历价格表，尽管它们解决的是同一个问题的两个侧面。
2. 哈希开销：范围连接迫使查询规划器先对 sym（股票代码）进行哈希，然后对每一对匹配结果重新过滤 BETWEEN 谓词。
3. 聚合压力：外层的 GROUP BY 是一个哈希聚合操作，需要在内存中为每个 (ts, symbol) 对物化一行数据。在测试数据中，这导致了 5000 万个分组。

在这种架构下，优化器无法有效地融合、并行化或向量化这些操作。

核心内容

QuestDB 引入了专用的 WINDOW JOIN 语法来解决上述问题。该操作符允许用户直接指定一个时间窗口，对另一张表中的行进行聚合。

专用语法与逻辑

SELECT t.*, avg(p.bid) avg_bid, avg(p.ask) avg_ask
FROM trades t
WINDOW JOIN prices p
ON p.sym = t.symbol
RANGE BETWEEN 1 second PRECEDING AND 1 second FOLLOWING;

这一操作符明确知晓其职责：对于连接左侧（LHS，如交易表）的每一行，在右侧（RHS，如价格表）找到时间戳落在 [lo, hi] 窗口内的行，限制匹配特定的键（如股票代码），并执行批量聚合函数。

性能优化的两大支柱

为了实现高性能，QuestDB 采用了两个核心优化手段：数据级并行化 和 低基数快速路径（SIMD 向量化）。

在包含 5000 万行交易表和 1.5 亿行价格表的基准测试中，这种并行 + SIMD 的路径比 QuestDB 自身的单线程回退方案快 5.0 倍，比 ClickHouse 的最佳重写方案快 25 倍。

1. 数据级并行化（Data-level Parallelism）

QuestDB 采用追加列式存储，数据按时间分区。查询引擎将数据读取为“页帧”（page frames）——即直接映射到文件页的连续列式内存块。过滤和聚合都以此粒度为单位。

• 分片策略：WINDOW JOIN 将 LHS 表切片为页帧。每个工作线程（Worker）获取一个帧，负责产生该帧内所有 LHS 行的聚合结果。
• 高效定位：为了高效工作，线程需要找到 RHS 表中落在所有窗口并集范围内的行。由于 QuestDB 的存储布局保证行在磁盘上按时间戳顺序排列，定位 RHS 切片只需每个工作线程执行一次二分查找，而非对每个 LHS 行进行扫描。
• 内存索引构建：对于 LHS 帧中存在的连接键，工作线程在内存中构建一个小型索引：包含每个键的 RHS 时间戳列表，以及待聚合值的数组。
• 内部循环：一旦索引构建完成，处理 LHS 行的内部循环仅需对每行执行两次二分查找（确定窗口的低边界和高边界），随后对连续的数组范围进行聚合。由于二分查找是单调向前进行的，它们可以在同一帧的行之间分摊成本。
• 无锁减少：减少步骤（Reduce step）是每帧独立的且无锁的，工作线程之间不共享可变状态。

2. 低基数键的快速路径（The Low-Cardinality-Key Fast Path）

为了利用 SIMD（单指令多数据流）加速聚合，QuestDB 将 RHS 的值复制到每键（per-key）的连续缓冲区中，以便现有的 SAMPLE BY SIMD 内核可以直接运行。

• 问题：窗口内的 RHS 行在内存中是分散的（跨越页帧、混合列），无法直接用于 SIMD 计算。
• 解决方案：对于低基数等值连接（如 p.sym = t.symbol）和可向量化的聚合（sum, avg, min, max, count），工作线程遍历 RHS 切片一次，同时构建每键时间戳索引并将聚合列的值复制到每键值缓冲区。
• 缓冲区布局：这些缓冲区是类型化且打包的。例如，所有 AAPL 的 bid 值都位于一个连续的 double 数组块中，并按 RHS 时间戳排序。
• 向量化执行：当内部循环到达 LHS 行时，每键值缓冲区已经按照 SIMD 所需的布局排列。两次二分查找给出缓冲区中的 [rowLo, rowHi) 范围，直接将该切片传递给向量化聚合函数。

for (int i = 0; i < groupByFuncCount; i++) {
    groupByFunctions.getQuick(i).computeBatch(
        value, // 运行聚合状态
        bufferStart(i) + typeSize * rowLo, // 指向每键缓冲区的指针
        (int) (rowHi - rowLo), // 切片长度
        0
    );
}

• 回退机制：对于不符合条件（如非向量化聚合或非低基数连接）的查询，系统完全跳过缓冲区复制，回退到标量 computeBatch 循环。

性能权衡分析

虽然额外遍历 RHS 切片以构建缓冲区需要读取每列两次，但这在以下条件下是划算的：

1. SIMD 加速：如果输入是连续的，QuestDB 的聚合循环受限于 SIMD 吞吐量；否则受限于每行的函数调用开销。对于 double 类型，AVX2 指令集带来了约一个数量级的提升。
2. 内存预取友好：RHS 列的顺序读取配合预取机制，是内存子系统最擅长的场景。
3. 缓存友好：每键值缓冲区的大小与当前 LHS 帧的 RHS 切片相匹配，确保工作集保留在 L2/L3 缓存中。

关键要点

• 专用操作符优势：WINDOW JOIN 作为专用语法，让优化器能够理解操作意图，从而避免传统 SQL 中多步连接、去重和聚合带来的巨大开销。
• 存储布局红利：QuestDB 的列式追加存储和按时间排序的物理布局，使得在并行化过程中，通过单次二分查找即可高效定位 RHS 数据切片，消除了随机 I/O 和全表扫描。
• 并行化粒度：以“页帧”为并行单元，工作线程独立处理帧内的数据，通过构建内存索引实现帧内行的快速窗口定位，且无需跨线程锁竞争。
• SIMD 向量化关键：通过“额外一次遍历”将分散的 RHS 数据重组为每键的连续内存缓冲区，成功激活了手写的 SIMD 内核（如 AVX2），实现了数量级的性能提升。
• 条件触发机制：向量化快速路径仅在满足特定条件时启用（向量化的聚合函数 + 低基数等值连接），否则优雅回退到标量处理，保证了通用性。
• 基准测试表现：在 50M x 150M 数据规模下，该实现比单线程回退快 5 倍，比竞争对手 ClickHouse 的最佳重写方案快 25 倍。

意义与影响

QuestDB 对 WINDOW JOIN 的并行化和向量化改造，展示了现代时序数据库在应对高频交易等复杂分析负载时的工程