。 S 3.08 1 Access-path Based Query Optimization 基于存取路径的查询优化 182-1
182-1 §3.08_1 Access-path Based Query Optimization ——基于存取路径的查询优化
代数优化是在操作次序及组合上进行 变换和调整。不涉及存取路径和操作 执行策略上的优化。效果受限。 合理选择存取路径，往往也具显著优 化效果。应当重视。 本节结合存取路径分析，讨论各基本 操作的执行策略及其选择原则。 182-2
182-2 • 代数优化是在操作次序及组合上进行 变换和调整。不涉及存取路径和操作 执行策略上的优化。效果受限。 • 合理选择存取路径，往往也具显著优 化效果。应当重视。 • 本节结合存取路径分析，讨论各基本 操作的执行策略及其选择原则
选择操作的实现和优化 1，选择条件有三类： ·等值：即属性等于某给定值， 范围：属性值在给定范围， ·集合：用集合关系表示的条件。 2,实现方法与存取路径： ·原始的方法是逐个扫描并按选择条件检验。大关系中 选少量元组时效率很低。 。 其它存取路径主要是以B+树或其变种构成的各种索引： (1)无序索引文件 特点：主文件为堆文件，具有相同索引值的元组 可能存储在不同物理块，每读一个元组均需方问一个 物理块。 1823
182—3 一，选择操作的实现和优化 1，选择条件有三类： • 等值：即属性等于某给定值， • 范围：属性值在给定范围， • 集合：用集合关系表示的条件。 2，实现方法与存取路径： • 原始的方法是逐个扫描并按选择条件检验。大关系中 选少量元组时效率很低。 • 其它存取路径主要是以B+树或其变种构成的各种索引： （1）无序索引文件—— 特点：主文件为堆文件，具有相同索引值的元组 可能存储在不同物理块，每读一个元组均需方问一个 物理块
适用：大关系中查询索引少数元组。问题：可 索引一个关系的较多元组时，引起大量访问物 理块。 (2)索引顺序文件 特点：主文件是按索引属性排序的。 适用：索引属性上的范围查询。 问题：主文件插入，删除，索引维修量大 注意：(1)一个索引一般只对应一个属性，故 只支持索引属性上的查询。 (2)有的数据库提供多属性索引，动态散 列等存取路径，只对个别查询有利。 182—4
182—4 适用：大关系中查询索引少数元组。问题：可 索引一个关系的较多元组时，引起大量访问物 理块。 （2）索引顺序文件—— 特点：主文件是按索引属性排序的。 适用：索引属性上的范围查询。 问题：主文件插入，删除，索引维修量大。 注意：（1）一个索引一般只对应一个属性，故 只支持索引属性上的查询。 （2）有的数据库提供多属性索引，动态散 列等存取路径，只对个别查询有利
3,·实现存取路径选择规则 (1)小关系可不考虑存取路径，直接用顺序 扫描。 (2)涉及的属性无索引，散列等路径可用 或估计选中元组占关系元组总数的比例较大 (如>20%)，也选用顺序扫描。 (3)主键等值选择，只有一个元组可选中 优先用主键上的索引或散列。 (4)非主键等值选择，视可选中元组比，如 小于20%可用无序索引，否则只可用顺序索 无顺序索引，用顺序扫描
182—5 3，实现存取路径选择规则 （1）小关系可不考虑存取路径，直接用顺序 扫描。 （2）涉及的属性无索引，散列等路径可用; 或估计选中元组占关系元组总数的比例较大 （如>20%）,也选用顺序扫描。 （3）主键等值选择，只有一个元组可选中， 优先用主键上的索引或散列。 （4）非主键等值选择，视可选中元组比，如 小于20%可用无序索引，否则只可用顺序索引， 无顺序索引，用顺序扫描
5)范围条件，先用顺序索引找到边界后 沿顺序集搜索。被选属性上无顺序索引， 顺序扫描。 (6)AND合取条件，如有，优先多属性索引。 否则，如无可按(3,4,5)原则初选的个别 条件，如有则初选，在初选集上再用其它合取 条件选择。 (5)OR析取，开销大，无好办法，只能一个 一个析取式按(3,4,5)方法，取并。或顺 序扫描。故，应少用。 (6)注意有些条件在索引上可得，如索引属 性的最大，最小，平均值等，优先用索引
182—6 （5）范围条件，先用顺序索引找到边界后 沿顺序集搜索。被选属性上无顺序索引， 顺序扫描。 （6）AND合取条件，如有，优先多属性索引。 否则，如无可按（3，4，5）原则初选的个别 条件，如有则初选，在初选集上再用其它合取 条件选择。 （5）OR析取，开销大，无好办法，只能一个 一个析取式按（3，4，5）方法，取并。或顺 序扫描。故，应少用。 （6）注意有些条件在索引上可得，如索引属 性的最大，最小，平均值等，优先用索引
主文件（顺序集） 指针 一级索引 98601 98602 98605 ● 98603 块1 二级索引 98616 98604 块1 98628 98605 98648 98637 98608 98642 98611 ● 块1 98648 98612 块2 98655 99697 98613 98616 98617 98625 98626 98627 块5 99697 主关键字 指针 99696 99697 换的】 图4.18 索引顺序文件
稠密索引 主文件 98601 79644 二级索引 一级索引 98602 98605 98672 98608 98603 98602 98604 98690 98605 98601 99697 98608 99696 98690 98603 99697 。 99644 98608 99690 98604 99697 99696 99697 图4.19索引无序文件
第一个索引项 第二个索引项 最后一个索引项略去主关键字 ky se 索引块 b2 b3 b4 u☑ me no u 记录块 b5 b6 b7 b8 b9 b10 b11 hahu☑jo ka ky la to me ne no ru se wO wu xi ze 图4.32 一个简单B+树
中 45 45 45 24 24 53 (a) (b) (c) (d) 45 45 24 53 24 53 12 24 45 24 53 12 24 90 (g) 图9.8二叉排序树的构造过程 (a)空树，(b)插入45多(c)插入24 (d)插入53，(e)插入12，(f)插入90