cmu15445 查询优化- 下

• DBMS在其内部 catalog 中存储有关表、属性和索引的内部统计信息。不同的系统在不同的时间更新它们。

• 选择基数 SC(A, R)

• 给定NR / V（A， R）的属性A的值的平均记录数

LOGICAL COSTS

COMPLEX PREDICATES 复杂谓词

• 公式取决于谓词类型：

Equality

• Nr 是 people 的数量 =5

• V(age,people) = 5

• SC(P)：每个年龄的值，平均能选上几个人

• 在数据不倾斜的假设下，5个人对应 5 个年龄

• SC(P)=1

• sel(A=constant)=1/5 age这列的选择率就是1/5

Range

Negation

• 从选择率近似于概率，自然的引出多谓词的情况

• 如图语句中 and 的情况

• 可以取两个选择率的交集

Conjunction 交集

Disjunction 并集

RESULT SIZE ESTIMATION FOR JOINS

• 认为每个内表里的所有数据都能和外表找到至少一个匹配

• 表 R 和表 S 相交的列只有 A col

• Ns 先和 S 表算选择率，再和 Nr 乘

• 交换律

• Nr 先和 R 表算选择率 ，再和 Ns 相乘

• 最后得出结论

• join 的结果集的大小是

• 分母选大的

• 最后 size 选个小的结果

• 用这个公式去估计两表 join 结果集大小

SELECTION CARDINALITY 3条件

• 数据均匀分布

• 谓词选择性独立

• 数据对应

• 假设这三个条件都满足，才有上面的估算方法

• 当然也有反例，谓词不独立时候 举例

CORRELATED ATTRIBUTES 关联属性

• 谓词独立出现问题了

• 不能简单的 1/10 x 1/100

• 因为只有本田生产雅阁，别的公司不生产雅阁

• 所以只用 1/10 就行

• 均匀的估计很好用

• 但是会出现问题

• 实际上的数据分布不一定是均匀的

• 简单粗暴的记录每个数据出现了几次

• 这样记录下的 key 的大小显然很大

• 所以出现几种方法来改进这种情况

EQUI-WIDTH HISTOGRAM 等宽直方图📊

• 不记录每个，而是按取件记录数量

• 问题也有
• 比如 11 没有
• 7 8 差距过大
• 当然也可以改进
• 用等深直方图

EQUI-DEPTH HISTOGRAMS 等深直方图

• 宽度不定 1-5，6-8

• 但是每个桶的总数是差不多的 10 个左右

• 优点
• 节约内存
• 精确度进步

SKETCHES 草图

Count-Min Sketch

HyperLogLog

• redis 有用

SAMPLING 采样

• 5 点采样法回忆一波种地

• 问题
• 小表开销
• 维护数据删除同步

• 好处
• 真实数据来估计

OBSERVATION 目的

• 上边讨论了半天代价估计的手段

• 但是我们还需要枚举出很多计划才能对比他们各自的代价

• 我们知道代价的目的是从候选的计划选出代价最小的

QUERY OPTIMIZATION

SINGLE-RELATION QUERY PLANNING 单表

• 三种扫描方法
• 有索引就用索引

• 谓词下推

• oltp 系统经常用 rbo

• 简单的启发式就行

MULTI-RELATION QUERY PLANNING 多表查询

• 多表会经常出现 join

• 要降低 jion 的开销

• 只使用左深树

• 左深树带来一个意想不到的好处

• 流式处理，无需暂存中间结果

• 顺序

• 算子

• 扫描

• 列举方案使用动态规划

DYNAMIC PROGRAMMING

• 剪枝

• 继续

• 剪枝

• 最后得到一条最优路径

• 实现细节省略了 扫描

CANDIDATE PLAN EXAMPLE 纯暴力 不用动态规划 一般没 DB 用这个

• 干掉笛卡尔积

• 列举出join 算法

• 列举读表方法

Example

POSTGRES OPTIMIZER

• 动态规划 12 个表以内

• 遗传算法 超过 12 个

• 不止左深树

遗传算法

• 随机选三个全局方案 选两较好的

• 干掉最差的 优胜劣汰

• 做基因突变

• 再随机生成一个

• 算开销

• 干掉

• 做突变 换方法

CONCLUSION

• 尽早下推

• Selectivity estimations
• 均匀
• 谓词独立
• jion 能找到 jion 对象
• 直方图
• 表有相关性时候

• 动态规划

• 真难🤯