查询处理与优化 夏英 (xiaying@cqupt.edu.cn) 重庆邮电大学计算机学院
查询处理与优化 夏英 (xiaying@cqupt.edu.cn) 重庆邮电大学计算机学院
主要内容 ■查询处理的步骤 ■查询代价的度量 ■典型运算的代价分析—选择、排序、连接 查询优化方法
主要内容 查询处理的步骤 查询代价的度量 典型运算的代价分析——选择、排序、连接 查询优化方法
查询处理和优化 任务:根据用户命令从数据库中高效地提取数据 ●查询处理是 RDBMS的核心,查询优化是查询处理的关键 ●用户只需提出“做什么”,不必说明“怎么做”,由系统 选择有效的执行策略,提高查询性能
查询处理和优化 任务：根据用户命令从数据库中高效地提取数据 查询处理是RDBMS的核心，查询优化是查询处理的关键 用户只需提出 “做什么 ”，不必说明 “怎么做 ”，由系统 选择有效的执行策略，提高查询性能
DBMS的运行过程(从用户的角度) 以某一应用程序读取数据库中的记录为例 1.APP向DBMS发出访问DB的命令,其中给出了关系名和 查询条件; 2.DBMS读取数据字典,检查是否存在该关系和相应的字 段,并对该命令进行语法检查和用户存取权限检查。 如果数据库和相应的字段在、命令语法和语义正确且 存取权限合法,则执行该命令,否则拒绝并返回出错 信息 3.执行该命令时,首先根据数据字典中的定义信息将命令 中的外模式映射到模式,确定应该读如哪些记录; 4.根据数据字典中的定义信息,将模式映射到内模式,确 定应该读入哪些物理记录及有关的地址信息;
DBMS的运行过程 (从用户的角度) 以某一应用程序读取数据库中的记录为例 1. APP向DBMS发出访问DB的命令，其中给出了关系名和 查询条件； 2. DBMS读取数据字典，检查是否存在该关系和相应的字 段，并对该命令进行语法检查和用户存取权限检查。 如果数据库和相应的字段在、命令语法和语义正确且 存取权限合法，则执行该命令，否则拒绝并返回出错 信息； 3. 执行该命令时，首先根据数据字典中的定义信息将命令 中的外模式映射到模式，确定应该读如哪些记录； 4. 根据数据字典中的定义信息，将模式映射到内模式，确 定应该读入哪些物理记录及有关的地址信息；
5.DBMS向OS发送读取该记录的命令; 6.OS执行读取数据的有关操作,从指定地址读取记录并存入 系统缓冲区; 7.DBMS将系统缓冲区中的数据转换为模式并进而转换为外 模式; 8.DBMS将系统缓冲区外模式形式的记录返回给应用程序; 9DBMS将运行情况登记在运行日志中; 10.DBMS将命令执行状态返回APP; 11.若APP中的命令需读取多条记录,则反复执行410步
5. DBMS向OS发送读取该记录的命令； 6. OS执行读取数据的有关操作，从指定地址读取记录并存入 系统缓冲区； 7. DBMS将系统缓冲区中的数据转换为模式并进而转换为外 模式； 8. DBMS将系统缓冲区外模式形式的记录返回给应用程序； 9. DBMS将运行情况登记在运行日志中； 10. DBMS将命令执行状态返回APP； 11. 若APP中的命令需读取多条记录，则反复执行4-10步
查询处理的步骤 语法分析与翻译( Parsing and translation 2优化( Optimization) 3.执行( Evaluation) query parser and relational-algebra translator expression optimizer>← query evaluation engine output execution plan data statistics about data
查询处理的步骤 1. 语法分析与翻译 （Parsing and translation ） 2. 优化 （Optimization ） 3. 执行 （Evaluation ）
查询处理的步骤 语法分析与翻译 扫描、识别SQL语句,进行词法、语法解析,判断是否符合SQL 语法规则 检查语句中的关系名是否存在和有效,检查用户与权限和完整性 约束 把SQL语句转换成等价的内部表示形式(语法分析树,或进一步 翻译成关系代数表达式,代表一种执行计划) ■优化 选择一个高效执行的查询执行计划 ●选择的依据:基于代价 执行 按照选定的查询执行计划执行,并输出结果
查询处理的步骤 语法分析与翻译 扫描 、识别SQL语句，进行词法 、语法解析，判断是否符合SQL 语法规则 检查语句中的关系名是否存在和有效，检查用户与权限和完整性 约束 把SQL语句转换成等价的内部表示形式 （语法分析树，或进一步 翻译成关系代数表达式，代表一种执行计划 ） 优化 选择一个高效执行的查询执行计划 选择的依据：基于代价 执行 按照选定的查询执行计划执行，并输出结果
查询优化 ■在SQL中,一个查询可有多种表示方式,不要期待用户 写出具有最高效率执行计划的查询语句 个关系代数表达式可能有多个等价的表达式 如oay70 ar(instructor))-等价于 Isalarvosalarv 75000(instructor)) ■每个关系代数运算通常有多重计算方式,即执行计划 ●如,可以利用 salary上的索引查找 salary<75000的 instructors 或者,扫描全表并去掉 salary≥75000的 Instructors ■不同的执行计划有不同的代价
查询优化 在SQL中，一个查询可有多种表示方式，不要期待用户 写出具有最高效率执行计划的查询语句 一个关系代数表达式可能有多个等价的表达式 如 σsalary<75000(∏salary(instructor))等价于 ∏salary(σsalary<75000(instructor)) 每个关系代数运算通常有多重计算方式，即执行计划 如, 可以利用salary上的索引查找salary < 75000的instructors 或者，扫描全表并去掉salary ≥ 75000的instructors 不同的执行计划有不同的代价
name, title ∏ title dept_name= music instructor deptname= Music teaches course instructor teaches COurse 同一查询的不同执行计划
同一查询的不同执行计划
name, title (sort to remove duplicates) Chash join) <(merge join) course pipeline pipeline dept_name= music year=2009 use index (use linear scan) instructor eaches 一个更详细的执行计划
一个更详细的执行计划