【数据库】第九章关系查询处理与优化

阳光穿透心脏的1/2处 2024-03-26 14:21 43阅读 0赞

## 第九章 关系查询处理与优化 ##

### 索引 ###

![在这里插入图片描述][62739fb0bdc54d99bb056d77e8966a4b.png]

> 索引文件是一种辅助存储结构，其存在与否不改变存储表的物理存储结 构；然而其存在，可以明显提高存储表的访问速度。

**索引文件组织方式**有两种：(相对照的，主文件组织有堆文件、排序文件、散列文件、 聚簇文件等多种方式)

*  排序索引文件(Orderedindices):按索引字段值的某一种顺序组织存储
 *  散列索引文件(Hash  indices):依据索引字段值使用散列函数分配散列桶的 方式存储

#### 特点 ####

*  在一个表上可以针对不同的属性或属性组合建立不同的索引文件，可建立 多个索引文件。索引字段的值可以是Table中的任何一个属性的值或任何多个 属性值的组合值
 *  索引文件比主文件小很多。通过检索一个小的索引文件(可全部装载进内 存)，快速定位后，再有针对性的读取非常大的主文件中的有关记录
 *  有索引时，更新操作必须同步更新索引文件和主文件。
    
     *  > DBMS可以自动维护，table改变，索引也会有相应的改变
 *  索引技术应用使检索效率大幅度提高，但同时其也增加了存储空间、使维 护负担加重(不仅要维护主文件，而且要维护索引文件)
    
    **衡量索引性能好坏**：
 *  访问时间
 *  插入时间
 *  删除时间
 *  空间负载
 *  支持存取的有效性
    
     *  比如：支持的是属性的限定值(是否符合单一值)， 还是支持属性的限定范围的值(是否符合一定范围)

#### 相关概念 ####

![在这里插入图片描述][25796fae2c17418f9d369fc977e6ba11.png]

#### 创建索引 ####

![在这里插入图片描述][47bade3105b54a1daab5b9813c2463d1.png]

![在这里插入图片描述][5450dce04c90411986dfe24b72ca727c.png]

*  对于主文件中每一个记录(形成的每一个索引字段值)，都有一个索引项和它 对应，指明该记录所在位置。这样的索引称**稠密索引**(denseindex)
    
     *  候选键属性的稠密索引
        
         *  先查索引，然后再依据索引读主文件
     *  候选键属性的稠密索引(三种情况)  
        ![在这里插入图片描述][24557bc28bbc41b591ad2aa0b3fe6451.png]  
        ![在这里插入图片描述][84283d19a3794136ab4759db98d7d7fa.png]

![在这里插入图片描述][21c74ceaf7924492872b25ddabd82cfd.png]

*  对于主文件中部分记录(形成的索引字段值)，有索引项和它对应，这样的索 引称非稠密索引(undense index)或**稀疏索引**(sparseindex)
    
     *  稀疏索引如何定位记录
        
         *  定位索引字段值为 K的记录，需要
            
             *  首先找相邻的小于K的最大索引字段值所对应的索引项
             *  从该索引项所对应的记录开始顺序进行Table的检索
         *  稀疏索引的使用要求—主文件必须是按对应索引字段属性排序存储
         *  相比稠密索引：空间占用更少，维护任务更轻，但速度更慢
         *  平衡:索引项不指向记录指针，而是指向记录所在存储块的指针，即每一 存储块有一个索引项，而不是每条记录有一索引项----主索引  
            ![在这里插入图片描述][6a5d7adca14547fab665ca18f53a983b.png]  
            ![在这里插入图片描述][f7884d91d4bf4534af314b94a3a38538.png]  
            ![在这里插入图片描述][5a5017cce3c5468fa06b630fcea70d21.png]

比较

*  一个主文件仅可以有一个主索引，但可以有多个辅助索引
 *  主索引通常建立于主码/排序码上面；辅助索引建立于其他属性上面
 *  可以利用主索引重新组织主文件数据，但辅助索引不能改变主文件数据
 *  主索引是稀疏索引，辅助索引是稠密索引

