RBO 模式和 CBO 模式 | 青年营说明

RBO模式和CBO模式|青训营笔记

这是我参与【第四届青训营-大数据场】笔记创作活动的第2天

RBO模式

• ROB是基于关系代数等价规则对逻辑计划进行变换他符合等价变化关系，例如结合率，交换率，
• RBO具有传递性
• 主流ROB实现的一般都有几百条基于经验归纳得到的优化规则
• 优点是实现简单，优化速度快
• 缺点是不保证得到最优的执行计划

• • 单表扫描:索引扫描(随机 I/O)vs. 全表扫描(顺序 I/O)
• • √ 如果查询的数据分布非常不均衡，索引扫描可能不如全表扫描
• • Join 的实现:Hash Join vs. SortMerge Join
• • 两表 Hash Join:用小表构建哈希表--如何识别小表?
• • √ 多表Join:
• • 哪种连接顺序是最优的?
• • 是否要对每种组合都探索?
• • √ N个表连接，仅仅是 left-deep tree 就有差不多 N! 种连接顺序
• • N = 10 -> 总共 3, 628, 800 个连接顺序 CBO模式

• • 使用一个模型估算执行计划的代价，选择代价最小的执行计划
  • 分而治之，执行计划的代价等于所有算子的执行代价之和
  • 通过 RBO 得到（所有）可能的等价执行计划（非原地替换）是RBO的下一步选择
  • 算子代价包含 CPU，cache misses，memory，disk I/O，network I/O 等代价
  • 和算子的统计信息有关，比如输入、输出结果的行数，每行大小等
    • 叶子算子 scan：通过统计原始表数据得到
  • 中间算子：根据一定的推导规则，从下层算子的统计信息推导得到 - 和具体的算子类型，以及算子的物理实现有关（e.g. hash join vs. sort join）
  • 使用动态规划枚举所有执行计划，选出执行代价最小的执行计划 原始表统计信息

• 表或者分区级别：行数、行平均大小、表在磁盘中占用了多少字节等

列级别：min、max、num nulls、num、not nulls、num、distinct value(NDV)、histogram 等

• 选择率（selectivity） ：对于某一个过滤条件，查询会从表中返回多大比例的数据
• 基数（cardinality） ：基本含义是表的 unique 行数，在查询计划中常指算子需要处理的行数

社区资源开发