2015 第八讲-查询优化.ppt

* * 因此，只用于选择度较低的情况 * * * * * * * * * * * 本质上是在SC上做选择运算 * 本质上是在SC上做选择运算 * 本质上是在SC上做选择运算 * * * * * 思想：如果R和S的原组能进行连接，则它们的连接属性作为键值会在散列到具有相同索引项的bucket中。 * 思想：如果R和S的原组能进行连接，则它们的连接属性作为键值会在散列到具有相同索引项的bucket中。 * 思想：如果R和S的原组能进行连接，则它们的连接属性作为键值会在散列到具有相同索引项的bucket中。 * 思想：如果R和S的原组能进行连接，则它们的连接属性作为键值会在散列到具有相同索引项的bucket中。 * 思想：如果R和S的原组能进行连接，则它们的连接属性作为键值会在散列到具有相同索引项的bucket中。 * * 操作树中的三个操作可以放入一个流水线 * * 那么如何来衡量查询的性能？ * 当涉及到多关系进行连接时,通常在内存中尽可能多地加载某个表,而留下一块存放另一个表. * 知道了这些信息后，就可以对查询处理进行一个简单地估算。 * * * * 临时关系大小估计 一个操作的代价依赖于它的输入的大小和其他统计信息 基本统计信息 nr:关系r的元组数 br:包含关系r中元组的磁盘块数 lr:关系r中每个元组的字节数 fr:关系r的块因子 —— 一个磁盘块能容忍的关系r中元组的个数 V(A,r):关系r中属性A中出现的非重复值个数，与πA(r)相等。如果A是r的主码， V(A,r)=nr。 选择运算结果的大小估计 假设：取值均匀分布 单独的等值谓词σA=a(r) 假设属性A存在值a 估计选择结果包含nr/V(A,r)个元组 单独的比较谓词σA≤v(r) 已知的统计信息包括min(A,r)和max(A,r) 若v min(A,r),则有0个元组 若v max(A,r),则有nr个元组 否则，元组个数为 nr v - min(A,r) max(A,r) - min(A,r) . 选择运算结果的大小估计 复杂选择-合取 合取选择 σθ1∧θ2…∧θn (r) 假设：各条件θi相互独立； 对每个θi，按前面方法计算 σθi (r)，记为si ； σθi (r)的中选率(selectivity)为 si /nr，即关系中一个元组满足选择条件θi的概率； 则满足全部选择条件的元组数量为 nr s1 * s2 *···* sn nrn * 选择运算结果的大小估计 复杂选择-析取 析取选择 σθ1∨θ2…∨θn (r) 如前所述，si/nr 代表某元组满足条件θi的概率； 元组满足整个析取式的概率为 将该数值乘以nr，即得到满足选择条件的元组数的估计。 * 1- (1- ) nr s1 (1- ) nr s2 (1- ) nr sn * * ··· 选择运算结果的大小估计 复杂选择-取反 若无空值 σ ? θ (r) ：不在σθ(r)中的关系r的元组集； σ ? θ (r) 的元组数为 nr 减去σθ(r)的估计元组数； 若有空值 首先估计对条件 θ取值为未知的元组数目； 然后从上面无空值的估计中减去该数目； 连接运算结果的大小估计 笛卡尔积 r×s 包含nr*ns个元组，每个元组占用lr + ls个字节； 自然连接 假设：每个值等概率出现，令 r(R) 和 s(S)为两个关系； 若R∩S = ?，则r s与r×s结果一样； 若R∩S是R的码，则 s 的一个元组至多与 r 的一个元组连接，r s中的元组数不会超过 s 的元组的数目； 若R∩S构成了S中参照R的外码，则r s中的元组数正好与s中的元组数相等； 连接运算结果的大小估计 自然连接（续） 若R∩S既不是R的码也不是S的码，假定R∩S={A}，r 的元组 t 在r s中产生： 个元组，则r s中的元组数为： 若将 r 与 s 角色颠倒，则r s的元组数为： 取二者中的较小值 V(A, s) ns V(A, s) nr*ns V(A, t) nr*ns 连接运算结果的大小估计 θ连接 将r θ s重写成σθ (r×s)的形式； 利用笛卡尔积的大小估计和选择操作的大小估计相结合的方法进行。 课程安排 查询优化 查询优化的必要性 关系表达式的转换 启发式优化 临时关系大小估计 基于代价的优化 查询处理 查询处理过程概述 典型索引结构 选择运算的查询处理 连接运算的查询处理