#### 聚簇索引与非聚簇索引 ####

*  聚簇索引—是指索引中邻近的记录在主文件中也是临近存储的；
 *  非聚簇索引—是指索引中邻近的记录在主文件中不一定是邻近存储的

特点

*  如果主文件的某一排序字段不是主码，则该字段上每个记录取值便不唯 一，此时该字段被称为聚簇字段；聚簇索引通常是定义在聚簇字段上。
 *  聚簇索引通常是对聚簇字段上的每一个不同值有一个索引项（索引项的总数和 主文件中聚簇字段上不同值的数目相同），索引字段即是聚簇字段的不同值，由于有相同聚簇字 段值的记录可能存储于若干块中，则索引项的指针指向其中的第一个块。
 *  一个主文件只能有一个聚簇索引文件，但可以有多个非聚簇索引文件 主索引通常是聚簇索引(但其索引项总数不一定和主文件中聚簇字段上不同值的数目相 同，其和主文件存储块数目相同)；辅助索引通常是非聚簇索引。
 *  主索引/聚簇索引是能够决定记录存储位置的索引；而非聚簇索引则只能用 于查询，指出已存储记录的位置

#### 其他索引类型 ####

*  倒排索引

![在这里插入图片描述][3c557feb92b54cbe9efba11cf1793ba8.png]  
![在这里插入图片描述][601adfb9e7584f6ab141dc910d86cfc5.png]

### 数据库查询实现算法 ###

#### 一趟扫描算法 ####

### 数据库查询优化技术 ###

#### 思路 ####

![在这里插入图片描述][2dc42b613e874cedbc8b668df2b8201d.png]  
![在这里插入图片描述][85ebff4f656543a994e1674f195026ea.png]

![在这里插入图片描述][c98832e20ef44f3499cdc1d6fe0773f2.png]

*  (1)尽可能地早做选择和投影：可使中间 结果变小，节省几个数量级的执行时间。
 *  (2)把选择与投影串接起来：一元运算序 列可一起执行，只需对整个关系扫描一遍。
 *  (3)把投影与其前或后的二元运算结合 起来：在第一次用关系时去掉一些无关属性， 可以避免多次扫描整个关系。
 *  (4)把某些选择与其前的笛卡尔积合并 成一个连接：当R×S前有选择运算且其中有 条件是R、S属性间比较的运算时，可将其转化 为连接运算可节省时间。
 *  (5)执行连接运算前对关系做适当预处 理：文件排序、建立临时索引等，可使两关系 公共值高效联接。
 *  (6)找出表达式里的公共子表达式：若 公共子表达式结果不大，则预先计算，以后可读 入此结果，节时多，尤当视图情况下有用。

#### 关系代数操作交换的等价性 ####

关系代数： 并，差，积，选择，投影

**等价**：

![在这里插入图片描述][16f2d9fa361c43259c796762ca0e4cfa.png]

##### 关系交换定理 #####

1.  连接与连接，积与积的交换律  
    ![在这里插入图片描述][b61d4ff30cda4bf68d3b9a016a456c71.png]

> 通常，我们选择结果集合小的表达式，先装入内存

1.  连接与连接、积和积的结合律

![在这里插入图片描述][730cfe58f8fd4808aa60f7d52d95f6e7.png]

> 通常，我们选择结果集合小的表达式，先装入内存

1.  投影串接律

![在这里插入图片描述][0b929f6a46534e32adf1de8390eb8d38.png]

1.  选择串接律

![在这里插入图片描述][6c29f60fb48948be8d7bec318b1d6781.png]

1.  选择和投影交换律

![在这里插入图片描述][cd645e267829420daf37819f92f22d31.png]

1.  选择和积的交换律  
    ![在这里插入图片描述][62f5436edb3b418e874b8a0e96026aa0.png]
