📚 读书笔记 | 数据库管理系统 - 原理与设计 (续)

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

大二下学期课程，记录一下学习的重点和笔记。🐷

《数据库管理系统 - 原理与设计》

本文内容包括书中的五个部分：数据库基础、存储与索引、查询评估、事务管理和数据库设计与调整

最后一部分只写了一部分的内容，因为上课也是只讲了这一部分的第一章的部分内容，以后有时间再继续读这本书，写的的确是很深入，对于数据库的理解很有帮助。

其实还有第二部分 应用程序开发的，只是这个部分理论的不多，大多是实际项目做法，就跳过了。

PS: 由于文章太长，因此切割成两个部分

第四部分 查询评估

查询求解概述

OVERVIEW OF QUERY EVALUTION

Descriptive data / metadata 元数据，存储在系统目录(system catalogs)中

系统目录

用户表以及索引对应的文件构成的集合表示了数据库中的数据

关系型 DBMS 使用一个目录表来维护关于其所有表的索引的信息。目录表也被称为数据字典、系统目录、简称目录

目录中的信息

缓冲池的大小、页的大小、关于单个表，索引和视图的信息。

对于每一个表：

  • 表名，文件名（或某种标识），以及文件存储的文件结构
  • 表中每一个属性的属性名和类型。
  • 表上每一个索引的索引名
  • 表上的完整性约束（主码、外码约束）

对于每一个索引：

  • 索引的名称和结构（B+树）

  • 搜索码所含的属性

对于每一个视图：

  • 视图的名称和定义。

关于表和索引的统计信息（非实时更新）:

  • 基数 Cardinality: 每一个表 R 的元组个数 NTuples(R)
  • 大小 Size: 每一个表 R 的页数 NPage(R)
  • 索引的基数 Index Cardinality: 每一个索引 I 中不同码值的个数 NKeys(I)
  • 索引的大小 Index Size: 每一个索引 I 的页数 INPage(I)
  • 索引的高度 Index Height: 每一个树非叶子层的层数 IHeight(I)
  • 索引的范围 Index Range 每一个索引 I 的当前最小码值 ILow(I)和最大码值 IHigh(I)

操作符求解概述

INTRODUCTION TO Operation Evaluation

对于大多数操作符来说，没有绝对最好的方法

影响算法的性能：表大小、存在的索引、排序的顺序、缓冲池大小、缓冲区替换策略

三种常用技术

  • 索引， Indexing：如果制定了一个选择或连接(selection or join condition)条件，使用一个索引去检查哪些仅仅满足条件的元组。
  • 迭代， Iteration： 逐个地检查输入表中的所有元组(Exam all tuples in an input table no use of the index)。
  • 划分， Partitioning： 通过在一个排序码(sort key)上划分元组，常常可以将一个操作分解成一组廉价(less expensive collection of operations on partitions)的操作。
    • 排序和哈希是两种常见的划分技术

访问路径

从表中获取元组的方法。由文件扫描或索引加上匹配选择的条件所构成。

  • An access path is a way of retrieving tuples from a table and consists of either (1) a file scan or (2) an index plus a matching selection condition.
  • Every relational operator 关系操作符 accepts one or more tables as input, and the access methods used to retrieve tuples contribute significantly to the cost of the operator.
  • A simple selection 简单的选择 that is a conjunction of conditions of the form attr op value由若干条件组成. Such selections are said to be in conjunctive normal form (CNF) 合取范式, and each condition is called a conjunct合取体.
  • 区别 合区范式：attr op value 这样的选择形式
    • 合取体：每一个这样条件
  • 索引可以用于获取那些刚好满足条件的元组 索引与一个选择条件相匹配。
  • A hash index matches a CNF selection 哈希索引搜索码中每一个属性在 CFN 选择中都以一个形如 attr op value 的条件，则哈希索引与该 CFN 选择匹配
  • A tree index matches a CNF selection
  • The conjuncts that the index matches are called the primary conjuncts in the section
    • 一个索引可能与选择条件中合取体的某个子集相匹配，尽管不匹配整个选择条件。索引所匹配的合取体成为选择中的主合取体
  • 访问路径中文 P299
  • 索引刚好满足
  • 选择条件比索引满足的少
    • HASH 不满足
    • B+树部位主排序的码值，不满足
  • 多个索引满足条件
    • 主合取体为和索引相匹配的部分成为主合取体 primary conjunct.
    • 必须用在选择条件中与索引不匹配的合取体来检查每一个获取的元组。
访问路径的选择型

Selectivity

一个访问路径的选择性是所有获取的页面数。(The number of pages retrieved(index pages plus data pages))

  • 三条选择路径
    • The index and a scan of the data file and the index scan
  • Most selective access path 最有选择性的路径：检索最少页的路径
  • 缩减因子：满足给定合取体的元组在表中所占的百分比 (reduction factor)
    • 多个合取体：缩减因子大约是各自缩减因子的乘积。

查询优化概述

Introduction to query optimization

  • 对查询语句进行语法分析
  • 由查询优化器负责选择最佳的查询求解计划
  • 优化器生成多个可选的执行计划，并选择轻重开销最小的计划

基本步骤:

  • 枚举求解表达式的各个执行计划
    • Enumerating alternative plans for evaluating the expression
  • 估算每个枚举的执行计划的开销，并选取开销最小的执行计划
    • Estimating the cost o each enumerated plan and choosing the pan with the lowest estimated cost

查询求解计划

Query Evaluation Plans

查询求解计划（执行计划simply plan）由一个扩展的关系代数树(extended relational algebra tree)和节点上 表示关系存取路径及关系操作的实现方法的标记组成。

可以由 SQL 语句转换为关系代数表达式， 然后表示成查询树

多处理器查询: 流水线求解

Pipelined Evaluation

当一个查询包括多个关系运算时，可以通过管道（pipeline）将操作的运算结果传递给下一个操作，而不需要将查询执行的中间结果保存在临时的关系中。

流水线技术在操作之间传递数据，避免了将操作的中间结果写回磁盘再读取出来的开销。

实物化临时元组（materialized）：用临时关系保存操作的中间结果，再由下一个操作继续处理。

流水线的查询求解就是调控执行计划中不同连接的运算速率的管理策略。

当一个一元操作的关系是以流水线的方式输入，这个操作是及时完成的。(on-the-fly)

It has the great virtue of not writing the result of intermediate jions to a temporary file because the results are produced, consumed, and discarded one page at a time.

好处：求解过程中每次生成、处理、然后丢弃一个数据页的中间数据，无需写入临时文件

迭代操作的接口

The Iterator Interface

每个关系操作有一个或者多个输出，在执行计划中表示为节点

组成执行计划树节点（采用流水线技术求解）的关系运算通常支持同一的迭代操作接口(uniformly iterator interface)，隐藏关系运算的实现细节。

包括 open，get_next，close

  • open： 对迭代操作进行初始化，为输入和输出缓冲区分配缓冲区页，也用来传递关系运算的参数
    • 分配缓冲区页
    • 传参
  • get_next： 调用每个输入节点的 get_next 函数，然后调用关系运算特定的实现代码(operator-specific code)处理输入元组
  • close：释放状态信息(deallocate state information)

仅仅支持流水线方式。

如果实现算法需要反复检查输入元组，那么就需要实物化输入元组

可选计划

ALTERNATIVE PLANS

下推选择

优化连接操作的一个启发性的规则是尽可能减少连接关系的大小。

检查是否可以将选择操作吓退到连接操作之前

一种方法就是提前进行选择操作。

使用索引

当存在可用的索引，就不下推选择操作，否则选择后就不存在索引了。

一个典型的优化器做些什么

TYPICAL OPTIMIZER DOES

关系查询优化器使用关系代数等价来确定一个给定查询的多个等价的查询表达式。

如果统一输入表集合上的两个关系代数对于输入表达式的所有示例都产生同样输出 ： 等价

考虑不同的查询计划

使用等价可以使我们将最初的表达式转化为等价的表达式：

  • 选择和叉积可以合并在连接中
  • 连接可以重新排序
  • 选择和投影可以减少输入的数据量，可以被“推”至连接之上
左深计划

left-deep

连接时优化器通常采用动态编程的方法来有效地搜索所有的左深计划。

选择左深计划的原因

  • 削减可选计划的空间
  • 允许我们生成所有的全流水线(fully pipeline)计划，即所有的连接可以使用流水线求解。

估算计划的代价

  • 一个计划的代价是其含有所有操作的代价之和。

    单个关系符的代价使用来自系统字典的信息(system catalogs)

    如果集中关注 I/O 代价，计划的代价被分成：

    • 读输入表 read the input tables
    • 写中间结果表 writing intermediate tables(全流水线不需要写中间结果表)
    • 可能会对最后结果排序 sorting the final result

外排序

EXTERNAL SORTING

根据查询码进行排序。

什么时候 DBMS 需要对数据进行排序

  • 用户需要按一定的次序返回查询结果
  • 在块载入树索引(bulk loading)时，排序时第一个步骤
  • 消除重复元组(duplicate copies)时需要排序操作
  • 重要的关系代数操作一些连接方法，需要进行排序

