。 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%可用无序索引，否则只可用顺序索引， 无顺序索引，用顺序扫描