第九讲SQL优化设计

1、数据库系统简介An Introduction to Database System第9章关系查询处理和查询优化，第9章关系系统及其查询优化，9.1关系数据库系统的查询处理9.2关系数据库系统的查询优化9.3代数优化9.4物理优化9.5小注释，9.1关系数据库系统的查询处理，9.1.1查询处理步骤9.1.2实现查询操作的算法示例语法分析和翻译2。优化3 .执行，处理查询阶段(续)，处理查询阶段，1。解析和翻译程序、查询处理器必须对查询语言中的语句进行解析，并将其转换为某种内部表示形式。祖怀语言的语法分析与传统编程语言的语法分析几乎没有区别。语法分析和翻译过程类似于编程语言编译器的语法分析过程。也

2、就是说，使用较高级别的查询语句(如SQL)作为输入，并输出关系代数表达式。2 .查询优化在关系数据库系统中占有非常重要的位置。关系数据库系统和非程序SQL语言取得巨大成功的关键在于查询优化技术的发展。关系查询优化是影响RDBMS性能的关键因素。优化是关系系统的挑战和机会。挑战是，关系系统必须执行查询优化，以获得用户可接受的性能。关系表达式具有较高的语义级别，使关系系统可以在关系表达式中分析查询语义，从而提供执行查询优化的可能性。这为关系系统接近非关系系统或发挥更多性能提供了机会。2 .查询优化程序，查询优化解决的问题：1，每个SQL语句可以转换为多个等价关系代数表达式。替代关系代数表达式是什么

3、？2，每个关系代数表达式的关系运算可以用不同的算法实现，可以使用不同的索引。具体使用什么算法和什么索引？3、整体表达式评估是使用管道计算方法，还是使用实体化计算方法？还是使用两种混合计算方法？2 .查询优化程序，1，问题中的呈现查询SQL语句可以用多种方式表示，每个SQL语句可以转换为多个等价关系代数表达式。例如，select balance from account where balance 2500可以转换为两个关系代数表达式，其中每个表达式的关系运算可以用另一个算法和索引实现。因此，查询优化程序的任务是找到上述表达式中成本最低的指定查询的处理进程。2 .查询优化程序、2、执行计划查询优

4、化程序使用关系代数表达式作为输入来输出查询执行计划。什么是查询执行计划？2 .查询优化程序，2，执行计划不仅提供关系代数表达式，还计算查询。这些注释用于说明如何具体实现每个任务。例如，可以描述用于关系运算的算法或要使用的一个或多个特定索引。添加了有关如何执行的注释的这种关系代数运算称为执行原语，用于计算一个查询的基元序列称为查询执行计划或查询计算计划。查询优化是为给定查询选择最有效的查询执行计划的过程，它包括两个方面：也就是说，它在关系代数级别进行了优化，执行此操作的目的是找到与给定关系代数表达式相同，但更有效的表达式。查询语句处理的详细策略的选择。例如，确定用于执行运算的特定算法和要使用的特

5、定索引等。2 .查询优化程序，2，执行计划，2。优化程序必须估计每个查询执行计划的成本，以便查询优化程序、3、查询优化程序可以从许多查询执行计划中进行选择。这使用了关系的统计数据。如何估计查询执行计划的成本？3 .执行引擎查询执行引擎允许的输入是查询执行计划，结果是特定查询结果的引擎。，3 .所有数据库系统都运行不完全遵循这些步骤的引擎。大多数数据库系统不使用关系代数表达式来表示查询。相反，执行引擎查询执行引擎允许的输入是查询执行计划，输出是特定查询结果的注释语法分析树基于给定的SQL查询结构。9.1关系数据库系统中的查询处理，9.1.1查询处理步骤实现9.1.2查询操作的算法示例，实现9.1

6、.2查询操作的算法示例，第一，选择操作的实现2，连接操作的实现，第一，选择操作的实现，示例1 select * from student where需要考虑的一些情况：C1:无条件；C2:SnO 200215121；C3:sage 20；C4:sdept cs and sage 20；以选择实施作业(继续)，然后选择实施一般作业的方法。1.简单全表扫描方法在查询的基础表顺序扫描中，单独确定每个元组是否满足选择条件，将满足条件的元组与结果输出匹配到较小的表。不适合大桌子2。索引(或散列)扫描方法首先通过选择条件的属性具有索引(例如b树索引或散列索引)的索引查找符合条件的元组主指针或元组指针，然后

7、通过元组指针直接在查询的基表中查找元组，选择操作的实现(续)；示例1-C2中为C2，Sno200215121，然后在b树的顺序集中，作为起点，sag20的所有元组指针将通过此元组指针在student表中搜索所有大于20的学生。选择作业实现(续)，示例1-C4，SdeptCS AND Sage20，Sdept和Sage都有索引：分别查找算法1: SdeptCS的一组元组指针和sag20的另一组元组指针。查找从这两组指针的交集到学生表的计算机系统年龄大于20的学生搜索算法2: student表的sdepts的元组指针集。通过此元组指针，确保其他选择条件(如sag20)将满足条件的元组输出到结果，以