简单的两路归并排序算法

TWO-WAY MERGE SORT

文件排序时会产生一些有序的子文件，称之为段(sorted subfield as run)

If the bumber of pages in the input file is 2^k

  • Pass 0 produces 2^k storted runs of one page each
  • Pass 1 produces 2^(k-1) sorted runs of two pages each
  • …
  • Pass k produces 1 sorted run of 2^k pages

处理的遍数：[log2N + 1] I/O 开销 2N[log2N + 1]

假设有7个数据页，一共需要4遍，56次I/O

该算法只占用 3 个内存页。可以使用的主存再多，排序算法也不能有效利用。

外归并排序

采用 B - 1 路归并，第 0 遍生成的有序段的数目为 $N1=[N/B]$, 总的遍数为 $[log_{B-1}N1]+1$

假设有 B 个可用的页，需要排序的文件包括那个数据页。

  • 第 0 遍，每次读入 B 个数据页，生成[N / B]个长度为 B 的数据页的段。
  • 第 i 次处理，使用 B-1 个缓存输入，剩余一个作为输出。同时归并 B-1 个有序的段。

总遍数：(log(B-1) N1) + 1 (N1 = N / B) I/O 次数为 2N((log(B-1) N1) + 1)

I/O 次数已知->2Nn

多路归并(multiway merge)的 CPU 开销更大，需要从(B-1)个有序段中找出最小的记录，写到缓冲区

段数最小化：替换排序算法(replacement sort) 除了输入和输出两个缓冲区的元组。平均段长可以达到 2B

最小化 I/O 开销与 I/O 次数

块 I/O

块读写技术可以减少读写单个数据页的平均开销

第一次生成 N2 = [N / 2B ]个段，之后归并 F=[B / b] - 1 个有序段

处理遍数为$log_fN2$

双缓冲

Double Buffer

外排序中输入缓冲块的所有元组都用完了，程序发送 I/O 请求。读入当前有序段的下一个缓冲区块，同时暂停处理数据。

当输入缓冲区块的元组都处理完后，CPU 可以继续处理当前有序段的另一个输入的缓冲区块，同时发送 I/O 请求，读入下一个缓冲区块

有效降低文件排序的总开销

使用 B+树来排序

聚簇索引

如果采用第一种数据项格式，那么顺序访问的唯一开销就是读取顺序集合中的数据页（空间利用率大约为 67%，读取的数据页的数目会大于在文件中保存记录实际需要的数据页数）

采取第二种->从根到页+读取顺序集合+读取包括数据记录的 N 个数据页

比外排序效率更高

非聚簇索引

假定每个数据页平均记录数目为 p，总共有 N 个数据页，那么数据记录的数目是 p _ N。设 f 是数据条目大小与树记录大小的比，B+树页节点的数目近似为 f(data entries) _ N，因此顺序读取记录的总开销为 (f + p) * N = pN

完全取决于数据条目(data entries)的次序与存储次序的对应成都。

最坏的情况接近于 pN

采用排序算法效率比非聚簇索引高

关系操作求解

EVALUATING RELATIONAL OPERATORS

  • 在这里只考虑 I/O 的开销，而且只考虑读写的数据页数目
  • 对每个关系运算，我们都要讨论若干不同的算法

选择操作

无索引, 未排序的数据

No Index, Unsorted Data

不存在对应属性域上的索引，并且关系对于这个查询数据项时无序的。

可以扫描整个关系，对每个元组检查条件是否成立，并把满足条件的元组加入查询结果，但是开销是最大的。

无索引, 排序的数据

No index, Sorted

如果不存在对应属性域的索引，但是关系是按照这个属性域排序的，就可以使用二分法查找，复杂度为 $O(log_2M)$

但是实际上，如果 DBMS 支持第一种索引数据条目，那么关系的存储就不可能时有序的，如果需要维护顺序，最好使用第一种索引数据条目的 B+树索引。

B+树索引

查找索引树，之后找到指向满足条件的 R 元组的第一个索引条目，之后快速扫描叶节点数据页

确定起始叶节点 2-3 I/O

如果 B+树时非聚簇的，采用索引的开销依赖于满足查询条件的元组数目。

使用索引:

  • 查找索引树，找到指向满足条件的 R 元组的第一个索引条目
  • 扫描索引页节点的数据页
  • 读取所有查询码值满足选择条件的数据条目

如果查用第一种数据条目索引，那么唯一的开销就是读取数据条目了。

在第二或第三种索引，实际上，

  • 确定扫描的起始页节点的开销大约为 2-3 次 I/O 操作
  • 扫描页节点数据页，查找满足条件的数据条目的开销：依赖于满足条件的数目
  • 读取满足条件的元组的开销 The cost of retrieving qualifying tuples from R deoends on two factors:：
    • 依赖于满足条件元组(the number of qualifying tuples)的数目
    • 依赖于是否是聚簇索引，如果是，只需要 1 次 I/O 操作，否则每个数据元组都需要一次 I/O 操作（如果先按照 page-id 对 rid 排序，那么开销就等于包括满足条件的元组的数据页数目）这是非聚簇索引因为每条索引条目指向的元组可能都不在一个数据页中。

非聚簇索引求解范围查询是比较耗时的，简单扫描整个关系可能更好一点

哈希排序, 等价选择

查询的开销包括：

  • 在索引中查找合适的桶数据页
  • 从关系中读取元组（依赖于元组的数目或是否聚簇索引）

如果先根据元组所在的数据页对元组进行排序，那么 I/O 操作数就会极大减少。

一般的选择条件

CNF 和索引匹配

处理一般的选择条件，首先要把查询条件表示成合取范式(CNF)，即表示成通过逻辑符 $\and$ 连接起来的合取范式的集合。

对于包含 V 的合取式析取范式(disjunctive)，我们通常转为合取范式(contain disjunction)。

  • 合取conjunctive

  • 析取disjunctive

求解无析取的选择

Without Disjunction

  • 采用文件扫描的方法，或利用某个合取式匹配的(match)索引。再对元组检查所有的非主合取式。
  • 利用与某个合取式匹配的索引（或者多个），排序后求出集合的交集

求解有析取的选择

With Disjunction

  • 最有选择新的存取路径是文件扫描 file scan
  • 如果析取式中的每个条件都有相匹配的索引，可以利用这些索引找到候选的元组，求并集
  • 目前大多数数据库系统不能有效处理含有析取式的查询条件

投影操作

Projection Operation

实现投影操作，需要完成:

  • 清除不需要的属性值 Remove unwanted attributes
  • 清除重复的元组（使用划分技术：基于排序的算法/ 采用哈希函数的算法） Eliminate any duplicate tuples produced

基于排序的投影

  • 扫描关系 R， 生成只包含所需属性域的元组集合
  • 以元组中的所有属性域作为码，对元组进行排序
  • 顺序扫描集合同时比较相邻的元素以消除重复的元组

关系 R 的数据页数目为 M，则一共需要 M 次 I/O 操作，写回临时关系需要 T 次。T = O(M)。第二步开销 O(TlogT)，也就是 O(MlogM)。第三步为 T。

排序的算法可以进行改进：

  • 在外排序的第一遍处理过程中，消除不需要的属性域 写出 T / M * B 页临时关系，或者改进外排序算法一共生成 2B
  • 在归并有序段的过程中，消除重复的元组。
  • Avoid the temp files, work on the fly
    • Modify Pass 0 of sort to eliminate unwanted fields.
    • Modify Passes 1+ to eliminate duplicates.

Cost:

Reserves with size ratio 0.25 = 250 pages.

With 20 buffer pages can sort in 2 passes, so:

1.Read 1000 pages

2.Write 250 (in runs of 40 pages each) = 7 runs

3.Read and merge runs (20 buffers, so 1 merge pass!) 1 = logF (N1) + 1

Total cost = 1000 + 250 +250 = 1500.

基于哈希函数的投影

Projection based on Hashing

前提：缓冲区页的 B 足够大

算法组成： 划分和消除重复元组

划分： 采用一个输入缓冲区和 B-1 个输出缓冲区，每次读入一个数据页，消除不需要的属性域，对生于的属性应用哈希函数均匀分布在 B-1 个缓冲区

划分完成后，每部分的元组只包含指定的属性域，并且有相同的哈希值。

每部分包括 T/(B - 1)个数据页，哈希表为 T/(B-1) * f

至少需要根号(fT)个缓冲区页

基于投影的排序和哈希

不均匀分布使得基于排序的投影算法比哈希算法好。

基于排序的投影算法是有序的。

排序时投影操作的标准实现方法。

用于投影的索引使用

利用已有的索引，可以不需要存取实际数据，同时应用上面的投影技术，成为唯索引扫描技术 index-only scan

连接操作

The Join Operation

$R \bowtie S$, 是关系代数中最重要的操作之一， 是连接两个或多个关系中信息的主要方法。

商业数据库系统的连接操作：

  • 索引嵌套循环算法
  • 块嵌套循环算法
  • 哈希连接项技术
  • 排序归并连接算法
  • 面向数据页的嵌套循环算法
  • 简单哈希算法
  • 黄河哈希连接算法

