跳到主要内容

并行和分布式查询处理

22.1 概述​

在数据分区之后,一个自然的问题是:如何在多台节点上并行地执行 SQL 查询? 目标是把查询的执行时间从 TT 缩短到接近 T/NT/N(NN 为节点数)——即达到线性加速比(speedup)与线性可扩放性(scaleup)。

并行执行的三个基本粒度:

粒度含义例子
操作间并行(inter-operator)同一查询内不同算子并行同时执行左右两个 Scan 供 Join 使用
操作内并行(intra-operator)单个算子被切成 NN 份并行执行分区排序、分区连接
流水线并行(pipeline)算子间用流水线方式传数据Scan → Filter → Project 一路推
并行粒度加速上限依赖数据分区内存放大
操作间受最长子树限制不必视 buffer 而定
操作内接近线性强依赖NN 倍
流水线受流水线长度限制不必少

真实的并行执行器(例如 Greenplum、Spark、Presto)通常是三种粒度的混合。本章按"排序→连接→其他运算→执行框架→查询优化→流处理→跨源分布式查询"的顺序展开。


22.2 并行排序​

排序既是 SQL ORDER BY 的直接实现,也是很多算子(合并连接、分组聚集)的前置步骤,因此其并行化是所有并行数据库的基础技能。设关系 rr 大小为 ∣r∣|r|,分布在 NN 台节点上,各节点已有 ∣r∣/N|r|/N 行数据。

22.2.1 范围分区排序​

范围分区排序(range-partitioning sort) 分两步:

  1. 重分区:选一组划分向量 v1<v2<⋯<vN−1v_1 < v_2 < \cdots < v_{N-1},每个节点扫描本地数据,把每行按排序键送到对应的目的节点。结束后,第 ii 号节点上的所有行都严格小于第 i+1i+1 号节点。
  2. 局部排序:每个节点对本地收到的数据做单机排序。

结束后按节点编号顺序读出即为全局有序。关键难点在划分向量的选择:向量偏差会导致某节点数据量远大于其他节点。常用方法是先在样本上取分位数,样本大小取 O(Nlog⁡N)O(N \log N) 即足够。

22.2.2 并行的外排序-归并​

并行外排序-归并(parallel external sort–merge) 复用了单机外排序的思路:

  1. 每个节点先在本地做外部排序,产生一批已排序 run。
  2. 由一个节点(或多层归并树)以流水线方式对所有节点的 run 做多路归并。

它与范围分区排序的取舍是:

  • 范围分区排序把网络代价集中在"分区阶段",随后各节点独立干活;
  • 外排序-归并把网络代价放在"归并阶段",每一行都要穿过归并树。

对结果需要全局有序输出的情形(如 ORDER BY ... LIMIT k),范围分区排序几乎总是更优。对结果只需局部有序(如支撑合并连接)则两者接近。


22.3 并行连接​

连接是查询处理中最昂贵的运算。并行连接的思路都是**"让能连上的行落到同一台节点上,然后本地做连接"**。

22.3.1 分区连接​

分区连接(partitioned join) 对两张表都按连接键做散列或范围分区:

r⋈r.A=s.Bsr \bowtie_{r.A = s.B} s

按 h(A)h(A) 与 h(B)h(B)(同一散列函数)分区后,rr 的第 ii 分区只可能与 ss 的第 ii 分区连上。每个节点接下来独立做散列连接或合并连接即可。

若 rr 已按 AA 分区、ss 也已按 BB 分区且散列函数相同,则可跳过分区步骤,得到并置连接(co-located join)——这是无共享数据库中最理想的场景,也是分区键选择的核心目标之一。

22.3.2 分片-复制连接​

当一张表远小于另一张时,重分区大表的代价不划算。分片-复制连接(fragment-and-replicate join) 把大表保持分片在各节点,把小表广播复制到所有节点,每个节点用完整的小表去连接自己那份大表分片。

代价对比(NN 台节点,忽略常数):

方案网络数据量
双侧分区连接∥r∥+∥s∥\|r\| + \|s\|
分片-复制(复制 ss)N⋅∥s∥N \cdot \|s\|

当 ∣s∣|s| 很小时(例如维表),N⋅∣s∣≪∣r∣N \cdot |s| \ll |r|,广播代价小;反之应选双侧分区。

