《大规模分布式计算深入解析》8.2 CBO 与统计信息

CBO 先估行数、再算代价、最后选算法。本节用 NDV 1000 推出选择率 0.001,用 1 万 × 10 万、NDV 10 万算出 join 输出 1 万行,比较 hash 505 万与 sort-merge 的 9966 万 ns,并说明统计过期带来的 100 倍偏差。

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 万行过滤后(公式推导)
1000.0110,000 行
1,0000.0011,000 行
10,0000.0001100 行

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 NDV100,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
阶段行数代价贡献
build50,00050,000
probe5,000,0005,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,0000.001
实际100,0000.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

下载卷五 Java 8 实验 · 实验运行与版本说明

在 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 纠偏。

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析》15.3 落地:从 Neo4j 到自研图引擎
  2. 《大规模分布式计算深入解析·图计算与图数据库内核》 · 目录与学习路径(45 篇)
  3. 《大规模分布式计算深入解析》15.2 十一卷主线:从切分到图