查询树的优化.ppt

第四章查询优化 4 1关系数据库系统的查询处理 查询处理步骤 Selectstudent namefromstudent scWherestudent sno o 2 例 选修了2号课程的学生姓名 4 1关系数据库系统的查询处理 Selectstudent namefromstudent scWherestudent sno o 2 1 查询分析 识别其中的关键字 属性名 表名 2 查询检查 属性名是否有效 表名是否有效等 3 查询优化 例如上例中先执行连接还是先执行o 2从sc表中进行选择 选用何种方法进行连接 4 查询执行 4 1关系数据库系统的查询处理 查询处理步骤查询分析 对查询语句进行扫描 词法分析和语法分析 查询检查 语义检查查询优化 代数优化和物理优化查询执行 4 1关系数据库系统的查询处理 为什么进行代数优化 例 选修了2号课程的学生姓名 sname student sno sc sno o 2 SC Student 4 1关系数据库系统的查询处理 sname student sno sc sno o 2 SC Student 假设有1000个学生记录 10000个选课记录 2号课程的选课记录为500个 1 笛卡尔积计算 1000 100002 选择 扫描1000 10000个记录3 投影 4 1关系数据库系统的查询处理 假设有1000个学生记录 10000个选课记录 2号课程的选课记录为500个 1 连接 采用嵌套循环 10000 1000 得到10000个结果2 选择 扫描10000个记录3 投影 4 1关系数据库系统的查询处理 假设有1000个学生记录 10000个选课记录 2号课程的选课记录为500个 1 选择 扫描10000个记录 得到500个记录2 连接 采用嵌套循环 500 1000次 得到500个记录3 投影 选择操作先做可以提高效率 4 2代数优化 4 2 1关系代数表达式等价变换规则 等价的概念 若关系表达式f E1 E2 En 的结果与关系表达式g E1 E2 En 的结果是同一个关系 那么称这两个表达式等价 若关系表达式E1和E2是等价的可以记为 等价变换规则 1 连接 笛卡儿积交换率设E1和E2是关系代数表达式 F是连接运算的条件 则有 等价变换规则 1 连接 笛卡儿积的结合率设E1 E2 E3是关系代数表达式 F1和F2是连接运算的条件 则有 等价变换规则 2 连接 笛卡儿积的结合率设E1 E2 E3是关系代数表达式 F1和F2是连接运算的条件 则有 3 投影的串接定律 这里 E是关系代数表达式 Ai i 1 2 n Bj j 1 2 m 是属性名且 A1 A2 An 是 B1 B2 Bm 的子集 等价变换规则 4 选择的串接定律 等价变换规则 求IS系年龄大于 岁的学生 4 选择的串接定律 E是关系代数表达式 F1和F2是选择条件 选择的串接定律说明选择条件可以合并 这样一次就可以检查全部的条件 等价变换规则 等价变换规则 5 选择与投影的交换律 此时 条件F只涉及属性组A 若条件中有不属于A的属性组B 那么有更一般的规则 等价变换规则 6 选择与笛卡尔积的交换 1 F只涉及E1的属性 2 F F1 F2 且F1只涉及E1的属性 F2只涉及E2的属性 3 F F1 F2 且F1只涉及E1的属性 而F2涉及E1和E2的属性 1 实例 选修1号课程的学生信息 等价变换规则 2 实例 信息系选修1号课程的学生信息 7 选择与并的分配率 设E E1 E2 E1和E2有相同的属性名 则 注 先做选择可以减少读取写入的数据 因此减少磁盘IO量 从而提高了效率 等价变换规则 设S1是计科041的学生关系表 S2是计科042的学生关系表 等价变换规则 8 选择与差运算的分配率 设E1和E2有相同的属性名 则 注 先做选择可以减少读取写入的数据 因此减少磁盘IO量 从而提高了效率 等价变换规则 设S1是计科041的学生关系表 S3是计科专业的学生关系表 等价变换规则 9 选择对自然连接的分配率 F只涉及E1和E2的公共属性 注 先做选择可以减少做笛卡儿积的数据 结果关系的数据量也同步减少 因此减少磁盘IO量 提高了效率 等价变换规则 等价变换规则 10 投影与笛卡尔积的分配律 设E1和E2是两个关系表达式 A是E1的属性组 B是E2的属性组 则 注 先做投影可以减少读取写入的数据 因此减少磁盘IO量 从而提高了效率 等价变换规则 查找所有学生可能的选课对 等价变换规则 11 投影与并的分配律 设E1和E2有相同的属性名 则 注 先做投影可以减少读取写入的数据 因此减少磁盘IO量 从而提高了效率 等价变换规则 设S1是计科041的学生关系表 S2是计科042的学生关系表 查找计科041 042的学生姓名 等价变换规则 优化规则 选择运算尽可能先做 投影运算和选择运算同时进行 把投影运算同其前后的双目运算结合执行 选择运算和笛卡儿积运算结合成连接运算 找出公共子表达式 避免重复运算 4 2 2查询树的优化 4 2代数优化 1 查询树 S C SC 4 2 2优化算法 1 利用规则4分解选择运算 2 利用规则4 9把选择运算尽量移到叶端 3 利用规则3 5 10 11把投影运算尽量移到叶端 4 利用规则3 5把选择和投影的串接合并成单个选择 单个投影或一个选择后跟一个投影的形式 使尽可能多的选择和投影同时执行 5 分组 双目运算和他的直系祖先为一组 双目运算后代直道叶子全是单目运算时并入改组 笛卡儿积的后面若不是与之可以合并的自然连接的等值选择时 其后代单独分为一组 优化实例 例 查询至少选修了一门先行课号为5号课程的学生姓名 其中 C是课程表 S是学生表 SC是学生选课表 在优化规则中没有对自然连接的直接优化 我们把自然连接分解为笛卡儿积和选择 分解后的关系代数表达式 S C SC 第一步 利用规则4分解选择运算 S C SC 第二步 尽量下放选择运算 S C SC S C SC 第二步 2 下放完成后 第三步 尽量下放投影运算 S C SC E 第三步 尽量下放投影运算 S C SC