ThinkLab

多关系查询计划

多关系（多表）查询的优化难点在于：随着连接数量增加，可选执行计划呈指数级爆炸（大约有 (4^n) 种 n 表连接次序）。因此优化器必须限制搜索空间。

自底向上（生成式）优化

代表系统：System R、DB2、MySQL、Postgres 等

核心思路：从“什么都没有”开始，一步步“构造”更大的计划，并用动态规划选择局部最优，从而得到全局近似最优。

（一）典型过程（以 System R 为例）

将 SQL 查询分解为查询块（如子查询、子句）
对每个查询块生成逻辑算子（选择、投影、连接、聚合等）
对每个逻辑算子生成若干物理算子实现（如嵌套循环连接、排序-合并连接、哈希连接）
使用动态规划按子集大小迭代构造“左深（left-deep）”连接树，评估每个部分计划的代价，保留代价最小的方案

（二）特点

易于实现，工程上成熟
搜索空间通常限制为左深树，大幅减少组合数
可与启发式规则结合（如先做选择、投影）加速搜索

（三）简化示例

三张表：A, B, C，条件：A ⋈ B ⋈ C

所有连接次序有：
- (A ⋈ B ⋈ C)
- (A ⋈ C ⋈ B)
- (B ⋈ A ⋈ C)
- ……（很多等价形式）
自底向上动态规划做法：
- 先找所有单表访问的最优方式（索引扫描 / 全表扫描）
- 然后对所有表对 {A,B}、{A,C}、{B,C} 找最优连接方式
- 最后在这些“最优二表结果”基础上，再加入第三张表，得到最终最优计划

自顶向下（变换式）优化

代表系统：MSSQL、Greenplum、CockroachDB、Volcano 等

从一个完整的初始逻辑查询计划出发，通过一系列规则重写和实现选择，寻找等价但更优的计划。

（一）关键机制

变换规则（逻辑→逻辑） 例如：
- 连接交换：( R ⋈ S \Rightarrow S ⋈ R )
- 连接结合：( R ⋈ S ⋈ T \Rightarrow R ⋈ S ⋈ T )
- 谓词下推、投影下推等
实现规则（逻辑→物理） 将“连接”逻辑算子替换为具体的哈希连接、排序-合并连接等物理算子
备忘录（Memo）结构 记录“同一逻辑表达式的不同等价形式和实现”，防止重复搜索
Enforcer（属性强制器） 特殊物理算子，用于保证某些输出属性（如排序、有无去重、分区方式），例如：
- 为满足 ORDER BY 引入 sort 算子
- 为分布式连接引入 repartition 算子

（二）特点

搜索空间更灵活，可处理复杂查询变换
依赖规则系统设计与启发式剪枝
Memo + 自顶向下递归，可避免无效重复计算

数据统计信息

优化器需要数据统计帮助估算选择率与中间结果大小，从而估计成本。

直方图（Histogram）

真实数据常常偏斜（skewed），又不能把每个值都存下来。直方图是常见的压缩统计方式。

（一）等宽直方图（Equi-Width）

将取值域按固定宽度划分成多个区间（bucket），每个 bucket 记录该区间内值的频数
优点：结构简单，构建代价低
缺点：若数据分布非常不均匀，有些桶非常空，有些则非常满（对选择率估计不友好）

示例

假设年龄字段 age ∈ [0, 100]，切成 10 个桶，每个区间宽度为 10：

桶1：[0, 10)，计数 100
桶2：[10, 20)，计数 1000
…… 如果绝大多数人年龄集中在 20–30 岁，等宽直方图会浪费很多桶在无人区间。

（二）等深直方图（Equi-Depth）

每个桶包含大致相同数量的元组，因此桶宽度不固定
对偏斜数据更友好：高密度区间被划分为多个窄桶，低密度区间为宽桶

示例

仍然是年龄数据：

桶1：包含约 10% 的记录，对应年龄 [0, 15]
桶2：下一个 10% 的记录，对应年龄 [15, 21]
桶3：再下一个 10%，对应 [21, 24]
……

可以看到年龄集中区间会被切得更细，有利于精确选择率估计。

（三）端偏直方图（End-Biased）

使用前 (N-1) 个桶精确存储最频繁的若干值，最后一个桶存储“其他所有值”的平均频率
适合存在少数“重元素（heavy hitters）”场景，例如：
- status 字段中 90% 是 “ACTIVE”，10% 分散在其它值
- country 字段中 “US”/“CN”/“IN” 特别多，其它国家很少

示例（N=4）

桶1：value = 'US'，计数 5,000,000
桶2：value = 'CN'，计数 3,000,000
桶3：value = 'IN'，计数 1,000,000
桶4：其余所有国家的总计 1,000,000，并只存储平均值（如每个约 100）

当谓词是 country = 'US' 时，估计极精确；当谓词是 country = 'JP' 时，就用桶4的平均值估计。

（四）Sketch / 草图结构

一些系统用近似结构代替直方图，例如：

Count-Min Sketch：估计频数
HyperLogLog：估计去重计数（cardinality）

特点是：空间极小 + 估计近似，适合大规模或流式数据。

抽样（Sampling）

通过对表的子集计算统计信息来近似整个表的选择率。

（一）两种方式

维护只读样本表：定期或按阈值重建样本
直接对真实表在线抽样：如 TABLESAMPLE

（二）更新策略

当原表修改量超过某阈值（如 10%）时，重建或更新样本。

