《关系查询处理和查询优化》由会员分享，可在线阅读，更多相关《关系查询处理和查询优化（66页珍藏版）》请在金锄头文库上搜索。
1、关系查询处理和查询优化1 关系数据库系统的查询处理1.1 查询优化的必要性（一个实例） 【例6.1】对教材预定数据库，查询“217”号教 师预定的所有教材名称。SELECT Book.bookname FROM Book，OrderDetail WHERE Book.bookID=OrderDetail.bookID AND OrderDetail.teacherID=217；假设n该数据库中有1000个教材记录，10000条预 定记录，其中“217”号教师的预定记录有30 条。n一个块能装10个Book元组或10个 OrderDetail元组，在内存中一次可以存放5 块Book元组和1块Or
2、derDetail元组。 n读写速度：20块/秒n连接方法：基于数据块的嵌套循环法n装入的第一个表为Book表一、第一种情况 BookOrderDetail读取总块数= 读Book表块数 + 读OrderDetail表遍数*每遍块数= 1000/10+(1000/(105) (10000/10)=100+20000=20100读数据时间=20100/20=1005秒中间结果大小 = 1000*10000 = 107 (1千万条元组) 写中间结果时间 = 10000000/10/20 = 50000秒 与写中间结果时间近似相等 读数据时间 = 50000秒 忽略 总时间 =10055000050
3、000秒 = 101005秒 28小时二、第二种情况 读数据时间=20100/20=1005秒 与第一种情况相同 中间结果大小=10000 （减少1000倍） 写中间结果时间=10000/10/20=50秒 与写中间结果时间近似相等 读数据时间=50秒 忽略 总时间10055050秒1105秒18分 三、第三种情况 读OrderDetail表总块数= 10000/10=1000块 读数据时间=1000/20=50秒 中间结果大小=30条 不必写入外存 读Book表总块数= 1000/10=100块 读数据时间=100/20=5秒 忽略总时间505秒55秒n系统比用户程序“优化”的更好n优化器可
4、从数据字典中获取许多统计信息。n如果数据库的物理统计信息改变了，系统可自 动对查询进行优化以选择相适应的执行计划。n优化器可考虑百种不同的执行计划，程序员只 能考虑几种。n优化器包括很多复杂的优化技术。1.2 查询处理的步骤1. 查询分析 2. 查询检查 3. 查询优化 4. 查询执行 1. 查询分析n对查询语句进行扫描、词法分析和语法分析 n从查询语句中识别出语言符号 n进行语法检查和语法分析 2. 查询检查 n根据数据字典对合法的查询语句进行语义检查 n根据数据字典中的用户权限和完整性约束定义对 用户的存取权限进行检查 n检查通过后把SQL查询语句转换成等价的关系代 数表达式 nRDBMS
5、一般都用查询树(语法分析树)来表示扩展 的关系代数表达式 n把数据库对象的外部名称转换为内部表示 3. 查询优化n查询优化：选择一个高效执行的查询处理策略 n查询优化分类 ：n代数优化：指关系代数表达式的优化n物理优化：指存取路径和底层操作算法的选择n查询优化方法选择的依据：n基于规则(rule based)n基于代价(cost based)n基于语义(semantic based)4. 查询执行 n依据优化器得到的执行策略生成查询计划n代码生成器(code generator)生成执行查询计划的 代码 1.3 查询的执行代价n在集中式数据库中，查询的执行代价为： 总代价=I/O代价+CPU代
6、价n多用户环境下，查询的执行代价为： 总代价=I/O代价+CPU代价+内存代价n对于分布式数据库，还要加上通信代价： 总代价=I/O代价+CPU代价+内存代价+通信代价2 代数优化2.1 关系代数等价变换规则 n关系代数表达式等价n指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的n上面的优化策略大部分都涉及到代数表达式的变换设E1、E2等是关系代数表达式，F是条件 表达式，则有： E1 E2 E2E1 E1 E2E2 E1 E1 F E2E2 F E11. 连接、笛卡儿积交换律2. 连接、笛卡儿积的结合律(E1E2) E3 E1 (E2E3)(E1 E2) E3 E1 (E2 E3
7、)(E1 F E2) F E3 E1 F (E2 F E3) 3. 投影的串接定律nA1,A2, ,An( B1,B2, ,Bm(E)A1,A2, ,An (E)假设： 1)E是关系代数表达式 2)Ai(i=1，2，n), Bj(j=l，2，m)是属 性名。 3)A1, A2, , An构成Bl，B2，Bm的 子集。4. 选择的串接定律n F1 （ F2（E） F1 F2（E）n选择的串接律说明 选择条件可以合并n这样一次就可检查全部条件。 5. 选择与投影的交换律(1)假设: 选择条件F只涉及属性A1，An F (A1,A2, ,An(E) A1,A2, ,An( F(E)(2)假设: F中
8、有不属于A1, ,An的属性 B1,Bm A1,A2, ,An ( F (E) A1,A2, ,An( F (A1,A2, ,An,B1,B2, ,Bm(E)6. 选择与笛卡儿积的交换律(1)假设：F中涉及的属性都是E1中的属性 F (E1E2) F (E1)E2 (2)假设：F=F1F2，并且F1只涉及E1中的属 性，F2只涉及E2中的属性则由上面的等价变换规则1，4，6可推出： F(E1E2) F1(E1) F2 (E2)(3) 假设： F=F1F2，F1只涉及E1中的属性，F2涉及E1和E2两者的属性 F(E1E2) F2( F1(E1)E2)它使部分选择在笛卡儿积前先做7. 选择与并的
9、分配律n假设：E=E1E2，E1，E2有相同的属性名 F(E1E2) F(E1) F(E2)8. 选择与差运算的分配律假设：E1与E2有相同的属性名 F(E1-E2) F(E1) - F(E2)9. 选择对自然连接的分配律 F(E1 E2) F(E1) F(E2)F只涉及E1和E2的公共属性10. 投影与笛卡儿积的分配律假设：E1和E2是两个关系表达式，A1，An是E1的属性，B1，Bm是E2的属性 A1,A2, ,An,B1,B2, ,Bm （E1E2) A1,A2, ,An（E1) B1,B2, ,Bm(E2)l1. 投影与并的分配律假设：E1和E2 有相同的属性名 A1,A2, ,An(
10、E1E2) A1,A2, ,An(E1) A1,A2, ,An(E2) 2.2 查询优化一般策略(1) 选择运算应尽早执行。 (2) 把投影运算和选择运算同时进行。 (3) 把投影操作与它前面或后面的一个双目运 算结合起来。 (4) 执行连接运算之前进行预处理。 (5) 把笛卡儿积和其后的选择运算合并成为连 接运 (6) 存储公用子表达式。 2.3 关系代数表达式的优化算法算法：关系表达式的优化 输入：一个关系表达式的语法树。 输出：优化的查询树。（1）根据SQL语句生成初始查询树。（2）分解选择运算利用规则4把形如 F1 F2 Fn (E)变换为 F1 ( F2( ( Fn(E) ) （3）
11、交换选择运算n通过交换选择运算，将其尽可能移到叶端.n对每一个选择，利用规则49尽可能把它移到树 的叶端。（4）交换投影运算n通过交换投影运算，将其尽可能移到叶端n对每一个投影利用规则3，5，l0，11中的一般形式 尽可能把它移向树的叶端。 （5）合并串接的选择和投影n以便能同时执行或在一次扫描中完成n利用规则35把选择和投影的串接合并成单个 选择、单个投影或一个选择后跟一个投影。n尽管这种变换似乎违背“投影尽可能早做”的原 则，但这样做效率更高。（6）对内结点分组n把上述得到的语法树的内节点分组。n每一双目运算（， ，）和它所有的直接 祖先为一组（这些直接祖先是 ，运算）。n如果其后代直到叶
12、子全是单目运算，则也将它们 并入该组，但当双目运算是笛卡尔积（），而且 其后的选择不能与它结合为等值连接时除外。把 这些单目运算单独分为一组。 （7）生成执行程序n生成一个程序，每组结点的计算是程序中的 一步。n各步的顺序是任意的，只要保证任何一组的 计算不会在它的后代组之前计算。n【例6.2】 对订单数据库有如下查询，求所有北京 客户所订的全部商品名称。 SELECT pdName FROM Product，Customer，Order，OrderDetail WHERE Product.pdID = OrderDetail.pdID ANDCustomer.custID = Order.c
13、ustID ANDOrder.orderID = OrderDetail.orderID ANDCustomer.custCity = 北京；3 物理优化物理优化n代数优化改变查询语句中操作的次序和组合，不 涉及底层的存取路径n对于一个查询语句有许多存取方案，它们的执行 效率不同， 仅仅进行代数优化是不够的 n物理优化就是要选择高效合理的操作算法或存取 路径，求得优化的查询计划 n选择的方法： n基于规则的启发式优化n基于代价估算的优化n两者结合的优化方法3.1 基于规则的优化方法n选择操作的优化规则 n连接操作的优化规则 对于小关系，使用全表顺序扫描，即使选择列上有 索引。选择操作的优化规则
14、:1. 对于选择条件是主码值的查询n查询结果最多是一个元组，可以选择主码索引n一般的RDBMS会自动建立主码索引。 2. 对于选择条件是非主属性值的查询，并且选择 列上有索引n要估算查询结果的元组数目n如果比例较小( /*条件表达式为真时才被执行*/ ELSE /*条件表达式为假时才被执行*/n循环控制语句的语法格式为： WHILE 条件表达式/*循环体，BEGIN和END定义的语句 块 */ 4. 创建存储过程CREATE PROCEDURE parameter data_type = default AS 5. 执行存储过程【例6.10】执行例6.7中创建的存储过程，要求从 “010038
15、15868”账号转出1000元到“01003813828” 账号：EXEC TRANSFER 01003813828, 01003815868, 1000 ;6. 删除存储过程DROP PROCEDURE 【例6.11】 删除例6.9中创建的存储过程。DROP PROCEDURE TRANSFER;7. 存储过程的优点(1) 存储过程大大增强了SQL语言的功能和灵活性，可以完成 复杂的判断和较复杂的运算。 (2) 通过存储过程可以使没有权限的用户在控制之下间接地存 取数据库，从而保证数据的安全。 (3) 存储过程降低了客户端和服务器之间的通信量。客户端上 的应用程序只要通过网络向服务器发送存储过程的名字和 参数，就可以让系统执行多条SQL语句，并执行数据处理 。只有最终的处理结果才返回客户端。 (4) 方便实施企业规则。可以把体现企业规则的运算程序写成 存储过程放入数据库服务器中，既有利于集中控制，又方 便维护。当企业规则
