《第6章数据存储与查询优化》由会员分享，可在线阅读，更多相关《第6章数据存储与查询优化（25页珍藏版）》请在金锄头文库上搜索。
1、第第6 6章章 数据存储与数据存储与查询优化查询优化数据库原理及应用数据库原理及应用郑轶（郑轶（20102010）目目 录录n6.1 6.1 物理存储物理存储 n6 6.2.2 索引结构索引结构n6 6.3.3 查询处理过程查询处理过程n6 6.4.4 代数优化代数优化n6.5 6.5 物理优化物理优化6.1 6.1 物理存储物理存储6.1.1 6.1.1 物理存储介质概述物理存储介质概述n存储介质可以根据数据存取的速度、购买介质时每单位数存储介质可以根据数据存取的速度、购买介质时每单位数据的成本和介质的可靠性来分类。主要的介质有：据的成本和介质的可靠性来分类。主要的介质有： 磁带、光盘等磁带
2、、光盘等磁盘磁盘内存内存cachecache一级存储一级存储二级存储二级存储三级存储三级存储磁盘磁盘n读写磁盘数据步骤：读写磁盘数据步骤：1.1.移动磁盘臂，确定磁道；移动磁盘臂，确定磁道；寻道时间寻道时间。2.2.旋转盘片，确定扇区；旋转盘片，确定扇区；旋转时间旋转时间。3.3.读写数据；读写数据；传输时间传输时间。n磁盘访问时间磁盘访问时间= =寻道时间寻道时间+ +旋转时间旋转时间+ +传输时间传输时间n数据预存：数据预存：读取指定数据读取指定数据的同时预先读取与其相邻的同时预先读取与其相邻的一定范围内的数据。的一定范围内的数据。n按块传输：按块传输：块大小块大小1-8KB1-8KB6.
3、1.2 6.1.2 缓冲区管理缓冲区管理n缓冲区是内存的一部分，用于存储磁盘块的内容。缓冲区是内存的一部分，用于存储磁盘块的内容。n缓冲区管理器管理内存中缓冲区空间的分配。缓冲区管理器管理内存中缓冲区空间的分配。 n缓冲区管理器使用不同的技术（比如缓冲区替换策略、缓冲区管理器使用不同的技术（比如缓冲区替换策略、牵制的块、缓冲区高速缓存等）来有效地为数据库系牵制的块、缓冲区高速缓存等）来有效地为数据库系统服务。统服务。 n最近最少使用替换策略（最近最少使用替换策略（Least Recently UsedLeast Recently Used，LRULRU）6.1.3 6.1.3 记录的存储记录的
4、存储n数据通常是以记录的形式存储的。数据通常是以记录的形式存储的。 n记录又由字段组成。由于字段类型分为定长和变长两种，记录又由字段组成。由于字段类型分为定长和变长两种，文件也可分为：文件也可分为：定长记录定长记录和和变长记录变长记录两种。两种。n定长记录中，所有的字段都是定长的，只需将所有字段按既定的定长记录中，所有的字段都是定长的，只需将所有字段按既定的顺序连续存放，所有字段的地址相对于记录首地址的偏移都可以顺序连续存放，所有字段的地址相对于记录首地址的偏移都可以由计算得到。由计算得到。6.1.3 6.1.3 记录的存储记录的存储n变长记录中每个字段相对于记录首地址的偏移不固定。变长记录中
5、每个字段相对于记录首地址的偏移不固定。n内部格式通常有两种：内部格式通常有两种：n用特殊的分割符将记录的各字段分开。用特殊的分割符将记录的各字段分开。n在记录首部存储各个字段的偏移量。在记录首部存储各个字段的偏移量。块格式块格式数据文件的重整数据文件的重整超长记录和记录的跨块存储超长记录和记录的跨块存储n跨块存储提高了磁盘空间的利用率。跨块存储提高了磁盘空间的利用率。n跨块存储的记录分布于不同的块中，在物理上不连续，需跨块存储的记录分布于不同的块中，在物理上不连续，需要用一个链表维护同一记录的不同部分。要用一个链表维护同一记录的不同部分。6.1.4 6.1.4 文件组织方式文件组织方式n在在D
6、BMSDBMS中常用的文件组织方式有：中常用的文件组织方式有：n堆文件：堆文件：记录间没有次序关系，新加入的记录可以存储在文件中记录间没有次序关系，新加入的记录可以存储在文件中任何有空间的地方。任何有空间的地方。n顺序文件：顺序文件：记录按搜索键排序。记录按搜索键排序。n哈希文件：哈希文件：对记录的某些字段进行哈希运算，运算的结果决定记对记录的某些字段进行哈希运算，运算的结果决定记录存储在文件中的哪一块。录存储在文件中的哪一块。n聚集文件：聚集文件：将同种类或相关的来自于不同关系的记录存放在同一将同种类或相关的来自于不同关系的记录存放在同一块中，以减少同时获取这些记录的块中，以减少同时获取这些
7、记录的I/OI/O操作。操作。6.2 6.2 索引索引n从理论上来说，只要记录被正确地存储于书记文件中，从理论上来说，只要记录被正确地存储于书记文件中，DBMSDBMS就可以正常工作；但实际上，单纯依赖数据文件处理就可以正常工作；但实际上，单纯依赖数据文件处理查询有时效率非常低。查询有时效率非常低。n索引是一个表或数据结构，用于确定文件中满足某些条件索引是一个表或数据结构，用于确定文件中满足某些条件的行（记录）的位置。的行（记录）的位置。 n索引键（索引字段）索引键（索引字段）nB+B+树索引、哈希索引树索引、哈希索引6.3 6.3 查询处理过程查询处理过程n查询处理过程包括三步：语法分析、查
8、询优化、执行。查询处理过程包括三步：语法分析、查询优化、执行。n查询总代价查询总代价=I/O=I/O代价代价+CPU+CPU代价代价+ +内存代价内存代价 + +通信代价（分布式数据库）通信代价（分布式数据库）n例：求选修了课程例：求选修了课程C2C2的学生姓名。其的学生姓名。其SQLSQL语句：语句：SELECT SELECT S.SnameS.SnameFROM S,SCFROM S,SCWHERE WHERE S.SnoS.Sno= =SC.SnoSC.Sno AND AND SC.CnoSC.Cno=C2;=C2;n假定学生课程数据库中有假定学生课程数据库中有10001000个学生记录
9、，个学生记录，1000010000个选个选课记录，其中选修课记录，其中选修C2C2课程的选课记录为课程的选课记录为5050个。个。n系统可用多种等价的关系代数表达式来完成这一查询：系统可用多种等价的关系代数表达式来完成这一查询：n Q1= Q1= SnameSname( (S.SnoS.Sno= =SC.SnoSC.CnoSC.SnoSC.Cno=C2=C2（SSCSSC） ) )n Q2= Q2= SnameSname ( (SC.CnoSC.Cno=C2=C2（S SSCSC） ) )n Q3= Q3= SnameSname ( (S SSC.CnoSC.Cno=C2=C2（SCSC） )
10、 )一个实例一个实例Q1= Q1= SNSN( (S.SS.S#=SC.S#SC.C#=C2#=SC.S#SC.C#=C2（SSC)SSC)1 1、计算广义笛卡儿积、计算广义笛卡儿积n设一个块能装设一个块能装1010个个S S元组或元组或100100个个SCSC元组，在内存中存放元组，在内存中存放5 5块块S S元组元组1 1块块SCSC元组，则读取总块数为：元组，则读取总块数为：1000/101000/1010000/100 (1000/10)/510000/100 (1000/10)/521002100块块n其中读其中读S S表表100100块，读块，读SCSC表表2020遍，每遍遍，每遍
11、100100块，若每秒读块，若每秒读2020块，则总计块，则总计要花要花105105秒。秒。n连接以后的元组数为连接以后的元组数为100010000100010000，设每块能装，设每块能装1010个元组，则写出这个元组，则写出这些块要花些块要花10106 6/20/205105104 4秒。秒。 E1xE2E1xE2代价估计主要是从磁盘代价估计主要是从磁盘读块和中间结果写盘的时间考虑，读块和中间结果写盘的时间考虑，而对主存中数据的处理时间忽略而对主存中数据的处理时间忽略不计。不计。 E1xE2E1xE2读块总数读块总数=E1=E1的块数的块数+E2+E2的块数的块数读读E2E2的遍数的遍数2
12、 2、作选择操作、作选择操作n依次读入连接后的元组，按照选择条件选取满足要求的记录，依次读入连接后的元组，按照选择条件选取满足要求的记录，假定内存处理时间忽略。假定内存处理时间忽略。n这一步读取中间文件花费的时间需这一步读取中间文件花费的时间需5105104 4秒秒( (同写中间文件同写中间文件一样一样) )。满足条件的元组假设仅满足条件的元组假设仅5050个，均可放在内存。个，均可放在内存。3 3、作投影操作、作投影操作n把第把第2 2步的结果在步的结果在SNSN上作投影输出，得到最终结果。上作投影输出，得到最终结果。n内存操作，忽略。内存操作，忽略。nQ1Q1的查询代价的查询代价 2(51
13、02(5104 4) )105 10105 105 5秒秒Q1= Q1= SnameSname( (S.SnoS.Sno= =SC.SnoSC.CnoSC.SnoSC.Cno=C2=C2（SSC)SSC)1 1、计算自然连接、计算自然连接n读取读取S S和和SCSC表的策略不变，总的读取块数仍为表的策略不变，总的读取块数仍为21002100块花费块花费105105秒；秒；n但自然连接的结果比第一种情况大大减少，为但自然连接的结果比第一种情况大大减少，为1000010000个；个；n平均每人选平均每人选1010门课，故写出这些元组时间门课，故写出这些元组时间10104 4/10/20/10/20
14、5050秒。秒。2 2、读取中间文件块，执行选择运算、读取中间文件块，执行选择运算n花费时间也为花费时间也为5050秒。秒。3 3、把连接结果投影输出、把连接结果投影输出nQ2Q2的查询代价的查询代价 105105505050 20550 205秒秒Q2= Q2= SnameSname( (SC.CnoSC.Cno=C2=C2（S SSCSC） ) )1 1、先对、先对SCSC表作选择运算表作选择运算n只需读一遍只需读一遍SCSC表，存取表，存取10000/10010000/100块，花费时间为块，花费时间为5 5秒。秒。n满足条件的元组仅满足条件的元组仅5050个，存在内存中。个，存在内存中
15、。2 2、读取、读取S S表表n把读入的把读入的S S元组和内存中的元组和内存中的SCSC元组作自然连接，也只需读元组作自然连接，也只需读一遍一遍S S表共表共1000/101000/10块，花费时间为块，花费时间为5 5秒。秒。3 3、把连接结果投影输出。、把连接结果投影输出。nQ3Q3的查询代价的查询代价 5 55 105 10秒秒Q3= Q3= SnameSname(S(SSC.CnoSC.Cno=C2=C2（SCSC） ) )查询代价的比较查询代价的比较nQ3Q3的进一步优化的进一步优化n若若SCSC上有上有CnoCno索引，则选择操作只需读取索引，则选择操作只需读取5050个元组。个
16、元组。n若若S S上有上有SnoSno索引，则连接操作也不一定要读取所有索引，则连接操作也不一定要读取所有10001000个元组。个元组。优化规则优化规则n针对给定的查询问题，通常有以下优化规则：针对给定的查询问题，通常有以下优化规则：n规则1：尽量将选择和投影运算提前，以减少元组数和关系大小。n规则2：把某些选择运算和笛卡尔积相结合，即将选择运算附加在连接运算上，可减少中间结果保存以备后用的时间代价。n规则3：对同一关系上的多个选择和投影运算同时进行，以避免重复扫描同一关系。n规则4：把投影操作和连接运算结合起来执行。n查询优化的两种主要途径：查询优化的两种主要途径：代数优化、物理优化代数优化、物理优化。6.4 6.4 代数优化代数优化nQ1= Q1= SnameSname( (S.SnoS.Sno= =SC.SnoSC.CnoSC.SnoSC.Cno=C2=C2（SSC)SSC)代数优化实例代数优化实例代数优化实例代数优化实例代数优化实例代数优化实例6.5 6.5 物理优化物理优化n代数优化：关系代数表达式的优化。n改变查询语句中操作的次序和组合，不涉及底层的存取路径。n物理优化：存取路径和底层操作算法的估算与选择。n选择高效合理的操作算法或存取路径，求得优化的查询计划。n物理优化过程：n枚举策略 - 估算代价 生成计划n基于代价进行