迭代技术(iteration technique)： 简单的嵌套循环算法、块嵌套循环算法。

本质上是对叉积中的每个元组进行列举，并丢弃其中不满足连接条件的元组。

索引 index 和划分 partition 技术：把两个关系划分成部分，使得只有属于同一部份的元组才能进行连接。避免了叉积。

索引嵌套循环连接算法：对其中一个关系进行扫描，对关系中的每个元组，利用另一个关系的索引查找数据同一部分的元组，不需要列举叉积中的所有元组。

排序归并连接算法，哈希连接算法：利用连接条件划分关系中的元组，并且在计算关系的连接时之比较同一部份中的元组，但不依赖于已有的索引。（对关系排序和应用哈希函数来划分关系）

假设在关系 R 中，数据有 M 页， 每页有$P_R$ 个元组；

在关系 S 中，数据有 N 页， 每页有$P_S$个元组。

嵌套循环连接算法

Nested Loops Join

每次处理一个元组的嵌套循环算法(tuple-at-a-time nested loops evaluation)（就是两个循环遍历两个数据表找相同的元组）

I/O 效率非常地低

大概总的开销为$M+P_R\times M \times N$ 次 I/O

改进: 每次只连接一页，对关系 R 的每个数据页，读取 S 的每个数据页，然后进行连接，总的开销大概为$M+M\times N$

块嵌套循环连接算法

Block Nested Loop Jion

充分利用可用的缓冲区

将一个较少(smaller)的关系，如 R 整个读取缓冲区内，然后逐页扫描较大的关系 S，这样总的开销就为$M + N$

改进：创建关系 R 的哈希表，可以降低 CPU 开销

如果没有足够的内存容纳整个关系 R，那么也可以把 R 划分成可容纳的块。R 只扫描一次(outer relation)外关系，S(inner relation)内关系，多次扫描。一般如果有 B 个可用缓冲区，那么就读入 B-2 个页的 R 数据，剩余一个扫描 S 一个用作输出缓冲区。

因此总的开销为$M + N \times [M / (B -2)]$

块存取技术对连接算法的影响

最好的方法就是平均划分缓冲池， 这种分配方式导致扫描内关系的次数增加，但是读取磁盘时，定位数据页的时间会大大减少。（也可以采用双缓冲区技术）

索引嵌套循环连接算法

Index Nested Loops Join

利用关系的索引来存取关系。

读取关系 S 的匹配元组的开销，取决于索引类型和匹配元组的数目

  • 如果 S 索引为 B+树索引，那么查找适当的页节点通常需要 2-4 次 I/O 操作。如果为哈希，需要 1-2 次
  • 一旦找到了适当的页节点或桶，读取 S 元组的开销依赖于所有是否为聚簇索引。如果是，那么对于每个 R 元组 I/O 就是 1 次，否则每个匹配的 S 元组都需要一次。

开销$M + (M \times P_R) \times cost\ to\ find\ matching\ S\ tuples$

如果一个外关系元组相匹配的内关系元组的平均数目很小，那么索引嵌套循环连接算法的开销比简单的嵌套循环连接的开销小得多。

排序归并连接算法

Sort-Merge Join

基本思想： 在连接属性域上对两个关系进行排序，然后通过查找匹配的元组$r\in R$ 和 $s\in S$ 来归并两个有序关系。

排序使得识别在连接属性上属性值相同的元组的集合或部分更容易。

对于一个部分的 R 元组，只与同一个部分的 S 元组进行比较。

归并步骤：

  • 扫描关系 R 和 S，查找匹配元组
  • 扫描从两个关系的第一个元组开始，只要当前 R 元组小于当前 S 元组，就一直扫描关系 R
  • 反之，一直扫描关系 S
  • 直到找到匹配元素
  • 然后输出
    • 需要处理所有相等的元组
    • 对于“码 - 外码”(key-foreign key)的结构，只需要处理单边的重复
排序归并连接算法的开销

排序的开销为$O(MlogM)$

如果对 S 的部分只需要扫描一次（或者扫描后放在缓冲区），那么归并阶段的开销为$M+N$

如果有一个关系时有序的或者存在聚簇索引，那么这个算法时十分有效的

与块嵌套循环算法相比，排序归并连接算法的开销并不受缓冲区大小的影响，十分稳定，而如果缓冲区比较大，那么块嵌套循环算法开销就比较小。

如果对第二个关系中的部分关系进行多次扫描，那么可能增加算法的开销。但是通常只会对每个关系扫描一次。最坏形况下开销为$M \times N$（两个关系所有元组的连接属性上的值都相等）

Cost: Sort R + Sort S + ([R]+[S])

Suppose B = 35 buffer pages:

Both R and S can be sorted in 2 passes

Total join cost = 41000 + 4500 + (1000 + 500) = 7500

Suppose B = 300 buffer pages:

Again, both R and S sorted in 2 passes

Total join cost = 7500

记住外归并，不要跟块 I/O 混淆：

$$
2N[log_{B-1}(N / B ) + 1]
$$

对算法的改进

把关系排序和归并阶段与连接算法的归并阶段结合起来。

在归并 R 和 S 流时应用连接条件，消除叉积中不满足连接条件的元组

那么开销就可以降低为$3(M+N)$

块存取和双缓存技术

可以用其进行优化

哈希连接

首先在算法的划分阶段(partitioning phase)对关系 R 和 S 进行划分，在连接阶段(probing phase)比较 R 部分的元组和关系 S 相应部分的元组，检查等价条件。

划分阶段（创建阶段 building）类似于哈希投影算法中的划分阶段。

连接阶段（匹配阶段 matching）

主要思想：对两个关系的来连接属性（join attribute）应用同一个哈希函数 h，一旦划分了关系 R 和 S，只要有足够的内存，容纳关系 R 的每一个部分，就可以读入关系 R 和 S 一遍，完成连接操作。

实际处理还会用与 h 不同的哈希函数 h2，对哈希函数 h 的部分进行划分， 创建 R 部分的哈希表。因此需要多一点的内存。

总的开销为$3(M+N)$

创建过程 2(M+N)，合并过程为(M+N)

对内存的需求以及溢出处理

在连接阶段，为了保证算法的良好性能，大约需要缓冲区页的数目为$B>\sqrt{f \times M}$

对于溢出，我们首先把关系 R 和 S 的部分划分成子部分，然后对于子部分进行连接。

利用额外的内存, 混合哈希连接算法

基本思想在划分阶段为 R 的第一个部分创建哈希表，而不需要将该部分写回磁盘。

如果有足够的内存，那么开销可以降低到$M+N$

哈希连接算法和块嵌套循环连接算法

块嵌套循环连接算法需要对其中一个关系扫描多次，这种情况下混合哈希连接算法的性能相对更优。

哈希连接算法和排序归并算法

采用哪一种算法取决于：

  • 如果哈希连接算法中关系部分不是均匀分布，那么哈希连接算法的开销较大
  • 如果可用缓冲区数目在$[\sqrt{M}, \sqrt{N}]$, 那么哈希连接算法的开销较小，排序归并连接算法选哟内容较大关系的缓冲区
  • 如果缓冲区数目大于 sqrt(N)，归并和哈希都是 3(M+N)。
  • 排序归并算法的结果是有序的

Given a minimum amount of memory (what is this, for each?) both have a cost of 3(M+N) I/Os. Hash Join superior if relation sizes differ greatly (e.g., if one rein fits in memory). Also, Hash Join shown to be highly parallelizable.

Sort-Merge less sensitive to data skew; result is sorted.

一般的连接条件

对于多个等值连接条件：

  • 索引嵌套循环连接算法，可以为属性域组合创建索引
  • 对于排序归并连接算法，在组合属性域上排序
  • 对于哈希，在组合属性域上划分关系

对于非等值条件：

  • 索引嵌套循环连接算法需要使用 B+树索引
  • 哈希连接算法和排序归并连接算法不适用
  • Block NL quite likely to be the best join method here. 块嵌套循环是最有效的

性能取决于：

  • 关系的尺寸
  • 可用的存取方法
  • 缓冲区的大小
  • 连接算法

集合操作

Set Operations

集合操作有交、叉积、并、差等。

从实现的角度来看，关系的交和叉积可以被看做特殊的连接操作。

并和减主要问题在于消除重复的元组，有基于排序和哈希函数两种算法

用于并和差的排序

  • 并:

    • 在所有属性域上对关系 R 和 S 排序
    • 并行扫描关系 R 和 S，进行归并，并消除重复元组

    差：R - S

    • 类似与上面
    • 在归并阶段只把不在关系 S 中出现的 R 写回结果

用于并和差的哈希

并:

  • 利用哈希函数 h 划分关系 R 和 S
  • 对每个划分处理
    • 内存中创建$S_1$ 部分的哈希表（利用哈希函数$h2 \neq h$)
    • 扫描$R_1$， 对部分中的每个元组，找$S_1$的哈希表，如果元组已经在哈希表中，丢弃，否则，将元组加入到哈希表
    • 输出哈希表中的元组

