数据库查询过程和优化

数据库查询过程

(1)查询分析(词法分析、语法分析)：使用(Lex、)生成查询语句对应的查询树。

(2)查询优化:用户只负责提出查询需求(要查什么)，而如何进行查询以减少系统开销，则是数据库查询优化器(optimizer)和查询执行器(plan)完成的工作。

   (A)代数优化:关系代数表达式的优化

   (B)物理优化:存取路径和底层操作算法的选择(比如建立数据索引)

(3)查询执行:依据优化器得到的执行策略生成查询计划,代码生成器(code generator)生成执行查询计划的代码

查询代价定义:RDBMS通过某种代价模型计算出各种查询执行策略的执行代价，然后选取代价最小的执行方案

查询执行方案的代价

      集中式数据库:总代价 = I/O代价 + CPU代价 + 内存代价

      分布式数据库:总代价 = I/O代价 + CPU代价  + 内存代价 + 通信代价

代数优化:通过对关系代数表达式的等价变换来提高查询效率

     1. 选择运算应尽可能先做。在优化策略中这是最重要、最基本的一条

  2. 把投影运算和选择运算同时进行.如有若干投影和选择运算，并且它们都对同一个关系操作，则可以在扫描此关系的同时完成所有的这些运算以避免重复扫描关系。

     3. 把投影同其前或其后的双目运算结合起来

  4. 把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接

    s_{Studnet.Sno=SC.Sno} (Studnet×SC)=======>Studnet ∞ SC

     5. 找出公共子表达式.如果这种重复出现的子表达式的结果不是很大的关系并且从外存中读入这个关系比计算该子表达式的时间少得多，则先计算一次公共子表达式并把结果写入中间文件是合算的

例子：找出选择课程名称为：'数据结构'的学生的姓名和所在院系

SELECT sname,sdept FROM s, c, s

    WHERE s.sno= sc.sno

                 AND c.cno=sc.cno

                 AND cname='数据结构' ;

代数优化过程如下图所示：

求选修2号课程的学生姓名

SELECT sname FROM Student inner join SC on Student.SNO=SC.SNO where SC.CNO=‘2’

假设1：

• Student: 1000条；SC: 10000条
• 选修2号课程:  50条

假设2：连接方法：基于数据块的嵌套循环法

• 在内存中尽可能多地装入Student表的若干块元组，留出一块(A块)存放SC表的元组。
• 然后从SC表读一块元组装入A块
• 然后把A块中的SC元组与内存中的Student元组连接，连接完后写入到中间文件。
• 再从SC表读一块元组装入A块，与内存中的Student元组连接，连接完后写入到中间文件。
• 重复读SC表，直到SC表处理完。
• 再一次读入Student表的其他若干块元组，重复上述过程，直到Student表处理完。

假设3：

• 内存中一次可以同时存放: 5块Student元组，1块SC元组和若干块连接结果元组
• 一个内存块装元组：10个Student元组，或100个SC元组，或10个连接后的元组

假设4：

• 读写速度：20块/秒

下面分析三种关系表达式下的查询代价：

 

关系代数表达式一:

• p_Sname(s_{Studnet.Sno=SC.Sno Ù SC.Cno=’2’}(Studnet×SC)

① Student×SC

   第一遍: 读5块Student，按块读SC读100块。

• 读取块数：5 + 100
• 要处理20遍
• 读取总块数：20×( 5+100 ) = 2100
• 读数据时间：2100/20=105秒
• 中间结果大小：1000*10000 = 10⁷
• 写中间结果时间 10⁷/10/20 = 50000秒 

② б读数据时间 = 50000秒.  结果50个元组。

③ П：时间忽略。

总时间：105＋50000＋50000秒 = 100105秒 = 27.8小时

关系代数表达式二:

• p_Sname(s_{SC.Cno=’2’}(Student∞SC))

① Student∞SC

• 第一遍: 读5块Student，按块读SC读100块。
• 读取块数：5 + 100
• 要处理20遍
• 读取总块数：20×( 5+100 ) = 2100
• 读数据时间：2100/20=105秒
• 中间结果大小：10000
• 写中间结果时间 10000/10/20 = 50秒 

② б：读数据时间 = 50秒 。结果50个元组。

③ П：时间忽略。

总时间：105＋50＋50秒 = 205秒= 3.4分

关系代数表达式三:

• p_Sname(Student∞s_{SC.Cno=’2’}(SC))
• ① б：
  • 读SC表总块数：10000/100=100块
  • 读数据时间：100/20=5秒 
  • 中间结果大小：50条，不必写入中间文件 
• ② ∞ ：
  • 读Student表总块数：1000/10=100块
  • 读数据时间：100/20=5秒 
  • ③ П：时间忽略。
  • 总时间：5＋5秒＝10秒