对非等值连接(如 r.A<s.Br.A < s.B),散列分区不适用,只能使用分片-复制或非对称分片(把 rr 按范围分片,把 ss 按覆盖每个分片的范围复制)。

22.3.3 处理并行连接中的偏斜​

若连接键中存在大热键(例如某商品被交易了上千万次),单纯散列会把所有配对压到一台节点。处理办法:

  • 热键复制:识别出 top-K 热键,把这些键上的 ss 数据广播到所有节点,热键上的 rr 数据保持分片。热键做分片-复制,其余键做正常散列。
  • 加盐(salting):把热键的每一行随机附加 kk 个盐值,成为 kk 个"虚拟键";同时把 ss 对应键的行复制 kk 份,每份带一个盐值。热键的连接就被 kk 拆分。
  • 动态感知:执行期检测哪个分区变慢,把它进一步细分并调度到空闲节点。

22.4 其他运算​

22.4.1 其他关系运算​

  • 选择 σ\sigma:单表本地过滤,天然并行,无需任何数据搬运。
  • 投影 π\pi:同选择;若含 DISTINCT 则退化为分组聚集。
  • 并 ∪\cup / 差 −- / 交 ∩\cap:可按元组散列到相同节点后本地合并。
  • 分组聚集 γG,F(A)(r)\gamma_{G, F(A)}(r):
    1. 两阶段聚集:先在每个节点做局部聚集,得到 (G,部分聚集值)(G, \text{部分聚集值});再按 h(G)h(G) 重分区,做最终聚集。
    2. 对可结合可交换的聚集函数(SUM、COUNT、MIN、MAX)效果最好;AVG 需拆成 SUM/COUNT 组合。
    3. DISTINCT 或 MEDIAN 无法两阶段化,只能全量重分区。

22.4.2 map 和 reduce 操作​

MapReduce 把并行数据处理抽象为两个用户函数:

  • map:(k1,v1)→list⟨(k2,v2)⟩\text{map}: (k_1, v_1) \to \text{list}\langle (k_2, v_2) \rangle
  • reduce:(k2,list⟨v2⟩)→list⟨v3⟩\text{reduce}: (k_2, \text{list}\langle v_2 \rangle) \to \text{list}\langle v_3 \rangle

框架自动完成:并行执行 map → 按 k2k_2 shuffle → 排序 → reduce。

MapReduce 与并行关系代数一一对应:

MapReduce关系代数
Map 中过滤/投影σ\sigma、π\pi
Map 输出同一 keyshuffle 分区
Reduce 聚集γ\gamma
Reduce 迭代两侧 list⋈\bowtie(连接)

Spark、Flink 等系统在此之上加了内存 RDD/DataStream 与流水线执行,避免了每个阶段都落地磁盘的开销,成为通用并行执行引擎。


22.5 查询计划的并行执行​

22.5.1 操作间并行​

操作间并行又分两种:

  • 独立并行:两个子树互不依赖,可完全并行。例如 (A ∪ B) ∩ (C ∪ D),左右两个并集可同时算。
  • 流水线并行:上游算子边产出边推给下游,形如 Scan → Filter → HashJoin(build) → Project,减少中间物化的代价。

阻塞算子(如排序、构建端散列表)会打断流水线;非阻塞算子(如过滤、投影、探测)不打断。

22.5.2 交换算子模型​

将并行执行融入经典火山模型(Volcano),Graefe 提出了交换算子(Exchange operator) 模型。所有分区/复制/合并的语义都封装在一个 Exchange 算子中,其余关系算子完全不感知并行。

Exchange 的实现三要素:分区函数(决定行去往哪个 worker)、通信通道(内存队列或 RPC)、缓冲/流控(避免上游压垮下游)。

22.5.3 情况汇总​

工业界的并行执行通常混合运用:

  • 一个查询计划被切成若干个stage,stage 之间以 Exchange 相连;
  • 每个 stage 内部再切成 NN 份task,每份 task 在一台节点上以火山模型执行;
  • task 内部尽量用流水线 + 向量化(vectorized execution) 提高单核吞吐。

22.5.4 查询计划中的容错​