差:

  • 类似于上面
  • 对部分的处理，为$S_1$创建哈希表后，对$R_1$进行扫描，对于$R_1$中每个元组，查找哈希表，如果元组不在哈希表中，就写如元组中

聚集操作

基本算法: 扫描整个关系，并维护元组的运行信息

开销：扫描所有元组的开销

据此操作也可以和 GROUP BY 语句联合使用。

  • 基于排序的算法很简单-在分组属性域上对关系排序，再扫描计算每个组的聚集操作的结果。
  • 基于哈希的算法，在分组域上创建关系的哈希表。
    • Sort on group-by attributes, then scan relation and compute aggregate for each group. (Better: combine sorting and aggregate computation.)
    • Similar approach based on hashing on group-by attributes.

使用索引实现聚集

  • 利用索引选择有用元组的技术不适合聚集操作。特殊情况可以使用数据条目 data entries 而不用数据记录 data records
    • Given a tree index whose search key includes all attributes in the SELECT or WHERE clauses, can do index-only scan.
  • 如果索引的查询码包括聚集查询涉及的使用属性域，可以对索引中数据条目应用于如上的聚集操作。
  • GROUP BY 语句的属性域列表是索引查询码前缀，索引为树索引，可以按照分组操作需要的顺序读取数据条目，避免关系排序的步骤。
    • if group-by attributes form prefix of search key, can retrieve data entries/tuples in group-by order.

典型的关系查询优化器

如何将 SQL 查询转化成查询块单元？

如果将查询块翻译成(扩展的)关系代数表达式？

查询优化器？

将 SQL 查询转换成关系代数表达式

查询语句首先被分解成若干个查询块

查询块是一个无嵌套的 SQL 语句，只有一个 SELECT 语句和 FROM 语句，最多有一个 WHERE, GROUP BY 和 HAVING 语句

把查询块表示成关系代数表达式

估算执行计划的开销

  • 对查询树的每个节点，估算执行对应操作的开销
  • 对查询树的每个节点，估算操作结果的规模，以及结果是否有序

估计结果的大小

查询结果元组的最大数目是 FROM 语句中所有关系的叉积，但是 WHERE 会消除其中一些候选数据。因此我们可以确定一个约简因子， 是得到结果关系大小与输入关系大小的比值。

约简因子取决于不同的查询条件

  • column = value
    • 如果关系column上存在索引I， 则约简因子近似于$1/(NKeys(I))$
    • 如果不存在索引，那么默认为$1/10$
    • 不存在索引也可以维护统计信息：关系某属性域上不同属性值的数目
  • column1 = column2
    • 如果关系分别存在索引I1和I2 那么约简因子近似于$1/ MAX(NKeys(I1), NKeys(I2))$ (对较小索引的每一个码值，在另一个索引中存在一个对应的码值)
    • 如果只有一个索引I， 那么就是$1/(NKeys(I))$
    • 不存在就默认值
  • column > value
    • 如果存在索引I， 那么近似于 $(High(I) - value)/(High(I) - Low(I))$
    • 如果不存在那么就任意设定一个小于 1/2 的分数
  • column IN (list of values)
    • 等于column = value的约简因子与列表中属性值数目的乘积

关系代数的等价

Statistic Meaning
NTuples # of tuples in a table (cardinality)
NPages # of disk pages in a table
Low/High min/max value in a column
Nkeys # of distinct values in a column
IHeight the height of an index
INPages # of disk pages in an index

选择

Selection

$\sigma {c1\and c2\and …\and cn}(R) == \sigma{c1}(\sigma_{c2}(…(\sigma_{c3}(R))…))$

利用该等式可以将若干选择操作结合成一个选择操作

而且选择操作时可以互换(commutative)的

$$
\sigma{c2}(\sigma{c1}(R)) == \sigma{c1}(\sigma{c2}(R))
$$

投影

Projection

从关系中消除属性域， 等价于一次性的清除除结果属性外的所有属性：

$\pi_{a1}(R) == \pi_{a1}(\pi_{a2}(…(\pi_{an}(R))…))$

叉积和连接

Cross-products and Joins

如果属性域以属性名而不是以位置区分，那么下面的操作时可以互换的

$R \times S == S \times R$

$R \bowtie S == S \bowtie R$

然后，我们可以任意选择连接操作的内关系和外关系

连接和叉积操作时满足结合律的

$R \times (S \times T) == (R \times S ) \times T$

$R \bowtie (S \bowtie T) == (R \bowtie S ) \bowtie T$

因此，当连接多个关系时，可以任意选择连接的次序。

选择, 投影和连接

如果选择操作只涉及投影操作所保留的属性域，那么他们可以互换

$\pi_a(\sigma_c(R)) == \sigma_c(\pi_a(R))$

其中 c 中设计的属性域必须在 a 中

可以将选择和叉积操作组合起来形成连接操作

$R\bowtie_{c}S == \sigma_c(R\times S)$

如果选择条件只涉及叉积或连接操作中一个参数的属性域，则可以将选择操作和叉积或连接操作互换：

$\sigma_c(R \times S) == \sigma_c(R)\times S$

$\sigma_c(R\bowtie S) == \sigma_c(R)\bowtie S$

c 中涉及的属性域，必须只属于关系 R，不能属于关系 S

投影操作与叉积也可以互换

$\pi_{a}(R \times S) == \pi_{a1}(R) \times {c} \pi{a2}(S)$

其中 a1 是集合 a 属于关系 R 的属性集合，a2 是集合 a 属于关系 S 的属性集合。c 设计的属性与必须属于集合 a

$\pi_{a}(R \bowtie S) == \pi_{a1}(R) \bowtie {c} \pi{a2}(S)$

a1是a中属于关系R的属性集合，a2是a中属于关系S的属性集合

目的：下推

列举可选的执行计划

单关系查询

  • Index I on primary key matches selection:

    • Cost is Height(I)+1 for a B+ tree.

  • Clustered index I matching one or more selects:

    • (NPages(I)+NPages(R)) * product of RF’s of matching selects.

  • Non-clustered index I matching one or more selects:

    • (NPages(I)+NTuples(R)) * product of RF’s of matching selects.

  • Sequential scan of file:

    • NPages(R).

  • If we have an index on rating:

    • Cardinality = (1/NKeys(I)) _ NTuples(R) = (1/10) _ 40000 tuples

  • Clustered index: (1/NKeys(I)) * (NPages(I)+NPages(R))

    = (1/10) * (50+500) = 55 pages are retrieved. (This is the cost.)

  • Unclustered index: (1/NKeys(I)) * (NPages(I)+NTuples(R))

    = (1/10) * (50+40000) = 4005 pages are retrieved.

  • If we have an index on sid:

    • Would have to retrieve all tuples/pages. With a clustered index, the cost is 50+500, with unclustered index, 50+40000.

  • Doing a file scan:

    • We retrieve all file pages (500).

多关系查询

  • 对于一些连接或者叉积的操作

    查询结果的大小取决于：

    • FROM 语句中所有关系的规模
    • WHERE 语句中条件的约简因子
    • 关系连接的顺序（影响中间连接结果）

第五部分 事务管理

事务管理概述

Overview of transaction management

事物的主要特点：

  • 并发执行concurrent execution
  • 在系统发生故障时能进行恢复recovery from system failure in a a DBMS

ACID 属性

事务应该具有下面四个主要特性:

  • A - 原子性(Atomicity)：所有操作要么全部被执行，要么都不被执行。不存在不完全的事务。
    • Either all actions are carried out or none are. users should not have to worry about the effect of incomplete transactions
  • C - 一致性(Consistency)：每个单独执行的事务，在不和其他事务并发执行情况下，都具有一致性
  • I - 隔离性(Isolation)：事务都是独立的，不受来自其他并发调度的事务的影响
    • Protected from the effects of concurrently scheduling other transactions
  • D - 持久性(Durability)：一旦事务完成，即使发生了故障，结果也能永久保持住。
    • Even if the system crashes before all its changes are reflected on disk.

一致性和隔离性

一致性：提交事务的用户必须确保事务执行完毕时仍保持数据库实例处于“一致”的状态

隔离性：当若干事务交叉执行时，实际处理结果和按照某种串行顺序执行事务相同。

  • DB consistency expressed as a set of declarative Integrity Constraints
    • CREATE TABLE/ASSERTION statements
  • Xacts（活动事务） that violate ICs are aborted
    • That’s all the DBMS can automatically check!

原子性和持久性

事务未正常结束的原因:

  • 执行时产生某些异常，被 DBMS 终止，以失败结束
    • A transaction can be aborted or terminated unsuccessfully by the DBMS because some anomaly arises during execution.
  • 一个或多个事务正常处理时系统发生崩溃system crash
  • 事务处于某种非预期状态 unexpected situation（如读到不正常数据、不能访问磁盘）而决定终止

DBMS 通过取消未完成的事务保证事务的原子性，将对数据库的所有写操作记录在日志里。日志也能用于确保持久性。

DBMS ensures transaction atomicity by undoing the actions of incomplete transactions.

