《查询处理》ppt课件

《《查询处理》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5章查询处理本章内容参考数据库概念(第四版)byA.SilberschatzChapter13QueryProcessing简介+自学补充内容本章要解决的关键问题如何将用户的查询请求转化为可执行的查询计划如何估算基本关系代数运算的代价本章内容特色实：在实现DBMS和高级应用中有用，是数据库管理员必备知识细：细致，有一定难度，课堂上不一定能完全理解，需课后仔细体会定：定量分析，比较不同方案用数字来作结论模：定量分析需要数学模型(先作一些假定，忽略一些次要的因素，用一套符号表示一些度量，然后计算除结果，可学到建立定量分析模型的方法)主要内容查询处理基本步骤查询代价度量选择操作排序连接操作其他

2、操作表达式求值DBMSArchitectureQueryExecutorBufferManagerStorageManagerStorageTransactionManagerLogging&RecoveryLockManagerBuffersLockTablesMainMemoryUser/WebForms/Applications/DBAquerytransactionQueryOptimizerQueryRewriterQueryParserFiles&AccessMethodsPastlectures查询处理基本步骤1.词法分析与翻译(本章)2.优化(下章)3.求值(本章)查询处理

3、基本步骤词法分析与翻译将查询翻译成内部形式,再翻译成关系代数表达式词法分析器检查语法,验证关系求值查询执行引擎以查询求值方案为输入,执行该方案,并返回查询结果查询处理的基本步骤求值计划在表达式上加标注以说明详细求值策略,称为求值计划例如,可利用balance上的索引来查找余额小于2500的账户,或者也可以执行完全的关系扫描,丢弃那些余额2500的账户查询优化在所有等价的求值计划中选择代价最低者利用数据库目录中的统计信息来求值代价如每个关系的元组数,元组大小等查询处理的基本步骤:优化本章研究如何度量查询代价关系代数运算的求值算法如何将单个运算的算法结合起来以对整个表达式求值下章研究如何优化

4、查询,即如何找到具有最低求值代价的求值计划查询代价的度量查询代价通常用回答查询所耗费总时间来度量许多因素影响时间代价磁盘存取(I/O),CPU,网络通信一般来说,磁盘存取对代价起决定性作用,并且相对容易求值，磁盘存取代价的度量要考虑:寻址次数*average-seek-cost读块数*average-block-read-cost写块数*average-block-write-cost写一块的代价大于读一块的代价写数据后要读回，以确保写成功查询代价的度量为简单起见,我们仅用磁盘块传送数作为代价的度量忽略顺序与随机I/O之间的代价不同之处忽略CPU代价代价依赖于内存缓冲区的大小内存多可以减少

5、磁盘存取数可用于缓冲区的实际内存量取决于其他并发OS进程,在实际执行之前难以确定我们经常用最坏情形求值,故假定只有操作所需的最小内存量可用实际系统要考虑CPU代价,区分顺序与随机I/O,考虑缓冲区大小在代价公式中不包括将输出写到磁盘的代价插曲：科研方法(10/12)借本章内容为载体，介绍一些作科研的方法原创工作vs非原创工作vsdelta研究建立模型：引入记号，变量，确定变量之间关系，常常简化模型，忽略次要因素，抓主要矛盾分而治之，先推导局部公式综合公式从公式分析，改进方向改进，试验，结论论文或成果建立数学模型是深入研究的开始插曲：科研方法简化模型：(即忽略次要因素，抓主要矛盾）传输块

6、数numberofblocktransfers（盘：内存）忽略顺序和随机I/O的差别，忽略CPU的花销花销大小依赖于缓存大小缓存大，磁盘传输快OS管理缓存（进程）常用最坏情形估计worstcaseestimates在工程中的实际系统不忽略CPU花销，要考虑随机和顺序的影响输出时写盘的时间也忽略用于代价估算的统计信息nr:关系r中的元组个数br:包含r中元组的块数sr:r中元组的大小fr:r的块因子—即,能放入一块之中的r的元组数V(A,r):r中出现的A属性上的不同值的个数,等于A(r)的大小SC(A,r):关系r中属性A的选择基数,满足A上等值条件的平均记录数若r中元组在文件中连续存放

7、,则:关于索引的目录信息fi:索引i的内节点的平均扇出,适用于树结构索引,如B+树HTi:索引i的层数—即高度对于关系r上A属性的平衡树索引(如B+-树),HTi=logfi(V(A,r))对于散列索引,HTi为1LBi:索引i的底层索引块数—即索引叶子层的块数选择操作文件扫描–定位并读取满足选择条件的记录的搜索算法算法A1(线性搜索):扫描每个文件块并测试所有记录是否满足选择条件求值代价(扫描磁盘块数)=brbr表