CMU-15-445笔记(十三)
Cost Model
Statistics
DBMS将内部的一些关于table, attributes, indexs的静态信息存到内部的catalog里面，不同的系统会有不同的更新方式
Selection cardinality（选择基数）
现在假设有R种关系，对于每个都有$N_R$个tuple，$V(A,R)$代表了$A$ attribute中不同的value的数量。假设数据分布出现的均匀，代表A属性下每个值平均的记录个数。
$$SC(A,R)=N_R/V(A,R)$$
Complex Predicates
selectivity(选择率)表明table中有多少tuple符合查询的条件。每种操作都有不同的选择率的计算
Equality Predicate
$$sel(A=constant) = SC(P)/N_R$$
假设有一个age表，有0-4值，每个值出现的次数一样，那么
$$SC(age=2)=1$$
$$sel(age=2)=1/5$$
Range Predicate
$$sel(A>=a)=(A_{max}-a)/(A_{max}-A{min})$$
例如
$$sel(age>=2)\approx (4-2)/(4-0) \approx 1/2$$
这里的选择率和实际上的概率（3/5）是不等于的，有可能会导致operator拿到的数据比预估的多
Negation Query
$$sel(not P) = 1-sel(P)$$
例如
$$sel(age!=2) = 1 (1-(1/5))=4/5$$
这里selectivity = probability
Conjunction
$$sel(P1\land P2)=sel(P1) \bullet sel(P2)$$
例如
$$sel(age=2 \land name ; LIKE ‘A%‘)$$
这里假设两个概率都是独立的。
Disjunction
$$sel(P1 \vee P2) = sel(P1)+sel(P2) - sel(P1) \bullet sel(P2)$$
问题
以上的计算都是基于三个假设
- 数据分布均匀
- 概率独立
- join时每个tuple都有对应的outer tuple
现实中三种假设不一定成立，所以会出现误差。假设现在要选择车的品牌和车的型号，因为上面的概率独立假设，品牌和型号的概率是要进行相乘的，但是实际上，这两个概率并不独立，型号对应了特定的品牌，所以就会出现预测的选择率偏低的情况。
统计方式
对于不是均匀分布的数据来说，可以将每个attribute下的数据分为几个bucket，每个bucket，一种方式是每个bucket的宽度相同，但是这样对于bucket内小数据不公平
另一种方式就是让每个bucket的总和大致相同
Sampling
在高端数据库中，可以使用采样，将真实的table的分布采样成更小的副本，计算选择率之类的数据的时候直接用副本来计算。
Query Optimization
有了以上的cost的计算方式，就可以用来选取 query plan
Single Relation Query Plan
对于单一关系的查询，首先是确定访问的方式
- 顺序查询
- 二分/聚簇查询
- 索引查询
然后去判断条件的顺序，如果某个条件能去掉更多的数据，那它应该优先使用
OLTP Query Plan
首先判断这个查询是否是sargable的（Search Argument Able ），大概意思就是查询过程可以使用一个最优(选择率)的索引来辅助查询。
Multi Relation Query Plan
在System R系统中（早期系统），多重join使用的是 left deep join trees，这样可以使join后的结果可以直接通过pipelin传递，不需要中间存储来等待另一个join
对于怎么实现join，需要考虑到join的顺序，operator的种类，以及访问table的方式，可以使用dynamic programming 来减少总的耗时。
首先计算出所有的可能方式的花费，然后找一条总cost最少的路径来实现join
实现join的总综合步骤
- 枚举realtion的顺序
，对于systemR来说，只考虑left outer join，所以最右两个被排除。 - 对于每个顺序（不包括被排除的），计算每种join algorithm的cost
- 计算每种访问table的cost
Postgers Optimizer
对于有12表join以下的，Postgers用的就是SystemR的方式，以上的用的是遗传算法。
CMU-15-445笔记(十三)