第15讲数据库查询处理与优化分解.ppt

物理优化 【例7-10】假定B(R)=1000，B(S)=500，M=101。假设一个块可以容纳每个关系的10个元组，即T(R)=10000，T(S)=5000，同时假设V(S,Y)=100。计算采用基于索引的连接算法代价。 如果R是聚集的，需要1000次磁盘I/O用来读取R的所有元组。 S在Y上有一个聚集索引，需要10000×500/100=50000次磁盘I/O读取S。 如果R是非聚集的或S上的索引是非聚集的，代价会更高。 物理优化 操作符的实现算法 连接操作的实现算法 基于索引的连接运算 常见的连接查询的情况是与S相比，R是很小的，V(S,Y)是很大的。在这种情况下，S的大多数元组的Y值根本不出现在R中，这些元组将无需被算法检查，即不需要读入内存。但是，不论基于排序的还是基于散列的连接方法都需检查S的每一个元组至少一次。所以，在实际的应用中，索引选择算法仍是一种常用的方法。 【例】分析实现“查询选修了课程号为‘c02’课程的学生姓名” （1）T(S)=1000，T(SC)=10000。选修“c02” 课程的元组为50个。 （2）一个磁盘块能存储10个S元组记录，或100个SC 元组记录。则B(S)=100， B(SC)=100。 ? Q1: SELECT SN FROM S，SC WHERE S.Sno=SC.Sno AND SC.Cno= c02 ; Q1：πSN ((бSC.Cno= c02 (SC) ? S)) —————————— R 物理优化 物理优化 物理优化 从一个逻辑查询计划产生物理查询计划时，为逻辑查询计划的每一个操作符选择实现算法并选择这些操作符的执行顺序，还包括许多实现细节。 被查询的关系是怎样被访问的，即获得所存储数据的方式以及一个关系何时或是否应当被排序等； 必须估计每个可能选项的执行代价，使用代价估计来评价一个查询计划。 基于代价的物理优化方法 查询计划的代价因素 一个查询的实际执行所需的代价包括: 磁盘访问代价：读写记录所在磁盘数据块的代价。 存储代价：存储由查询执行计划产生的中间结果文件的代价。 计算代价：在查询执行过程中对数据缓冲区完成内存操作的代价。 内存使用代价：与执行查询所需内存缓冲区数相关的代价。 通信代价：将查询与查询结果从一个数据库站点传送到另一个站点（或发出查询的终端）的代价。 物理优化 基于代价的物理优化方法 查询计划的代价因素 代价用的磁盘I/O次数受以下因素影响： 在选择逻辑查询计划时所选取的用于实现查询的逻辑查询运算符，例如进行乘积运算还是连接运算。 中间关系的大小。 用于实现逻辑查询运算符的物理查询运算符，例如连接运算算法的选择，对给定关系是否加以排序等其他运算。 由一个物理运算符向下一个物理运算符传递参数的方式，例如，通过在磁盘上保存中间结果还是通过使用迭代算子每次传送一个参数的一个元组或一个主存缓冲区。 物理优化 基于代价的物理优化方法 查询计划的代价因素 在对由给定的逻辑查询计划导出可能的物理查询计划进行评价时，我们需要知道各个物理计划的代价是多少。 在不执行查询计划的情况下，我们不能准确知道其代价。 由于执行一个查询计划比查询编译器选择一个计划所做的工作要多得多，我们需要不执行查询计划而估计该计划的代价。 要准确估计不同查询计划的代价，查询优化器需要从数据库中有效地获得某些重要的参数信息，即从数据字典中获取代价估计所需的各种信息。 物理优化 基于代价的物理优化方法 代价估计基于的数据信息 对每个关系表文件，该表的记录总数（T）、记录长度、占用的块数（B）、占用的溢出块数（BO）； 对关系表文件的每个属性，该属性不同值的个数（V）、选择率（具有该值的记录数/T）、该属性最大值、最小值，该属性上是否已建索引，何种索引（B+树索引、散列索引、聚集索引）； 对于索引，比如B+树索引，该索引的层数（L）、不同索引值的个数、索引的选择基数S（有S个元组有某个索引值）、索引的叶结点数（Y）等等。 物理优化 优化器可以根据这些信息作出正确的估算，选择高效的执行计划。 基于代价的物理优化方法 物理查询计划的选择方法 由给定的逻辑查询计划可有多个可能的物理查询计划，要穷尽所有的查询计划进行代价估算往往是不可行的，会造成查询优化本身付出的代价大于获得的益处。 常常先使用启发式规则，选取若干较优的候选方案，减少代价估算的工作量；然后分别计算这些候选方案的执行代价，较快地选出最终的优化方案。 物理优化 基于代价的物理优化方法 物理查询计划的选择方法 启发式选择 某些操作（如选择和连接操作）可以有多种执行这个操作的算法，可以根据一些启发式规则来选择代价较小的实现操作的算法。 物理优化 基于代价的物理