数据库课堂笔记Ⅲ

数据库课堂笔记Ⅲ

数据库物理存储

​ 主要讲了计算机系统的存储体系,磁盘的结构与特性,DBMS数据存储与查询实现的基本思想,数据库之表和记录与磁盘块的映射,数据库之文件组织方法。

​ 计算机系统的存储体系。需要解决两个基本问题,如何高效存储(数据组织与索引),如何快速检索(查询实现与查询优化)。数据库管理系统实现的基础是存储体系,将不同性价比的存储器组织在一起,满足高速度,大容量,低价格。CPU与内存直接交换信息,按存储单元(存储字)进行访问,外存按存储块进行访问。通常来讲数据库都是存储在磁盘上的,因为主存是电易失的。磁盘以批量换速度。现在数据库还有磁带上的数据库,内存数据库(通过保持通电)。在访问磁盘数据库时都会将数据放到主存中并由CPU处理。

​ 操作系统如何组织磁盘上的数据,磁盘划分为若干个磁盘块,一个磁盘块相当于一个或若干个连续扇区,或者称为一簇。用户访问的时候,会将一个文件拆分成若干个磁盘块保存,文件不总是能顺序地存储在磁盘块上面的,需要有文件分配表。文件分配表中有一个数值,表示下一块应该是哪里,第一个磁盘块的确定是在目录或文件夹保存的,通常一个文件一个条目以及第一个簇的簇号。内存管理,内存也可以分解成页面,称为内存块或者内存页,需要将磁盘块装载到内存中才能进行处理。数据库中一条记录的地址是页面加页内偏移量。对于内存的时候需要申请,如果数据不再内存中需要从磁盘载入。

​ 磁盘的结构与特性。磁盘由若干个盘面组成,围绕主轴高速旋转,读写臂是可以移动的。磁道是磁盘上不同的同心圆,磁道上划分了若干个扇区。若干个连续的扇区形成了磁盘块,一个磁盘块可以连续地读写。如果要读写某一个磁盘块,首先需要旋转,然后移动读写臂(寻道)。读写磁盘需要给出盘面,磁道,扇区。注意一个磁盘有两面。

​ 磁盘数据的读写时间,有寻道时间,旋转时间,传输时间。在设计算法的时候需要考虑如何降低I/O次数,降低排队等待的时间,降低寻道/旋转延迟时间(同一磁道连续快存储,同一柱面不同磁道并行块存储,多个磁盘并行存储)。RAID技术,独立磁盘的冗余阵列。多个磁盘如何组织来共同完成读写任务。需要并行处理,需要对数据进行比特级拆分或块级拆分,可靠性技术,奇偶校验与纠错,磁盘间的读写校验。RAID0是块级拆分但无冗余(不能校验和纠错),RAID1每个磁盘有一个镜像磁盘,RAID2是4个磁盘存储4位+3个校验盘存储3校验位,RAID3交叉检验结合扇区/块读写校验和磁盘间的读写校验,RAID4是块拆分存储,RAID5是块交叉分布式校验(互为校验)。

​ DBMS数据存储与查询实现的基本思想。索引联系了逻辑数据库的表和实际数据库的磁盘。操作系统有FAT表(文件分配表)。内存中有数据库缓冲区,数据库缓冲区也有记录表。还有记录和记录所在位置的表。磁盘管理,读/写块,内存-缓冲区管理,文件管理/索引管理,数据逻辑结构,查询操作算法。

image-20200520224800797

​ 表-记录与磁盘块的映射。逻辑层面:表-记录-属性值,物理层面:文件-磁盘块-块内0/1数据。文件到磁盘块是FAT,磁盘块是由盘面,磁道和扇区确定。DBMS中是表到磁盘块进行映射。数据库记录在磁盘上的存储有定长记录和变长记录。变长属性需要加入标志(指针)来表示属性和记录的结束,最开始存储的部分有指针指向每条记录的开头位置。记录是非跨块存储还是跨块存储,跨块存储会影响并行处理。表占的磁盘块的分配方法1.连续分配可以让磁盘块读写速度加快,但是有扩展问题,需要预留空间,2.链接分配,数据块中包含指向下一数据块的指针,有访问速度的问题,3.按簇分配,簇是若干连续的磁盘块,簇内连续分配,簇之间靠指针连接,簇有时也称片段或者盘区,4.索引分配,索引块中存放指向实际数据块的指针,即联系了逻辑层面的表和物理层面的磁盘块。

​ 文件组织方法。数据组织需要考虑更新和检索需求。更新涉及到存储空间的扩展与回收问题,检索涉及到扫描整个数据库的问题,大批量处理数据问题。文件组织是指数据组织成记录,块和访问结构的方式,包括把记录和块存储在磁盘上的方式,以及记录和块之间相互联系的方式。存取方法是指对文件所采取的存取操作方法。一种文件组织可以采取多种存取方法进行访问。

​ 文件组织方法1.无序记录文件,堆文件,记录可以存储在任意位置,磁盘上记录是无序的,更新效率很高,检索效率低,新纪录始终插入到尾部,删除记录时需要移动后面的数据或者添加标志方便插入,这些有空间回收利用问题,需要进行数据库重组,将被删除记录彻底移走,2.有序记录文件,检索效率高,用于排序的属性称为排序字段,通常用主码,所以又称排序码,更新效率不高,可以使用溢出文件,即后插入的记录放在新的文件(溢出文件,是无序的)里,当溢出文件太大时需要数据库重组,将溢出文件合并到主文件中,3.散列文件,将记录散列到不同的桶当中,用于进行散列函数计算的属性通常称为散列字段,通常用主码,又称散列码,有可能有冲突,需要按序查找,当桶满了之后使用溢出桶,4.聚簇文件,是将具有相同或相似属性值的记录存放于连续的磁盘块中,多表聚簇,将若干个相互关联的Table存储与一个文件中在有些情况下可以大幅度提高查询速度。更新操作要求高可以使用无序记录文件,散列记录文件,检索要求比较高可以使用有序记录文件,如果性能下降了,需要数据库重组。不同的文件组织方法需要配合不同的存取方法和不同的存取算法才能发挥文件组织的效率。

​ Oracle数据库物理存储简介。从下至上依次是基本数据块,盘区,段,表,文件,表空间,数据库。每个数据库分成一个或多个表空间。每个数据库都分成一个或多个表空间,其中有一个系统表空间,用于关于表,列和索引的信息,数据存储在用户表空间,用户可以创建多个用户表空间。每个表空间由一个或多个操作系统文件构成,一个操作系统文件只能与一个数据库相关联,操作系统文件仅起占位的作用,数据在表空间中可跨文件进行操作。操作系统文件中存储一个表或多个表,表是以空间为单位的,即可以跨操作系统文件。只能看到数据文件,但是不能看到表和表空间,DBMS将若干个数据文件组成表空间。这是逻辑存储层。

​ Oracle数据库的物理存储层。由段,盘区和数据块构成的。数据块是基本的操作单位,也称为Oracle块,页(相当于页),盘区是特定数量的连续数据块(相当于簇),Oracle中的盘区是可以动态变化的,随不同的数据库存储需求而调整(可以设置盘区的大小),段是一组分配了特定数据结构的盘区,又分为数据段,索引段和临时段,一个表可以将数据存放在多个段内,一个段也可以存放多个表的数据。

