数据存储与查询优化.pptx

《数据存储与查询优化.pptx》由会员分享，可在线阅读，更多相关《数据存储与查询优化.pptx（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、目 录6.1 物理存储 6.2 索引结构6.3 查询处理过程6.4 代数优化6.5 物理优化第1页/共25页6.1 物理存储6.1.1 物理存储介质概述存储介质可以根据数据存取的速度、购买介质时每单位数据的成本和介质的可靠性来分类。主要的介质有：磁带、光盘等磁带、光盘等磁盘磁盘内存内存cachecache一级存储一级存储二级存储二级存储三级存储三级存储第2页/共25页磁盘读写磁盘数据步骤：n移动磁盘臂，确定磁道；寻道时间。n旋转盘片，确定扇区；旋转时间。n读写数据；传输时间。磁盘访问时间=寻道时间+旋转时间+传输时间数据预存：读取指定数据的同时预先读取与其相邻的一定范围内的数据。1.按块传输：

2、块大小1-8KB第3页/共25页6.1.2 缓冲区管理缓冲区是内存的一部分，用于存储磁盘块的内容。缓冲区管理器管理内存中缓冲区空间的分配。缓冲区管理器使用不同的技术（比如缓冲区替换策略、牵制的块、缓冲区高速缓存等）来有效地为数据库系统服务。最近最少使用替换策略（Least Recently Used，LRU）第4页/共25页6.1.3 记录的存储数据通常是以记录的形式存储的。记录又由字段组成。由于字段类型分为定长和变长两种，文件也可分为：定长记录和变长记录两种。定长记录中，所有的字段都是定长的，只需将所有字段按既定的顺序连续存放，所有字段的地址相对于记录首地址的偏移都可以由计算得到。第5页/共

3、25页6.1.3 记录的存储变长记录中每个字段相对于记录首地址的偏移不固变长记录中每个字段相对于记录首地址的偏移不固定。定。内部格式通常有两种：内部格式通常有两种：用特殊的分割符将记录的各字段分开。用特殊的分割符将记录的各字段分开。在记录首部存储各个字段的偏移量。在记录首部存储各个字段的偏移量。第6页/共25页块格式第7页/共25页数据文件的重整第8页/共25页超长记录和记录的跨块存储跨块存储提高了磁盘空间的利用率。跨块存储的记录分布于不同的块中，在物理上不连续，需要用一个链表维护同一记录的不同部分。第9页/共25页6.1.4 文件组织方式在DBMS中常用的文件组织方式有：堆文件：记录间没有次

4、序关系，新加入的记录可以存储在文件中任何有空间的地方。顺序文件：记录按搜索键排序。哈希文件：对记录的某些字段进行哈希运算，运算的结果决定记录存储在文件中的哪一块。聚集文件：将同种类或相关的来自于不同关系的记录存放在同一块中，以减少同时获取这些记录的I/O操作。第10页/共25页6.2 索引从理论上来说，只要记录被正确地存储于书记文件中，DBMS就可以正常工作；但实际上，单纯依赖数据文件处理查询有时效率非常低。索引是一个表或数据结构，用于确定文件中满足某些条件的行（记录）的位置。索引键（索引字段）B+树索引、哈希索引第11页/共25页6.3 查询处理过程查询处理过程包括三步：语法分析、查询优化、

5、执行。查询总代价=I/O代价+CPU代价+内存代价 +通信代价（分布式数据库）第12页/共25页例：求选修了课程C2的学生姓名。其SQL语句：SELECT FROM S,SCWHERE =AND =C2;假定学生课程数据库中有1000个学生记录，10000个选课记录，其中选修C2课程的选课记录为50个。系统可用多种等价的关系代数表达式来完成这一查询：Q1=Sname(=C2（SSC）)Q2=Sname(=C2（SSC）)Q3=Sname(S=C2（SC）)一个实例第13页/共25页Q1=SN(#=SC.S#SC.C#=C2（SSC)1、计算广义笛卡儿积设一个块能装10个S元组或100个SC元组

6、，在内存中存放5块S元组1块SC元组，则读取总块数为：1000/1010000/100(1000/10)/52100块其中读S表100块，读SC表20遍，每遍100块，若每秒读20块，则总计要花105秒。连接以后的元组数为100010000，设每块能装10个元组，则写出这些块要花106/205104秒。E1xE2 E1xE2代价估计主要是从磁盘代价估计主要是从磁盘读块和中间结果写盘的时间考虑，读块和中间结果写盘的时间考虑，而对主存中数据的处理时间忽略而对主存中数据的处理时间忽略不计。不计。E1xE2E1xE2读块总数读块总数=E1=E1的块数的块数+E2+E2的块数的块数读读E2E2的遍数的遍

7、数第14页/共25页2、作选择操作依次读入连接后的元组，按照选择条件选取满足要求的记录，假定内存处理时间忽略。这一步读取中间文件花费的时间需5104秒(同写中间文件一样)。满足条件的元组假设仅50个，均可放在内存。3、作投影操作把第2步的结果在SN上作投影输出，得到最终结果。内存操作，忽略。Q1的查询代价 2(5104)105 105秒Q1=Sname(=C2（SSC)第15页/共25页1、计算自然连接读取S和SC表的策略不变，总的读取块数仍为2100块花费105秒；但自然连接的结果比第一种情况大大减少，为10000个；平均每人选10门课，故写出这些元组时间104/10/2050秒。2、读取中

8、间文件块，执行选择运算花费时间也为50秒。3、把连接结果投影输出Q2的查询代价 1055050 205秒Q2=Sname(=C2（SSC）)第16页/共25页1、先对SC表作选择运算只需读一遍SC表，存取10000/100块，花费时间为5秒。满足条件的元组仅50个，存在内存中。2、读取S表把读入的S元组和内存中的SC元组作自然连接，也只需读一遍S表共1000/10块，花费时间为5秒。3、把连接结果投影输出。Q3的查询代价 55 10秒Q3=Sname(S=C2（SC）)第17页/共25页查询代价的比较Q3的进一步优化若SC上有Cno索引，则选择操作只需读取50个元组。若S上有Sno索引，则连接

9、操作也不一定要读取所有1000个元组。第18页/共25页优化规则针对给定的查询问题，通常有以下优化规则：规则1：尽量将选择和投影运算提前，以减少元组数和关系大小。规则2：把某些选择运算和笛卡尔积相结合，即将选择运算附加在连接运算上，可减少中间结果保存以备后用的时间代价。规则3：对同一关系上的多个选择和投影运算同时进行，以避免重复扫描同一关系。规则4：把投影操作和连接运算结合起来执行。查询优化的两种主要途径：代数优化、物理优化。第19页/共25页6.4 代数优化Q1=Sname(=C2（SSC)第20页/共25页代数优化实例第21页/共25页代数优化实例第22页/共25页代数优化实例第23页/共25页6.5 物理优化代数优化：关系代数表达式的优化。改变查询语句中操作的次序和组合，不涉及底层的存取路径。物理优化：存取路径和底层操作算法的估算与选择。选择高效合理的操作算法或存取路径，求得优化的查询计划。物理优化过程：枚举策略-估算代价 生成计划基于代价进行第24页/共25页感谢您的观看！第25页/共25页