To be able to ensure durability, the DBMS maintains a record, called the log, of all writes to the database

  • Atomicity means the effect of aborted Xacts must be removed
  • Durability means the effects of a committed Xacts must survive failures.

事务和调度

Transactions and schedule

事务可以看作一个操作系列或者队列，包括对数据库对象的读和写操作

A transaction is seen by the DBMS as a series or list, of actions. The actions that can be executed by a transaction includes reads and writes of database objects.

$R_T(O)$: 事务 T 读数据对象 O 的操作

$W_T(O)$: 事务 T 写数据对象 O 的操作

$Commit_T$: 成功提交

$Abort_T$: 终止并取消所有已执行的修改操作

两个重要假设Two assmuptions

  • 事务之间之只能通过数据库的读写操作进行交互（ only via database read and write operations）， 它们之间不能交换信息
  • 数据库是独立对象的固定的集合
    • A database is a fixed collection of independent objects.

调度是某个事务集合(a list of actions)对应的一个操作（读、写、提交、中止）列表，并且两个来自同一个事务 T 的操作必须和原来在 T 中的次序相同。（Two actions of a transaction T appear in a schedule must be the same as the order in which they appear in T）

一个调度表示的时实际 ACTION 或者潜在 POTENTIAL 的执行顺序。

完全调度： 调度中包括每个事务的中止或者提交操作

串行调度：事务一个接一个地开始执行一直到结束 Transactions are executed from start to finish

事务的并发执行

CONCURRENT EXECUTION OF TRANSACTIONS

并发执行的动机

  • 减少磁盘和 CPU 的空闲等待时间
    • Overlapping I/O and CPU activities reduces the amount of time disks and processors are idle
  • 增加系统的吞吐量system throughput（给定实践内完成事务的平均数目）
  • 减少事务的平均执行时间
  • The latency argument
    • Response time: the average time taken to complete an Xact.
    • A short Xact could get stuck behind a long Xact, leading to unpredictable（不可预测的） delays in response time.
  • The throughput argument
  • Throughput: the average number of Xacts completed in a given time.
  • Overlapping I/O and CPU activity reduces the amount of time disks and CPU are idle.

可串行化

Serializability

调度执行的结果对应的数据库实例和按照某种串行顺序执行这些事务得到的结果相同。

  • Two schedules are equivalent if:

    • They involve **the same actions of the same Xacts.（事务中有相同的操作）
    • and they leave the DB in the same final state.（最终状态是相同的）

  • A serializable schedule over a set S of Xacts is

    a schedule whose effect on any consistent database instance is guaranteed to be identical to that of some complete serial schedule over the set of committed Xacts in S.调度执行的结果对应的数据库实例按照某种串行顺序执行的这些事务结果相同。

不可串行化的原因:

  • DBMS 使用的并发控制方法采用的调度本身不是可串行化的，但等价于某种可串行化调度
  • SQL 允许某些应用程序执行 DBMS 采用不可串行化的调度

交叉执行带来的异常

读未提交的数据(WR 冲突)

Reading Uncommitted Data

事务 T2 读已经被另一个事务 T1 修改但还没偶提交的数据库对象 A， 这种读称为脏读

不可重复的读(RW 冲突)

Unrepeatable Reads

当事务 T1 读数据对象 A， 并仍在运行时， 事务 T2 修改了 A 的值。

重写未提交的数据(WW 冲突)

Overwriting Uncommitted Data

当 T1 已经修改了数据对象 A，并仍在运行时， T2 重复写入 A 的值。这种写称为盲写

存在更新丢失的问题。

包括中止事务的调度

可串行的调度的定义：如果事务集合 S 的一个调度执行的结果和 S 的所有提交事务构成的的某个完全串行调度执行的结果相同，那么该调度称为可串行化调度。

定义依赖于：已终止事务的所有操作都可以反做。

一个可恢复的调度要求：

如果一些事务读了另一些事务修改了的数据，那么他们的提交必须放在另一些事务的提交之后， 如果事务仅仅读已提交事务修改的数据，那么这个调度不但使可恢复的，而且也可以在中止一个事务时不用再中止其他事务。这种调度称为避免了级联中止。

取消事务可能带来的问题：

假设事务 T2 重写已经被事务 T1 修改的数据对象 A，此时 T1 仍在运行，但随后就中止了。T1 所有对数据库对象的修改将会被反做， 恢复为修改之前的值。但 T1 以这种方式中止，即使提交了事务 T2，那么 T2 进行的修改也会丢失。

可以使用一种严格的 2PL(strict 2PL)技术来防止这类问题的发生。

基于加锁的并发控制

DBMS 一般使用加锁协议来确保只运行可串行化的可恢复的调度，并且再取消中止事务时，已提交事务的所有事务都不会丢失。

严格的两阶段加锁

严格的 2PL，具有以下两个规则：

  • 如果事务 T 希望读（或修改）某个数据对象，那么应该首先申请一个该对象的共享（或排他）锁
  • 事务结束时，其拥有的所有的锁都会被释放。

严格 2PL 只允许可串行化调度

死锁

等待锁释放的事务循环被称为死锁

常用的方法时检测并解除死锁

发现死锁的一个简单的方法是超时机制，当一个事务为某个锁等待的时间过长，那么可以悲观认为是死锁循环并终止。

加锁的性能

加锁使用两种机制：

  • 阻塞(blocking)[极端情况为死锁]
  • 终止(aborting)

都涉及一个性能上的损失。

存在一个点，当再增加一个事务数的时候会导致吞吐量的下降，这个新增加的事务被阻塞并与现存的事务竞争或阻塞现存的事务，我们称系统在这一点失败。

当活动事务 30%被阻塞，失败一般就会发生

增加吞吐量的方法：

  • 对最小可能的对象加锁
  • 减少一个事务持有锁的时间
  • 减少热点（一个进程被访问或修改的数据库对象，并会导致大量的阻塞延迟）

SQL 对事务的支持

创建和结束事务

创建：用户执行一个访问数据库和目录的语句时候，如 SELECT, UPDATE, CREATE TABLE

结束：COMMIT 命令或 ROLLBACK(终止)命令

SQL 中支持长事务的特性：

savepoint：允许指定事务中的一点，并在这一点后选择性地执行回滚操作

1
2
SAVEPOINT <name>
ROLLBACK TO SAVEPOINT <name>

链事务(chained transaction)：可以在提交和回滚一个事务之后立即初始化另一个事务

使用AND CHAIN 关键字

应该锁住什么

不同粒度

幻影问题：一个事务查询一组对象两次，即使它自己没有改变任何元组，但是看到是不同的结果

需要加锁解决

SQL 中事务的特性

SQL 控制事务引起的锁的开销的模式：

  • 访问模式(access mode)
  • 诊断尺度(diagnostics size)：记录错误情况的个数
  • 隔离级别(isolation level)：控制了某一给定的事务暴露在其他并发执行的事务动作中的程度

崩溃恢复简介

CRASH RECOVERY

  • Undo the actions of aborted/failed Xacts.
  • Redo actions of committed Xacts not yet propagated to disk when system crashes.

偷帧和强制写页

写对象操作会带来两个问题：

  • 在事务 T 提交前，是否需要将 T 对对象 O 的修改从缓冲池写回磁盘？另外的事务调入时，而缓冲管理程序决定替换存有 O 的界面时，就需要写。如果允许，就称作采用了偷帧(Stealing Frame)方法。
  • 事务提交时，确保事务在缓冲池对数据对象进行的所有修改立即存盘，称为强制写页(Forcing Page)

不偷帧、强制写页的恢复管理程序更为简单

大多数使用偷帧和非强制写页，更加快。

非窃取 窃取
非强制 重做 快、重做、反做
强制 慢 反做

并发控制

2PL、可串行性和可恢复性

调度的冲突等价(conflict equivalent)：

  • 两个调度包括相同的事务操作(The same transaction)
  • 它们发生冲突操作对在调度中的次序相同（They order every pair of conlficting actions of two committed transaction in the same way）

You can transform S into a serial schedule by swapping consecutive non-conflicting operations of different xacts.

调度后对数据库具有相同的的结果

冲突可串行的调度：

  • 一个调度冲突等价于某个串行调度

也就是说串行中的顺序等于并发执行的顺序

每个冲突可串行的调度也是可串行化的，但可串行化不一定是冲突可串行化的。

冲突可串行化也是可串行化的

优先图(precedence graph)（依赖图）可以获取调度中事务间所有冲突，也称为可串行图。serializability graph

一个调度 S 的优先图包括：

  • 对于 S 中每个提交的事务用一个节点来表示 A node for each committed transaction in S
  • 如果$T_i$先执行，并且和$T_j$的某个操作发生冲突，那么应存在一条从$T_i$到$T_j$的边

严格的 2PL 只允许进行可串行化调度

  • 调度 S 是冲突和串行的，当且仅当其优先图中不会存在回路
  • 严格的 2PL 保证其允许的所有调度优先图中都不包含回路

变种：两阶段加锁(Two-phase Locking)(2PL)，允许事务在结束前释放锁。

Lock Compatibility Matrix 锁兼容矩阵