2.  投影和积的交换律

![在这里插入图片描述][9922aeda24a54bf0aaa8f11876bb1ec6.png]

1.  选择和并的交换律

![在这里插入图片描述][dc19338e5f964b8e9439e5be5385360e.png]

1.  选择和差的交换律

![在这里插入图片描述][2aa0e9833769424081a4d6567e9dceee.png]

1.  投影和并的交换律

![在这里插入图片描述][b9e46453f3784bd3a46f06a19c1a321e.png]

#### 查询优化算法及示例 ####

![在这里插入图片描述][e0458ef44438413bb4a71d0056deb440.png]

#### 物理层优化 ####

#### 代价估算 ####

[62739fb0bdc54d99bb056d77e8966a4b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/5c426bb6e91f455682ac79898f81badd.png
[25796fae2c17418f9d369fc977e6ba11.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/f6a8d186e5034e8aa857b8f580ddd5b8.png
[47bade3105b54a1daab5b9813c2463d1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/a04f992132fc434c8a390254c224727c.png
[5450dce04c90411986dfe24b72ca727c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/bd82552e1c9741b69ba77e8f6039f6fc.png
[24557bc28bbc41b591ad2aa0b3fe6451.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/945150936281479da50c0ed1440fbe12.png
[84283d19a3794136ab4759db98d7d7fa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/5ddcb8c6a93541f9aff329905d0ab7f8.png
[21c74ceaf7924492872b25ddabd82cfd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/bcaa70e174234dceb4d13ed19b26eecb.png
[6a5d7adca14547fab665ca18f53a983b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/2da301a0026d4831ad6bca03850446ca.png
[f7884d91d4bf4534af314b94a3a38538.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/f80a3e58d81f4f29bec21ea7f48796bf.png
[5a5017cce3c5468fa06b630fcea70d21.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/bbf3c80e43024349a679397ba35586a3.png
[3c557feb92b54cbe9efba11cf1793ba8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/e8a7752fe88744d684204f1e5b2a7b4d.png
[601adfb9e7584f6ab141dc910d86cfc5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/2530aa118b9e454e8e02421311ab1a19.png
[2dc42b613e874cedbc8b668df2b8201d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/3b37bae6ff7549f7b30a95947ee0cc3e.png
[85ebff4f656543a994e1674f195026ea.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/7eb6b97f35854a19b5f9a212fb443c20.png
[c98832e20ef44f3499cdc1d6fe0773f2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/284afa0955694a5091d41771122ca0d1.png
[16f2d9fa361c43259c796762ca0e4cfa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/a77b73fadf5d4d9d98be186d2af339bd.png
[b61d4ff30cda4bf68d3b9a016a456c71.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/46ad27b1714343248e1642467a3da010.png
[730cfe58f8fd4808aa60f7d52d95f6e7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/7619a0d16fe944238377e34b7c99c610.png
[0b929f6a46534e32adf1de8390eb8d38.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/fff234a64974452b821e33c0f3ddca2e.png
[6c29f60fb48948be8d7bec318b1d6781.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/fa450e208e2643afb157ce7d3b228075.png
[cd645e267829420daf37819f92f22d31.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/d87786a28fcf4121b8f6415699f128ca.png
[62f5436edb3b418e874b8a0e96026aa0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/99878ed70f5a4f82b7b578daafe1ce69.png
[9922aeda24a54bf0aaa8f11876bb1ec6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/c6f0826b9c204b00b1db509d3719a2b3.png
[dc19338e5f964b8e9439e5be5385360e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/d39d2930810a47018f196b7700558ce0.png
[2aa0e9833769424081a4d6567e9dceee.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/a0e0db61777d4cd2b8a236f47e5066b8.png
[b9e46453f3784bd3a46f06a19c1a321e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/fd4db37d0f574d429d9ec20fb51b0517.png
[e0458ef44438413bb4a71d0056deb440.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/616ca00fb4b94fd580b29530385bd07a.png