​ Oracle定义数据库要创建表空间。一个表空间可以由多个文件构成。参数有表空间的文件是否可以自动扩展AUTOEXTEND OFF/ON,可以设置最小盘区是多大,可以设置表空间的初始容量,盘区的大小是可以动态调整的。在表空间中可以定义表,CREATE TABLE还可以定义表的物理存储参数,可以定义分配给表的初始盘区大小,指定第二个盘区的大小,指定第三个及后续分配的盘区的增长百分比,PCTFREE,PCTUSED通常是用来考虑磁盘块中数据存储利用率,分别是存储块中为更新预留空间的最小百分比和为存储块中制定块中数据使用空间的最低百分比。

​ 本讲总结。

image-20200521174858128

数据库索引

​ 主要讲了为什么需要索引,什么是索引,索引的简单分类,B+树索引,散列索引。

​ 什么是及为什么需要索引。索引是定义在存储表基础之上,有助于无序检查所有记录而快速定位所需记录的一种辅助存储结构。由一些列存储在磁盘上的索引项组成,每一索引项又由两部分组成1.索引字段,2.行指针。存储索引项的文件称为索引文件,存储表又称为主文件。索引文件组织有两种形式1.排序索引文件,2.散列索引文件,主文件也有这两种组织。在一个表上,可以建立多个索引,索引字段的值可以是Table中任何一个属性的值或任何多个属性值的组合值。索引文件比主文件小很多,因为主文件通常是多列构成的,索引文件可以一次性装入内存。更新需要保持主文件和索引文件一致。索引技术应用使检索效率大幅度提高,但同时也增加了存储空间和维护负担。衡量索引性能好坏需要衡量:访问时间,插入时间,删除时间,空间负载,支持存取的有效性(范围的查询)。对检索条件经常出现的属性建立索引。排序码,索引码和搜索码不一定具有唯一性(和主码不一样),搜索码是指在主文件中查找记录的属性或属性集。

​ SQL语言中的索引创建与维护。当定义Table后,如果定义了主键,系统将自动创建主索引,利用主索引对Table进行快速定位,检索与更新,索引可以由用户创建,也可以由用户撤销,DBMS将自动维护所有索引,当表被删除之后,定义在该Table上的所有索引都被删除。CREATE INDEX ON创建索引。如果索引不再需要,则可通过撤销命令DROP撤销用户创建的索引。要对经常出现在检索条件,连接条件,分组计算条件中的属性可建立索引,建立索引还要考虑索引的类型,索引如何支持存取的有效性。

​ 稠密索引与稀疏索引。索引可以分为稠密索引和稀疏索引。稠密索引是指主文件中的每一个记录的索引字段值都有一个索引项对应。索引文件包含了主文件对应字段的所有不同值。稀疏索引是对主文件部分记录的索引字段值有索引和它对应。稀疏索引中不存在搜索码的值不代表主文件中没有对应搜索码的记录。利用稀疏索引检索找字段值为K的记录,找到小于K的最大索引对应的索引项,从该索引项所对应的记录开始顺序进行Table的检索。稀疏索引必须要主文件按照索引码排序存储,稀疏索引空间占用更少,维护任务更轻,但速度更慢。主索引是每个磁盘块有一条索引项。

​ 稠密索引又分为候选键上的索引和非候选键上的索引,两者的差别是属性值是否唯一,非候选键属性可以分多种情况处理,如果索引文件中索引字段值是不重复的(即索引文件中索引值唯一),则可以把主文件排序,查找相同字段的记录时可以在索引到的记录附近查找,如果索引文件中不要求索引字段值唯一,则主文件可以不排序,多个相同的值有多个不同的链接,如果主文件没有排序,索引文件要求唯一,可以引入中间层,指针组。

​ 主索引与辅助索引。主索引是每一个存储块都有一个索引项。存储表的每一存储块的第一条记录,又称为锚记录,或者简称为块锚。主索引文件中保存了块锚主码值,主索引的索引字段值为块锚的索引字段值,而指针指向其所在的存储块。主索引是按索引字段值进行排序的一个有序文件,主索引的索引字段与主文件的排序码(主码)有对应关系。主索引是稀疏索引。

​ 辅助索引是定义在主文件的任一或多个非排序字段上的辅助存储结构。辅助索引通常是对某一非排序字段上的每一个不同值有一个索引项,如果是非候选键索引则需要采用一个类似链表的结构来保存包含该字段值的所有记录的位置。辅助索引是稠密索引,检索效率有时候相当高。一个主文件仅可以有一个主索引,但可以有多个辅助索引,主索引通常建立于主码/排序码上面,辅助索引建立于其他属性上面。主索引指针指向块地址,辅助索引指针不仅可以指向块地址,还可以直接是记录。可以利用主索引重新组织主文件数据,但辅助索引不能改变主文件数据。主索引是稀疏索引,辅助索引是稠密索引。

​ 其他类型的索引。聚簇索引和非聚簇索引,聚簇索引是指索引中邻近存储的记录在主文件中也是邻近存储的,否则是非聚簇索引。如果主文件按索引码排序则聚簇索引文件。对于聚簇索引如果主文件的某一排序字段不是主码,则该字段上每个记录取值便不唯一,此时该字段被成为聚簇字段,聚簇索引通常是定义在聚簇字段上。聚簇索引通常是对聚簇字段上的每一个不同值有一个索引项,主文件中多个相同的值存储在若干个块中,索引项指向第一个块。一个主文件只能有一个聚簇索引文件,但可以有多个非聚簇索引文件。主索引通常都是聚簇索引,但是索引总数和块数而不是主文件不同值的个数相同,辅助索引通常都是非聚簇索引。主索引/聚簇索引是能够决定记录存储位置的索引,而非聚簇索引则只能用于查询,指出已存储记录的位置。

​ 倒排索引。广泛用于文本检索。需要以关键词为单位建立索引,倒排是指一个词汇包含了哪些文档。词汇表指向一个中间结构,指针指向文档。多级索引,当索引比较大的时候,可以针对索引文件再建立索引,最典型是B树,B+树索引。多属性索引,索引字段由Table多个属性值组合在一起形成的索引。散列索引,使用散列技术组织的索引。网格索引,使用多索引字段进行交叉联合定位与检索。

​ B+树索引。B+树索引是一种多级索引,是一种以树型数据结构来组织索引项的多级索引。每个结点可以有多个指针和索引字段,指针可以指向索引块或数据块或数据块中记录。B+树中的叶子结点中的指针指向主文件的数据块或者记录。B+树能够自动保持与主文件大小适应的树的层次,每个索引块的指针利用率都在50%到100%之间。一块中有n-1个索引项和n个指针。指针在位置表示范围。非叶子结点的指针指向索引块,叶子结点指向数据块。叶子结点的最后一个指针指向下一个叶子结点。一索引块实际使用的索引指针个数d满足$n/2\leq d\leq n$,根结点至少2个指针被使用。索引字段值可能重复出现于叶子结点和非叶子结点,指向主文件的指针仅出现于叶子结点,所有叶子结点即可覆盖所有键值的索引,索引字段值在叶子结点中是按顺序排列的。叶子结点的集合就是主文件的完整索引。B+树的层数是相同的,是平衡的。在插入和删除需要分裂和合并结点,可以保持性质。