S X
S ✔ ❌
X ❌ ❌

两阶段封锁：分为请求锁和释放锁两个阶段

保证冲突可串行化，但是不保证避免级联中止。

严格两阶段封锁（事务结束时候才释放锁）可以保证避免级联中止。

对于某个调度，如果一个事务写入的值在其提交或者终止之前没有其他事务读或者重写，那么就称这个调度是严格的。

观测可串行化

View Serializability

冲突可串行化可串行化的充分但非必要条件

具有相同事务集合的两个调度 S1 和 S2 观测等价：

  • $T_i$在 S1 中读对象 A 的初始值，在 S2 中也必须读对象 A 的初始值
  • 如果在 S1 中$T_i$读的式$T_j$写入对象 A 的值， 那么在 S2 中$T_i$也必须读
  • 对于一个数据对象 A， 如果在 S1 中执行了最后一个对 A 的写操作，那么在 S2 中也必须执行最后一个对 A 的写操作
  • 可观测串行化不一定是冲突可串行化，如果不是则含有盲写 WW Conflict
类型 条件 特点
可串行化 调度执行的结果对应的数据库实例和按照某种串行顺序执行这些事务得到的结果相同 每个冲突可串行的调度也是可串行化的，但可串行化不一定是冲突可串行化的。严格的 2PL 保证避免级联中止和冲突可串行化。
冲突可串行化 一个调度冲突等价于某个串行调度 优先图中不会存在回路
观测可串行化 一个调度观测等价于某个串行调度 满足三个条件
可恢复的 如果一些事务读了另一些事务修改了的数据，那么他们的提交必须放在另一些事务的提交之后， 如果事务仅仅读已提交事务修改的数据 避免级联终止。严格的 2PL 不仅是可恢复的，而且是严格的。
避免中止级联 可恢复的，则避免级联中止 2PL 保证冲突可串行化，但是不保证避免级联止。严格的 2PL 保证避免级联中止和冲突可串行化。
严格的 如果一个事务写入的值在其提交或者终止之前没有其他事务读或者重写

加锁管理简介

锁管理器维护一个锁表(lock table)（一个以数据对象标识为码的哈希表）Lock and unlock requests handled by Lock Manager.

DBMS 在事务表中每个事务中包含一个指向事务拥有锁列表的指针，请求锁前需要检查这个列表。

锁表中的信息：

  • 拥有某个数据对象锁的事务数目 List of xacts currently holding lock
  • 锁的字样属性 Type of lock held (shared or exclusive)
  • 一个指向加锁请求队列的指针 Queue of lock requests

实现加锁和解锁请求

按照严格的 2PL

共享锁和互斥锁有不同的操作

加锁和解锁的原子性

Atomicity of Locking and Unlocking

需要使用系统的同步机制来原子地加锁和解锁。为了避免发生冲突，完整的加锁请求执行过程必须实现成原子操作。

护卫, 闭锁

Latches，Conveys

设置闭锁可以确保物理读写使原子操作（所有操作要么全部被执行，要么都不被执行）

DBMS 对事务的调度和操作系统对进程访问 CPU 调度的相互影响会出现护卫现象，大多数 CPU 周期都在进程切换上。

锁转换

LOCK CONVERSIONS

锁升级(upgrade)

事务已经具有了共享锁，如果将互斥锁请求放在等待队列的末尾，在等待队列中还有其他事务请求该对象互斥锁时可能造成死锁。使用锁的升级不能避免由冲突更新操作导致的死锁

一种更好的方法是不进行锁升级，开始时获得排它锁。

死锁处理

DEALING WITH DEADLOCKS

DBMS 必须周期性地检查死锁

锁管理器通过维护一个等待图来检测死锁循环

等待图(wait-for graph)：

  • 图中的节点对应正在处于执行状态的事务
  • 当且仅当$T_i$等待$T_j$释放锁时，存在一条$T_i$到$T_j$的边

定期检查等待图中是否存在表明死锁的回路

死锁预防

DL Prevention

如果死锁不是经常发生，基于计划的死锁检测在实际中效果更好，如果对锁的竞争很激烈，死锁可能性增大，基于死锁预防的方案能够得到更好的性能。

赋予每个事务一个优先权值(priority)，并保证低优先权的事务不用等待高优先权事务，可以预防死锁(preventing)

可以使用时间戳(timestamp)作为优先值

冲突处理策略：

  • 等待-死亡策略(Wait-die)：如果$T_i$的优先权高，则等到$T_j$结束，否则中止$T_i$
    • 低优先权的事务永远不会等待高优先权的事务
    • 非抢先
    • 事务变老之后会去等待越来越堵年轻的事务
  • 受伤-等待策略(Wound-wait)：如果$T_i$优先权高，中止$T_j$，否则$T_i$等待
    • 高优先权的事务永远不会等待低优先权的事务
    • 缺电：年轻事务可能被反复中止。

保守的 2PL(Conservative 2PL)也可以预防死锁

要求在事务开始执行时，需要获得事务的所需的所有锁

如果有一个需要的锁没有获得，需要释放之前获得的所有锁

特殊的加锁技术

Specialize Locking Techniques

动态数据库和幻影(phantom)问题

严格的 2PL 能够保证冲突可串行化

如果新的数据项加入到数据库中，那么冲突可串行化不能保证为可串行化

处理幻影问题：

  • 如果没有索引，那么 T1 需要对所有页加锁，并且不允许新的页加入到文件
  • 如果由一个索引，那么可以获取所有特定数据项的索引的锁，称为索引锁

B+树的并发控制

直接方法：忽略索引结果，直接将每个页看作一个数据对象，并采用某个版本的 2PL

2PL on B+-tree pages is a rotten idea.

简单的加锁策略会导致对树的高层节点的锁频繁争夺

注意:

  • 树的高层只用于直接搜索，所有数据存于叶子层
  • 插入时，如果更新的叶节点发生分裂并传播上去，那么对于上层节点也必须加锁。保守的加锁策略可能需要获得所有节点的互斥锁。称为锁耦合或 crabbing

对于兄弟节点：在分离一个叶子节点时，新的节点必须加到这个叶子节点的左边，否则兄弟节点的指针必须修改的节点为另一个。

多粒度锁

Multiple-Granularity Locking

能够对包含其他对象的对象加锁

除了共享锁（S）和互斥锁（X）外，还有准备共享锁（IS）和准备互斥锁（IX）

IS 仅和 X 有冲突，IX 和 S 和 X 有冲突。

如果事务需要对某个节点加 S 锁，那么需要先对所有子孙点加 IS 锁。

如果有事务对某个节点加了 S 锁，其他事务不能对该节点的子孙加 X 锁。

如果事务对某个节点加了 X 锁，其他事务不能对该节点的子孙加 S、X 锁

SIX 锁：等同于同时持有 S 锁和 IX 锁->事务需要读整个文件并修改其中的少量记录

顺着也在到根的顺序来解锁Must release locks in bottom-up order.

锁兼容矩阵

IS IX SIX S X
IS ✔ ✔ ✔ ✔
IX ✔ ✔
SIX ✔
S ✔ ✔
X

不加锁的并发控制

Optimistic Concurrency Control

乐观的并发控制方法：

思想： 尽可能允许事务执行

事务执行的阶段：

  • 读
  • 验证(Validation)：提交时检查是否会发生冲突，如果存在，事务中止，清空工作区并重新启动
  • 写

验证阶段，对于任意的$TS(T_i) < TS(T_j)$ 两个事务，以下条件之一必须满足（保证$T_j$更新的结果对$T_i$不可见）

  • $T_i$在$T_j$ 开始执行前已经结束所有三个阶段
    • 允许$T_j$看到$T_i$更新的结果，但是他们是串行的
  • $T_i$在$T_j$开始执行$T_j$的写阶段前已经结束，并且$T_i$没有写任何$T_j$读的数据对象
    • 允许$T_j$在$T_i$正在修改对象时读某些数据对象，但是没有读被修改过的对象
  • $T_i$ 在 $T_j$ 结束读阶段前已经完成了自己的读阶段，并且不写任何$T_j$读或写的数据对象
    • 允许同时写操作，但是写对象没有任何交集

基于时间戳的并发控制

Time-Based Concurrency Control

对每个数据库对象给定一个读时间戳RTS(O) 和一个写时间戳WTS(O)。

当事务 T 希望写对象 O 时：

  • TS(T) < RTS(O)， 写操作和对象 O 最近的读操作发生冲突，需要中止并重启事务 T
  • TS(T)< WTS(O), 可以忽略（被称为 Thomas 写规则）
  • 写对象 O，将 WTS(O) 设为 TS(T)

这个协议并不能保证是可恢复的

多版本并发控制

对于每个数据对象维护具有不同写时间戳的若干版本，并允许事务$T_i$读取时间戳在$TS(T_i)$之前最新的版本

崩溃恢复

CRASH RECOVERY

DBMS 事务管理器保证事务的原子性和持久性

  • 通过取消未完成事务的所有操作保证事务的原子性
  • 通过保证已提交事务的操作在系统崩溃和介质故障时仍然有效来获得事务的持久性

