【数据库系统】数据库系统概论——第九章 关系查询处理和查询优化

第九章 关系查询处理和查询优化文章目录第九章 关系查询处理和查询优化前言9.1关系数据库系统的查询处理9.1.1查询处理步骤9.1.2实现查询操作的算法示例9.2关系数据库系统的查询优化9.2.1查询优化概述9.2.2一个实例9.3代数优化9.3.1关系代数表达式等价变换规则9.3.2查询树的启发式优化9.4物理优化9.4.1基于启发式规则的存取路径选择优化9.4.2基于代价的优化9.5查询计划的执行9.6小结前言本章首先介绍关系数据库管理系统的查询处理步骤，然后介绍查询的优化。查询优化分类：代数优化：也称逻辑优化，是指关系代数表达式的优化。物理优化：也称非代数优化。是指存取路径和底层操作算法的选择。9.1关系数据库系统的查询处理9.1.1查询处理步骤关系数据库管理系统查询处理分为：查询分析、查询检查、查询优化、查询执行。查询分析对查询语句进行扫描、词法分析和语法分析。词法分析：从查询语句中识别出正确的语言符号。语法分析：进行语法检查。查询检查（1）合法性检查：根据数据字典中有关的模式定义检查语句中的数据库对象，如关系名、属性名是否存在和有效。（2）视图转换：如果是对视图的操作，则要用视图消解方法把对视图的操作转换成对基本表的操作。（3）安全性和完整性初步检查：根据数据字典中的用户权限和完整性约束定义对用户的存取权限进行检查。检查通过后把SQL查询语句转换成内部表示，即等价的关系代数表达式。关系数据库管理系统一般都用查询树，也称为语法分析树来表示扩展的关系代数表达式。查询优化查询优化即选择一个高效执行的查询处理策略。（1）查询优化分类代数优化/逻辑优化：指关系代数表达式的优化，即按照一定的规则，通过对关系表达式进行等价变化，改变关系代数操作的次序和组合，使查询执行更高效。物理优化：指存取路径和底层操作算法的选择。（2）查询优化的选择依据基于规则（rule based）基于代价（cost based）基于语义（semantic based）查询执行依据优化器得到的执行策略生成查询执行计划，由代码生成器生成执行查询计划的代码，然后执行这个查询计划，回送查询结果。9.1.2实现查询操作的算法示例选择操作的典型实现（1）全表扫描方法对查询的基本表顺序扫描，逐一检查每个元组是否满足选择条件，把满足条件的元组作为结果输出。该方法适合小表，不适合大表。（2）索引扫描方法适合于选择条件中的属性上有索引（例如B+树索引或Hash索引），通过索引先找到蛮子条件的元组主码或元组指针，再通过元组指针直接在查询的基本表中找到元组。全表扫描算法思想：假设可以使用的内存为M块。①按照物理次序读Studentd M块到内存；②检查内存的每个元组t，如果满足选择条件，则输出t；③如果Student还有其他块未被处理，重复①和②。连接操作的实现连接操作是查询处理中最耗时的操作之一，本节只讨论等值连接（或自然连接）最常用的实现算法。（1）嵌套循环算法（2）排序-合并算法（3）索引连接算法（4）Hash Join算法第一阶段：划分阶段，也称为创建阶段对包含较少元组的表进行一遍处理，把它的元组按Hash函数分散到Hash表的桶中。第二阶段：试探阶段也称为连接阶段对包含较多元组的表进行一遍处理，把表的元组也按照同一个Hash函数（Hash码是连接属性）进行散列，把元组与桶中来自较少元组的表并与之相匹配的元组连接起来。算法前提：较小的表在第一阶段后可完全放入内存Hash桶中。9.2关系数据库系统的查询优化查询优化在关系数据库系统中有着非常重要的地位。关系查询优化是影响数据库管理系统性能的关键因素。由于关系表达式的语义级别很高，使关系系统可以从关系表达式中分析查询语义，提供了执行查询优化的可能性。9.2.1查询优化概述关系系统的查询优化：是关系数据库管理系统实现的关键技术又是关系系统的优点所在，减轻了用户选择存取路径的负担。用户只要提出“干什么”，不必指出“怎么干”。非关系系统：用户使用过程化的语言表达查询要求，执行何种记录级的操作，以及操作的序列是由用户来决定的。因此，用户必须了解存取路径，系统要提供用户选择存取路径的手段，查询效率由用户的存取策略决定，如果用户做了不当的选择，系统是无法对此加以改进的。查询优化的优点不仅在于用户不必考虑如何最好地表达查询以获得较好的效率，还在于系统可比用户程序的“优化”做得更好。主要原因是：（1）优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息。（2）如果数据库的物理统计信息改变了，系统可自动对查询重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。（3）优化器可以考虑数百种不同的执行计划，程序员一般只能考虑有限的几种可能。（4）优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术。关系数据库管理系统通过某种代价模型计算出各种查询执行策略的执行代价，然后选取代价最小的执行方案。在集中式数据库中，执行代价主要包括：磁盘存取块数（I/O代价）、处理时间（CPU代价）、查询的内存开销，其中I/O代价是最主要的，因为I/O操作涉及机械动作。在分布式数据库中，执行代价主要包括：总代价=I/O代价+CPU代价+内存代价+通信代价说明：因为I/O操作涉及机械动作较耗时，所以在计算查询代价时一般用查询处理读写的块数作为衡量单位。查询优化的总目标是选择有效的策略，求得给定关系表达式的值，使得查询代价最小（实际上是较小）。9.2.2一个实例一个关系查询可以对应不同的执行方案，其效率可能相差非常大。例：求选修了2号课程的学生姓名。 SELECT Student.Sname FROM Student，SC WHEREStudent.Sno=SC.Sno AND SC.Cno=‘2’；假定学生-课程数据库中有1000个学生记录，10000个选课记录选修2号课程的选课记录为50个。可以用多种等价的关系代数表达式来完成这一查询：Q 1 = π S n a m e ( σ S s t u d e n t . S n o = S C . S n o ∧ S C . C n o = ′ 2 ′ ( S t u d e n t × S C ) ) Q_1=\pi_{S_{name}}(\sigma_{S_{student}.Sno=SC.Sno\wedge SC.Cno='2'}(Student×SC))Q1​=πSname​​(σSstudent​.Sno=SC.Sno∧SC.Cno=′2′​(Student×SC))Q 2 = π S n a m e ( σ S C . C n o = ′ 2 ′ ( S t u d e n t ⋈ S C ) ) Q_2=\pi_{S_{name}}(\sigma_{SC.Cno='2'}(Student⋈SC))Q2​=πSname​​(σSC.Cno=′2′​(Student⋈SC))Q 3 = π S n a m e ( S t u d e n t ⋈ σ S C . C n o = ′ 2 ′ ( S C ) ) Q_3=\pi_{Sname}(Student⋈\sigma_{SC.Cno='2'}(SC))Q3​=πSname​(Student⋈σSC.Cno=′2′​(SC))第一种情况Q 1 = π S n a m e ( σ S s t u d e n t . S n o = S C . S n o ∧ S C . C n o = ′ 2 ′ ( S t u d e n t × S C ) ) Q_1=\pi_{S_{name}}(\sigma_{S_{student}.Sno=SC.Sno\wedge SC.Cno='2'}(Student×SC))Q1​=πSname​​(σSstudent​.Sno=SC.Sno∧SC.Cno=′2′​(Student×SC))（1）计算广义笛卡尔积 ①在内存中尽可能多地装入某个表（Student表）的若干块，留出一块 存放另一个表（如SC表）的元组。②把SC中的每个元组和Student中的每个元组连接，连接后的元组装满一块后就写到中间文件上。③从SC中读入一块和内存中的Student元组连接，直到SC表处理完。 ④重复上述处理过程，直到把Student表处理完。设一个块能装10个Student元组或100个SC元组，在内存中存放5块Student元组和1块SC元组，则读取总块数为：1000 10 + 1000 10 × 5 × 10000 100 = 100 + 20 × 100 = 2100 块 \frac{1000}{10}+\frac{1000}{10×5}×\frac{10000}{100}=100+20×100=2100块101000​+10×51000​×10010000​=100+20×100=2100块其中：读Student表100块，读SC表20遍，每遍100块，则总计要读取2100数据块。连接后的元组数为10 3 × 10 4 = 10 7 10^3×10^4=10^7103×104=107。设每块能装10个元组，则写出10 6 10^6106块。 （2）作选择操作依次读入连接后的元组，按照选择条件选取满足要求的记录，假设内存处理时间忽略。读取中间文件花费的时间（同写中间文件一样）需读入10 6 10^6106块。若满足条件的元组仅50个，均可放在内存。（3）作投影操作 把第（2）步的结果在Sname上作投影输出，得到最终结果。第一种情况下执行查询的总读写数据块= 2100 + 10 6 + 10 6 =2100+10^6+10^6=2100+106+106。第二种情况Q 2 = π S n a m e ( σ S C . C n o = ′ 2 ′ ( S t u d e n t ⋈ S C ) ) Q_2=\pi_{S_{name}}(\sigma_{SC.Cno='2'}(Student⋈SC))Q2​=πSname​​(σSC.Cno=′2′​(Student⋈SC))（1）计算自然连接执行自然连接，读取Student和SC表的策略不变，总的读取块数仍为2100块，自然连接的结果比第一种情况大大减少，为10 4 10^4104个元组，写出数据块=10 3 10^3103块。（2）读取中间文件块，执行选择运算，读取的数据块= 10 3 =10^3=103块。 （3）把第（2）步结果投影输出。第二种情况下执行查询的总读写数据块= 2100 + 10 3 + 10 3 =2100+10^3+10^3=2100+103+103，其执行代价大约是第一种情况的1 488 \frac{1}{488}4881​。第三种情况Q 3 = π S n a m e ( S t u d e n t ⋈ σ S C . C n o = ′ 2 ′ ( S C ) ) Q_3=\pi_{Sname}(Student⋈\sigma_{SC.Cno='2'}(SC))Q3​=πSname​(Student⋈