​ 用B+树建立键属性的稠密索引,索引字段是主文件的主键等。用B+树建立稀疏索引,索引字段是主文件的主键,指针指向数据块。用B+树建立非键属性稠密索引,可能有多条相同值,主文件必须按非键属性排序,指针可以指向重复值的第一个。用B+树建立非键属性的稠密索引,主文件中没有按非键属性排序,索引文件的索引字段值是有重复的,指针指向的是记录。

​ B树。B树的索引字段仅出现一次或者在叶子结点中或者在非叶子结点中。指向主文件的指针出现在叶子结点和非叶子结点中。插入记录时,伴随这结点的分裂与合并,层数相同,平衡。所有结点才能覆盖所有键值的索引。B树和B+树一块中存放的索引项个数是不相同的,B+数中的索引项更多。B+树的索引字段值重复出现在叶子结点和某一个非叶子结点,B树索引字段值是没有重复出现的,在叶子结点和非叶子结点中都仅出现一次。B+树的指针都存在叶子结点中,B树的指针存放在非叶子结点和叶子结点中。B+树和B树分裂和合并的方法是否一致,原理上应该是一致的,细微的操作上是有差别的。

​ B+树的插入与结点分裂。从叶子结点分裂到根结点。B+树的删除与合并。插入记录时,可能需要分裂:当索引块充满时,需要分裂,分裂可能引发连锁反应,由叶子结点直至根结点,分裂后需要仔细调整索引键值及指针,注意叶子结点之间链接关系的调整。删除记录时,可能需要合并:合并记录,从相邻结点中转移索引项(依旧是两个结点块),可能需要合并:两个结点块合并成一个结点块,合并可能引发连锁反应,由叶子结点直至根结点,合并后需要仔细调整索引键值及指针,注意叶子结点之间链接关系的调整。

​ 散列索引。有M个桶,有一个散列函数h(k),可以将键值k映射到0到M-1中的某一个值。将具有键值k的记录Record(k)存储在对应的h(k)编号的桶中。如果主桶满了可以增加溢出桶。目标是选择一个合适的散列函数,将一个Record集合(每个Record都包含一个关键字k)均匀地映射到M个桶中。可以实现快速定位。散列索引,内存数据可采用散列确定存储页,主文件可以采用散列确定存储块,索引也可以采用散列确定索引项的存储块。M个桶,一个桶可以是一个存储块,也可以是若干个连续的存储块。删除操作之后有可能需要合并溢出桶和主桶。如果有若干的溢出桶则需要二次检索,需要考虑的是均匀分布如何做到和桶的数目M如何确定,数目过大会浪费,数目过小会有溢出桶。桶的数目M是固定值,是静态散列索引,桶的数目随键值增多,动态增加,是动态散列索引,如果M发生变化,原来的已经散列存储的数据按新的桶数是否需要重新进行散列存储,M的变化是否会影响原来存储的内容。

​ 本讲总结。

image-20200523174517332

一趟扫描算法

​ 主要讲了数据库查询实现算法概述,以连接操作为例看逻辑实现算法与物理实现算法,利用迭代器构造查询实现算法,几个关系操作的一趟扫描算法,基于索引的查询实现算法。

​ 数据库查询实现算法概述。数据存储在磁盘上,磁盘上的信息以磁盘块为基本单位读写,内存中是以内存页也单位进行处理的,内存页通常和磁盘块有一一对应的关系,缓冲区管理器主要管理内存页的分配,管理内存页和磁盘块的映射,管理当需要访问的数据不在内存页中如何找到磁盘块读到内存中。数据库是以表,记录,属性来操作的。一个表占用哪些磁盘块,包括定长记录,变长记录,磁盘的跨块分配,非跨块存储,磁盘块的分配等等,文件的组织,堆文件,散列文件,排序文件等。如何建立表中数据和磁盘块中的数据建立映射,有各种索引,主索引,辅助索引,稠密索引,稀疏索引,聚簇索引,非聚簇索引。关系数据库的核心是编译器和执行引擎。

​ 数据库查询实现的基本思想。对于关系代数操作有五种基本的代数操作,对每个动作作为指令进行表达,将查询语句转化为关系代数操作的组合,由程序执行机构进行拆解,形成基本动作的调用次序,然后按照次序调用基本动作。查询实现和查询优化,首先将SQL语句转化为关系代数表达式,但是需要对关系代数表达式按照不同顺序执行,找一种执行时间最短的次序,这个过程是逻辑查询优化。要为每一个关系代数操作选择优化的执行例行程序,这就是物理查询优化,形成物理查询计划。接下来交给执行引擎。逻辑查询优化和物理查询优化合称查询优化。

​ 物理查询优化如何实现。需要定期获取数据库的相关信息,选择相应的操作的例行程序,进行代价估算,形成查询计划,这就是查询实现。

​ 数据库的三大类操作1.一次单一元组的一元操作,选择,投影,用迭代器算法,2.整个关系的一元操作,去重DISTINCT,分组GROUP BY,排序SORTING,用一趟扫描算法,两趟扫描算法,多趟扫描算法,用不同的算法是因为内存不一定足够,对于这些算法都有基于排序的算法,基于散列的算法和基于索引的算法,3.整个关系的二元操作,集合上的操作,包上的操作,积,连接。

​ 连接操作的实现算法。逻辑层面,从两个关系的第一个元组开始扫描每个元组,只要满足连接条件就连接起来,用两重循环,这只是逻辑算法,物理上要复杂。物理层面,以磁盘块为单位,需要装载进内存(I/O操作),然后再进行元组操作,$T_R,B_R,M,I_R,b$,两重循环读取两个关系的所有磁盘,磁盘的I/O操作,然后在两重循环里面进行逻辑层面的两重循环,算法的复杂性忽略内存操作的时间,I/O次数估计为$B_R+B_R\times B_S$,暂忽略保存结果关系的I/O次数,应用条件用三个内存页即可。

​ 连接操作的全主存实现算法。应用条件:假定内存页M大于等于两个关系的磁盘块,则每次读入一个磁盘块然后进行连接,算法复杂性的I/O次数估计为$B_R+B_S$,暂忽略结果关系保存的I/O次数。连接操作的半主存实现算法,如果内存仅能装载一个关系的所有元组,则将能够装载的关系一次性读入内存,然后每次读取另一个关系的磁盘块进行连接操作,算法的复杂性也为$B_R+B_S$。连接操作的大关系实现算法,如果两个关系都不能完全装入内存,内存中M-2块输入关系S,1块输入关系R的磁盘块,1块输出,算法复杂性的I/O次数估计为$B_R(B_S/(M-2))+B_S$。还有归并排序连接算法,散列连接(Hash连接)算法,索引连接算法。

​ 连用迭代器构造查询实现算法。查询实现的两种策略1.物化计算策略,是将每一个操作得到完整的结果,保留下来之后然后再进行下一个操作的处理,2.流水线计算策略,对关系R和关系S有输入缓冲区,没有形成的完整的中间结果关系,在形成一步结果之后立刻将结果传递给下一步。差别在于扫描一遍数据库可以完成几个操作和中间结果是否完整地存储。迭代器算法可以用于构造一个流水线计算策略。

