查询优化实例（8）
• （2）计算Q2的查询时间 • ●计算自然连接：计算自然连接时读取S与SC表
的方式与Q1一致，总读取块数为2100块，花费时 间为10 5秒，但其连接结果块数大为减少，总计 104个，所花时间为104/10/20s=50s。仅为Q1的 千分之一。 • ●作选择操作：做选择操作的时间为50s。 • ●做投影操作：与Q1类似，其时间可忽略不计 • 这样，Q2的全部查询时间≈ 105+50+50= 205s
查询优化实例（5）
• 其中读S表100块，读SC表20次，每次100 块 。 由 于 每 块 花 费 时 间 1/20 秒 ， 此 时 总 共 花费时间105秒。
• 连接后的元组数为103×104=107，设每块 （约）能装10个元组，则写入中间文件要 花106/20=5×104s。
第4章 关系数据查询优化： 4.1 查询处理与优化
第4章 关系数据查询优化： 4.1 查询处理与优化
查询优化实例（10）
• 从这3个计算时间可以看出，3种等价的查 询表达式具有完全不同的处理时间，它们 分别是10 5s、205s和10s，其差距之大令 人瞠目。
第4章 关系数据查询优化： 4.2 查询优化技术 4.2查询优化技术 4.2.1手动优化与自动优化
存放SC元组。 • ● 读/写一块磁盘的时间为1/20秒，即1秒读写20个磁盘
块。 • ● 为了简化起见，所有内存操作所花的时间忽略不计。
第4章 关系数据查询优化： 4.1 查询处理与优化
查询化实例（4）
• （1）计算Q1的查询时间 • ① 首先做笛卡尔乘积 • 将S与SC的每个元组相连接，其方法为先读入S中的50个
元组（5*10）至s表中的内存缓冲区，然后不断地将SC的 元组按100位一块读入后与S的元组相连接，直至读完所 有SC元组（共计100次）。这种操作内连接满100位后就 写中间文件一次。反复进行这样的操作，直至做完笛卡尔 乘积，此时读取的总块数为 • = 100+20×100=2100块
第4章 关系数据查询优化： 4.1 查询处理与优化
第4章 关系数据查询优化： 4.1 查询处理与优化
查询优化实例（3）
• 作如下的统一约定： • ● 设S有1000个元组，SC有10000个元组，其中修读C5
的元组数为50。 • ● 磁盘中每个物理块能存放10个S元组，或100个SC元组。 • ● 内存有6个块的缓冲区，其中5块可以存放S元组，1块
第4章 关系数据查询优化： 4.1 查询处理与优化
查询优化概念
• 一般而言，相同查询要求和结果存在不同 实现策略，系统执行这些查询策略的开销 通常有很大差别。对于一个数据库系统来 说，查询处理过程都必须面对如何从查询 的多个执行策略中进行“合理”选择的问 题，这种“择优”的过程就是“查询处理 过程中的优化”，简称为查询优化。
第4章 关系数据查询优化： 4.1 查询处理与优化
4.2.2 查询优化器（1）
• 自动进行查询优化应当是DBMS的关键技 术。由DBMS自动生成若干候选查询计划 并且从中选取较“优”的查询计划的软件 程序称谓查询优化器。
第4章 关系数据查询优化： 4.2 查询处理与优化
4.2.2 查询优化器（2）
第4章 关系数据查询优化： 4.1 查询处理与优化
查询优化实例（2）
• 考虑查询语句对应的三种代数表达式： • Q1 =∏Sn（σS.S# =SC。S#SC.C# =‘C5’
（S×SC））； • Q2 =∏Sn（σSC.C# =‘C5’（SSC））； • Q3 =∏Sn（SσSC.C# =‘C5’（SC））。
• 1.查询优化器所使用的技术可分三类. • ① 规则优化技术 如果查询仅仅涉及查询语句本身，根据
某些启发式规则，例如“先选择、投影和后连接”等就可 完成的优化。其特点是对相应关系代数表达式进行等价变 换，以减少执行开销，也称为代数优化。 • ② 物理优化技术 如果优化与数据物理组织和访问路径有 关，需要对如何选择实现策略进行必要考虑。 • ③ 代价估算优化技术 对于多个候选策略逐个进行执行代 价估算，从中选择代价最小的作为执行策略。
数据库系统基础教程
第4章 关系数据库查询优化
第4章 关系数据查询优化： 4.1 查询处理与优化
4.1 查询处理与优化 关系数据查询过程
查询要求 相关数据统计信息
数据库
查询结果
DML 处理器
查询转换为内部格式
关系代数语法树
查询优化器
制定执行策略
查询计划
代码生成器
生成执行代码
执行代码
运行处理器
执行查询代码
• ③ 最后做投影操作 • 第二项操作的结果满足条件的元组数为50个，它
们可全部存放在内存。对他们在S上做投影操作， 由于是在内存中进行，其时间可忽略不计。这样 Q1的全部查询时间约为105+2×5×104 ≈ 105s。 注意到一天为86400s，所以这个运算需要超过一 天的时间来完成。
第4章 关系数据查询优化： 4.1 查询处理与优化
查询优化实例（6）
• ② 其次做选择操作 • 从中间文件中读出连接后的元组，按选择
要求选取纪录（此项为内存操作，时间可 忽略不计），此项操作所需时间与写入中 间文件时间一样，即5×104s。满足条件的 元组假设为 50个，均放在内存。
第4章 关系数据查询优化： 4.1 查询处理与优化
查询优化实例（7）
第4章 关系数据查询优化： 4.1 查询处理与优化
查询优化实例（9）
• （3）计算Q3的查询时间 • ●对SC做选择操作：对SC表作选择操作需读SC
表一遍共计读100块，花费5s结果为50个元组故 不需要使用中间文件。 • ●做连接运算：对S选择后的SC左联接运算，由 于选择后的SC已全部在内存，因此全部操作时间 为S读入内存的时间共100块，花费时间为5秒。 • ●作投影运算：其时间忽略不计。 • 这样，Q3的全部查询时间≈ 5+5=10s
第4章 关系数据查询优化： 4.1 查询处理与优化
查询优化实例（1）
• 设有关系S，C，SC，查询修读课程号为 C5的所有学生姓名。
• 对应于此查询的SQL查询语言的语句为： • SELECT S.Sn • FROM S,SC • WHERE S.Sn=SC.Sn AND SC.C# = ＇
C5＇；