短查询(OLTP)通常靠整体重试容错——单节点故障即让整个查询重跑。长查询(OLAP、报表、ETL)则需要中间结果物化:每个 stage 的输出落到分布式文件系统或对象存储,下一个 stage 出错时可从最近的物化点恢复。这是 Hadoop MapReduce 与 Spark(RDD lineage)容错的核心思想。


22.6 共享内存体系结构上的查询处理​

在共享内存(SMP、多核 CPU)上,交换算子退化为线程内共享队列,几乎没有网络代价。此时并行的主要挑战反而是:

  • NUMA(非一致性内存访问):跨 socket 的内存访问延迟明显高于本地内存,应尽量让处理某分区的线程与该分区的内存在同一 NUMA 节点。
  • 缓存亲和性:散列表分块设计,避免线程间乒乓 cacheline。
  • 锁与原子操作:无锁数据结构(如无锁散列表、Morsel-Driven 执行)在这里价值极高。

现代Morsel-Driven 执行(HyPer/DuckDB)把数据切成 morsel(几万行的小块),线程动态领取 morsel 执行,天然实现负载均衡。


22.7 并行执行的查询优化​

22.7.1 并行查询计划空间​

单机优化器在逻辑计划上枚举物理算子(Nested Loop / Merge / Hash Join;Index / Seq Scan);并行优化器还要额外决定:

  • 每个算子的并行度 NN;
  • 上下算子之间的Exchange 类型(Hash / Broadcast / Gather / Round-Robin);
  • 数据托管属性(partitioning、sortedness、replication)在计划中的传播与利用。

搜索空间显著变大,因此实践中多采用启发式剪枝:优先考虑并置连接、按代价选择广播 vs 分区。

22.7.2 并行查询计算的代价​

代价函数需要综合:

Cost=wcpu⋅Tcpu+wio⋅Tio+wnet⋅Tnet+Tstartup\text{Cost} = w_{\text{cpu}} \cdot T_{\text{cpu}} + w_{\text{io}} \cdot T_{\text{io}} + w_{\text{net}} \cdot T_{\text{net}} + T_{\text{startup}}

并行下的关键变化:

  • 响应时间(response time)=max⁡iTi= \max_i T_i,即最慢子任务决定用户感受;
  • 资源代价(total work)=∑iTi= \sum_i T_i,用于集群总吞吐评估;
  • 启动代价 TstartupT_{\text{startup}} 不可忽略——建立 RPC、分发计划、加载 UDF。

22.7.3 选择并行查询计划​

一个可行的两阶段方案:

  1. 用单机优化器选出最优逻辑连接顺序 + 物理算子;
  2. 再对每条边选择 Exchange 类型(分区 or 广播),并把并行度扫描一遍。

更彻底的方案(如 Cascades 框架)把并行属性作为物理属性加入枚举,让搜索一次到位;工程上代价较高,仅在 SQL Server、Greenplum 等系统全面采用。

22.7.4 数据托管​

数据托管指优化器把"该数据现在按什么分区、是否有序、是否复制"作为物理属性记录并利用:

  • 若两表已按连接键并置分区,则连接无需 Exchange;
  • 若某维表已在所有节点复制,则不需要广播;
  • 若数据已排序,则可省掉 sort。

在数据仓库设计中,分布键(distribution key) 与排序键(sort key) 的显式声明本质就是提示优化器"这份数据已经具备什么物理属性"。

22.7.5 物化视图的并行维护​

物化视图在并行环境下有两种维护方式:

  • 同步维护:视图与基表同事务更新,语义强但代价高;跨分片视图需要 2PC。
  • 异步维护:基表事务只写日志,视图后台合并;语义为最终一致。

对聚集类物化视图,"两阶段聚集"技巧同样适用:每个分片维护本地增量,中心节点归并。


22.8 流数据的并行处理​

流处理(Streaming)与批处理最大差别在于数据无界:查询本身是长期驻留的算子网络,输入源源不断到来。

22.8.1 元组的路由​

流入的元组由Source(如 Kafka Consumer)读入,按各算子的分区键路由到对应的算子实例——这与批处理中的 Exchange 完全同构。常见路由:

  • Hash by key:用于聚集、连接。
  • Broadcast:用于小维表增量分发。
  • Rebalance / Round-Robin:负载均衡型。
  • Keyed by user:保证同一用户的事件在同一算子实例被有序处理。

22.8.2 流运算的并行处理​