​ 迭代器,迭代的读取一个集合中的每一个元素,而封装其读取细节。抽象类iterator,有函数Open,GetNext,Close。表空间扫描算法,需要定义Open,GetNext,Close函数,按顺序遍历所有元组。用R和S的迭代器构造一个并操作的迭代器,先后用两个关系的迭代器读取两个关系的所有元组。用R的迭代器构造R的选择操作的迭代器,用R的迭代器判断每个元组是否满足条件。投影迭代器,使用选择迭代器,每次将选择迭代器返回的元组做投影运算返回,流水线的操作可以通过这种嵌套构造迭代器来实现。R和S的连接运算的迭代器,用R的迭代器,S的迭代器,对于关系R的每一个元组,循环地(REAPT UITL)读S直到出现能够和S进行连接的元组。

​ 查询实现的一趟扫描算法。对于一次单一元组的一元操作可以使用迭代器算法,整个关系的一元操作,如果内存能够装载整个关系那么一遍扫描数据库就可以完成整个关系的一元操作,这就是一趟扫描算法,如果磁盘的内容不能完整地装到内存当中,那么就需要两趟扫描算法和多趟扫描算法。如何读取一个关系,聚簇的关系是指关系的元组集中存放,一个块中仅是一个关系中的元组。针对聚簇关系值需要按照关系将所在磁盘块中的内容读到内存中就可以了,表空间扫描算法TableScan(R),复杂性是B(R)的,扫描结果未排序,SortTableScan(R)是排序了的,复杂性是3B(R)。索引扫描算法,IndexScan(R)扫描结果未排序,B(R),SortIndexScan(R),扫描结果排序,B(R)或3B(R)。如果是非聚簇关系,关系的元组不一定集中存放,扫描结果未排序的复杂性是T(R),扫描结果排序是T(R)+2B(R)。

​ 去重复操作,DISTINCT,需要在内存中保存已处理过的元组,用数据结构组织(排序或者B+树之类的)用来查找是否出现过相同的元组,复杂性是B(R),即关系占用的磁盘块数,应用条件是B(R)$\leq$M。

​ 分组聚集计算,GROUP BY,需要在内存中保存所有的分组,保存每个分组上的聚集信息,用M-2个缓冲区保存属于哪一分组,需要建立内存数据结构,以快速定位一个元组。一趟扫描算法的要点是在内存中的数据结构怎么建立,可以建立排序结构,散列结构,B+树等。算法复杂性B(R),应用条件是所有分组的数量应能在内存中完整保存。例如可以用散列结构,数据结构需要快速插入和快速查找。

​ 集合上的并,交,差和包上的并,交,差是不同的,集合的操作要去重,都是扫描一个关系,然后再扫描另一个关系,包的操作需要计数每个元组的出现次,算法复杂性是B(R)+B(S),应用条件是min(B(R),B(S))$\leq$M。

​ 连接操作,对连接操作P4的改进,完全装入一个关系之后对这个关系建立数据结构,例如按照散列存储起来,这样遍历另一个关系的数据块的时候可以直接用数据结构进行比较。

​ 基于索引的算法。基于索引的算法广泛用于选择操作和连接操作。对于选择操作,没有索引的情况下把所有的元组读进内存然后逐个检查。选择条件中有设计到索引属性的时候,可以使用索引,聚簇索引和非聚簇索引使用时的效率不一样,可以用索引判断范围性的条件。如果R是聚簇的,不使用索引,查询代价是B(R)数据块数,如果R不是聚簇的,不使用索引,查询代价是T(R)元组数。V(R,a)表示关系R中属性a的不同值有多少个,假如是100,使用索引的查询代价都要除以100。

​ 基于有序索引的连接算法。关系R和S都有关于Y属性的B+数索引。对两个B+树的叶子结点进行归并排序,称为Zig-Zag算法。

​ 本讲总结。

image-20200622234303250

两趟扫描算法

​ 主要讲了为什么需要两趟算法,两趟算法的基本思想,两阶段多路归并排序算法,基于排序的两趟扫描算法,基于散列的两趟扫描算法。

​ 为什么需要两趟扫描算法。整个关系的一元操作存在什么问题,需要任何一个元组需要与所有元组进行比较,当需保存的待处理数据块数远远大于内存可用块数时怎么办,这就需要两趟算法,有时候需要多趟算法。

​ 两趟算法的基本思路,第一趟是划分子集,使子集具有某种特性,如有序或者相同散列值,处理好了之后写回到磁盘上,第二趟处理全局性的内容操作,形成结果关系,如多子集间的归并排序,相同散列值子集的操作等。原始关系,到具有某种特性的若干子集,到结果关系。需要考虑大数据集上的操作可否等于子集上操作的并集,例如元组在某一子集上无重复即相当于在全集上无重复,以及横向处理的子集上纵向归并结果是否等同于在全集上处理结果。

​ 两阶段多路归并排序,TPMMS。排序问题可以分为内排序问题和外排序问题。基本排序策略,将待排序数划分成N个子集合,使每个子集合的块数小于内存可用块数,每个子集合都可装入内存并采用内排序算法排好序并重新写回磁盘,然后在各子集间的归并排序,每个子集合占用的内存相等,设置输出缓冲区。算法的I/O次数,如果不考虑最终结果的写回是3B(R),如果考虑是4B(R),应用条件是子集合数和子集合的块数都小于内存块数,即大数据集块数小于内存块数的平方,如果大于可以采用多趟/多阶段,把子集合划分成子集合来对子集合排序。

​ 基于排序的两趟扫描算法。针对整个关系上的一元操作和二元操作,基于排序,基于两趟扫描完成处理1.去重复操作,第一趟划分子表,并进行子表排序,第二趟归并阶段,在排序的基础上,直接将重复的记录剔出掉,不输出。算法的复杂性不考虑输出是3B(R),考虑输出是4B(R),2.分组聚集操作,第一趟划分子表,并进行子表排序,第二趟归并阶段,在排序基础上,将不重复的记录,作为新分组输出,将重复的记录进行分组聚集计算。算法的复杂性和去重复相同,3.集合上的操作,也区分为包上的操作。对于包上的并操作,是无需两趟的,对于集合上的并操作,需要两趟的,因为需要去重复的环节,第一趟划R和S的子表并子表排序,第二趟,归并时注意是R的输入还是S的输入,R和S两路输入之间去重复性合并输出。集合上的交运算和包上的交运算都需要两趟,需要处理出现的次数或去重复,第一趟划分R和S的子表并子表排序,第二趟归并时注意是R的输入还是S的输入,R和S的两路输入之间按要求进行输出,对于集合交,如果t在R和S中都出现就输出,对于包交,输出t的次数是它在R和S中出现的最小次数,3.差运算,集合和包上的差运算都需要两趟,需要处理出现的次数或者去重复,大致过程和交运算一样,对于集合差,当且仅当t出现在R中但不出现在S中时输出,对于包差,输出t的次数是它在R中的次数减去其在S中出现的次数,4.连接运算,第一趟划分R和S的子表并进行子表排序,排序均基于Y属性(连接时判断的属性)排序,第二趟归并时注意是R的输入还是S的输入,R和S的两路输入之间进行连接检查并连接后输出。

