查询优化技术ppt课件.ppt

第七章查询优化技术 查询处理器是数据库管理系统DBMS的一个部件 它把用户的查询命令转换成对数据库的一连串操作 鉴于用查询语言SQL表达查询是在较高的层次上 查询处理器必须提供如何进行查询的诸多细节 1 设S是一个存储有关学生信息的关系 包括学号S 和姓名SN等属性 SC是存储学生选课情况的关系 包括学号S 和课程号C 等属性 下边的SQL语句表示查询 列出所有选修课程C2的学生姓名 SELECTDISTINCTS SNFROMS SCWHERES S SC S ANDSC C C2 查询优化例 2 假定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 三种查询处理策略 3 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中元组全部处理完 4 设BS能装50个S的元组 BSC能装100个SC的元组 每个磁盘块能装10个S的元组或100个SC的元组 上述算法需要读关系S的100个磁盘块数据 需要20遍读SC关系 每遍读100个磁盘块 读取总块数为 2100 若每秒可读20个磁盘块 则总计要花105秒 S和SC的笛卡尔积的结果元组数为10000000 设每个磁盘块能装5个结果元组 则结果元组的写出要花费100000秒 设每秒写20块 5 2 从临时文件读入S和SC的笛卡尔积 按照选择条件选取满足要求的记录 这一步读取中间文件花费的时间为100000秒 同写中间文件一样 3 把第2步的结果在SN上作投影输出 得到最终结果 设满足条件的元组数为50 可存放在内存中 忽略CPU时间 Q1需要的处理时间大于200105秒 6 Q2的处理过程和时间开销分析 1 计算自然连接 为了执行自然连接 读取S和SC表的策略不变 总的读取块数仍为2100块 需要105秒的时间 但自然连接的结果大大减少 为l000个元组 因此写出这些元组花费的时间为l0秒 2 读取中间文件块 执行选择运算 花费时间也为10秒 3 把第2步结果投影输出 如果忽略CPU时间 Q2的处理时间约为125秒 7 Q3的处理过程和时间开销分析 1 先对SC作选择运算 只需读一遍SC表 存取100块花费时间为5秒 因为满足条件的元组仅50个 不必使用中间文件 2 读取S表 把读入的S元组和内存中的SC元组作连接 这一步只需读一遍S 共100块 需要5秒钟的时间 3 把连接结果投影输出 忽略CPU时间 Q3的处理时间约为10秒 8 本章的开始部分 将考察用于改善逻辑查询方案的各种代数法则 并考察每一种关系代数算符的可能算法 将一个逻辑查询方案转换为一个物理查询方案 不仅要定义出所用的算子 还要给出如何实现算子及如何将数据传给另一算子的方法 本章主要内容 9 关系代数传统的关系代数假设关系是在集合的基础上设计出来的 而SQL中的关系实际上是包 bag 或称多重集 也就是说 SQL关系中可以存在任意个重复元组 因此 我们将引入一种包上的关系代数 10 并 交 差在R S中 元组t在运算结果中出现的次数 等于在R中出现的次数与S中出现的次数之和 在R S中 元组t在运算结果中出现次数 是R中出现次数与S中出现次数的较小者 在R S中 元组t在运算结果中出现次数 等于R中出现次数减去S中出现次数之差 但不少于零它们对应着SQL中的UNION INTERSECT和EXCEPT运算 11 选择运算假设R是一个关系 C是条件 则 C R 表示对关系R进行选择运算 它是R中符合条件C的元组的包 运算结果的域与R的域相同 运算 被称为关系代数的选择运算 12 投影运算若R是一个关系 则 L R 为R在投影属性表L上的投影 将扩充这一运算 使之模拟SQL的SELECT子句 允许属性的重命名 用 来指示重命名 例如 L中的成员x y表示取R的x属性列并重新命名为y 允许表L中包括属性的算术或条件运算 若L的成员不是单个的属性 则必须由箭号和属性来命名表达式的结果 13 14 笛卡尔乘积运算 若R和S是关系 则R S也是关系 其结果关系的域来自于R的域加上S的域 若某一个属性 如a 在两个关系中都有 则在结果域中用R a和S a作为这两个属性的名字 结果关系的元组都是由从R中取一个元组且在这一元组的分量后接S的任一元组的分量而形成的 若一元组r在R中出现n次 另一元组s在S中出现m次 则元组rs在结果中出现nm次 15 16 17 连接运算最简单的连接是自然连接 我们用R S来表示R和S的自然连接 自然连接可分解为 L C R S 其中 C是使R和S中所有同名的属性对相等的条件 L是R和S的所有属性的列表 只是每一对相等的属性中去掉一个 若R x和S x是相等的属性 则因为在投影的结果中只有一个属性x 任取R x和S x之一 并重新命名为x 18 用于改善查询方案的代数定律关系代数表达式可以用树结构来表示 在不改变查询结果的前提下 将这棵树进行变换 以达到降低查询的时间和空间复杂性的目的 这一工作称为关系代数优化 这一工作是在较高的抽象层次上即逻辑数据结构层上进行的 19 查询的符号表示形式 查询树 查询树是一种表示关系代数表达式的树形结构 在一个查询树中 叶子节点表示关系 内部节点表示关系代数操作 查询树以自底向上的方式执行 当一个内部节点的操作分量有值时 这个内部节点所表示的操作开始启动执行 执行结束后用结果关系代替这个内部节点 20 给定一个用SQL语言定义的查询 SELECTlistFROMR1 R2 RnWHEREC其中 C是条件表达式 list是输出属性表 可以按照如下方法把这个查询转换为关系代数表达式 1 使用FROM从句中的关系R1 R2 Rn构造笛卡尔乘积R1 R2 Rn 2 在第1步的基础上构造一个选择操作 C R1 R2 Rn 在第2步的基础上构造一个投影操作 list C R1 R2 Rn 21 假设有关系MovieStar name addr gender birthdate StarsIn title year starName 从中我们要查找出那些在1996年的影片中出现的女演员的出生日期和影片名 SELECTtitle birthdateFROMMovieStar StarsInWHEREyear 1996ANDgender F ANDstarName name 22 23 等价的表达方式 下图中所用的方案与上图明显不同 第一 应用于两个关系的乘积上的WHERE子句中的条件starName name是一个等值连接 一般地 连接运算产生的元组比乘积运算产生的结果元组要少 因此 如有可能 尽量使用连接运算 第二 WHERE子句的其他两个条件被分成了两个 运算 并且两个 运算都被顺着树往下移 其中 因为选择运算 year 1996只涉及到StarsIn的一个属性year 所以 它可直接应用到关系StarsIn之上 24 25 的两个分离规则 C1ANDC2 R C1 C2 R C1ORC2 R C1 R C2 R 注意 和 的次序是灵活的 例如 我们也可以把上面的第一个规则写成 在 之后进行操作 即 C2 C1 R 实际上 运算符的次序可任意交换 C1 C2 R C2 C1 R 优化查询过程的一个最重要的思想 是不改变表达式的作用而尽量将选择操作顺着查询树往下移 26 例给出关系R a b S b c 和表达式 a 1ORa 3 ANDb c R S 条件b c可单独应用于S 条件a 1ORa 3可单独应用于R 因此 从分解这两个条件的AND开始 得 a 1ORa 3 b c R S 接着 可以将选择 b c下移至S 得到表达式 a 1ORa 3 R b c S 最后 将第一个条件移至R 生成 a 1ORa 3 R b c S 27 设有关系MovieStar name addr gender birthdate StarsIn title year starName 并且想知道对每一年出现在该年影片中的最年轻演员的生日 我们可以把这一查询表达为 SELECTyear MAX birthdate FROMMovieStar StarsInWHEREname starNameGROUPBYyear 28 直接由这