（三）示例

假设原表有 10 亿行，用 1% 的随机样本（1000 万行）估计选择率：

查询：WHERE age BETWEEN 20 AND 25
在样本中有 1,000,000 行符合
估计总体满足行数 ≈ 1,000,000 × 100 = 100,000,000 行
选择率 ≈ 10%

成本估计（Cost Estimation）

优化器通过成本模型评估不同执行计划，选择代价最小者。

成本指标

常见成本维度：

CPU：
- 每条记录或每个算子需要的 CPU 操作
- 单次成本小，但计数准确较难（依赖实现细节与硬件）
磁盘 I/O：
- 访问的磁盘块数（block transfers）
- 通常被视为主要成本来源（特别是传统磁盘）
内存：
- 算子所需的 DRAM 空间
- 会影响是否需要溢写磁盘（如哈希连接溢出）
网络：
- 分布式系统中消息数、传输字节数

由于计划枚举空间巨大，穷举所有执行计划不现实，必须限制搜索空间。

统计信息表

大部分系统会在内部 catalog 中维护统计表，而不是每次都在线扫描全表。

对每个关系 (R)，典型统计包括：

(N_R)：表 R 的元组数
(V(A, R))：属性 (A) 在表 R 中的不同取值数量（distinct）

基于这些信息，可以推导选择基数（Selection Cardinality）：

[ SC(A, R) = \frac{N_R}{V(A, R)} ]

表示：在均匀分布假设下，每个不同值大约对应 (SC(A,R)) 行。

示例

表 R 有 (N_R = 1{,}000{,}000) 行
字段 city 有 (V(city,R) = 100) 个不同城市
则 [ SC(city, R) = \frac{1{,}000{,}000}{100} = 10{,}000 ]
估计 WHERE city = 'Beijing' 时，将返回约 10,000 行（假设均匀）

选择谓词与选择率估计

选择率（Selectivity）

选择率 (\text{sel}(P)) 定义为：满足谓词 (P) 的元组占总元组的比例，即一个概率。

输出行数 ≈ 输入行数 × 选择率

（一）简单谓词（等值唯一键）

对于唯一键上的等值谓词（如主键）估计很简单：

如果主键保证唯一：
- WHERE id = 123 的选择率 ≈ (1 / N_R)
- 返回行数 ≈ 1

这种场景下，索引选择非常明确（如 B+ 树索引）。

（二）复杂谓词（范围、合取）

如图中所示，复杂谓词（范围、多个条件 AND/OR 组合）估计要复杂得多，需要组合多个选择基数。

示例一：范围谓词

表 R 有 1,000,000 行，age ∈ [0, 100]，假设均匀
查询：WHERE age BETWEEN 20 AND 30
选择率 ≈ 区间长度 / 总范围 = 10 / 100 = 0.1
结果行数 ≈ 100,000 行

示例二：合取谓词（AND）

条件：age BETWEEN 20 AND 30 AND city = 'Beijing'
若假设两个谓词独立（重要假设），且
- sel(age) = 0.1
- sel(city='Beijing') = 0.05
则整体选择率估计为： [ sel(\text{age}) \times sel(\text{city}) = 0.1 \times 0.05 = 0.005 ]
结果行数 ≈ 1,000,000 × 0.005 = 5,000 行

（三）否定谓词（NOT）

利用“概率视角”可以很简单地处理否定谓词：

[ sel(\text{NOT } P) = 1 - sel(P) ]

文中示例给出了一个否定查询，其选择率为 ( \frac{4}{5} )，正好是 1 减去正向查询选择率。

具体示例

WHERE status = 'ACTIVE' 的选择率估计为 0.2
则 WHERE status <> 'ACTIVE' 的选择率估计为： [ 1 - 0.2 = 0.8 ]

选择率估计中的关键假设

优化器通常会依赖三大假设来简化选择率与基数估计：

（一）均匀分布（Uniform Data）

除了少数“重元素”，所有取值在域中均匀分布
问题：现实数据往往高度偏斜（如热门城市、热门商品）

（二）谓词独立（Independent Predicates）

不同属性上的谓词相互独立
问题：真实世界中属性往往高度相关，如：
- city 与 country 显然相关
- salary 与 title 相关
如果忽略相关性，多条件 AND 的结果可能被估得过低或过高

（三）包含原则（Containment Principle）

假设连接键域有良好重叠：
- 每个 inner 表中的 key 都能在 outer 表中找到匹配
实际中若存在大量“孤立键”（只出现一边），估计也会偏差

这些假设往往不满足，导致基数估计误差，进一步影响成本估计和计划选择。

连接基数估计（Join Size Estimation）

考虑两个关系 (R) 与 (S)，在共享属性 (A) 上进行等值连接：

[ R ⋈_{R.A = S.A} S ]

在之前三大假设（均匀、独立、包含）下，常用估计公式为：

[ |R ⋈ S| \approx \frac{N_R \times N_S}{\max(V(A,R), V(A,S))} ]

其中：

(N_R, N_S)：R 和 S 的行数
(V(A,R), V(A,S))：属性 A 在各表中不同值个数

解释

若 A 值在两表中大致均匀分布，且每个 A 值都在两边出现
那么每个 A 值在 R 中大约有 (N_R / V(A,R)) 行，在 S 中约有 (N_S / V(A,S)) 行
对所有可能的 A 值累加，得到上述近似