​ 基于散列的两趟扫描算法。基本思想是将大数据集划分成若干个子集,第一趟用散列函数将原始关系划分成M-1个子表,并存储,每个子集合有相同的散列值,第二趟处理每个子表,用另一散列函数,将子表读入内存并建立内存结构,进行不同的操作,散列函数随操作的不同而有不同的选择1.去重复操作,可以是第一趟散列函数对部分属性取模M,第二趟散列函数对整个元组的值取模M,算法复杂性不考虑输出是3B(R),考虑输出是4B(R),元组在子表上不重复,则在大关系中亦不重复,2.分组计算操作,可以是第一趟散列函数计算分组属性的值对M取模,第二趟散列函数是用分组属性的二进制位串重新计算值,然后对M取模,算法的复杂性和去重复相同,同一分组的所有记录应在同一个子表中,同一子表中同一分组的所有记录应在同一内存块中,两个散列函数不能相同,但都以分组属性为基础,3.集合上的并交差和包上的并交差,包上的并运算只要一趟,集合上的并运算,第一趟以相同的散列函数散列R和S形成M-2个子表,第二趟将每个S子表装入内存中,再依次处理每个R子表的的每一块和判断在两个子表都出现的元组t,则仅输出t的一个副本,否则输出S和R的子表。包上的交和集合上的交,包上的差和集合上的差都可以采取相似的方法处理,4.连接操作,以连接属性Y作散列关键字,设计散列函数,第一趟,使用相同散列函数散列两个操作对象R和S,第二趟将S的每个子表读入到内存,再处理对应R的子表的每一块,进行连接。

​ 本讲总结。

image-20200623235238854

数据库查询优化技术

​ 主要讲了为什么要查询优化,什么是查询优化,查询优化的基本思路,逻辑查询优化,物理查询优化。

​ 什么是查询优化。关系数据库的执行效率问题。通过不同的关系代数可以得到不同的速度。先做选择运算和投影运算较好。查询优化就是如何使数据库查询的执行时间最短。有三个层面进行优化1.语义优化,利用模型的语义及完整性规则,优化查询,2.语法优化,逻辑层优化,利用语法结构,优化操作执行顺序,3.执行优化,物理层优化,存取路径和执行算法的选择与执行次序优化。

​ 查询优化的总体思路。书写SQL语句阶段,优化可以去掉无关的表,去掉无关的属性,改写成等价的效果更好的语句。可以从两个方面考虑1.语义等价性,2.完整性规则。SQL语句翻译成关系代数阶段(DBMS自动转换)阶段,优化可以尽可能早做选择运算,尽可能早做投影运算,改写成等价的效果更好的语句,称为逻辑优化/语法优化,优化后的关系代数表达式称为逻辑查询计划,基本思想是改变关系代数的操作次序。关系代数表达式执行阶段,每个关系代数操作都有若干个执行算法,为每个关系代数操作选取优化的执行层例行程序,形成物理查询计划,物理查询计划是基于不同算法的实现程序构造,物理查询计划的选择和优化问题就是物理优化和执行优化。优化之后将程序交给执行引擎调用例行程序进行处理,并返回结果。物理优化的过程(基本思路)是根据数据库的信息和例行程序库选择相应的执行层例行程序,然后代价评估,然后形成查询计划。

​ 逻辑层查询优化策略。逻辑优化是基于关系代数的优化。关系代数表达式可以用一棵语法树来表达出来。逻辑优化策略1.尽可能早做选择和投影,可使中间结果变小,节省几个数量级的执行时间,2.把选择与投影串接起来,一元运算序列可一起执行,只需对整个关系扫描一遍,可以用流水线的方式,3.把投影与其前或后的二元运算结合起来,在第一次用关系时去掉一些无关属性,可以避免多次扫描整个关系,4.把某些选择与其前的笛卡尔积合并成一个连接,连接操作的执行速度要比乘积之后再做选择的执行速度要快,5.执行连接运算前对关系做适当预处理,比如排序和临时索引,6.找出公共子表达式,可以优先计算,可以节省时间。

​ 关系代数操作次序交换的等价性。关系代数基本操作是并,积,差,选择,投影。等价性的定义,两个关系操作表达式的同名变量带入相同关系后产生相同的结果则称这两个关系操作表达式等价。定理有1.连接与连接,积与积的交换律,通常连接操作或积操作时选择结果集合小的表达式先装入内存,2.连接与连接,积与积的结合律,3.投影串接率,即把两个连续的投影合并为一个投影,也可以反过来,前者可以把两遍扫描变为一遍扫描,后者属性扩展便于投影操作的移动,4.选择串接率,可以把两遍扫描变为一遍扫描,分解复杂操作便于选择操作的移动,5.选择和投影的交换律,如果选择操作的条件都是投影操作中的属性则可以交换,如果选择运算中有不是投影运算中的属性,可以先把选择条件中所有的属性和投影运算中所有的属性投影出来,再选择,再投影,6.选择和积交换律,如果选择条件中属性都是做乘积运算中某个关系的属性,可以先对这个关系做选择运算再乘积,或者拆分两个交的选择条件来分别对两个关系先做选择运算再乘积,或者拆分出只和有一个关系属性的选择条件,对这个关系先做选择运算再乘积再做剩下的选择运算,7.投影和积的交换律,两个关系的乘积的投影等价于两个关系的属性的投影再乘积,8.选择和并的交换律,注意两个关系需要是并相容的,9.选择和差的交换律,10.投影和并的交换律,注意投影和差不能交换。

​ 基于关系代数的查询优化算法及示例。算法是首先拆分交的选择操作,把每个选择操作移到树的底部,对每个投影,移到树的底部(在选择操作上面),如果一个投影是对某表达式所有属性进行的,则去掉,然后把串接的选择和投影组合为单个选择,单个投影,或者一选择后跟一个投影,对修改后的语法树进行分组,对于二元运算将它和直接祖先放在一组,对于一元运算将链条合并,对于二元运算如果其中一个子结点为链条则合并,构造的程序以一组为一步。投影移动时加上经过的各个投影运算和选择运算需要的属性,去掉子树中没有的属性。

​ 物理层查询优化。为什么需要物理查询优化,对于选择操作有很多执行方案,有1.表空间扫描方法,2.利用属性的排序索引的方法,需要决定选择哪一个方法。物理查询运算符有获取关系元组的操作,1.TableScan(R),表空间扫描算法,2.SortTableScan(R),表空间扫描排序算法,3.IndexScan(R),索引扫描算法,4.SortIndexScan(R),索引扫描排序算法,关系操作的各种实现算法,选择,投影,去重复,分组,排序,集合上的操作,包上的操作,积,连接,每一种操作都有一趟算法,两趟算法,基于索引算法,基于散列算法,基于排序算法。物理查询运算符通常是关系代数操作符的一个特定实现。还有迭代器构建,流水化,物化。

​ DBMS如何衡量物理查询计划的优劣。衡量I/O访问次数,衡量CPU占用时间,内存使用代价,中间结果存储代价,计算量等。根据数据库中的数据字典或系统目录中的统计信息1.T(R),关系R的元组数目,2.B(R),关系R的磁盘块数目,3.I(R),关系R的每个元组的字节数,4.f(R),R的块因子,即一块能够存储的R的元组数目,5.V(A,R),R中属性A出现不同值的数目,6.SC(A,R),R中属性A的选择基数,满足属性A上的等值选择条件的平均元组数,7.b,每个磁盘块的字节数。统计信息不是自动收集的,必要要DBA使用特定命令来完成信息统计,统计信息可能会过时,需要定期执行。理想情况寻找最优的查询计划,现实情况避免最差的查询计划。

