超级详细的查询树优化！数据库笔记GET
查询树优化
⼀、执⾏代价估算
即查询操作的不同执⾏策略的代价估算
⽬前关系数据库管理系统通过某种代价模型计算出各种查询执⾏策略的执⾏代价，然后选取代价最⼩的执⾏⽅案。
执⾏开销
查询操作的执⾏开销主要包括：（以集中式数据库为例）
1. 磁盘存取块数（I/O代价） 因为磁盘I/O操作涉及机械动作，所以需要的时间和内存操作相⽐要⾼⼏个数量级，所以我们计算查询代价时⼀般以查
询处理读写的块数作为衡量单位。
2. 处理机时间（CPU代价）
3. 查询的内存开销
（如果是分布式数据库，还要考虑 4. 通信代价）
执⾏开销计算实例
eg：求选修了2号课程的学⽣姓名。
1）⽤SQL语句来表达这个查询：
SELECT Student.Sname
FROM Student,SELECT
WHERE Student.Sno=SC.Sno AND SC.Cno='2';
2）系统可以使⽤多种等价的关系代数表达式完成上⾯的查询操作，但是查询执⾏的策略不同，查询效率相差⾮常⼤。
我们下⾯分析三种⾮常有代表性的关系代数表达式，研究这3个表达式/执⾏策略需要耗费的I/O（处理读写的块数）代价。
电脑通过虚拟⽂件系统（VFS）访问物理磁盘，每次对磁盘访问的最⼩单位是⼀个盘⾯的⼀个磁道上的⼀个扇区，即使⽤户只需要访问⼀个字节的数据，实际读写的时候也是先将所在扇区读⼊内存，然后再进⾏访问，正因为如此，⽂件系统是由⼀系列块构成的。块的⼤⼩通常是⼀个扇区的⼤⼩，⽽⼀个扇区通常为512字节
为了⽅便计算我们先做⼀些假定：
a. 学⽣-课程数据库中有1000个学⽣记录，10 000个选课记录，其中选修2号课程的选课记录为50个。
b. 计算笛卡⼉积时，以Student和SC的元组连接为例，⼀般采⽤的做法是：
在内存中尽可能多地装⼊某个表（如Student表）的若⼲块，留出⼀块存放另⼀个表（如SC表）的元组：然后把SC中的每个元组和Student中每个元组进⾏连接，连接后的元组装满⼀块后就写到中间⽂件上，再从SC中读⼊⼀块和内存中的Student元组连接，直到SC表处理完；
之后再读⼊若⼲块Student元组，读⼊⼀块SC元组，重复上述处理过程，直到把Student表处理完。
其实就是类似于嵌套循环算法的处理⽅式，但是这⾥由于内存的限制，只能每次取出⼀部分Student中的元组来和SC中的全部元组进⾏ 连接 ，即每次读进⼀部分Student中的元组，都要遍历⼀遍SC表。
整个过程可以这样描述（上述Student对应下⾯的R表 SC对应S表）：
设连接表R和S分别占⽤的块数是Br和Bs，连接操作使⽤的内存缓冲区块数是为K，分配K-1块给外表。如果R为外表，则嵌套循环法存取的块数是Br+BrBs/（K-1），显然我们选择外表时应该选择块数较⼩的表。
c. ⼀个（内存缓冲区中的）块能装10个Student元组或100个SC元组。
d. 内存缓冲区中总共使⽤6个块，其中5块⽤来存放Student元组，1块⽤来存放SC元组
下⾯是对这三种执⾏策略的代价估算：
上⾯的例⼦不仅说明了查询优化的重要性，也给了我们⼗分宝贵的优化经验和优化“直觉”，之后的启发式规则就是基于类似这样的经验得出的。
⼆、等价变换公式
关系代数表达式的等价变换规则
我们可以通过下⾯这些等价关系，对关系代数表达式进⾏等价变换以达到提⾼查询效率的⽬的
详细描述以及证明可见王珊⽼师的的代数优化章节。
1.连接、笛卡⼉积的交换律
2.连接、笛卡⼉积的结合律
3.投影的串接定律
4.选择的串接定律
5.选择与投影的交换律
sql优化的几种方式
6.选择与笛卡⼉积的交换律
7.选择与并的分配律

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。