基于存取路径的规则优化

1、2.1Database Systemn纯代数优化未考虑到查询表上的存储情况，可能会盲目优化。n根据被查询表上的索引等情况，总结一套非定量的规则，用于进行执行方案的选择。n对每一种关系代数的操作单独考虑这些规则2.2Database Systemn选择操作的执行策略与下列因素有关：H选择条件：等值，范围H可用的存取路径H选取的元组数n选择操作的实现方法H顺序扫描H利用主键索引H利用二次索引或簇集索引4等值查询效率与范围查询效率H散列索引，如果在查询字段上建有散列索引，且是等值查询4如果是范围查询的效率如何？H多属性索引2.3Database Systemn小关系：顺序扫描n结果为20%以上，顺序

2、扫描n主键上的等值查询，用主索引n非主键上的等值查询H小于20%，用二次索引H大于20%,用簇集或顺序扫描n范围查询，用B+树的顺序集或簇集索引H选择条件是在排序主索引上的比较H选择条件是在次索引上的比较H如果无索引，用顺序扫描P1222.4Database SystemnAND连接的多条件选择H多属性索引H预查找法H利用部分索引，同时进行其它条件的判断H建立临时索引H顺序扫描nOR连接的多条件选择H分条件计算H预查找法H顺序扫描2.5Database Systemn直接利用索引H在索引键上的选择H部分聚集函数的计算4MIN4MAX4COUNT4SUM4AVGSelect max(age),s

3、um(age)from student2.6Database SystemnJOIN操作的几种计算方法HNested-loop joinHBlock nested-loop joinHIndexed nested-loop joinHMerge-joinHHash-join2.7Database SystemTuple-based scan2.8Database System如：计算连接如：计算连接depositor customer的代价：的代价：ndepositor=5000; ncustomer=10000;fdepositor=50; fcustomer=252.9Database S

4、ystemBlock-based scan2.10Database System与b bs s * * b br r+b+bs s比较？小关系作为内或外关系时何为更有效？2.11Database System计算要访问的物理块数？nB是计算可用的缓冲物理块数，r是br块，s是bs块，则涉及的物理块的输入数是br+ （br/ （nB - 1）* bsnB - 11缓冲区brbsr关系s关系2.12Database System临时索引2.13Database System如连接计算时，内关系中有超过20%的元组会被连接上，则用顺序扫描比用无序的二次索引的效率高。2.14Database Syst

5、em2.15Database System算法见书P124图6-52.16Database System桶2.17Database System2.18Database System2.19Database System2.20Database Systemn两个关系已按连接属性排序，并且为等值或自然连接时，则采用两个关系已按连接属性排序，并且为等值或自然连接时，则采用排序归并法。排序归并法。n两个关系中一个关系已按连接属性排序，另一个没有排序：两个关系中一个关系已按连接属性排序，另一个没有排序：H如未排序的关系较小，可先将小关系排序，再采用排序归并法。如未排序的关系较小，可先将小关系排序，再

6、采用排序归并法。H如未排序的关系建立有如未排序的关系建立有B+树次索引，可采用混合归并连接方法。树次索引，可采用混合归并连接方法。n两个关系中一个关系在连接属性上建立有索引或散列两个关系中一个关系在连接属性上建立有索引或散列H可将该关系作为内关系，利用索引或散列寻找匹配元组。可将该关系作为内关系，利用索引或散列寻找匹配元组。H如果两个关系均在连接属性上建立有索引，可将小关系作为外关系。如果两个关系均在连接属性上建立有索引，可将小关系作为外关系。H如果作为内关系建有次索引，但匹配元组较多时，可采用基本嵌套循如果作为内关系建有次索引，但匹配元组较多时，可采用基本嵌套循环法。环法。n在连接属性上无任

7、何存取路径，可采用基本嵌套循环法。在连接属性上无任何存取路径，可采用基本嵌套循环法。n在连接属性上无任何存取路径的等值或自然连接，可采用散列连在连接属性上无任何存取路径的等值或自然连接，可采用散列连接法。接法。2.21Database System2.22Database System2.23Database System排序算法是大量使用的2.24Database SystemP126-1272.25Database System2.26Database System2.27Database System2.28Database Systemn一个查询操作中可包含多个操作，因此，尽量将其中的

8、操作组合起来同时进行，可以减少临时文件的创建，省去许多操作。n例子：P1282.29Database Systemn通过定量的代价比较，进行更精确的方案选择,前面的规则优化中仅提供基于访问路径的算法和一些启发式规则。n代价只能估算:H磁盘的I/O次数2.30Database System2.31Database SystemnnR-关系R中的元组数；npR-关系R的块因子，即每个物理块中所含的元组数nNa-属性a在关系中不同值的个数nFa-属性a的选择因子，即属性a为某一属性值的概率，一般假定属性值均匀分布，即Fa=1/Na。nMa-属性a的域的大小；nL-索引的级数。2.32Database