​ 代价估算。估算投影的大小,简单情况投影之后的元组数目一样,可以减少存储结果关系的块数。估算选择运算中等于条件的大小,介于0到T(R)-V(R,A)+1之间,估计值为T(S)=T(R)/V(R,A),这是按照平均分布来估计,当不知道V(R,A)时,估计T(S)=T(R)/10,估算选择条件中小于条件的大小,介于0到T(R)之间,估计值为T(S)=T(R)/2,实际应用(比较广泛)的估计为T(S)=T(R)/3。估算有等于条件和小于条件的交的选择操作,估计值为T(R)/(V(R,A)*3),即交的把两个条件相乘即可。估算并条件的选择操作,用T(R)减去两个条件相反条件的交的元组数。估算连接运算,估计值为T(S)=T(R)T(S)/max(V(R,Y),V(S,Y))。

​ 本讲总结。

image-20200625000159998

并发控制

​ 主要讲了为什么需要并发控制,事务调度及可串行性,基于封锁的并发控制方法,基于时间戳的并发控制方法,基于有效性确认的并发控制方法。

​ 为什么要进行并发控制。数据库可能存在不一致,多个用户对数据库进行操作,有READ,UPDATE,WRITE三个阶段和可能的ROLL BACK,可能会导致1.丢失修改,2.不能重复读,3.脏读,这是三种典型的不一致现象。并发控制有两大类方法,一类是基于封锁的方法,一类是基于撤回的方法。

​ 事务。事务是数据库管理系统提供的控制数据操作的一种手段,通过这一手段,应用程序员将一系列的数据库操作组合在一起作为一个整体进行操作和控制,以便数据库管理系统能够提供一致性状态转换的保证。事务从宏观上(程序员看到的)讲是一个存取或改变数据库内容的程序的一次执行,或者说一条或多条SQL语句的一次执行被看作一个事务。一个事务可处理一个数据或一条记录,也可能处理一批数据或一批记录,循环执行的程序语句,每次重复执行都将产生一个事务。事务的微观性(DBMS看到的事务),对数据库的一系列基本操作(读,写)的一个整体性执行。事务的并发执行,多个事务从宏观上看是并行执行的,但其微观上的基本操作(读,写)则可以是交叉执行的,有宏观独立完整和微观交错执行。

​ 事务的特性:ACID。有1.原子性,DBMS能够保证事务的一组更新操作是原子不可分的,2.一致性,DBMS保证事务的操作状态是正确的,符合一致性的操作规则,3.隔离性,DBMS保证并发执行的多个事务之间互相不受影响,例如两个事务T1和T2,即使并发执行,也相当于或者先执行了T1,再执行T2,或者先执行了T2,再执行T1,4.持久性,DBMS保证已提交事务的影响是持久的,被撤销事务的影响是可回复的。具有ACID特性的若干数据库基本操作的组合体被称为事务。事务管理器,可以产生事务,管理事务的时间戳,管理事务的一系列操作,事务调度器,可以对所有事务的操作产生一个读写操作序列(即调度),保证事务的一致性,可以用锁表。

​ 事务调度。事务调度是一组事务的基本步的一种执行顺序称为对这组事务的一个调度。并发(或并行)调度是多个事务从宏观上看是并行执行的,但其微观上的基本操作(读,写)则是交叉执行的。并发调度的正确性,当且仅当在这个并发调度下所得到的新数据库结果与分别串行地运行这些事务所得的新数据库完全一致,则说调度是正确的。

​ 可串行性。如果不管数据库初始状态如何,一个调度对数据库状态的影响都和某个串行调度相同,则我们说这个调度是可串行化的或具有可串行性。可串行化调度一定是正确的并行调度,但正确的并行调度,却未必都是可串行化的调度。并行调度的正确性强调内容结果的正确性,可串行性是指形式上结果正确性(读取了数据最终没有写入,而是写入了另外的答案,则是并行调度正确,但不是可串行性的)。可串行化的等效串行序列不一定唯一。

​ 事务调度的标记模型。冲突是调度中一对连续的动作,它们满足:如果它们的顺序交换,那么设计的事务中至少有一个事务的行为会改变。有冲突的两个操作是不能交换次序的,没有冲突的两个事务是可交换的。冲突的情况有1.同一事务的任何两个操作都是冲突的,2.不同事务对同一元素的两个写操作是冲突的,写写,3.不同事物对同一元素的一读一写(或一写一读)操作是冲突的,读写,写读。冲突可串行性,一个调度,如果通过交换相邻两个无冲突的操作能够转换到某一个串行的调度,则称此调度为冲突可串行化的调度。冲突可串行性是比可串行性要严格的概念。

​ 冲突可串行性判别算法。并发调度正确性包含可串行性,可串行性包含冲突可串行性。没有办法判断并发调度的正确性和可串行性,但是可以判断是否是冲突可串行性,如果是冲突可串行化的则一定是并发调度正确的。算法是构造一个有向图,结点是事务,边表示两个事务有冲突,由先发生的事务指向后发生的事务,如果有向图有环,则不是冲突可串行化的,否则是冲突可串行化的。

​ 基于封锁的并发控制方法。产生一个冲突可串行化的调度,有1.基于封锁的并发控制,2.基于时间戳的并发控制,3.基于有效性确认的并发控制,总体是两大类,一类是基于锁的方法,一类是基于撤回的方法。

​ 基于锁的方法。锁是控制并发的一种手段,每一数据元素都有一唯一的锁。每一事务读写数据元素前,要获得锁,如果被其他事务持有该元素的锁,则要等待,事务处理完成后要释放锁。L表示加锁,U表示解锁。锁是事务调度器管理和使用的,需要维护一个锁表Locks(elements,transactions),或者Locks(elements,transactions,Type)。调度器可利用锁来保证冲突可串行性。锁本身并不能保证冲突可串行性,锁为调度提供了控制的手段,但如何用锁,仍需说明。

​ 锁的类型。可以分为1.排他锁X,写锁,只有一个事务能读,写,其他任何事务都不能读,写,2.共享锁S,读锁,所有事务都可以读,但任何事务都不能写,3.更新锁U,初始读,以后可升级为写,4.增量锁I,增量更新(对元素增加某个值),区分增量更新和其他类型的更新,有些连续的增量操作可以交换顺序,有些不可冲突串行化的调度也可能是正确的并行调度。

​ 相容性矩阵。持有锁时是否可以申请这个锁的矩阵。读锁写锁协议,只有S锁和X锁,只有持有S锁并且申请S锁是可以的,其他都是不可以的。更新锁协议,有S锁,X锁,U锁,只有持有S锁申请S锁,持有S锁申请U锁时是可以的,其他都是不可以的。

