重邮版第七章

第七章关系查询优化

本章要点

关系查询优化的基本概念关系查询优化的一般准则7.1查询优化的基本概念同一个关系查询可以有多种等价表达形式，但由于计算、磁盘访问、中间结果存储、通信传输等环节都会产生不同的CPU、内存、磁盘I/O等代价，不同表达形式的查询效率可能存在明显差异。例：求5号客户购买的服装品牌，系统可以用多种等价的关系代数表达式来完成这一查询：假定数据库中有l000件服装，l0000个购买记录，其中5号客户的购买记录为50个。同时，假设读取表的策略为：一个块能装10条服装记录或100条购买记录，在内存中存放5块服装记录和1块购买记录，每秒读写20块。Q1的时间代价1.计算笛卡尔积读取所有数据库记录到内存所需时间=需读取总块数/20。其中，需读取总块数为1000/10+1000/(10*5)*10000/100=2100，则读取数据的时间是105秒。设每块能装10条笛卡尔积所得到的记录，则将积结果从内存写到中间文件的时间是1000*10000/10/20=50000秒。2.选择操作需要将笛卡尔积的结果从中间文件读入内存，其时间为1000*10000/10/20=50000秒。3.投影运算由于选择操作后得到的结果仅50条记录，最后在此基础上作投影运算，其时间可以忽略。另外，忽略内存代价，执行Q1的总时间约为100105秒。Q2的时间代价1.计算自然连接读取数据的时间和Q1相同是105秒。将自然连接的计算结果写到中间文件的时间为10000/10/20＝50秒。2.选择操作需要将连接后的结果从中间文件读入内存，所需要的时间和写入的时间相同是50秒。3.投影运算对上一步所得的结果进行投影运算，其时间可忽略。同样忽略内存代价，执行Q2的总时间约为205秒。Q3的时间代价1.选择运算现对购买记录表作选择运算，只需读一遍服装记录表，其读取时间为10000/100/20=5秒。因为满足条件的记录仅50条，不必使用中间文件。2.自然连接读取服装记录表，把读入的服装记录和内存中的购买记录作连接，也只需读一遍服装记录表，其读取时间为1000/10/20=5秒。3.投影运算对第二步得到的结果进行投影运算，其时间可忽略。同时忽略内存代价，执行Q3的总时间约为10秒。关系查询优化的目的关系查询优化的目标是根据用户输入的查询语句，选择有效的查询计划并求得给定关系表达式的值。关系查询优化对提高RDBMS的查询效率是非常必要的，是影响RDBMS性能的关键因素。查询优化是由RDBMS中自动完成的，用户不必考虑如何最好地表达查询才能获得较好的效率。查询处理过程7.2关系代数表达式的变换关系代数表达式的优化是关系查询优化的基础。两个关系表达式El和E2是等价的，是指用相同的关系代替两个表达式中的关系变量所得到的结果是相同的，并记为E1≡E2。常用的等价变换规则①连接、笛卡尔积交换律常用的等价变换规则②连接、笛卡尔积的结合律常用的等价变换规则③投影的串接定律④选择的串接定律常用的等价变换规则⑤选择与投影的交换律这里，选择条件F只涉及属性A1,...,An。若F中有不属于Al,...,An的属性B1,…,Bm则有更一般的规则：常用的等价变换规则⑥选择与笛卡尔积的交换律如果F中涉及的属性都是El中的属性，则如果F=F1∧F2，并且F1只涉及E1中的属性，F2只涉及E2中的属性，则由上面的等价变换规则1、4、6可推出：若F1只涉及E1中的属性，F2涉及E1和E2两者的属性，则仍有常用的等价变换规则⑦选择与并的交换⑧选择与差运算的交换常用的等价变换规则⑨投影与笛卡尔积的交换⑩投影与并的交换7.3查询优化的一般准则利用等价变换规则可以得到查询的所有等价式，但在实际应用中不可能也没有必要计算一个查询的所有等价式，而是使用一些优化准则进行关系表达式的变换。利用查询优化策略一般能提高查询效率，但不一定是所有策略中最优的。7.3查询优化的一般准则（1）选择运算应尽可能先做。选择运算一般使计算的中间结果大大变小，提前处理常常可使查询代价降低几个数量级。（2）在执行连接前对关系适当地预处理。如执行连接前事先在连接属性上建立索引，可以减少对表的扫描次数，从而大大减少连接处理的时间。（3）投影运算和选择运算同时进行。如有若干投影和选择运算，并且它们都对同一个关系操作，则可以在扫描此关系的同时完成所有的这些运算以避免重复扫描关系。7.3查询优化的一般准则（4）把投影同其前或其后的双目运算结合起来。没有必要为了去掉某些字段而扫描一遍关系。（5）把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算，连接特别是等值连接运算要比同样关系上的笛卡尔积省很多时间。（6）找出公共子表达式。对那些重复出现且结果不是很大的子表达式，可以先计算一次并把结果写入中间文件，需要时从外存中读入。7.4查询优化的处理步骤实际系统对查询优化的具体实现一般可以归纳为四个步骤：将