ARIES 算法简介

ARIES 是一个窃取、非强制的并发控制方法相结合的恢复算法

恢复数据库的三个阶段：

  • 分析：识别缓冲池中的脏页(dirty pages)和崩溃时当前事务
  • 重做(redo)：从日志的某个适合的点开始，重复所有的操作，将数据库恢复到崩溃时所处的状态
  • 反做(undo)：取消没有提交的事务的操作，使数据库只反映已提交事务的操作结果

三个基本原理：

  • 写优先日志法(Write-ahead logging): 任何对数据库对象的修改首先写入日志
  • 重做时重复历史(Repeating History During Redo) ARIES 从新追踪 DBMS 崩溃前的所有操作，使系统恢复到崩溃一样的状态。然后取消崩溃时还在执行的事务所做的操作。
  • 恢复修改的记录数据(Logging Change During Undo)：反做某些事务时，如果出现对数据库的改变需要写入日志，确保在重复崩溃时不需要重复这些操作。

#1 Must force the log record for an update to disk before the corresponding data page gets to disk.

  • This rule helps guarantee Atomicity.
  • This allows us to implement Steal policy.

#2 Must write all log records for an Xact to disk before commit.

  • I.e. transaction is not committed until all of its log records including its “commit” record are written to disk.
  • This rule helps guarantee Durability.
  • This allows us to implement No-Force policy.

日志

  • trail 或 journal

    是 DBMS 对其所执行操作的历史记录，保存在稳定存储中

    每个日志记录，都有一个唯一标识：日志顺序码(log sequence number, LSN)

    数据库中的每一页都应该包含日志中对该页进行最后一个更新的记录的 LSN，称为 pageLSN

    需要写入日志的操作：

    • 更新一页 Updateing a Page：在修改某页，一条类型为更新(update)的记录被添加到日志尾。该页的 pageLSN也被设成刚插入的更新日志记录的 LSN(该页要被锁定在缓冲池中)
    • 提交 Commit: 当一个事务决定提交，会强制写一个包含事务标识的类型为 commit 的日志记录，并将含有提交记录的日志尾写入到稳定存储。
    • 中止 Abort：如果事务被中止，包含事务标识的中止日志记录被添加到日志中，并取消事务。
    • 结束 End：中止或者提交事务时，除写中止或者提交日志记录外，需要进行其他操作。完成后包含事务标识的结束日志记录被添加到日志中。
    • 反做一个更新 Undoing an update：当事务回滚(roll back)时，事务已经进行的更新需要被取消，然后写入补偿日志记录 CLR(compensation log record)

    每条日志记录都有：

    • preLSN：可以快速获取前一条记录
    • transID：存储生成日志记录的事务的标识
    • type：表明日志记录的类型

更新日志记录 Update Log Records**

pageID：被修改页的标识

length：更新长度

offset: 更新开始的偏移量

before-image: 更新前数据值

after-image：更新后数据值

*补偿日志记录 * Compensation Log Records

CLR 包含一个称为undoNextLSN的字段，表示下一个需要反做操作的日志记录的 LSN。

CLR 描述的是一个永远不会被反做的操作

  • Possible log record types:
    • Update, Commit, Abort
    • Checkpoint (for log maintainence)
    • Compensation Log Records (CLRs)
      • for UNDO actions
    • End (end of commit or abort)

与恢复相关的其他数据结构

  • 事务表：每个当前事务的
    • 事务标识
    • 状态
    • 最近日志记录的 LSN，称为 lastLSN
  • 脏页表：
    • recLSN：引起该页变脏的第一个日志记录的 LSN（第一个需要重做的日志记录）

写优先日志协议

Write-ahead Log Protocol

WAL 是确保系统从崩溃中进行恢复时所有更新日志记录都可用的最主要规则

检查点

是对 DBMS 状态的一个快照，可以减少崩溃中进行恢复的工作量。

ARIES 方法设检查点的三个步骤：

  • 写入标识检查点开始的 begin_checkpoint 记录
  • 构造 end_checkpoint 记录，包括事务表和脏页表的当前内容，并添加到日志中
  • 在 end_checkpoint 记录写入稳定存储后开始：将特殊记录 master（包括 begin_checkpoint 的 LSN）写入稳定存储

最后得到事务表和脏页表内容保持在 begin_checkpoint 记录时的内容

这种检查点称为模糊检查点(fuzzy checkpoint)

当系统从崩溃中恢复时，重启过程从最近的检查点记录开始处理。

从系统崩溃中恢复

三个阶段：

  • 分析阶段
  • 重做阶段
  • 反做阶段

分析阶段

  • 确定从日志中开始重做的起点
  • 找出系统崩溃时缓冲池的脏页（一般为超集）
  • 确定出崩溃时正在执行，现在必须取消的事务

分析工作正向扫描日志，直到日志的结尾：

  • 如果事务 T 具有“结束”的日志，那么将 T 从事务表删除
  • 如果 T 没有结束，那么就需要把 T 的条目添加到事务表中
    • lastLSN 设为该日志的 LSN
    • 如果日志时 commit，那么就把状态设置为 C，否则为 U(反做)
  • 如果出现对页 P 产生影响并且能够重做的操作，那么就把 P 加入脏页表中
    • recLSN 设置为改日志的 LSN

重做阶段

No Forcing

重新执行所有事务的更新操作，包括已提交或者处于其他状态的事务

重做阶段从脏页表中最小的recLSN的日志记录开始，向前正向扫描日志到结尾。

不需要重做的情况：

  • 受影响的页没有出现在脏页表中
    • 表示该页的所有更新已经写入磁盘
  • 受影响的页在脏页表中，但是该数据项的 recLSN 比正在检查的日志记录的 LSN 要大
    • 表示更新操作已经写入磁盘
  • 对某个页面检索，获得它的 pageLSN，而这个 pageLSN 大于或等于正在检查的记录的 LSN
    • 保证更新页已经写入磁盘

最后，将所有状态为 C 的事务从事务表删除，并且日志中写入这些事务的最末记录。

反做阶段

Steal

从日志的最后向前扫描，取消崩溃时正在执行事务的所有更新操作。

反做算法

失败事务(loser transaction)：崩溃时正在执行的事务，所有操作必须按照日志中出现的相反的顺序取消

所有失败事务的lastLSN值的集合，称为ToUndo，取消时，反复从这个集合选择最大的 LSN 值开始处理，直到ToUndo为空

处理步骤:

  • 如果记录为 CLR，并且undoNextLSN不为空，则将undoNextLSN添加到集合ToUndo，如果undoNextLSN为空，那么就表示反做工作已经完成。日志中写对应事务的最末记录， 丢掉 CLR
  • 如果事务为更新记录， 写入 CLR 并反做相应更新操作，并且把更新日志记录的preLSN添加到集合ToUndo

重新启动时的崩溃

CLR 保证对于更新的日志记录只需执行一次。

中止一个事务只是反做操作的一个特例

  • How do you limit the amount of work in REDO?
    • Flush asynchronously in the background.
    • Watch “hot spots”!
  • How do you limit the amount of work in UNDO?
    • Avoid long-running Xacts.

介质恢复

基于定期生成的数据库副本

当数据库对象损坏，需要使用最近的副本，通过日志识别并重做已提交事务的更新操作

其他算法以及与并发控制的交互作用

其他算法在反做之后，重做非失败事务的操作， 并且回滚所有失败事务的操作。

第六部分 数据库设计与调整

模式求精与范式

模式求精简介

冗余导致的问题

Redundancy

数据的冗余是指数据库存储了同一信息的多个副本

可能导致的问题

  • 冗余存储
  • 更新异常：如果所有的副本没有进行同样的修改，那么就会导致数据不一致
  • 插入异常：只有当一些信息已经存储在数据库中，另外一些信息才能存入到数据库中
  • 删除异常：删除某些信息的时候可能会丢失其他的信息

空值有时能够解决某些问题，但是不是通用的方法。

模式分解

当我们再一个关系模式的属性之间强加一个关联时就会出现冗余现象。

函数依赖(Functional dependencies)可以识别这种情况并且给出进一步的求精(refinements)建议。

我们要将 R 的任意实例通过实例的投影来存储

模式分解中的问题

分解的时候需要考虑的问题：

  • 是否需要分解一个关系？
    • 如果一个关系满足某种范式(normal forms)，那么在分解中，一些特定的问题就不会出现。
    • 根据范式来判断是否需要分解。
  • 分解会导致什么问题的出现？

模式分解的两个有趣的性质：

  • 无损连接(lossless-join)
    • 可以通过连接分解所得到的较小的关系来恢复被分解关系的所有实例。
  • 保持依赖(dependency-preservation)
    • 所有依赖在较小的关系中得以保留

分解的缺点：

对于原关系的查询可能需要对分解的关系及进行连接

  • 如果经常发生这样的查询，那么分解所导致的心梗损失比较大。

If W -> Z holds over R and W 交 Z is empty, then decomposition of R into R-Z and WZ is loss-less.

函数依赖

Functional Dependencies 是一种完整性(IC)约束