​ 加锁/解锁时机。0级协议(0-LP),有写要求的数据对象A加排他锁,不再访问后即可解锁,可防止丢失修改,但允许脏读,允许重复读错误,1级协议(1-LP),有些要求的数据库对象A加排他锁,事务递交时刻解锁,可防止丢失修改,可回复,防止脏读,允许重复读错误,2级协议(2-LP),有写要求的数据对象A加排他锁,事务提交时刻解锁,有读要求的数据对象B加共享锁,不再访问后即可解锁,可防止丢失修改,防止脏读,不允许重复读错误,3级协议(3-LP),有写要求的数据对象A加排他锁,事务提交时刻解锁,有读要求的数据对象B加共享锁,事务提交时刻解锁,防止所有不一致性。

​ 隔离性级别。有1.读未提交,相当于0级协议,2.读已提交,相当于1级协议,3.可重复读,相当于2级协议,4.可串行化,相当于3级协议。

​ 封锁粒度。指封锁数据对象的大小,粒度单位有属性值,元组,元组集合,整个关系,整个DB,某索引项,整个索引。由前往后粒度越大,并发度越小,封锁开销小,由后往前,并发度大,封锁开销大。当前数据库基本都是在元组层面上。

​ 对于封锁协议要考虑封锁的类型,封锁的粒度,相容性矩阵,封锁的时机。

​ 两段封锁协议。一种基于锁的并发控制方法,2PL,two-Phase Locking protocol。读写数据之前要获得锁,每个事务中所有封锁请求先于任何一个解锁请求。把事务中的加锁,解锁划分为严格的两个阶段,加锁段,解锁段,在加锁段中不能有解锁操作,解锁段中不能有加锁操作,这个锁是排他锁,两段封锁协议可以保证冲突可串行性,可用归纳法证明。两段封锁协议可能产生“死锁”。

​ 基于时间戳的并发控制方法。时间戳是一种基于时间的标志,将某一时刻转换成的一个数值。时间戳具有唯一性和递增性。事务的时间戳是事务T启动时,系统将该时刻赋予T,为T的时间戳,时间戳可以表征一系列事务执行的先后次序,时间戳小的事务先执行,时间戳大的事务后执行,利用时间戳可以不用锁进行并发控制。借助时间戳,强制使一组并发事务的交叉执行,等价于一个特定顺序的串行执行,特定顺序是指时间戳由小到大,强制是指执行时判断冲突,如果没有冲突则执行,如果有则撤销事务并重启该事务,此时该事务获得了一个更大的时间戳,表明是后执行的事务。读-读无冲突,读-写或者写-读冲突(可能有冲突,要考虑时间),写-写冲突(可能有冲突,要考虑时间)。一种简单的调度规则,对DB中的每个数据元素x,RT(x)表示读过该数据事务中最大的时间戳,即最后读x的事务的时间戳,WT(x)表示写过该数据事务最大的时间戳,即最后写x的事务的时间戳,TS(T)即事务的时间戳,读-写并发,读x的时候看WT(x),写x的时候看RT(x),如果有冲突,撤回T,重启T,写-写并发,看WT(x),如果有冲突,T撤回重做,都是TS大的时候允许操作,读的时候要看WT,写的时候要看RT和WT。这种规则可以解决T过晚的读(后启动先写),和T过晚的写(先启动后写)。

​ 基于时间戳的另一种调度规则。第一种简单的调度规则不能避免脏读,不能放行一些事实上可实现的冲突,即托马斯写规则(重复写数据元素,后启动的写的先执行,先启动的写的操作就可以不执行),不能单纯地使用托马斯规则,因为后启动的事务可能被撤销。除了RT(x),WT(x),还有提交位C(x),当且仅当最近写x的事务已经提交,C(x)为真,目的是避免出现事务读另一事务U所写数据然后U终止这样的情况。调度器有三种动作1.同意请求,2.撤销/终止,并重启具有新时间戳的T,撤销加重启是回滚,3.推迟T。调度规则是假如调度器收到读操作请求,如果TS(T)大于WT(x),判断C(x),如果为真则同意请求,否则推迟,如果没有则回滚T,假如调度器收到写操作请求,如果TS(T)大于RT(x)和WT(x),则同意操作并置C(x)=false,如果在RT(x)和WT(x)之间,如果C(x)为真则忽略写操作(托马斯写规则),如果C(x)为假则推迟T,直到C(x)为真或者写x的事务终止,如果TS(T)小于RT(x),则回滚T,假如调度器收到提交T的请求,将T写的所有数据库元素x置C(x)=true,如果有任何等待x被提交的事务,这些事务就被允许继续进行,假如调度器收到终止T的请求,则检验任何等待T缩写元素x的事务必须重新尝试读或写,看这一动作现在T的写被终止后是否合法。

​ 基于有效性确认的并发控制方法。事务在启动时刻被赋予唯一的时间戳,以示其启动顺序,为每一活跃事务保存其读写数据的集合RS(T),WS(T)。通过对多个事务的读写集合判断是否有冲突,即有效性确认,来完成事务的提交与回滚,强制事务以可串行化的方式执行。

​ 事务分三个阶段。有1.读阶段,事务重数据库中读取集合中的所有元素,2.有效性确认阶段,调度器通过比较该事务与其他事务的读写集合来确认该事务的有效性,3.写阶段,事务往数据库中写入其写集合中元素的值。每个成功确认的事务是在其有效性确认的瞬间执行的,并发事务串行的顺序即事务有效性确认的顺序。

​ 调度器维护三个集合。有1.START集合,所有开始但尚未完成有效性确认的事务集合,2.VAL集合,已经确认有效性但尚未完成第3阶段写的事务,3.FIN集合,已经完成第3阶段的事务。

​ 可能的冲突。有1.U在VAL或者FIN中,FIN(U)大于START(T),RS(T)和WS(U)非空,即T后启动,T要读U中要写的数据,T不能进行有效性确认,T可能读到未写入的数据,2.U在VAL中,FIN(U)代VAL(T),WS(T)和WS(U)非空,即已经确认但未提交的事务U和T的写集合的交集不为空,T不能进行有效性确认,T有可能先写。有效性规则是根据冲突确定的。检测的时候按照有效性确认的顺序来逐个检查。

​ 本讲总结。

image-20200627002718077

故障恢复

​ 主要讲了数据库故障恢复的宏观思路,运行日志及其检查点,三种类型的运行日志,利用运行日志进行故障恢复。

​ 数据库的故障类型及其影响。在计算机内部的存储体系,外存通常是介质存储,CPU和内存按存储字直接访问,内存和外存按磁盘块来访问。在内存中又分为系统数据,和每个程序(事务)的数据,内存中有数据库的缓冲区,磁盘上有数据库。事务中的数据,数据库缓冲区和数据库之间保持一致很重要。事务是DBMS对数据库进行控制的基本逻辑单元,事务需要提交和撤销。提交后的事务对数据库的影响是深远的,持久的,撤销后的事务没有丝毫影响。数据元素可以是磁盘块,内存页,也可以是更小的一条记录,也可以更大,通常按照记录来考虑,但是DBMS在处理的过程中通常是以磁盘块作为一个数据元素。事务具有ACID特性,有1.原子性,2.一致性,3.隔离性,4.持久性。故障恢复设计到如何保证原子性和持久性。

​ 故障类型。有1.事务故障,某一个程序(事务)自身运行错误所引起的故障,影响该程序(事务)本身,2.系统故障,由于掉电,非正常关机等所引起的故障,影响正在运行的事务以及数据库缓冲区,数据库缓冲区将涉及正在运行和已经运行的事务,3.介质故障,由于介质损坏等所引起的故障,影响是全面的,即影响内存中的数据,又影响介质中存储的数据。故障恢复是指把DB由当前不正确的状态恢复到已知为正确的某一状态。DBMS中故障恢复程序约占10%,故障恢复是DBMS的核心技术。