8、获取到student表的结果元组结果。第二，连接操作的实现，这是查询处理中最耗时的任务之一，在本节中，对等连接(或自然连接)最常用的实现算法示例2 SELECT * FROM Student，SC WHERE Student。Sno=SC。Sno；实施连接操作(续)，1 .巢状回圈方法2。(nested loop method)。排序-合并方法(sort-merge join或merge join) 3。索引联合方法4。Hash Join方法、连接操作的实现(续)、嵌套循环方法(nested loop)通过为外部循环(Student)中的每个元组(s)检索内部循环(sc)中的每个元组(SC)来

9、实现这两个元组如果满足连接条件，线程将输出到结果，直到处理了外部循环表的元组(续)，2。排序-如果已排序连接的表(sort-merge join或merge join)，则排序合并连接方法的步骤：如果已连接的表未排序，则首先按连接属性Sno对Student表和SC表排序，然后扫描SC表中具有相同Sno的元组。实施连接操作(继续)、实施连接操作(继续)、排列连接方法(继续):当Sno扫描另一个SC元组时，返回到Student表，扫描下一个元组，然后扫描SC表中具有相同Sno的元组，重复以上步骤，直到Student表扫描完成(继续)、实施连接操作索引联接方法步骤：在SC表中为属性Sno创建索引，如

10、果原始Student中的每个元组没有索引，则Sno值将通过SC的索引查找相应的SC元组，然后循环浏览相应的SC元组和Student元组，直到处理了Student表中的元组，从而实现连接操作(续)，4 .Hash Join方法将连接属性用作Hash代码。将r和s的元组以相同散列函数散列到相同散列文件的步骤：拆分步骤：包含较少元组的表的迭代处理hash函数，散列表的桶导航步骤(probing phase):又处理另一个表(s)(也称为组合步骤)时，s的元组会散列到相应的hash桶中。其中，hash join算法的工作方式是连接与r中的所有元组匹配的元组，假设两个表中的较小表在第一步之后可以完全放在

11、内存中hash桶的上面。第九章关系系统和查询优化，9.1关系数据库系统的查询处理9.2关系数据库系统的查询优化9.3代关系数据库系统的查询优化9.4对象优化9.5小节点，9.2关系数据库系统的查询优化，查询优化在关系数据库系统中提供了非常重要的状态关系查询优化，这是影响RDBMS性能的关键因素。关系系统允许分析关系表达式中的查询语义，从而提供了执行查询优化的可能性。查询优化概览(续)，查询优化的优点在于，用户不必考虑如何最好地表示查询以获得更好的效率，如果系统比用户程序的优化更好，(1)优化程序可以从数据字典中获取很多统计信息，但是用户程序很难获取这些信息，(2)数据库的物理统计信息发生变化时

12、，可以自动重新调整查询，选择合适的执行计划。在郑智薰关系系统中，程序需要重写，而重写程序在实际应用程序中的可能性往往很小。查询优化概述(续)，(3)优化程序可以考虑数百种不同的执行计划，程序员通常只能考虑一些可能性。(4)优化程序往往包含很多复杂的优化技术，只有最好的程序员才能掌握。系统的自动优化相当于让每个人都查看查询优化概览(继续)，RDBMS通过某种成本模型计算各种查询执行策略的执行成本。然后选择最低成本的执行方案中央数据库执行开销主要是磁盘访问块数(I/O成本)处理器时间(CPU成本)查询的内存开销I/O成本最重要的分布式数据库的总成本=I/O成本CPU成本内存成本通信成本、查询优化概

13、览(续)、查询优化的总目标：通过选择有效策略给出的关系用SQL表示：SELECT Student。Sname FROM Student，sc where Student . SnO=sc . SnO and sc . cno=2；学生-假定学科课程数据库中有1，000个学生记录，1，000个选项记录中选项2的选项记录为50个(续)，Q1=sname(student . SnO=sc . snosc . cn o=2(student sc)计算广泛的笛卡尔乘积如何连接student和sc的每个元组。从内存中加载一个表(如student表)的多个块，并保留另一个表(如sc表)的一个元组。在处理SC

14、表之前，将SC中的每个元组和Student中的每个元组连接填充一片，然后从SC中读取一片和内存中的Student元组连接。在处理Student表之前，读取多个Student元组；一个实例(续)、一个块可以包含10个Student元组或100个SC元组；读取SC元组直到内存包含5个Student元组和1个SC元组，因此总块数为=100 20100=2100块其中读取Student表100块。读20次SC表，每次读100个。每秒读取和写入20块时，使用连接到105s的元组数，直到10304=107。每个设置可以安装10个元组，106/20=5104s，读取表，写入文件，实例(续)，2。为选择操作依

15、次读取相关联的元组，根据选择条件，假定满足要求的记录选择会忽略内存处理时间。读取中间文件所用的时间(相当于写入中间文件)假定5104s只有50个元组符合条件，一个实例(继续)，3 .投影操作将步骤2中的结果投影到Sname，在最终结果第一种情况下运行查询所用的总时间105 25104105s所有内存处理时间都将被忽略，无论一个实例是什么。第二，在第二种情况下，Q2=Sname(Sc .cno=2(Student SC)1。计算自然连接、执行自然连接和读取Student和SC表的策略保持不变，使用105 s自然连接(总读取块数仍为2100块)的结果比第一种情况明显减少。写入这些元组中的104个时，使用104/10/20=50s，第一个时的千分之一2。读取中间文件块和执行选择操作所需的时间为50s。将步骤2的结果投影到输出。第二个方案的总运行时间105 50 505050505005s，一个实例(续)，第三个，第三个方案的Q