网站开发角色分配权限,wordpress改站点标题,附近卖建筑模板市场,建筑工程网格化区域划片管理制度第一章#xff1a;DBMS系统概述 1
数据库管理系统将满足#xff1a;
用户使用专门的数据定义语言来创建新的数据库并指定其模式#xff08;数据的逻辑结构#xff09;用户使用适当的语言查询数据大量的数据长期地进行存储数据具有持久性#xff0c;从故障、多种类型的错…
第一章DBMS系统概述 1
数据库管理系统将满足
用户使用专门的数据定义语言来创建新的数据库并指定其模式数据的逻辑结构用户使用适当的语言查询数据大量的数据长期地进行存储数据具有持久性从故障、多种类型的错误或者故意滥用中进行恢复。多个用户同时对数据进行访问孤立性原子性
关系数据库系统关系数据库的程序员并不需要关心存储结构。查询可以用很高级的语言来表达这样可以极大地提高数据库程序员的效率。
数据操纵语言(DML)查询响应
查询编译器对查询进行分析和优化得到的查询计划传给执行引擎。执行引擎向资源管理器发出一系列对小的数据单元通常是记录或关系的元组(tuple))的请求。查找数据的请求被传送给缓冲区管理器。从持久地存储数据的辅助存储器磁盘中将数据的适当部分取到主存的缓冲区中。缓冲区管理器和存储管理器进行通信以从磁盘获取数据存储管理器的任务是控制数据在磁盘上的放置和在磁盘与主存之间的移动。
事务处理孤立地执行的单位一个或多个数据库操作组成一组称作事务1. 并发控制管理器或调度器它负责保证事务的原子性和孤立性。2. 日志和恢复管理器它负责事务的待久性。 第二章辅助存储管理
加速数据库操作的关键技术是安排好数据 使得当某一个磁盘块中有数 据被访问时 大约在同时很有可能该块上的其他数据也需要被访问。数据库中的任何修改都不能认为是最终有效的直到该修改被存储到非易失性的辅助存储器中。倘若一部分磁化层被以某种方式损坏那么那些包含这个部分的整个扇 区也不能再使用。 加速对辅助存储器的访问
1/0开销的主导地位块访问磁盘1/0)次数就是算法所需要的时间的近似值 而且应该被最小化。
将要一起访问的块放在同一柱面上这样我们可以经常避免寻道时间也可能避免旋转延迟。将数据分隔存储在几个相对较小的磁盘上而不是放在一个大磁盘上。让更多的磁头组设备分别去访问磁盘块可增加在单位时间内的磁盘块访问数量。镜像“磁盘一把两个或者更多的数据副本放在不同的磁盘上。该策略除了可以保存数 据以备某个磁盘可能坏掉如同将数据分隔存储几个磁盘上可以让我们一次访问多个磁盘块。加快读取速度不能加快存储速度在操作系统、DBMS或磁盘控制器中使用磁盘调度算法选择读写所请求的块的顺序。预先将预期被访问的磁盘块取到主存储器中。 磁盘故障
分为间断性故障和介质损坏以及磁盘崩溃
间断性故障
磁盘块的正确内容没有被传送到磁盘控制器中。判断校验和。 每个扇区有若干个附加位称为校验和 (checksum)
奇偶校验单位/多位
关千大规模的错误任何一个奇偶位将 检测出错误的可能性是50%, 8位都检测不 出错误的机会仅仅是1/2^8 如果我们用n个独立位作为校验码漏掉一个错误的机会仅为1/2^n
稳定存储的策略 稳定存储策略是一种数据冗余技术用于提高数据存储的可靠性和容错能力。比如在写时发生故障写的数据丢失同时原数据也遭到破坏。成对的扇区数据被存储在成对的扇区中每对扇区包含相同的数据内容X。这些扇区被称为“左”拷贝XL和“右”拷贝XR。奇偶校验每个拷贝使用额外的奇偶校验位来增强数据的完整性。写策略
步骤1首先将数据X写入XL。如果写入过程中奇偶校验位正确认为写入成功否则需要重新写入直到成功或确定存在介质故障。步骤2如果XL写入成功对XR重复步骤1的操作。
介质故障处理如果在多次尝试后数据仍然无法写入某个扇区可以认为该扇区存在介质故障。此时应使用备用扇区来代替故障扇区。读策略
交替尝试读取XL和XR直到获得一个“好”的值即奇偶校验位正确的值。如果在预设的尝试次数内无法获得好值可以认为数据X是不可读的。
容错能力通过成对存储和奇偶校验该策略能够容忍单个扇区的故障同时保持数据的完整性。
稳定存储的错误处理
写故障 在写入数据X的过程中如果发生系统故障如电源断电可能导致X在主存中丢失同时正在写入的X的拷贝也可能被破坏。系统恢复后我们可以通过测试XL和XR的状态来确定X的值。可能的情况包括
a) 写XL时发生故障
如果故障发生在写入XL的过程中我们将发现XL的状态是“坏”。由于我们从未写入XR它的状态将是“好”除非XR同时发生介质故障这种情况可能性很小。这样我们可以从XR读取X的旧值并可以将XR复制到XL以修复XL的故障。
b) 写XR后发生故障
如果故障发生在写入XR之后我们预计XR将有状态“好”并且我们可以从XR读取X的新值。由于XL可能包含部分新值和部分旧值我们需要将XR复制到XL中以确保两个扇区的数据一致性。
冗余技术
将多个物理磁盘驱动器组合成一个或多个逻辑单元以提高数据存储性能和提供容错能力的技术。
RAID1
一个数据盘一个冗余盘。
RAID4奇偶块
多个数据盘一个冗余盘
读操作
从数据盘读取数据块与从冗余盘读取数据块在操作上没有区别。读操作可以直接从任何一个数据盘进行因为所有数据盘上的数据块内容是一致的。
写操作
当向数据盘写入一个新的数据块时不仅需要更改该数据盘上的块还需要更新冗余盘上相应的奇偶校验块以保持数据的奇偶校验一致性。
朴素的写方法
读取所有n个数据盘上相应的数据块。将这些数据块进行模2加法以计算新的奇偶校验值。重写冗余盘上的块以反映新的奇偶校验信息。这种方法涉及n-1次数据盘的读操作1次数据盘的写操作以及1次冗余盘的写操作总共是n1次磁盘操作。
改进的写方法
只关注正在被重写的数据块i的旧版本和新版本。通过取旧版本和新版本的模2加法确定哪些位发生了变化从0变为1或从1变为0。由于变化总是使1的总数从一个偶数变为一个奇数只需更改冗余块中相应位置的位即可恢复奇偶校验的一致性。这种方法减少了磁盘操作次数提高了写操作的效率。
写操作的步骤
读取要被改变的数据盘上的旧数据块。读取冗余盘上相应的奇偶校验块。将新数据块写入数据盘。根据新旧数据块的模2加法结果重新计算并写入冗余盘的相应块。
RAID 4级别能够在单个数据盘发生故障时保护数据不丢失并且通过奇偶校验机制实现数据的恢复。然而每次写操作都需要更新奇偶校验信息。
RAID5
旨在解决RAID 4中的写入瓶颈问题。RAID 5是为了提高写入性能而设计的它通过分布式奇偶校验来平衡各个磁盘的读写负载。在RAID 4中所有的写操作都需要访问一个专用的冗余磁盘来更新奇偶校验信息这成为系统的瓶颈。RAID 5使用分布式奇偶校验即奇偶校验信息不是存储在一个专用的冗余磁盘上而是分散存储在所有磁盘上。在RAID 5中写操作不需要总是访问同一个磁盘而是根据数据块的位置动态选择奇偶校验磁盘从而提高了写入性能。
多个盘崩溃时的处理RAID6
海明码于检测和纠正单个位的错误在某些情况下可以检测两个错误并纠正一个【官方双语】汉明码Pa■t1如何克服噪■_哔哩哔哩_bilibili【官方双语】汉明码part2优雅的全貌_哔哩哔哩_bilibili1.盘5的位是盘1、2、3 相应位的模2和。2.盘6的位是盘1、2、4相应位的模2和。3.盘7的位是盘1、3、4相应位的模2和。读从任何一个数据盘中正常地读数据。冗余盘可以不予理睬。写为了写某个数据盘的一个块我们要求那个块的新版与旧版的模2和。得出的结果与对应的冗余块进行模2和更新。
2.6 指针混写
处理数据项在不同存储层次如主存储器和二级存储器之间的移动时的指针地址转换问题指针混写是块从第二级存储器移到内存中时将数据库地址空间转换为虚拟地址空间。 自动混写
优点高效性一旦块被加载到内存所有可识别的指针立即被混写减少了后续操作中查找和混写指针的延迟。简化编程开发者无需担心指针的混写和解混写DBMS自动处理。缺点资源浪费如果某些混写的指针从未被访问则混写这些指针的时间和资源就被浪费了。复杂性需要复杂的机制来识别和定位块内的所有指针可能涉及模式识别或额外的数据结构。
按需混写
优点资源节约只在指针被实际使用时才进行混写避免了不必要的混写操作。灵活性可以根据访问模式动态调整混写策略。缺点延迟首次访问未混写的指针时会有额外的混写开销。编程复杂性开发者需要更仔细地管理指针的混写状态确保在需要时能够正确混写。
不混写
优点简单性无需实现复杂的混写和解混写逻辑。灵活性指针始终以数据库地址形式存在便于处理和跟踪。缺点性能下降每次访问数据库地址时都需要通过转换表查找对应的内存地址增加了访问延迟。内存管理限制数据块无法像混写时那样被有效地固定在内存中。混写的程序控制优点灵活性开发者可以根据具体的应用场景和需求来控制混写行为。性能优化对于频繁访问的数据块可以显式地进行混写以提高性能。缺点编程复杂性需要开发者对应用的访问模式有深入的了解并编写额外的代码来控制混写行为。错误风险不恰当的混写控制可能导致性能下降或资源浪费。
块返回磁盘
转换表Translation Table存储了内存地址memAddr和数据库地址dbAddr之间的映射关系。这种映射允许系统在需要时将内存中的地址转换回它们在数据库即磁盘上的原始地址或者在数据从磁盘加载到内存时执行相反的转换。为了加速查询过程通常在转换表上建立索引。 索引 常见的索引结构包括散列表Hash Table、B树B-Tree或平衡树如AVL树、红黑树等。 _散列表_在提供快速查找方面具有优势特别是对于等长键的查找。然而散列表在处理键的删除和重新插入时可能会遇到性能问题尤其是当发生哈希冲突时。 _B树和类似的平衡树结构_则更适合于需要支持范围查询和频繁更新的场景。它们通过保持树的平衡来确保查询、插入和删除操作的时间复杂度保持在对数级别。 被钉住的记录和块
如果内存中一个块当前不能安全地被写回磁盘称它为被钉住的。内存中B1有一个混写指针指向B2。B2移回磁盘时B1的指针成为悬挂指针我们称B2是被钉住的。我们需要解混写指向B2的所有指针。因此对每一个有数据项在内存中的数据库地址转换表必须记录指向内存中存在那个数据项的混写指针的位置。为了解决悬挂指针的问题系统需要维护一个转换表。这个表记录了每个在内存中有数据项的数据库地址以及指向这些数据项的混写指针在内存中的位置。当某个内存块如B2需要被写回到磁盘时系统会使用这个转换表来找到所有指向该内存块的混写指针并将它们更新为新的有效值如果B2的数据在磁盘上有了新的位置或删除它们如果B2的数据不再需要被引用。
在转换表中使用附加链表
在这种方法中转换表不仅仅存储数据库地址到内存地址的映射还附加了一个链表来跟踪所有引用该内存地址的混写指针。这个链表实际上是附加在转换表中与特定内存地址相关联的表项上的。当需要将一个内存块如B2写回磁盘时系统会查找转换表中B2的内存地址memAddr对应的条目。然后它会遍历附加在该条目上的链表找到并更新或删除所有引用B2的混写指针。
在指针自身空间中创建链表
这种方法假设内存地址或指针大小比数据库地址短得多因此有足够的空间在指针本身内部来存储额外的信息。每个指针不再仅仅是一个内存地址而是被扩展为一个结构体包含至少两个部分a)被混写的指针或数据库地址指向实际数据的原始数据库地址。b)链表指针指向一个链表节点该节点是包含所有引用该指针的混写指针出现的链表的一部分。链表内容每个链表节点包含对另一个混写指针实际上是另一个扩展的指针结构体的引用这些混写指针都指向同一个内存地址。 2.7 变长数据和记录 2.7.1 具有变长字段的记录
将所有定长字段放在变长字段之前然后我们在记录首部写人以下信息:1.记录长度。2.指向所有除第一个之外的变长字段起始处(即偏移量)的指针(我们知道第一个变长字段就紧跟在定长字段之后)。
2.7.2 具有重复字段的记录 方法一
将字段F的每次出现放在一起在记录首部放一个指针让它指向字段F出现的第一个位置。我们可用以下方法找到字段F出现的所有位置:令字段F的一次出现占用的字节数为L然后在字段F的偏移量上加上L的所有整数倍数从0开始而后L、2L、3L依此类推。最后我们到达F后面的字段的偏移量或记录末尾至此停止。
方法二
另一种表示方法是保持记录定长而将变长部分(无论它是变长字段还是重复次数不确定的字段)放在另一个块上。在记录本身中我们存储:1.指向每一个重复字段开始处的指针。2.重复次数或者重复结束处。优点保持记录定长。可以更有效地对记录进行搜索使块首部的开销最少记录能很容易地在块内或块间移动。缺点另一方面将变长部分存储在另一个块中增加了为检査一条记录的所有部分而进行的磁盘 //0 数目。
2.7.4 不能装入一个块中的记录
如果记录能跨块则每一条记录和记录片段需要一些额外的首部信息:1.每一条记录或片段首部必须包含一个二进制位指明它是否为一个片段。2.如果它是一个片段则它需要几个二进制位指明它是否为它所属的记录的第一个或最后一个片段。3.如果对同一条记录有下一个和/或前一个片段则片段需要指向这样一些其他片段的指针。记录片段2-a的首部包含一个指明它是片段的标记一个指明它是记录的第一个片段的标记和一个指向下一个片段2-b的指针。同样2-b首部指明它是记录的最后一个片段且有一个指向前一个片段2a的反向指针。 2.7.5 BLOB大数据量存储
连续存储 理想情况下BLOB数据应该连续存储在磁盘上以减少磁头移动的次数从而提高数据读取效率。然而随着BLOB数据量的增加找到足够大的连续空间可能会变得困难。链表存储 当无法找到足够的连续空间时BLOB数据可能被分割并存储在磁盘的多个不连续块中这些块通过链表连接起来。这种方式虽然解决了空间分配的问题但可能会增加数据检索时的磁盘I/O操作次数降低性能。多磁盘存储 对于非常大的BLOB数据可以考虑将其分布在多个磁盘上。这样当进行数据检索时可以并行地从多个磁盘读取数据块显著提高读取速度。这种方法特别适用于需要实时处理大量数据的场景如视频流服务。按需传输 数据库系统可以根据客户端的播放速度实时地传输BLOB数据块而无需等待整个文件完全加载。这种方式极大地减少了延迟提高了用户体验。
2.7.6列存储
列存储Column-Oriented Storage是一种数据库存储技术与传统的行存储Row-Oriented Storage方式相对。在列存储中数据库表中的数据不是按行存储而是按列存储。列存储的优势数据压缩 由于同一列中的数据通常具有相似的数据类型和值域因此可以实现高效的数据压缩。例如在性别gender列中如果只有“男”和“女”两种值则可以使用非常少的位来表示每个值从而大大减少存储需求。更快的查询速度 当查询只涉及表中的少数几列时列存储数据库可以只读取这些列的数据而无需读取整行数据。这减少了I/O操作的数量从而提高了查询速度。更好的缓存利用率 由于相同列的数据在物理上连续存储因此它们更有可能被缓存在一起。这提高了缓存的利用率因为一旦某个列的数据被读入缓存后续对该列的查询就可以直接从缓存中获取数据。更高效的聚合操作 列存储特别适合于执行聚合操作如SUM、AVG、COUNT等因为相同列的数据已经聚集在一起可以直接进行计算而无需跨行访问。
2.8 记录的修改 2.8.1 插入
定位块-检查空间-空间足够-滑动记录-更新偏移量表-插入新记录-添加新指针(可以通过偏移量表来访问它了)
块空间不够插入新数据
在“邻近块”中找空间
步骤找到逻辑上或物理上紧随块B的下一个块如块B’。检查块B’是否有足够的空间。如果有将块B中最后一个记录或几个记录移动到块B’的开始位置为新记录腾出空间。更新块B和块B’的偏移量表如果使用和任何必要的索引。将新记录插入到块B的适当位置。这种方法的好处是保持了记录的物理顺序减少了数据碎片但可能需要移动大量数据以腾出空间。
创建一个溢出块
当在邻近块中找不到足够的空间时或者为了优化性能而减少数据移动可以创建一个溢出块来存储那些在当前块中无法容纳的额外记录。步骤当块B没有足够的空间时创建一个新的溢出块。在块B的首部或某个预定义的位置添加一个指针指向这个溢出块。将原本应该插入到块B但由于空间不足而无法存储的记录放入溢出块中。优点减少了因插入操作而需要移动的数据量缺点可能会增加查询操作的复杂性因为查询可能需要遍历多个溢出块来找到所需的记录。此外过多的溢出块还可能导致性能下降因为需要读取更多的磁盘块来完成查询。
2.8.2 删除
删除记录并回收空间如果记录可以滑动那么在删除一条记录后可以将块中的其他记录向前滑动以填补被删除记录留下的空白。这样可以使块内的空间更加紧凑减少碎片。在使用偏移量表的情况下删除记录后需要更新偏移量表中的指针。如果记录不能滑动在块首部维护一个可用空间列表。这个列表记录了块中所有可用的空间区域及其大小。当删除一条记录时将该记录所占用的空间区域添加到可用空间列表中。当需要插入新记录时可以从这个列表中查找合适的空间区域。
第三章索引结构 3.1 索引基础结构
索引它以一个或多个字段的值为输人并能快速地找出具有该值的记录。索引使我们只需查看所有可能记录中的一小部分就能找到所需记录。建立索引的字段(组合)称为查找键。稠密索引为数据文件中的每个记录都创建一个索引项。这种索引方式提供了最精确的位置信息但会占用更多的存储空间。稀疏索引不是为数据文件中的每个记录都创建索引项而是选择性地为某些记录如每个数据块的首个记录创建索引项。稀疏索引减少了索引文件的大小但可能需要在检索时执行额外的步骤来定位具体的数据记录。主索引也称为聚集索引它决定了数据文件中记录的物理存储顺序。主索引能够直接定位到数据文件中的记录位置因此查询效率很高。在数据库中通常会在主键上建立主索引。辅助索引非聚集索引不决定数据记录的物理存储顺序仅提供查找键与数据记录之间的逻辑关联。辅助索引通常用于非主键列以提高基于这些列的查询效率。顺序文件顺序文件是对关系中的元组按主键进行排序而生成的文件。关系中的元组按照这个次序分布在多个数据块中。
3.1.2 稠密索引
如果记录是排好序的我们就可以在记录上建立稠密索引它是这样一系列存储块:块中只存放记录的键以及指向记录本身的指针存储索引文件比存储数据文件所需存储块要少得多。通过使用索引文件我们每次査询只用一次 I/0操作就能找到给定键值的记录。查找索引更快1.索引块数量通常比数据块数量少。 索引块数量通常比数据块数量少的原因主要基于以下几点 键与记录大小的差异在数据库中一个记录record通常包含多个字段如姓名、地址、电话号码等这些字段合起来可能占用相当多的存储空间。相比之下索引中存储的仅仅是键key以及指向记录的指针或地址。键通常是记录中的一个或几个字段因此其大小远小于整个记录。由于索引块中只存储键和指针所以每个索引块能够存储的索引项即键和指针的组合数量相对较多。 压缩性由于索引中的键通常是按顺序存储的这允许数据在物理存储上更加紧凑。此外如果键的类型是固定的如整数或固定长度的字符串那么索引块中的空间可以得到更有效的利用因为不需要为每个键动态分配空间。 索引的稀疏性索引不需要为数据集中的每个记录都创建一个索引项。特别是在面对大量数据时完全索引即每个记录都有一个索引项可能会非常庞大且效率低下。相反索引可以设计为稀疏的即只在关键位置如数据块的起始处或特定间隔创建索引项。这样索引文件就会比完全索引要小得多。 多层索引结构对于非常大的数据集通常会采用多层索引结构如B树、B树等。在这些结构中最底层的索引块叶子节点直接指向数据记录而更高层的索引块则指向下一层的索引块。这种多层结构进一步减少了顶层索引块的数量因为每个上层索引块能够覆盖多个下层索引块或数据块。 2.由于键被排序我们可以使用二分查找法来查找K。若有几个索引块我们只需查找log2^n 个块。3.索引文件可能足够小以至可以永久地存放在主存缓冲区中。要是这样的话查找键K时就只涉及主存访问而不需执行 I/0 操作。
3.1.3 稀疏索引
稀疏索引只为数据文件的每个存储块设一个键-指针对它比稠密索引节省了更多的存储空间但查找给定值的记录需更多的时间。只有当数据文件是按照某个查找键排序时在该查找键上建立的稀疏索引才能被使用而稠密索引则可以应用在任何的査找键。
3.1.4 多级索引 3.1.5 辅助索引 有一个书架上面放了很多书。这些书是按照某种顺序比如书名的字母顺序排列的这个顺序就是书的主索引类似于数据库中的聚簇索引。你按照这个顺序找书会很快因为书是按照这个顺序摆放的。 但是有时候你可能不想按照书名来找书而是想按照作者名、出版年份或者书的主题来找。这时候如果书架上没有额外的标记或指示来帮助你快速找到这些书你就会很费劲。 在数据库中这就是辅助索引的作用。辅助索引就像是书架上的标签或指示牌它们告诉你“如果你想找作者名是XXX的书可以去看这里如果你想找出版年份是YYYY的书可以去看那里。” 具体来说辅助索引在数据库中是一个额外的数据结构它存储了表中某些列的值比如作者名、出版年份等以及这些值对应的行在表中的位置通常是一个指向主键的指针因为主键能够唯一标识表中的每一行。 当你根据非主键列比如作者名来查询数据时数据库会使用辅助索引来快速定位到这些列的值对应的行。首先数据库在辅助索引中查找你指定的值比如作者名找到后它会获取到对应的行位置比如主键值然后再根据这个位置去聚簇索引中找到完整的行数据。 需要注意的是虽然辅助索引可以提高查询效率但它们也会占用额外的存储空间并且在数据发生变化如插入、删除、更新时数据库需要同时更新辅助索引这可能会增加额外的维护成本。 **辅助索引总是稠密索引**辅助索引的索引项与字段值的数量是相对应的呈现出一种“稠密”的状态。如果辅助索引是稀疏的即只为字段的某些值建立索引项那么就无法保证快速定位到所有相关的记录。
3.1.7 辅助索引中的间接
每个查找键K有一个键-指针对指针指向一个桶文件该文件中存放K的桶。从这个位置开始直到索引指向的下一个位置其间指针指向索引键值为K的所有记录。辅助索引上使用间接层也有一个重要的好处:我们通常可以在不访问数据文件记录的前提下利用桶的指针来帮助回答一些查询。特别是当查询有多个条件而每个条件都有一个可用的辅助索引时我们可以通过在主存中将指针集合求交来找到满足所有条件的指针然后只需要检索交集中指针指向的记录。这样我们就节省了检索满足部分条件而非所有条件的记录所需的 I/0开销。辅助索引求交集
3.1.8 文档检索和倒排索引
传统的数据库索引该索引的键是文档ID而值是文档中出现的词或词频、位置等信息。然**倒排索引**索引的键是文档中出现的词或称为“词条”而值则是包含该词的文档ID列表或称为“文档集合”。这样当我们想要查找包含某个特定词的文档时就可以直接通过该词作为键来查找对应的文档ID列表而无需遍历所有文档的索引项。文档检索 一个文档可被看成是关系 Doc的元组。这个关系有很多的属性每个属性对应于文档可能出现的一个词。每个属性都是布尔型的–表明该词在该文档出现还是没有出现。因此这一关系模式可以被看作: Doc(hasCathasDog,...)br / 其中 hasCat 取值为真当且仅当该文档中至少出现一次“cat这个词。关系 Doc 的每个属性上都建有辅助索引。不过我们不必费心为属性值为FALSE的元组建索引项;相反索引只会将我们带到出现该词的那些文档。也就是说索引中只有查找键值为 TRUE的索引项。 我们不是给每个属性(即每个词)建立一个单独的索引而是把所有的索引合成一个称为倒排索引。这个索引使用间接桶来提高空间利用率正如3.1.7节中讨论的那样。
桶文件中指针可以是:1.指向文档本身的指针。2.指向词的一个出现的指针。在这种情况下指针可以是由文档的第一个块和一个表示该词在文档中出现次数的整数构成的对。
当我们使用指针“桶”指向每个词的多次出现的时候我们可能就会想扩展这个想法使桶数组包含更多有关词的出现的信息。这样桶文件本身就成了有重要结构的记录集合。
3.2 B-树 B-树能自动地保持与数据文件大小相适应的索引层次。 对所使用的存储块空间进行管理使每个块的充满程度在半满与全满之间。 3.2.1 B-树的结构
一颗m阶的B树定义如下1每个结点最多有m-1个关键字。2根结点最少可以只有1个关键字。3非根结点至少有Math.ceil(m/2)-1个关键字。m/2向上取整减去14每个结点中的关键字都按照从小到大的顺序排列每个关键字的左子树中的所有关键字都小于它而右子树中的所有关键字都大于它。5所有叶子结点都位于同一层或者说根结点到每个叶子结点的长度都相同。
3.2.2 B-树的应用
B-树是用来建立索引的一种强有力的工具。它的叶结点上指向记录的一系列指针可以起到任何一种索引文件中指针序列的作用。
3.2.5 B-树的插入
1、插入一个元素时首先在B树中是否存在如果不存在即比较大小寻找插入位置在叶子结点处结束然后在叶子结点中插入该新的元素2、如果叶子结点空间足够这里需要向右移动该叶子结点中大于新插入关键字的元素如果空间满了以致没有足够的空间去添加新的元素则将该结点进行“分裂”将一半数量的关键字元素分裂到新的其相邻右结点中中间关键字元素上移到父结点中当然如果父结点空间满了也同样需要“分裂”操作3、当结点中关键元素向右移动了相关的指针也需要向右移。如果在根结点插入新元素空间满了则进行分裂操作这样原来的根结点中的中间关键字元素向上移动到新的根结点中因此导致树的高度增加一层。
3.2.6 B-树的删除
1如果当前需要删除的key位于非叶子结点上则用后继key这里的后继key均指后继记录的意思覆盖要删除的key然后在后继key所在的子支中删除该后继key。此时后继key一定位于叶子结点上这个过程和二叉搜索树删除结点的方式类似。删除这个记录后执行第2步2该结点key个数大于等于Math.ceil(m/2)-1结束删除操作否则执行第3步。3如果兄弟结点key个数小于Math.ceil(m/2)-1则父结点中的key下移到该结点兄弟结点中的一个key上移删除操作结束。否则将父结点中的key下移与当前结点及它的兄弟结点中的key合并形成一个新的结点。原父结点中的key的两个孩子指针就变成了一个孩子指针指向这个新结点。然后当前结点的指针指向父结点重复上第2步。有些结点它可能即有左兄弟又有右兄弟那么我们任意选择一个兄弟结点进行操作即可。 删除27。从上图可知27位于非叶子结点中所以用27的后继替换它。从图中可以看出27的后继为28我们用28替换27然后在28原27的右孩子结点中删除28。删除后的结果如下图所示。 删除后发现当前叶子结点的记录的个数小于2而它的兄弟结点中有3个记录当前结点还有一个右兄弟选择右兄弟就会出现合并结点的情况不论选哪一个都行只是最后B树的形态会不一样而已我们可以从兄弟结点中借取一个key。所以父结点中的28下移兄弟结点中的26上移,删除结束。结果如下图所示。 3.2.7 B-树的效率
B-树的效率磁盘I/O次数、树的层数、节点的分裂与合并、以及针对查找、插入和删除操作的优化。磁盘I/O次数B-树的主要优势之一是它减少了磁盘I/O次数这是因为它通过保持树的高度尽可能低来实现。在B-树中每个节点可以包含多个键和子指针这允许树在保持相同数量元素的情况下具有更少的层数。对于大多数数据库和文件系统应用三层B-树足以满足需求因为节点容量如每块340个键-指针对可以非常大这取决于块的大小和键的大小。树的层数B-树的层数决定了查找记录所需的最大磁盘I/O次数。在三层B-树中最多需要三次磁盘I/O从根到叶节点加上一次读取数据记录本身。然而通过缓存技术如将根节点或某些中间节点常驻内存这个次数可以进一步减少。例如如果根节点被缓存那么查找将只需要两次磁盘I/O。节点的分裂与合并在B-树中节点的分裂和合并是罕见的特别是当节点容量足够大时。当节点需要分裂时大多数操作都局限于叶节点这减少了对树结构整体的影响。此外分裂和合并操作通常只涉及两个节点一个要被分裂的节点和一个新的或已有的节点以及它们的父节点这进一步限制了操作的复杂性。插入和删除插入和删除操作可能需要额外的磁盘I/O来更新数据记录和索引本身。然而通过适当地维护B-树的平衡如通过旋转和重新分布节点中的键可以最小化这些操作的影响。在某些实现中如果删除操作导致节点中的键数低于最小要求但预计该节点很快会再次填满那么可能不对该节点进行合并或重新分配键而是简单地留下该节点。删除标记在处理删除操作时一种常见的策略是使用“删除标记”而不是实际从B-树中删除条目。这样做的好处是即使记录已从数据库中删除B-树索引仍然可以保留对该记录的引用尽管它已被标记为删除。这有助于维护索引的完整性并允许通过B-树索引查询已删除记录的状态例如检查记录是否已被删除。
3.3 散列表
散列函数散列函数 ( h ) 接受一个查找键Key作为输入并计算出一个介于 0 到 ( B-1 ) 之间的整数其中 ( B ) 是桶Bucket的数目。桶桶是散列表中用于存储数据的单元。每个桶可以存储多个数据项通常使用链表来实现。桶数组是一个序号从 0 到 ( B-1 ) 的数组每个数组元素对应一个桶。存储当需要存储一个记录时首先计算其查找键 ( K ) 的散列值 ( h(K) )。然后将该记录链接到桶号为 ( h(K) ) 的桶表中。
3.3.1 辅存散列表
有的散列表包含大量记录记录如此之多以至于它们主要存放在辅助存储器上这样的散列表在一些细小而重要的方面与主存中的散列表存在区别
3.3.2 散列表的插入
查找键为K的新记录需要被插入时计算h(K)。如果桶号为h(K)的桶还有空间我们就把该记录存放到此桶的存储块中。其存储块没有空间时存储到块链上的某个溢出块中如果桶的所有存储块都没有空间:我们就增加一个新的溢出块到该桶的链上。
3.3.5 可扩展散列表
它在简单的静态散列表结构上主要增加了:1.为桶引人了一个间接层即用一个指向块的指针数组来表示桶而不是用数据块本身组成的数组来表示桶。2.指针数组能增长它的长度总是2的幂因而数组每增长一次桶的数目就翻倍。3.并非每个桶都有一个数据块;如果某些桶中的所有记录可以放在一个块中那么这些桶可能共享一个块。4.散列函数h为每个键计算出一个K位二进制序列该K足够大比如32。但是桶的数目总是使用从序列第一位或最后一位算起的若干位此位数小于K比如说是i位。也就是说当i是使用的位数时桶数组将有2^i个项。3.3.6 可扩展散列表的插入计算哈希值首先计算要插入的键的哈希值 h(K)。定位桶数组项使用哈希值 h(K) 的前 i 位来确定桶数组中的项。这里的 i 是当前用于索引桶数组的全局位数global bit position。检查存储块空间如果找到的存储块B有足够的空间来存放新记录则直接插入新记录。如果存储块已满即没有空间则需要进行分裂或桶数组扩展。处理存储块满的情况如果 j i 将存储块 B 分裂成两个新的存储块。 根据新记录的哈希值的第 (j1) 位来决定其归属的存储块0 或 1。 更新存储块的小方块中的位数为 (j1)表示现在使用更多的位来确定存储块的成员资格。 调整桶数组中的指针根据新记录的哈希值的第 (j1) 位来指向正确的存储块。 如果分裂后仍然有存储块过满则继续以更高的 j 值重复分裂过程。 如果 j i 桶数组的长度翻倍并创建一个新的桶数组。 对于旧桶数组中的每个项 w在新桶数组中创建两个项 u0 和 u1分别通过在 w 后面添加 0 和 1 来获得。这两个新项都指向原 w 项指向的存储块。 然后像 j i 的情况一样分裂过满的存储块。 3.3.7 线性散列表
可扩展散列缺点1.当桶数组需要翻倍时要花费很长的时间。2.当桶数翻倍后它在主存中可能就装不下了或者把其他的一些我们需要保存在主存的数据挤出去。其结果是一个运行良好的系统可能突然之间每个操作所需磁盘I/O开始大增。3.如果每块的记录数很少那么很有可能某一块的分裂比在逻辑上讲需要分裂的时间提前许多。线性散列解决其缺点
桶数n的选择总是使存储块的平均记录数保持与存储块所能容纳的记录总数成一个固定的比例如 80%。由于存储块并不总是可以分裂所以允许有溢出块尽管每个桶的平均溢出块数远小于1。用来作桶数组项序号的二进制位数是1og2^n向上取整其中n是当前的桶数。这些位总是从散列函数得到的位序列的右(低位)端开始取。假定散列函数值的i位正在用来给桶数组项编号且有一个键值为K的记录想要插人到编号为 a,…a; 的桶中;即 a,…a 是h(K)的后i位。那么,把 a,a,…a;当作二进制整数设它为 m。如果mn那么编号为m的桶存在并把记录存入该桶中。如果 n≤m2i那么m桶还不存在因此我们把记录存人桶m-2(i-1)也就是当我们把a1(它肯定是1)改为0时对应的桶。
3.3.8 线性散列表的插入
确定桶号使用哈希函数 h(K) 计算键 K 的哈希值。取 h(K) 序列末尾的 i 位来表示桶号 m。这里i 是一个与当前散列表容量相关的参数可能基于 n当前桶的数量的某种属性如 log2(n) 的整数部分但具体取决于实现。如果 m n则直接将记录插入到桶 m 中。如果 m ≥ n则通过 (m - 2^(i-1)) % n来计算实际的桶号并插入记录。处理溢出如果桶已满则创建一个新的溢出块如链表节点将新记录存入该节点并将此节点链接到桶的尾部。动态扩容和桶分裂每次插入后检查当前记录总数与 n 的比例是否超过了某个阈值 r/n。如果超过则增加散列表的容量即增加桶的数量并可能需要重新组织或分裂某些桶。如果新增加的桶号的二进制表示为 1aa…a则分裂桶号为 0aa…a 的桶。这通常意味着根据记录的后 i 位值特别是从右数起的第 i 位来重新分配记录到两个桶中。i 值的调整当 n 超过 2^i 时i1。
3.4 多维索引 3.4.2 利用传统索引执行范围查询
在处理二维范围查询时尽管分别为x和y坐标构建一维B-树索引可以高效定位单维度范围内的记录但将它们用于二维查询时效率较低。因为即使每维索引能减少候选记录数量交集操作后仍需访问大量数据块导致磁盘I/O成本高昂。因此在处理多维数据时考虑使用如R树等多维索引结构以更直接地定位满足多维查询条件的记录从而提高查询性能。
3.4.1 多维索引应用
1.部分匹配查询。我们指定一维或多维上的值并查找在这些维上匹配这些值的所有点。2.范国查询。我们给出一维或多维上的范围并查找在这些范围内点的集合或者在所表示的是形状时查找出部分或全部形状在该范围内的形状的集合。3.最近邻查询。我们查找与给定点最近的点。4.where-am-查询。已知一个点我们想知道该点所处的形状若存在这样的形状的话。一个熟悉的例子是当你点击鼠标时系统决定你点击的是哪个显示元素。
3.4.2传统索引进行范围查询
首先我们通过x的B-树索引得到在x范围内的所有记录的指针。然后我们通过y的B-树索引得到在y范围内的所有记录的指针。最后求出这些指针的交集。I/O次数多。
3.5 多维数据的散列结构 3.5.1 网格文件
网格文件Grid File是一种用于多维数据索引的高效数据结构它通过在各维度上划分空间为网格状区域显著提升了多维数据查询的性能。这种划分允许将数据集划分为多个子空间或“条状”其中每个子空间由网格线界定且网格线的数量和间隔在不同维度上可灵活设置甚至在同一维度内也可不同从而实现了对多维数据的高效索引和查询处理。
3.5.2 网格文件的查找
空间划分成的每一个区域可以被看成是散列表的一个桶落人该区域的每个点的记录都存放在属于该桶的块中。如有必要溢出块可以用来增加桶的大小。与传统散列表中使用的一维桶数组不同网格文件使用的桶数组的维数与数据文件的维数一样。
3.5.3 网格文件的插入
我们遵循查找记录的过程并把新记录放到查找到的桶中。如果在该桶中的块有空间那就不需要做更多的事。如果在桶中没有空间通常有两种方法解决这个问题:1.按需要给桶增加溢出块。2.通过增加或移动网格线来重组结构。这种方法类似于3.3节讨论的动态散列技术但这里还有别的问题因为在一个维上桶的内容是相互关联的。也就是说增加一条网格线将分裂沿该线的所有桶。因此要选择一条对所有桶都最优的网格线也许是不可能的。例如要是一个太大我们也许不知是该选择对维分裂还是对点分裂并且不会造成许多的空桶或使某些桶太满。
3.6 多维数据的树结构
1.多键索引。2. kd-树。3.四叉树。4.R-树。前三种用于点集。R-树通常用来表示区域的集合它也可用来表示点集。
3.6.1 多键索引
假若我们有几个属性来表示我们的数据点的维并且我们想在这些点上支持范围查询或最近邻查询。用来访问这些点的一个简单的树模式是索引的索引或者用更一般的话来说是一棵树它的每一层的结点都是一个属性的索引。这种想法如图 所示这是两个属性的情况,“树根”是两个属性中第一个属性的索引它可以是任何类型的常规索引如B-树或散列表。该索引把每一个索引键值–即第一个属性的值–同指向另一个索引的指针相关联。如果V是第一个属性的一个值那么通过键值V和它的指针找到的索引是一个指向这些点集的索引这些点的第一个属性值是V而第二个属性为任意值。
3.6.3 kd-树
kd-树(k维搜索树)是把二叉搜索树推广到多维数据的一种主存数据结构。我们将先介绍这种思想然后讨论怎样使这种思想适合存储的块模型。kd-树是一个二叉树它的内部结点有一个相关联的属性a和一个值V它将数据点集分成两个部分:a值小于V的部分和a值大于等于V的部分。由于所有维的属性在层间交替出现所以树的不同层上的属性是不同的。在一般的 kd-树中数据点被存放在结点内就像在二叉搜索树中一样。不过我们在开始引人这个思想时做了两个修改以便获得块模式的有限益处:1.内部结点只有一个属性该属性的一个划分值和指向左、右子树的指针。2.叶结点是块块空间中存放着尽可能多的记录。在kd-树中查找一个所有维都给定值的元组类似于在二叉搜索树中查找一个值。从根节点开始根据当前节点的划分维度和查询点的对应维度值决定是向左子树还是向右子树递归查找直到达到叶节点。如果叶节点中包含查询点则查找成功否则查找失败。
3.6.4 kd-树的操作
插入操作1. 查找过程首先执行一个类似于查找的过程以确定新数据点应该插入的位置。这将引导我们到一个叶节点。2. 空间检查如果叶节点的块中还有空间即未达到最大容量限制则直接将新数据点放入该块中。3. 分裂操作如果叶节点的块已满则需要进行分裂操作。选择当前节点的划分维度作为分裂维度并根据该维度上的中位数或其他合适的值将节点中的点分为两部分创建两个新的子节点。4. 创建新节点然后创建一个新的内部节点其左右子节点指向这两个新创建的子节点并设置该内部节点的划分值为分裂时使用的值。范围查询在范围查询中我们可能需要根据多个维度上的范围来查找数据点。例如查找年龄在35到55之间且薪水在8100K至200K之间的所有点。1. 从根节点开始根据根节点的划分维度假设是薪水和查询范围确定是否进入左子树、右子树或两者都进入。2. 递归查询在每个子节点上重复上述过程根据当前节点的划分维度和查询范围来决定搜索路径。3. 收集结果当达到叶节点时检查该节点中的点是否满足查询条件并将满足条件的点添加到结果集中。4. 回溯在回溯过程中继续检查其他可能包含满足条件点的子树。
3.6.5 使 kd-树适合辅助存储器
为了提高kd-树在辅助存储器如磁盘上的效率可以通过内部结点的多分支和聚集内部结点到块这两种方法来解决长路径和未用空间的问题。多分支使得内部结点能够管理更多的键和指针减少树的高度而聚集内部结点到块则通过减少磁盘I/O次数来优化性能因为一次磁盘访问可以处理多个内部结点。这两种方法共同作用能够显著提升kd-树在处理大规模数据集时的效率。
3.6.7 R-树
R-树(区域树)是一种利用B-树的某些本质特征来处理多维数据的数据结构。B-树的结点有一个键的集合这些键把线分成片段沿着那条线的每个点仅属于一个片段B-树因此使我们很容易地找到点。如果我们把沿线各处的点表示成B-树结点我们就能够确定点所属的唯一子结点在那里可以找到该点。而R-树表示由二维或更高维区域组成的数据我们把它称为数据区。R-树的一个内部结点对应于某个内部区域或称“区域”它不是普通的数据区。原则上区域可以是任何形状虽然实际上它经常为矩形或其他简单形状。R-树的结点的键位置上含有子区域它表示结点的子结点的内容。允许子区域有部分重叠尽管我们希望重叠较小。
3.7 位图索引 二进制的位数代表总共有多少数据哪个数据中包含25对应位为1。 第2,8个数据是25所以25的向量为100000001000 第四章查询执行 查询编译预览
查询分析Analysis目的将输入的查询语句如SQL查询转换成一种中间表示形式即分析树Parse Tree或抽象语法树AST。这个树形结构表示了查询的语法结构但尚未考虑查询的逻辑或物理执行方式。过程词法分析器Lexer将查询语句分解成一系列的词法单元tokens如关键字、标识符、常量等然后语法分析器Parser根据这些词法单元构建出分析树。查询重写Query Rewriting目的将分析树转换为初始查询计划这个计划通常以查询的代数表达式如关系代数表达式的形式表示。之后这个初始计划会被进一步优化以产生一个预期执行时间更短的等价查询计划。过程逻辑优化包括规则如谓词下推Pushdown Predicates、视图重写View Rewriting、选择投影合并Select-Project Merge等以减少计算量或避免不必要的数据访问。等价变换寻找查询的代数等价形式这些形式可能在执行时更高效。物理计划生成Physical Plan Generation目的将逻辑查询计划转换为物理查询计划这包括为每个逻辑操作符选择具体的实现算法如哈希连接、嵌套循环连接等并决定这些操作符的执行顺序。过程操作符选择为每个逻辑操作符如选择、投影、连接等选择最合适的物理实现算法。执行顺序确定根据数据分布、索引可用性等因素确定操作符的最佳执行顺序。数据传输策略决定数据如何在操作之间传输包括是否使用流水线Pipeline、内存缓冲区或磁盘等。
4.1 物理查询计划操作符介绍 4.1.1 扫描表
1. 表扫描Table Scan表扫描是最直接的读取数据方式它遍历表中存储的所有数据块读取并检查每个元组行以找出满足查询条件的那些。这种方式的效率通常较低特别是在处理大型表或只有少数元组满足查询条件时。然而在以下情况下表扫描可能是必要的或最优的表中数据量很小。没有合适的索引可以利用或者索引的使用成本如索引维护开销超过了直接扫描表的成本。查询条件涉及非索引列或复杂计算使得索引无法有效减少搜索空间。2. 索引扫描Index Scan索引扫描利用索引来快速定位满足查询条件的元组。索引是数据库管理系统用于提高数据检索效率的数据结构它存储了表中某些列或列的组合的值以及这些值对应的元组在表中的位置信息。通过索引数据库系统可以快速缩小搜索范围只检查那些可能包含所需数据的块或页。索引扫描可以分为几种类型全索引扫描遍历索引中的所有条目但这通常比表扫描要快因为索引通常比表小得多。范围索引扫描在索引中查找一个范围内的条目。唯一索引扫描当索引是唯一的并且查询条件精确匹配索引中的一个值时这种扫描非常高效。索引扫描的优势在于其速度尤其是在处理大型表时。然而索引并非没有成本。索引需要额外的存储空间并且在数据插入、删除和更新时需要维护这可能会降低这些操作的性能。
4.1.2 扫描表时的排序
在数据库查询处理中排序是一个常见的操作它可能由查询中的ORDER BY子句直接触发。使用索引进行排序如果排序所依据的属性如属性a上存在B-树索引或者关系本身就是按照该属性的索引顺序存储的那么可以直接通过索引扫描来获取已经排序好的数据。这种方法非常高效因为它避免了额外的排序步骤直接利用了索引的有序性。内存排序如果关系R的大小足够小能够完全装入内存那么可以先通过表扫描或索引扫描获取R的所有元组然后在内存中使用排序算法如快速排序、归并排序等对它们进行排序。内存排序的优点是速度快但缺点是当数据集很大时可能无法全部装入内存从而导致溢出到磁盘影响性能。多路归并排序当关系R太大无法全部装入内存时就需要采用外部排序的方法。多路归并排序是外部排序的一种常用技术它将关系R分成多个可以装入内存的部分称为“块”或“段”对每个部分在内存中进行排序然后将排序后的部分写入到外部存储如磁盘上。最后使用多路归并算法将这些排序后的部分合并成一个完整的有序关系。
4.1.4 衡量代价的参数
**B**当描述一个关系R的大小时绝大多数情况下我们关心包含R的所有元组所需的块的数目。这个块的数目表示为B®。**T**有时候我们也需要知道R中的元组的数目我们将这个数量表示为T®。**V**最后我们有时候希望参考出现在关系的一个列中的不同值的数目。如果R是一个关系它的一个属性是。那么V(Ra)是R中a对应列上不同值的数目。
4.1.6 实现物理操作符的迭代器
**1.0pen()。**这个方法启动获得元组的过程但并不获得元组。**2.GetNext()。**这个方法返回结果中的下一个元组3. Close()/注意如果S已消耗完s.GetNext将会返回 NotFound对 GetNext 来说这也是正确的动作
4.2 一趟算法
我们怎样执行逻辑查询计划中的每个单独的步骤(例如连接或选择)?关于各种操作符已提出了很多算法我们可以将操作符算法按照难度和代价分成三种“等级”:a)一些方法仅从磁盘读取一次数据这就是一趟(one-pass)算法。它们通常要求操作的至少一个操作对象能完全装人内存.b)一些方法处理的数据量太大以至于不能装入可利用的内存但又不是可想象的最大的数据集合。这些两趟算法的特点是首先从磁盘读一遍数据用某种方式处理将全部或绝大部分写回磁盘然后在第二趟中为了进一步处理再读一遍数据。c)某些方法对处理的数据量没有限制。这些方法用三趟或更多趟来完成工作它们是对两趟算法的自然的递归的推广。操作符分为三大类:1.一次单个元组一元操作。我们一次可以读一个块使用内存缓冲区并产生我们的输出。2.整个关系一元操作。这些单操作对象的操作需要一次从内存中看到所有或大部分元组因此一趟算法局限于大小约为M(内存中可用缓冲区的数量)或更小的关系。3.整个关系二元操作。其他所有的操作可以归为这一类:并、交、差、连接和积的集合形式以及包形式。我们将发现如果要用一趟算法那么这类操作中的每一个都要求至少一个操作对象的大小限制在 M 以内。
4.2.1一次单个元组操作的一趟算法
我们一次读取R的一块到输人缓冲区对每一个元组进行操作,并将选出的元组或投影得到的元组移至输出缓冲区。如果R是聚集的代价就是B如果R不是聚集的代价就是T。 B包含R的所有元组所需的块的数目。这个块的数目表示为B®。 TR中的元组的数目我们将这个数量表示为T®。 4.2.2 整个关系的一元操作的一趟算法
一元操作消除重复分组消除重复一次一个地读取R的每一块但是对每一个元组我们需要判定:1.这是我们第一次看到这个元组这时将它复制到输出。2.我们从前见过这个元组这时不必输出它。为支持这个判定我们需要为见过的每一个元组在内存中保存一个备份。用一个内存缓冲区保存R的元组的一个块其余的M-1个缓冲区可以用来保存目前为止我们见过的每个元组的一个副本。分组
对 MIN(a)或MAX(a)聚集来说分别记录组内迄今为止见到的任意元组在属性a上的最小或最大值。每当见到组中的一个元组时如果合适就改变这个最小值或最大值。对于任意 COUNT聚集来说为组中见到的每个元组加1。对SUM(a)来说如果a不为NULL的话在它的组里扫描到的累加值上增加属性a的值。AVG(a)的情况复杂。我们必须保持两个累计值:组内元组个数以及这些元组在a上的值的和。二者的计算分别与我们为COUNT和SUM聚集所做的一样。当R中所有元组都被扫描后我们计算总和和个数的商以得到平均值。
4.2.3 二元操作的一趟算法并、交、差、积和连接
B包 S集合1. 集合并Union操作合并两个集合S和R中的所有不重复元素。实现将S读入内存并使用查找结构如哈希表存储然后遍历R的每一块对于R中的每个元素如果它不在S中则将其复制到输出。2. 集合交Intersection操作找出同时存在于S和R中的元素。实现同样将S读入内存并使用查找结构然后遍历R的每一块对于R中的每个元素如果它也在S中则将其复制到输出。3. 集合差Difference操作找出存在于S但不在R中的元素S-R或存在于R但不在S中的元素R-S。实现对于S-R遍历R并删除S中与R相同的元素最后输出S中剩余的元素。对于R-S遍历R并仅输出不在S中的元素。4. 包交Bag Intersection操作类似于集合交但保留元素出现的次数。实现为S中的每个元素维护一个计数遍历R时如果元素在S中存在且计数大于0则输出该元素并减少计数。5. 包差Bag Difference操作类似于集合差但保留元素出现的次数。实现对于S-R遍历R并减少S中对应元素的计数最后输出计数大于0的元素及其剩余次数。对于R-S遍历R如果元素不在S中或S中计数为0则输出元素可能带计数。6. 积Cartesian Product操作将S和R中的每个元素组合起来。实现将S读入内存然后遍历R的每一块将R中的每个元素与S中的每个元素组合后输出。7. 自然连接Natural Join操作基于两个关系的公共属性连接它们。实现将S读入内存并使用公共属性作为查找键构建查找结构然后遍历R的每一块对于R中的每个元素使用查找结构找到S中与之匹配的元素并输出连接后的结果。
4.3 嵌套循环连接 4.3.1 基于元组的嵌套循环连接
如果我们不注意关系R和S的块的缓冲方法那么这种算法需要的磁盘I/0可能多达T®T(S)。当我们可以使用R的连接属性上的索引来查找与给定的8元组匹配的R元组时这样的匹配不必读取整个关系R。执行内层循环时要尽可能多地使用内存以减少磁盘0的数目。
4.3.3 基于块的嵌套循环连接算法
1.对作为操作对象的两个关系的访问均按块组织。2.使用尽可能多的内存来存储属于关系S的元组S是外层循环中的关系。第1点确保了当在内层循环中处理关系R的元组时我们可以用尽可能少的磁盘I/0来读取R。第2点使我们不是将读到的R的每一个元组与S的一个元组连接而是与能装入内存的尽可能多的S元组连接。 σ® - 选择Selectionπ® - 投影Projection ♾️连接 4.4 基于排序的两趟算法 4.4.1 两阶段多路归并排序
两阶段多路归并排序TPMMS是一种针对大数据集进行排序的有效方法特别是在处理无法一次性装入内存的数据集时。第一阶段分割和局部排序分割将大数据集R分割成多个较小的部分块每个部分大小适中可以单独放入内存进行排序。局部排序使用内存中的排序算法如快速排序、归并排序等对每个块进行排序并将排序后的结果写回到外存如硬盘。每个块排序后形成一个有序的子表。第二阶段全局归并读取和归并从外存中读取这些有序的子表到内存中并使用多路归并算法将它们合并成一个大的有序表。多路归并同时处理多个有序子表每次从所有子表中选出最小或最大的元素并将其放入结果集中。这个过程中可能需要多次从外存读取子表数据到内存。
4.4.2 利用排序去除重复
第一趟分割和局部排序与TPMMS的第一阶段相同第二趟去重和归并去重对于每个输入块算法读取第一个未考虑的元组t并将其复制到输出块中。然后它检查输入块中剩余的元素如果发现有与t相同的元素则将它们从输入块中删除或标记为已处理实际删除可能不是必需的具体取决于实现方式。这样每个唯一的元组只会被复制到输出块一次。归并由于输入块已经是有序的因此可以确保在复制过程中输出块中的元素也是有序的。随着输入块的读取和去重算法会不断地将唯一的元组添加到输出块中。性能分析磁盘I/O与TPMMS相同该算法的总磁盘I/O次数也是3B®其中B®是数据集的块数。这是因为每个块在第一趟中需要被读入和写出一次在第二趟中可能再次被读入用于去重和归并并且结果可能还需要被写出尽管在某些情况下这个结果可能直接用于后续处理而不需要写回磁盘。
4.4.3 利用排序进行分组和聚集
第一趟分割、排序和写入读取和排序将数据集R的元组按批次读取到内存中每次读取M个块。使用分组属性作为排序关键字对每个内存中的块进行排序。写入磁盘将每个排好序的子表块写回到磁盘上。这样每个子表都是按分组属性有序的。第二趟归并、分组和聚集初始化缓冲区为每个子表分配一个主存缓冲区并将每个子表的第一个块加载到其对应的缓冲区中。查找最小分组在所有缓冲区的可用元组中反复查找排序关键字即分组属性的最小值。这个最小值确定了下一个要处理的分组。分组和聚集准备聚集为每个新的分组准备一个空白的聚集结果列表或数据结构。遍历和累计遍历所有缓冲区中的元组检查每个元组的分组属性是否与当前处理的分组相匹配。如果匹配则根据需要对元组中的其他属性进行聚集操作如计数、求和等。更新聚集结果将每个匹配的元组的贡献累加到当前分组的聚集结果中。替换空缓冲区如果一个缓冲区的所有匹配元组都已处理完毕即缓冲区为空或剩余元组不属于当前分组则用同一子表中的下一个块替换它如果有的话。输出分组和聚集结果当不再有排序关键字为当前分组的元组时输出一个包含分组属性和对应聚集值的元组。重复重复步骤2-5直到所有分组都被处理完毕。
4.4.4 基于排序的并算法
第一趟创建排序子表将关系R和S的元组分别读取到内存中并使用排序关键字通常是元组本身因为并集操作不需要特定的排序属性进行排序。将排好序的元组块写回到磁盘上形成排序子表。这些子表将用于第二趟的归并操作。第二趟归并和输出为R和S的每个子表分配一个内存缓冲区并用每个子表的第一块数据初始化这些缓冲区。重复地在所有缓冲区中查找并比较剩余的第一个元组t。将t复制到输出缓冲区或直接输出到最终结果中如果输出缓冲区已满或接近满并从所有包含t的缓冲区中删除t的副本在集合的情况下每个元素至多有两个副本分别来自R和S。当输入缓冲区变空或输出缓冲区变满时根据TPMMS算法的策略进行处理从磁盘上读取新的块到输入缓冲区或将输出缓冲区的内容写回磁盘并清空输出缓冲区以继续接收新数据。
4.4.5 基于排序的交和差算法
集合与包交算法集合交当处理到所有缓冲区中最小的元组t时如果t同时在关系R和S的缓冲区中都存在则输出t。由于是集合操作不考虑t在R和S中出现的次数只关心是否存在。包交对于包交需要计算t在R和S中出现的最小次数并输出该次数。如果t在任一关系中未出现即计数为0则不输出t。集合与包差算法集合差 R-S当处理到所有缓冲区中最小的元组t时如果t在R的缓冲区中存在但在S的缓冲区中不存在则输出t。由于是集合操作不关心t在R中出现的具体次数。包差 R-S对于包差需要计算t在R中出现的次数减去在S中出现的次数并输出该差值。如果差值小于或等于0即t在S中出现的次数至少等于在R中出现的次数则不输出t。当处理一个块且该块中所有剩余的元组都是t时需要继续读取下一个块来计算t的准确出现次数。
4.4.6 基于排序的一个简单的连接算法
给定两个要连接的关系R(X, Y)和S(Y, Z)其中Y是连接属性且有一个大小为M的内存块限制用于缓冲区。算法的目标是计算这两个关系的连接结果。1. 排序 ○ 使用Y作为排序关键字对关系R和S分别应用2PMMS两趟多路归并排序算法进行排序。排序后具有相同Y值的元组在各自的关系中会相邻。2. 归并和连接 ○ 使用两个缓冲区一个用于存储R的当前块另一个用于存储S的当前块。 ○ 重复执行以下步骤直到R和S的所有元组都被处理完a. 在当前R和S的块的前端查找连接属性Y的最小值y。b. 如果y在另一个关系的前部没有出现即当前R块的最小Y值大于当前S块的最大Y值或反之则删除当前块中具有排序关键字y的元组或跳过它们因为它们无法参与当前连接并尝试从磁盘加载下一个块到相应关系的缓冲区中。c. 如果y在两个关系中都出现则 ■ 从R和S中读取尽可能多的块直到确定每个关系中都不再有y的副本。在这个过程中可以使用多达M个缓冲区来存储具有相同Y值的元组。 ■ 输出通过连接R和S中具有共同的Y值y的元组所能形成的所有元组。这通常涉及嵌套循环遍历具有相同Y值的元组对。d. 如果一个关系在内存中已没有未考虑的元组即其缓冲区为空则重新从磁盘加载该关系的下一个块到缓冲区中。
4.4.8 一种更有效的基于排序的连接
排序阶段使用连接属性Y作为排序关键字分别对关系R(X, Y)和S(Y, Z)进行排序。将排序后的数据分割成多个子表或块每个子表的大小通常受限于内存中的可用缓冲区大小。这里假设总共有不超过M个子表每个子表可以被完全加载到内存中。初始化缓冲区为每个子表分配一个缓冲区总共不超过M个缓冲区并将每个子表的第一块加载到对应的缓冲区中。归并和连接阶段重复执行以下步骤直到所有子表都被完全处理a. 在所有子表的当前块中查找具有最小Y值的元组。b. 一旦找到具有最小Y值y的元组就识别出关系R和S中所有具有此Y值的元组。c. 使用找到的元组进行连接操作并输出所有可能的连接结果。这通常涉及到对两个关系中具有相同Y值的元组进行嵌套循环遍历。d. 如果一个子表的当前块中的所有元组都已被处理则将该子表的下一个块从磁盘加载到其对应的缓冲区中。如果所有块都已被处理则可能需要重新排序或合并剩余的子表块。
4.5 基于散列的两趟算法
基于散列的算法在处理大数据集时提供了一种有效的方法来减少内存使用并提高操作效率。这些算法通过选择适当的散列关键字将大量数据分散到有限数量的桶或称为哈希桶中从而允许算法一次处理一个桶或具有相同散列值的一对桶。
4.5.1通过散列划分关系
初始化设定散列函数h该函数将关系R中的整个元组t作为输入并输出一个介于0到M-1之间的整数表示桶的索引。准备M个缓冲区或磁盘上的块每个缓冲区对应一个桶。注意实际上只有M-1个桶用于存储数据而第M个缓冲区用作临时存储以便在最后一个桶填满时可以继续加载数据。遍历关系R遍历关系R中的每个元组t。使用散列函数h计算元组t的桶索引h(t)。将元组t复制到对应桶的缓冲区中。缓冲区管理如果某个桶的缓冲区已满将该缓冲区的内容写入磁盘上的相应块中。为该桶初始化一个新的缓冲区以便继续存储后续的元组。处理最后一个桶在遍历完关系R的所有元组后最后一个桶可能包括第M个缓冲区中暂存的元组可能并未填满。如果最后一个桶的缓冲区不为空将其内容写入磁盘上的相应块中。
4.5.2 基于散列的消除重复算法
**散列划分**使用散列函数h将关系R的元组划分到M-1个桶中。每个桶与一个缓冲区或磁盘块相关联用于存储散列到该桶的元组。如果某个桶的缓冲区满了就将其内容写入磁盘上的一个新块并为该桶初始化一个新的缓冲区。**写入磁盘**遍历完关系R后将所有非空桶的缓冲区内容写入磁盘上的块中。**重复消除**对每个桶中的数据进行重复消除。由于每个桶的大小相对较小假设每个桶都能装入内存因此可以使用一趟算法如4.2.2节中讨论的方法来去除重复元组。优点减少了内存使用因为每个桶都可以独立地装入内存处理。提高了处理速度因为可以并行处理多个桶。适用于大数据集因为可以通过增加桶的数量来扩展处理能力。
4.5.3 基于散列的分组和聚集算法
**散列划分**使用依赖于分组属性的散列函数h将关系R的元组划分到M-1个桶中。每个桶收集具有相同散列值的元组这些元组在分组属性上可能相同或相似。写入磁盘如果某个桶的缓冲区满了就将其内容写入磁盘上的一个新块并为该桶初始化一个新的缓冲区。最终所有非空桶的内容都需要被写入磁盘以便后续处理。**分组和聚集**遍历每个桶对每个桶内的元组进行分组。由于桶的大小可能较大但分组是基于散列值的因此同一分组的所有元组理论上应该都在同一个桶内。对每个分组应用聚集函数如求和、平均值、最大值、最小值等。合并结果将来自不同桶的聚集结果合并成一个完整的结果关系。这通常不需要额外的磁盘I/O除非结果关系本身太大而无法完全装入内存。
4.5.4 基于散列的并∪、交∩和差-算法
**散列划分**使用相同的散列函数h将关系R和S的元组分别散列到M-1个桶中。这意味着对于R我们有桶R₀, R₁, …, R_{M-1}对于S我们有桶S₀, S₁, …, S_{M-1}。**写入磁盘**如果某个桶的缓冲区满了就将其内容写入磁盘上的一个新块。最终所有非空桶的内容都需要被写入磁盘以便后续处理。执行集合操作并∪对于每个i计算桶R_i和S_i的并集并将结果输出到结果关系的相应桶中。注意由于使用了相同的散列函数任何在两个关系中都出现的元组都会被散列到相同的桶中从而避免了在结果中引入重复。交∩对于每个i计算桶R_i和S_i的交集并将结果输出到结果关系的相应桶中。差-对于每个i计算桶R_i中但不在S_i中的元组即R_i - S_i并将结果输出到结果关系的相应桶中。注意如果还需要计算S - R则需要额外处理。
4.5.5 散列连接算法
为了计算关系R(X, Y)和S(Y, Z)的连接我们可以使用基于散列的两趟算法。这个算法的核心思想是利用连接属性Y作为散列关键字将R和S的元组分别散列到多个桶中。然后对每个对应的桶对执行一趟连接操作最终将所有桶的连接结果合并起来得到最终的结果关系。**散列划分**使用连接属性Y作为散列关键字将R和S的元组分别散列到M个桶中。结果得到桶R_0, R_1, …, R_{M-1}和桶S_0, S_1, …, S_{M-1}。**写入磁盘**将每个桶的内容写入磁盘以便后续处理。**执行连接操作**对每对对应的桶R_i 和 S_i执行一趟连接操作。由于连接属性Y被用作散列关键字因此如果R中的元组t_R能与S中的元组t_S连接则它们必然位于具有相同i值的桶中。在一趟连接过程中算法会读取桶R_i和S_i的内容到内存中执行连接操作并将结果输出到结果关系的相应部分。**合并结果**将来自不同桶的连接结果合并成一个完整的结果关系。这通常涉及读取每个桶的连接结果并将它们组合起来。**磁盘I/O**散列连接算法大致需要3(B® B(S))次磁盘I/O操作其中B®和B(S)分别是关系R和S的块数。这些操作包括读取R和S的块到桶中、将桶写入磁盘如果必要、以及读取桶对以执行连接操作。
4.5.6 节省一些磁盘 I/O混合散列连接
桶的分配与内存使用假设有两个关系R和S其中S较小。我们创建k个桶但k的数量远小于可用的内存M以块为单位。选择m个桶m k完全保留在内存中以存储S的元组。这些桶的选择基于它们预期的大小和内存的限制。对于剩下的k-m个桶每个桶只保留一个块在内存中其余部分写入磁盘。第一趟处理当读取S的元组时将它们分配到相应的桶中。m个桶完全保留在内存中而k-m个桶的剩余部分写入磁盘。当读取R的元组时也进行类似的分配。但此时对于R的每个桶如果它对应的S桶在内存中则直接进行连接如果S桶在磁盘上则将R桶的当前块写入内存中的临时空间以便后续处理。第二趟处理读取所有写入磁盘的桶包括S和R的桶并对它们进行连接。重要的是对于那些在第一趟中已经在内存中完成连接的S桶和R桶对不需要在第二趟中再次连接。节省磁盘I/O的关键减少寻道时间和旋转延迟通过将多个块连续写入磁盘可以减少磁盘的寻道次数和旋转延迟从而提高I/O效率。避免不必要的读写通过在内存中直接连接部分桶可以避免将这些桶的内容写入磁盘后再读取的额外I/O要最大化节省的磁盘I/O需要使m/k的比率尽可能大同时满足内存限制。
基于排序和基于散列的区别
大小依赖性的差异基于散列的算法在处理二元操作时如比较、合并等其性能或空间需求通常依赖于两个操作对象中较小的一个的大小。这是因为散列通常通过映射较小的数据元素到固定的桶或位置中来工作避免了直接处理整个数据集的大小。相比之下基于排序的算法通常需要处理整个数据集或至少是数据集的一个显著部分其性能往往与数据集的总大小直接相关。有序输出的能力基于排序的算法天然能够产生有序的结果集这对于需要排序输出的应用非常重要。排序后的数据还可以用于进一步的查询或分析如二分查找、范围查询等。基于散列的算法则不直接提供排序功能其输出通常是无序的。如果需要排序则必须额外进行排序操作。桶大小的限制基于散列的算法依赖于固定大小的桶来存储数据。如果数据分布不均可能导致某些桶过载而其他桶空闲影响性能。此外桶的数量通常受限于可用的存储空间或内存大小。特别是在处理具有少量不同值的场景如group-by操作中的少量分组时桶的利用效率可能较低。磁盘I/O效率在基于排序的算法中通过合理组织磁盘上的数据块可以最小化磁盘I/O操作提高性能。特别是当排序后的数据可以连续存储在磁盘上时可以减少磁头移动和旋转延迟时间。基于散列的算法在磁盘I/O方面可能不那么高效除非能够精心组织桶的存储位置以减少磁盘访问时间。批量读写优化当排序子表的数量远小于可用内存块M时基于排序的算法可以通过批量读写磁盘块来减少I/O操作次数和延迟。类似地在基于散列的算法中如果桶的数量可以精心选择以匹配磁盘块的布局则可以实现类似的性能优化。
4.6 基于索引的算法
通过在关系的一个或多个属性上创建索引可以极大地加速数据检索、选择和连接等操作。基于索引的算法利用这些索引来快速定位数据从而显著提高查询效率。
4.6.1聚簇和非聚簇索引
聚簇Clustering在数据库管理系统中聚簇通常指的是将表中的数据物理地存储在一起以便基于某个特定的顺序或属性来优化查询性能。当关系的元组被紧缩到能存储这些元组的尽可能少的块中时我们称这个关系是被聚簇的。聚簇可以是基于整个表即整个关系的也可以是基于表中某个或某些属性的。聚簇索引Clustered Index聚簇索引是一种特殊的索引它不仅定义了表中数据的逻辑顺序还决定了数据的物理存储顺序。在具有聚簇索引的表中索引键的值决定了数据行在磁盘上的物理位置。这意味着当你通过聚簇索引来查询数据时数据库可以直接定位到数据的物理位置并快速读取数据。非聚簇索引Non-Clustered Index与聚簇索引不同非聚簇索引不定义表中数据的物理存储顺序。相反它提供了一个索引结构该结构包含索引键和指向表中相应数据行的指针。这意味着当你通过非聚簇索引来查询数据时数据库首先使用索引来快速定位到数据行的指针然后通过该指针访问实际的数据行。
4.6.2 基于索引的选择
聚簇索引下的选择操作当属性a上的索引是聚簇的时数据本身就是按照索引键即属性a的值的顺序存储的。这意味着如果我们想要选择所有av的元组我们可以直接通过索引快速定位到这些元组在磁盘上的位置并读取它们所在的块。然而实际的磁盘I/O次数可能会受到几个因素的影响索引不在内存中索引本身可能不完全驻留在内存中因此可能需要从磁盘读取索引块。块分裂即使所有满足条件的元组都可以放入少量的块中这些元组也可能因为块分裂而分布在多个块中特别是如果它们不是从块的开始位置开始的。块填充和预留空间关系R的块可能没有被完全填满或者为了未来的插入操作而预留了空间。这会导致需要读取更多的块来检索所有相关的元组。整数取整如果B®/V(R,a)不是整数我们需要向上取整以确保所有相关的块都被读取。非聚簇索引下的选择操作在非聚簇索引的情况下索引仅仅提供了指向数据行指针的列表而数据本身并不是按照索引键的顺序物理存储的。因此当我们通过非聚簇索引查找满足av的元组时每个匹配的元组都可能位于不同的块中。这导致我们需要读取更多的块来检索所有相关的元组因为索引只能告诉我们每个元组的位置而不能保证它们会聚集在一起。
4.6.3 使用索引的连接
自然连接 R(X, Y) ⨝ S(Y, Z)在自然连接中我们假设两个关系R和S分别具有属性集X和Y的交集以及各自的额外属性集Y对于RZ对于S。连接操作基于这些共同的属性在这个例子中是Y来合并元组。索引的使用假设S在属性Y上有一个索引。这个索引可以极大地加速连接过程因为它允许我们快速定位S中所有与R中当前元组在Y属性上相匹配的元组。磁盘I/O数量的分析读取R的元组如果R是聚簇的我们需要读取B®个块来获取R的所有元组。如果R不是聚簇的可能需要读取多达T®个块即R中元组的总数。对于R中的每个元组查找S中的匹配元组使用S在Y属性上的索引我们可以快速定位到S中所有Y值匹配的元组。如果索引是非聚簇的那么对于R中的每个元组我们平均需要读取T(S)/V(S,Y)个S的元组这里V(S,Y)是S中Y属性不同值的数量。因此总的磁盘I/O次数大约为T®T(S)/V(S,Y)。如果索引是聚簇的那么我们可以直接通过索引访问到物理上连续存储的元组从而减少磁盘I/O。在这种情况下我们大约需要T®B(S)/V(S,Y)次磁盘I/O这里假设每个块可以容纳多个具有相同Y值的元组。注意如果B(S)/V(S,Y)小于1则至少需要一个磁盘I/O来读取包含至少一个匹配元组的块。
4.6.4 使用有序索引的连接
当索引以有序形式如B-树索引存在时我们可以利用这些索引来优化连接操作。有序索引允许我们直接按照排序顺序遍历关系中的元组而无需显式地对整个关系进行排序从而节省了大量的计算资源和时间。Zig-Zag 连接当两个关系R(X, Y)和S(Y, Z)在共同的属性Y上都拥有有序的索引时我们可以采用一种高效的连接方法称为Zig-Zag连接。这种方法的核心思想是同时遍历R和S的索引并比较当前元组的Y值以找到所有匹配的元组对。**初始化**设置两个指针一个指向R的索引的起始位置另一个指向S的索引的起始位置。**比较与遍历**比较两个指针当前指向的元组的Y值。如果Y值相等则这两个元组构成一个连接对输出它们并将两个指针都向前移动。如果R的Y值小于S的Y值则将R的指针向前移动。如果R的Y值大于S的Y值则将S的指针向前移动。重复上述步骤直到至少一个索引被完全遍历。
4.7 缓冲区管理 4.7.1 缓冲区管理结构
1. 直接控制内存的缓冲区管理器在这种模式下DBMS的缓冲区管理器直接管理内存中的缓冲区负责分配和回收内存空间给这些缓冲区。2. 使用虚拟内存的缓冲区管理器DBMS的缓冲区管理器在虚拟内存中分配缓冲区而不是直接管理物理内存。操作系统负责将虚拟内存映射到物理内存并根据需要在物理内存和磁盘的交换空间之间移动数据块。
4.7.2 缓冲区管理策略 最近最少使用(LRU) 先进先出(FIFO) “时钟”算法(第二次机会) 4.8 使用超过两趟的算法 4.8.1 基于排序的多趟算法
当关系R的大小以块数B®衡量可以直接装入M个内存缓冲区时读取数据将整个关系R读入内存。排序在内存中使用任何高效的排序算法如快速排序、归并排序等对R进行排序。写回磁盘将排序后的关系R写回到磁盘上。当关系R的大小超过了M个内存缓冲区能够容纳的范围时分组将R的块分成M个组即R₁, R₂, …, Rₘ。递归排序对每个分组Rᵢi1,…,M递归地应用排序算法。这意味着每个分组都会被读入内存、排序然后写回磁盘。合并排序的子表使用类似于外部归并排序的方法将所有M个排序后的子表合并成一个大的有序表。这个步骤可能需要多趟读写操作具体取决于内存大小和关系R的块数。执行一元操作如果需要在排序的同时执行一元操作如去重δ或分组γ则需要在合并步骤中适当修改算法去重δ在合并过程中仅当遇到新的元组时才将其写入输出文件忽略重复的元组。分组γ首先按分组属性对关系进行排序然后在合并过程中收集具有相同分组属性值的元组并根据需要进行聚合操作如求和、平均等。执行二元操作对于二元操作如交、连接等算法也遵循类似的分而治之策略分组和排序对两个关系R和S分别进行分组和排序生成排序后的子表。分配缓冲区根据R和S的块数B®和B(S)按比例分配M个缓冲区给R和S。执行操作使用适当的算法如嵌套循环连接、归并连接等来合并排序后的子表并执行所需的二元操作。这个步骤可能需要多次从磁盘读取和写入数据具体取决于操作类型和缓冲区大小。
4.8.3 基于散列的多趟算法
一元操作如果关系R能够装入M个内存缓冲区中即B® ≤ M则直接将R读入内存并在内存中执行所需的一元操作。如果关系R太大无法装入M个内存缓冲区则执行以下步骤散列到桶中使用散列函数将关系R的元组散列到M-1个桶中。递归处理对每个桶递归地执行一元操作。合并结果将所有桶的处理结果合并成一个最终的结果集。二元操作如果有一个关系比如R能够装入M-1个内存缓冲区中而另一个关系比如S可以逐个块地装入剩下的第M个缓冲区则可以直接在内存中执行连接操作。具体地将R读入内存然后逐个块地将S读入第M个缓冲区并在内存中执行连接。如果两个关系都太大无法同时装入内存则执行以下步骤散列到桶中将两个关系R和S分别散列到M-1个桶中。对于每个桶ii1,…,M-1R和S都有一个对应的桶R[i]和S[i]。递归处理对每个相应的桶对(R[i], S[i])递归地执行连接操作。注意这里的递归处理与一元操作类似但操作的是桶对而不是单个关系。合并结果将所有桶对的连接结果合并成一个最终的结果集。这个合并过程可能需要额外的排序和归并步骤以确保最终结果的顺序性如果需要的话。
第五章 查询编译器 5.1 语法分析和预处理 5.1.1 语法分析与语法分析树
语法分析树的构成原子语法分析树中的叶子节点对应于源代码中的不可再分的基本元素如关键字、标识符如变量名、表名、列名、常量、标点符号如括号、逗号、运算符等。这些元素是词法分析器Lexer的输出词法分析器负责将源代码文本分割成这些基本的词法单元Tokens。语法类语法分析树中的非叶子节点代表语法结构中的构造块或“短语”这些短语由一组原子或更小的语法类通过特定的语法规则组合而成。这些节点用于表示语言中的语法结构如表达式、语句、程序块等。在表示时通常会使用尖括号 来标识语法类的名称以便于区分原子和语法类。 整个查询的根节点表示一个完整的SQL查询。 表示一个SELECT语句可能包括选择列表、FROM子句、WHERE子句等。 包含要选择的列名或表达式的列表如name, age。 表示对表中某列的引用如name和age尽管在这里它们直接作为原子出现但在更 复杂的表达式中它们可能是的实例。 表示FROM子句指定查询的数据来源如FROM users。 表示表名如users。 表示WHERE子句包含用于过滤结果的条件如WHERE age 30。 表示一个条件表达式如age 30。这里可以进一步细分比如表示比较操作表示值尽管在这个例子中30被直接视为原子。 SELECT name, age FROM users WHERE age 30;该查询的语法分析树可能包含以下节点
Query根节点表示整个查询。
SelectList包含name和age的列表。
name原子
age原子
FromClause包含users。
users原子
WhereClause包含条件表达式。
Condition表示条件表达式age 30。
age原子
原子
30原子5.1.2 SQL 的一个简单子集的语法
存在一些“基本”或“终端”语法类有时也称为词法单元或标记它们不是通过其他语法规则组合而成的而是直接对应于源代码中的基本元素。这些元素在语法分析阶段之前就已经被词法分析器识别出来。通常代表数据库表中的列名。在SQL查询中这些列名用于指定要从表中检索哪些数据。在语法分析树中的一个实例就是任何当前数据库模式中存在的有效列名。例如在表employees中name、age和salary都可能是的实例。代表数据库中的一个表或视图。在SQL查询中FROM子句后面通常会跟有一个或多个以指定查询将要从哪些表中检索数据。同样在语法分析树中的一个实例就是任何当前数据库模式中存在的有效表名或视图名。例如employees、departments和orders都可能是的实例。在SQL中通常与字符串匹配和搜索相关尽管在标准的SQL查询中直接使用的情况可能不如和那么普遍。但是在像LIKE这样的SQL语句中用于指定要匹配的字符串模式。的一个实例是任何被引号括起来的、符合SQL字符串匹配规则的字符串。例如在LIKE语句中John%可能是一个的实例用于匹配以John开头的任何字符串。
5.1.3预处理器
视图引用的预处理当查询语句中引用的关系实际上是一个视图时预处理器需要将该视图的定义嵌入到原始查询中。语义检查确保查询语句在逻辑上是合理的。包括检查关系、属性、类型和运算符的使用是否满足数据库规则。检查关系的使用验证FROM子句中指定的每个关系表或视图在当前数据库模式中是存在的。检查属性的使用确保在SELECT子句、WHERE子句等中引用的每个属性都属于当前查询范围内的一个关系。类型的检查验证每个属性的使用是否符合其数据类型的要求。例如在WHERE子句中使用LIKE运算符时比较的两边通常应该是字符串或可以隐式转换为字符串的类型。如果使用了不兼容的类型如将日期类型直接与字符串进行比较预处理器将需要执行类型转换。
5.2 用于改进查询计划的代数定律
本节列出一些代数定律用于将一个表达式树转换成一个等价的表达式树后者可能有更有效的物理查询计划。应用这些代数变换式的结果是逻辑查询计划它是查询重写阶段的输出。数据库系统之关系代数详解-超详细-CSDN博客 选择σ选择运算用于从关系中选择满足特定条件的元组。选择运算的表达式通常表示为σp®其中p是选择条件R是关系名。 投影π投影运算用于从关系中选择指定的属性列并删除重复的元组。投影运算的表达式通常表示为πA®其中A是属性列表R是关系名。 消除重复δ当δ运算符应用于一个关系时它会检查关系中的每个元组并移除所有重复的元组。这意味着在结果关系中每个元组都是唯一的。 笛卡尔积笛卡尔积是指两个集合在数据库操作中可以理解为两个表的所有可能组合。如果表A有M行表B有N行那么A和B的笛卡尔积将有M*N行。每一行都是由表A中的一行与表B中的一行组合而成。不考虑表之间的实际关系简单地将一个表中的每一行与另一个表中的每一行进行组合。 自然连接自然连接是一种特殊的等值连接它自动根据两个表中具有相同名称的列来连接这两个表。如果两个表中存在多个具有相同名称的列则这些列都会被用作连接条件。连接后结果表中只保留一个公共列并去除不满足连接条件的行。根据两个表中具有相同名称的列来连接这两个表只保留满足连接条件的行并且结果表中只保留一个公共列。 等值连接E Inner Join 等值连接是基于两个或多个表中指定列的值相等进行连接的连接操作。与自然连接不同等值连接需要显式指定连接条件即哪些列的值应该相等。连接结果中包含满足连接条件的所有行和列不会自动去除重复的列。 SELECT * FROM 表A INNER JOIN 表B ON 表A.ID 表B.ID; 5.2.1 交换律与结合律
交换律对于某些运算符其操作数的顺序可以互换而不影响结果。并集∪、交集∩和笛卡尔积×等运算符满足交换律。并集∪对于任意两个关系R和S如果它们有相同的结构相同的列名则R ∪ S S ∪ R。交集∩对于任意两个结构相同的关系R和SR ∩ S S ∩ R。笛卡尔积×虽然笛卡尔积通常用于不同结构的关系之间但如果我们考虑两个关系R和S不必有相同的结构则R × S和S × R的结果在逻辑上是不同的因为结果关系中的元组顺序和属性排列会不同。然而在关系代数的上下文中我们通常只关注元组的内容而不关注其顺序因此可以认为笛卡尔积在“无序”的意义上满足交换律。结合律并集∪、交集∩和笛卡尔积×等运算符也满足结合律。并集∪对于任意三个结构相同的关系R、S和T(R ∪ S) ∪ T R ∪ (S ∪ T)。交集∩(R ∩ S) ∩ T R ∩ (S ∩ T)。笛卡尔积×对于任意两个关系R和S以及另一个关系TT的结构可以与R和S不同(R × S) × T 和 R × (S × T) 在逻辑上是不等价的因为结果关系的结构和元组数会不同。但是如果我们考虑将笛卡尔积的结果视为一个单一的关系并仅关注元组的内容而不考虑其内部结构则可以认为笛卡尔积满足结合律。
5.2.2 涉及选择的定律
“下推选择”Pushing Selections Down是一种重要的优化策略旨在通过重新排列查询计划中的操作顺序来减少处理的数据量从而提高查询效率。 下推选择是指在构建查询执行计划时将选择或称为过滤操作尽可能地移动到查询计划的早期阶段即靠近数据源如表扫描或索引扫描的位置。这样做的目的是减少后续操作需要处理的数据量从而提高查询的整体性能。 1.对于并选择必须下推到两个参数中。2.对于差选择必须下推到第一个参数下推到第二个参数是可选的。3.对于其他运算符只要求选择下推到其中一个参数。对于连接和积将选择下推到两个参数是没有意义的因为参数可能有也可能没有选择所要求的属性。即使可以同时下推到两者该做法也不一定能改进计划。选择条件可能依赖于两个表之间的交互数据而这些数据在连接或积操作之前是不可见的。假设关系R具有C中要求的全部属性
5.2.3 下推选择
当查询包含虚视图时有时首先将选择尽可能往树的上部移是很必要的然后再把选择下推到所有可能的分支。**选择前置**原始查询中的选择条件即电影年份为1996年实际上可以前置到连接操作之前。我们可以先对Movies表进行过滤只选择1996年的电影然后再与StarsIn表进行连接。**选择下推**在将选择前置后我们可以将这个选择条件进一步下推到连接的子节点上。因为year是Movies表的属性也是连接操作需要考虑的属性所以我们可以将这个条件分别应用于Movies表和StarsIn表。连接操作只需要处理与1996年电影相关的StarsIn记录从而显著减少了处理的数据量。
5.2.4 涉及投影的定律
投影的下推当投影操作可以下推到其他操作如连接、排序等中时可以优化查询的执行计划。投影操作只是减少了每个元组的长度对总处理量的减少作用有限。因此在选择和投影都能下推的情况下优先选择下推选择操作往往更为有效。扩展投影扩展投影是投影操作的一个扩展它允许在投影的过程中不仅选择原始关系中的属性还可以计算新的属性或表达式作为输出。在扩展投影中输出属性x可能是一个复杂的表达式该表达式可以包含输入属性E中的属性、常量或函数运算等。E-x输入属性在投影操作中E中提到的属性称为输入属性它们是原始关系中的属性用于计算或选择输出属性。输出属性在投影或扩展投影中x是输出属性它可能是原始关系中的一个属性也可能是通过输入属性计算得到的新值。简单投影如果投影列表中的属性只是简单地选择原始关系中的属性没有包含复杂的表达式或更名操作则称该投影为简单投影。
5.2.6 有关消除重复的定律 5.2.7 涉及分组与聚集的定律
运算符 γ (Gamma): γ 表示聚集运算符它可以对一组数据进行某种形式的聚合操作比如求和、计数、平均、最小值或最大值等。运算符 δ (Delta): 表示去重操作即从一组数据中删除重复的记录只保留唯一的记录。运算符 π (Pi): 是一个选择操作符用于从一组数据中选择特定的列或属性。L属性列表通常与聚集操作相关联。在聚集函数的表达式中“L” 指的是聚集操作所应用的属性列表。M属性列表通常用于投影操作。在关系代数中投影操作π用来从关系中选择特定的列或属性。表示从关系 R 中选择属性列表 M 中的所有属性。“M” 在聚集操作中的作用是确保在进行聚集之前关系中包含所有需要的属性。聚集运算符的通用定律: δ(γL®) γL®意味着先进行聚集操作然后去重与先去重再进行聚集操作的结果是相同的。这是因为聚集操作本身不关心数据中的重复项。投影去除无用属性: γL® γL(πM®) 表示在进行聚集操作之前我们可以选择性地去除那些在聚集列表 L 中没有被使用的属性 M。这是因为这些属性对于最终的聚集结果没有影响。不受重复影响的聚集: 当聚集列表 L 中只包含 MIN 或/和 MAX 函数时我们称这个聚集操作是不受重复影响的。这是因为 MIN 和 MAX 函数的结果是不会因为数据中的重复项而改变的。因此可以有 γL® γL(δ®)即无论数据是否有重复最终的聚集结果都是相同的。受重复影响的聚集: 与不受重复影响的聚集相反像 SUM、COUNT、AVG 这样的聚集函数其结果会受到数据中重复项的影响。如果在计算这些聚集之前去除重复项最终的值可能会不同。
5.3 从语法分析树到逻辑查询计划
第一步使用关系代数运算符替换语法树关系代数是一组抽象的操作用于对关系即表进行查询和修改。这些操作包括选择σ、投影π、连接⨝、并∪、差-、笛卡尔积×等。 表引用直接映射为关系代数中的关系即表。 选择条件转换为选择σ操作用于过滤满足条件的元组。 投影将SELECT子句中的字段名转换为投影π操作用于选择特定的属性。 连接根据JOIN条件如A.dept_id B.dept_id转换为连接⨝操作合并两个或多个关系。 第二步优化关系代数表达式在得到逻辑查询计划即关系代数表达式后下一步是优化它以生成更有效的物理查询计划。 查询重写通过等价变换如改变连接顺序、合并选择操作等来减少计算量。 索引利用识别并利用索引来加速查询执行。 并行处理如果可能将查询分解为可以并行执行的部分。 5.3.1 转换成关系代数
您“简单”SELECT-FROM-WHERE结构转换为关系代数表达式的规则。处理FROM列表将FROM列表中提及的所有关系即表视为关系代数中的基本关系。如果FROM列表中包含了多个表并且这些表之间需要通过某种方式如JOIN条件相关联则首先计算这些表的笛卡尔积。处理WHERE条件使用选择σ运算符来过滤满足WHERE子句中条件的元组。将WHERE子句中的条件表达式转换为关系代数中的选择条件。处理SELECT列表使用投影π运算符来选择SELECT列表中指定的属性。投影运算符作用于经过选择和连接如果有的话处理后的关系上。
5.3.2 从条件中去除子查询 5.3.3 逻辑查询计划的改进
** 选择条件下推**选择条件下推是一种将选择过滤操作尽可能地向查询计划树的底部即数据源移动的优化策略。当查询中包含多个连接的表时将选择条件尽早应用于较小的数据集可以减少后续操作的数据量从而提高查询效率。对于AND连接的多个条件可以分别将每个条件下推到树的相应位置。投影下推投影下推是另一种优化策略它将投影即选择列操作尽可能地向查询计划树的底部移动。这有助于减少在数据传输和处理过程中所需的数据量。重复消除重复消除是指移除查询结果中的重复行。在某些情况下这个操作可以被移动到查询计划树中更方便的位置以减少需要处理的数据量。选择与积的结合在某些情况下可以将选择条件与下面的连接操作结合将等值条件的选择操作转换为等值连接。这通常可以提高查询的效率因为等值连接通常可以更有效地利用索引和连接算法。
5.4 运算代价的估计
在将逻辑查询计划转换为物理查询计划的过程中有四个方面值得关注。1. 满足结合律与分配律的运算的次序与分组结合律对于满足结合律的运算如连接、并、交其操作对象的次序可以改变而不影响最终结果。在物理计划中我们可以重新排列这些运算的次序以最小化数据移动、减少中间结果的大小或利用系统的并行处理能力。分配律在某些情况下我们可以利用类似分配律的性质来优化查询。例如将选择过滤操作“分配”到连接操作之前以减少需要连接的数据量。分组将多个可结合的运算组合成一个更大的运算单元可以减少运算符之间的数据交换次数提高执行效率。例如将多个连接操作组合成一个复合连接操作。2. 逻辑计划中每个运算符的算法选择在逻辑计划中我们定义了要执行的运算但在物理计划中我们需要选择实现这些运算的具体算法。例如对于连接操作我们可以选择嵌套循环连接、散列连接或排序合并连接等算法。3. 物理计划中的其他运算符扫描物理计划需要明确如何从存储介质如磁盘中读取数据。这通常涉及扫描操作可以是全表扫描或索引扫描。排序在物理计划中排序操作可能是显式的如ORDER BY子句或隐式的如连接操作前的排序。排序算法的选择和数据的物理布局都会影响排序操作的效率。4. 参数和数据的传输方式在物理计划中我们需要考虑数据如何在不同的运算符之间传输。这包括确定中间结果的存储位置如内存、磁盘以及传输机制如迭代器、批量传输。使用磁盘上的中间结果可以减少内存的使用但会增加I/O成本。使用迭代器可以逐条处理数据减少内存占用但可能增加CPU的开销。
5.4.1 中间关系大小的估计
主要关注查询执行过程中产生的临时结果即中间关系的元组数或数据量。这是评估查询性能的一个重要方面因为中间关系的大小直接影响了查询所需的存储空间、I/O操作次数以及后续运算的复杂度。
5.4.2 投影运算大小的估计
对于关系 R每个元组大小12元组头 4a 4b 100c 120字节。块中元组数(1024−24)/1208向下取整。元组总数 T®10000因此块数 B®10000/81250。对于关系 Sπ ®其中 表示扩展投影用 a 与 b 的和替代 a 和 b新的元组结构包括12元组头 4ab的和假设结果仍为整数 100c 116字节。尽管元组大小略有减少但由于仍然可以存放8个元组在一个块中所以块数和元组总数保持不变T(S)10000B(S)1250。对于关系 Uπ a,b ®即传统的去除 c 的投影新的元组结构包括12元组头 4a 4b 20字节。由于元组大小显著减小现在每个块可以存放更多的元组(1024−24)/2050向下取整。因此虽然元组总数仍然是 T(U)10000但块数大大减少B(U)10000/50200。
5.4.3 选择运算大小的估计
等值比较当查询条件为某个属性等于某个常量时如 S σAc®那么结果集的大小可以通过 T(S) T® / V(R, A) 来估计其中 T® 是表 R 的元组数V(R, A) 是属性 A 的不同取值的数量。这个假设在属性值均匀分布时较为准确。非等值比较对于非等值比较如 S σAc® 或 S σAc®由于条件的非确定性结果集的估计更加复杂。一种假设是认为满足条件的元组大约占总元组数的一半然而涉及非等值比较的查询倾向产生更小量的元组因此我们估计 T(S) T® / 3。特殊比较对于某些特殊的选择条件如检查某个属性是否非空A IS NOT NULL如果大多数元组都满足这个条件即空值较少则可以假设所有元组都满足条件即 T(S) T®。或者更精确地可以通过 T(S) T® * (V(R, A) - 1) / V(R, A) 来估计。
5.4.4 连接运算大小的估计
值集的包含如果一个属性Y同时出现在关系R和S中且R的Y值集合是S的Y值集合的子集即V(R,Y) ≤ V(S,Y)那么R中的每个Y值都会在S中出现。这个假设在Y是S的键且是R的外键时成立但在其他情况下可能不成立。值集的保持在进行连接时非连接属性即只出现在一个关系中的属性不会丢失其值集中的任何值。这意味着如果A是R的属性但不是S的属性那么V(R∞S, A) V(R, A)。这个假设在大多数情况下是合理的但也可能在某些特殊情况下不成立。概率计算与结果集大小估计如果V(R,Y) V(S,Y)那么S中每个Y值都会出现在R中因此s的Y值出现在R中的概率为1但r和s具有相同Y值的概率为1/V(R,Y)因为R中有V(R,Y)个可能的Y值。如果V(R,Y) V(S,Y)则情况相反r的Y值会出现在S中r和s具有相同Y值的概率为1/V(S,Y)。为了统一这两种情况我们可以将概率估算为1/max(V(R,Y), V(S,Y))。基于上述概率我们可以估算连接结果集T(R∞S)的大小T(R∞S) T®×T(S)/max( V(R,Y),V(S,Y) )
5.4.5 多连接属性的自然连接
当连接R(XY)xS(YZ)中的属性集Y包含多于一个属性时R⋈S的大小估计是通过T®乘以T(S)对于每一个R与S的公共属性y除以V(Ry)与V(Sy)中较大者来计算。假设我们有两个关系R(X, Y)和S(Y, Z)其中Y是两个关系的共同属性集并且Y包含多个属性y1, y2, …, yn。我们可以尝试使用以下方法来近似计算自然连接结果集的大小
5.4.6 多个关系的连接
在考虑多个关系表的自然连接时特别是当某个属性A出现在多个关系中时我们需要分析这些关系在连接后如何影响结果集的大小以及属性A上值的分布。以下是对您提出的问题的详细解答假设有 k 个关系 _R_1,_R_2,…,Rk它们通过自然连接合并成一个新的关系 S即 SR_1⋈_R_2⋈…⋈_Rk。属性 A 出现在这 k 个关系中的至少两个关系中。属性A上值的分布假设属性 A 在 k 个关系中的值集大小分别为 _u_1,_u_2,…,uk且已按从小到大的顺序排列即 u_1≤_u_2≤…≤_uk。值集保持假设在连接后的关系 S 中属性 A 的值集大小将是这些 ui 中的最小值即 _u_1。所选元组在属性A上相同的概率假设首先从具有最小 _u_1 的关系 _R_1 中选择一个元组 _t_1其属性 A 的值为 a。对于其他关系 Ri其中 i2,3,…,k所选元组 ti 在属性 A 上与 _t_1 相同的概率是 _ui_1因为 Ri 中有 ui 个不同的 A 值。因此所有 k 个元组在属性 A 上相同的概率是这些概率的乘积即 1/_u_1_u_2…uk。估计连接后的大小一个近似的估计方法是对于每个这样的属性 A从乘积中除以除了 V(Ri,A) 中的最小值即 _u_1之外的所有 V(Ri,A) 的较大值的乘积
5.4.7 其他运算大小的估计
并包的并结果的大小正好是参数关系大小之和。集合的并结果的大小介于两参数大小之和到两参数中较大者之间。建议取中间值如较大者加上较小者的一半。交结果的大小可以从0个元组无交集时到两参数中较小者完全重叠时之间变化。建议取两极端的平均值即较小值的一半。差当计算 R_−_S 时结果中的元组数可以从 T(R)S 为空时到 T(R)−_T_(S)S 完全包含在 R 中时之间变化。建议估计值取其平均值T(R)−_T_(S)/2。消除重复如果 R(_a_1,_a_2,…,an) 是一个关系则去重后 δ(R) 的大小理论上等于 R 中不同元组的数量。由于这个统计值通常不可得需要取近似值。极端情况下去重后的大小可以是 T(R)无重复元组时或1所有元组都相同时。另一个上限是可能存在的不同元组的最大数即所有 V(R,ai)i1,2,…,n的乘积。然而这个数可能远大于 T(R) 的实际值。一个合理的估计是取 T(R)/2 与所有 V(R,ai) 之积中的较小者。分组GROUP BY与聚集对于分组操作 γL(R)其中 L 是分组属性列表结果中的元组数与分组数相同。分组数的范围可以从1所有元组在分组属性上都相同到 T(R)每个元组在分组属性上都是唯一的。与去重类似可以使用所有 V(R,A)其中 A 是 L 中的属性的乘积作为分组数的上界。建议的估计值是 T(R)/2 与这个乘积中的较小者。
5.5 基于代价的计划选择介绍 5.5.1 大小参数估计值的获取
元组数和不同值数目的获取元组数T®通过对整个关系R进行一次扫描可以简单地计算出关系中的元组数。不同值数目V(R,A)通过扫描关系R并跟踪每个属性A的不同值可以计算出该属性列的不同值数目。块数B®的估计 : 如果关系R是聚簇存储的那么它所占用的块数B®可以通过实际使用的块数来计数。如果关系不是聚簇存储的或者需要更粗略的估计则可以通过将元组数T®除以一个磁盘块可以容纳的R的元组个数来估算块数。直方图的计算等宽直方图将属性值的范围划分为等宽的区间并计算每个区间内的元组数。如果遇到新的更小的值可能需要调整区间的边界。等高直方图基于百分比来划分区间例如列出最小值、比最小值多p%的值、比最小值多2p%的值等直到最大值。最频值直方图列出最常见的值及其出现次数同时可能包含其他值的分组统计。基于直方图的连接大小估计使用直方图可以更准确地估计连接操作的结果大小。特别是当连接属性的值显式地出现在两个关系的直方图上时可以精确地知道结果中有多少元组将具有该值。
5.5.2 统计量的计算
周期性更新的原因稳定性数据库中的统计量在短时间内通常不会发生剧烈变化因此没有必要频繁更新。一致性即使统计量不是绝对精确的只要它们被一致地应用于所有查询计划优化器仍然能够进行有效的比较和选择。性能考量频繁更新统计量会将统计量本身变成数据库中的“热点”因为它们会被频繁读取和写入这会影响数据库的整体性能。取样大小取样的元组数量需要根据统计精度和计算成本之间的平衡来确定。例如可以选择关系R的1%作为样本。
5.5.4 枚举物理计划的方法
选择最优的物理查询计划**穷尽法**穷尽法是一种最直接但可能最耗时的方法它尝试所有可能的物理计划组合并对每个计划进行代价估计最终选择代价最小的计划。这种方法适用于小型数据库或查询但对于大型数据库和复杂查询来说其计算量将变得不可接受。自顶向下与自底向上方法自顶向下Top-Down从逻辑查询计划树的根部开始逐级向下考虑每个运算符的可能实现并计算每种组合的代价。这种方法在每一步都需要评估所有可能的子计划并可能导致大量的重复计算。自底向上Bottom-Up从逻辑查询树的叶子节点即基本关系开始逐级向上计算每个子表达式的最优计划并在构建较大子表达式的计划时只考虑较小子表达式的最优计划。这种方法通常与动态规划相结合以减少重复计算并提高效率。**动态规划**动态规划是自底向上方法的一个变种它通过保存子问题的解来避免重复计算。对于每个子表达式动态规划方法只保留其最小代价的计划并在构建更大子表达式的计划时利用这些已保存的最优解。这种方法虽然不保证总是找到全局最优解但在许多情况下都能获得很好的结果。**Selinger 风格的优化**是对动态规划方法的一种改进。它不仅记录了每个子表达式的最小代价计划还记录了那些具有较高代价但结果顺序对上层运算符有用的计划。这种方法利用了查询计划中的某些特性如排序、分组和连接属性以期望从非最优的子表达式计划中构建出整体最优的查询计划。启发式选择基于一系列启发式规则来选择物理计划。这些规则通常基于经验或统计信息旨在快速找到近似最优的查询计划。例如如果连接的一个参数在连接属性上有索引则采用索引连接如果需要对多个关系进行并或交操作则先对最小关系进行组合等。启发式选择方法通常比穷尽法更快但可能无法找到全局最优解。**分支界定计划枚举**通过启发式方法找到一个好的初始物理计划并以此为基准来剪枝搜索空间。在搜索过程中任何代价高于当前已知最优计划的计划都将被放弃因为它们不可能成为更优的完整查询计划的一部分。这种方法可以显著减少搜索空间的大小并提高搜索效率。爬山法从一个初始的物理计划开始通过不断地对计划进行小的修改如替换运算符的实现方法、重新排序连接等来寻找代价更低的邻近计划。当无法再通过小修改来降低计划的代价时算法停止并返回当前的计划作为最优解。这种方法可能陷入局部最优解但通常能够快速找到一个可接受的解决方案。
5.6连接顺序的选择 5.6.1 连接的左右参数的意义
**一趟连接**通常选择较小的关系作为左参数构造用关系并将其加载到内存中构建成一个哈希表。这个哈希表使得数据查找变得非常高效。然后将较大的关系右参数探查用关系分批读入内存并将每个元组与哈希表中的元组进行匹配从而执行连接操作。这种策略利用了较小的关系能够完全加载到内存中并构建高效索引的优势。嵌套循环连接左参数通常被选作外部循环关系。这意味着查询优化器会遍历左参数中的每一个元组并将其与右参数中的所有元组进行比较以查找匹配项。如果左参数较小则外部循环的开销相对较小这有助于提升整体性能。如果左参数很大则可能需要考虑其他连接策略。索引连接右参数通常被认为是有索引的关系。这意味着在连接过程中查询优化器会利用右参数的索引来快速定位匹配的元组而不是遍历整个关系。因此选择拥有有效索引的关系作为右参数可以显著提高连接操作的效率。索引连接特别适用于当右参数很大但可以通过索引快速访问其特定部分时。
5.6.3 左深连接树
左深树浓密树右深树左深树的数量与所有树的数量对于给定数目的关系即树叶所有可能的树形结构包括非左深树和左深树的数量是巨大的特别是随着关系数量的增加这个数量呈指数级增长。相比之下左深树作为这些所有可能树形结构的一个子集其数量虽然也很大但增长速度要慢得多。这是因为左深树的结构限制了树的形状使得每个节点最多只能有一个右子节点且该右子节点可以是另一个连接或关系从而减少了可能的组合方式。左深树与连接算法的交互一趟连接左深树使得优化器能够选择较小的关系作为构建哈希表的关系即左子树而将较大的关系或连接结果作为探查的关系即右子树。这种安排可以最大化哈希表的效率因为哈希表可以一次性构建并用于多个连接操作。嵌套循环连接在嵌套循环连接中左深树允许优化器将较小的关系放在外层循环即左子树而将较大的关系或连接结果放在内层循环即右子树。这样可以减少内层循环的迭代次数从而提高整体连接的效率。**左深树中的运算符**左深树或右深树中的树叶即基本关系不仅可以是简单的关系还可以是包含其他运算符如选择、投影的内部节点。这意味着在构建查询计划时优化器可以灵活地将这些运算符应用于连接的输入或输出以进一步减少处理的数据量并优化查询性能。
5.6.4 通过动态规划来选择连接顺序和分组
1. 定义状态和问题在动态规划中我们首先定义状态。在这个场景下状态可以定义为包含一定数量表的集合以及这些表之间可能的连接顺序和成本。目标是找到包含所有目标表的一个集合的最优连接顺序使得总成本最小。2. 构建代价表代价表或称为DP表用于存储中间结果即对于每个可能的表集合其最优连接顺序及其对应的成本。这个表通常通过归纳法来填充。基础情况对于只包含一个表的集合其最优连接顺序就是该表本身成本为0因为没有进行连接。归纳步骤对于包含多个表的集合我们考虑所有可能的子集划分并计算每种划分下的连接成本。我们选择成本最小的划分作为该集合的最优连接顺序。3. 考虑左深树与其他树形左深树在只考虑左深树的情况下连接顺序的选择相对简单。对于集合R中的k个表我们尝试将R划分为R-i和{i}其中i是R中的一个表并计算R-i与i连接的成本。我们选择成本最小的划分作为最优解。所有可能的树形如果考虑所有可能的树形问题变得更加复杂。我们需要考虑所有可能的子集划分并计算每种划分下将子集连接起来的成本。这通常涉及更复杂的成本函数和更多的计算。4. 计算成本和表达式对于每种划分我们需要计算两个主要值连接成本这是将两个子集连接起来的成本通常基于它们的大小、索引使用情况、以及可能的公共属性等因素。结果大小这是连接操作后结果集的大小用于后续连接的成本计算。5. 表达式构建在找到最优连接顺序的同时我们还需要构建相应的表达式这个表达式描述了表之间的连接顺序。在左深树的情况下表达式就是表的顺序在更一般的情况下表达式可能包括嵌套的连接操作。6. 应用到实际查询最终我们得到的代价表和相应的表达式可以被用来优化实际的数据库查询。通过选择成本最低的连接顺序数据库管理系统可以减少查询的执行时间提高查询效率。
5.6.5 带有更具体的代价函数的动态规划
仅基于关系大小来估计连接成本可能会忽略一些重要的实现细节如索引的使用、磁盘I/O成本等。为了更准确地估计连接成本我们可以对动态规划算法进行修改以纳入更具体的代价函数如磁盘I/O成本。在动态规划算法中我们可以修改代价的计算方式以考虑实际的连接成本。这通常涉及以下几个方面磁盘I/O成本对于每个关系我们需要知道其数据在磁盘上的存储方式如是否索引以及访问这些数据所需的磁盘I/O次数。连接算法不同的连接算法如嵌套循环连接、排序合并连接、散列连接具有不同的成本特性。我们需要根据关系的特性和可用索引来选择最合适的连接算法。中间结果的大小连接操作的结果大小也会影响后续操作的成本。较大的中间结果可能需要更多的磁盘空间并增加后续操作的I/O成本。**Selinger风格优化**是一种更全面的查询优化方法它不仅考虑连接操作的成本还考虑查询结果的排序和存储顺序。这种方法对于生成高效的查询计划特别有用特别是当查询结果需要按照特定顺序返回给用户时。在Selinger风格优化中对于每个可能被连接的关系集合我们不仅计算连接的最小成本还考虑生成以几个“感兴趣”的顺序中的任意一个顺序存储的关系的最小成本。这些“感兴趣”的顺序可能包括对后续排序连接有利的顺序如果查询计划中包含排序连接那么生成已经排序的中间结果可能会减少后续操作的成本。用户期望的输出顺序如果查询结果需要按照特定顺序返回给用户那么生成符合这一顺序的中间结果可能会减少最终排序的成本。
5.6.6 选择连接顺序的贪婪算法
在数据库查询优化中特别是在处理多表连接JOINs时选择最优的连接顺序对于提高查询效率至关重要。当连接的表数量增多时可能的连接顺序组合呈指数级增长这使得穷尽搜索所有可能的连接顺序变得不现实。因此启发式算法如贪婪算法成为了一个实用的选择。贪婪算法在连接顺序选择中的应用贪婪算法在选择连接顺序时遵循局部最优原则即每一步都选择当前看来最好的选择从而希望导致全局最优解。**初始化**选择一个或多个基础表通常是较小的表或者索引良好的表作为起始点。初始化一个空的连接树这个树开始时只包含选定的基础表。**迭代选择**在所有尚未被添加到当前连接树中的表中选择一个表与当前连接树的根或某个节点进行连接这个选择基于某种估计的成本或大小如基于统计信息的行数估计。将选中的表添加到连接树中形成新的连接树结构。
5.7 物理查询计划选择的完成
1. 算法选择在逻辑查询计划转换为物理查询计划的过程中需要为各个操作选择合适的算法。2. 中间结果的物化和流水操作物化物化是指将查询的中间结果完全存储在磁盘上。这种方式在内存不足或需要重用中间结果时非常有用。然而物化会增加磁盘IO操作降低查询效率。流水操作流水操作是指在执行查询时中间结果只在内存中临时存储不保存到磁盘上。这种方式可以减少磁盘IO但要求系统有足够的内存来支持所有中间结果的存储。
5.7.1 选取一个选择方法
分析不同算法的代价1. 表扫描算法与过滤器步骤结合代价估计如果R被聚集ClusteredB®其中B®是关系R的数据块数量。聚集意味着数据在物理存储上按某个特定属性通常是主键或索引键的顺序排列但这对于表扫描的代价估计通常不直接影响因为表扫描仍需检查所有块。如果R没有被聚集T®这里T®可能表示关系R中所有元组的总数但在I/O代价的上下文中更准确地应该是T®除以每块能容纳的元组数但通常简化为B®即数据块的数量因为I/O操作以块为单位进行。2. 利用等值索引扫描代价估计如果索引是聚集的B®/V(R,a)其中V(R,a)是属性a在关系R中的唯一值数量或近似值。聚集索引意味着数据本身就是按照索引的顺序存储的因此可以更快地定位到满足条件的元组。但代价估计中仍然考虑了整个关系的数据块数量因为即使索引是聚集的也可能需要遍历多个块来找到所有匹配的元组。如果索引不是聚集的T®/V(R,a)。非聚集索引不包含数据本身只包含指向数据块的指针因此需要额外的I/O来检索实际的数据行。但在这个简化的估计中我们假设通过索引可以快速定位到包含所需数据的块。3. 利用不等值索引扫描如果索引是聚集的B®/3.9。这个估计试图反映不等值查询可能需要检查比等值查询更多的块因为不等值条件可能匹配多个连续的数据块。然而这个数字3.9是一个高度简化的假设实际中可能需要更复杂的模型来准确估计。如果索引不是聚集的T®/3。对于非聚集索引不等值查询同样需要额外的I/O来检索数据行但代价估计的具体数字取决于索引和数据的实际情况。
5.7.3 /4流水操作与物化
流水操作流水操作是一种更有效的方法它允许同时交错进行多个运算减少了磁盘I/O的需求。在流水操作中一个运算产生的结果元组直接传递给需要它的运算而不需要将中间结果存储在磁盘上。这种方法通常由迭代器网络执行迭代器网络中的迭代器在适当的时候互相调用实现数据的流动。**一元流水**一元流水操作是指涉及单个输入源的操作如选择Selection和投影Projection。在这种操作中消费者即需要结果的查询部分通过调用迭代器的GetNext()方法来请求下一个元组。**二元流水**二元运算涉及两个输入参数如连接Join或合并Union操作。二元运算的结果也可以进行流水操作。我们使用一个缓冲区将结果传递给消费者一次一块。然而计算结果和消费结果所需的其他缓冲区数目是不同的它们取决于结果的大小以及参数的大小。我们将使用一个扩展的例子来演示折中和机会。
5.7.7 物理运算的排序
物理查询计划树的分解与执行树的分解当查询计划以树的形式表示时我们可以通过物化即存储中间结果来分解这棵树。物化意味着在树中的某些节点处将中间结果存储在磁盘上以便后续运算使用。这样做可以将复杂的查询计划分解成一系列较小的、更易于管理的子树。子树的执行顺序在物化策略下子树的执行顺序通常是按照从下到上、从左到右的前序遍历顺序进行的。这种顺序确保了每个子树在其依赖的子树完成执行后才能开始执行从而保证了数据的正确性和完整性。迭代器网络与流水操作对于采用流水操作也称为流水线操作的物理查询计划迭代器网络是实现这一策略的关键。迭代器网络由一系列相互连接的迭代器组成每个迭代器代表查询计划中的一个运算。迭代器之间通过调用GetNext等方法来传递数据从而实现了数据的直接传递和连续处理而无需将中间结果存储在磁盘上。迭代器网络中的事件顺序在迭代器网络中事件的顺序是由各个迭代器之间的交互和调用关系决定的。具体来说当一个迭代器需要数据时它会调用其上游迭代器的GetNext方法。这个调用会触发上游迭代器执行必要的运算并将结果返回给下游迭代器。通过这种方式整个查询计划中的运算被同步地执行而事件的确切顺序则是由这些调用关系决定的。查询优化与执行代码生成基于上述策略查询优化器可以为给定的查询生成相应的执行代码。这些代码通常是一系列函数调用的序列它们按照预定的顺序执行查询计划中的各个运算。通过这种方式数据库系统能够高效地处理查询请求并返回准确的结果。
第6章系统故障对策
日志是支持数据可恢复性的基础技术。日志以安全的方式记录了数据库中所有变更的历史包括数据的增、删、改操作。日志类型
Undo 日志记录了如何将数据库从当前状态回滚到某个之前的状态。主要用于处理事务的撤销操作确保在事务失败或需要回滚时数据库能够恢复到事务开始前的状态。Redo 日志记录了如何将数据库从某个旧状态重新应用更改以恢复到当前状态。在系统故障后可以使用这些日志来重做所有未完成的更改以恢复数据库的最新状态。Undo/Redo 日志结合了上述两种日志的特性既能够回滚也能够重做数据库的操作提供了更灵活的恢复策略。 Undo日志和Redo日志在数据库系统中各有其独特的作用和应用场景。Undo日志主要用于事务的回滚操作确保事务的原子性和一致性而Redo日志则主要用于系统的恢复和故障处理过程确保数据库在崩溃或故障后能够恢复到一致的状态。两者共同协作为数据库系统的可靠性和稳定性提供了重要保障。 **检查点技术**减少恢复过程中需要检查的日志量提高恢复效率。工作原理定期在数据库系统中创建一个检查点该点表示此时刻数据库的状态是一致的。在检查点时刻系统会记录当前所有事务的状态如已提交、未提交等和日志信息的位置。如果系统发生故障恢复过程只需要从最近的检查点开始而不是从头开始检查日志从而大大减少了恢复所需的时间和资源。
6.1 可恢复操作的问题和模型 6.1.1 故障模式
1. 错误数据输入 :::danger 错误数据输入可能由人为因素如键盘输入错误或系统错误引起。这些错误可能难以被自动检测特别是当错误数据在格式上仍然符合规则时如电话号码中的一位数字错误。 ::: 应对措施 编写约束通过数据库管理系统提供的约束功能如NOT NULL、UNIQUE、CHECK等限制输入数据的类型和范围确保数据在逻辑上的一致性。 触发器使用触发器在数据被插入、更新或删除时自动执行特定的检查或操作以识别并处理潜在的数据错误。 2. 介质故障 :::danger 介质故障包括磁盘的局部故障如单个扇区损坏和全局故障如磁头损坏导致整个磁盘不可访问。 ::: 应对措施 奇偶校验利用与磁盘扇区相关联的奇偶校验来检测并纠正局部故障。 RAID技术通过配置RAID独立磁盘冗余阵列来提高数据的可用性和容错性。RAID可以通过数据条带化、镜像、校验等方式来减少单个磁盘故障对数据完整性的影响。 备份定期创建数据库的完整或增量备份并将备份存储在远离主数据库的安全位置。这样在发生介质故障时可以通过恢复备份来恢复数据。 分布式冗余拷贝在多个物理节点上保存数据库的冗余拷贝以提高系统的可靠性和容错性。同时需要维护这些拷贝之间的一致性确保数据的准确性。 3. 灾难性故障 :::danger 灾难性故障包括数据库所在物理环境的完全毁坏如火灾、爆炸或恶意破坏导致所有数据介质同时失去作用。 ::: 备份和冗余与介质故障相似但备份需要更加频繁和全面以确保在灾难发生后能够恢复尽可能多的数据。 分布式冗余拷贝将数据库的冗余拷贝分布在不同地理位置的多个节点上以减少单一地点灾难对系统的影响。 系统故障 :::danger 系统故障通常指的是导致事务状态丢失的问题如掉电或软件错误。由于内存是易失性的掉电会导致主存中的数据丢失包括事务的当前状态和修改结果。 ::: 日志记录使用非易失性的日志来记录所有对数据库的更新操作。这样在系统故障后可以通过日志来恢复事务的状态和数据库的一致性。 恢复机制开发复杂的恢复机制确保日志记录能够在不受故障干扰的情况下进行。这些机制通常包括日志的持久化、事务的原子性保证以及恢复算法等。 6.1.2 关于事务的进一步讨论
事务是执行数据库操作的基本单位它确保了数据的一致性和完整性。事务的四个基本特性ACID特性原子性Atomicity事务中的所有操作要么全部完成要么全部不执行不能存在部分执行的情况。一致性Consistency事务执行的结果必须使数据库从一个一致性状态转变到另一个一致性状态。隔离性Isolation并发执行的事务之间互不干扰每个事务都独立运行如同没有其他事务在并发执行一样。持久性Durability一旦事务被提交它对数据库的修改就是永久性的即使系统发生故障也不会丢失。日志管理器负责维护日志确保事务的日志记录能够正确地存储在磁盘上。由于日志记录最初是存储在内存中的因此它们需要在适当的时候被拷贝到磁盘上以确保数据的持久性。日志管理器与缓冲区管理器交互以管理日志记录的存储和检索。恢复管理器在数据库系统崩溃时被激活。它检查日志记录并使用这些记录来恢复数据库到一致的状态。恢复管理器可能需要回滚未提交的事务或者重做已提交但尚未写入磁盘的事务以确保数据库的完整性和一致性。
6.1.3 事务的正确执行
数据库元素与状态数据库元素如关系、磁盘块/页、元组等是数据库操作的基本单位。选择磁盘块或页作为数据库元素的原因在于它们通常是数据库管理系统DBMS中数据读写操作的最小单位。这样做可以简化事务日志和恢复机制的设计因为每次事务操作都可以针对完整的磁盘块进行记录从而避免了部分数据写入导致的复杂问题。数据库状态的一致性数据库状态的一致性不仅要求满足数据库模式中的显式约束如键约束、值约束等还需要满足隐式约束。隐式约束可能来源于业务逻辑、数据完整性规则或用户界面的限制等。确保数据库状态的一致性对于维护数据的完整性和可靠性至关重要。事务的正确性原则如果事务在没有其他任何事务和系统错误的情况下执行并且在它开始执行时数据库处于一致的状态那么当事务结束时数据库仍然处于一致的状态。
6.1.4 事务的原语操作
1. INPUT(X)INPUT(X) 操作负责将包含数据库元素 X 的磁盘块读取到主存中的一个缓冲区中。2. READ(X, t)READ(X, t) 操作首先检查包含数据库元素 X 的块是否在主存缓冲区中。如果不在则执行 INPUT(X) 将其加载到缓冲区。然后将缓冲区中 X 的值赋给事务的局部变量 t。3. WRITE(X, t)WRITE(X, t) 操作首先检查包含数据库元素 X 的块是否在主存缓冲区中。如果不在则执行 INPUT(X)。然后将事务局部变量 t 的值写入缓冲区中 X 的位置。4. OUTPUT(X)OUTPUT(X) 操作负责将包含数据库元素 X 的缓冲区中的块写回到磁盘上。这个操作是确保数据持久性的关键步骤。
6.2 undo 日志
Undo 日志记录了如何将数据库从当前状态回滚到某个之前的状态。主要用于处理事务的撤销操作确保在事务失败或需要回滚时数据库能够恢复到事务开始前的状态。
6.2.1 日志记录
日志记录类型的详细解释1. 记录含义这个记录表示事务T已经开始执行。它标记了事务在日志中的起始点有助于在恢复过程中识别哪些事务可能尚未完成。作用在恢复过程中 记录用于确认事务的存在和开始时间。虽然它本身不直接参与恢复操作但它是事务日志完整性的重要组成部分。2. 记录含义这个记录表示事务T已成功完成并且其对数据库的所有修改都应该是永久的。然而由于缓冲区管理器的行为这些修改可能尚未写入磁盘。作用在恢复过程中 记录是确定哪些事务应该被视为成功完成的依据。然而由于磁盘写入的不确定性恢复管理器可能需要额外的步骤来确保所有已提交事务的修改都被正确地写入磁盘。3. 记录含义这个记录表示事务T由于某种原因如内部错误、死锁、超时等不能成功完成。作用在恢复过程中 记录用于标识需要回滚撤销的事务。恢复管理器将使用undo日志中的更新记录来回滚这些事务所做的所有修改以确保数据库的一致性。4. 更新记录 T, X, v含义这个三元组表示事务T修改了数据库元素X而X的原始值是v。它记录了事务对数据库的具体修改。作用更新记录是undo日志的核心。在恢复过程中如果事务T被中止即出现记录恢复管理器将使用这些更新记录来将数据库元素X的值恢复到它们在事务T开始之前的状态。这样中止事务对数据库的影响就被消除了。undo日志的局限性undo日志仅记录旧值不记录新值。这意味着它只能用于回滚事务而不能用于重做已提交事务的修改。
6.2.2 undo 日志规则
规则U1如果事务T修改了数据库元素X那么表示这一修改的日志记录形如T, X, v其中v是X的旧值必须在X的新值被写入磁盘之前写入磁盘。这条规则确保了即使在系统崩溃时也有足够的信息来撤销事务T对X所做的修改从而恢复数据库的一致性。规则U2如果事务提交那么它的COMMIT日志记录必须在事务改变的所有数据库元素都已被写入磁盘之后写入磁盘但应尽快。这条规则确保了提交操作是持久的即一旦事务被提交其修改就不会因为系统故障而丢失。
6.2.3 使用 undo 日志的恢复
恢复过程撤销Undo未提交的事务对于那些在崩溃时尚未提交的事务恢复管理器需要撤销它们所做的所有修改以确保这些事务不会留下任何不一致的状态。重做Redo可能丢失的已提交事务的修改如果某些已提交事务的修改因为系统崩溃而未能完全写入磁盘恢复管理器需要重做这些修改。识别事务状态已提交事务这些事务的记录已经写入日志。它们的修改被认为是有效的不需要撤销。未提交事务这些事务的记录存在但记录不存在。它们的修改需要被撤销以恢复数据库到一致状态。撤销未提交事务的修改恢复管理器从日志的末尾开始扫描向前移动。当遇到T, X, v记录时如果尚未扫描到记录则意味着事务T未提交需要撤销对X的修改。恢复管理器会将X的值改回日志中记录的修改前的值。如果已经扫描到记录则不对该事务的修改进行任何操作。处理事务结束在完成所有必要的撤销操作后恢复管理器会为每个未完成的事务T写入记录到日志中并刷新日志以确保这些记录被持久化。
6.2.4 检查点
检查点机制通过定期地记录数据库和日志文件的状态来确保在系统崩溃后能够快速地恢复到最近的一个一致状态。
停止新事务。等待所有活跃事务完成这包括等待所有事务提交或中止并在日志中记录COMMIT或ABORT。这一步确保了在检查点时刻所有未完成的事务状态都是已知的。刷新日志到磁盘将内存中的日志记录强制写入磁盘确保日志的持久性。写入记录在日志中写入一个特殊的检查点记录表明此点之后的所有事务都是在此检查点之后开始的。 记录用于标记检查点Checkpoint的完成。在记录之后的所有事务都是在当前检查点之后开始的。记录包含了以下关键信息 时间戳记录了检查点完成的具体时间点这对于后续的恢复操作至关重要。 状态信息可能包含了数据库在检查点时刻的特定状态信息如活跃事务列表、已提交事务的日志位置等这些信息有助于恢复过程快速定位到正确的恢复起点。 日志位置在某些实现中记录还可能包含当前日志文件的写入位置或检查点相关的日志序列号LSN这有助于恢复过程确定从哪些日志记录开始应用或忽略。 通过记录数据库系统能够在发生崩溃或需要恢复时快速定位到最近的检查点并仅从该检查点之后的日志记录中恢复未完成的事务或应用已提交事务的修改。这大大减少了恢复过程所需处理的数据量提高了恢复效率。 重新开始接收事务一旦检查点完成系统可以继续接收新的事务。
6.2.5 非静止检查点
传统的静止检查点要求在检查点期间停止接收新的事务等待所有当前活跃的事务完成并将它们的修改写入磁盘。然而这种方法会导致系统暂停服务影响用户体验。非静止检查点技术允许在系统进行检查点的同时继续接收和处理新的事务非静止检查点的步骤
开始检查点
系统在日志中写入一个特殊的STARTCKPT(T,…,T)记录其中T,…,T是所有当前活跃事务的标识符。这个记录表明从现在开始系统将开始一个检查点过程但会继续接收新的事务。
等待活跃事务完成
系统继续运行允许新事务进入并处理。同时系统等待记录中列出的所有活跃事务完成提交或中止并将它们的修改写入磁盘。
结束检查点
当所有活跃事务都完成后系统在日志中写入一个记录。这个记录表明检查点过程已完成所有在之前开始的事务都已经处理完毕。恢复过程当系统从故障中恢复时它会从日志的尾部开始向后扫描如果先遇到记录那么恢复过程可以安全地忽略之前的所有日志记录因为它们所代表的事务更新已经稳定地存储在数据库中。恢复过程将继续向后扫描直到遇到下一个记录。如果先遇到记录但还没有记录那么系统崩溃发生在检查点过程中。恢复过程需要找到并撤销那些在和崩溃之间开始且未完成的事务以及那些在中列出但尚未在崩溃前完成的事务。
6.3 redo 日志
undo 日志在恢复时消除未完成事务的影响并忽略已提交事务而redo日志忽略未完成的事务并重复已提交事务所做的改变。undo日志要求我们在COMMIT日志记录到达磁盘前将修改后的数据库元素写到磁盘而redo日志要求COMMIT记录在任何修改后的值到达磁盘前出现在磁盘上。对于undo日志恢复时需要旧值即事务开始前的值来撤销更改。而对于redo日志恢复时需要的是新值即事务提交后应该存在于数据库中的值来重做更改。
6.3.1 redo 日志规则
指出被修改元素的日志记录
当事务T需要修改数据库元素X时首先会生成一条形如T, X, v的日志记录其中T是事务标识X是被修改的数据库元素标识v是新的值。这条记录会立即被写入到日志文件中但此时数据库元素X本身还没有被修改。
COMMIT 日志记录
当事务T完成所有修改并准备提交时会生成一条的日志记录表示事务T已经成功完成。这条记录同样会被写入到日志文件中并且它必须出现在所有与该事务相关的更新记录之后。
改变的数据库元素自身
只有当上述所有与事务T相关的日志记录包括更新记录和提交记录都成功写入到磁盘上的日志文件中之后事务T才会实际修改数据库元素X的值并将这个新的值写入到磁盘上的数据库文件中。这恢复过程会检查日志文件中的记录并按照事务的提交顺序重新执行所有已提交的更新操作从而恢复数据库到崩溃前的状态。由于先写日志规则的存在即使数据库元素本身还没有被写入磁盘但是相关的日志记录已经存在因此可以通过这些日志记录来恢复数据库的状态。这种机制大大提高了数据库的可靠性和恢复能力。
6.3.2 使用redo 日志的恢复
确定已提交的事务在恢复过程开始时首先需要确定哪些事务是已经提交的哪些事务是未完成的即已启动但尚未提交或已回滚的事务。这通常通过检查日志文件中的记录来完成。如果日志中存在记录则事务T被认为是已提交的否则事务T被认为是未完成的。2. 从首部开始扫描日志接下来从日志文件的开始部分顺序扫描每一条记录。对于遇到的每一条T, X, v记录其中T是事务标识X是数据库元素标识v是新值需要执行以下操作
a) 如果T是未提交的事务
在这种情况下由于事务T最终没有成功提交因此它对数据库所做的任何修改都不应该被保留。因此对于这样的记录恢复过程将忽略它不执行任何操作。
b) 如果T是提交的事务
对于已提交的事务其修改是有效的并且需要被应用到数据库中。因此恢复过程会将新值v写入到数据库元素X中无论该元素当前的值是什么。这是通过redo日志实现的即重新执行已提交事务的修改操作。3. 对每个未完成的事务T在日志中写入一个记录并刷新日志在扫描完所有日志记录并应用了所有已提交事务的修改之后恢复过程需要处理那些未完成的事务。虽然这些事务的修改不会被应用到数据库中但出于一致性和审计的目的通常会在日志中为每个未完成的事务写入一个记录。这个记录表明事务T由于某种原因如系统崩溃而未能成功完成并且其修改应该被忽略。为了确保记录被正确地写入到日志文件中通常需要执行一个“刷新”操作以确保日志文件的更改被持久化到磁盘上。这样即使系统再次崩溃也能够从日志文件中准确地了解哪些事务是已提交的哪些事务是未完成的。
6. 3. 3 redo 日志的检查点
写入日志记录START CKPT(T1,…,Tn)其中T1,…,Tn是所有活跃即未提交的事务并刷新日志2. 将STARTCKPT记录写入日志时所有已提交事务已经写到缓冲区但还没有写到磁盘的数据库元素写到磁盘在写入记录之后系统需要遍历所有的缓冲区找出那些已经被已提交事务修改过但尚未写入磁盘的数据库元素即“脏页”。然后将这些脏页写入磁盘。这一步是检查点过程的核心因为它确保了所有在检查点之前已经提交的事务的修改都被持久化到磁盘上。3. 写入日志记录并刷新日志在所有必要的脏页都被写入磁盘之后系统在redo日志中写入一个记录标志着检查点过程的结束。
6.3.4 使用带检查点 redo 日志的恢复
情况一最后一个检查点记录是STARTCKPT(T,…,T)记录之前提交的所有事务的修改都已经成功写入了磁盘。因此恢复过程可以简化为忽略STARTCKPT(T,…,T)之前提交的事务因为它们的修改已经持久化。关注STARTCKPT(T,…,T)中列出的事务以及在该检查点之后开始的所有事务。扫描日志从日志的开头或上一个检查点之后开始直到找到STARTCKPT(T,…,T)。重做redoSTARTCKPT(T,…,T)中列出的事务以及之后开始并提交的所有事务的修改。这些事务的修改可能还没有写入磁盘。停止扫描日志当遇到最早的记录表示一个新事务的开始且该事务不在STARTCKPT(T,…,T)中时因为这意味着后续的事务与当前恢复过程无关。情况二最后一个检查点记录是START CKPT (T,…,Tk)我们不能确定在START CKPT (T,…,Tk)之前提交的事务的修改是否已经被写入磁盘。因此恢复过程需要更多的步骤回溯到日志中查找最近的记录。找到与这个匹配的STARTCKPT(S,…,Sn)记录。重做redo所有在STARTCKPT(S,…,Sn)和START CKPT (T,…,Tk)之间开始并成功提交的事务的修改因为这些事务的修改可能还没有被写入磁盘。检查START CKPT (T,…,Tk)之后的事务并只重做那些已经提交的事务的修改。
6.4 undo/redo 日志
我们已经看到了两种不同的日志方式它们的差别在于当数据库元素被修改时日志中保存旧值还是新值。它们各有其缺陷:
undo日志要求数据在事务结束后立即写到磁盘可能增加需要进行的磁盘I/0次数。另一方面redo日志要求我们在事务提交和日志记录刷新以前将所有修改过的块保留在缓冲区中这样可能增加事务需要的平均缓冲区数。如果数据库元素不是完整的块或块集在检查点过程中undo日志和redo日志在如何处理缓冲区方面都存在矛盾。例如如果一个缓冲区中包含被提交的事务修改过的数据库元素A和同一缓冲区中被尚未将其COMMIT记录写到磁盘的事务修改过的数据库元案B。
6.4.1 undo/redo 规则
规则UR1在事务T对数据库元素X的修改即新值w写入磁盘上的X之前更新记录T, X, v, w必须已经写入磁盘。这里v是修改前的旧值w是修改后的新值。这个规则确保了即使在系统崩溃之后我们也有足够的信息来恢复数据通过重做已提交事务的修改或撤销未提交事务的修改。这个日志记录为系统提供了足够的信息来执行undo如果事务需要被回滚或redo如果事务已经提交但系统崩溃需要重新应用其修改操作。
6.4.2 使用 undo/redo 日志的恢复
1. 按照从前往后做顺序重做所有已提交的事务这一步是在系统恢复过程中首先执行的。它的目的是重新应用所有已经成功提交的事务的修改以确保这些修改对数据库的影响是持久的。2. 按照从后往前做顺序撤销所有未提交的事务在重做所有已提交事务之后下一步是撤销所有未提交的事务。这是因为未提交的事务表示它们还没有被系统正式接受为数据库状态的一部分因此它们的修改不应该在恢复后的数据库中反映出来。为了撤销这些事务系统会按照日志中从后往前的顺序即事务发生的逆序来查找所有未包含日志记录的事务并撤销它们所做的修改。
6.4.3 undo/redo 日志的检查点
写入日志记录 START_CKPT(T,…,T) 并刷新日志2. 将所有脏缓冲区写到磁盘3. 写入日志记录 END_CKPT 并刷新日志
6.5 针对介质故障的防护 6.5.1 备份
完全转储完全转储涉及拷贝数据库在某一时刻的完整状态。这是恢复过程的基础因为它提供了一个完整的、无遗漏的数据集。完全转储通常被标记为“0级”转储因为它不依赖于任何先前的转储。增量转储增量转储仅拷贝自上次转储无论是完全转储还是增量转储以来发生变化的数据库元素。这种方法显著减少了每次备份所需的数据量但恢复过程可能需要多个转储文件因为它们是按顺序依赖的。增量转储可以进一步细分为多个级别其中“i级”转储表示拷贝自最后一个小于或等于i级转储之后改变的所有内容。 起始点恢复过程通常从一个完整的转储0级转储开始因为这个转储包含了数据库在某个时间点的完整状态。 增量层叠随后的增量转储1级、2级、…、i级都是基于之前的转储进行的。例如1级增量转储包含了自0级转储以来发生变化的元素而2级增量转储则包含了自最近一次1级或更低级别增量转储以来发生变化的元素以此类推。 恢复顺序在恢复时必须首先恢复0级转储因为这是所有后续增量转储的基础。然后需要按照递增的顺序1级、2级、…、i级应用增量转储以确保所有更改都被正确地应用到数据库中。 6.5.2 非静止转储
非静止转储是一种在数据库系统不停止运行的情况下进行的备份策略。由于数据库在备份过程中仍然处于活动状态新的事务可能会开始、修改或提交因此备份的数据库状态可能会与转储开始时有所不同。为了解决这个问题非静止转储结合了日志记录来确保数据库在恢复时能够达到一个一致的状态。非静止转储的特点并发性在备份过程中数据库系统继续处理新的事务包括数据的插入、更新和删除。日志依赖由于备份是在数据库活动的状态下进行的因此备份中可能包含不一致的数据。为了恢复到一个一致的状态需要依赖于在备份过程中生成的日志记录。顺序拷贝非静止转储通常按照某种固定的顺序如数据库表的顺序或数据页的顺序来拷贝数据库元素。然而由于并发性这些元素在被拷贝的过程中可能会被其他事务修改。恢复过程恢复过程包括将备份数据恢复到数据库并应用备份过程中生成的日志记录来纠正任何不一致。这通常涉及回滚未提交的事务并应用已提交事务的更改。
6.5.3 使用备份和日志的恢复
假设发生了介质故障并且我们要通过此前已到达安全的远程结点、在崩溃中未丢失的日志和最近的备份重建数据库。我们执行下列步骤:1.根据备份恢复数据库。a)找到最近的完全转储并根据它来恢复数据库(即将备份拷贝到数据库)。b)如果有后续的增量转储按照从前往后做的顺序根据各个增量转储修改数据库。2.用保留下来的日志修改数据库。使用对应所用日志方式的合适的恢复机制。 第7章 并发控制
调度器不同事务各个步骤的执行顺序由调度器完成。调度器所要实现的可串行性或者冲突可串行性。调度器最重要的技术封锁时间戳有效性确认。
7.1 串行调度和可串行化调度 7.1.1 调度
重要的读写动作发生在主存缓冲区中而不是磁盘上。调度是一个或多个事务的重要动作的一个序列。
7.1.2 串行调度
一个事务的所有动作完成之后才能进行下一个事务的所有动作。不同事务的调度顺序结果可能不一样。
7.1.3 可串行化调度
可串行化调度 它允许事务并发执行但产生的结果与某个串行调度产生的结果相同。**可串行化**如果一个并发调度即多个事务可能同时执行的执行结果与某个串行调度即事务按某种顺序一个接一个执行的执行结果对于所有可能的数据库初始状态都是相同的那么这个并发调度就被认为是可串行化的。
7.1.5 事务和调度的一种记法
读操作 (rTi(X)): 表示事务读取数据库元素X的当前值。写操作 (wTi(X)): 表示事务将数据库元素X的值更改为新值。
7.2 冲突可串行化 7.2.1 冲突
同一事务的两个动作总是冲突的。单个事务的动作顺序不能改变。不同事务对同一数据库元素的写冲突。不同事务对同一数据库元素的读和写也冲突。
总结不同事务的任何两个动作可以交换除以下情况外:
它们涉及同一数据库元素。至少有一个是写。
冲突等价如果通过一系列相邻动作的非冲突交换能将它们中的一个转换为另一个我们说两个调度是冲突等价的。冲突可串行化如果一个调度 冲突等价 于一个串行调度那么我们说该调度是冲突可串行化的。
7.2.2 优先图及冲突可串行化判断
**冲突可串行化:**它确保了一个调度虽然可能包含并行执行的事务但这些事务的执行顺序可以重新排列成一个没有冲突的串行执行顺序同时保持所有事务的原始读写操作。如果这样的串行顺序存在那么该调度就被称为冲突可串行化。优先图优先图是一种有向图用于表示事务之间的先后顺序关系。根据调度序列与r冲突的是w与w冲突的是rw。例
与r2A冲突的是w1.3A因此存在一条 2——3与r1B冲突的是w2.3B因此存在一条 1——2与w2A冲突的是w1.3Ar1.3A,因此存在一条2——3与r2B冲突的是w1.2B因此存在一条2——1
以此类推…得到优先图
7.3 使用锁的可串行化实现
事务获得在它所访问的数据库元素上的锁以防止其他事务几乎在同一时间访问这些元素并因而引人非可串行化的可能。
7.3.1 锁
读写前的锁请求事务T在读取r(X)或写入w(X)数据库元素X之前必须先请求L(X)并获得该元素上的锁。这确保了当事务尝试访问数据库元素时它对该元素具有独占访问权从而避免了数据的不一致性问题。锁请求L(X)和读写操作r(X)或w(X)之间不能有释放该元素锁的操作u(X)。这是为了确保在访问元素期间锁是持续有效的。锁的释放事务T在完成对数据库元素X的读写操作后必须释放u(X)在该元素上的锁。这允许其他事务在需要时能够请求并获取锁进而访问或修改该元素。锁的互斥性任何两个事务T1和T2都不能在同一时间封锁同一个数据库元素X除非其中一个事务如T1已经先释放了它在X上的锁。这意味着如果调度中存在两个连续的锁请求动作L(X)和L(X’)假设它们是由不同事务发出的那么在这两个动作之间必须有一个对应的解锁动作u(X)由已经持有锁的事务执行。确保了数据库元素在任何时候都只能被一个事务独占访问从而维护了数据的一致性和完整性。
7.3.3 两阶段封锁
加锁阶段在此阶段事务可以申请并获得它需要的所有锁。一旦事务开始了加锁阶段它就不能释放任何锁直到进入解锁阶段。解锁阶段在此阶段事务可以释放它在加锁阶段获得的所有锁。一旦事务进入了解锁阶段它就不能再申请任何新锁。
7.4 有多种锁模式的封锁系统
在7.3节讨论的简单封锁模式中每个事务在读写数据库元素时都需要获得锁这在实际应用中可能过于严格且效率低下。
事务T即使只想读数据库元素X而不写它也必须获得X上的锁。
7.4.1 共享锁与排他锁
共享锁Shared LockS锁也称为读锁。当事务需要读取数据库元素但不修改它时可以请求共享锁。多个事务可以同时持有同一个数据库元素上的共享锁这意味着它们可以同时读取该元素。如果某个事务已经持有数据库元素的共享锁其他事务也可以请求该元素的共享锁但不能请求排他锁。排他锁Exclusive LockX锁也称为写锁。当事务需要修改数据库元素时必须请求排他锁。排他锁是独占的即在同一时间只有一个事务可以持有某个数据库元素上的排他锁。如果某个事务已经持有数据库元素的排他锁其他事务既不能请求该元素的共享锁也不能请求排他锁 sliX事务Ti申请数据库元素X上的一个共享锁 xliX事务Ti申请数据库元素X上的一个排他锁 liX请求锁 uiX释放锁 7.4.2 相容性矩阵
行表示数据库元素上当前已经被其他事务持有的锁类型。列表示新申请的锁类型。示例
S 申请X 申请S 持有是否X 持有否否 7.4.3 锁的升级
在数据库事务管理中锁机制是确保数据一致性和隔离性的重要手段。锁升级是指事务在开始时获取较低级别的锁如共享锁随着操作的进行根据需要将其升级到更高级别的锁如排他锁。优点提高并发性在事务开始时使用共享锁可以允许多个事务同时读取数据从而提高了系统的并发性能。减少等待时间事务在需要写入数据前可能已经完成了大部分读取操作此时升级锁可以减少因等待排他锁而导致的延迟。缺点死锁风险增加多个事务可能同时尝试升级同一资源的锁导致它们相互等待对方释放锁从而引发死锁。出现死锁当T和T’几乎同时开始时它们都会首先获取A上的共享锁。随后它们都试图将A上的锁升级为排他锁但由于对方持有A上的共享锁因此都无法立即升级。结果是T和T’都会陷入无限等待状态因为它们都在等待对方释放A上的锁。死锁解决方案使用超时机制在尝试升级锁时设置超时时间如果在规定时间内无法升级锁则释放已持有的锁并回滚事务或采取其他恢复措施。
7.4.4 更新锁
更新锁介于共享锁S锁和排他锁X锁之间。更新锁允许事务在读取数据的同时保留将来可能对该数据进行更新的权利。更新锁的特点读取权限持有更新锁的事务可以读取数据但不能写入数据。升级权限更新锁可以被升级为排他锁但共享锁不能直接升级为排他锁除非先释放共享锁。互斥性一旦资源上有了更新锁就不能再有其他事务在该资源上获得任何类型的锁包括共享锁、更新锁和排他锁直到更新锁被释放或升级为排他锁。 行表示数据库元素上当前已经被其他事务持有的锁类型。
列表示新申请的锁类型。
避免死锁在例7.16中由于事务T和T’都试图将共享锁升级为排他锁导致它们互相等待对方释放锁从而引发死锁。通过使用更新锁我们可以避免这种情况。在例7.17中事务T和T’都首先申请A上的更新锁。由于更新锁的互斥性当T持有A上的更新锁时T’尝试获取A上的更新锁将会被拒绝。这样T可以继续执行并完成其操作然后释放A上的锁。之后T’可以获取A上的更新锁进而升级为排他锁并完成其操作。
7.4.5 增量锁
增量锁是一种特殊的锁机制适用于那些仅涉及对数据库元素进行增加或减少操作的事务。多个事务可以同时对同一数据库元素进行增量操作而这些操作的结果与它们执行的顺序无关。增量锁的特性增量操作的交换性增量锁允许多个事务同时对同一数据库元素进行增量操作且这些操作的顺序可以交换而不影响最终结果。锁的兼容性在增量锁被持有的情况下其他事务不能对该元素加共享锁S锁或排他锁X锁但可以同时有多个事务持有该元素的增量锁i锁。限制读写操作增量锁不赋予事务对数据库元素进行读或写操作的权力仅允许进行增量操作。
7.5 封锁调度器的一种体系结构
事务申请锁释放锁都是调度器的干预。
7.5.1 插入锁动作的调度器
事务请求的动作通常通过调度器传送并在数据库上执行。但是在某些情况下事务等待个锁而被推迟其请求(暂时)不被传送到数据库。第I部分请求处理与锁插入功能负责接收来自事务的请求流这些请求包括数据库访问操作如读、写、增量、更新和必要的锁请求。操作在数据库访问操作之前插入适当的锁动作如加锁、解锁等。然后将处理后的封锁和数据库访问动作序列传递给第Ⅱ部分。第Ⅱ部分动作执行与锁管理功能接收第I部分传来的封锁和数据库访问动作序列并负责它们的执行。操作
如果一个事务由于等待锁而被推迟则将该动作推迟并加入到一个待执行列表中。如果事务的所有请求锁都已被授予则执行该事务的数据库访问操作或封锁动作。封锁动作的执行包括检查锁表以确定锁是否可以被授予。如果可以则更新锁表如果不可以则在锁表中标记该锁已被申请并推迟事务直到锁可用。
锁释放与通知当事务提交或中止时通知第I部分释放锁。如果有事务等待这些锁则通知第Ⅱ部分进行处理。锁的获得与执行当某个数据库元素上的锁变得可用时第Ⅱ部分决定哪个或哪些事务可以获得这些锁并允许它们执行被推迟的操作直到它们完成或遇到新的锁等待。
7.5.2 锁表
锁表是将数据库元素与有关该元素的封锁信息联系起来的一个关系表。表可以用一个散列表来实现使用数据库元素(地址)作为散列码。任何未被封锁的元素在表中不出现因此表的大小只与被封锁元素的数目成正比而不是与整个数据库的大小成正比。一个列表描述所有或者在A上当前持有锁或者在等待A上的锁的那些事务。组模式概括事务申请A上的一个新锁时所面临的最苛刻的条件。在共享-排他-更新(SXU)封锁模式中规则很简单:组模式:a)S表示被持有的只有共享锁。b)U表示有一个更新锁而且可能有一个或多个共享锁。c)X表示有一个排他锁并且没有其他的锁。封锁请求处理检查锁表项
如果A的锁表项不存在说明A上当前没有锁调度器将创建一个新的锁表项并立即同意T的请求。如果A的锁表项存在调度器将检查当前的组模式U-更新锁、X-排他锁、S-共享锁。
根据组模式决定请求
如果组模式是U更新锁则只有T自己持有的U锁或与其他请求相容的锁才能被授予。否则请求被拒绝并在等待列表中为T的请求添加一项设置Wait?Yes。如果组模式是X排他锁则请求同样被拒绝并添加等待项。如果组模式是S共享锁则另一个共享锁或更新锁可以被授予。如果授予的是更新锁则组模式改为U如果是共享锁则组模式保持S。
更新锁表
无论锁是否被授予新的列表项都会通过Tnext和Nex字段正确地链接到等待列表中。调度器可以从锁表直接获取所需信息无需检查锁的列表但列表用于管理等待的事务。
解锁处理删除列表项从等待列表中删除T关于A的项。检查并更新组模式如果T持有的锁与组模式不同如T持有S锁但组模式是U则组模式保持不变因为还有其他事务可能持有U锁。如果T的锁与组模式相同并且T是最后一个持有该锁的事务即没有其他事务持有A上的锁了则组模式可能需要更改如果组模式是U并且没有其他锁存在则组模式变为无因为没有锁了。如果组模式是S并且还有其他事务持有S锁则组模式保持S否则也变为无。授予等待的锁如果存在等待的锁Waiting ‘yes’调度器需要决定如何授予这些锁。策略包括先来先服务按照请求的先后顺序授予锁确保公平性。共享锁优先首先授予所有等待的共享锁然后是更新锁最后是排他锁。这种策略可能导致更新锁或排他锁饿死。升级优先如果有一个持有U锁的事务在等待将其升级到X锁则优先授予该锁。这可以确保重要的更新或写入操作尽快完成。
7.6 数据库元素的层次 7.6.1 多粒度的锁
元组级锁最细粒度优点支持高并发因为每个事务只需要锁定它所修改或查询的元组。缺点管理开销大因为锁的数量可能非常多同时增加了死锁的风险。适用场景当大量事务主要修改或查询少量的数据时如银行的存款和取款操作每个账户视为一个元组。页/块级锁优点相对于元组级锁减少了锁的数量和管理开销同时仍然可以支持较高的并发。缺点可能会因为锁定整个页/块而导致一些不必要的等待尤其是当页/块内只有少量数据被修改时。适用场景当事务倾向于修改或查询页/块内多个数据时如银行数据库中同一页内的多个账户。关系级锁最粗粒度优点管理开销最小因为整个关系只需要一个锁。缺点并发性能低因为任何对关系内数据的修改都需要先获得整个关系的锁。适用场景当大多数事务是读操作且很少写操作时如文档数据库其中文档经常被检索但很少被编辑。
7.6.2 警示锁
。警示锁与普通锁如共享锁S和排他锁X配合使用以提供更灵活的锁控制机制特别是在处理多层次数据结构时。警示锁的基本概念定义警示锁通过在普通锁前加前缀如“意向”来表示例如ISIntention Shared和IXIntention Exclusive。它们用于表明事务打算在其子元素上获取特定类型的锁。作用警示锁主要用于提高锁管理的效率减少不必要的锁冲突并帮助数据库系统快速判断某个事务是否可能与其他事务发生冲突。警示锁的协议规则从根开始在尝试对任何元素加S或X锁之前必须从层次结构的根如关系开始。直接加锁如果当前结点就是需要封锁的结点则直接请求该结点上的S或X锁。向下传递警示如果需要封锁的结点位于层次结构中更靠下的位置则在当前结点上添加一个警示锁IS或IX。然后继续向包含目标结点的子结点行进并重复此过程。 锁的相容性矩阵
7.6.3 幻象与插入的正确处理
幻象问题是指在一个事务执行过程中另一个事务插入了新的行这些新行满足第一个事务中某个查询的条件但第一个事务在开始时并未看到这些行。这会导致第一个事务的查询结果不准确违反了事务的隔离性。解决方案使用更严格的隔离级别如可串行化Serializable隔离级别。在这个级别下事务会完全串行执行从而避免了幻象的发生。但这种方法可能会显著降低系统的并发性能。使用锁表级锁在事务开始时对整个表加锁直到事务结束。这可以防止其他事务插入新行。但这种方法会限制表的并发访问。范围锁对查询涉及的数据范围加锁防止其他事务在该范围内插入新行。但这种方法需要数据库系统能够预测查询的范围这在很多情况下是不可行的。幻象锁Phantom Locks一种特殊的锁用于防止在特定查询条件下插入新行。虽然大多数数据库系统不直接提供这种锁但可以通过其他机制如索引锁、谓词锁等来实现类似的效果。使用多版本并发控制MVCCMVCC 允许数据库为每个事务维护数据的一个或多个版本。当事务读取数据时它看到的是事务开始时数据的一个快照。这样即使其他事务插入了新行也不会影响当前事务的查询结果。
7.7 树协议 7.7.1基于树的封锁的动机
在处理B-树索引的并发访问时传统的两阶段封锁2PL协议可能会遇到严重的限制导致并发性能不佳。这是因为B-树的结构特性使得根节点或内部节点的锁可能成为瓶颈特别是在进行插入或删除操作时理论上可能需要重写这些节点基于树的封锁动机减少锁粒度直接在B-树的根节点或所有内部节点上加锁会极大地限制并发性因为这会要求事务在继续深入树之前获得这些高级别节点的锁。通过基于树的结构特性来优化锁的使用可以减少不必要的锁等待和锁冲突。提高并发性通过观察和预测B-树操作的局部性可以设计一种机制使得事务在确信不会修改树的高层结构时能够提前释放高级别节点的锁。这种策略可以显著增加多个事务同时访问B-树的能力。保持可串行性虽然释放锁可能违反了两阶段封锁的原则但可以通过设计专门的协议来确保事务的调度仍然是可串行化的。这些协议利用了B-树操作的特定顺序性和结构稳定性通过跟踪事务对树的访问路径和所做的修改来确保数据的一致性。
7.7.2 访问树结构数据的规则
事务的第一个锁可以在树的任何结点上这个规则允许事务从树的任何位置开始其操作而不仅仅是从根节点开始。这增加了灵活性因为事务可以根据其需要直接定位到树中的相关部分。只有事务当前在父结点上持有锁时才能获得后续的锁这个规则确保了事务在深入树结构时遵循一种“从上到下”的顺序。这有助于防止不同事务之间的锁冲突因为它们在树中的路径不会交叉。此外这个规则还隐含了一个要求即事务在释放一个节点的锁之前必须先释放其所有子节点的锁。这是因为如果没有这个要求事务可能会陷入一个无法释放父节点锁的情况因为它还持有子节点的锁。结点可以在任何时候解锁这个规则允许事务在不再需要某个节点的锁时立即释放它。这有助于减少锁持有的时间从而提高并发性。事务不能对一个它已经解锁的结点重新上锁即使它在该结点的父结点上仍持有锁这个规则防止了事务在释放了一个节点的锁之后重新获取它除非它重新开始整个事务或重新获得从根节点到该节点的路径上所有节点的锁。这有助于避免死锁和复杂的状态管理问题。
7.8 使用时间戳的并发控制 7.8.1 时间戳
基于系统时间生成这种方法利用操作系统的当前时间来为事务分配时间戳。使用计数器生成调度器维护一个递增的计数器每当一个新事务开始时计数器加1并将新值作为事务的时间戳。RT(X)X的读时间戳。表示最后一次成功读取X的事务的时间戳。当事务T读取X时如果T的时间戳大于RT(X)则更新RT(X)为T的时间戳。WT(X)X的写时间戳。表示最后一次成功写入X的事务的时间戳。当事务T写入X时无论T的时间戳与WT(X)的关系如何都更新WT(X)为T的时间戳。C(X)X的提交位。表示最后一次写入X的事务是否已经提交。
7.8.2 事实上不可实现的行为
过晚的读事务T试图读取一个在其理论上执行之后才被写入的值。这违反了时间戳调度器的假设即事务的执行顺序应该与其时间戳顺序一致。我们只能中止事务T。过晚的写如果事务的时间戳处于一个“过晚”的位置即它试图写入一个已经被其他事务读取但尚未写入新值的数据库元素并且这个读取操作的时间戳比当前事务的时间戳还要晚那么就发生了过晚的写。
7.8.3 脏数据的问题
脏读问题脏读发生在一个事务读取了另一个未提交事务修改的数据。但事务最终可能由于某种原因而未能提交。解决方法检查提交位C(X)如果C(X)为假表示X的当前值尚未被提交因此事务T应该推迟读取X直到事务U提交或中止。另一潜在问题事务T试图写入X但发现有一个时间戳更晚的事务U已经写入了XT继续写的话会造成数据错误。解决方法Thomas写法则Thomas写法则允许一个事务在发现有更晚时间戳的写操作已经发生时跳过自己的写操作。Thomas写法则的潜在问题如果事务U后来中止其写入X的操作应该被撤销但此时T的写操作已经被跳过无法恢复X到T写入之前的状态。这可能导致数据丢失或不一致。处理策略尝试性写入当事务T写入数据库元素X时调度器并不立即将X的值更新为T写入的值而是将这次写入视为“尝试性”的。调度器同时保存X的旧值和原有写时间戳WT(X)的拷贝。提交或中止处理如果事务T提交调度器将X的值更新为T写入的值并将提交位C(X)设为真。如果事务T中止调度器将撤销T对X的写入恢复X的旧值和原有写时间戳WT(X)。
7.8.4 基于时间戳调度的规则
每个事务分配一个唯一的时间戳TS。
1. 读请求的处理
当调度器收到来自事务T的对数据项X的读请求r(X)时
如果TS(T) ≥ WT(X)即事务T的时间戳大于或等于X的最近写时间戳说明T的读请求是事实上可实现的即不会读到脏数据。 如果C(X)为真表示X的最近写已提交则同意请求并根据需要更新X的读时间戳RT(X)。如果C(X)为假表示X的最近写未提交则推迟T直到C(X)为真或写X的事务中止。 如果TS(T) WT(X)即事务T的时间戳小于X的最近写时间戳说明T的读请求是事实上不可实现的即会读到脏数据因此必须回滚T并重启。
2. 写请求的处理
当调度器收到来自事务T的对数据项X的写请求w(X)时
如果TS(T) ≥ PT(X) 且 TS(T) ≥ WT(X)即事务T的时间戳大于或等于X的最早提交时间戳和最近写时间戳说明T的写请求是事实上可实现的即T写X之后暂时不会被其他写覆盖必须执行。 为X写入新值。更新WT(X)为TS(T)。将C(X)设为false表示X的最新写尚未提交。 如果TS(T) RT(X) 但 TS(T) WT(T)即T的时间戳大于X的读时间戳但小于X的最近写时间戳说明T的写是事实上可实现的但X已有更晚的写。 如果C(X)为真则前一个X的写已提交忽略T的写。如果C(X)为假则推迟T直到C(X)为真或写X的事务中止。 如果TS(T) RT(X)即事务T的时间戳小于X的读时间戳说明T的写是事实上不可实现的必须回滚T。
3. 提交请求的处理
当调度器收到事务T的提交请求时
将T所写的所有数据库元素X的C(X)设为true表示这些写已提交。允许任何等待X被提交的事务继续进行。
4. 中止或回滚请求的处理
当调度器收到事务T的中止请求或决定回滚T时
任何等待T所写元素X的事务需要重新尝试其读或写请求检查这些操作在T的写被中止后是否仍然合法。
7.8.5 多版本时间戳
每个数据库元素如记录、块或页都可能有多个版本每个版本都与一个特定的时间戳相关联。这些版本记录了数据在不同时间点的状态。多版本时间戳的主要目的是允许事务在读取数据时即使其他事务正在修改这些数据也能继续执行而不会导致中止。这是通过让事务读取适合其时间戳的数据版本来实现的。
7.8.6 时间戳与封锁
时间戳机制在高冲突场景下由于多个事务尝试写入相同数据可能导致大量事务需要回滚增加系统延迟。适用于大多数事务为只读或并发事务较少读写同一数据元素的情况。封锁机制事务可能因等待锁而阻塞导致性能下降甚至可能出现死锁。在高冲突场景下即多个事务频繁读写相同数据元素时封锁机制的性能较好。
7.9 使用有效性确认的并发控制
有效性确认与时间戳的主要区别在于调度器维护关于活跃事务正在做什么的一个记录而不是为所有数据库元素保存读时间和写时间。事务开始为数据库元素写人值前的一刹那它经过一个“有效性确认阶段”这时用它已经读的和将写的元素集合与其他活跃事务的写集合做比较。如果存在事实上不可实现行为的风险该事务就被回滚。
7.9.1 基于有效性确认调度器的结构
告知调度器事务T的读集合RST和写集合WST读阶段事务读取其读集合RS(T)中的所有数据库元素。事务在其局部地址空间中计算将要写入的所有值但此时不修改数据库。有效性确认阶段调度器比较当前事务的读写集合RS(T)和WS(T)与其他活跃事务即在START或VAL集合中的事务的读写集合。如果发现存在冲突即当前事务的写集合与其他事务的读集合或写集合有交集且不满足可串行化的要求则事务被回滚。如果确认成功事务进入下一个阶段。写阶段事务将其写集合WS(T)中的值写入数据库。
为了支持做出是否确认事务有效性的决定调度器维护三个集合:START集合包含已经开始但尚未完成有效性确认的事务。对于每个事务T调度器记录其开始时间START(T)。VAL集合包含已经通过有效性确认但尚未完成写阶段的事务。T确认时间VAL(T)。FIN集合包含已经完成写阶段的事务。T完成时间FIN(T)。
7.9.2 有效性确认规则 规则一检查读后写冲突
对于所有已经过有效性确认即在VAL或FIN集合中且在事务T开始前没有完成的事务U即满足FIN(U) START(T)调度器需要检测是否存在读后写冲突。这种冲突发生在事务T读取了某个数据库元素X之后而事务U可能或已经修改了X的值。
具体检查检查RS(T) ∩ WS(U) 是否非空。如果非空说明事务T读取了事务U将要修改的数据库元素这可能导致事务T读到了旧值而事务U最终会写入新值从而破坏了串行顺序的假设。处理如果检测到这种冲突调度器必须回滚事务T以避免潜在的数据不一致。
规则二检查写-写冲突
对于所有已经过有效性确认即在VAL集合中且在事务T进入其有效性确认阶段前没有完成的事务U即满足FIN(U) VAL(T)调度器需要检测是否存在写-写冲突。这种冲突发生在两个事务都试图修改同一个数据库元素。
具体检查检查WS(T) ∩ WS(U) 是否非空。如果非空说明事务T和事务U都计划修改同一个数据库元素而根据假设的串行顺序事务U应该在事务T之前完成修改。处理如果检测到这种冲突调度器同样需要回滚事务T以确保事务的执行顺序与假设的串行顺序一致。
