(十四--十五)数据库查询优化Part I
如果理解的有问题。欢迎大家指出。这也是我在看课记得笔记。。可能会有很多问题
查询优化的重要性
请记住用户只会告诉DMBS他们想要什么样的结果，而不会告诉他们如何获得结果
不同的查询plan性能上会有非常大的差距。[比如之前的nested join 和 index join]
1. Heuristics / Rules策略这一策略侧重于重构那些愚蠢的sql语句
注意这里的Logical Plan和Physical Plan是不同的
在第一个阶段我们会重写SQL语句。这里更多的是利用一些启发式的思维，比如列裁剪（过滤掉查询不需要使用到的列）、谓词下推（将过滤尽可能地下沉到数据源端）、常量累加（比如 1 + 2 这种事先计算好） 以及常量替换（比如 SELECT * FROM table WHERE i = 5 AND j = i + 3 可以转换成 SELECT * FROM table WHERE i = 5 AND j = 8）等等。
后面会把引用格式转换成内部的标识符，然后构建语法树。至此我们的逻辑计划就大致构建完成。⚠️一个逻辑计划会对应许多的物理计划。
最后Optimizer的作用就是选择代价最小的物理计划。根据代价，将确定从逻辑计划到物理计划的选择
这里需要一点关系代数的只是。但是cmu数据库重点并不是放在这个上面。所以附上一个链接大家看看就好
物理查询的代价估计与选择
1.1 重写sql的优化-->谓词PushDown这里用几个ppt里的例子看一下。这个操作对于查询的优化
左右两个语法树最后产生的结果完全一致。但是性能上确大相径庭。
左边是整个Student表和右边的enrolled表做join操作。然后再做select操作。但是如果在enrolled表中只有几条元素满足grade==A。这样我们把昨天的sql重写成右边的sql就会让整体的性能提高许多。
从语法树上看我们把select grade =='A'这个谓词向下push了。所以这种优化也叫谓词push down。
1.2 重写sql的优化 --> PROJECTION PUSHDOWN
我们先进行投影操作。就可以减少遍历tuple的大小。对于速度和内存上都是不小的优化
同样我们可以直接删掉那些不可能或不必要的谓词
对于下面的我们就可以直接忽略谓词
对于下面的操作我们可以合并谓词
为了估计花销而引入的一些变量
\(N_R\) : Number of tuples in R.
\(V(A,R)\): Number of distinct values for attribute A.
\(SC(A,R)\) :selection cardinality is the average number of records with a value for an attribute A given \(\frac{N_R}{V(A,R)}\)
2.1 SELECTION STATISTICS这里假设了所有的数据都符合均匀分布
看下面的例子。这个关系中有5个tuple。年龄分别为0～4。那么假设数据符合均匀分布。年龄为2的人在里面就占了百分之20.
再看下面对于范围谓词的例子
这里其实很好理解。就是看A所在的范围在整个数据范围占的比例
对于neg谓词
一些复杂的谓词
这里和概率论里的容斥原理基本类似
对于交运算
对于或运算