流上的关系运算需要**"窗口化"** 才能有界执行:

  • 翻滚窗口(tumbling):非重叠、等长的时间段。
  • 滑动窗口(sliding):重叠的时间段。
  • 会话窗口(session):按活跃度动态切分。

事件时间 vs 处理时间:事件时间是事件本身发生的时刻,处理时间是流处理系统看到它的时刻。真实业务几乎总应基于事件时间。

水位线(watermark) 是流系统对"事件时间已推进到 tt,晚于 tt 的迟到数据可能不再到来"的估计。当水位线越过窗口末端,即可安全触发窗口计算并释放状态。对迟到数据:

  • 丢弃:简单但会造成结果不完整;
  • 旁路输出:写到 side output,另作分析;
  • 允许延迟触发:设定 allowed lateness,窗口在关闭后一段时间内仍可被迟到事件更新,触发回撤(retraction) 或增量输出。

22.8.3 流数据的容错​

流处理系统的容错手段:

  • 检查点(checkpoint):周期性把所有算子的状态一致地快照到分布式存储(如 Flink 的 Chandy–Lamport 变体)。
  • Exactly-once 语义:结合可重放的 Source(Kafka)与幂等/事务型 Sink 达成。
  • At-least-once:仅保证不丢,可能重复,需下游幂等处理。
  • 状态后端:把大状态存到 RocksDB 或远端存储,避免内存溢出。

22.9 分布式查询处理​

分布式查询处理面向的是跨越多个自治数据源的查询——每个源可能是不同厂商的 DBMS,甚至可能是关系库 + NoSQL + 文件。

22.9.1 来自多个数据源的数据集成​

两种主要范式:

  • 数据仓库(ETL):把各源数据抽取、转换、加载到集中的仓库中查询。数据延迟高,但查询性能好。
  • 联邦查询(federation):查询实时下发到各源,源本地执行后把结果汇总。数据实时,但受各源性能与语义差异约束。

22.9.2 模式和数据集成​

跨源集成需要解决模式异构:

  • 命名冲突:不同源的字段名不同(emp_id vs employee_no)。
  • 结构冲突:同一概念在一处建模为字段、另一处建模为表。
  • 语义冲突:单位(美元 vs 人民币)、粒度(月 vs 日)、口径。

主流方案是全局-局部模式映射(GAV / LAV):定义统一的全局模式,用视图把它映射到各源。

22.9.3 跨多个数据源的查询处理​

跨源查询的关键是下推(pushdown):

  1. 全局优化器把查询拆成子查询,尽量把选择、投影、聚集下推到各源本地执行;
  2. 各源返回中间结果,由联邦执行器完成连接、去重、最终聚集;
  3. 由于各源统计信息不透明,代价估计极不可靠,实际执行常需自适应重优化。

半连接(semi-join) 技巧在分布式查询中尤为常用:先取 rr 中连接键的去重值发送到 ss 端,ss 端用它过滤后再发回,可显著减少网络传输。

22.9.4 分布式目录系统​

分布式查询依赖一个目录服务(catalog) 保存全局元数据:模式、分区、副本位置、统计信息。目录本身也需要高可用与低延迟,通常做法:

  • 元数据分片 + Paxos/Raft 复制(如 Spanner 的 directory、Presto 的 metastore)。
  • 客户端缓存 + 版本号/租约保证缓存一致性。
  • 与查询优化器紧耦合,避免每次查询都跨网访问。

22.10 总结​

  • 并行查询处理的目标是线性加速,需要综合运用操作间/操作内/流水线三种粒度。
  • 排序有范围分区排序与并行归并两种范式;连接有双侧分区、分片-复制、非对称分片三种范式;偏斜通过热键复制/加盐/动态感知处理。
  • Exchange 算子模型把并行封装到通信算子中,其余算子保持串行语义,是现代并行执行器的通用架构。
  • 并行查询优化扩展了搜索空间(并行度 + Exchange 类型),依赖数据托管属性做剪枝。
  • 流数据处理在概念上与批处理同构,关键差异在于窗口、事件时间、水位线与长期运行的状态容错。
  • 跨源分布式查询通过下推 + 半连接 + 全局目录来管理异构性;语义与代价估计是主要挑战。

下一章讨论并行事务处理——分布式提交、并发控制、复制一致性与共识协议。