9、 System1。顺序扫描（1）最多选取一个元组 Csa=0.5n/p=0.5b（2）选取多个元组 Csb=b2.33Database System2。利用主键上的索引或散列进行等值查询（1）通过索引 CIk=L+1（2）通过散列（假定没溢出） Chk=12.34Database System3。利用非主键上的无序索引进行等值查询满足条件的元组数估计为 s=n/N=n*F当s(n-p)时，m=b; m为需访问块数当s=(n-p)时，mb1-(1-1/b)sS很大时，m b; 可采用顺序扫描S=20(student)Q4： dept=cs and dno=108 and age=20(stude

10、nt)2.38Database Systemn估算：Q1： CQ1=L+1=5Q2： 用dept上的簇集索引 满足条件的元组数估计为s=10000/25=400 CQ2=L+ s/p=2+ 400/5=82Q3：age是非簇集索引，且是范围查询，约取一半元组，故用顺序扫描 CQ3=b=20002.39Database Systemn估算：nQ4：两种可能的存取策略：预查找法、先选取满足某个条件的元组再用其他条件筛选nA.预查找法nSdno=n/Ndno=10000/20=500n设每个物理块平均可容纳200个tid，则nCdno=L+ 500/200=3+3=6nCage=L+ 5000/20

11、0=2+25=27n预查找法代价 Ca=Cdno+Cage+500=533dept=cs and dno=108 and age=20(student)2.40Database SystemnB. 用其中一个条件选出元组，再用其他条件筛选n从三个条件的I/O代价中选最小的：ndept=cs 同Q2， CQ2=82ndno=108： Cdno=Cdno+500=506nage=20: 同Q3, CQ3=2000n其中dept=cs的代价最小nCb=82n由于CaCb，故CQ4=Cb=822.41Database Systemn假设连接条件是R.A=S.B，连接属性的域MA=MB=Mn令连接因子

12、js = | RcS| / (|R|S|)H表示连接结果占整个积的比例Hjs=1/M (参看书上的推导参看书上的推导)2.42Database SystemR为外关系，S为内关系，则 CNLJ=bR+ bR /(nB-1) bS +（js|R|S|)/PRS连接结果占的块数（后面忽略）2.43Database SystemCNSJ=bR +（|R| （LB + |S|/NB) 对R中的每一个元组，需要扫描S一次对S做一次扫描时，需要的I/O次数2.44Database SystemCSJ=bR +（|R| （LB + |S|/(NBps) 对S做一次扫描时，需要的I/O次数对R中的每一个元组，

13、需要扫描S一次2.45Database SystemCSHJ=bR +|R|h 每次散列访问的块数溢出很少的时候，h接近1对R中的每一个元组，需要扫描S一次2.46Database SystemCSHJ=bR + bS 未计入排序的代价2.47Database SystemCH=bR + bSR中一个元组可以与S进行匹配的概率为NB/M则：R中的匹配元组数=|R| (NB/M)=js|R|NB S中的匹配元组数=|S| (NA/M)=js|S|NACJ=js (|R|NB +|S|NA) 总的代价 CH + CJ预先散列的代价散列连接的代价假设元组散布在不同的物理块中2.48Database

14、Systemn关系dept，有属性dno, menon关系emp，有属性edno, enonDept的统计数据为：nD=125, bD=13,n 在dno上建有排序主索引：Ndno=125, Ldno=2n 在meno上建有二次索引：Nmeno=125, Lmeno=2nEmp上的统计数据为：nE=10000, bE=2000,n在eno上建无序索引，Neno=10000，Leno=4n在edno上建有二次索引，Nedno=125, Ledno=2n有查询：Q1：emp edno=dno deptn Q2：edpt meno=eno emp2.49Database System估算Q1：（a)

15、嵌套循环法 bDbE，选dept为外关系，设缓冲块数nB=2，则 CNLJ=bD+bD*bE=13+13*2000=26013 (b)利用索引寻找匹配元组法 扫描dept，用索引访问emp. CNSJ=bD+(nD*(Ledno+nE/Nedno) =13+(125*(2+10000/125)=10263选（b）。2.50Database System估算Q2：（a)嵌套循环法 CNLJ=bD+bD*bE=13+13*2000=26013 (b)利用索引寻找匹配元组法 扫描dept，用索引访问emp. CNSJ=bD+(nD*(Leno+nE/Neno) =13+(125*(4+10000/1

16、0000)=638选（b）2.51Database SystemnDB2提供的SQL命令可视化解释器 Visual explain，通过一个图形界面来分析存取方案和解释表中的优化器信息，可用来查看 S Q L存取计划: H 查看D B 2优化器为指定的S Q L语句生成的存取计划。H调整S Q L语句以获得更好的性能。H查看S Q L存取计划的详细信息，包括系统编目表中的统计信息。H确定是否需要在表上创建索引。H通过分析存取计划或 S Q L语句的执行性能，以确定性能问题的根源。n成本估计。对于解释的每个语句，记录执行所选存取方案的相关成本估计值。此成本以一种称为 timerons 的编制的相

17、对计量单位来给出。不提供经过时间估计值,仅估计资源消耗。 2.52Database Systemn生成存取计划图表的步骤：H如果系统编目表中的数据库统计信息已不是最新信息，则可使用 R U N S TAT S命令收集最新的统计信息。H在Commander Center的脚本( S c r i p t )页中输入一条S Q L语句。确认所输入的 S Q L语句正确无误后，H在菜单中选择interactiveCreate access plan。HCommander Center的Access plan页中将显示出一个已生成的存取计划图H使用放大滑动条可查看存取计划图的详细信息。H用鼠标双击存取计划图中的一个表节点，显示相关表的统计信息2.53Database SystemnP135页H2，3，8n补充H对例子3-4（P63）进行代数优化。2.54Database Systemn实验目的：利用DB2