查询优化技术.pptVIP

* 第七章 查询优化技术 查询处理器是数据库管理系统DBMS的一个部件，它把用户的查询命令转换成对数据库的一连串操作。鉴于用查询语言SQL表达查询是在较高的层次上，查询处理器必须提供如何进行查询的诸多细节。 设S是一个存储有关学生信息的关系，包括学号S#和姓名SN等属性。SC是存储学生选课情况的关系，包括学号S#和课程号C#等属性。下边的SQL语句表示查询“列出所有选修课程C2的学生姓名”： SELECT DISTINCT S.SN FROM S, SC WHERE S.S#＝SC.S# AND SC.C#＝“C2”。 查询优化例 假定S中包含1000个学生记录，SC中包含10000个选课记录，其中选修C2课程的选课记录为50个。 我们用三个等价的关系代数表达式来表示这个查询的三种处理策略： Q1=∏SN(σ(s.s#＝sc.s#) ∧(sc.c#=”c2”)(s×sc))； Q2＝∏SN(σ(sc.c#＝”c2”) (s ?s.s#=sc.s# sc))； Q3＝∏SN(σsc.c#＝”c2”sc ?s.s#=sc.s# s) 三种查询处理策略 Q1=∏SN(σ(s.s#＝sc.s#) ∧(sc.c#=”c2”)(s×sc) 执行过程和时间开销分析 (1)计算S和SC的笛卡尔积。 步骤1，使用一个内存缓冲区BS读入某个关系(如S)的未处理元组； 步骤2，使用另一个内存缓冲区BSC读入另一个关系(如SC)的未处理元组； 步骤3，把BS中的每个元组和BSC中每个元组相连接，并送人输出缓冲区BO； 步骤4，如果BO已满则写到一个临时文件； 步骤5，重复步骤②～④，直至SC中元组全部处理完； 步骤6，重复步骤①～⑤，直至S中元组全部处理完。 设BS能装50个S的元组，BSC能装100个SC的元组，每个磁盘块能装10个S的元组或100个SC的元组。上述算法需要读关系S的100个磁盘块数据，需要20遍读SC关系，每遍读100个磁盘块，读取总块数为：2100。 若每秒可读20个磁盘块，则总计要花105秒。 S和SC的笛卡尔积的结果元组数设每个磁盘块能装5个结果元组，则结果元组的写出要花费100000秒(设每秒写20块)。 (2)从临时文件读入S和SC的笛卡尔积，按照选择条件选取满足要求的记录。这一步读取中间文件花费的时间为100000秒(同写中间文件一样)。 (3)把第2步的结果在SN上作投影输出，得到最终结果。设满足条件的元组数为50，可存放在内存中。 忽略CPU时间，Q1需要的处理时间大于200105秒。 Q2的处理过程和时间开销分析 (1)计算自然连接。为了执行自然连接，读取S和SC表的策略不变，总的读取块数仍为2100块，需要105秒的时间。但自然连接的结果大大减少，为l000个元组。因此写出这些元组花费的时间为l0秒。 (2)读取中间文件块，执行选择运算，花费时间也为10秒。 (3)把第2步结果投影输出。 如果忽略CPU时间，Q2的处理时间约为125秒。 Q3的处理过程和时间开销分析 (1)先对SC作选择运算，只需读一遍SC表，存取100块花费时间为5秒。因为满足条件的元组仅50个，不必使用中间文件。 (2)读取S表，把读入的S元组和内存中的SC元组作连接。这一步只需读一遍S，共100块，需要5秒钟的时间。 (3)把连接结果投影输出。 忽略CPU时间，Q3的处理时间约为10秒。 本章的开始部分，将考察用于改善逻辑查询方案的各种代数法则。并考察每一种关系代数算符的可能算法。将一个逻辑查询方案转换为一个物理查询方案，不仅要定义出所用的算子，还要给出如何实现算子及如何将数据传给另一算子的方法。 本章主要内容 关系代数 传统的关系代数假设关系是在集合的基础上设计出来的，而SQL中的关系实际上是包(bag)，或称多重集。也就是说， SQL关系中可以存在任意个重复元组。因此，我们将引入一种包上的关系代数。 并，交，差 在R∪S中，元组t 在运算结果中出现的次数，等于在R中出现的次数与S中出现的次数之和。 在R∩S中，元组t 在运算结果中出现次数，是R中出现次数与S中出现次数的较小者。 在R-S中，元组t 在运算结果中出现次数，等于R中出现次数减去S中出现次