8.2 CBO 与统计信息
8.1 的规则优化把计划摆正,但它回答不了「先 join 哪两张表」「用 hash 还是 sort-merge」。这些问题需要行数,而行数不是 SQL 里写着的,是统计信息估出来的。基于代价的优化(cost-based optimization,CBO)就是这套「先估行数、再算代价、最后选计划」的流程。
CBO 的成败几乎完全取决于估算准不准。估算准,代价模型只是在几个正确候选里挑一个;估算错,再精细的代价模型也只是把错误的输入算得更精确。
CBO 的三段流水
CBO 的结构可以拆成三段,每段都有独立的误差来源:
| 阶段 | 输入 | 输出 | 主要误差 |
|---|---|---|---|
| 基数估算 | 统计信息、谓词 | 每个算子的输出行数 | 选择率假设 |
| 代价计算 | 行数、算子参数 | 每个候选计划的代价 | 代价模型简化 |
| 计划选择 | 候选代价 | 最优计划 | 搜索空间裁剪 |
三段是串联的,前一段的误差会一路放大。选择率估错 100 倍,join 输出就估错 100 倍,代价比较的结论可能整个翻转。所以工程上大部分精力花在第一段,而不是把代价公式写得更花哨。
选择率:等值谓词约 1/NDV
选择率(selectivity)是「谓词过滤后剩下的行数比例」。对等值谓词,最常用的假设是「值在列上均匀分布」,于是命中某一个值的概率约等于 1 除以该列的不同值个数(NDV,number of distinct values)。
lab 用例 71 的口径是 NDV 为 1000 的等值谓词:
选择率 ≈ 1 / NDV
= 1 / 1000
= 0.001
| NDV | 选择率 | 100 万行过滤后(公式推导) |
|---|---|---|
| 100 | 0.01 | 10,000 行 |
| 1,000 | 0.001 | 1,000 行 |
| 10,000 | 0.0001 | 100 行 |
1/NDV 是一个极强的假设:它假定每个值出现次数一样多。真实数据往往长尾,热门值可能占 10%,冷门值可能只出现一次。一旦谓词命中的是热门值,实际行数可能是估算的几十倍,这就是后面 100 倍偏差的来源之一。
join 基数:左行 × 右行 / NDV
两表等值 join 的输出行数,常用「左行数 × 右行数 / 较大 NDV」估算。直觉是:左表每个 key 在右表平均出现「右行数 / NDV」次,乘上左表行数就是输出规模。
lab 用例 72 的口径是左 1 万行、右 10 万行、NDV 10 万:
join 输出 ≈ 左行数 × 右行数 / NDV
= 10,000 × 100,000 / 100,000
= 10,000 行
| 参数 | 取值 | 说明 |
|---|---|---|
| 左表行数 | 10,000 | 事实表侧 |
| 右表行数 | 100,000 | 维度表侧 |
| join key NDV | 100,000 | 右表唯一 |
| 输出行数 | 10,000 | 用例 72 |
输出等于左表行数,说明这是一次「多对一」关联:右表 key 唯一,左表每行最多匹配一行。这种形状下 join 不会放大数据,是数仓里最理想的外键关联。如果 NDV 估小了,输出就会被高估,优化器可能误以为这是一次会爆炸的 join。
hash join 的代价账本
hash join 分两段:先拿小表建哈希表(build),再拿大表逐行探测(probe)。代价近似为两侧行数之和,因为每行都要参与一次建表或一次探测。
lab 用例 73 的口径是 build 5 万行、probe 500 万行:
hash join 代价 = build 行数 + probe 行数
= 50,000 + 5,000,000
= 5,050,000
| 阶段 | 行数 | 代价贡献 |
|---|---|---|
| build | 50,000 | 50,000 |
| probe | 5,000,000 | 5,000,000 |
| 合计 | — | 5,050,000(用例 73) |
hash join 的成本随「大表行数」线性增长,与小表大小关系不大。这也是它偏爱「小表 build、大表 probe」的原因:build 侧要装进内存,probe 侧只扫一遍。若两侧都很大,build 侧溢出到磁盘,代价模型就要额外加一项。
sort-merge 的代价账本
sort-merge join 先按 join key 给两侧排序,再归并。排序的比较次数约为 n × log2(n),乘上每次比较的成本就是排序开销的主项。
lab 用例 73 用 100 万行、每次比较 5ns 估算:
比较次数 ≈ n × log2(n)
= 1,000,000 × log2(1,000,000)
≈ 1,000,000 × 19.93
≈ 19,930,000 次
排序代价 ≈ 19,930,000 × 5ns
≈ 99,657,842.8ns
≈ 9966 万 ns
| 口径 | 数值 | 说明 |
|---|---|---|
| 参与行数 | 1,000,000 | 排序侧 |
| 每行比较次数 | log2(1,000,000) ≈ 19.93 | 公式推导 |
| 每次比较 | 5ns | 模型参数 |
| 排序代价 | 约 99,657,842.8ns | 用例 73 |
| 摊到每行 | 约 99.7ns | 公式推导 |
同样的数据量,sort-merge 的排序开销比 hash 的行级操作高出一个量级。这不是说 sort-merge 一无是处:当两侧已经有序(比如落在排序列上),排序这一步可以省掉,sort-merge 反而更便宜;当需要稳定输出顺序时,它还能顺便满足排序需求。
两种算法的选择判据
把两份账放在一起,选择判据并不复杂:
| 条件 | 倾向 hash | 倾向 sort-merge |
|---|---|---|
| build 侧能装进内存 | 是 | — |
| 两侧已按 key 有序 | — | 是 |
| 只需要 join 结果 | 是 | — |
| 结果还需按 key 排序 | — | 是,省一次排序 |
| build 侧超大 | 需分区或换算法 | 可流式归并 |
默认选 hash,是因为大多数 join 的 build 侧足够小。优化器真正要做的是判断「build 侧到底多大」,这又回到基数估算:估小了,选了 hash 却在运行时溢出;估大了,白白放弃更便宜的 hash。
统计过期:100 倍偏差
统计信息不是实时更新的。表每天新增数据、发生大量更新,统计信息可能还是上周的。lab 用例 74 刻画了这种偏差:实际 NDV 10 万,统计里还写着 1000:
偏差倍数 = 实际 NDV / 估算 NDV
= 100,000 / 1,000
= 100 倍
| 口径 | NDV | 选择率(等值) |
|---|---|---|
| 估算(过期) | 1,000 | 0.001 |
| 实际 | 100,000 | 0.00001 |
| 偏差 | 100 倍 | 100 倍(用例 74) |
100 倍偏差会把选择率的量级彻底搞错。优化器以为过滤后还剩千分之一,实际只剩十万分之一;它可能因此把一个本该 broadcast 的小表当成大表,或者把一个爆炸性 join 当成安全 join。更麻烦的是,这种错误不会报错,只会让作业慢。
统计信息的来源与维护
不同引擎收集统计的方式不同,但大体逃不出三类:
| 来源 | 内容 | 时效性 |
|---|---|---|
| 表级统计 | 行数、总字节数 | 更新时刷新 |
| 列级统计 | NDV、min/max、空值数 | ANALYZE 时刷新 |
| 运行时统计 | 实际输出行数、分区大小 | 每次执行产生 |
列级统计是 CBO 的主粮,也是最容易过期的。ANALYZE TABLE 之所以要定期跑,就是因为 NDV 会随数据增长而漂移。9.1 的 AQE 走的是另一条路:不指望事前统计准确,而是用运行时统计在计划执行到一半时纠偏。
代价模型的边界
代价模型再细,也只是对真实执行的近似。它通常忽略缓存命中、CPU 频率、网络抖动、数据倾斜这些因素,只保留行数、I/O、CPU 的粗粒度项。
| 被建模 | 常被忽略 |
|---|---|
| 行数、字节数 | 缓存局部性 |
| 顺序/随机 I/O | 网络拥塞 |
| 排序比较次数 | 数据倾斜 |
| build 内存占用 | 并发争抢 |
忽略倾斜是代价模型最大的盲区。估算按「平均值」算,一个 key 独占了 80% 的数据,平均值完全看不出来。这也解释了为什么 9.3 的倾斜处理必须依赖运行时观测,而不能只靠事前代价。
三个常见误解
误解一:CBO 一定比 RBO 好。 真相:CBO 的上限取决于统计质量;统计过期 100 倍时,基于代价的选择可能还不如一条稳定的启发式规则。
误解二:选择率就是 1/NDV,估得很准。 真相:1/NDV 假定均匀分布,长尾数据下热门值可能被低估几十倍,冷门值可能被高估。
误解三:join 输出行数等于两表行数相乘。 真相:等值 join 要除以 NDV;本例 1 万 × 10 万除以 10 万等于 1 万行,直接相乘会高估 10 万倍。
一句话总结本节
CBO 先估行数再算代价:等值谓词选择率约 1/NDV,NDV 1000 时为 0.001;左 1 万行乘右 10 万行再除以 NDV 10 万,join 输出 1 万行;hash join 代价 505 万,sort-merge 排序约 9966 万 ns,默认选 hash;统计过期让实际 NDV 10 万被估成 1000,基数偏差 100 倍,这是 CBO 最常见的失效方式。
本节 lab
在 bd-engine-lab 中验证选择率与代价比较:
- 源码:
src/optimizer/Optimizer.java与src/optimizer/OptimizerSuite.java。 - 运行:
cd bd-engine-lab && mkdir -p out && javac -d out $(find src -name '*.java') && java -cp out lab.RunAll。 - 断言:用例 71 验证「NDV 1000 的等值谓词选择率为 0.001」;用例 72 验证「左 1 万行 × 右 10 万行、NDV 10 万,join 输出 1 万行」;用例 73 验证「hash join 代价 505 万,sort-merge 约 99,657,842.8ns,hash 更优」;用例 74 验证「实际 NDV 10 万、估算 1000,基数偏差 100 倍」。
- 整卷 runner 的预期汇总为
TOTAL: 116 passed, 0 failed。
对应本节判断链:规则优化选不了顺序 → 用 1/NDV 估选择率、用行数乘除估 join 基数 → 把行数代入 hash 与 sort-merge 的代价式比较 → 统计过期时 100 倍偏差让估算失效 → 定期 ANALYZE,或在运行时用 AQE 纠偏。
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。