​ 数据库故障恢复的宏观思路。需要保证事务的原子性和持久性。事务故障的恢复,可以重做事务和撤销事务,重做事务可保证已提交事务的持久性,而撤销事务则消除未提交事务的影响。对于系统故障,可以用运行日志,是DBMS维护的一个文件,该文件以流水方式记录了每一个事务对数据库的每一次操作以操作顺序,运行日志直接写入介质存储上,会保证正确性,当事务对数据库进行操作时,先写运行日志,写成功后,再与数据库缓冲区进行信息交换。按照运行日志记录的事务操作顺序重做事务或撤销事务,故障恢复是需要时间的。检查点是DBMS在运行日志中定期设置和更新的,检查点是这样的时刻,在该时刻,DBMS强制使内存DB Buffer中的内容与介质和DB中的保持一致,即将DB Buffer更新的所有内容写回DB中,检查点表征了在检查点之前内存中数据与介质中数据是保持一致的。系统故障的恢复,检查点之前结束的事务不需要恢复,检查点之后结束或发生的事务需要依据运行日志进行恢复,故障点前结束的重做,故障点时刻未结束的撤销。介质故障恢复,副本,在某一时刻,对数据库在其他介质存储上产生的另一份等同记录,由于介质故障影响全面,在用副本恢复后还需要依据运行日志进行恢复,如何确定备份的时刻:转储点,过频影响系统工作效率,过疏造成运行日志过大,也影响系统运行性能,备份转储周期与运行日志的大小密切相关。

​ 运行日志的概念。数据库通常由元素构成,通常是一磁盘块,以内存页/块,也可以更小是一记录,或者更大是一关系。每个事务都会读/写某些元素,READ(X,t),WRITE(X,t),事务发出,INPUT(X),OUPUT(X),缓冲区管理器发出。OUTPUT是强制性输出,将传冲去内容写回磁盘。每个事务都以提交或撤销结束,COMMIT,ABORT。DBMS需要保证事务的持久性和原子性。持久性是已提交的事务,缓冲区内容保证写回磁盘,未提交事务,缓冲区内容不能影响磁盘。

​ 缓冲区处理策略。缓冲区内容不一定和磁盘内容一致。有1.Force策略,内存中的数据最晚在commit的时候写入磁盘,2.No steal,不允许在事务commit之前把内存中的数据写入磁盘,3.No force,内存中数据可以一致保留,在commit之后过一段时间再写入磁盘,在系统崩溃的时候可能还没有写入到磁盘,需要Redo,4.Steal,允许事务commit之前把内存中的数据写入磁盘,可能导致系统崩溃的时候已经有一部分数据写入磁盘了,需要Undo。当前最常用的是Steal加No force。事务故障会影响事务的原子性。

​ 日志。一个包含日志记录的只能追加的顺序文件,不同事务的日志记录交错存储,按发生时存储。发生系统故障时,使用日志进行恢复,故障时已提交的事务重做,故障时未提交的事务,撤销。日志记录的信息有1.Start T,表示事务T已经开始,2.Commit T,表示事务T成功完成,3.Abort T,事务T未成功,被终止,4.T X v1,或T X v2,或T X v1 v2,表示事务T改变了数据库元素X,X原来的值为v1,X新的值为v2。有三种日志1.Undo型日志,Redo型日志,Undo/Redo型日志,这三类日志记录内容和记录次序不同,恢复策略也不同。

image-20200627171222663

​ UNDO型日志。对于任一事务T,按下列顺序向磁盘输出T的日志信息,首先T X v被写到日志中,其次 OUTPUT(X),最后COMMIT T或ABORT T被写到日志中。Undo型日志仅保留旧值,第一步的v为X原来的值。Undo型日志是将事务改变的所有数据写到磁盘前不能提交该事务。如何利用Undo型日志进行恢复,首先确定每个事务是否已完成,如果有START T和COMMIT T表明已完成,如果有START T和ABORT T表示已结束,但是未完成,如果只有START T则表明没有完成,然后从日志的尾部开始按日志记录的反序,处理每一日志记录,撤销未完成事务的所有修改,COMMIT T标记T已完成,ABORT T标记T已结束但未完成,T X v如果T未完成,则将X=v写回磁盘,否则跳过,START T跳过。

​ 为什么需要检查点。因为要确定哪一个更新没有被影响和处理到日志的哪一个位置才能结束。检查点有1.静止检查点,周期性地对日志设置检查点,停止接收新的事务,等到所有当前活跃事务提交或终止并在日志中写入了COMMIT或ABORT记录后,将日志刷新到磁盘,写入日志记录CKPT,并再次刷新日志,2.非静止检查点,在设置检查点的时候不必关闭系统,允许新事务进入,写入一条START CKPT(T1,…,Tk),其中T是所有活跃的未结束事务,继续正常操作,直到所有活跃事务都完成时,写入END CKPT。

​ 检查点使用。按照Undo型日志从后向前找到第一个检查点为止,恢复工作就结束了。如果是一个非静止检查点,在恢复的时候恢复到第一个START CKPT就可以了。

​ Redo型日志。对于任一事务T,按下列顺序向磁盘输出T的日志信息,首先T X v被写到日志中,其次COMMIT T被写到日志中,最后OUTPUT(X)。Redo型日志保留新值,T X v中v为X更新后的值。与Undo型的差别,在后两步,先写提交记录后输出,还是先输出再写提交记录。利用Redo型日志进行恢复,首先确定每一个事务是否已完成,如果是START T和COMMIT T则是已完成,如果是START T和ABORT T是已结束,未完成,如果是START T是没有完成的。从日志的起始位置开始按日志记录的正序处理每一日志记录,重做已提交事务的所有修改,如果是COMMIT T标记T已完成,ABORT T标记T已结束但未完成,T X v如果T已完成,则将X=v写回磁盘,否则跳过,START T跳过。非静止检查点的使用1.找到最后的END CKPT,2.找到对应的START CKPT,找到活跃事务最早开始事务START T的地方开始进行恢复。

​ Undo/Redo结合型日志。Redo型日志与Undo型日志的比较,Undo型日志OUTPUT必须先做,可能引起性能下降,频繁地写磁盘,Redo型日志OUTPUT必须后做,灵活性差。对于任一事务T,按下列顺序向磁盘输出T的日志信息,首先T X u v被写到日志中,可以是先COMMIT T被写到日志中,OUTPUT(X),也可以是先OUTPUT,COMMIT T。利用Undo/Redo型日志进行恢复,首先确定每一个事务是否已完成,如果有START T和COMMIT T则已完成,如果有START T和ABORT T则已结束,但未完成,如果有START则未完成。自前向后,按日志记录的正序,重做所有已提交的事务,自后向前,按日志记录的反序,撤销所有未完成事务的所有修改,COMMIT T标记T已完成,ABORT T标记T已结束但未完成,T X u v如果T未完成,则将X=u写回磁盘,否则将X=v写回磁盘,START T跳过。

​ 本讲总结。

image-20200627230436867