首页 cmu 15-445

CBS (cost-based search 基于代价)

手动调用更新代价表
postgres/SQLite: ANALYZE
Oracle/MySQL: ANALYZE TABLE
SQL Server: UPDATE STATISTICS
DB2: RUNSTATS

N: number of tuples in R,R表中tuple的数量

V(A, R):number of distinct values for attribute A, A这里列有多少唯一值

SC(AR) selection cardinalityN / V(A, R) 注意,用这种方式数据是uniformity,均匀的

selectivity sel选择率,根据谓词的选择性选择率去计算选择率

谓词有:equality range negation conjunction disjunction

假设一个表distinct value有五个值

equality predicate : 相等谓词时 sel (=2)= SC(P) / N = 1 / 5

如果使用这种方式,就假设数据是均匀的

range predicate : 范围谓词 sel (>=2)= 2 / 5

negation query : 不等查询 sel(!= 2) = 1 - 1 / 5 = 4 / 5

发现选择性与概率很相像,那么多个谓词就可以取多个谓词的交集

conjunction 就是交集

disjunction 就是并集

join:

1.png

以上基于的假设:

  • uniform data 数据是均匀的
  • independent predicates 谓词的选择性是独立的
  • inclusion principle 假设join时总能找到匹配

但是有时候谓词的选择性是不独立的,例如雅阁这种车型只有本田有,所以概率应该是雅阁的概率而不是雅阁的概率乘本田的概率

所以基于不独立,不均匀的数据(实际的数据),但是也不能搞一个新表做一个统计信息可能占比太大了,就需要其他方式了

equi-width histogram等宽直方图,不记录特定值,而记录一个范围的占比

equi-depth histogram等深直方图,不记录特定值,记录特定数量的所占的数据,例如前十个数据在那个范围

sketchs 从概率上推断数据

count-min sketch

hyperloglog

sampling采样,小表上概率是多少,大表从概率上来说也是多少,当然,如果大表上数据被删除了,小表也要删除,而且毕竟跑了一遍数据,也算是浪费时间了

我们找到执行计划的代价的目的是为了找到多个执行计划中可能最佳的执行计划

针对单表的查询,可以用规则查找

多表查询, join是有很大的搜索空间,可以进行优化,例如必须是左深树等等 可以列举怎么构建左深树,执行计划,读表方式,一般使用动态规划降低搜索量

例如R join S join T,谁先join,hash join or merge join,就可以使用代价(cost)模型加剪枝来得到运行结果

暴力搜索:先列举所有可能,再根据规则删除一些,例如要删除使用笛卡尔积的,然后根据cost模型选择hash join or merge join,之后在取寻找读表方式,找到最佳的

2.png

GEQO genetic query optimizer 遗传算法

列举几种方式,把最差的干掉,对剩下的做基因突变,迭代的更新,规定一个优化时间,得到一个最好的,得到的不一定是最好的,但一定是比较优秀的,而且如果表太多 走动态规划太浪费时间了

3.png




文章评论