函数依赖$X\rightarrow Y$ 表示如果两个元组在属性 X 上的值相同，那么他们在属性 Y 上的值也相同。

  • $X\rightarrow Y$ (X 决定 Y)

  • 码约束是函数依赖的一个特例。码中的属性相当于定义中的 X，关系中所有属性相当于定义中的 Y。

  • 函数依赖的定义中不要求集合 X 是极小的，但 X 要成为码，他必须满足极小的条件。

    • 如果$X\rightarrow Y$，存在 X 的子集 V 使得$V\rightarrow Y$，称 X 为超码
      • If “K -> all attributes of R” then K is a superkey for R

函数依赖推理

Reasoning About FDs

函数依赖集的闭包

Closure of a Set of FDs

所有可从函数依赖集 F 中推导出的函数依赖所组成的集合称为F 的闭包，记作$F^+$

Armstrong 公理：

  • 自反律(Reflexivity)：如果$X\supseteq Y $, 那么$X\rightarrow Y$
  • 增补律(Augmentation)：如果$X\rightarrow Y$， 那么对于任何 Z 来说$XZ\rightarrow YZ$
  • 传递律(Transitivity)：如果$X\rightarrow Y$而且$Y\rightarrow Z$，那么$X\rightarrow Z$

Armstrong 公理

  • 有效性(sound)是指由 F 出发，根据 Armstrong 公理推导出来的每个函数依赖一定在$F^+$中。
  • 完备性(complete)是指$F^+$中的每个函数依赖，必定可以由 F 触发根据 Armstrong 公理推导出来

衍生出来的规则：

  • 合并：如果$X\rightarrow Y$而且$X\rightarrow Z$， 那么$X\rightarrow YZ$
  • 分解：如果$X\rightarrow YZ$，那么$X\rightarrow Y$而且$X\rightarrow Z$

属性闭包

如果要判断一个给定的函数依赖，比如$X\rightarrow Y$， 可以通过计算 X 的属性闭包$X^+$来判断

1
2
3
4
5
closure = X;
Repeat until 没有变化: {
	If 有一个函数依赖 U->V 在F中，且U属被包含于closure,
	T很集合 closure = closure 并 V
}
  • Is AD a candidate key for R?
    • A+ = A
    • A not a key, nor is D so Yes!

注意区分：

码 在闭包中有

超码 If all attributes of R are in the closure of X, then X is a superkey for R.

候选码

范式

如果一个关系满足某种范式，一些特定的问题就不会出现。

范式以函数依赖为基础

  • 第一范式(1NF)
  • 第二范式(2NF)
  • 第三范式(3NF)
  • Boyce-Codd 范式(BCNF)

鲍依斯-柯德范式

R 是一个关系模式，X 是 R 属性的一个子集，A 是 R 的一个属性

对于每个 R 上成立的函数依赖$X\rightarrow A$ 下面的条件有一个成立：

  • $A\in X$，即他是一个平凡函数依赖
  • X 是一个超码

如果给定一个函数依赖集 F，为了确定 R 是否是 BCNF 范式，必须考虑闭包 F+中的每个依赖 X->A。只要检查左边部分是否为 F 的超码即可。

BCNF 范式可以确保只使用函数依赖不能再检测出冗余

如果一个关系满足 Boyce-Codd 范式，那么仅仅利用函数依赖，每个元组的部分字段的信息是不能通过所有元组的其他字段的值被推导出来

SNLRWH has FDs S -> SNLRWH and R -> W

Q: Is this relation in BCNF?

No, The second FD causes a violation;

W values repeatedly associated with R values.

第三范式

R 是一个关系模式，X 是 R 属性的一个子集，A 是 R 的一个属性

对于每个 R 上成立的函数依赖$X\rightarrow A$ 下面的条件有一个成立：

  • $A\in X$，即他是一个频繁函数依赖
  • X 是一个超码
  • A 是 R 的码的一部分

因为找出一个关系模式的所有码是一个 NP-complete 问题，因此判断一个关系模式是否为第三范式也是要给 NP-complete 问题

违反 3NF 的情况：

  • X 是某个码 K 的子集，这种依赖被成为部分依赖(partial dependency)， 即重复存储了(X,A)对
  • X 不是任何码的一部分，成为传递依赖(transitive dependency)， 表示依赖链$K\rightarrow X\rightarrow A$，在 知道一个 X 的值和 K 相关之前，必须知道一个 A 值和这个 X 相关。会导致插入、删除、更新异常

3NF 通过允许有码属性的特殊依赖(certain dependency)，能够使用具有特定需要的属性的分解，将每个关系模式都让分解为一组满足 3NF 范式的关系。

BCNF 范式比 3NF 严格

3NF 中允许出现冗余(A 属于码的一部分从而满足 3NF)

2NF 不允许存在部分依赖

3NF->2NF

  • The problems associated with partial and transitive dependences can persist in 3NF if
    • There is a non-trivial FD XàA,
    • and X is not a superkey,
    • but A is part of a key.

分解的特征

分解时消除冗余的一种工具

无损连接分解

能够根据分解后的关系恢复原来的关系

充要条件：$F^+$包含函数依赖$R_1\bigcap R_2 \rightarrow R_1$ 或 $R_1\bigcap R_2 \rightarrow R_2$

也就是$R_1$和$R_2$的公共属性包含$R_1$或$R_2$的码

如果函数依赖$X\rightarrow Y$成立， 并且$X\bigcap Y$为空集， 则分解$R-Y和XY$是无损连接分解

q(Avoids Problem #1 on our list.)

保持依赖分解

Intuitively, a dependency preserving decomposition allows us to enforce all FDs by examining a single relation instance on each insertion or modification of a tuple.

在对一个元组进行插入或修改时，保持依赖分解允许只通过检测单个的关系实例就能保证函数依赖集中的的所有函数依赖成立。

$F_x$为 F 在 X 上的投影，是闭包$F^+$中的一个函数依赖集合，这些依赖只包含 X 中的属性。The projection of F on X (denoted FX ) is the set of FDs U -> V in F+ such that all of the attributes U, V are in X. (same holds for Y of course)

如果$(F_x\bigcup F_y)^+=F^+$那么具有函数依赖集 F 的关系模式 R 分解为 X 和 Y 的分解为保持依赖分解

(Avoids Problem #2 on our list.)

Important to consider F + in this definition:

ABC, A -> B, B -> C, C -> A, decomposed into AB and BC.

Is this dependency preserving? Is C -> A preserved?

note: F + contains F 并 {A -> C, B -> A, C -> B}, so…

$F_{AB}$ contains A ->B and B -> A; $F_{BC}$ contains B -> C and C -> B .So, ($F_{AB} /bigcup F_{BC}$)+ contains C -> A

规范化

NORMALIZATION

可以通过无损连接分解将一个关系变为 BCNF， 但是不一定可以保持依赖

如果分解成既是无损也是保持依赖，那么一定可以分解为 3NF

分解成 BCNF

  • 假设 R 不是 BCNF。设$X\subset R$, A 是 R 中一个单独的属性，$X\rightarrow A$是一个违反 BCNF 的函数依赖，那么就将 R 分解成 R-A 和 XA(guaranteed to be loss-less)
  • 如果 R-A 和 XA 不是 BCNF，那么就继续分解

BCNF 中的冗余

为了保持依赖，可以加上一个具有依赖的属性的关系的冗余。

BCNF 中内部不存在冗余，但是关系之间可能还是存在冗余的。

分解为 BCNF 的不同方法

从不同的依赖出发，可以得到不同的 BCNF 关系集合

BCNF 和保持依赖

有些关系分解为 BCNF 就不能保持依赖了。

分解为 3NF

既是无损也是保持依赖的

  • We can ensure every relation schema can be decomposed into a collection of 3NF relations
  • using only lossless-join, dependency preserving decompositions.

函数依赖集的最小覆盖

最小覆盖满足以下条件：

  • 在 G 中每个依赖具有形式$X\rightarrow A$， 其中 A 是一个单属性
  • F 的必报$F^+$等于 G 的闭包$G^+$
  • 如果从 G 中删除一个或多个依赖，或者从 G 的一个依赖中删除属性后得到的依赖及 H，则$F^+\neq H^+$

最小覆盖就是一个等价的依赖集合

最小的体现：

  • 每个依赖都尽可能小，左边没有多余，右边是单属性
  • 每个依赖都是必要的

获取最小依赖的一般算法:

  • 将所有函数依赖变成标准形式，将所有依赖的右边变成单属性
  • 最小化每个依赖的左边，检查左边的属性是否可以删除
  • 删除冗余的函数依赖

分解为 3NF 的保持依赖分解

  • 标识出依赖集 F 中不在$F_i$并集闭包中的依赖，记作 N
  • 对于每个在 N 中的依赖$X\rightarrow A$，生成一个关系模式 XA，添加到分解 R 中

3NF 合成

对于 F 中的每个依赖$X\rightarrow A$都在 R 的分解中加入一个关系模式 XA

结语

以上就是一些数据库部分的知识，对于接下来的部分，有空会继续写下去的。😄

土豪通道
0%