精华内容
下载资源
问答
  • 数据库底层原理

    千次阅读 2019-04-24 21:44:47
    看到一篇很不错的数据库文章,拿过来...你可以自己谷歌/百度一下『关系型数据库原理』,看看结果多么的稀少【译者注:百度为您找到相关结果约1,850,000个…】,而且找到的那些文章都很短。现在如果你查找最近时髦...

    看到一篇很不错的数据库文章,拿过来分享一下:

    一提到关系型数据库,我禁不住想:有些东西被忽视了。关系型数据库无处不在,而且种类繁多,从小巧实用的 SQLite 到强大的 Teradata 。但很少有文章讲解数据库是如何工作的。你可以自己谷歌/百度一下『关系型数据库原理』,看看结果多么的稀少【译者注:百度为您找到相关结果约1,850,000个…】 ,而且找到的那些文章都很短。现在如果你查找最近时髦的技术(大数据、NoSQL或JavaScript),你能找到更多深入探讨它们如何工作的文章。

    难道关系型数据库已经太古老太无趣,除了大学教材、研究文献和书籍以外,没人愿意讲了吗?

    作为一个开发人员,我不喜欢用我不明白的东西。而且,数据库已经使用了40年之久,一定有理由的。多年以来,我花了成百上千个小时来真正领会这些我每天都在用的、古怪的黑盒子。关系型数据库非常有趣,因为它们是基于实用而且可复用的概念。如果你对了解一个数据库感兴趣,但是从未有时间或意愿来刻苦钻研这个内容广泛的课题,你应该喜欢这篇文章。

    虽然本文标题很明确,但我的目的并不是讲如何使用数据库。因此,你应该已经掌握怎么写一个简单的 join query(联接查询)和CRUD操作(创建读取更新删除),否则你可能无法理解本文。这是唯一需要你了解的,其他的由我来讲解。

    我会从一些计算机科学方面的知识谈起,比如时间复杂度。我知道有些人讨厌这个概念,但是没有它你就不能理解数据库内部的巧妙之处。由于这是个很大的话题,我将集中探讨我认为必要的内容:数据库处理SQL查询的方式。我仅仅介绍数据库背后的基本概念,以便在读完本文后你会对底层到底发生了什么有个很好的了解

    【译者注:关于时间复杂度。计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。如果不了解这个概念建议先看看维基百度百科,对于理解文章下面的内容很有帮助】

    由于本文是个长篇技术文章,涉及到很多算法和数据结构知识,你尽可以慢慢读。有些概念比较难懂,你可以跳过,不影响理解整体内容。

    这篇文章大约分为3个部分:

    • 底层和上层数据库组件概况
    • 查询优化过程概况
    • 事务和缓冲池管理概况

    回到基础

    很久很久以前(在一个遥远而又遥远的星系……),开发者必须确切地知道他们的代码需要多少次运算。他们把算法和数据结构牢记于心,因为他们的计算机运行缓慢,无法承受对CPU和内存的浪费。

    在这一部分,我将提醒大家一些这类的概念,因为它们对理解数据库至关重要。我还会介绍数据库索引的概念。

    O(1) vs O(n^2)

    现今很多开发者不关心时间复杂度……他们是对的。

    但是当你应对大量的数据(我说的可不只是成千上万哈)或者你要争取毫秒级操作,那么理解这个概念就很关键了。而且你猜怎么着,数据库要同时处理这两种情景!我不会占用你太长时间,只要你能明白这一点就够了。这个概念在下文会帮助我们理解什么是基于成本的优化

    概念

    时间复杂度用来检验某个算法处理一定量的数据要花多长时间。为了描述这个复杂度,计算机科学家使用数学上的『简明解释算法中的大O符号』。这个表示法用一个函数来描述算法处理给定的数据需要多少次运算。

    比如,当我说『这个算法是适用 O(某函数())』,我的意思是对于某些数据,这个算法需要 某函数(数据量) 次运算来完成。

    重要的不是数据量,而是当数据量增加时运算如何增加。时间复杂度不会给出确切的运算次数,但是给出的是一种理念。

    图中可以看到不同类型的复杂度的演变过程,我用了对数尺来建这个图。具体点儿说,数据量以很快的速度从1条增长到10亿条。我们可得到如下结论:

    • 绿:O(1)或者叫常数阶复杂度,保持为常数(要不人家就不会叫常数阶复杂度了)。
    • 红:O(log(n))对数阶复杂度,即使在十亿级数据量时也很低。
    • 粉:最糟糕的复杂度是 O(n^2),平方阶复杂度,运算数快速膨胀。
    • 黑和蓝:另外两种复杂度(的运算数也是)快速增长。

    例子

    数据量低时,O(1) 和 O(n^2)的区别可以忽略不计。比如,你有个算法要处理2000条元素。

    • O(1) 算法会消耗 1 次运算
    • O(log(n)) 算法会消耗 7 次运算
    • O(n) 算法会消耗 2000 次运算
    • O(n*log(n)) 算法会消耗 14,000 次运算
    • O(n^2) 算法会消耗 4,000,000 次运算

    O(1) 和 O(n^2) 的区别似乎很大(4百万),但你最多损失 2 毫秒,只是一眨眼的功夫。确实,当今处理器每秒可处理上亿次的运算。这就是为什么性能和优化在很多IT项目中不是问题。

    我说过,面临海量数据的时候,了解这个概念依然很重要。如果这一次算法需要处理 1,000,000 条元素(这对数据库来说也不算大)。

    • O(1) 算法会消耗 1 次运算
    • O(log(n)) 算法会消耗 14 次运算
    • O(n) 算法会消耗 1,000,000 次运算
    • O(n*log(n)) 算法会消耗 14,000,000 次运算
    • O(n^2) 算法会消耗 1,000,000,000,000 次运算

    我没有具体算过,但我要说,用O(n^2) 算法的话你有时间喝杯咖啡(甚至再续一杯!)。如果在数据量后面加个0,那你就可以去睡大觉了。

    继续深入

    为了让你能明白

    • 搜索一个好的哈希表会得到 O(1) 复杂度
      • 搜索一个均衡的树会得到 O(log(n)) 复杂度
      • 搜索一个阵列会得到 O(n) 复杂度
      • 最好的排序算法具有 O(n*log(n)) 复杂度
      • 糟糕的排序算法具有 O(n^2) 复杂度

    注:在接下来的部分,我们将会研究这些算法和数据结构。

    有多种类型的时间复杂度

    • 一般情况场景
    • 最佳情况场景
    • 最差情况场景

    时间复杂度经常处于最差情况场景。

    这里我只探讨时间复杂度,但复杂度还包括:

    • 算法的内存消耗
    • 算法的磁盘 I/O 消耗

    当然还有比 n^2 更糟糕的复杂度,比如:

    • n^4:差劲!我将要提到的一些算法具备这种复杂度。
    • 3^n:更差劲!本文中间部分研究的一些算法中有一个具备这种复杂度(而且在很多数据库中还真的使用了)。
    • 阶乘 n:你永远得不到结果,即便在少量数据的情况下。
    • n^n:如果你发展到这种复杂度了,那你应该问问自己IT是不是你的菜。

    注:我并没有给出『大O表示法』的真正定义,只是利用这个概念。可以看看维基百科上的这篇文章

    合并排序

    当你要对一个集合排序时你怎么做?什么?调用 sort() 函数……好吧,算你对了……但是对于数据库,你需要理解这个 sort() 函数的工作原理。

    优秀的排序算法有好几个,我侧重于最重要的一种:合并排序。你现在可能还不了解数据排序有什么用,但看完查询优化部分后你就会知道了。再者,合并排序有助于我们以后理解数据库常见的联接操作,即合并联接 。

    合并

    与很多有用的算法类似,合并排序基于这样一个技巧:将 2 个大小为 N/2 的已排序序列合并为一个 N 元素已排序序列仅需要 N 次操作。这个方法叫做合并

    我们用个简单的例子来看看这是什么意思:

    通过此图你可以看到,在 2 个 4元素序列里你只需要迭代一次,就能构建最终的8元素已排序序列,因为两个4元素序列已经排好序了:

    • 1) 在两个序列中,比较当前元素(当前=头一次出现的第一个)
    • 2) 然后取出最小的元素放进8元素序列中
    • 3) 找到(两个)序列的下一个元素,(比较后)取出最小的
    • 重复1、2、3步骤,直到其中一个序列中的最后一个元素
    • 然后取出另一个序列剩余的元素放入8元素序列中。

    这个方法之所以有效,是因为两个4元素序列都已经排好序,你不需要再『回到』序列中查找比较。

    【译者注:合并排序详细原理,其中一个动图(原图较长,我做了删减)清晰的演示了上述合并排序的过程,而原文的叙述似乎没有这么清晰,不动戳大。】

    既然我们明白了这个技巧,下面就是我的合并排序伪代码。

    C

    array mergeSort(array a) if(length(a)==1) return a[0]; end if //recursive calls [left_array right_array] := split_into_2_equally_sized_arrays(a); array new_left_array := mergeSort(left_array); array new_right_array := mergeSort(right_array); //merging the 2 small ordered arrays into a big one array result := merge(new_left_array,new_right_array); return result;

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    array mergeSort(array a)

       if(length(a)==1)

          return a[0];

       end if

     

       //recursive calls

       [left_array right_array] := split_into_2_equally_sized_arrays(a);

       array new_left_array := mergeSort(left_array);

       array new_right_array := mergeSort(right_array);

     

       //merging the 2 small ordered arrays into a big one

       array result := merge(new_left_array,new_right_array);

       return result;

    合并排序是把问题拆分为小问题,通过解决小问题来解决最初的问题(注:这种算法叫分治法,即『分而治之、各个击破』)。如果你不懂,不用担心,我第一次接触时也不懂。如果能帮助你理解的话,我认为这个算法是个两步算法:

    • 拆分阶段,将序列分为更小的序列
    • 排序阶段,把小的序列合在一起(使用合并算法)来构成更大的序列

    拆分阶段

    在拆分阶段过程中,使用3个步骤将序列分为一元序列。步骤数量的值是 log(N) (因为 N=8, log(N)=3)。【译者注:底数为2,下文有说明】

    我怎么知道这个的?

    我是天才!一句话:数学。道理是每一步都把原序列的长度除以2,步骤数就是你能把原序列长度除以2的次数。这正好是对数的定义(在底数为2时)。

    排序阶段

    在排序阶段,你从一元序列开始。在每一个步骤中,你应用多次合并操作,成本一共是 N=8 次运算。

    • 第一步,4 次合并,每次成本是 2 次运算。
    • 第二步,2 次合并,每次成本是 4 次运算。
    • 第三步,1 次合并,成本是 8 次运算。

    因为有 log(N) 个步骤,整体成本是 N*log(N) 次运算

    【译者注:这个完整的动图演示了拆分和排序的全过程,不动戳大。】

    合并排序的强大之处

    为什么这个算法如此强大?

    因为:

    • 你可以更改算法,以便于节省内存空间,方法是不创建新的序列而是直接修改输入序列。

    注:这种算法叫『原地算法』(in-place algorithm)

    • 你可以更改算法,以便于同时使用磁盘空间和少量内存而避免巨量磁盘 I/O。方法是只向内存中加载当前处理的部分。在仅仅100MB的内存缓冲区内排序一个几个GB的表时,这是个很重要的技巧。

    注:这种算法叫『外部排序』(external sorting)。

    • 你可以更改算法,以便于在 多处理器/多线程/多服务器 上运行。

    比如,分布式合并排序是Hadoop(那个著名的大数据框架)的关键组件之一。

    • 这个算法可以点石成金(事实如此!)

    这个排序算法在大多数(如果不是全部的话)数据库中使用,但是它并不是唯一算法。如果你想多了解一些,你可以看看 这篇论文,探讨的是数据库中常用排序算法的优势和劣势。

    阵列,树和哈希表

    既然我们已经了解了时间复杂度和排序背后的理念,我必须要向你介绍3种数据结构了。这个很重要,因为它们是现代数据库的支柱。我还会介绍数据库索引的概念。

    阵列

    二维阵列是最简单的数据结构。一个表可以看作是个阵列,比如:

    这个二维阵列是带有行与列的表:

    • 每个行代表一个主体
    • 列用来描述主体的特征
    • 每个列保存某一种类型对数据(整数、字符串、日期……)

    虽然用这个方法保存和视觉化数据很棒,但是当你要查找特定的值它就很糟糕了。 举个例子,如果你要找到所有在 UK 工作的人,你必须查看每一行以判断该行是否属于 UK 。这会造成 N 次运算的成本(N 等于行数),还不赖嘛,但是有没有更快的方法呢?这时候树就可以登场了(或开始起作用了)。

    树和数据库索引

    二叉查找树是带有特殊属性的二叉树,每个节点的关键字必须:

    • 比保存在左子树的任何键值都要大
    • 比保存在右子树的任何键值都要小

    【译者注:binary search tree,二叉查找树/二叉搜索树,或称 Binary Sort Tree 二叉排序树。见百度百科 】

    概念

    BST-624x321

    这个树有 N=15 个元素。比方说我要找208:

    • 我从键值为 136 的根开始,因为 136<208,我去找节点136的右子树。
    • 398>208,所以我去找节点398的左子树
    • 250>208,所以我去找节点250的左子树
    • 200<208,所以我去找节点200的右子树。但是 200 没有右子树,值不存在(因为如果存在,它会在 200 的右子树)

    现在比方说我要找40

    • 我从键值为136的根开始,因为 136>40,所以我去找节点136的左子树。
    • 80>40,所以我去找节点 80 的左子树
    • 40=40,节点存在。我抽取出节点内部行的ID(图中没有画)再去表中查找对应的 ROW ID。
    • 知道 ROW ID我就知道了数据在表中对精确位置,就可以立即获取数据。

    最后,两次查询的成本就是树内部的层数。如果你仔细阅读了合并排序的部分,你就应该明白一共有 log(N)层。所以这个查询的成本是 log(N),不错啊!

    回到我们的问题

    上文说的很抽象,我们回来看看我们的问题。这次不用傻傻的数字了,想象一下前表中代表某人的国家的字符串。假设你有个树包含表中的列『country』:

    • 如果你想知道谁在 UK 工作
    • 你在树中查找代表 UK 的节点
    • 在『UK 节点』你会找到 UK 员工那些行的位置

    这次搜索只需 log(N) 次运算,而如果你直接使用阵列则需要 N 次运算。你刚刚想象的就是一个数据库索引

    B+树索引

    查找一个特定值这个树挺好用,但是当你需要查找两个值之间的多个元素时,就会有麻烦了。你的成本将是 O(N),因为你必须查找树的每一个节点,以判断它是否处于那 2 个值之间(例如,对树使用中序遍历)。而且这个操作不是磁盘I/O有利的,因为你必须读取整个树。我们需要找到高效的范围查询方法。为了解决这个问题,现代数据库使用了一种修订版的树,叫做B+树。在一个B+树里:

    • 只有最底层的节点(叶子节点)才保存信息(相关表的行位置)
    • 其它节点只是在搜索中用来指引到正确节点的。

    【译者注:参考 B+树 , 二叉树遍历    维基百科

    database_index

    你可以看到,节点更多了(多了两倍)。确实,你有了额外的节点,它们就是帮助你找到正确节点的『决策节点』(正确节点保存着相关表中行的位置)。但是搜索复杂度还是在 O(log(N))(只多了一层)。一个重要的不同点是,最底层的节点是跟后续节点相连接的。

    用这个 B+树,假设你要找40到100间的值:

    • 你只需要找 40(若40不存在则找40之后最贴近的值),就像你在上一个树中所做的那样。
    • 然后用那些连接来收集40的后续节点,直到找到100。

    比方说你找到了 M 个后续节点,树总共有 N 个节点。对指定节点的搜索成本是 log(N),跟上一个树相同。但是当你找到这个节点,你得通过后续节点的连接得到 M 个后续节点,这需要 M 次运算。那么这次搜索只消耗了 M+log(N) 次运算,区别于上一个树所用的 N 次运算。此外,你不需要读取整个树(仅需要读 M+log(N) 个节点),这意味着更少的磁盘访问。如果 M 很小(比如 200 行)并且 N 很大(1,000,000),那结果就是天壤之别了。

    然而还有新的问题(又来了!)。如果你在数据库中增加或删除一行(从而在相关的 B+树索引里):

    • 你必须在B+树中的节点之间保持顺序,否则节点会变得一团糟,你无法从中找到想要的节点。
    • 你必须尽可能降低B+树的层数,否则 O(log(N)) 复杂度会变成 O(N)。

    换句话说,B+树需要自我整理和自我平衡。谢天谢地,我们有智能删除和插入。但是这样也带来了成本:在B+树中,插入和删除操作是 O(log(N)) 复杂度。所以有些人听到过使用太多索引不是个好主意这类说法。没错,你减慢了快速插入/更新/删除表中的一个行的操作,因为数据库需要以代价高昂的每索引 O(log(N)) 运算来更新表的索引。再者,增加索引意味着给事务管理器带来更多的工作负荷(在本文结尾我们会探讨这个管理器)。

    想了解更多细节,你可以看看 Wikipedia 上这篇关于B+树的文章。如果你想要数据库中实现B+树的例子,看看MySQL核心开发人员写的这篇文章 和 这篇文章。两篇文章都致力于探讨 innoDB(MySQL引擎)如何处理索引。

    哈希表

    我们最后一个重要的数据结构是哈希表。当你想快速查找值时,哈希表是非常有用的。而且,理解哈希表会帮助我们接下来理解一个数据库常见的联接操作,叫做『哈希联接』。这个数据结构也被数据库用来保存一些内部的东西(比如锁表或者缓冲池,我们在下文会研究这两个概念)。

    哈希表这种数据结构可以用关键字来快速找到一个元素。为了构建一个哈希表,你需要定义:

    • 元素的关键字
      • 关键字的哈希函数。关键字计算出来的哈希值给出了元素的位置(叫做哈希桶)。
      • 关键字比较函数。一旦你找到正确的哈希桶,你必须用比较函数在桶内找到你要的元素。

    一个简单的例子

    我们来看一个形象化的例子:

    这个哈希表有10个哈希桶。因为我懒,我只给出5个桶,但是我知道你很聪明,所以我让你想象其它的5个桶。我用的哈希函数是关键字对10取模,也就是我只保留元素关键字的最后一位,用来查找它的哈希桶:

    • 如果元素最后一位是 0,则进入哈希桶0,
    • 如果元素最后一位是 1,则进入哈希桶1,
    • 如果元素最后一位是 2,则进入哈希桶2,
    • …我用的比较函数只是判断两个整数是否相等。

    【译者注:取模运算

    比方说你要找元素 78:

    • 哈希表计算 78 的哈希码,等于 8。
    • 查找哈希桶 8,找到的第一个元素是 78。
    • 返回元素 78。
    • 查询仅耗费了 2 次运算(1次计算哈希值,另一次在哈希桶中查找元素)。

    现在,比方说你要找元素 59:

    • 哈希表计算 59 的哈希码,等于9。
    • 查找哈希桶 9,第一个找到的元素是 99。因为 99 不等于 59, 那么 99 不是正确的元素。
    • 用同样的逻辑,查找第二个元素(9),第三个(79),……,最后一个(29)。
    • 元素不存在。
    • 搜索耗费了 7 次运算

    一个好的哈希函数

    你可以看到,根据你查找的值,成本并不相同。

    如果我把哈希函数改为关键字对 1,000,000 取模(就是说取后6位数字),第二次搜索只消耗一次运算,因为哈希桶 00059 里面没有元素。真正的挑战是找到好的哈希函数,让哈希桶里包含非常少的元素

    在我的例子里,找到一个好的哈希函数很容易,但这是个简单的例子。当关键字是下列形式时,好的哈希函数就更难找了:

    • 1 个字符串(比如一个人的姓)
    • 2 个字符串(比如一个人的姓和名)
    • 2 个字符串和一个日期(比如一个人的姓、名和出生年月日)

    如果有了好的哈希函数,在哈希表里搜索的时间复杂度是 O(1)。

    阵列 vs 哈希表

    为什么不用阵列呢?

    嗯,你问得好。

    • 一个哈希表可以只装载一半到内存,剩下的哈希桶可以留在硬盘上。
    • 用阵列的话,你需要一个连续内存空间。如果你加载一个大表,很难分配足够的连续内存空间
    • 用哈希表的话,你可以选择你要的关键字(比如,一个人的国家和姓氏)。

    想要更详细的信息,你可以阅读我在Java HashMap 上的文章,是关于高效哈希表实现的。你不需要了解Java就能理解文章里的概念。

    全局概览

    我们已经了解了数据库内部的基本组件,现在我们需要回来看看数据库的全貌了。

    数据库是一个易于访问和修改的信息集合。不过简单的一堆文件也能达到这个效果。事实上,像SQLite这样最简单的数据库也只是一堆文件而已,但SQLite是精心设计的一堆文件,因为它允许你:

    • 使用事务来确保数据的安全和一致性
    • 快速处理百万条以上的数据

    数据库一般可以用如下图形来理解:

    撰写这部分之前,我读过很多书/论文,它们都以自己的方式描述数据库。所以,我不会特别关注如何组织数据库或者如何命名各种进程,因为我选择了自己的方式来描述这些概念以适应本文。区别就是不同的组件,总体思路为:数据库是由多种互相交互的组件构成的

    核心组件:

    • 进程管理器(process manager:很多数据库具备一个需要妥善管理的进程/线程池。再者,为了实现纳秒级操作,一些现代数据库使用自己的线程而不是操作系统线程。
    • 网络管理器(network manager:网路I/O是个大问题,尤其是对于分布式数据库。所以一些数据库具备自己的网络管理器。
    • 文件系统管理器(File system manager磁盘I/O是数据库的首要瓶颈。具备一个文件系统管理器来完美地处理OS文件系统甚至取代OS文件系统,是非常重要的。
    • 内存管理器(memory manager:为了避免磁盘I/O带来的性能损失,需要大量的内存。但是如果你要处理大容量内存你需要高效的内存管理器,尤其是你有很多查询同时使用内存的时候。
    • 安全管理器(Security Manager:用于对用户的验证和授权。
    • 客户端管理器(Client manager:用于管理客户端连接。
    • ……

    工具:

    • 备份管理器(Backup manager:用于保存和恢复数据。
    • 复原管理器(Recovery manager:用于崩溃后重启数据库到一个一致状态
    • 监控管理器(Monitor manager:用于记录数据库活动信息和提供监控数据库的工具。
    • Administration管理器(Administration manager:用于保存元数据(比如表的名称和结构),提供管理数据库、模式、表空间的工具。【译者注:好吧,我真的不知道Administration manager该翻译成什么,有知道的麻烦告知,不胜感激……】
    • ……

    查询管理器:

    • 查询解析器(Query parser):用于检查查询是否合法
    • 查询重写器(Query rewriter):用于预优化查询
    • 查询优化器(Query optimizer):用于优化查询
    • 查询执行器(Query executor):用于编译和执行查询

    数据管理器:

    • 事务管理器(Transaction manager:用于处理事务
    • 缓存管理器Cache manager:数据被使用之前置于内存,或者数据写入磁盘之前置于内存
    • 数据访问管理器Data access manager:访问磁盘中的数据

    在本文剩余部分,我会集中探讨数据库如何通过如下进程管理SQL查询的:

    • 客户端管理器
    • 查询管理器
    • 数据管理器(含复原管理器)

    客户端管理器

    客户端管理器是处理客户端通信的。客户端可以是一个(网站)服务器或者一个最终用户或最终应用。客户端管理器通过一系列知名的API(JDBC, ODBC, OLE-DB …)提供不同的方式来访问数据库。

    客户端管理器也提供专有的数据库访问API。

    当你连接到数据库时:

    • 管理器首先检查你的验证信息(用户名和密码),然后检查你是否有访问数据库的授权。这些权限由DBA分配。
    • 然后,管理器检查是否有空闲进程(或线程)来处理你对查询。
    • 管理器还会检查数据库是否负载很重。
    • 管理器可能会等待一会儿来获取需要的资源。如果等待时间达到超时时间,它会关闭连接并给出一个可读的错误信息。
    • 然后管理器会把你的查询送给查询管理器来处理。
    • 因为查询处理进程不是『不全则无』的,一旦它从查询管理器得到数据,它会把部分结果保存到一个缓冲区并且开始给你发送
    • 如果遇到问题,管理器关闭连接,向你发送可读的解释信息,然后释放资源。

    查询管理器

    这部分是数据库的威力所在,在这部分里,一个写得糟糕的查询可以转换成一个快速执行的代码,代码执行的结果被送到客户端管理器。这个多步骤操作过程如下:

    • 查询首先被解析并判断是否合法
    • 然后被重写,去除了无用的操作并且加入预优化部分
    • 接着被优化以便提升性能,并被转换为可执行代码和数据访问计划。
    • 然后计划被编译
    • 最后,被执行

    这里我不会过多探讨最后两步,因为它们不太重要。

    看完这部分后,如果你需要更深入的知识,我建议你阅读:

    • 关于成本优化的初步研究论文(1979):关系型数据库系统存取路径选择。这个篇文章只有12页,而且具备计算机一般水平就能理解。
    • 非常好、非常深入的 DB2 9.X 如何优化查询的介绍
    • 非常好的PostgreSQL如何优化查询的介绍。这是一篇最通俗易懂的文档,因为它讲的是『我们来看看在这种情况下,PostgreSQL给出了什么样的查询计划』,而不是『我们来看看PostgreSQL用的什么算法』。
    • 官方SQLite优化文档。『易于』阅读,因为SQLite用的是简单规则。再者,这是唯一真正解释SQLite如何工作的官方文档。
    • 非常好的SQL Server 2005 如何优化查询的介绍
    • Oracle 12c 优化白皮书
    • 2篇查询优化的教程,第一篇 第二篇。教程来自《数据库系统概念》的作者,很好的读物,集中讨论磁盘I/O,但是要求具有很好的计算机科学水平。
    • 另一个原理教程,这篇教程我觉得更易懂,不过它仅关注联接运算符(join operators)和磁盘I/O。

    查询解析器

    每一条SQL语句都要送到解析器来检查语法,如果你的查询有错,解析器将拒绝该查询。比如,如果你写成”SLECT …” 而不是 “SELECT …”,那就没有下文了。

    但这还不算完,解析器还会检查关键字是否使用正确的顺序,比如 WHERE 写在 SELECT 之前会被拒绝。

    然后,解析器要分析查询中的表和字段,使用数据库元数据来检查:

    • 表是否存在
    • 表的字段是否存在
    • 对某类型字段的 运算 是否 可能(比如,你不能将整数和字符串进行比较,你不能对一个整数使用 substring() 函数)

    接着,解析器检查在查询中你是否有权限来读取(或写入)表。再强调一次:这些权限由DBA分配。

    在解析过程中,SQL 查询被转换为内部表示(通常是一个树)。

    如果一切正常,内部表示被送到查询重写器。

    查询重写器

    在这一步,我们已经有了查询的内部表示,重写器的目标是:

    • 预优化查询
    • 避免不必要的运算
    • 帮助优化器找到合理的最佳解决方案

    重写器按照一系列已知的规则对查询执行检测。如果查询匹配一种模式的规则,查询就会按照这条规则来重写。下面是(可选)规则的非详尽的列表:

    • 视图合并:如果你在查询中使用视图,视图就会转换为它的 SQL 代码。
    • 子查询扁平化:子查询是很难优化的,因此重写器会尝试移除子查询

    例如:

    MySQL

    SELECT PERSON.* FROM PERSON WHERE PERSON.person_key IN (SELECT MAILS.person_key FROM MAILS WHERE MAILS.mail LIKE 'christophe%');

    1

    2

    3

    4

    5

    6

    SELECT PERSON.*

    FROM PERSON

    WHERE PERSON.person_key IN

    (SELECT MAILS.person_key

    FROM MAILS

    WHERE MAILS.mail LIKE 'christophe%');

    会转换为:

    MySQL

    SELECT PERSON.* FROM PERSON, MAILS WHERE PERSON.person_key = MAILS.person_key and MAILS.mail LIKE 'christophe%';

    1

    2

    3

    4

    SELECT PERSON.*

    FROM PERSON, MAILS

    WHERE PERSON.person_key = MAILS.person_key

    and MAILS.mail LIKE 'christophe%';

     

    • 去除不必要的运算符:比如,如果你用了 DISTINCT,而其实你有 UNIQUE 约束(这本身就防止了数据出现重复),那么 DISTINCT 关键字就被去掉了。
    • 排除冗余的联接:如果相同的 JOIN 条件出现两次,比如隐藏在视图中的 JOIN 条件,或者由于传递性产生的无用 JOIN,都会被消除。
    • 常数计算赋值:如果你的查询需要计算,那么在重写过程中计算会执行一次。比如 WHERE AGE > 10+2 会转换为 WHERE AGE > 12 , TODATE(“日期字符串”) 会转换为 datetime 格式的日期值。
    • (高级)分区裁剪(Partition Pruning):如果你用了分区表,重写器能够找到需要使用的分区。
    • (高级)物化视图重写(Materialized view rewrite):如果你有个物化视图匹配查询谓词的一个子集,重写器将检查视图是否最新并修改查询,令查询使用物化视图而不是原始表。
    • (高级)自定义规则:如果你有自定义规则来修改查询(就像 Oracle policy),重写器就会执行这些规则。
    • (高级)OLAP转换:分析/加窗 函数,星形联接,ROLLUP 函数……都会发生转换(但我不确定这是由重写器还是优化器来完成,因为两个进程联系很紧,必须看是什么数据库)。

    【译者注: 物化视图  。谓词,predicate,条件表达式的求值返回真或假的过程】

    重写后的查询接着送到优化器,这时候好玩的就开始了。

    统计

    研究数据库如何优化查询之前我们需要谈谈统计,因为没有统计的数据库是愚蠢的。除非你明确指示,数据库是不会分析自己的数据的。没有分析会导致数据库做出(非常)糟糕的假设。

    但是,数据库需要什么类型的信息呢?

    我必须(简要地)谈谈数据库和操作系统如何保存数据。两者使用的最小单位叫做页或块(默认 4 或 8 KB)。这就是说如果你仅需要 1KB,也会占用一个页。要是页的大小为 8KB,你就浪费了 7KB。

    回来继续讲统计! 当你要求数据库收集统计信息,数据库会计算下列值:

    • 表中行和页的数量
    • 表中每个列中的:
      唯一值
      数据长度(最小,最大,平均)
      数据范围(最小,最大,平均)
    • 表的索引信息

    这些统计信息会帮助优化器估计查询所需的磁盘 I/O、CPU、和内存使用

    对每个列的统计非常重要。
    比如,如果一个表 PERSON 需要联接 2 个列: LAST_NAME, FIRST_NAME。
    根据统计信息,数据库知道FIRST_NAME只有 1,000 个不同的值,LAST_NAME 有 1,000,000 个不同的值。
    因此,数据库就会按照 LAST_NAME, FIRST_NAME 联接。
    因为 LAST_NAME 不大可能重复,多数情况下比较 LAST_NAME 的头 2 、 3 个字符就够了,这将大大减少比较的次数。

    不过,这些只是基本的统计。你可以让数据库做一种高级统计,叫直方图。直方图是列值分布情况的统计信息。例如:

    • 出现最频繁的值
    • 分位数 【译者注:http://baike.baidu.com/view/1323572.htm】

    这些额外的统计会帮助数据库找到更佳的查询计划,尤其是对于等式谓词(例如: WHERE AGE = 18 )或范围谓词(例如: WHERE AGE > 10 and AGE < 40),因为数据库可以更好的了解这些谓词相关的数字类型数据行(注:这个概念的技术名称叫选择率)。

    统计信息保存在数据库元数据内,例如(非分区)表的统计信息位置:

    • Oracle: USER / ALL / DBA_TABLES 和 USER / ALL / DBA_TAB_COLUMNS
    • DB2: SYSCAT.TABLES 和 SYSCAT.COLUMNS

    统计信息必须及时更新。如果一个表有 1,000,000 行而数据库认为它只有 500 行,没有比这更糟糕的了。统计唯一的不利之处是需要时间来计算,这就是为什么数据库大多默认情况下不会自动计算统计信息。数据达到百万级时统计会变得困难,这时候,你可以选择仅做基本统计或者在一个数据库样本上执行统计。

    举个例子,我参与的一个项目需要处理每表上亿条数据的库,我选择只统计10%,结果造成了巨大的时间消耗。本例证明这是个糟糕的决定,因为有时候 Oracle 10G 从特定表的特定列中选出的 10% 跟全部 100% 有很大不同(对于拥有一亿行数据的表,这种情况极少发生)。这次错误的统计导致了一个本应 30 秒完成的查询最后执行了 8 个小时,查找这个现象根源的过程简直是个噩梦。这个例子显示了统计的重要性。

    注:当然了,每个数据库还有其特定的更高级的统计。如果你想了解更多信息,读读数据库的文档。话虽然这么说,我已经尽力理解统计是如何使用的了,而且我找到的最好的官方文档来自PostgreSQL

    查询优化器

    所有的现代数据库都在用基于成本的优化(即CBO)来优化查询。道理是针对每个运算设置一个成本,通过应用成本最低廉的一系列运算,来找到最佳的降低查询成本的方法。

    为了理解成本优化器的原理,我觉得最好用个例子来『感受』一下这个任务背后的复杂性。这里我将给出联接 2 个表的 3 个方法,我们很快就能看到即便一个简单的联接查询对于优化器来说都是个噩梦。之后,我们会了解真正的优化器是怎么做的。

    对于这些联接操作,我会专注于它们的时间复杂度,但是,数据库优化器计算的是它们的 CPU 成本、磁盘 I/O 成本、和内存需求。时间复杂度和 CPU 成本的区别是,时间成本是个近似值(给我这样的懒家伙准备的)。而 CPU 成本,我这里包括了所有的运算,比如:加法、条件判断、乘法、迭代……还有呢:

    • 每一个高级代码运算都要特定数量的低级 CPU 运算。
    • 对于 Intel Core i7、Intel Pentium 4、AMD Opteron…等,(就 CPU 周期而言)CPU 的运算成本是不同的,也就是说它取决于 CPU 的架构。

    使用时间复杂度就容易多了(至少对我来说),用它我也能了解到 CBO 的概念。由于磁盘 I/O 是个重要的概念,我偶尔也会提到它。请牢记,大多数时候瓶颈在于磁盘 I/O 而不是 CPU 使用

    索引

    在研究 B+树的时候我们谈到了索引,要记住一点,索引都是已经排了序的

    仅供参考:还有其他类型的索引,比如位图索引,在 CPU、磁盘I/O、和内存方面与B+树索引的成本并不相同。

    另外,很多现代数据库为了改善执行计划的成本,可以仅为当前查询动态地生成临时索引

    存取路径

    在应用联接运算符(join operators)之前,你首先需要获得数据。以下就是获得数据的方法。

    注:由于所有存取路径的真正问题是磁盘 I/O,我不会过多探讨时间复杂度。

    【译者注:四种类型的Oracle索引扫描介绍  】

    全扫描

    如果你读过执行计划,一定看到过『全扫描』(或只是『扫描』)一词。简单的说全扫描就是数据库完整的读一个表或索引。就磁盘 I/O 而言,很明显全表扫描的成本比索引全扫描要高昂

    范围扫描

    其他类型的扫描有索引范围扫描,比如当你使用谓词 ” WHERE AGE > 20 AND AGE < 40 ” 的时候它就会发生。

    当然,你需要在 AGE 字段上有索引才能用到索引范围扫描。

    在第一部分我们已经知道,范围查询的时间成本大约是 log(N)+M,这里 N 是索引的数据量,M 是范围内估测的行数。多亏有了统计我们才能知道 N 和 M 的值(注: M 是谓词 “ AGE > 20 AND AGE < 40 ” 的选择率)。另外范围扫描时,你不需要读取整个索引,因此在磁盘 I/O 方面没有全扫描那么昂贵

    唯一扫描

    如果你只需要从索引中取一个值你可以用唯一扫描

    根据 ROW ID 存取

    多数情况下,如果数据库使用索引,它就必须查找与索引相关的行,这样就会用到根据 ROW ID 存取的方式。

    例如,假如你运行:

    MySQL

    SELECT LASTNAME, FIRSTNAME from PERSON WHERE AGE = 28

    1

    SELECT LASTNAME, FIRSTNAME from PERSON WHERE AGE = 28

    如果 person 表的 age 列有索引,优化器会使用索引找到所有年龄为 28 的人,然后它会去表中读取相关的行,这是因为索引中只有 age 的信息而你要的是姓和名。

    但是,假如你换个做法:

    MySQL

    SELECT TYPE_PERSON.CATEGORY from PERSON ,TYPE_PERSON WHERE PERSON.AGE = TYPE_PERSON.AGE

    1

    2

    SELECT TYPE_PERSON.CATEGORY from PERSON ,TYPE_PERSON

    WHERE PERSON.AGE = TYPE_PERSON.AGE

    PERSON 表的索引会用来联接 TYPE_PERSON 表,但是 PERSON 表不会根据行ID 存取,因为你并没有要求这个表内的信息。

    虽然这个方法在少量存取时表现很好,这个运算的真正问题其实是磁盘 I/O。假如需要大量的根据行ID存取,数据库也许会选择全扫描。

    其它路径

    我没有列举所有的存取路径,如果你感兴趣可以读一读 Oracle文档。其它数据库里也许叫法不同但背后的概念是一样的。

    联接运算符

    那么,我们知道如何获取数据了,那现在就把它们联接起来!

    我要展现的是3个个常用联接运算符:合并联接(Merge join),哈希联接(Hash Join)和嵌套循环联接(Nested Loop Join)。但是在此之前,我需要引入新词汇了:内关系和外关系( inner relation and outer relation) 【译者注: “内关系和外关系” 这个说法来源不明,跟查询的“内联接(INNER JOIN)  、外联接(OUTER JOIN)  ” 不是一个概念 。只查到百度百科词条:关系数据库 里提到“每个表格(有时被称为一个关系)……” 。 其他参考链接 “Merge Join”   “Hash Join”   “Nested Loop Join” 】  。 一个关系可以是:

    • 一个表
    • 一个索引
    • 上一个运算的中间结果(比如上一个联接运算的结果)

    当你联接两个关系时,联接算法对两个关系的处理是不同的。在本文剩余部分,我将假定:

    • 外关系是左侧数据集
    • 内关系是右侧数据集

    比如, A JOIN B 是 A 和 B 的联接,这里 A 是外关系,B 是内关系。

    多数情况下, A JOIN B 的成本跟 B JOIN A 的成本是不同的

    在这一部分,我还将假定外关系有 N 个元素,内关系有 M 个元素。要记住,真实的优化器通过统计知道 N 和 M 的值。

    注:N 和 M 是关系的基数。【译者注: 基数 】

    嵌套循环联接

    嵌套循环联接是最简单的。

    道理如下:

    • 针对外关系的每一行
    • 查看内关系里的所有行来寻找匹配的行

    下面是伪代码:

    C

    nested_loop_join(array outer, array inner) for each row a in outer for each row b in inner if (match_join_condition(a,b)) write_result_in_output(a,b) end if end for end for

    1

    2

    3

    4

    5

    6

    7

    8

    nested_loop_join(array outer, array inner)

      for each row a in outer

        for each row b in inner

          if (match_join_condition(a,b))

            write_result_in_output(a,b)

          end if

        end for

       end for

    由于这是个双迭代,时间复杂度是 O(N*M)。

    在磁盘 I/O 方面, 针对 N 行外关系的每一行,内部循环需要从内关系读取 M 行。这个算法需要从磁盘读取 N+ N*M 行。但是,如果内关系足够小,你可以把它读入内存,那么就只剩下 M + N 次读取。这样修改之后,内关系必须是最小的,因为它有更大机会装入内存。

    在CPU成本方面没有什么区别,但是在磁盘 I/O 方面,最好最好的,是每个关系只读取一次。

    当然,内关系可以由索引代替,对磁盘 I/O 更有利。

    由于这个算法非常简单,下面这个版本在内关系太大无法装入内存时,对磁盘 I/O 更加有利。道理如下:

    • 为了避免逐行读取两个关系,
    • 你可以成簇读取,把(两个关系里读到的)两簇数据行保存在内存里,
    • 比较两簇数据,保留匹配的,
    • 然后从磁盘加载新的数据簇来继续比较
    • 直到加载了所有数据。

    可能的算法如下:

    C

    // improved version to reduce the disk I/O. nested_loop_join_v2(file outer, file inner) for each bunch ba in outer // ba is now in memory for each bunch bb in inner // bb is now in memory for each row a in ba for each row b in bb if (match_join_condition(a,b)) write_result_in_output(a,b) end if end for end for end for end for

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    // improved version to reduce the disk I/O.

    nested_loop_join_v2(file outer, file inner)

      for each bunch ba in outer

      // ba is now in memory

        for each bunch bb in inner

            // bb is now in memory

            for each row a in ba

              for each row b in bb

                if (match_join_condition(a,b))

                  write_result_in_output(a,b)

                end if

              end for

           end for

        end for

       end for

    使用这个版本,时间复杂度没有变化,但是磁盘访问降低了:

    • 用前一个版本,算法需要 N + N*M 次访问(每次访问读取一行)。
    • 用新版本,磁盘访问变为 外关系的数据簇数量 + 外关系的数据簇数量 * 内关系的数据簇数量
    • 增加数据簇的尺寸,可以降低磁盘访问。

    哈希联接

    哈希联接更复杂,不过在很多场合比嵌套循环联接成本低。

    哈希联接的道理是:

    • 1) 读取内关系的所有元素
    • 2) 在内存里建一个哈希表
    • 3) 逐条读取外关系的所有元素
    • 4) (用哈希表的哈希函数)计算每个元素的哈希值,来查找内关系里相关的哈希桶内
    • 5) 是否与外关系的元素匹配。

    在时间复杂度方面我需要做些假设来简化问题:

    • 内关系被划分成 X 个哈希桶
    • 哈希函数几乎均匀地分布每个关系内数据的哈希值,就是说哈希桶大小一致。
    • 外关系的元素与哈希桶内的所有元素的匹配,成本是哈希桶内元素的数量。

    时间复杂度是 (M/X) * N + 创建哈希表的成本(M) + 哈希函数的成本 * N 。
    如果哈希函数创建了足够小规模的哈希桶,那么复杂度就是 O(M+N)

    还有个哈希联接的版本,对内存有利但是对磁盘 I/O 不够有利。 这回是这样的:

    • 1) 计算内关系和外关系双方的哈希表
    • 2) 保存哈希表到磁盘
    • 3) 然后逐个哈希桶比较(其中一个读入内存,另一个逐行读取)。

    合并联接

    合并联接是唯一产生排序的联接算法。

    注:这个简化的合并联接不区分内表或外表;两个表扮演同样的角色。但是真实的实现方式是不同的,比如当处理重复值时。

    1.(可选)排序联接运算:两个输入源都按照联接关键字排序。

    2.合并联接运算:排序后的输入源合并到一起。

    排序

    我们已经谈到过合并排序,在这里合并排序是个很好的算法(但是并非最好的,如果内存足够用的话,还是哈希联接更好)。

    然而有时数据集已经排序了,比如:

    • 如果表内部就是有序的,比如联接条件里一个索引组织表 【译者注: index-organized table 】
    • 如果关系是联接条件里的一个索引
    • 如果联接应用在一个查询中已经排序的中间结果

    合并联接

    这部分与我们研究过的合并排序中的合并运算非常相似。不过这一次呢,我们不是从两个关系里挑选所有元素,而是只挑选相同的元素。道理如下:

    • 1) 在两个关系中,比较当前元素(当前=头一次出现的第一个)
    • 2) 如果相同,就把两个元素都放入结果,再比较两个关系里的下一个元素
    • 3) 如果不同,就去带有最小元素的关系里找下一个元素(因为下一个元素可能会匹配)
    • 4) 重复 1、2、3步骤直到其中一个关系的最后一个元素。

    因为两个关系都是已排序的,你不需要『回头去找』,所以这个方法是有效的。

    该算法是个简化版,因为它没有处理两个序列中相同数据出现多次的情况(即多重匹配)。真实版本『仅仅』针对本例就更加复杂,所以我才选择简化版。

    如果两个关系都已经排序,时间复杂度是 O(N+M)

    如果两个关系需要排序,时间复杂度是对两个关系排序的成本:O(N*Log(N) + M*Log(M))

    对于计算机极客,我给出下面这个可能的算法来处理多重匹配(注:对于这个算法我不保证100%正确):

    C

    mergeJoin(relation a, relation b) relation output integer a_key:=0; integer b_key:=0; while (a[a_key]!=null and b[b_key]!=null) if (a[a_key] < b[b_key]) a_key++; else if (a[a_key] > b[b_key]) b_key++; else //Join predicate satisfied write_result_in_output(a[a_key],b[b_key]) //We need to be careful when we increase the pointers if (a[a_key+1] != b[b_key]) b_key++; end if if (b[b_key+1] != a[a_key]) a_key++; end if if (b[b_key+1] == a[a_key] && b[b_key] == a[a_key+1]) b_key++; a_key++; end if end if end while

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    18

    19

    20

    21

    22

    23

    24

    25

    mergeJoin(relation a, relation b)

      relation output

      integer a_key:=0;

      integer  b_key:=0;

     

      while (a[a_key]!=null and b[b_key]!=null)

         if (a[a_key] < b[b_key])

          a_key++;

         else if (a[a_key] > b[b_key])

          b_key++;

         else //Join predicate satisfied

          write_result_in_output(a[a_key],b[b_key])

          //We need to be careful when we increase the pointers

          if (a[a_key+1] != b[b_key])

            b_key++;

          end if

          if (b[b_key+1] != a[a_key])

            a_key++;

          end if

          if (b[b_key+1] == a[a_key] && b[b_key] == a[a_key+1])

            b_key++;

            a_key++;

          end if

        end if

      end while

     

    哪个算法最好?

    如果有最好的,就没必要弄那么多种类型了。这个问题很难,因为很多因素都要考虑,比如:

    • 空闲内存:没有足够的内存的话就跟强大的哈希联接拜拜吧(至少是完全内存中哈希联接)。
    • 两个数据集的大小。比如,如果一个大表联接一个很小的表,那么嵌套循环联接就比哈希联接快,因为后者有创建哈希的高昂成本;如果两个表都非常大,那么嵌套循环联接CPU成本就很高昂。
    • 是否有索引:有两个 B+树索引的话,聪明的选择似乎是合并联接。
    • 结果是否需要排序:即使你用到的是未排序的数据集,你也可能想用成本较高的合并联接(带排序的),因为最终得到排序的结果后,你可以把它和另一个合并联接串起来(或者也许因为查询用 ORDER BY/GROUP BY/DISTINCT 等操作符隐式或显式地要求一个排序结果)。
    • 关系是否已经排序:这时候合并联接是最好的候选项。
    • 联接的类型:是等值联接(比如 tableA.col1 = tableB.col2 )? 还是内联接外联接笛卡尔乘积?或者自联接?有些联接在特定环境下是无法工作的。
    • 数据的分布:如果联接条件的数据是倾斜的(比如根据姓氏来联接人,但是很多人同姓),用哈希联接将是个灾难,原因是哈希函数将产生分布极不均匀的哈希桶。
    • 如果你希望联接操作使用多线程或多进程

    想要更详细的信息,可以阅读DB2ORACLE 或 SQL Server)的文档。

    简化的例子

    我们已经研究了 3 种类型的联接操作。

    现在,比如说我们要联接 5 个表,来获得一个人的全部信息。一个人可以有:

    • 多个手机号(MOBILES)
    • 多个邮箱(MAILS)
    • 多个地址(ADRESSES)
    • 多个银行账号(BANK_ACCOUNTS)

    换句话说,我们需要用下面的查询快速得到答案:

    MySQL

    SELECT * from PERSON, MOBILES, MAILS,ADRESSES, BANK_ACCOUNTS WHERE PERSON.PERSON_ID = MOBILES.PERSON_ID AND PERSON.PERSON_ID = MAILS.PERSON_ID AND PERSON.PERSON_ID = ADRESSES.PERSON_ID AND PERSON.PERSON_ID = BANK_ACCOUNTS.PERSON_ID

    1

    2

    3

    4

    5

    6

    SELECT * from PERSON, MOBILES, MAILS,ADRESSES, BANK_ACCOUNTS

    WHERE

    PERSON.PERSON_ID = MOBILES.PERSON_ID

    AND PERSON.PERSON_ID = MAILS.PERSON_ID

    AND PERSON.PERSON_ID = ADRESSES.PERSON_ID

    AND PERSON.PERSON_ID = BANK_ACCOUNTS.PERSON_ID

    作为一个查询优化器,我必须找到处理数据最好的方法。但有 2 个问题:

    • 每个联接使用那种类型?
      我有 3 种可选(哈希、合并、嵌套),同时可能用到 0, 1 或 2 个索引(不必说还有多种类型的索引)。
    • 按什么顺序执行联接?
      比如,下图显示了针对 4 个表仅仅 3 次联接,可能采用的执行计划:

    那么下面就是我可能采取的方法:

    • 1) 采取粗暴的方式
      用数据库统计,计算每种可能的执行计划的成本,保留最佳方案。但是,会有很多可能性。对于一个给定顺序的联接操作,每个联接有三种可能性:哈希、合并、嵌套,那么总共就有 3^4 种可能性。确定联接的顺序是个二叉树的排列问题,会有 (2*4)!/(4+1)! 种可能的顺序。对本例这个相当简化了的问题,我最后会得到 3^4*(2*4)!/(4+1)! 种可能。
      抛开专业术语,那相当于 27,216 种可能性。如果给合并联接加上使用 0,1 或 2 个 B+树索引,可能性就变成了 210,000种。我是不是告诉过你这个查询其实非常简单吗?
    • 2) 我大叫一声辞了这份工作
      很有诱惑力,但是这样一来,你不会的到查询结果,而我需要钱来付账单。
    • 3) 我只尝试几种执行计划,挑一个成本最低的。
      由于不是超人,我不能算出所有计划的成本。相反,我可以武断地从全部可能的计划中选择一个子集,计算它们的成本,把最佳的计划给你。
    • 4) 我用聪明的规则来降低可能性的数量
      有两种规则:
      我可以用『逻辑』规则,它能去除无用的可能性,但是无法过滤大量的可能性。比如: 『嵌套联接的内关系必须是最小的数据集』。
      我接受现实,不去找最佳方案,用更激进的规则来大大降低可能性的数量。比如:『如果一个关系很小,使用嵌套循环联接,绝不使用合并或哈希联接。』

    在这个简单的例子中,我最后得到很多可能性。但现实世界的查询还会有其他关系运算符,像 OUTER JOIN, CROSS JOIN, GROUP BY, ORDER BY, PROJECTION, UNION, INTERSECT, DISTINCT … 这意味着更多的可能性。

    那么,数据库是如何处理的呢?

    动态规划,贪婪算法和启发式算法

    关系型数据库会尝试我刚刚提到的多种方法,优化器真正的工作是在有限时间里找到一个好的解决方案。

    多数时候,优化器找到的不是最佳的方案,而是一个『不错』的

    对于小规模的查询,采取粗暴的方式是有可能的。但是为了让中等规模的查询也能采取粗暴的方式,我们有办法避免不必要的计算,这就是动态规划

    动态规划

    这几个字背后的理念是,很多执行计划是非常相似的。看看下图这几种计划:

    它们都有相同的子树(A JOIN B),所以,不必在每个计划中计算这个子树的成本,计算一次,保存结果,当再遇到这个子树时重用。用更正规的说法,我们面对的是个重叠问题。为了避免对部分结果的重复计算,我们使用记忆法。

    应用这一技术,我们不再有 (2*N)!/(N+1)! 的复杂度,而是“只有” 3^N。在之前 4 个JOIN 的例子里,这意味着将 336 次排序降为 81 次。如果是大一些的查询,比如 8 个 JOIN (其实也不是很大啦),就是将 57,657,600 次降为 6551 次。【译者注:这一小段漏掉了,感谢 nsos指出来。另外感谢 Clark Li 指出Dynamic Programing 应该翻译为动态规划。 】

    对于计算机极客,下面是我在先前给你的教程里找到的一个算法。我不提供解释,所以仅在你已经了解动态规划或者精通算法的情况下阅读(我提醒过你哦):

    C

    procedure findbestplan(S) if (bestplan[S].cost infinite) return bestplan[S] // else bestplan[S] has not been computed earlier, compute it now if (S contains only 1 relation) set bestplan[S].plan and bestplan[S].cost based on the best way of accessing S /* Using selections on S and indices on S */ else for each non-empty subset S1 of S such that S1 != S P1= findbestplan(S1) P2= findbestplan(S - S1) A = best algorithm for joining results of P1 and P2 cost = P1.cost + P2.cost + cost of A if cost < bestplan[S].cost bestplan[S].cost = cost bestplan[S].plan = 『execute P1.plan; execute P2.plan; join results of P1 and P2 using A』 return bestplan[S]

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    procedure findbestplan(S)

    if (bestplan[S].cost infinite)

       return bestplan[S]

    // else bestplan[S] has not been computed earlier, compute it now

    if (S contains only 1 relation)

             set bestplan[S].plan and bestplan[S].cost based on the best way

             of accessing S  /* Using selections on S and indices on S */

         else for each non-empty subset S1 of S such that S1 != S

       P1= findbestplan(S1)

       P2= findbestplan(S - S1)

       A = best algorithm for joining results of P1 and P2

       cost = P1.cost + P2.cost + cost of A

       if cost < bestplan[S].cost

           bestplan[S].cost = cost

          bestplan[S].plan = 『execute P1.plan; execute P2.plan;

                     join results of P1 and P2 using A』

    return bestplan[S]

    针对大规模查询,你也可以用动态规划方法,但是要附加额外的规则(或者称为启发式算法)来减少可能性。

    • 如果我们仅分析一个特定类型的计划(例如左深树 left-deep tree,参考),我们得到 n*2^n 而不是 3^n。

    • 如果我们加上逻辑规则来避免一些模式的计划(像『如果一个表有针对指定谓词的索引,就不要对表尝试合并联接,要对索引』),就会在不给最佳方案造成过多伤害的前提下,减少可能性的数量。【译者注:原文应该是有两处笔误: as=has, to=too】
    • 如果我们在流程里增加规则(像『联接运算先于其他所有的关系运算』),也能减少大量的可能性。
    • ……

    贪婪算法

    但是,优化器面对一个非常大的查询,或者为了尽快找到答案(然而查询速度就快不起来了),会应用另一种算法,叫贪婪算法。

    原理是按照一个规则(或启发)以渐进的方式制定查询计划。在这个规则下,贪婪算法逐步寻找最佳算法,先处理一条JOIN,接着每一步按照同样规则加一条新的JOIN。

    我们来看个简单的例子。比如一个针对5张表(A,B,C,D,E)4次JOIN 的查询,为了简化我们把嵌套JOIN作为可能的联接方式,按照『使用最低成本的联接』规则。

    • 直接从 5 个表里选一个开始(比如 A)
    • 计算每一个与 A 的联接(A 作为内关系或外关系)
    • 发现 “A JOIN B” 成本最低
    • 计算每一个与 “A JOIN B” 的结果联接的成本(“A JOIN B” 作为内关系或外关系)
    • 发现 “(A JOIN B) JOIN C” 成本最低
    • 计算每一个与 “(A JOIN B) JOIN C” 的结果联接的成本 ……
    • 最后确定执行计划 “( ( (A JOIN B) JOIN C) JOIN D ) JOIN E )”

    因为我们是武断地从表 A 开始,我们可以把同样的算法用在 B,然后 C,然后 D, 然后 E。最后保留成本最低的执行计划。

    顺便说一句,这个算法有个名字,叫『最近邻居算法』。

    抛开细节不谈,只需一个良好的模型和一个 N*log(N) 复杂度的排序,问题就轻松解决了。这个算法的复杂度是 O(N*log(N)) ,对比一下完全动态规划的 O(3^N)。如果你有个20个联接的大型查询,这意味着 26 vs 3,486,784,401 ,天壤之别!

    这个算法的问题是,我们做的假设是:找到 2 个表的最佳联接方法,保留这个联接结果,再联接下一个表,就能得到最低的成本。但是:

    • 即使在 A, B, C 之间,A JOIN B 可得最低成本
    • (A JOIN C) JOIN B 也许比 (A JOIN B) JOIN C 更好。

    为了改善这一状况,你可以多次使用基于不同规则的贪婪算法,并保留最佳的执行计划。

    其他算法

    [ 如果你已经受够了算法话题,就直接跳到下一部分。这部分对文章余下的内容不重要。] 【译者注:我也很想把这段跳过去 -_- 】

    很多计算机科学研究者热衷于寻找最佳的执行计划,他们经常为特定问题或模式探寻更好的解决方案,比如:

    • 如果查询是星型联接(一种多联接查询),某些数据库使用一种特定的算法。
    • 如果查询是并行的,某些数据库使用一种特定的算法。 ……

    其他算法也在研究之中,就是为了替换在大型查询中的动态规划算法。贪婪算法属于一个叫做启发式算法的大家族,它根据一条规则(或启发),保存上一步找到的方法,『附加』到当前步骤来进一步搜寻解决方法。有些算法根据特定规则,一步步的应用规则但不总是保留上一步找到的最佳方法。它们统称启发式算法。

    比如,基因算法就是一种:

    • 一个方法代表一种可能的完整查询计划
    • 每一步保留了 P 个方法(即计划),而不是一个。
    • 0) P 个计划随机创建
    • 1) 成本最低的计划才会保留
    • 2) 这些最佳计划混合在一起产生 P 个新的计划
    • 3) 一些新的计划被随机改写
    • 4) 1,2,3步重复 T 次
    • 5) 然后在最后一次循环,从 P 个计划里得到最佳计划。

    循环次数越多,计划就越好。

    这是魔术?不,这是自然法则:适者生存!

    PostgreSQL 实现了基因算法,但我并没有发现它是不是默认使用这种算法的。

    数据库中还使用了其它启发式算法,像『模拟退火算法(Simulated Annealing)』、『交互式改良算法(Iterative Improvement)』、『双阶段优化算法(Two-Phase Optimization)』…..不过,我不知道这些算法当前是否在企业级数据库应用了,还是仅仅用在研究型数据库。

    如果想进一步了解,这篇研究文章介绍两个更多可能的算法《数据库查询优化中联接排序问题的算法综述》,你可以去阅读一下。

    真实的优化器

    [ 这段不重要,可以跳过 ]

    然而,所有上述罗里罗嗦的都非常理论化,我是个开发者而不是研究者,我喜欢具体的例子

    我们来看看 SQLite 优化器 是怎么工作的。这是个轻量化数据库,它使用一种简单优化器,基于带有附加规则的贪婪算法,来限制可能性的数量。

    • SQLite 在有 CROSS JOIN 操作符时从不给表重新排序
    • 使用嵌套联接
    • 外联接始终按顺序评估
    • ……
    • 3.8.0之前的版本使用『最近邻居』贪婪算法来搜寻最佳查询计划
      等等……我们见过这个算法!真是巧哈!
    • 从3.8.0版本(发布于2015年)开始,SQLite使用『N最近邻居』贪婪算法来搜寻最佳查询计划

    我们再看看另一个优化器是怎么工作的。IBM DB2 跟所有企业级数据库都类似,我讨论它是因为在切换到大数据之前,它是我最后真正使用的数据库。

    看过官方文档后,我们了解到 DB2 优化器可以让你使用 7 种级别的优化:

    • 对联接使用贪婪算法
    •     0 – 最小优化,使用索引扫描和嵌套循环联接,避免一些查询重写
      •     1 – 低级优化
      •     2 – 完全优化
    • 对联接使用动态规划算法
    •     3 – 中等优化和粗略的近似法
      •     5 – 完全优化,使用带有启发式的所有技术
      •     7 – 完全优化,类似级别5,但不用启发式
      •     9 – 最大优化,完全不顾开销,考虑所有可能的联接顺序,包括笛卡尔乘积

    可以看到 DB2 使用贪婪算法和动态规划算法。当然,他们不会把自己的启发算法分享出来的,因为查询优化器是数据库的看家本领。

    DB2 的默认级别是 5,优化器使用下列特性: 【译者注:以下出现的一些概念我没有做考证,因为[ 这段不重要,可以跳过 ]】

    • 使用所有可用的统计,包括线段树(frequent-value)和分位数统计(quantile statistics)。
    • 使用所有查询重写规则(含物化查询表路由,materialized query table routing),除了在极少情况下适用的计算密集型规则。
    • 使用动态规划模拟联接
    •     有限使用组合内关系(composite inner relation)
    •     对于涉及查找表的星型模式,有限使用笛卡尔乘积
    • 考虑宽泛的访问方式,含列表预取(list prefetch,注:我们将讨论什么是列表预取),index ANDing(注:一种对索引的特殊操作),和物化查询表路由。

    默认的,DB2 对联接排列使用受启发式限制的动态规划算法

    其它情况 (GROUP BY, DISTINCT…) 由简单规则处理。

    查询计划缓存

    由于创建查询计划是耗时的,大多数据库把计划保存在查询计划缓存,来避免重复计算。这个话题比较大,因为数据库需要知道什么时候更新过时的计划。办法是设置一个上限,如果一个表的统计变化超过了上限,关于该表的查询计划就从缓存中清除。

    查询执行器

    在这个阶段,我们有了一个优化的执行计划,再编译为可执行代码。然后,如果有足够资源(内存,CPU),查询执行器就会执行它。计划中的操作符 (JOIN, SORT BY …) 可以顺序或并行执行,这取决于执行器。为了获得和写入数据,查询执行器与数据管理器交互,本文下一部分来讨论数据管理器。

    数据管理器

    在这一步,查询管理器执行了查询,需要从表和索引获取数据,于是向数据管理器提出请求。但是有 2 个问题:

    • 关系型数据库使用事务模型,所以,当其他人在同一时刻使用或修改数据时,你无法得到这部分数据。
    • 数据提取是数据库中速度最慢的操作,所以数据管理器需要足够聪明地获得数据并保存在内存缓冲区内。

    在这一部分,我没看看关系型数据库是如何处理这两个问题的。我不会讲数据管理器是怎么获得数据的,因为这不是最重要的(而且本文已经够长的了!)。

    缓存管理器

    我已经说过,数据库的主要瓶颈是磁盘 I/O。为了提高性能,现代数据库使用缓存管理器。

    查询执行器不会直接从文件系统拿数据,而是向缓存管理器要。缓存管理器有一个内存缓存区,叫做缓冲池从内存读取数据显著地提升数据库性能。对此很难给出一个数量级,因为这取决于你需要的是哪种操作:

    • 顺序访问(比如:全扫描) vs 随机访问(比如:按照row id访问)
    • 读还是写

    以及数据库使用的磁盘类型:

    • 7.2k/10k/15k rpm的硬盘
    • SSD
    • RAID 1/5/…

    要我说,内存比磁盘要快100到10万倍

    然而,这导致了另一个问题(数据库总是这样…),缓存管理器需要在查询执行器使用数据之前得到数据,否则查询管理器不得不等待数据从缓慢的磁盘中读出来。

    预读

    这个问题叫预读。查询执行器知道它将需要什么数据,因为它了解整个查询流,而且通过统计也了解磁盘上的数据。道理是这样的:

    • 当查询执行器处理它的第一批数据时
    • 会告诉缓存管理器预先装载第二批数据
    • 当开始处理第二批数据时
    • 告诉缓存管理器预先装载第三批数据,并且告诉缓存管理器第一批可以从缓存里清掉了。
    • ……

    缓存管理器在缓冲池里保存所有的这些数据。为了确定一条数据是否有用,缓存管理器给缓存的数据添加了额外的信息(叫闩锁)。

    有时查询执行器不知道它需要什么数据,有的数据库也不提供这个功能。相反,它们使用一种推测预读法(比如:如果查询执行器想要数据1、3、5,它不久后很可能会要 7、9、11),或者顺序预读法(这时候缓存管理器只是读取一批数据后简单地从磁盘加载下一批连续数据)。

    为了监控预读的工作状况,现代数据库引入了一个度量叫缓冲/缓存命中率,用来显示请求的数据在缓存中找到而不是从磁盘读取的频率。

    注:糟糕的缓存命中率不总是意味着缓存工作状态不佳。更多信息请阅读Oracle文档

    缓冲只是容量有限的内存空间,因此,为了加载新的数据,它需要移除一些数据。加载和清除缓存需要一些磁盘和网络I/O的成本。如果你有个经常执行的查询,那么每次都把查询结果加载然后清除,效率就太低了。现代数据库用缓冲区置换策略来解决这个问题。

    缓冲区置换策略

    多数现代数据库(至少 SQL Server, MySQL, Oracle 和 DB2)使用 LRU 算法。

    LRU

    LRU代表最近最少使用(Least Recently Used)算法,背后的原理是:在缓存里保留的数据是最近使用的,所以更有可能再次使用。

    图解:

    为了更好的理解,我假设缓冲区里的数据没有被闩锁锁住(就是说是可以被移除的)。在这个简单的例子里,缓冲区可以保存 3 个元素:

    • 1:缓存管理器(简称CM)使用数据1,把它放入空的缓冲区
    • 2:CM使用数据4,把它放入半载的缓冲区
    • 3:CM使用数据3,把它放入半载的缓冲区
    • 4:CM使用数据9,缓冲区满了,所以数据1被清除,因为它是最后一个最近使用的,数据9加入到缓冲区
    • 5:CM使用数据4,数据4已经在缓冲区了,所以它再次成为第一个最近使用的
    • 6:CM使用数据1,缓冲区满了,所以数据9被清除,因为它是最后一个最近使用的,数据1加入到缓冲区
    • ……

    这个算法效果很好,但是有些限制。如果对一个大表执行全表扫描怎么办?换句话说,当表/索引的大小超出缓冲区会发生什么?使用这个算法会清除之前缓存内所有的数据,而且全扫描的数据很可能只使用一次。

    改进

    为了防止这个现象,有些数据库增加了特殊的规则,比如Oracle文档中的描述:

    『对非常大的表来说,数据库通常使用直接路径来读取,即直接加载区块[……],来避免填满缓冲区。对于中等大小的表,数据库可以使用直接读取或缓存读取。如果选择缓存读取,数据库把区块置于LRU的尾部,防止清空当前缓冲区。』

    还有一些可能,比如使用高级版本的LRU,叫做 LRU-K。例如,SQL Server 使用 LRU-2。

    这个算法的原理是把更多的历史记录考虑进来。简单LRU(也就是 LRU-1),只考虑最后一次使用的数据。LRU-K呢:

    • 考虑数据最后第K次使用的情况
    • 数据使用的次数加进了权重
    • 一批新数据加载进入缓存,旧的但是经常使用的数据不会被清除(因为权重更高)
    • 但是这个算法不会保留缓存中不再使用的数据
    • 所以数据如果不再使用,权重值随着时间推移而降低

    计算权重是需要成本的,所以SQL Server只是使用 K=2,这个值性能不错而且额外开销可以接受。

    关于LRU-K更深入的知识,可以阅读早期的研究论文(1993):数据库磁盘缓冲的LRU-K页面置换算法

    其他算法

    当然还有其他管理缓存的算法,比如:

    • 2Q(类LRU-K算法)
    • CLOCK(类LRU-K算法)
    • MRU(最新使用的算法,用LRU同样的逻辑但不同的规则)
    • LRFU(Least Recently and Frequently Used,最近最少使用最近最不常用)
    • ……

    写缓冲区

    我只探讨了读缓存 —— 在使用之前预先加载数据。用来保存数据、成批刷入磁盘,而不是逐条写入数据从而造成很多单次磁盘访问。

    要记住,缓冲区保存的是(最小的数据单位)而不是行(逻辑上/人类习惯的观察数据的方式)。缓冲池内的页如果被修改了但还没有写入磁盘,就是脏页。有很多算法来决定写入脏页的最佳时机,但这个问题与事务的概念高度关联,下面我们就谈谈事务。

    事务管理器

    最后但同样重要的,是事务管理器,我们将看到这个进程是如何保证每个查询在自己的事务内执行的。但开始之前,我们需要理解ACID事务的概念。

    “I’m on acid”

    一个ACID事务是一个工作单元,它要保证4个属性:

    • 原子性Atomicity): 事务『要么全部完成,要么全部取消』,即使它持续运行10个小时。如果事务崩溃,状态回到事务之前(事务回滚)。
    • 隔离性Isolation): 如果2个事务 A 和 B 同时运行,事务 A 和 B 最终的结果是相同的,不管 A 是结束于 B 之前/之后/运行期间。
    • 持久性Durability): 一旦事务提交(也就是成功执行),不管发生什么(崩溃或者出错),数据要保存在数据库中。
    • 一致性Consistency): 只有合法的数据(依照关系约束和函数约束)能写入数据库,一致性与原子性和隔离性有关。

    在同一个事务内,你可以运行多个SQL查询来读取、创建、更新和删除数据。当两个事务使用相同的数据,麻烦就来了。经典的例子是从账户A到账户B的汇款。假设有2个事务:

    • 事务1(T1)从账户A取出100美元给账户B
    • 事务2(T2)从账户A取出50美元给账户B

    我们回来看看ACID属性:

    • 原子性确保不管 T1 期间发生什么(服务器崩溃、网络中断…),你不能出现账户A 取走了100美元但没有给账户B 的现象(这就是数据不一致状态)。
    • 隔离性确保如果 T1 和 T2 同时发生,最终A将减少150美元,B将得到150美元,而不是其他结果,比如因为 T2 部分抹除了 T1 的行为,A减少150美元而B只得到50美元(这也是不一致状态)。
    • 持久性确保如果 T1 刚刚提交,数据库就发生崩溃,T1 不会消失得无影无踪。
    • 一致性确保钱不会在系统内生成或灭失。

    [以下部分不重要,可以跳过]

    现代数据库不会使用纯粹的隔离作为默认模式,因为它会带来巨大的性能消耗。SQL一般定义4个隔离级别:

    • 串行化(Serializable,SQLite默认模式):最高级别的隔离。两个同时发生的事务100%隔离,每个事务有自己的『世界』。
    • 可重复读(Repeatable read,MySQL默认模式):每个事务有自己的『世界』,除了一种情况。如果一个事务成功执行并且添加了新数据,这些数据对其他正在执行的事务是可见的。但是如果事务成功修改了一条数据,修改结果对正在运行的事务不可见。所以,事务之间只是在新数据方面突破了隔离,对已存在的数据仍旧隔离。
      举个例子,如果事务A运行”SELECT count(1) from TABLE_X” ,然后事务B在 TABLE_X 加入一条新数据并提交,当事务A再运行一次 count(1)结果不会是一样的。
      这叫幻读(phantom read)。
    • 读取已提交(Read committed,Oracle、PostgreSQL、SQL Server默认模式):可重复读+新的隔离突破。如果事务A读取了数据D,然后数据D被事务B修改(或删除)并提交,事务A再次读取数据D时数据的变化(或删除)是可见的。
      这叫不可重复读(non-repeatable read)。
    • 读取未提交(Read uncommitted):最低级别的隔离,是读取已提交+新的隔离突破。如果事务A读取了数据D,然后数据D被事务B修改(但并未提交,事务B仍在运行中),事务A再次读取数据D时,数据修改是可见的。如果事务B回滚,那么事务A第二次读取的数据D是无意义的,因为那是事务B所做的从未发生的修改(已经回滚了嘛)。
      这叫脏读(dirty read)。

    多数数据库添加了自定义的隔离级别(比如 PostgreSQL、Oracle、SQL Server的快照隔离),而且并没有实现SQL规范里的所有级别(尤其是读取未提交级别)。

    默认的隔离级别可以由用户/开发者在建立连接时覆盖(只需要增加很简单的一行代码)。

    并发控制

    确保隔离性、一致性和原子性的真正问题是对相同数据的写操作(增、更、删):

    • 如果所有事务只是读取数据,它们可以同时工作,不会更改另一个事务的行为。
    • 如果(至少)有一个事务在修改其他事务读取的数据,数据库需要找个办法对其它事务隐藏这种修改。而且,它还需要确保这个修改操作不会被另一个看不到这些数据修改的事务擦除。

    这个问题叫并发控制

    最简单的解决办法是依次执行每个事务(即顺序执行),但这样就完全没有伸缩性了,在一个多处理器/多核服务器上只有一个核心在工作,效率很低。

    理想的办法是,每次一个事务创建或取消时:

    • 监控所有事务的所有操作
    • 检查是否2个(或更多)事务的部分操作因为读取/修改相同的数据而存在冲突
    • 重新编排冲突事务中的操作来减少冲突的部分
    • 按照一定的顺序执行冲突的部分(同时非冲突事务仍然在并发运行)
    • 考虑事务有可能被取消

    用更正规的说法,这是对冲突的调度问题。更具体点儿说,这是个非常困难而且CPU开销很大的优化问题。企业级数据库无法承担等待几个小时,来寻找每个新事务活动最好的调度,因此就使用不那么理想的方式以避免更多的时间浪费在解决冲突上。

    锁管理器

    为了解决这个问题,多数数据库使用和/或数据版本控制。这是个很大的话题,我会集中探讨锁,和一点点数据版本控制。

    悲观锁

    原理是:

    • 如果一个事务需要一条数据
    • 它就把数据锁住
    • 如果另一个事务也需要这条数据
    • 它就必须要等第一个事务释放这条数据
      这个锁叫排他锁

    但是对一个仅仅读取数据的事务使用排他锁非常昂贵,因为这会迫使其它只需要读取相同数据的事务等待。因此就有了另一种锁,共享锁

    共享锁是这样的:

    • 如果一个事务只需要读取数据A
    • 它会给数据A加上『共享锁』并读取
    • 如果第二个事务也需要仅仅读取数据A
    • 它会给数据A加上『共享锁』并读取
    • 如果第三个事务需要修改数据A
    • 它会给数据A加上『排他锁』,但是必须等待另外两个事务释放它们的共享锁。

    同样的,如果一块数据被加上排他锁,一个只需要读取该数据的事务必须等待排他锁释放才能给该数据加上共享锁。

    锁管理器是添加和释放锁的进程,在内部用一个哈希表保存锁信息(关键字是被锁的数据),并且了解每一块数据是:

    • 被哪个事务加的锁
    • 哪个事务在等待数据解锁

    死锁

    但是使用锁会导致一种情况,2个事务永远在等待一块数据:

    在本图中:

    • 事务A 给 数据1 加上排他锁并且等待获取数据2
    • 事务B 给 数据2 加上排他锁并且等待获取数据1

    这叫死锁

    在死锁发生时,锁管理器要选择取消(回滚)一个事务,以便消除死锁。这可是个艰难的决定:

    • 杀死数据修改量最少的事务(这样能减少回滚的成本)?
    • 杀死持续时间最短的事务,因为其它事务的用户等的时间更长?
    • 杀死能用更少时间结束的事务(避免可能的资源饥荒)?
    • 一旦发生回滚,有多少事务会受到回滚的影响?

    在作出选择之前,锁管理器需要检查是否有死锁存在。

    哈希表可以看作是个图表(见上文图),图中出现循环就说明有死锁。由于检查循环是昂贵的(所有锁组成的图表是很庞大的),经常会通过简单的途径解决:使用超时设定。如果一个锁在超时时间内没有加上,那事务就进入死锁状态。

    锁管理器也可以在加锁之前检查该锁会不会变成死锁,但是想要完美的做到这一点还是很昂贵的。因此这些预检经常设置一些基本规则。

    两段锁

    实现纯粹的隔离最简单的方法是:事务开始时获取锁,结束时释放锁。就是说,事务开始前必须等待确保自己能加上所有的锁,当事务结束时释放自己持有的锁。这是行得通的,但是为了等待所有的锁,大量的时间被浪费了

    更快的方法是两段锁协议(Two-Phase Locking Protocol由 DB2 和 SQL Server使用),在这里,事务分为两个阶段:

    • 成长阶段:事务可以获得锁,但不能释放锁。
    • 收缩阶段:事务可以释放锁(对于已经处理完而且不会再次处理的数据),但不能获得新锁。

    这两条简单规则背后的原理是:

    • 释放不再使用的锁,来降低其它事务的等待时间
    • 防止发生这类情况:事务最初获得的数据,在事务开始后被修改,当事务重新读取该数据时发生不一致。

    这个规则可以很好地工作,但有个例外:如果修改了一条数据、释放了关联的锁后,事务被取消(回滚),而另一个事务读到了修改后的值,但最后这个值却被回滚。为了避免这个问题,所有独占锁必须在事务结束时释放

    多说几句

    当然了,真实的数据库使用更复杂的系统,涉及到更多类型的锁(比如意向锁,intention locks)和更多的粒度(行级锁、页级锁、分区锁、表锁、表空间锁),但是道理是相同的。

    我只探讨纯粹基于锁的方法,数据版本控制是解决这个问题的另一个方法

    版本控制是这样的:

    • 每个事务可以在相同时刻修改相同的数据
    • 每个事务有自己的数据拷贝(或者叫版本)
    • 如果2个事务修改相同的数据,只接受一个修改,另一个将被拒绝,相关的事务回滚(或重新运行)

    这将提高性能,因为:

    • 读事务不会阻塞写事务
    • 写事务不会阻塞读
    • 没有『臃肿缓慢』的锁管理器带来的额外开销

    除了两个事务写相同数据的时候,数据版本控制各个方面都比锁表现得更好。只不过,你很快就会发现磁盘空间消耗巨大。

    数据版本控制和锁机制是两种不同的见解:乐观锁和悲观锁。两者各有利弊,完全取决于使用场景(读多还是写多)。关于数据版本控制,我推荐这篇非常优秀的文章,讲的是PostgreSQL如何实现多版本并发控制的。

    一些数据库,比如DB2(直到版本 9.7)和 SQL Server(不含快照隔离)仅使用锁机制。其他的像PostgreSQL, MySQL 和 Oracle 使用锁和鼠标版本控制混合机制。我不知道是否有仅用版本控制的数据库(如果你知道请告诉我)。

    [2015-08-20更新]一名读者告诉我:

    Firebird 和 Interbase 用不带锁的版本控制。

    版本控制对索引的影响挺有趣的:有时唯一索引会出现重复,索引的条目会多于表行数,等等。

    如果你读过不同级别的隔离那部分内容,你会知道,提高隔离级别就会增加锁的数量和事务等待加锁的时间。这就是为什么多数数据库默认不会使用最高级别的隔离(即串行化)。

    当然,你总是可以自己去主流数据库(像MySQLPostgreSQL 或 Oracle)的文档里查一下。

    日志管理器

    我们已经知道,为了提升性能,数据库把数据保存在内存缓冲区内。但如果当事务提交时服务器崩溃,崩溃时还在内存里的数据会丢失,这破坏了事务的持久性

    你可以把所有数据都写在磁盘上,但是如果服务器崩溃,最终数据可能只有部分写入磁盘,这破坏了事务的原子性

    事务作出的任何修改必须是或者撤销,或者完成。

    有 2 个办法解决这个问题:

    • 影子副本/页(Shadow copies/pages):每个事务创建自己的数据库副本(或部分数据库的副本),并基于这个副本来工作。一旦出错,这个副本就被移除;一旦成功,数据库立即使用文件系统的一个把戏,把副本替换到数据中,然后删掉『旧』数据。
    • 事务日志(Transaction log):事务日志是一个存储空间,在每次写盘之前,数据库在事务日志中写入一些信息,这样当事务崩溃或回滚,数据库知道如何移除或完成尚未完成的事务。

    WAL(预写式日志)

    影子副本/页在运行较多事务的大型数据库时制造了大量磁盘开销,所以现代数据库使用事务日志。事务日志必须保存在稳定的存储上,我不会深挖存储技术,但至少RAID磁盘是必须的,以防磁盘故障。

    多数数据库(至少是Oracle, SQL ServerDB2PostgreSQL, MySQL 和 SQLite) 使用预写日志协议(Write-Ahead Logging protocol ,WAL)来处理事务日志。WAL协议有 3 个规则:

    • 1) 每个对数据库的修改都产生一条日志记录,在数据写入磁盘之前日志记录必须写入事务日志。
    • 2) 日志记录必须按顺序写入;记录 A 发生在记录 B 之前,则 A 必须写在 B 之前。
    • 3) 当一个事务提交时,在事务成功之前,提交顺序必须写入到事务日志。

    这个工作由日志管理器完成。简单的理解就是,日志管理器处于缓存管理器(cache manager)和数据访问管理器(data access manager,负责把数据写入磁盘)之间,每个 update / delete / create / commit / rollback 操作在写入磁盘之前先写入事务日志。简单,对吧?

    回答错误! 我们研究了这么多内容,现在你应该知道与数据库相关的每一件事都带着『数据库效应』的诅咒。好吧,我们说正经的,问题在于,如何找到写日志的同时保持良好的性能的方法。如果事务日志写得太慢,整体都会慢下来。

    ARIES

    1992年,IBM 研究人员『发明』了WAL的增强版,叫 ARIES。ARIES 或多或少地在现代数据库中使用,逻辑未必相同,但AIRES背后的概念无处不在。我给发明加了引号是因为,按照MIT这门课的说法,IBM 的研究人员『仅仅是写了事务恢复的最佳实践方法』。AIRES 论文发表的时候我才 5 岁,我不关心那些酸溜溜的科研人员老掉牙的闲言碎语。事实上,我提及这个典故,是在开始探讨最后一个技术点前让你轻松一下。我阅读过这篇 ARIES 论文 的大量篇幅,发现它很有趣。在这一部分我只是简要的谈一下 ARIES,不过我强烈建议,如果你想了解真正的知识,就去读那篇论文。

    ARIES 代表『数据库恢复原型算法』(Algorithms for Recovery and Isolation Exploiting Semantics)。

    这个技术要达到一个双重目标:

    • 1) 写日志的同时保持良好性能
    • 2) 快速和可靠的数据恢复

    有多个原因让数据库不得不回滚事务:

    • 因为用户取消
    • 因为服务器或网络故障
    • 因为事务破坏了数据库完整性(比如一个列有唯一性约束而事务添加了重复值)
    • 因为死锁

    有时候(比如网络出现故障),数据库可以恢复事务。

    这怎么可能呢?为了回答这个问题,我们需要了解日志里保存的信息。

    日志

    事务的每一个操作(增/删/改)产生一条日志,由如下内容组成:

    • LSN:一个唯一的日志序列号(Log Sequence Number)。LSN是按时间顺序分配的 * ,这意味着如果操作 A 先于操作 B,log A 的 LSN 要比 log B 的 LSN 小。
    • TransID:产生操作的事务ID。
    • PageID:被修改的数据在磁盘上的位置。磁盘数据的最小单位是页,所以数据的位置就是它所处页的位置。
    • PrevLSN:同一个事务产生的上一条日志记录的链接。
    • UNDO:取消本次操作的方法。
      比如,如果操作是一次更新,UNDO将或者保存元素更新前的值/状态(物理UNDO),或者回到原来状态的反向操作(逻辑UNDO) **。
    • REDO:重复本次操作的方法。 同样的,有 2 种方法:或者保存操作后的元素值/状态,或者保存操作本身以便重复。
    • …:(供您参考,一个 ARIES 日志还有 2 个字段:UndoNxtLSN 和 Type)。

    进一步说,磁盘上每个页(保存数据的,不是保存日志的)都记录着最后一个修改该数据操作的LSN。

    *LSN的分配其实更复杂,因为它关系到日志存储的方式。但道理是相同的。

    ** ARIES 只使用逻辑UNDO,因为处理物理UNDO太过混乱了。

    注:据我所知,只有 PostgreSQL 没有使用UNDO,而是用一个垃圾回收服务来删除旧版本的数据。这个跟 PostgreSQL 对数据版本控制的实现有关。

    为了更好的说明这一点,这有一个简单的日志记录演示图,是由查询 “UPDATE FROM PERSON SET AGE = 18;” 产生的,我们假设这个查询是事务18执行的。【译者注: SQL 语句原文如此,应该是作者笔误 】

    每条日志都有一个唯一的LSN,链接在一起的日志属于同一个事务。日志按照时间顺序链接(链接列表的最后一条日志是最后一个操作产生的)。

    日志缓冲区

    为了防止写日志成为主要的瓶颈,数据库使用了日志缓冲区

    当查询执行器要求做一次修改:

    • 1) 缓存管理器将修改存入自己的缓冲区;
    • 2) 日志管理器将相关的日志存入自己的缓冲区;
    • 3) 到了这一步,查询执行器认为操作完成了(因此可以请求做另一次修改);
    • 4) 接着(不久以后)日志管理器把日志写入事务日志,什么时候写日志由某算法来决定。
    • 5) 接着(不久以后)缓存管理器把修改写入磁盘,什么时候写盘由某算法来决定。

    当事务提交,意味着事务每一个操作的 1 2 3 4 5 步骤都完成了。写事务日志是很快的,因为它只是『在事务日志某处增加一条日志』;而数据写盘就更复杂了,因为要用『能够快速读取的方式写入数据』。

    STEAL 和 FORCE 策略

    出于性能方面的原因,第 5 步有可能在提交之后完成,因为一旦发生崩溃,还有可能用REDO日志恢复事务。这叫做 NO-FORCE策略

    数据库可以选择FORCE策略(比如第 5 步在提交之前必须完成)来降低恢复时的负载。

    另一个问题是,要选择数据是一步步的写入(STEAL策略),还是缓冲管理器需要等待提交命令来一次性全部写入(NO-STEAL策略)。选择STEAL还是NO-STEAL取决于你想要什么:快速写入但是从 UNDO 日志恢复缓慢,还是快速恢复。

    总结一下这些策略对恢复的影响:

    • STEAL/NO-FORCE 需要 UNDO 和 REDO: 性能高,但是日志和恢复过程更复杂 (比如 ARIES)。多数数据库选择这个策略。 注:这是我从多个学术论文和教程里看到的,但并没有看到官方文档里显式说明这一点。
    • STEAL/ FORCE 只需要 UNDO.
    • NO-STEAL/NO-FORCE 只需要 REDO.
    • NO-STEAL/FORCE 什么也不需要: 性能最差,而且需要巨大的内存。

    关于恢复

    Ok,有了不错的日志,我们来用用它们!

    假设新来的实习生让数据库崩溃了(首要规矩:永远是实习生的错。),你重启了数据库,恢复过程开始了。

    ARIES从崩溃中恢复有三个阶段:

    • 1) 分析阶段:恢复进程读取全部事务日志,来重建崩溃过程中所发生事情的时间线,决定哪个事务要回滚(所有未提交的事务都要回滚)、崩溃时哪些数据需要写盘。
    • 2) Redo阶段:这一关从分析中选中的一条日志记录开始,使用 REDO 来将数据库恢复到崩溃之前的状态。

    在REDO阶段,REDO日志按照时间顺序处理(使用LSN)。

    对每一条日志,恢复进程需要读取包含数据的磁盘页LSN。

    如果LSN(磁盘页)>= LSN(日志记录),说明数据已经在崩溃前写到磁盘(但是值已经被日志之后、崩溃之前的某个操作覆盖),所以不需要做什么。

    如果LSN(磁盘页)< LSN(日志记录),那么磁盘上的页将被更新。

    即使将被回滚的事务,REDO也是要做的,因为这样简化了恢复过程(但是我相信现代数据库不会这么做的)。

    • 3) Undo阶段:这一阶段回滚所有崩溃时未完成的事务。回滚从每个事务的最后一条日志开始,并且按照时间倒序处理UNDO日志(使用日志记录的PrevLSN)。

     

    恢复过程中,事务日志必须留意恢复过程的操作,以便写入磁盘的数据与事务日志相一致。一个解决办法是移除被取消的事务产生的日志记录,但是这个太困难了。相反,ARIES在事务日志中记录补偿日志,来逻辑上删除被取消的事务的日志记录。

    当事务被『手工』取消,或者被锁管理器取消(为了消除死锁),或仅仅因为网络故障而取消,那么分析阶段就不需要了。对于哪些需要 REDO 哪些需要 UNDO 的信息在 2 个内存表中:

    • 事务表(保存当前所有事务的状态)
    • 脏页表(保存哪些数据需要写入磁盘)

    当新的事务产生时,这两个表由缓存管理器和事务管理器更新。因为是在内存中,当数据库崩溃时它们也被破坏掉了。

    分析阶段的任务就是在崩溃之后,用事务日志中的信息重建上述的两个表。为了加快分析阶段,ARIES提出了一个概念:检查点(check point),就是不时地把事务表和脏页表的内容,还有此时最后一条LSN写入磁盘。那么在分析阶段当中,只需要分析这个LSN之后的日志即可。

    结语

    写这篇文章之前,我知道这个题目有多大,也知道写这样一篇深入的文章会相当耗时。最后证明我过于乐观了,实际上花了两倍于预期的时间,但是我学到了很多。

    如果你想很好地了解数据库,我推荐这篇研究论文:《数据库系统架构》,对数据库有很好的介绍(共110页),而且非计算机专业人士也能读懂。这篇论文出色的帮助我制定了本文的写作计划,它没有像本文那样专注于数据结构和算法,更多的讲了架构方面的概念。

    如果你仔细阅读了本文,你现在应该了解一个数据库是多么的强大了。鉴于文章很长,让我来提醒你我们都学到了什么:

    • B+树索引概述
    • 数据库的全局概述
    • 基于成本的优化概述,特别专注了联接运算
    • 缓冲池管理概述
    • 事务管理概述

    但是,数据库包含了更多的聪明巧技。比如,我并没有谈到下面这些棘手的问题:

    • 如何管理数据库集群和全局事务
    • 如何在数据库运行的时候产生快照
    • 如何高效地存储(和压缩)数据
    • 如何管理内存

    所以,当你不得不在问题多多的 NoSQL数据库和坚如磐石的关系型数据库之间抉择的时候,要三思而行。不要误会,某些 NoSQL数据库是很棒的,但是它们毕竟还年轻,只是解决了少量应用关注的一些特定问题。

    最后说一句,如果有人问你数据库的原理是什么,你不用逃之夭夭,现在你可以回答:

    转载地址:https://blog.csdn.net/strivenoend/article/details/80205377

    展开全文
  • mysql数据库底层原理

    千次阅读 2020-05-18 21:47:19
    一、MySQL 的基本定义: A.术语介绍 1. 数据库(Database) 是按照数据结构来组织、存储和管理...是建立在关系模型基础上的数据库,借助于集合代数等数学概念和方法来处理数据库中的数据。 特点: 数据以表格

    一、MySQL 的基本定义:

    A.术语介绍

    1. 数据库(Database)

    是按照数据结构来组织、存储和管理数据的仓库。
    每个数据库都有一个或多个不同的API用于创建、访问、管理、搜索和复制所保存的数据。
    

    2. RDBMS(Relational Database Management System)

    关系数据库管理系统,由瑞典MySQL AB公司开发,目前属于Oracle公司。
    是建立在关系模型基础上的数据库,借助于集合代数等数学概念和方法来处理数据库中的数据。
    

    特点:

    数据以表格的形式出现。
    每行为各种记录名称。
    每列为记录名称所对应的数据域。
    许多的行和列组成一张表单。
    若干的表单组成Database。
    

    RDBMS术语:

    数据库: 数据库是一些关联表的集合。
    数据表: 表示数据的矩阵。
    列: 一列(数据元素)包含了相同类型的数据。
    行: 一行是一组相关的数据。
    冗余: 存储两倍数据,冗余降低了性能,但提高了数据的安全性。
    主键: 主键是唯一的,一个数据表中只能包含一个主键。
    外键: 外键用于关联两个表。
    复合键: 复合键(组合键)将多个列作为一个索引键,一般用于复合索引。
    索引: 使用索引可快速访问数据库表中的特定信息,索引是对数据库表中一列或多列的值进行排序的一种结构。
    参照完整性: 参照完整性要求关系中不允许引用不存在的实体,与实体完整性是关系模型必须满足的完整性约束条件,目的是保证数据的一致性。
    

    B.MySQL常用命令

    1. 管理MySQL的命令

    MySQL的用户设置,只需要在MySQL数据库中的user表中添加新用户即可。(use mysql; insert into user() values())。
    
    USE  数据库名 :选择要操作的MySQL数据库,使用该命令后所有MySQL命令都只针对该数据库。
    SHOW DATABASES :列出MySQL数据库管理系统的数据库列表。
    SHOW TABLES :显示指定数据库的所有表,使用该命令前需要使用use命令来选择要操作的数据库。
    SHOW COLUMNS FROM 数据表名 :显示数据表的属性,属性类型,主键信息,是否NULL,默认值等其它信息。
    SHOW INDEX FROM 数据表名 : 显示数据表的详细索引信息,包括 PRIMARY KEY(主键)。
    SHOW TABLE STATUS FROM 数据库名 LIKE ‘pattern’\G  :该命令输出MySQL数据库管理系统的性能及统计信息。
    

    2. MySQL的基本命令

    CREATE DATABASE 数据库名:创建数据库。(或者使用root权限创建:mysqladmin -u root -p create数据库名)。
    DROP DATABASE 数据库名:删除数据库。(或者使用root权限删除:mysqladmin -u root -p drop 数据库名)。
    
    SHOW CREATE TABLE 数据库名:获取创建数据表(CREATE TABLE)语句,该语句包含了原数据表的结构、索引。
    

    创建数据表

    CREATE TABLE tb_name (column_name column_type);
    例:
    create tale tb_student(
        s_id  int  PRIMARY KEY  AUTO_INCREMENT,
        s_name varchar(20)  NOT NULL,
        s_sex varchar(10),
        s_age int
    )ENGINE=InnoDB  DEFAULT CHARSET=utf8;
    
    NOT NULL :在操作数据库时如果输入该字段的数据为NULL,则报错。
    AUTO_INCREMENT :定义列为自增的属性,一般用于主键,数值会自动加1。
    PRIMARY_KEY :定义列为主键,(也可以使用多列定义主键,以逗号分隔)(PRIMARY_KEY s_id, s_sex)。
    ENGINE :设置存储引擎,不定义则使用默认存储引擎(MySQL默认存储引擎是 InnoDB)。
    CHARSET :设置编码格式,默认是UTF-8。
    

    删除数据表

    DROP TABLE tb_name;
    

    删除表中字段

    ALTER TABLE tb_name DROP column;
    

    向表中添加字段

    ALTER TABLE tb_name ADD column 类型;          # 添加到最后一列。
    ALTER TABLE tb_name ADD column 类型 FIRST;    # 添加到第一列。
    ALTER TABLE tb_name ADD column 类型 AFTER column;  # 添加到某个字段之后。
    

    修改字段类型及名称

    ALTER TABLE tb_name MODIFY column 类型;    # 使用MODIFY修改。
    ALTER TABLE tb_name CHANGE old_column new_column 类型;  # 使用CHANGE修改。
    ALTER TABLE tb_name MODIFY column 类型 NOT NULL DEFAULT 100; # 指定字段非空,默认值100。
    

    修改字段默认值

    ALTER TABLE tb_name ALTER column SET DEFAULT 1000;  # 修改字段默认值。
    ALTER TABLE tb_name ALTER column DROP DEFAULT;     # 删除字段默认值。
    

    修改表名

    ALTER TABLE old_tb_name RENAME TO new_tb_name;
    

    修改存储引擎

    ALTER TABLE tb_name engine=InnoDB;
    

    修改外键约束

    ALTER TABLE tb_name DROP FOREIGN KEY keyname;
    

    插入数据

    INSERT INTO table_name (field1, field2, ……, fieldN)  VALUES (value1, value2, ……, valueN);
    

    更新数据

    UPDATE tb_name SET field1=new-value1, field2=new-value2 WHERE … ;
    WHERE子句中可以指定任何条件。
    

    删除数据

    DELETE FROM table_name WHERE … ;
    WHERE 子句中可以指定任何条件。
    

    查询数据

    SELECT column_name1, column_name2 FROM table_name1, table_name2 
    WHERE [condition1 [AND [OR]] condition2 …… ;
    
    查询语句中可以使用一个或者多个表,表之间使用逗号(,)分割,并使用WHERE语句设定查询条件。
    WHERE 子句中可以指定任何条件。
    可以使用AND或者OR指定一个或多个条件。
    可以使用LIKE子句代替等号(=),LIKE通常与(%)一同使用,类似于一个元字符的搜索(LIKE“ACC%”)。
    WHERE子句也可以运用SQL的DELETE或UPDATE命令。
    可以使用LIMIT属性来设定返回的记录数。
    可以使用OFFSET指定SELECT语句开始查询的数据偏移量,默认偏移量为0。
    WHERE子句类似于程序语言中的if条件,根据MySQL表中的字段值来读取指定的数据。
    
    WHERE子句操作符:
    =        :等于
    <>, !=   :不等于
    >        :大于
    <        :小于
    >=      :大于等于
    <=      :小于等于
    

    UNION操作符

    UNION操作符用于连接两个以上的SELECT语句的结果组合到一个结果集合中。
    多个SELECT语句会删除重复的数据。
    
    SELECT expression1, expression2, ……, expressionN FROM tb_name1 WHERE ……
    UNION  [ ALL | DISTINCT ]
    SELECT expression1, expression2, ……, expressionN FROM tb_name2 WHERE ……;
    
    ALL :可选项,返回所有结果集,包含重复数据。
    DISTINCT :可选项,删除结果集中重复的数据。
    

    排序

    ORDER BY :对查询结果进行排序。
    SELECT column1, column2 FROM tb_name WHERE …… ORDER BY field1 [ASC/DESC],field2 [ASC/DESC]。
    
    ASC/DESC :升序/降序,默认ASC。
    

    分组

    GROUP BY :对查询结果进行分组。
    SELECT column1, column2 FROM tb_name WHERE …… GROUP BY column1, column2。
    

    连接

    JOIN  :在两个或多个表中查询数据。
    
    INNER JOIN(内连接,或等值连接):获取两个表中字段匹配关系的记录。
     内连接使用比较运算符对两个表中的数据进行比较,并列出与连接条件匹配的数据行,组合成新的记录,结果只保留满足条件的记录。
     SELECT column1, … FROM tb_name1 INNER JOIN tb_name2 ON tb_name1.id = tb_name2.id;
    
    LEFT JOIN(左连接):获取左表所有记录,即使右表没有对应匹配的记录。
    左表保持不动,右表在右侧滑动,用右表匹配左表,结果保留左表的所有行,右表中不匹配的行默认填充为空值NULL。
    SELECT column1, … FROM tb_name1 LEFT JOIN tb_name2 ON tb_name1.id=tb_name2.id;
    
    RIGHT JOIN(右连接):获取右表所有记录,即使左表没有对应匹配的记录。
    右表保持不动,左表在左侧滑动,用左表匹配右表,结果保留右表的所有行,左表中不匹配的行默认填充为空值NULL。
    SELECT column1, … FROM tb_name1 RIGHT JOIN tb_name2 ON tb_name1.id=tb_name2.id;
    

    空值

    IS NULL :当列的值是NULL,此运算符返回true。
    IS NOT NULL :当列的值不为NULL,此运算符返回true。
    <=> :比较操作符(不同于 = 运算符) :当比较的两个值相等或者都为NULL时,返回true。
    

    3. MySQL数据类型

    数值类型

    MySQL中支持所有标准SQL数值数据类型。
    包括严格数值数据类型(INTEGER,SMALLINT,DECIMAL,NUMERIC)。
    以及近似数值数据类型(FLOAT,REAL,DOUBLE PRECISION)。
    

    日期和时间类型

    表示时间值的日期和时间类型(DATETIME,DATE,TIMESTAMP,TIME,YEAR)。
    每个时间类型有一个有效值范围和一个“零”值,当指定不合法的MySQL不能表示的值时使用“零”值。
    

    字符串类型

    字符串类型(CHAR,VARCHAR,BINARY,VARBINARY,BLOB,TEXT,ENUM,SET)。
    

    4. MySQL索引

    索引是应用在SQL查询语句的条件,一般作为WHERE子句的条件。
    
    主键索引:数据列不允许重复,不允许为NULL,一个表只能有一个主键。
    普通索引:基本的索引类型,没有唯一性限制,允许为NULL值。
    唯一索引:索引列的值必须唯一,但允许有空值;如果是组合索引,则列值的组合必须唯一。
    前缀索引:用列的前缀代替整个列作为索引key,比如:like‘xxx%’。
    Hash索引:采用一定的哈希算法,把键值换算成新的哈希值,只需一次哈希算法即可定位到相应的位置,查询速度非常快。
    

    创建索引的三种方式

    CREATE INDEX indexName ON tb_name(column(length));   # 直接创建索引。
    ALTER TABLE tb_name ADD INDEX indexName(column);    # 修改表结构时添加索引。
    CREATE TABLE tb_name(                                  # 创建表的时候直接指定。
        id int NOT NULL,
        username VARCHAR(16) NOT NULL,
        INDEX  [indexName] (username(length))
    );
    

    创建唯一索引的三种方式

    CREATE UNIQUE INDEX indexName ON tb_name(column(length));    # 直接创建索引。
    ALTER TABLE tb_name ADD UNIQUE [indexName] (column(length));  # 修改表结构时创建索引。
    CREATE TABLE tb_name(                                             # 创建表时添加索引。
        id int NOT NULL,
        username VARCHAR(16) NOT NULL,
        UNIQUE [indexName] (username(length))
    );
    

    删除索引

    DROP INDEX [indexName] ON tb_name;
    

    使用ALTER命令添加、删除索引

    ALTER TABLE tb_name ADD PRIMARY KEY (column);   # 该语句添加一个主键,索引值必须是唯一的,且不能为NULL。
    ALTER TABLE tb_name ADD UNIQUE indexName (column);  # 该语句创建索引的值必须是唯一的(除NULL外)。
    ALTER TABLE tb_name ADD INDEX indexName (column);     # 添加普通索引,索引值可出现多次。
    ALTER TABLE tb_name ADD FULLTEXT indexName (column);  # 该语句指定索引为FULLTEXT,用于全文索引。
    ALTER TABLE tb_name DROP INDEX column;   # 删除索引。
    ALTER TABLE tb_name ADD PRIMARY KEY (column);   # 添加主键。
    ALTER TABLE tb_name DROP PRIMARY KEY;      # 删除主键。
    
    SHOW INDEX FROM tb_name;    # 显示索引信息。
    

    explain

    查看执行计划,使用explain关键字可以模拟优化器执行SQL语句,查看使用到的索引列及其它信息。
    explain select * from tb_name;
    

    5. 索引使用策略及优化

    最常用的索引底层存储结构是棵 B- Tree 或 B+ Tree。
    

    索引有两种:单列索引 和 组合索引

    单列索引:一个索引只包含单个列,一个表可以有多个单列索引。
    组合索引:一个索引包含多个列。
    
    单列索引:一个索引只能有一个字段。
    组合索引:也称复合索引,相对于单列索引,组合索引可以为多个字段创建一个索引。
    

    最左前缀原理

    最左匹配就是最左边优先;创建组合索引时,要根据业务要求,where子句中使用最频繁的一列放在最左边。
    组合索引的查找是先根据第一个字段查,然后再根据第二个字段查,或者只根据第一个字段查,但是不能跳过第一个字段、直接从第二个字段开始查,这就是所谓的最左前缀原理。
    
    第一个字段是有序的。
    当第一个字段值相等的时候,第二个字段也是有序的。
    当第一个字段值相等、第二个字段值也相等时,第三个字段也是有序的。
    
    例:在字段 a, b, c上创建一个联合索引,索引顺序会首先按照a字段排序,然后再按照b字段排序,最后是c字段。
    下面的SQL语句是按照((a),(a, b),(a, b, c))的顺序用到索引。
    select * from tb_name where a = 0;
    select * from tb_name where a = 0 and b = 1;
    select * from tb_name where a = 0 and b = 1 and c = 2;
    
    下面的SQL语句只用到一个索引a 。
    select * from tb_name where a = 0 and c = 2;
    
    下面的SQL语句未使用到索引,因未遵循最左匹配原理。
    select * from tb_name where b = 1 and c = 2;
    
    以MySQL为例,下面的SQL语句也能使用到索引,查询优化器会重新编译,不建议这样使用。
    select * from tb_name where b = 1 and c = 2 and a = 0;
    

    索引优化

    1. 主键、外键要建索引。
    2. 对where, on, group by, order by中出现的列使用索引。
    3. 最左匹配原则(重中之重)。
    4. 尽量扩展索引;例:已经有a字段索引,现在要使用(a, b)字段的索引,只需修改原来的索引即可。
    5. 不要过多创建索引,索引过多会影响插入、删除数据的速度。
    6. 对于like查询,“%”不要放在前面。
    7. where条件数据类型不匹配也无法使用索引。
    8. 为较长的字符串使用前缀索引。
    9. 对索引列进行函数运算时索引也会失效。
    

    6. 聚集索引 与 非聚集索引

    聚集索引 与 非聚集索引底层引用的都是 B+ 树索引。
    

    聚集索引(clustered)

    也叫聚簇索引,数据行的物理顺序与列值(主键)的逻辑顺序相同,一个表中只能拥有一个聚集索引。
    

    非聚集索引(unclustered)

    该索引中索引的逻辑顺序与磁盘上行的物理存储顺序不同,一个表中可以拥有多个非聚集索引。
    

    7. MySQL数据导入、导出(导入、导出文件需用户有FILE权限)

    常用导出数据语句

    SELECT … INTO OUTFILE
    将一个数据库的数据写入一个文件,输出不能是一个已存在的文件。
    SELECT * FROM tb_name INTO OUTFILE ‘/tmp/tmp.txt’;
    
    LOAD DATA INFILE
    将文件读回数据库。
    

    常用导入数据语句

    mysql命令导入
    mysql  -u用户名  -p密码   <   要导入的数据库数据(tmp.sql)
    例:mysql -uroot -p123456 < tmp.sql     # 将备份的整个数据库tmp.sql导入
    
    source 命令导入
    create database abc;           # 创建数据库。
    use abc;                       # 使用已创建的数据库。
    set names utf8;                # 设置编码。
    source  /home/abc/abc.sql;    # 导入备份数据库。
    
    LOAD DATA命令导入
    LOAD DATA LOCAL INFILE ‘tmp.txt’ INTO TABLE myTable
    FIELDS TERMINATED BY ‘:’
    LINES TERMINATED BY ‘\r\n’;     # 将tmp.txt文件中的数据导入myTable表中
    
    如果指定LOCAL关键词,则表明从客户主机上按路径读取文件。
    如果没有指定,则文件在服务器上按路径读取文件。
    

    二、数据库事务与并发性:

    A.数据库事务

    在MySQL中,只有使用了Innodb引擎的数据库或表才支持事务。
    

    1. 数据库事务定义

    事务处理可以用来维护数据库的完整性,保证SQL语句要么全部执行,要么全部不执行。
    事务用来管理 insert, update, delete 语句。
    

    1)原子性(Atomicity, 或称不可分割性)

    一个事务中的操作,要么全部完成,要么全部不完成,不会结束在中间某个环节。
    事务在执行过程中发生错误,会被回滚到事务开始前的状态。
    

    2)一致性(Consistency)

    在事务开始之前和事务结束之后,数据库的完整性没有被破坏。
    这表示写入的资料必须完全符合所有的预设规则。
    

    3)隔离性(Isolation,又称独立性)

    数据库允许多个并发事务同时对其数据进行读写和修改的能力。
    隔离性可以防止多个事务并发执行时由于交叉执行而导致数据的不一致。
    

    4)持久性(Durability)

    事务处理结束后,对数据的修改是永久的,即便系统故障也不会丢失。
    

    2. 事务控制语句

    MySQL数据库事务默认都是自动提交的,即执行完SQL语句后就会马上执行COMMIT操作。
    显示地开启、提交事务
    
    BEGIN / START TRANSACTION : 开启一个事务。
    COMMIT / COMMIT WORK :提交事务,使已对数据库进行的所有修改成为永久性的。
    ROLLBACK / ROLLBACK WORK :回滚事务,撤销正在进行的所有未提交的修改。
    
    SAVEPOINT identifier :允许在事务中创建一个保存点,一个事务中可以有多个SAVEPOINT。
    RELEASE SAVEPOINT identifier :删除一个事务的保存点,当没有指定的保存点时,执行该语句会抛出一个异常。
    ROLLBACK TO identifier :把事务回滚到标记点。
    SAVEPOINT 是在数据库事务处理中实现“子事务”,也称嵌套事务的方法。
    
    事务可以回滚到SAVEPOINT而不影响SAVEPOINT创建前的变化,不需要放弃整个事务。
    SAVEPOINT savepoint_name;     # 声明一个savepoint 。
    ROLLBACK TO savepoint_name;   # 回滚到 savepoint 。
    RELEASE SAVEPOINT savepoint_name;   # 删除指定保留点 。
    
    SET TRANSACTION :用来设置事务的隔离级别。
    
    MySQL事务处理的两种方法
    1) 用BEGIN, ROLLBACK, COMMIT实现。
        BEGIN 开始一个事务。
        ROLLBACK 回滚事务。
        COMMIT 提交事务。
    
    2)直接用SET来改变MySQL的自动提交模式
    SET AUTOCOMMIT = 0  :禁止自动提交。
    SET AUTOCOMMIT = 1  :开启自动提交。
    

    B.数据库并发性

    不同的数据库隔离级别不同,使用加锁的方式也不同。
    MySQL支持四种事务隔离级别,默认隔离级别是(RR, Repeatable Read)。
    Oracle 支持两种事务隔离级别(RC 与 Serializable),默认隔离级别是(RC, Read Committed)。
    

    1. 读数据的概念

    1) 脏读(Dirty Reads)

    就是对脏数据的读取,脏数据指的是未提交的数据。
    

    2) 不可重复读(Non-Repeatable Reads)

    一个事务先后读取同一条记录,两次读取的数据不同。
    

    3) 幻读(Phantom Reads)

    一个事务按相同的查询条件重新读取以前检索过的数据,却发现其它事务插入了满足其查询条件的新数据。
    

    例:存在两个事务(T1, T2)同时运行

    T1读取了已经被T2修改但还未提交的字段,由于某种原因,T2事务回滚,则T1读取的内容是临时且无效的;这就是脏读。
    T1读取一个字段,之后T2更新了该字段,T1再次读取该字段值时则读取到的是被T2更新后的新值;这就是不可重复读。
    T1从一个表中读取了一个字段,然后T2在该表中插入了一些新的行,之后T1再次读取该表时会多出几行。这就是幻读。
    

    2. 数据库隔离级别

    1) Read UnCommitted(读未提交数据)

    允许事务读取未被其它事务提交的变更数据。
    会出现脏读、不可重复读和幻读问题,隔离级别最低(读不锁)。
    

    2) Read Committed(读已提交数据)

    允许事务读取已经被其它事务提交的变更数据。
    可避免脏读,扔会出现不可重复读和幻读问题(读锁)。
    

    3) Repeatable Read(可重复读)

    确保事务可以多次从一个字段中读取相同的值。
    在此事务持续期间,禁止其它事务对此字段的更新。
    可以避免脏读和不可重复读,扔会出现幻读问题,RR隔离级别对读取到的记录加锁(写锁)。
    

    4) Serializable(序列化)

    确保事务可以从一个表中读取相同的行,在这个事务持续期间,禁止其它事务对该表执行插入、更新和删除操作。
    可避免所有并发问题,但性能非常低。
    所有的SELECT语句都被隐士的转换成SELECT …… LOCK IN SHARE MODE。
    即读取使用表级共享锁,读写相互都会阻塞,隔离级别最高(表级锁)。
    

    3. 数据库的存储引擎

    常见的数据库存储引擎有:(1)MyISAM    (2)InnoDB 。
    

    1) MyISAM

    支持表级锁。
    适用场景:读多写少,硬件配置不高。
    

    2) InnoDB (MySQL默认存储引擎)

    支持表级、行级(默认)锁。
    适用场景:支持事务、支持外键,即有读又有写的业务中。
    

    4. 数据库锁

    锁主要用于多用户环境下保证数据库完整性和一致性。
    

    1) 锁按使用方式划分

    乐观锁

    每次去拿数据的时候都认为别人不会修改,所以不会上锁。
    但是在更新的时候会判断一下在此期间别人有没有去更新这个数据。
    如果发生冲突了,则返回用户错误信息,让用户决定如何去做。
    大多是基于数据版本(Version)记录机制实现。
    

    悲观锁

    每次去拿数据的时候都认为别人会修改,所以每次拿数据的时候都会上锁。
    

    2) 锁按级别划分

    共享锁

    共享锁(Share Lock),S锁,也叫读锁,用于所有的只读数据操作。
    共享锁是非独占的,允许多个并发事务读取其锁定的资源。
    
    共享锁性质:
    多个事务可封锁同一个共享页。
    任何事务都不能修改该页。
    通常是该页被读取完毕,S锁立即被释放。
    

    排他锁

    排他锁(Exclusive Lock),X锁,也叫写锁,用于对数据进行写操作。
    如果一个事务对对象加了排他锁,其它事务就不能再给它加任何锁了。
    
    排他锁性质
    仅允许一个事务封锁此页。
    其它任何事务必须等到X锁被释放才能对该页进行访问。
    X锁一直到事务结束才能被释放。
    

    3) 锁按粒度划分(MySQL)

    表级锁

    锁的作用范围是整张表。
    开销小、加锁快,不会出现死锁。
    锁定粒度大,发生锁冲突的概率最高,并发度最低。
    

    行级锁

    锁的作用范围是行级别。
    开销大、加锁慢,会出现死锁。
    锁定粒度最小,发生锁冲突的概率最低,并发度最高。
    

    页级锁

    锁的作用范围是整个页面。
    开销和加锁时间界于表锁和行锁之间,会出现死锁,锁定粒度界于表锁和行锁之间,并发度一般。
    

    4) 意向锁

    意向锁是InnoDB自动加的,不需要用户干预。
    

    意向共享锁(Intention Shared Lock)

    表示事务准备给数据行加入共享锁,也就是说一个数据行加共享锁前必须先取得该表的IS锁。
    

    意向排它锁(Intention Exclusive Lock)

    表示事务准备给数据行加入排它锁,也就是说一个数据行加排它锁前必须先取得该表的IX锁。
    

    5. 锁实现方式

    当一个事务获得对一个表的写锁后,只有持有锁的事务可以对表进行更新操作,其它事务的读、写操作都会等待,直到锁被释放为止。
    当一个事务获取对一个表的读锁后,其它事务也可以获取此表的读操作权限,但其它事务不能获取此表的写操作权限,直到锁被释放为止。
    

    1) 行级锁实现方式

    行级锁不是锁记录,而是锁索引;只有通过索引条件检索数据,才能使用行级锁。
    

    隐式加锁

    对于UPDATE、DELETE、INSERT语句,InnoDB会自动给涉及数据集加排他锁。
    对于普通SELECT语句,InnoDB不会加任何锁。
    

    显式加锁

    SELECT * FROM tb_name WHERE …… LOCK IN SHARE MODE;    # 加共享锁。
    SELECT * FROM tb_name WHERE …… FOR UPDATE;              # 加排他锁。
    

    2) 表级锁实现方式

    隐式加锁

    在执行查询语句SELECT前,会自动给涉及的所有表加读锁。
    在执行更新操作UPDATE、DELETE、INSERT前,会自动给涉及的表加写锁。
    

    显式加锁

    LOCK TABLE tb_name WRITE;     # 加写锁
    LOCK TABLE tb_name READ;    # 加读锁
    
    UNLOCK TABLES;     # 释放锁
    

    6. InnoDB锁机制

    1) Record Lock

    行锁,单条索引记录加锁,Record Lock锁住的是索引,而非记录本身。
    

    2) Gap Lock

    间隙锁,在索引记录之间的间隙中加锁,或者是在某一条索引记录之前或者之后加锁,并不包括该索引记录本身。
    Gap Lock 是针对事务隔离级别为RR或以上。
    Gap Lock在InnoDB的唯一作用就是防止其它事务的插入操作,以此防止幻读的发生。
    Gap Lock 一般针对非唯一索引而言。
    

    3) Next-key Lock

    Next-key Lock是Record Lock和Gap Lock的结合,即锁住了记录本身,还要锁住索引之间的间隙。
    MySQL 的事务隔离级别默认是RR,若innodb_locks_unsafe_for_binlog参数为0,默认采用Next-key Lock。
    Next-key Lock是行锁和间隙锁的组合,当InnoDB扫描索引记录的时候,会首先对索引记录加上行锁(Record Lock),再对索引记录两边的间隙加上间隙锁(Gap Lock)。
    
    加上间隙锁之后,其它事务就不能在这个间隙修改或者插入记录。
    

    7. 死锁

    死锁是指两个或两个以上的进程在执行过程中,因争夺资源而造成的一种互相等待的现象,若无外力作用,他们都将无法推进下去。
    

    1) 产生死锁的原因

    系统的资源不足。
    代码执行的顺序不合适。
    资源分配不当。
    

    2) 产生死锁的必要条件

    互斥条件:一个资源每次只能被一个进程使用。
    请求与保持条件:一个进程因请求资源而阻塞时,对已获得的资源保持不放。
    不剥夺条件:进程已获得的资源,在未使用完之前,不能强行剥夺。
    循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。
    

    3) 减少死锁发生

    按同一顺序访问对象。
    避免事务中的用户交互。
    保持事务简短并在一个批处理中。
    使用低隔离级别。
    使用绑定连接。
    

    8. MVCC多版本并发控制

    MVCC:Multi-Version Concurrency Control 多版本并发控制。
    MVCC是一种并发控制的方法,一般在数据库管理系统中实现对数据库高并发场景下的吞吐性能。
    

    1) MVCC原理

    MVCC的实现,通过保存数据在某个时间点的快照来实现的。
    在每行记录后面保存两个隐藏的列,一列保存了行的创建时间,另一列保存了行的过期时间(或删除时间)。
    这里存储的时间并不是实际的时间值,而是系统版本号。
    每开始一个新事物,系统版本号都会自动递增。
    事务开始时刻的系统版本号会作为事务的版本号,用来与查询到的每行记录的版本号进行比较。
    

    2) MVCC特征

    每行数据都存在一个版本,每次数据更新时都更新该版本。
    修改时copy出当前版本进行修改,各个事务之间互不干扰。
    保存时比较版本号,如果成功(commit),则覆盖原纪录,失败则放弃copy(rollback)。
    

    3) MVCC实现

    在每一行数据中额外保存两个隐藏的列:(1)DATA_TRX_ID   (2)DATA_ROLL_PTR。
    
    DATA_TRX_ID
    记录最近一次修改(insert / update)本行纪录的事务id,大小为6字节。
    
    DATA_ROLL_PTR
    指向该行回滚段(rollback segment)的undo log record(撤销日志记录)指针,大小为7字节。
    如果一行记录被更新,则undo log record 包含“重建该行记录被更新之前内容”所必须的信息。
    InnoDB便是通过这个指针找到之前版本的数据。
    若该行记录上存储所有的旧版本,在undo中都通过链表的形式组织。
    
    如果表没有主键,则还会有一个隐藏的主键列 DB_ROW_ID。
    
    DB_ROW_ID
    行标识(隐藏单调自增ID),大小为6字节,如果表没有主键,InnoDB会自动生成一个隐藏主键。
    
    例:事务1、事务2, DATA_TRX_ID,   DATA_ROLL_PTR, DB_ROW_ID。
    事务1。
    执行新增一条数据 insert操作。
    此时DB_ROW_ID = 1, DATA_TRX_ID = 1(系统版本号),  DATA_ROLL_PTR = NULL。
    
    事务 2 执行update操作过程。
    对DB_ROW_ID = 1这行记录加排它锁。
    把该行copy前的值拷贝到undo log中。
    修改该行的值,这时会产生一个新版本号,更新DATA_TRX_ID为修改记录的事务ID。
    将DATA_ROLL_PTR指向刚刚copy到undo log 链中的旧版本记录,这样就能通过DATA_ROLL_PTR找到这条记录的历史版本;如果对同一行记录执行连续的UPDATE, undo log会组成一个链表,遍历这个链表可以看到这条记录的变迁。
    记录redo log,包括undo log中的修改。
    

    4) RR隔离级别下,MVCC具体的操作流程。

    SELECT :InnoDB只查找版本早于当前事务版本的数据行;行的删除版本,要么未定义,要么大于当前事务版本号,这样可以确保事务读取到的行在事务开始之前未被删除。
    INSERT :InnoDB为插入的每一行保存当前系统版本号作为行版本号。
    DELETE :InnoDB为删除的每一行保存当前系统版本号作为删除标识,标记为删除、而不是实际删除。
    UPDATE :InnoDB会把原来的行复制一份到回滚段中,保存当前系统版本号作为行版本号,同时,保存当前系统版本号到原来的行作为删除标识。
    

    三、InnoDB引擎的底层实现方式:

    InnoDB核心:(1)日志   (2)内存(缓存池(Buffer Pool))  (3) 磁盘(Datafile)
    InnoDB存储引擎有多个内存块,这些内存块组成了一个大的内存池。
    后台线程主要负责刷新内存池中的数据,将已修改的数据刷新到磁盘。
    
    当某个事务进行一次写操作时,InnoDB引擎将数据写入redo log后就会提交事务。
    而非写入到磁盘(Datafile),之后InnoDB再异步地将新事务的数据异步地写入Datafile,真正存储起来。
    

    A.redo log 和 undo log 和 bin log

    用来恢复事务所对应的脏数据块的日志文件。
    

    1. 前滚 与 回滚

    前滚

    未完全提交的事务,即该事务已经被执行commit命令了。
    该事务所对应的脏数据块中只有一部分被写到磁盘上的数据文件中,一部分还在内存中。
    若此时数据库实例崩溃,就需要用前滚来完成事务的完全提交。
    

    回滚

    未提交的事务,即该事务未被执行commit命令。
    

    2. Redo log

    重做日志,提供前滚操作。
    Redo log 通常是物理日志,记录的是数据页的物理修改,用来恢复提交后的物理数据页。
    恢复数据页、且只能恢复到最后一次提交的位置。
    

    Redo log 包括两部分

    内存中的日志缓冲(redo log buffer),该部分日志是易失性的。
    磁盘上的重做日志文件(redo log file),该部分日志是持久的。
    

    3. Undo log

    回滚日志,提供回滚操作。
    Undo log用来回滚行记录到某个版本。
    undo log一般是逻辑日志,根据每行记录进行记录。
    

    4. Bin log

    二进制日志,记录对数据发生或潜在发生更改的SQL语句,并以二进制的形式保存在磁盘中。
    可以用来查看数据库的变更历史(具体的时间点所做的操作),数据库增量备份和恢复。
    Show variables like %log_bin% ; 
    

    B.InnoDB内存

    1. InnoDB线程

    Master Thread

    最核心的线程,主要负责将缓存池中的数据异步刷新到磁盘,保证数据的一致性。
    

    IO Thread

    IO Thread 主要负责大量的异步IO来处理写IO请求。
    

    Purge Thread

    Purge Thread回收已经使用并分配的undo页,InnoDB支持多个Purge Thread,这样做可以加快undo页的回收。
    

    Page Cleaner Thread

    Page Cleaner Thread是将之前版本中脏页的刷新操作都放入单独的线程中来完成,减轻Master Thread的工作及对于用户查询线程的阻塞。
    

    2. InnoDB内存模型

    InnoDB引擎使用缓存池技术来提高数据库的整体性能。
    InnoDB中缓存池页的大小默认为16KB。
    

    计算机科学中著名的局部性原理

    当一个数据被用到时,其附近的数据也通常会马上被使用,程序运行期间所需要的数据通常比较集中。
    

    内存 与 磁盘

    主存和磁盘是以页为单位交换数据。
    当程序要读取的数据不在主存中时,会触发一个缺页异常。
    此时系统会向磁盘发出读盘信号,磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中。
    然后异常返回,程序继续运行。
    数据库、内存、磁盘
    在数据库中进行读取页的操作时,首先将从磁盘读到的页存放在缓存池中。
    下一次读取相同的页时,首先判断页是不是在缓存池中。
    若在、称该页在缓存池中被命中,直接读取该页。
    否则、读取磁盘上的页。
    
    对于数据库中页的修改操作,首先修改在缓存池中的页,然后再以一定的频率刷新到磁盘。 
    

    3. 缓存池(Buffer Pool)

    为了更好的管理这些被缓存的页,InnoDB为每一个缓存页都创建了一些控制信息(控制块)。
    这些控制信息包括该页所属的表空间编号、页号、页在Buffer Pool中的地址、锁信息、LSN信息等。
    每个缓存页对应一个控制块,每个控制块占用的内存大小是相同的,它们都被放到Buffer Pool中,如下图。

    4. Free List(空闲链表)

    启动MySQL服务器时,需要对Buffer Pool进行初始化,将Buffer Pool划分成若干对控制块和缓存页。
    随着程序的运行,会不断的将磁盘上的页缓存到Buffer Pool中,但如何管理Buffer Pool中空闲的缓存页呢?
    使用Free List(空闲链表)来管理空闲的缓存页,如下图。

    Free List控制信息:包含链表的头结点地址、尾结点地址、以及当前链表中结点的数量。
    每个Free List的结点中都记录了某个缓存页控制块的地址。
    每个缓存页控制块都记录着对应的缓存页地址。
    
    每当需要从磁盘中加载一个页到Buffer Pool中时,就从Free List中取一个空闲的缓存页,并且把该缓存页对应的控制块的信息填上,然后把该缓存页对应的Free List结点从Free List链表中删除。
    

    5. Buffer Pool 清理机制

    缓存命中率:假设一共访问了n次页,那么被访问的页已经在缓存中的次数除以n就是缓存命中率。
    
    InnoDB Buffer Pool采用经典的LRU算法进行页面淘汰,以提高缓存命中率。
    LRU(Least Recently Used):最近最少使用,用来管理缓存池中页的可用性。
    如果该页不在Buffer Pool中,在把该页从磁盘加载到Buffer Pool中的缓存页时,就把该缓存页包装成结点塞到链表的头部。
    如果该页在Buffer Pool中,则直接把该页对应的LRU链表结点移动到链表的头部。
    
    缺点
    若遇一次全表扫描就把热数据给冲完了,就会导致Buffer Pool污染问题,严重的降低了缓存命中率。
    Buffer Pool中的所有数据页都被换了一次血,其它查询语句在执行时又得执行一次从磁盘加载到Buffer Pool的操作。
    

    midpoint insertion stategy

    InnoDB存储引擎对传统的LRU算法做了一些优化。
    在InnoDB中加入了midpoint,新读到的页,虽然是最新访问的页。
    但并不直接插入到LRU列表的首部,而是插入到LRU列表的midpoint位置。
    默认配置插入到列表长度的 5/8 处,midpoint由参数innodb_old_blocks_pct控制。
    
    Midpoint之前的列表称之为new列表,之后的列表称之为old列表。
    可以简单的将new列表中的页理解为最活跃的热点数据。
    
    InnoDB存储引擎还引入了 innodb_old_blocks_time 来表示页读取到mid位置之后需要等待多久才会被加入到LRU列表的热端,可以通过设置该参数保证热点数据不轻易被刷出。
    
    

    6. FLUSH链表(Flush List)

    FLUSH链表用来管理将页刷新回磁盘,缓存池中通过FLUSH 链表存储需要被刷新到磁盘上的页(脏页)。
    这里的脏页指的是此页被加载进Buffer Pool后第一次修改后的页。
    只有第一次修改时才需要加入FLUSH链表(第二次修改时已经存在了)。
    

    7. LRU List, Free List, Flush List 三者关系

    8. Checkpoint 技术

    1) 缩短数据库恢复时间。

    redo log中记录了Checkpoint的位置。
    这个点之前的页已经被刷新回磁盘,只需要对Checkpoint之后的redo log进行恢复。
    

    2) 缓存池不够用时,刷新脏页。

    根据LRU算法,溢出最近最少使用页。
    如果页为脏页,强制执行Checkpoint,将脏页刷新回磁盘。
    

    3) Redo log不可用时,刷新脏页。

    由于redo log是循环使用的,这部分对应的数据还未刷新到磁盘。
    数据库恢复时,如果不需要这部分日志即可被覆盖。
    如果需要,必须强制执行Checkpoint,将缓存池中的页至少刷新到当前重做日志的位置。
    

    InnoDB存储引擎内部,有两种Checkpoint

    Sharp Checkpoint(默认, innodb_fast_shutdown=1)。

    Sharp Checkpoint发生在数据库关闭时,将所有的脏页都刷新回磁盘。
    缺点:不适用于数据库运行时的刷新。
    

    Fuzzy Checkpoint。

    Fuzzy Checkpoint适用于数据库运行时刷新脏页,只刷新一部分脏页。
    MasterThread Checkpoint
    异步刷新,每秒或每10秒从缓存池脏页列表刷新一定比例的页回磁盘。
    
    FLUSH_LRU_LIST Checkpoint
    若Buffer Pool中没有足够的空间时,根据LRU算法、溢出LRU列表尾端的页。
    如果这些页有脏页,需要进行Checkpoint(Page Cleaner Thread线程就是做这个事的)。
    InnoDB存储引擎需要保证LRU列表中差不多有100个空闲页可供使用。
    Innodb_lru_scan_dept :控制LRU列表中可用页的数量,默认1024。
    
    Asnc / Sync Flush Checkpoint
    指重做日志不可用时,需要强制刷新页回磁盘。
    此时的页是脏页列表(FLUSH LIST)中选取的。
    

    LSN

    事务日志中每条记录的编号。
    InnoDB存储引擎,通过LSN(Log Sequence Number)来标记版本,LSN是8字节的数字。
    
    redo_lsn :写入日志的 LSN。
    Checkpoint_lsn :刷新回磁盘的最新页 LSN。
    
    Checkpoint_age = redo_lsn – checkpoint_lsn。
    Async_water_mark = 75% * total_redo_file_size。
    Sync_water_mark = 90% * total_redo_file_size。
    

    Dirty Page too much Checkpoint

    即脏页太多,强制checkpoint,保证缓存池中有足够可用的页。
    参数设置:innodb_max_dirty_pages_pct = 75。
    表示:当缓存池中脏页的数量占75%时,强制checkpoint。1.0x之后默认75。

    C.InnoDB关键特性

    1. 插入缓存(Insert Buffer)

    Insert Buffer的设计,对于非聚集索引的插入和更新操作,不是每次都直接插入到索引页中。
    而是先判断插入非聚集索引页是否在缓存池中。
    若存在则直接插入,若不存在则先放入一个Insert Buffer对象中。
    
    数据库这个非聚集的索引并没有插入到叶子结点(因为B+树只有叶子结点才存储数据),而是存放在另一个位置。
    然后再以一定的频率和情况进行Insert Buffer和辅助索引页子结点的merge(合并)操作。
    这时通常能将多个插入合并到一个操作中(因为在一个索引页中),这就大大提高了对于非聚集索引插入的性能。
    

    使用Insert Buffer需要满足两个条件

    1) 索引是辅助索引。
    2) 索引不是唯一的。
    

    2. 两次写操作

    假设有这样一个场景,当数据库正在从内存向磁盘写一个数据页时,数据库宕机。
    从而导致这个页只写了部分数据,这就是部分写失效,它会导致数据丢失。
    这时是无法通过重做日志(redo log)恢复的。
    因为重做日志记录是对页的物理修改,如果页本身已损坏,重做日志也无能为力。
    
    如何解决以上问题 ?
    为了解决以上问题,可以使用两次写操作。
    因为在磁盘共享表空间中已有数据页副本拷贝,如果数据库在页写入数据文件的过程中宕机。
    在实例恢复时,可以从共享表空间中找到该页副本,将其拷贝覆盖原有的数据页,再应用重做日志即可。
    
    两次写原理。
    1) 当刷新缓存池脏页时,并不直接写到数据文件中,而是先拷贝至内存中的两次写缓存区。
    2) 接着从两次写缓存区分两次写入磁盘共享表空间中,每次写入1MB。
    3) 待第2步完成后,再将两次写缓存区写入数据文件。
    
    两次写需要额外添加两个部分。
    1) 内存中的两次写缓存(doublewrite buffer),大小为2MB。
    2) 磁盘上共享表空间中连续的128页,大小也为2MB。
    
    InnoDB默认开启两次写功能,可以通过skip_innodb_doublewrite禁用两次写功能。

     

    展开全文
  • 数据库】【底层原理数据库的最简单实现 数据以文本形式保存 第一步,就是将所要保存的数据,写入文本文件。这个文本文件就是你的数据库。 为了方便读取,数据必须分成记录,每一条记录的长度规定为等长。...

    【数据库】【底层原理】数据库的最简单实现

    数据以文本形式保存

    第一步,就是将所要保存的数据,写入文本文件。这个文本文件就是你的数据库。

    为了方便读取,数据必须分成记录,每一条记录的长度规定为等长。比如,假定每条记录的长度是800字节,那么第5条记录的开始位置就在3200字节。

    大多数时候,我们不知道某一条记录在第几个位置,只知道主键(primary key)的值。这时为了读取数据,可以一条条比对记录。但是这样做效率太低,实际应用中,数据库往往采用B树(B-tree)格式储存数据。

    什么是B树

    要理解B树,必须从二叉查找树(Binary search tree)讲起。

    在这里插入图片描述

    二叉查找树是一种查找效率非常高的数据结构,它有三个特点。

    (1)每个节点最多只有两个子树。

    (2)左子树都为小于父节点的值,右子树都为大于父节点的值。

    (3)在n个节点中找到目标值,一般只需要log(n)次比较。

    二叉查找树的结构不适合数据库,因为它的查找效率与层数相关。越处在下层的数据,就需要越多次比较。极端情况下,n个数据需要n次比较才能找到目标值。对于数据库来说,每进入一层,就要从硬盘读取一次数据,这非常致命,因为硬盘的读取时间远远大于数据处理时间,数据库读取硬盘的次数越少越好。

    B树是对二叉查找树的改进。它的设计思想是,将相关数据尽量集中在一起,以便一次读取多个数据,减少硬盘操作次数。

    在这里插入图片描述

    B树的特点也有三个。

    (1)一个节点可以容纳多个值。比如上图中,最多的一个节点容纳了4个值。

    (2)除非数据已经填满,否则不会增加新的层。也就是说,B树追求"层"越少越好。

    (3)子节点中的值,与父节点中的值,有严格的大小对应关系。一般来说,如果父节点有a个值,那么就有a+1个子节点。比如上图中,父节点有两个值(7和16),就对应三个子节点,第一个子节点都是小于7的值,最后一个子节点都是大于16的值,中间的子节点就是7和16之间的值。

    这种数据结构,非常有利于减少读取硬盘的次数。假定一个节点可以容纳100个值,那么3层的B树可以容纳100万个数据,如果换成二叉查找树,则需要20层!假定操作系统一次读取一个节点,并且根节点保留在内存中,那么B树在100万个数据中查找目标值,只需要读取两次硬盘。

    索 引

    数据库以B树格式储存,只解决了按照"主键"查找数据的问题。如果想查找其他字段,就需要建立索引(index)。

    所谓索引,就是以某个字段为关键字的B树文件。假定有一张"雇员表",包含了员工号(主键)和姓名两个字段。可以对姓名建立索引文件,该文件以B树格式对姓名进行储存,每个姓名后面是其在数据库中的位置(即第几条记录)。查找姓名的时候,先从索引中找到对应第几条记录,然后再从表格中读取。

    这种索引查找方法,叫做"索引顺序存取方法"(Indexed Sequential Access Method),缩写为ISAM。它已经有多种实现(比如C-ISAM库和D-ISAM库),只要使用这些代码库,就能自己写一个最简单的数据库。

    高级功能

    部署了最基本的数据存取(包括索引)以后,还可以实现一些高级功能。

    1:SQL语言是数据库通用操作语言,所以需要一个SQL解析器,将SQL命令解析为对应的ISAM操作。

    2:数据库连接(join)是指数据库的两张表通过"外键",建立连接关系。你需要对这种操作进行优化。

    3:数据库事务(transaction)是指批量进行一系列数据库操作,只要有一步不成功,整个操作都不成功。所以需要有一个"操作日志",以便失败时对操作进行回滚。

    4:备份机制:保存数据库的副本。

    5:远程操作:使得用户可以在不同的机器上,通过TCP/IP协议操作数据库。

    展开全文
  • 数据库底层原理-------数据结构

    万次阅读 多人点赞 2018-05-05 14:13:24
    你可以自己谷歌/百度一下『关系型数据库原理』,看看结果多么的稀少【译者注:百度为您找到相关结果约1,850,000个…】 ,而且找到的那些文章都很短。现在如果你查找最近时髦的技术(大数据、NoSQL或JavaScript...

    一提到关系型数据库,我禁不住想:有些东西被忽视了。关系型数据库无处不在,而且种类繁多,从小巧实用的 SQLite 到强大的 Teradata 。但很少有文章讲解数据库是如何工作的。你可以自己谷歌/百度一下『关系型数据库原理』,看看结果多么的稀少【译者注:百度为您找到相关结果约1,850,000个…】 ,而且找到的那些文章都很短。现在如果你查找最近时髦的技术(大数据、NoSQL或JavaScript),你能找到更多深入探讨它们如何工作的文章。

    难道关系型数据库已经太古老太无趣,除了大学教材、研究文献和书籍以外,没人愿意讲了吗?

    作为一个开发人员,我不喜欢用我不明白的东西。而且,数据库已经使用了40年之久,一定有理由的。多年以来,我花了成百上千个小时来真正领会这些我每天都在用的、古怪的黑盒子。关系型数据库非常有趣,因为它们是基于实用而且可复用的概念。如果你对了解一个数据库感兴趣,但是从未有时间或意愿来刻苦钻研这个内容广泛的课题,你应该喜欢这篇文章。

    虽然本文标题很明确,但我的目的并不是讲如何使用数据库。因此,你应该已经掌握怎么写一个简单的 join query(联接查询)和CRUD操作(创建读取更新删除),否则你可能无法理解本文。这是唯一需要你了解的,其他的由我来讲解。

    我会从一些计算机科学方面的知识谈起,比如时间复杂度。我知道有些人讨厌这个概念,但是没有它你就不能理解数据库内部的巧妙之处。由于这是个很大的话题,我将集中探讨我认为必要的内容:数据库处理SQL查询的方式。我仅仅介绍数据库背后的基本概念,以便在读完本文后你会对底层到底发生了什么有个很好的了解

    【译者注:关于时间复杂度。计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。如果不了解这个概念建议先看看维基百度百科,对于理解文章下面的内容很有帮助】

    由于本文是个长篇技术文章,涉及到很多算法和数据结构知识,你尽可以慢慢读。有些概念比较难懂,你可以跳过,不影响理解整体内容。

    这篇文章大约分为3个部分:

    • 底层和上层数据库组件概况
    • 查询优化过程概况
    • 事务和缓冲池管理概况

    回到基础

    很久很久以前(在一个遥远而又遥远的星系……),开发者必须确切地知道他们的代码需要多少次运算。他们把算法和数据结构牢记于心,因为他们的计算机运行缓慢,无法承受对CPU和内存的浪费。

    在这一部分,我将提醒大家一些这类的概念,因为它们对理解数据库至关重要。我还会介绍数据库索引的概念。

    O(1) vs O(n^2)

    现今很多开发者不关心时间复杂度……他们是对的。

    但是当你应对大量的数据(我说的可不只是成千上万哈)或者你要争取毫秒级操作,那么理解这个概念就很关键了。而且你猜怎么着,数据库要同时处理这两种情景!我不会占用你太长时间,只要你能明白这一点就够了。这个概念在下文会帮助我们理解什么是基于成本的优化

    概念

    时间复杂度用来检验某个算法处理一定量的数据要花多长时间。为了描述这个复杂度,计算机科学家使用数学上的『简明解释算法中的大O符号』。这个表示法用一个函数来描述算法处理给定的数据需要多少次运算。

    比如,当我说『这个算法是适用 O(某函数())』,我的意思是对于某些数据,这个算法需要 某函数(数据量) 次运算来完成。

    重要的不是数据量,而是当数据量增加时运算如何增加。时间复杂度不会给出确切的运算次数,但是给出的是一种理念。

    图中可以看到不同类型的复杂度的演变过程,我用了对数尺来建这个图。具体点儿说,数据量以很快的速度从1条增长到10亿条。我们可得到如下结论:

    • 绿:O(1)或者叫常数阶复杂度,保持为常数(要不人家就不会叫常数阶复杂度了)。
    • 红:O(log(n))对数阶复杂度,即使在十亿级数据量时也很低。
    • 粉:最糟糕的复杂度是 O(n^2),平方阶复杂度,运算数快速膨胀。
    • 黑和蓝:另外两种复杂度(的运算数也是)快速增长。

    例子

    数据量低时,O(1) 和 O(n^2)的区别可以忽略不计。比如,你有个算法要处理2000条元素。

    • O(1) 算法会消耗 1 次运算
    • O(log(n)) 算法会消耗 7 次运算
    • O(n) 算法会消耗 2000 次运算
    • O(n*log(n)) 算法会消耗 14,000 次运算
    • O(n^2) 算法会消耗 4,000,000 次运算

    O(1) 和 O(n^2) 的区别似乎很大(4百万),但你最多损失 2 毫秒,只是一眨眼的功夫。确实,当今处理器每秒可处理上亿次的运算。这就是为什么性能和优化在很多IT项目中不是问题。

    我说过,面临海量数据的时候,了解这个概念依然很重要。如果这一次算法需要处理 1,000,000 条元素(这对数据库来说也不算大)。

    • O(1) 算法会消耗 1 次运算
    • O(log(n)) 算法会消耗 14 次运算
    • O(n) 算法会消耗 1,000,000 次运算
    • O(n*log(n)) 算法会消耗 14,000,000 次运算
    • O(n^2) 算法会消耗 1,000,000,000,000 次运算

    我没有具体算过,但我要说,用O(n^2) 算法的话你有时间喝杯咖啡(甚至再续一杯!)。如果在数据量后面加个0,那你就可以去睡大觉了。

    继续深入

    为了让你能明白

    • 搜索一个好的哈希表会得到 O(1) 复杂度
      • 搜索一个均衡的树会得到 O(log(n)) 复杂度
      • 搜索一个阵列会得到 O(n) 复杂度
      • 最好的排序算法具有 O(n*log(n)) 复杂度
      • 糟糕的排序算法具有 O(n^2) 复杂度

    注:在接下来的部分,我们将会研究这些算法和数据结构。

    有多种类型的时间复杂度

    • 一般情况场景
    • 最佳情况场景
    • 最差情况场景

    时间复杂度经常处于最差情况场景。

    这里我只探讨时间复杂度,但复杂度还包括:

    • 算法的内存消耗
    • 算法的磁盘 I/O 消耗

    当然还有比 n^2 更糟糕的复杂度,比如:

    • n^4:差劲!我将要提到的一些算法具备这种复杂度。
    • 3^n:更差劲!本文中间部分研究的一些算法中有一个具备这种复杂度(而且在很多数据库中还真的使用了)。
    • 阶乘 n:你永远得不到结果,即便在少量数据的情况下。
    • n^n:如果你发展到这种复杂度了,那你应该问问自己IT是不是你的菜。

    注:我并没有给出『大O表示法』的真正定义,只是利用这个概念。可以看看维基百科上的这篇文章

    合并排序

    当你要对一个集合排序时你怎么做?什么?调用 sort() 函数……好吧,算你对了……但是对于数据库,你需要理解这个 sort() 函数的工作原理。

    优秀的排序算法有好几个,我侧重于最重要的一种:合并排序。你现在可能还不了解数据排序有什么用,但看完查询优化部分后你就会知道了。再者,合并排序有助于我们以后理解数据库常见的联接操作,即合并联接

    合并

    与很多有用的算法类似,合并排序基于这样一个技巧:将 2 个大小为 N/2 的已排序序列合并为一个 N 元素已排序序列仅需要 N 次操作。这个方法叫做合并

    我们用个简单的例子来看看这是什么意思:

    通过此图你可以看到,在 2 个 4元素序列里你只需要迭代一次,就能构建最终的8元素已排序序列,因为两个4元素序列已经排好序了:

    • 1) 在两个序列中,比较当前元素(当前=头一次出现的第一个)
    • 2) 然后取出最小的元素放进8元素序列中
    • 3) 找到(两个)序列的下一个元素,(比较后)取出最小的
    • 重复1、2、3步骤,直到其中一个序列中的最后一个元素
    • 然后取出另一个序列剩余的元素放入8元素序列中。

    这个方法之所以有效,是因为两个4元素序列都已经排好序,你不需要再『回到』序列中查找比较。

    【译者注:合并排序详细原理,其中一个动图(原图较长,我做了删减)清晰的演示了上述合并排序的过程,而原文的叙述似乎没有这么清晰,不动戳大。】

    既然我们明白了这个技巧,下面就是我的合并排序伪代码。

    合并排序是把问题拆分为小问题,通过解决小问题来解决最初的问题(注:这种算法叫分治法,即『分而治之、各个击破』)。如果你不懂,不用担心,我第一次接触时也不懂。如果能帮助你理解的话,我认为这个算法是个两步算法:

    • 拆分阶段,将序列分为更小的序列
    • 排序阶段,把小的序列合在一起(使用合并算法)来构成更大的序列

    拆分阶段

    在拆分阶段过程中,使用3个步骤将序列分为一元序列。步骤数量的值是 log(N) (因为 N=8, log(N)=3)。【译者注:底数为2,下文有说明】

    我怎么知道这个的?

    我是天才!一句话:数学。道理是每一步都把原序列的长度除以2,步骤数就是你能把原序列长度除以2的次数。这正好是对数的定义(在底数为2时)。

    排序阶段

    在排序阶段,你从一元序列开始。在每一个步骤中,你应用多次合并操作,成本一共是 N=8 次运算。

    • 第一步,4 次合并,每次成本是 2 次运算。
    • 第二步,2 次合并,每次成本是 4 次运算。
    • 第三步,1 次合并,成本是 8 次运算。

    因为有 log(N) 个步骤,整体成本是 N*log(N) 次运算

    【译者注:这个完整的动图演示了拆分和排序的全过程,不动戳大。】

    合并排序的强大之处

    为什么这个算法如此强大?

    因为:

    • 你可以更改算法,以便于节省内存空间,方法是不创建新的序列而是直接修改输入序列。

    注:这种算法叫『原地算法』(in-place algorithm)

    • 你可以更改算法,以便于同时使用磁盘空间和少量内存而避免巨量磁盘 I/O。方法是只向内存中加载当前处理的部分。在仅仅100MB的内存缓冲区内排序一个几个GB的表时,这是个很重要的技巧。

    注:这种算法叫『外部排序』(external sorting)。

    • 你可以更改算法,以便于在 多处理器/多线程/多服务器 上运行。

    比如,分布式合并排序是Hadoop(那个著名的大数据框架)的关键组件之一。

    • 这个算法可以点石成金(事实如此!)

    这个排序算法在大多数(如果不是全部的话)数据库中使用,但是它并不是唯一算法。如果你想多了解一些,你可以看看 这篇论文,探讨的是数据库中常用排序算法的优势和劣势。

    阵列,树和哈希表

    既然我们已经了解了时间复杂度和排序背后的理念,我必须要向你介绍3种数据结构了。这个很重要,因为它们是现代数据库的支柱。我还会介绍数据库索引的概念。

    阵列

    二维阵列是最简单的数据结构。一个表可以看作是个阵列,比如:

    这个二维阵列是带有行与列的表:

    • 每个行代表一个主体
    • 列用来描述主体的特征
    • 每个列保存某一种类型对数据(整数、字符串、日期……)

    虽然用这个方法保存和视觉化数据很棒,但是当你要查找特定的值它就很糟糕了。 举个例子,如果你要找到所有在 UK 工作的人,你必须查看每一行以判断该行是否属于 UK 。这会造成 N 次运算的成本(N 等于行数),还不赖嘛,但是有没有更快的方法呢?这时候树就可以登场了(或开始起作用了)。

    树和数据库索引

    二叉查找树是带有特殊属性的二叉树,每个节点的关键字必须:

    • 比保存在左子树的任何键值都要大
    • 比保存在右子树的任何键值都要小

    【译者注:binary search tree,二叉查找树/二叉搜索树,或称 Binary Sort Tree 二叉排序树。见百度百科

    概念

    BST-624x321

    这个树有 N=15 个元素。比方说我要找208:

    • 我从键值为 136 的根开始,因为 136<208,我去找节点136的右子树。
    • 398>208,所以我去找节点398的左子树
    • 250>208,所以我去找节点250的左子树
    • 200<208,所以我去找节点200的右子树。但是 200 没有右子树,值不存在(因为如果存在,它会在 200 的右子树)

    现在比方说我要找40

    • 我从键值为136的根开始,因为 136>40,所以我去找节点136的左子树。
    • 80>40,所以我去找节点 80 的左子树
    • 40=40,节点存在。我抽取出节点内部行的ID(图中没有画)再去表中查找对应的 ROW ID。
    • 知道 ROW ID我就知道了数据在表中对精确位置,就可以立即获取数据。

    最后,两次查询的成本就是树内部的层数。如果你仔细阅读了合并排序的部分,你就应该明白一共有 log(N)层。所以这个查询的成本是 log(N),不错啊!

    回到我们的问题

    上文说的很抽象,我们回来看看我们的问题。这次不用傻傻的数字了,想象一下前表中代表某人的国家的字符串。假设你有个树包含表中的列『country』:

    • 如果你想知道谁在 UK 工作
    • 你在树中查找代表 UK 的节点
    • 在『UK 节点』你会找到 UK 员工那些行的位置

    这次搜索只需 log(N) 次运算,而如果你直接使用阵列则需要 N 次运算。你刚刚想象的就是一个数据库索引

    B+树索引

    查找一个特定值这个树挺好用,但是当你需要查找两个值之间的多个元素时,就会有麻烦了。你的成本将是 O(N),因为你必须查找树的每一个节点,以判断它是否处于那 2 个值之间(例如,对树使用中序遍历)。而且这个操作不是磁盘I/O有利的,因为你必须读取整个树。我们需要找到高效的范围查询方法。为了解决这个问题,现代数据库使用了一种修订版的树,叫做B+树。在一个B+树里:

    • 只有最底层的节点(叶子节点)才保存信息(相关表的行位置)
    • 其它节点只是在搜索中用来指引到正确节点的。

    【译者注:参考 B+树二叉树遍历    维基百科

    database_index

    你可以看到,节点更多了(多了两倍)。确实,你有了额外的节点,它们就是帮助你找到正确节点的『决策节点』(正确节点保存着相关表中行的位置)。但是搜索复杂度还是在 O(log(N))(只多了一层)。一个重要的不同点是,最底层的节点是跟后续节点相连接的。

    用这个 B+树,假设你要找40到100间的值:

    • 你只需要找 40(若40不存在则找40之后最贴近的值),就像你在上一个树中所做的那样。
    • 然后用那些连接来收集40的后续节点,直到找到100。

    比方说你找到了 M 个后续节点,树总共有 N 个节点。对指定节点的搜索成本是 log(N),跟上一个树相同。但是当你找到这个节点,你得通过后续节点的连接得到 M 个后续节点,这需要 M 次运算。那么这次搜索只消耗了 M+log(N) 次运算,区别于上一个树所用的 N 次运算。此外,你不需要读取整个树(仅需要读 M+log(N) 个节点),这意味着更少的磁盘访问。如果 M 很小(比如 200 行)并且 N 很大(1,000,000),那结果就是天壤之别了。

    然而还有新的问题(又来了!)。如果你在数据库中增加或删除一行(从而在相关的 B+树索引里):

    • 你必须在B+树中的节点之间保持顺序,否则节点会变得一团糟,你无法从中找到想要的节点。
    • 你必须尽可能降低B+树的层数,否则 O(log(N)) 复杂度会变成 O(N)。

    换句话说,B+树需要自我整理和自我平衡。谢天谢地,我们有智能删除和插入。但是这样也带来了成本:在B+树中,插入和删除操作是 O(log(N)) 复杂度。所以有些人听到过使用太多索引不是个好主意这类说法。没错,你减慢了快速插入/更新/删除表中的一个行的操作,因为数据库需要以代价高昂的每索引 O(log(N)) 运算来更新表的索引。再者,增加索引意味着给事务管理器带来更多的工作负荷(在本文结尾我们会探讨这个管理器)。

    想了解更多细节,你可以看看 Wikipedia 上这篇关于B+树的文章。如果你想要数据库中实现B+树的例子,看看MySQL核心开发人员写的这篇文章这篇文章。两篇文章都致力于探讨 innoDB(MySQL引擎)如何处理索引。

    哈希表

    我们最后一个重要的数据结构是哈希表。当你想快速查找值时,哈希表是非常有用的。而且,理解哈希表会帮助我们接下来理解一个数据库常见的联接操作,叫做『哈希联接』。这个数据结构也被数据库用来保存一些内部的东西(比如锁表或者缓冲池,我们在下文会研究这两个概念)。

    哈希表这种数据结构可以用关键字来快速找到一个元素。为了构建一个哈希表,你需要定义:

    • 元素的关键字
      • 关键字的哈希函数。关键字计算出来的哈希值给出了元素的位置(叫做哈希桶)。
      • 关键字比较函数。一旦你找到正确的哈希桶,你必须用比较函数在桶内找到你要的元素。
    一个简单的例子

    我们来看一个形象化的例子:

    这个哈希表有10个哈希桶。因为我懒,我只给出5个桶,但是我知道你很聪明,所以我让你想象其它的5个桶。我用的哈希函数是关键字对10取模,也就是我只保留元素关键字的最后一位,用来查找它的哈希桶:

    • 如果元素最后一位是 0,则进入哈希桶0,
    • 如果元素最后一位是 1,则进入哈希桶1,
    • 如果元素最后一位是 2,则进入哈希桶2,
    • …我用的比较函数只是判断两个整数是否相等。

    【译者注:取模运算

    比方说你要找元素 78:

    • 哈希表计算 78 的哈希码,等于 8。
    • 查找哈希桶 8,找到的第一个元素是 78。
    • 返回元素 78。
    • 查询仅耗费了 2 次运算(1次计算哈希值,另一次在哈希桶中查找元素)。

    现在,比方说你要找元素 59:

    • 哈希表计算 59 的哈希码,等于9。
    • 查找哈希桶 9,第一个找到的元素是 99。因为 99 不等于 59, 那么 99 不是正确的元素。
    • 用同样的逻辑,查找第二个元素(9),第三个(79),……,最后一个(29)。
    • 元素不存在。
    • 搜索耗费了 7 次运算
    一个好的哈希函数

    你可以看到,根据你查找的值,成本并不相同。

    如果我把哈希函数改为关键字对 1,000,000 取模(就是说取后6位数字),第二次搜索只消耗一次运算,因为哈希桶 00059 里面没有元素。真正的挑战是找到好的哈希函数,让哈希桶里包含非常少的元素

    在我的例子里,找到一个好的哈希函数很容易,但这是个简单的例子。当关键字是下列形式时,好的哈希函数就更难找了:

    • 1 个字符串(比如一个人的姓)
    • 2 个字符串(比如一个人的姓和名)
    • 2 个字符串和一个日期(比如一个人的姓、名和出生年月日)

    如果有了好的哈希函数,在哈希表里搜索的时间复杂度是 O(1)。

    阵列 vs 哈希表

    为什么不用阵列呢?

    嗯,你问得好。

    • 一个哈希表可以只装载一半到内存,剩下的哈希桶可以留在硬盘上。
    • 用阵列的话,你需要一个连续内存空间。如果你加载一个大表,很难分配足够的连续内存空间
    • 用哈希表的话,你可以选择你要的关键字(比如,一个人的国家和姓氏)。

    想要更详细的信息,你可以阅读我在Java HashMap 上的文章,是关于高效哈希表实现的。你不需要了解Java就能理解文章里的概念。

    全局概览

    我们已经了解了数据库内部的基本组件,现在我们需要回来看看数据库的全貌了。

    数据库是一个易于访问和修改的信息集合。不过简单的一堆文件也能达到这个效果。事实上,像SQLite这样最简单的数据库也只是一堆文件而已,但SQLite是精心设计的一堆文件,因为它允许你:

    • 使用事务来确保数据的安全和一致性
    • 快速处理百万条以上的数据

    数据库一般可以用如下图形来理解:

    撰写这部分之前,我读过很多书/论文,它们都以自己的方式描述数据库。所以,我不会特别关注如何组织数据库或者如何命名各种进程,因为我选择了自己的方式来描述这些概念以适应本文。区别就是不同的组件,总体思路为:数据库是由多种互相交互的组件构成的

    核心组件

    • 进程管理器(process manager:很多数据库具备一个需要妥善管理的进程/线程池。再者,为了实现纳秒级操作,一些现代数据库使用自己的线程而不是操作系统线程。
    • 网络管理器(network manager:网路I/O是个大问题,尤其是对于分布式数据库。所以一些数据库具备自己的网络管理器。
    • 文件系统管理器(File system manager磁盘I/O是数据库的首要瓶颈。具备一个文件系统管理器来完美地处理OS文件系统甚至取代OS文件系统,是非常重要的。
    • 内存管理器(memory manager:为了避免磁盘I/O带来的性能损失,需要大量的内存。但是如果你要处理大容量内存你需要高效的内存管理器,尤其是你有很多查询同时使用内存的时候。
    • 安全管理器(Security Manager:用于对用户的验证和授权。
    • 客户端管理器(Client manager:用于管理客户端连接。
    • ……

    工具

    • 备份管理器(Backup manager:用于保存和恢复数据。
    • 复原管理器(Recovery manager:用于崩溃后重启数据库到一个一致状态
    • 监控管理器(Monitor manager:用于记录数据库活动信息和提供监控数据库的工具。
    • Administration管理器(Administration manager:用于保存元数据(比如表的名称和结构),提供管理数据库、模式、表空间的工具。【译者注:好吧,我真的不知道Administration manager该翻译成什么,有知道的麻烦告知,不胜感激……】
    • ……

    查询管理器

    • 查询解析器(Query parser):用于检查查询是否合法
    • 查询重写器(Query rewriter):用于预优化查询
    • 查询优化器(Query optimizer):用于优化查询
    • 查询执行器(Query executor):用于编译和执行查询

    数据管理器

    • 事务管理器(Transaction manager:用于处理事务
    • 缓存管理器Cache manager:数据被使用之前置于内存,或者数据写入磁盘之前置于内存
    • 数据访问管理器Data access manager:访问磁盘中的数据

    在本文剩余部分,我会集中探讨数据库如何通过如下进程管理SQL查询的:

    • 客户端管理器
    • 查询管理器
    • 数据管理器(含复原管理器)

    客户端管理器

    客户端管理器是处理客户端通信的。客户端可以是一个(网站)服务器或者一个最终用户或最终应用。客户端管理器通过一系列知名的API(JDBC, ODBC, OLE-DB …)提供不同的方式来访问数据库。

    客户端管理器也提供专有的数据库访问API。

    当你连接到数据库时:

    • 管理器首先检查你的验证信息(用户名和密码),然后检查你是否有访问数据库的授权。这些权限由DBA分配。
    • 然后,管理器检查是否有空闲进程(或线程)来处理你对查询。
    • 管理器还会检查数据库是否负载很重。
    • 管理器可能会等待一会儿来获取需要的资源。如果等待时间达到超时时间,它会关闭连接并给出一个可读的错误信息。
    • 然后管理器会把你的查询送给查询管理器来处理。
    • 因为查询处理进程不是『不全则无』的,一旦它从查询管理器得到数据,它会把部分结果保存到一个缓冲区并且开始给你发送
    • 如果遇到问题,管理器关闭连接,向你发送可读的解释信息,然后释放资源。

    查询管理器

    这部分是数据库的威力所在,在这部分里,一个写得糟糕的查询可以转换成一个快速执行的代码,代码执行的结果被送到客户端管理器。这个多步骤操作过程如下:

    • 查询首先被解析并判断是否合法
    • 然后被重写,去除了无用的操作并且加入预优化部分
    • 接着被优化以便提升性能,并被转换为可执行代码和数据访问计划。
    • 然后计划被编译
    • 最后,被执行

    这里我不会过多探讨最后两步,因为它们不太重要。

    看完这部分后,如果你需要更深入的知识,我建议你阅读:

    • 关于成本优化的初步研究论文(1979):关系型数据库系统存取路径选择。这个篇文章只有12页,而且具备计算机一般水平就能理解。
    • 非常好、非常深入的 DB2 9.X 如何优化查询的介绍
    • 非常好的PostgreSQL如何优化查询的介绍。这是一篇最通俗易懂的文档,因为它讲的是『我们来看看在这种情况下,PostgreSQL给出了什么样的查询计划』,而不是『我们来看看PostgreSQL用的什么算法』。
    • 官方SQLite优化文档。『易于』阅读,因为SQLite用的是简单规则。再者,这是唯一真正解释SQLite如何工作的官方文档。
    • 非常好的SQL Server 2005 如何优化查询的介绍
    • Oracle 12c 优化白皮书
    • 2篇查询优化的教程,第一篇 第二篇。教程来自《数据库系统概念》的作者,很好的读物,集中讨论磁盘I/O,但是要求具有很好的计算机科学水平。
    • 另一个原理教程,这篇教程我觉得更易懂,不过它仅关注联接运算符(join operators)和磁盘I/O。

    查询解析器

    每一条SQL语句都要送到解析器来检查语法,如果你的查询有错,解析器将拒绝该查询。比如,如果你写成”SLECT …” 而不是 “SELECT …”,那就没有下文了。

    但这还不算完,解析器还会检查关键字是否使用正确的顺序,比如 WHERE 写在 SELECT 之前会被拒绝。

    然后,解析器要分析查询中的表和字段,使用数据库元数据来检查:

    • 表是否存在
    • 表的字段是否存在
    • 对某类型字段的 运算 是否 可能(比如,你不能将整数和字符串进行比较,你不能对一个整数使用 substring() 函数)

    接着,解析器检查在查询中你是否有权限来读取(或写入)表。再强调一次:这些权限由DBA分配。

    在解析过程中,SQL 查询被转换为内部表示(通常是一个树)。

    如果一切正常,内部表示被送到查询重写器。

    查询重写器

    在这一步,我们已经有了查询的内部表示,重写器的目标是:

    • 预优化查询
    • 避免不必要的运算
    • 帮助优化器找到合理的最佳解决方案

    重写器按照一系列已知的规则对查询执行检测。如果查询匹配一种模式的规则,查询就会按照这条规则来重写。下面是(可选)规则的非详尽的列表:

    • 视图合并:如果你在查询中使用视图,视图就会转换为它的 SQL 代码。
    • 子查询扁平化:子查询是很难优化的,因此重写器会尝试移除子查询

    例如:

    会转换为:

    • 去除不必要的运算符:比如,如果你用了 DISTINCT,而其实你有 UNIQUE 约束(这本身就防止了数据出现重复),那么 DISTINCT 关键字就被去掉了。
    • 排除冗余的联接:如果相同的 JOIN 条件出现两次,比如隐藏在视图中的 JOIN 条件,或者由于传递性产生的无用 JOIN,都会被消除。
    • 常数计算赋值:如果你的查询需要计算,那么在重写过程中计算会执行一次。比如 WHERE AGE > 10+2 会转换为 WHERE AGE > 12 , TODATE(“日期字符串”) 会转换为 datetime 格式的日期值。
    • (高级)分区裁剪(Partition Pruning):如果你用了分区表,重写器能够找到需要使用的分区。
    • (高级)物化视图重写(Materialized view rewrite):如果你有个物化视图匹配查询谓词的一个子集,重写器将检查视图是否最新并修改查询,令查询使用物化视图而不是原始表。
    • (高级)自定义规则:如果你有自定义规则来修改查询(就像 Oracle policy),重写器就会执行这些规则。
    • (高级)OLAP转换:分析/加窗 函数,星形联接,ROLLUP 函数……都会发生转换(但我不确定这是由重写器还是优化器来完成,因为两个进程联系很紧,必须看是什么数据库)。

    【译者注: 物化视图  。谓词,predicate,条件表达式的求值返回真或假的过程】

    重写后的查询接着送到优化器,这时候好玩的就开始了。

    统计

    研究数据库如何优化查询之前我们需要谈谈统计,因为没有统计的数据库是愚蠢的。除非你明确指示,数据库是不会分析自己的数据的。没有分析会导致数据库做出(非常)糟糕的假设。

    但是,数据库需要什么类型的信息呢?

    我必须(简要地)谈谈数据库和操作系统如何保存数据。两者使用的最小单位叫做页或块(默认 4 或 8 KB)。这就是说如果你仅需要 1KB,也会占用一个页。要是页的大小为 8KB,你就浪费了 7KB。

    回来继续讲统计! 当你要求数据库收集统计信息,数据库会计算下列值:

    • 表中行和页的数量
    • 表中每个列中的:
      唯一值
      数据长度(最小,最大,平均)
      数据范围(最小,最大,平均)
    • 表的索引信息

    这些统计信息会帮助优化器估计查询所需的磁盘 I/O、CPU、和内存使用

    对每个列的统计非常重要。
    比如,如果一个表 PERSON 需要联接 2 个列: LAST_NAME, FIRST_NAME。
    根据统计信息,数据库知道FIRST_NAME只有 1,000 个不同的值,LAST_NAME 有 1,000,000 个不同的值。
    因此,数据库就会按照 LAST_NAME, FIRST_NAME 联接。
    因为 LAST_NAME 不大可能重复,多数情况下比较 LAST_NAME 的头 2 、 3 个字符就够了,这将大大减少比较的次数。

    不过,这些只是基本的统计。你可以让数据库做一种高级统计,叫直方图。直方图是列值分布情况的统计信息。例如:

    • 出现最频繁的值
    • 分位数 【译者注:http://baike.baidu.com/view/1323572.htm】

    这些额外的统计会帮助数据库找到更佳的查询计划,尤其是对于等式谓词(例如: WHERE AGE = 18 )或范围谓词(例如: WHERE AGE > 10 and AGE < 40),因为数据库可以更好的了解这些谓词相关的数字类型数据行(注:这个概念的技术名称叫选择率)。

    统计信息保存在数据库元数据内,例如(非分区)表的统计信息位置:

    • Oracle: USER / ALL / DBA_TABLES 和 USER / ALL / DBA_TAB_COLUMNS
    • DB2: SYSCAT.TABLES 和 SYSCAT.COLUMNS

    统计信息必须及时更新。如果一个表有 1,000,000 行而数据库认为它只有 500 行,没有比这更糟糕的了。统计唯一的不利之处是需要时间来计算,这就是为什么数据库大多默认情况下不会自动计算统计信息。数据达到百万级时统计会变得困难,这时候,你可以选择仅做基本统计或者在一个数据库样本上执行统计。

    举个例子,我参与的一个项目需要处理每表上亿条数据的库,我选择只统计10%,结果造成了巨大的时间消耗。本例证明这是个糟糕的决定,因为有时候 Oracle 10G 从特定表的特定列中选出的 10% 跟全部 100% 有很大不同(对于拥有一亿行数据的表,这种情况极少发生)。这次错误的统计导致了一个本应 30 秒完成的查询最后执行了 8 个小时,查找这个现象根源的过程简直是个噩梦。这个例子显示了统计的重要性。

    注:当然了,每个数据库还有其特定的更高级的统计。如果你想了解更多信息,读读数据库的文档。话虽然这么说,我已经尽力理解统计是如何使用的了,而且我找到的最好的官方文档来自PostgreSQL

    查询优化器

    所有的现代数据库都在用基于成本的优化(即CBO)来优化查询。道理是针对每个运算设置一个成本,通过应用成本最低廉的一系列运算,来找到最佳的降低查询成本的方法。

    为了理解成本优化器的原理,我觉得最好用个例子来『感受』一下这个任务背后的复杂性。这里我将给出联接 2 个表的 3 个方法,我们很快就能看到即便一个简单的联接查询对于优化器来说都是个噩梦。之后,我们会了解真正的优化器是怎么做的。

    对于这些联接操作,我会专注于它们的时间复杂度,但是,数据库优化器计算的是它们的 CPU 成本、磁盘 I/O 成本、和内存需求。时间复杂度和 CPU 成本的区别是,时间成本是个近似值(给我这样的懒家伙准备的)。而 CPU 成本,我这里包括了所有的运算,比如:加法、条件判断、乘法、迭代……还有呢:

    • 每一个高级代码运算都要特定数量的低级 CPU 运算。
    • 对于 Intel Core i7、Intel Pentium 4、AMD Opteron…等,(就 CPU 周期而言)CPU 的运算成本是不同的,也就是说它取决于 CPU 的架构。

    使用时间复杂度就容易多了(至少对我来说),用它我也能了解到 CBO 的概念。由于磁盘 I/O 是个重要的概念,我偶尔也会提到它。请牢记,大多数时候瓶颈在于磁盘 I/O 而不是 CPU 使用

    索引

    在研究 B+树的时候我们谈到了索引,要记住一点,索引都是已经排了序的

    仅供参考:还有其他类型的索引,比如位图索引,在 CPU、磁盘I/O、和内存方面与B+树索引的成本并不相同。

    另外,很多现代数据库为了改善执行计划的成本,可以仅为当前查询动态地生成临时索引

    存取路径

    在应用联接运算符(join operators)之前,你首先需要获得数据。以下就是获得数据的方法。

    注:由于所有存取路径的真正问题是磁盘 I/O,我不会过多探讨时间复杂度。

    【译者注:四种类型的Oracle索引扫描介绍  】

    全扫描

    如果你读过执行计划,一定看到过『全扫描』(或只是『扫描』)一词。简单的说全扫描就是数据库完整的读一个表或索引。就磁盘 I/O 而言,很明显全表扫描的成本比索引全扫描要高昂

    范围扫描

    其他类型的扫描有索引范围扫描,比如当你使用谓词 ” WHERE AGE > 20 AND AGE < 40 ” 的时候它就会发生。

    当然,你需要在 AGE 字段上有索引才能用到索引范围扫描。

    在第一部分我们已经知道,范围查询的时间成本大约是 log(N)+M,这里 N 是索引的数据量,M 是范围内估测的行数。多亏有了统计我们才能知道 N 和 M 的值(注: M 是谓词 “ AGE > 20 AND AGE < 40 ” 的选择率)。另外范围扫描时,你不需要读取整个索引,因此在磁盘 I/O 方面没有全扫描那么昂贵

    唯一扫描

    如果你只需要从索引中取一个值你可以用唯一扫描

    根据 ROW ID 存取

    多数情况下,如果数据库使用索引,它就必须查找与索引相关的行,这样就会用到根据 ROW ID 存取的方式。

    例如,假如你运行:

    如果 person 表的 age 列有索引,优化器会使用索引找到所有年龄为 28 的人,然后它会去表中读取相关的行,这是因为索引中只有 age 的信息而你要的是姓和名。

    但是,假如你换个做法:

    PERSON 表的索引会用来联接 TYPE_PERSON 表,但是 PERSON 表不会根据行ID 存取,因为你并没有要求这个表内的信息。

    虽然这个方法在少量存取时表现很好,这个运算的真正问题其实是磁盘 I/O。假如需要大量的根据行ID存取,数据库也许会选择全扫描。

    其它路径

    我没有列举所有的存取路径,如果你感兴趣可以读一读 Oracle文档。其它数据库里也许叫法不同但背后的概念是一样的。

    联接运算符

    那么,我们知道如何获取数据了,那现在就把它们联接起来!

    我要展现的是3个个常用联接运算符:合并联接(Merge join),哈希联接(Hash Join)和嵌套循环联接(Nested Loop Join)。但是在此之前,我需要引入新词汇了:内关系和外关系( inner relation and outer relation) 【译者注: “内关系和外关系” 这个说法来源不明,跟查询的“内联接(INNER JOIN)  、外联接(OUTER JOIN)  ” 不是一个概念 。只查到百度百科词条:关系数据库 里提到“每个表格(有时被称为一个关系)……” 。 其他参考链接 “Merge Join”   “Hash Join”   “Nested Loop Join” 】  。 一个关系可以是:

    • 一个表
    • 一个索引
    • 上一个运算的中间结果(比如上一个联接运算的结果)

    当你联接两个关系时,联接算法对两个关系的处理是不同的。在本文剩余部分,我将假定:

    • 外关系是左侧数据集
    • 内关系是右侧数据集

    比如, A JOIN B 是 A 和 B 的联接,这里 A 是外关系,B 是内关系。

    多数情况下, A JOIN B 的成本跟 B JOIN A 的成本是不同的

    在这一部分,我还将假定外关系有 N 个元素,内关系有 M 个元素。要记住,真实的优化器通过统计知道 N 和 M 的值。

    注:N 和 M 是关系的基数。【译者注: 基数

    嵌套循环联接

    嵌套循环联接是最简单的。

    道理如下:

    • 针对外关系的每一行
    • 查看内关系里的所有行来寻找匹配的行

    下面是伪代码:

    由于这是个双迭代,时间复杂度是 O(N*M)。

    在磁盘 I/O 方面, 针对 N 行外关系的每一行,内部循环需要从内关系读取 M 行。这个算法需要从磁盘读取 N+ N*M 行。但是,如果内关系足够小,你可以把它读入内存,那么就只剩下 M + N 次读取。这样修改之后,内关系必须是最小的,因为它有更大机会装入内存。

    在CPU成本方面没有什么区别,但是在磁盘 I/O 方面,最好最好的,是每个关系只读取一次。

    当然,内关系可以由索引代替,对磁盘 I/O 更有利。

    由于这个算法非常简单,下面这个版本在内关系太大无法装入内存时,对磁盘 I/O 更加有利。道理如下:

    • 为了避免逐行读取两个关系,
    • 你可以成簇读取,把(两个关系里读到的)两簇数据行保存在内存里,
    • 比较两簇数据,保留匹配的,
    • 然后从磁盘加载新的数据簇来继续比较
    • 直到加载了所有数据。

    可能的算法如下:

    使用这个版本,时间复杂度没有变化,但是磁盘访问降低了:

    • 用前一个版本,算法需要 N + N*M 次访问(每次访问读取一行)。
    • 用新版本,磁盘访问变为 外关系的数据簇数量 + 外关系的数据簇数量 * 内关系的数据簇数量
    • 增加数据簇的尺寸,可以降低磁盘访问。
    哈希联接

    哈希联接更复杂,不过在很多场合比嵌套循环联接成本低。

    哈希联接的道理是:

    • 1) 读取内关系的所有元素
    • 2) 在内存里建一个哈希表
    • 3) 逐条读取外关系的所有元素
    • 4) (用哈希表的哈希函数)计算每个元素的哈希值,来查找内关系里相关的哈希桶内
    • 5) 是否与外关系的元素匹配。

    在时间复杂度方面我需要做些假设来简化问题:

    • 内关系被划分成 X 个哈希桶
    • 哈希函数几乎均匀地分布每个关系内数据的哈希值,就是说哈希桶大小一致。
    • 外关系的元素与哈希桶内的所有元素的匹配,成本是哈希桶内元素的数量。

    时间复杂度是 (M/X) * N + 创建哈希表的成本(M) + 哈希函数的成本 * N 。
    如果哈希函数创建了足够小规模的哈希桶,那么复杂度就是 O(M+N)

    还有个哈希联接的版本,对内存有利但是对磁盘 I/O 不够有利。 这回是这样的:

    • 1) 计算内关系和外关系双方的哈希表
    • 2) 保存哈希表到磁盘
    • 3) 然后逐个哈希桶比较(其中一个读入内存,另一个逐行读取)。
    合并联接

    合并联接是唯一产生排序的联接算法。

    注:这个简化的合并联接不区分内表或外表;两个表扮演同样的角色。但是真实的实现方式是不同的,比如当处理重复值时。

    1.(可选)排序联接运算:两个输入源都按照联接关键字排序。

    2.合并联接运算:排序后的输入源合并到一起。

    排序

    我们已经谈到过合并排序,在这里合并排序是个很好的算法(但是并非最好的,如果内存足够用的话,还是哈希联接更好)。

    然而有时数据集已经排序了,比如:

    • 如果表内部就是有序的,比如联接条件里一个索引组织表 【译者注: index-organized table
    • 如果关系是联接条件里的一个索引
    • 如果联接应用在一个查询中已经排序的中间结果
    合并联接

    这部分与我们研究过的合并排序中的合并运算非常相似。不过这一次呢,我们不是从两个关系里挑选所有元素,而是只挑选相同的元素。道理如下:

    • 1) 在两个关系中,比较当前元素(当前=头一次出现的第一个)
    • 2) 如果相同,就把两个元素都放入结果,再比较两个关系里的下一个元素
    • 3) 如果不同,就去带有最小元素的关系里找下一个元素(因为下一个元素可能会匹配)
    • 4) 重复 1、2、3步骤直到其中一个关系的最后一个元素。

    因为两个关系都是已排序的,你不需要『回头去找』,所以这个方法是有效的。

    该算法是个简化版,因为它没有处理两个序列中相同数据出现多次的情况(即多重匹配)。真实版本『仅仅』针对本例就更加复杂,所以我才选择简化版。

    如果两个关系都已经排序,时间复杂度是 O(N+M)

    如果两个关系需要排序,时间复杂度是对两个关系排序的成本:O(N*Log(N) + M*Log(M))

    对于计算机极客,我给出下面这个可能的算法来处理多重匹配(注:对于这个算法我不保证100%正确):

    哪个算法最好?

    如果有最好的,就没必要弄那么多种类型了。这个问题很难,因为很多因素都要考虑,比如:

    • 空闲内存:没有足够的内存的话就跟强大的哈希联接拜拜吧(至少是完全内存中哈希联接)。
    • 两个数据集的大小。比如,如果一个大表联接一个很小的表,那么嵌套循环联接就比哈希联接快,因为后者有创建哈希的高昂成本;如果两个表都非常大,那么嵌套循环联接CPU成本就很高昂。
    • 是否有索引:有两个 B+树索引的话,聪明的选择似乎是合并联接。
    • 结果是否需要排序:即使你用到的是未排序的数据集,你也可能想用成本较高的合并联接(带排序的),因为最终得到排序的结果后,你可以把它和另一个合并联接串起来(或者也许因为查询用 ORDER BY/GROUP BY/DISTINCT 等操作符隐式或显式地要求一个排序结果)。
    • 关系是否已经排序:这时候合并联接是最好的候选项。
    • 联接的类型:是等值联接(比如 tableA.col1 = tableB.col2 )? 还是内联接外联接笛卡尔乘积?或者自联接?有些联接在特定环境下是无法工作的。
    • 数据的分布:如果联接条件的数据是倾斜的(比如根据姓氏来联接人,但是很多人同姓),用哈希联接将是个灾难,原因是哈希函数将产生分布极不均匀的哈希桶。
    • 如果你希望联接操作使用多线程或多进程

    想要更详细的信息,可以阅读DB2, ORACLESQL Server)的文档。

    简化的例子

    我们已经研究了 3 种类型的联接操作。

    现在,比如说我们要联接 5 个表,来获得一个人的全部信息。一个人可以有:

    • 多个手机号(MOBILES)
    • 多个邮箱(MAILS)
    • 多个地址(ADRESSES)
    • 多个银行账号(BANK_ACCOUNTS)

    换句话说,我们需要用下面的查询快速得到答案:

    作为一个查询优化器,我必须找到处理数据最好的方法。但有 2 个问题:

    • 每个联接使用那种类型?
      我有 3 种可选(哈希、合并、嵌套),同时可能用到 0, 1 或 2 个索引(不必说还有多种类型的索引)。
    • 按什么顺序执行联接?
      比如,下图显示了针对 4 个表仅仅 3 次联接,可能采用的执行计划:

    那么下面就是我可能采取的方法:

    • 1) 采取粗暴的方式
      用数据库统计,计算每种可能的执行计划的成本,保留最佳方案。但是,会有很多可能性。对于一个给定顺序的联接操作,每个联接有三种可能性:哈希、合并、嵌套,那么总共就有 3^4 种可能性。确定联接的顺序是个二叉树的排列问题,会有 (2*4)!/(4+1)! 种可能的顺序。对本例这个相当简化了的问题,我最后会得到 3^4*(2*4)!/(4+1)! 种可能。
      抛开专业术语,那相当于 27,216 种可能性。如果给合并联接加上使用 0,1 或 2 个 B+树索引,可能性就变成了 210,000种。我是不是告诉过你这个查询其实非常简单吗?
    • 2) 我大叫一声辞了这份工作
      很有诱惑力,但是这样一来,你不会的到查询结果,而我需要钱来付账单。
    • 3) 我只尝试几种执行计划,挑一个成本最低的。
      由于不是超人,我不能算出所有计划的成本。相反,我可以武断地从全部可能的计划中选择一个子集,计算它们的成本,把最佳的计划给你。
    • 4) 我用聪明的规则来降低可能性的数量
      有两种规则:
      我可以用『逻辑』规则,它能去除无用的可能性,但是无法过滤大量的可能性。比如: 『嵌套联接的内关系必须是最小的数据集』。
      我接受现实,不去找最佳方案,用更激进的规则来大大降低可能性的数量。比如:『如果一个关系很小,使用嵌套循环联接,绝不使用合并或哈希联接。』

    在这个简单的例子中,我最后得到很多可能性。但现实世界的查询还会有其他关系运算符,像 OUTER JOIN, CROSS JOIN, GROUP BY, ORDER BY, PROJECTION, UNION, INTERSECT, DISTINCT … 这意味着更多的可能性。

    那么,数据库是如何处理的呢?

    动态规划,贪婪算法和启发式算法

    关系型数据库会尝试我刚刚提到的多种方法,优化器真正的工作是在有限时间里找到一个好的解决方案。

    多数时候,优化器找到的不是最佳的方案,而是一个『不错』的

    对于小规模的查询,采取粗暴的方式是有可能的。但是为了让中等规模的查询也能采取粗暴的方式,我们有办法避免不必要的计算,这就是动态规划

    动态规划

    这几个字背后的理念是,很多执行计划是非常相似的。看看下图这几种计划:

    它们都有相同的子树(A JOIN B),所以,不必在每个计划中计算这个子树的成本,计算一次,保存结果,当再遇到这个子树时重用。用更正规的说法,我们面对的是个重叠问题。为了避免对部分结果的重复计算,我们使用记忆法。

    应用这一技术,我们不再有 (2*N)!/(N+1)! 的复杂度,而是“只有” 3^N。在之前 4 个JOIN 的例子里,这意味着将 336 次排序降为 81 次。如果是大一些的查询,比如 8 个 JOIN (其实也不是很大啦),就是将 57,657,600 次降为 6551 次。【译者注:这一小段漏掉了,感谢 nsos指出来。另外感谢 Clark Li 指出Dynamic Programing 应该翻译为动态规划。 】

    对于计算机极客,下面是我在先前给你的教程里找到的一个算法。我不提供解释,所以仅在你已经了解动态规划或者精通算法的情况下阅读(我提醒过你哦):

    针对大规模查询,你也可以用动态规划方法,但是要附加额外的规则(或者称为启发式算法)来减少可能性。

    • 如果我们仅分析一个特定类型的计划(例如左深树 left-deep tree,参考),我们得到 n*2^n 而不是 3^n。

    • 如果我们加上逻辑规则来避免一些模式的计划(像『如果一个表有针对指定谓词的索引,就不要对表尝试合并联接,要对索引』),就会在不给最佳方案造成过多伤害的前提下,减少可能性的数量。【译者注:原文应该是有两处笔误: as=has, to=too】
    • 如果我们在流程里增加规则(像『联接运算先于其他所有的关系运算』),也能减少大量的可能性。
    • ……
    贪婪算法

    但是,优化器面对一个非常大的查询,或者为了尽快找到答案(然而查询速度就快不起来了),会应用另一种算法,叫贪婪算法。

    原理是按照一个规则(或启发)以渐进的方式制定查询计划。在这个规则下,贪婪算法逐步寻找最佳算法,先处理一条JOIN,接着每一步按照同样规则加一条新的JOIN。

    我们来看个简单的例子。比如一个针对5张表(A,B,C,D,E)4次JOIN 的查询,为了简化我们把嵌套JOIN作为可能的联接方式,按照『使用最低成本的联接』规则。

    • 直接从 5 个表里选一个开始(比如 A)
    • 计算每一个与 A 的联接(A 作为内关系或外关系)
    • 发现 “A JOIN B” 成本最低
    • 计算每一个与 “A JOIN B” 的结果联接的成本(“A JOIN B” 作为内关系或外关系)
    • 发现 “(A JOIN B) JOIN C” 成本最低
    • 计算每一个与 “(A JOIN B) JOIN C” 的结果联接的成本 ……
    • 最后确定执行计划 “( ( (A JOIN B) JOIN C) JOIN D ) JOIN E )”

    因为我们是武断地从表 A 开始,我们可以把同样的算法用在 B,然后 C,然后 D, 然后 E。最后保留成本最低的执行计划。

    顺便说一句,这个算法有个名字,叫『最近邻居算法』。

    抛开细节不谈,只需一个良好的模型和一个 N*log(N) 复杂度的排序,问题就轻松解决了。这个算法的复杂度是 O(N*log(N)) ,对比一下完全动态规划的 O(3^N)。如果你有个20个联接的大型查询,这意味着 26 vs 3,486,784,401 ,天壤之别!

    这个算法的问题是,我们做的假设是:找到 2 个表的最佳联接方法,保留这个联接结果,再联接下一个表,就能得到最低的成本。但是:

    • 即使在 A, B, C 之间,A JOIN B 可得最低成本
    • (A JOIN C) JOIN B 也许比 (A JOIN B) JOIN C 更好。

    为了改善这一状况,你可以多次使用基于不同规则的贪婪算法,并保留最佳的执行计划。

    其他算法

    [ 如果你已经受够了算法话题,就直接跳到下一部分。这部分对文章余下的内容不重要。] 【译者注:我也很想把这段跳过去 -_- 】

    很多计算机科学研究者热衷于寻找最佳的执行计划,他们经常为特定问题或模式探寻更好的解决方案,比如:

    • 如果查询是星型联接(一种多联接查询),某些数据库使用一种特定的算法。
    • 如果查询是并行的,某些数据库使用一种特定的算法。 ……

    其他算法也在研究之中,就是为了替换在大型查询中的动态规划算法。贪婪算法属于一个叫做启发式算法的大家族,它根据一条规则(或启发),保存上一步找到的方法,『附加』到当前步骤来进一步搜寻解决方法。有些算法根据特定规则,一步步的应用规则但不总是保留上一步找到的最佳方法。它们统称启发式算法。

    比如,基因算法就是一种:

    • 一个方法代表一种可能的完整查询计划
    • 每一步保留了 P 个方法(即计划),而不是一个。
    • 0) P 个计划随机创建
    • 1) 成本最低的计划才会保留
    • 2) 这些最佳计划混合在一起产生 P 个新的计划
    • 3) 一些新的计划被随机改写
    • 4) 1,2,3步重复 T 次
    • 5) 然后在最后一次循环,从 P 个计划里得到最佳计划。

    循环次数越多,计划就越好。

    这是魔术?不,这是自然法则:适者生存!

    PostgreSQL 实现了基因算法,但我并没有发现它是不是默认使用这种算法的。

    数据库中还使用了其它启发式算法,像『模拟退火算法(Simulated Annealing)』、『交互式改良算法(Iterative Improvement)』、『双阶段优化算法(Two-Phase Optimization)』…..不过,我不知道这些算法当前是否在企业级数据库应用了,还是仅仅用在研究型数据库。

    如果想进一步了解,这篇研究文章介绍两个更多可能的算法《数据库查询优化中联接排序问题的算法综述》,你可以去阅读一下。

    真实的优化器

    [ 这段不重要,可以跳过 ]

    然而,所有上述罗里罗嗦的都非常理论化,我是个开发者而不是研究者,我喜欢具体的例子

    我们来看看 SQLite 优化器 是怎么工作的。这是个轻量化数据库,它使用一种简单优化器,基于带有附加规则的贪婪算法,来限制可能性的数量。

    • SQLite 在有 CROSS JOIN 操作符时从不给表重新排序
    • 使用嵌套联接
    • 外联接始终按顺序评估
    • ……
    • 3.8.0之前的版本使用『最近邻居』贪婪算法来搜寻最佳查询计划
      等等……我们见过这个算法!真是巧哈!
    • 从3.8.0版本(发布于2015年)开始,SQLite使用『N最近邻居』贪婪算法来搜寻最佳查询计划

    我们再看看另一个优化器是怎么工作的。IBM DB2 跟所有企业级数据库都类似,我讨论它是因为在切换到大数据之前,它是我最后真正使用的数据库。

    看过官方文档后,我们了解到 DB2 优化器可以让你使用 7 种级别的优化:

    • 对联接使用贪婪算法
    •     0 – 最小优化,使用索引扫描和嵌套循环联接,避免一些查询重写
      •     1 – 低级优化
      •     2 – 完全优化
    • 对联接使用动态规划算法
    •     3 – 中等优化和粗略的近似法
      •     5 – 完全优化,使用带有启发式的所有技术
      •     7 – 完全优化,类似级别5,但不用启发式
      •     9 – 最大优化,完全不顾开销,考虑所有可能的联接顺序,包括笛卡尔乘积

    可以看到 DB2 使用贪婪算法和动态规划算法。当然,他们不会把自己的启发算法分享出来的,因为查询优化器是数据库的看家本领。

    DB2 的默认级别是 5,优化器使用下列特性: 【译者注:以下出现的一些概念我没有做考证,因为[ 这段不重要,可以跳过 ]】

    • 使用所有可用的统计,包括线段树(frequent-value)和分位数统计(quantile statistics)。
    • 使用所有查询重写规则(含物化查询表路由,materialized query table routing),除了在极少情况下适用的计算密集型规则。
    • 使用动态规划模拟联接
    •     有限使用组合内关系(composite inner relation)
    •     对于涉及查找表的星型模式,有限使用笛卡尔乘积
    • 考虑宽泛的访问方式,含列表预取(list prefetch,注:我们将讨论什么是列表预取),index ANDing(注:一种对索引的特殊操作),和物化查询表路由。

    默认的,DB2 对联接排列使用受启发式限制的动态规划算法

    其它情况 (GROUP BY, DISTINCT…) 由简单规则处理。

    查询计划缓存

    由于创建查询计划是耗时的,大多数据库把计划保存在查询计划缓存,来避免重复计算。这个话题比较大,因为数据库需要知道什么时候更新过时的计划。办法是设置一个上限,如果一个表的统计变化超过了上限,关于该表的查询计划就从缓存中清除。

    查询执行器

    在这个阶段,我们有了一个优化的执行计划,再编译为可执行代码。然后,如果有足够资源(内存,CPU),查询执行器就会执行它。计划中的操作符 (JOIN, SORT BY …) 可以顺序或并行执行,这取决于执行器。为了获得和写入数据,查询执行器与数据管理器交互,本文下一部分来讨论数据管理器。

    数据管理器

    在这一步,查询管理器执行了查询,需要从表和索引获取数据,于是向数据管理器提出请求。但是有 2 个问题:

    • 关系型数据库使用事务模型,所以,当其他人在同一时刻使用或修改数据时,你无法得到这部分数据。
    • 数据提取是数据库中速度最慢的操作,所以数据管理器需要足够聪明地获得数据并保存在内存缓冲区内。

    在这一部分,我没看看关系型数据库是如何处理这两个问题的。我不会讲数据管理器是怎么获得数据的,因为这不是最重要的(而且本文已经够长的了!)。

    缓存管理器

    我已经说过,数据库的主要瓶颈是磁盘 I/O。为了提高性能,现代数据库使用缓存管理器。

    查询执行器不会直接从文件系统拿数据,而是向缓存管理器要。缓存管理器有一个内存缓存区,叫做缓冲池从内存读取数据显著地提升数据库性能。对此很难给出一个数量级,因为这取决于你需要的是哪种操作:

    • 顺序访问(比如:全扫描) vs 随机访问(比如:按照row id访问)
    • 读还是写

    以及数据库使用的磁盘类型:

    • 7.2k/10k/15k rpm的硬盘
    • SSD
    • RAID 1/5/…

    要我说,内存比磁盘要快100到10万倍

    然而,这导致了另一个问题(数据库总是这样…),缓存管理器需要在查询执行器使用数据之前得到数据,否则查询管理器不得不等待数据从缓慢的磁盘中读出来。

    预读

    这个问题叫预读。查询执行器知道它将需要什么数据,因为它了解整个查询流,而且通过统计也了解磁盘上的数据。道理是这样的:

    • 当查询执行器处理它的第一批数据时
    • 会告诉缓存管理器预先装载第二批数据
    • 当开始处理第二批数据时
    • 告诉缓存管理器预先装载第三批数据,并且告诉缓存管理器第一批可以从缓存里清掉了。
    • ……

    缓存管理器在缓冲池里保存所有的这些数据。为了确定一条数据是否有用,缓存管理器给缓存的数据添加了额外的信息(叫闩锁)。

    有时查询执行器不知道它需要什么数据,有的数据库也不提供这个功能。相反,它们使用一种推测预读法(比如:如果查询执行器想要数据1、3、5,它不久后很可能会要 7、9、11),或者顺序预读法(这时候缓存管理器只是读取一批数据后简单地从磁盘加载下一批连续数据)。

    为了监控预读的工作状况,现代数据库引入了一个度量叫缓冲/缓存命中率,用来显示请求的数据在缓存中找到而不是从磁盘读取的频率。

    注:糟糕的缓存命中率不总是意味着缓存工作状态不佳。更多信息请阅读Oracle文档

    缓冲只是容量有限的内存空间,因此,为了加载新的数据,它需要移除一些数据。加载和清除缓存需要一些磁盘和网络I/O的成本。如果你有个经常执行的查询,那么每次都把查询结果加载然后清除,效率就太低了。现代数据库用缓冲区置换策略来解决这个问题。

    缓冲区置换策略

    多数现代数据库(至少 SQL Server, MySQL, Oracle 和 DB2)使用 LRU 算法。

    LRU

    LRU代表最近最少使用(Least Recently Used)算法,背后的原理是:在缓存里保留的数据是最近使用的,所以更有可能再次使用。

    图解:

    为了更好的理解,我假设缓冲区里的数据没有被闩锁锁住(就是说是可以被移除的)。在这个简单的例子里,缓冲区可以保存 3 个元素:

    • 1:缓存管理器(简称CM)使用数据1,把它放入空的缓冲区
    • 2:CM使用数据4,把它放入半载的缓冲区
    • 3:CM使用数据3,把它放入半载的缓冲区
    • 4:CM使用数据9,缓冲区满了,所以数据1被清除,因为它是最后一个最近使用的,数据9加入到缓冲区
    • 5:CM使用数据4,数据4已经在缓冲区了,所以它再次成为第一个最近使用的
    • 6:CM使用数据1,缓冲区满了,所以数据9被清除,因为它是最后一个最近使用的,数据1加入到缓冲区
    • ……

    这个算法效果很好,但是有些限制。如果对一个大表执行全表扫描怎么办?换句话说,当表/索引的大小超出缓冲区会发生什么?使用这个算法会清除之前缓存内所有的数据,而且全扫描的数据很可能只使用一次。

    改进

    为了防止这个现象,有些数据库增加了特殊的规则,比如Oracle文档中的描述:

    『对非常大的表来说,数据库通常使用直接路径来读取,即直接加载区块[……],来避免填满缓冲区。对于中等大小的表,数据库可以使用直接读取或缓存读取。如果选择缓存读取,数据库把区块置于LRU的尾部,防止清空当前缓冲区。』

    还有一些可能,比如使用高级版本的LRU,叫做 LRU-K。例如,SQL Server 使用 LRU-2。

    这个算法的原理是把更多的历史记录考虑进来。简单LRU(也就是 LRU-1),只考虑最后一次使用的数据。LRU-K呢:

    • 考虑数据最后第K次使用的情况
    • 数据使用的次数加进了权重
    • 一批新数据加载进入缓存,旧的但是经常使用的数据不会被清除(因为权重更高)
    • 但是这个算法不会保留缓存中不再使用的数据
    • 所以数据如果不再使用,权重值随着时间推移而降低

    计算权重是需要成本的,所以SQL Server只是使用 K=2,这个值性能不错而且额外开销可以接受。

    关于LRU-K更深入的知识,可以阅读早期的研究论文(1993):数据库磁盘缓冲的LRU-K页面置换算法

    其他算法

    当然还有其他管理缓存的算法,比如:

    • 2Q(类LRU-K算法)
    • CLOCK(类LRU-K算法)
    • MRU(最新使用的算法,用LRU同样的逻辑但不同的规则)
    • LRFU(Least Recently and Frequently Used,最近最少使用最近最不常用
    • ……

    写缓冲区

    我只探讨了读缓存 —— 在使用之前预先加载数据。用来保存数据、成批刷入磁盘,而不是逐条写入数据从而造成很多单次磁盘访问。

    要记住,缓冲区保存的是(最小的数据单位)而不是行(逻辑上/人类习惯的观察数据的方式)。缓冲池内的页如果被修改了但还没有写入磁盘,就是脏页。有很多算法来决定写入脏页的最佳时机,但这个问题与事务的概念高度关联,下面我们就谈谈事务。

    事务管理器

    最后但同样重要的,是事务管理器,我们将看到这个进程是如何保证每个查询在自己的事务内执行的。但开始之前,我们需要理解ACID事务的概念。

    “I’m on acid”

    一个ACID事务是一个工作单元,它要保证4个属性:

    • 原子性Atomicity): 事务『要么全部完成,要么全部取消』,即使它持续运行10个小时。如果事务崩溃,状态回到事务之前(事务回滚)。
    • 隔离性Isolation): 如果2个事务 A 和 B 同时运行,事务 A 和 B 最终的结果是相同的,不管 A 是结束于 B 之前/之后/运行期间。
    • 持久性Durability): 一旦事务提交(也就是成功执行),不管发生什么(崩溃或者出错),数据要保存在数据库中。
    • 一致性Consistency): 只有合法的数据(依照关系约束和函数约束)能写入数据库,一致性与原子性和隔离性有关。

    在同一个事务内,你可以运行多个SQL查询来读取、创建、更新和删除数据。当两个事务使用相同的数据,麻烦就来了。经典的例子是从账户A到账户B的汇款。假设有2个事务:

    • 事务1(T1)从账户A取出100美元给账户B
    • 事务2(T2)从账户A取出50美元给账户B

    我们回来看看ACID属性:

    • 原子性确保不管 T1 期间发生什么(服务器崩溃、网络中断…),你不能出现账户A 取走了100美元但没有给账户B 的现象(这就是数据不一致状态)。
    • 隔离性确保如果 T1 和 T2 同时发生,最终A将减少150美元,B将得到150美元,而不是其他结果,比如因为 T2 部分抹除了 T1 的行为,A减少150美元而B只得到50美元(这也是不一致状态)。
    • 持久性确保如果 T1 刚刚提交,数据库就发生崩溃,T1 不会消失得无影无踪。
    • 一致性确保钱不会在系统内生成或灭失。

    [以下部分不重要,可以跳过]

    现代数据库不会使用纯粹的隔离作为默认模式,因为它会带来巨大的性能消耗。SQL一般定义4个隔离级别:

    • 串行化(Serializable,SQLite默认模式):最高级别的隔离。两个同时发生的事务100%隔离,每个事务有自己的『世界』。
    • 可重复读(Repeatable read,MySQL默认模式):每个事务有自己的『世界』,除了一种情况。如果一个事务成功执行并且添加了新数据,这些数据对其他正在执行的事务是可见的。但是如果事务成功修改了一条数据,修改结果对正在运行的事务不可见。所以,事务之间只是在新数据方面突破了隔离,对已存在的数据仍旧隔离。
      举个例子,如果事务A运行”SELECT count(1) from TABLE_X” ,然后事务B在 TABLE_X 加入一条新数据并提交,当事务A再运行一次 count(1)结果不会是一样的。
      这叫幻读(phantom read)。
    • 读取已提交(Read committed,Oracle、PostgreSQL、SQL Server默认模式):可重复读+新的隔离突破。如果事务A读取了数据D,然后数据D被事务B修改(或删除)并提交,事务A再次读取数据D时数据的变化(或删除)是可见的。
      这叫不可重复读(non-repeatable read)。
    • 读取未提交(Read uncommitted):最低级别的隔离,是读取已提交+新的隔离突破。如果事务A读取了数据D,然后数据D被事务B修改(但并未提交,事务B仍在运行中),事务A再次读取数据D时,数据修改是可见的。如果事务B回滚,那么事务A第二次读取的数据D是无意义的,因为那是事务B所做的从未发生的修改(已经回滚了嘛)。
      这叫脏读(dirty read)。

    多数数据库添加了自定义的隔离级别(比如 PostgreSQL、Oracle、SQL Server的快照隔离),而且并没有实现SQL规范里的所有级别(尤其是读取未提交级别)。

    默认的隔离级别可以由用户/开发者在建立连接时覆盖(只需要增加很简单的一行代码)。

    并发控制

    确保隔离性、一致性和原子性的真正问题是对相同数据的写操作(增、更、删):

    • 如果所有事务只是读取数据,它们可以同时工作,不会更改另一个事务的行为。
    • 如果(至少)有一个事务在修改其他事务读取的数据,数据库需要找个办法对其它事务隐藏这种修改。而且,它还需要确保这个修改操作不会被另一个看不到这些数据修改的事务擦除。

    这个问题叫并发控制

    最简单的解决办法是依次执行每个事务(即顺序执行),但这样就完全没有伸缩性了,在一个多处理器/多核服务器上只有一个核心在工作,效率很低。

    理想的办法是,每次一个事务创建或取消时:

    • 监控所有事务的所有操作
    • 检查是否2个(或更多)事务的部分操作因为读取/修改相同的数据而存在冲突
    • 重新编排冲突事务中的操作来减少冲突的部分
    • 按照一定的顺序执行冲突的部分(同时非冲突事务仍然在并发运行)
    • 考虑事务有可能被取消

    用更正规的说法,这是对冲突的调度问题。更具体点儿说,这是个非常困难而且CPU开销很大的优化问题。企业级数据库无法承担等待几个小时,来寻找每个新事务活动最好的调度,因此就使用不那么理想的方式以避免更多的时间浪费在解决冲突上。

    锁管理器

    为了解决这个问题,多数数据库使用和/或数据版本控制。这是个很大的话题,我会集中探讨锁,和一点点数据版本控制。

    悲观锁

    原理是:

    • 如果一个事务需要一条数据
    • 它就把数据锁住
    • 如果另一个事务也需要这条数据
    • 它就必须要等第一个事务释放这条数据
      这个锁叫排他锁

    但是对一个仅仅读取数据的事务使用排他锁非常昂贵,因为这会迫使其它只需要读取相同数据的事务等待。因此就有了另一种锁,共享锁

    共享锁是这样的:

    • 如果一个事务只需要读取数据A
    • 它会给数据A加上『共享锁』并读取
    • 如果第二个事务也需要仅仅读取数据A
    • 它会给数据A加上『共享锁』并读取
    • 如果第三个事务需要修改数据A
    • 它会给数据A加上『排他锁』,但是必须等待另外两个事务释放它们的共享锁。

    同样的,如果一块数据被加上排他锁,一个只需要读取该数据的事务必须等待排他锁释放才能给该数据加上共享锁。

    锁管理器是添加和释放锁的进程,在内部用一个哈希表保存锁信息(关键字是被锁的数据),并且了解每一块数据是:

    • 被哪个事务加的锁
    • 哪个事务在等待数据解锁
    死锁

    但是使用锁会导致一种情况,2个事务永远在等待一块数据:

    在本图中:

    • 事务A 给 数据1 加上排他锁并且等待获取数据2
    • 事务B 给 数据2 加上排他锁并且等待获取数据1

    这叫死锁

    在死锁发生时,锁管理器要选择取消(回滚)一个事务,以便消除死锁。这可是个艰难的决定:

    • 杀死数据修改量最少的事务(这样能减少回滚的成本)?
    • 杀死持续时间最短的事务,因为其它事务的用户等的时间更长?
    • 杀死能用更少时间结束的事务(避免可能的资源饥荒)?
    • 一旦发生回滚,有多少事务会受到回滚的影响?

    在作出选择之前,锁管理器需要检查是否有死锁存在。

    哈希表可以看作是个图表(见上文图),图中出现循环就说明有死锁。由于检查循环是昂贵的(所有锁组成的图表是很庞大的),经常会通过简单的途径解决:使用超时设定。如果一个锁在超时时间内没有加上,那事务就进入死锁状态。

    锁管理器也可以在加锁之前检查该锁会不会变成死锁,但是想要完美的做到这一点还是很昂贵的。因此这些预检经常设置一些基本规则。

    两段锁

    实现纯粹的隔离最简单的方法是:事务开始时获取锁,结束时释放锁。就是说,事务开始前必须等待确保自己能加上所有的锁,当事务结束时释放自己持有的锁。这是行得通的,但是为了等待所有的锁,大量的时间被浪费了

    更快的方法是两段锁协议(Two-Phase Locking Protocol由 DB2 和 SQL Server使用),在这里,事务分为两个阶段:

    • 成长阶段:事务可以获得锁,但不能释放锁。
    • 收缩阶段:事务可以释放锁(对于已经处理完而且不会再次处理的数据),但不能获得新锁。

    这两条简单规则背后的原理是:

    • 释放不再使用的锁,来降低其它事务的等待时间
    • 防止发生这类情况:事务最初获得的数据,在事务开始后被修改,当事务重新读取该数据时发生不一致。

    这个规则可以很好地工作,但有个例外:如果修改了一条数据、释放了关联的锁后,事务被取消(回滚),而另一个事务读到了修改后的值,但最后这个值却被回滚。为了避免这个问题,所有独占锁必须在事务结束时释放

    多说几句

    当然了,真实的数据库使用更复杂的系统,涉及到更多类型的锁(比如意向锁,intention locks)和更多的粒度(行级锁、页级锁、分区锁、表锁、表空间锁),但是道理是相同的。

    我只探讨纯粹基于锁的方法,数据版本控制是解决这个问题的另一个方法

    版本控制是这样的:

    • 每个事务可以在相同时刻修改相同的数据
    • 每个事务有自己的数据拷贝(或者叫版本)
    • 如果2个事务修改相同的数据,只接受一个修改,另一个将被拒绝,相关的事务回滚(或重新运行)

    这将提高性能,因为:

    • 读事务不会阻塞写事务
    • 写事务不会阻塞读
    • 没有『臃肿缓慢』的锁管理器带来的额外开销

    除了两个事务写相同数据的时候,数据版本控制各个方面都比锁表现得更好。只不过,你很快就会发现磁盘空间消耗巨大。

    数据版本控制和锁机制是两种不同的见解:乐观锁和悲观锁。两者各有利弊,完全取决于使用场景(读多还是写多)。关于数据版本控制,我推荐这篇非常优秀的文章,讲的是PostgreSQL如何实现多版本并发控制的。

    一些数据库,比如DB2(直到版本 9.7)和 SQL Server(不含快照隔离)仅使用锁机制。其他的像PostgreSQL, MySQL 和 Oracle 使用锁和鼠标版本控制混合机制。我不知道是否有仅用版本控制的数据库(如果你知道请告诉我)。

    [2015-08-20更新]一名读者告诉我:

    Firebird 和 Interbase 用不带锁的版本控制。

    版本控制对索引的影响挺有趣的:有时唯一索引会出现重复,索引的条目会多于表行数,等等。

    如果你读过不同级别的隔离那部分内容,你会知道,提高隔离级别就会增加锁的数量和事务等待加锁的时间。这就是为什么多数数据库默认不会使用最高级别的隔离(即串行化)。

    当然,你总是可以自己去主流数据库(像MySQL, PostgreSQLOracle)的文档里查一下。

    日志管理器

    我们已经知道,为了提升性能,数据库把数据保存在内存缓冲区内。但如果当事务提交时服务器崩溃,崩溃时还在内存里的数据会丢失,这破坏了事务的持久性

    你可以把所有数据都写在磁盘上,但是如果服务器崩溃,最终数据可能只有部分写入磁盘,这破坏了事务的原子性

    事务作出的任何修改必须是或者撤销,或者完成。

    有 2 个办法解决这个问题:

    • 影子副本/页(Shadow copies/pages):每个事务创建自己的数据库副本(或部分数据库的副本),并基于这个副本来工作。一旦出错,这个副本就被移除;一旦成功,数据库立即使用文件系统的一个把戏,把副本替换到数据中,然后删掉『旧』数据。
    • 事务日志(Transaction log):事务日志是一个存储空间,在每次写盘之前,数据库在事务日志中写入一些信息,这样当事务崩溃或回滚,数据库知道如何移除或完成尚未完成的事务。
    WAL(预写式日志)

    影子副本/页在运行较多事务的大型数据库时制造了大量磁盘开销,所以现代数据库使用事务日志。事务日志必须保存在稳定的存储上,我不会深挖存储技术,但至少RAID磁盘是必须的,以防磁盘故障。

    多数数据库(至少是Oracle, SQL ServerDB2PostgreSQL, MySQL 和 SQLite) 使用预写日志协议(Write-Ahead Logging protocol ,WAL)来处理事务日志。WAL协议有 3 个规则:

    • 1) 每个对数据库的修改都产生一条日志记录,在数据写入磁盘之前日志记录必须写入事务日志。
    • 2) 日志记录必须按顺序写入;记录 A 发生在记录 B 之前,则 A 必须写在 B 之前。
    • 3) 当一个事务提交时,在事务成功之前,提交顺序必须写入到事务日志。

    这个工作由日志管理器完成。简单的理解就是,日志管理器处于缓存管理器(cache manager)和数据访问管理器(data access manager,负责把数据写入磁盘)之间,每个 update / delete / create / commit / rollback 操作在写入磁盘之前先写入事务日志。简单,对吧?

    回答错误! 我们研究了这么多内容,现在你应该知道与数据库相关的每一件事都带着『数据库效应』的诅咒。好吧,我们说正经的,问题在于,如何找到写日志的同时保持良好的性能的方法。如果事务日志写得太慢,整体都会慢下来。

    ARIES

    1992年,IBM 研究人员『发明』了WAL的增强版,叫 ARIES。ARIES 或多或少地在现代数据库中使用,逻辑未必相同,但AIRES背后的概念无处不在。我给发明加了引号是因为,按照MIT这门课的说法,IBM 的研究人员『仅仅是写了事务恢复的最佳实践方法』。AIRES 论文发表的时候我才 5 岁,我不关心那些酸溜溜的科研人员老掉牙的闲言碎语。事实上,我提及这个典故,是在开始探讨最后一个技术点前让你轻松一下。我阅读过这篇 ARIES 论文 的大量篇幅,发现它很有趣。在这一部分我只是简要的谈一下 ARIES,不过我强烈建议,如果你想了解真正的知识,就去读那篇论文。

    ARIES 代表『数据库恢复原型算法』(Algorithms for Recovery and Isolation Exploiting Semantics)。

    这个技术要达到一个双重目标:

    • 1) 写日志的同时保持良好性能
    • 2) 快速和可靠的数据恢复

    有多个原因让数据库不得不回滚事务:

    • 因为用户取消
    • 因为服务器或网络故障
    • 因为事务破坏了数据库完整性(比如一个列有唯一性约束而事务添加了重复值)
    • 因为死锁

    有时候(比如网络出现故障),数据库可以恢复事务。

    这怎么可能呢?为了回答这个问题,我们需要了解日志里保存的信息。

    日志

    事务的每一个操作(增/删/改)产生一条日志,由如下内容组成:

    • LSN:一个唯一的日志序列号(Log Sequence Number)。LSN是按时间顺序分配的 * ,这意味着如果操作 A 先于操作 B,log A 的 LSN 要比 log B 的 LSN 小。
    • TransID:产生操作的事务ID。
    • PageID:被修改的数据在磁盘上的位置。磁盘数据的最小单位是页,所以数据的位置就是它所处页的位置。
    • PrevLSN:同一个事务产生的上一条日志记录的链接。
    • UNDO:取消本次操作的方法。
      比如,如果操作是一次更新,UNDO将或者保存元素更新前的值/状态(物理UNDO),或者回到原来状态的反向操作(逻辑UNDO) **。
    • REDO:重复本次操作的方法。 同样的,有 2 种方法:或者保存操作后的元素值/状态,或者保存操作本身以便重复。
    • …:(供您参考,一个 ARIES 日志还有 2 个字段:UndoNxtLSN 和 Type)。

    进一步说,磁盘上每个页(保存数据的,不是保存日志的)都记录着最后一个修改该数据操作的LSN。

    *LSN的分配其实更复杂,因为它关系到日志存储的方式。但道理是相同的。

    ** ARIES 只使用逻辑UNDO,因为处理物理UNDO太过混乱了。

    注:据我所知,只有 PostgreSQL 没有使用UNDO,而是用一个垃圾回收服务来删除旧版本的数据。这个跟 PostgreSQL 对数据版本控制的实现有关。

    为了更好的说明这一点,这有一个简单的日志记录演示图,是由查询 “UPDATE FROM PERSON SET AGE = 18;” 产生的,我们假设这个查询是事务18执行的。【译者注: SQL 语句原文如此,应该是作者笔误 】

    每条日志都有一个唯一的LSN,链接在一起的日志属于同一个事务。日志按照时间顺序链接(链接列表的最后一条日志是最后一个操作产生的)。

    日志缓冲区

    为了防止写日志成为主要的瓶颈,数据库使用了日志缓冲区

    当查询执行器要求做一次修改:

    • 1) 缓存管理器将修改存入自己的缓冲区;
    • 2) 日志管理器将相关的日志存入自己的缓冲区;
    • 3) 到了这一步,查询执行器认为操作完成了(因此可以请求做另一次修改);
    • 4) 接着(不久以后)日志管理器把日志写入事务日志,什么时候写日志由某算法来决定。
    • 5) 接着(不久以后)缓存管理器把修改写入磁盘,什么时候写盘由某算法来决定。

    当事务提交,意味着事务每一个操作的 1 2 3 4 5 步骤都完成了。写事务日志是很快的,因为它只是『在事务日志某处增加一条日志』;而数据写盘就更复杂了,因为要用『能够快速读取的方式写入数据』。

    STEAL 和 FORCE 策略

    出于性能方面的原因,第 5 步有可能在提交之后完成,因为一旦发生崩溃,还有可能用REDO日志恢复事务。这叫做 NO-FORCE策略

    数据库可以选择FORCE策略(比如第 5 步在提交之前必须完成)来降低恢复时的负载。

    另一个问题是,要选择数据是一步步的写入(STEAL策略),还是缓冲管理器需要等待提交命令来一次性全部写入(NO-STEAL策略)。选择STEAL还是NO-STEAL取决于你想要什么:快速写入但是从 UNDO 日志恢复缓慢,还是快速恢复。

    总结一下这些策略对恢复的影响:

    • STEAL/NO-FORCE 需要 UNDO 和 REDO: 性能高,但是日志和恢复过程更复杂 (比如 ARIES)。多数数据库选择这个策略。 注:这是我从多个学术论文和教程里看到的,但并没有看到官方文档里显式说明这一点。
    • STEAL/ FORCE 只需要 UNDO.
    • NO-STEAL/NO-FORCE 只需要 REDO.
    • NO-STEAL/FORCE 什么也不需要: 性能最差,而且需要巨大的内存。
    关于恢复

    Ok,有了不错的日志,我们来用用它们!

    假设新来的实习生让数据库崩溃了(首要规矩:永远是实习生的错。),你重启了数据库,恢复过程开始了。

    ARIES从崩溃中恢复有三个阶段:

    • 1) 分析阶段:恢复进程读取全部事务日志,来重建崩溃过程中所发生事情的时间线,决定哪个事务要回滚(所有未提交的事务都要回滚)、崩溃时哪些数据需要写盘。
    • 2) Redo阶段:这一关从分析中选中的一条日志记录开始,使用 REDO 来将数据库恢复到崩溃之前的状态。

    在REDO阶段,REDO日志按照时间顺序处理(使用LSN)。

    对每一条日志,恢复进程需要读取包含数据的磁盘页LSN。

    如果LSN(磁盘页)>= LSN(日志记录),说明数据已经在崩溃前写到磁盘(但是值已经被日志之后、崩溃之前的某个操作覆盖),所以不需要做什么。

    如果LSN(磁盘页)< LSN(日志记录),那么磁盘上的页将被更新。

    即使将被回滚的事务,REDO也是要做的,因为这样简化了恢复过程(但是我相信现代数据库不会这么做的)。

    • 3) Undo阶段:这一阶段回滚所有崩溃时未完成的事务。回滚从每个事务的最后一条日志开始,并且按照时间倒序处理UNDO日志(使用日志记录的PrevLSN)。

     

    恢复过程中,事务日志必须留意恢复过程的操作,以便写入磁盘的数据与事务日志相一致。一个解决办法是移除被取消的事务产生的日志记录,但是这个太困难了。相反,ARIES在事务日志中记录补偿日志,来逻辑上删除被取消的事务的日志记录。

    当事务被『手工』取消,或者被锁管理器取消(为了消除死锁),或仅仅因为网络故障而取消,那么分析阶段就不需要了。对于哪些需要 REDO 哪些需要 UNDO 的信息在 2 个内存表中:

    • 事务表(保存当前所有事务的状态)
    • 脏页表(保存哪些数据需要写入磁盘)

    当新的事务产生时,这两个表由缓存管理器和事务管理器更新。因为是在内存中,当数据库崩溃时它们也被破坏掉了。

    分析阶段的任务就是在崩溃之后,用事务日志中的信息重建上述的两个表。为了加快分析阶段,ARIES提出了一个概念:检查点(check point),就是不时地把事务表和脏页表的内容,还有此时最后一条LSN写入磁盘。那么在分析阶段当中,只需要分析这个LSN之后的日志即可。

    结语

    写这篇文章之前,我知道这个题目有多大,也知道写这样一篇深入的文章会相当耗时。最后证明我过于乐观了,实际上花了两倍于预期的时间,但是我学到了很多。

    如果你想很好地了解数据库,我推荐这篇研究论文:《数据库系统架构》,对数据库有很好的介绍(共110页),而且非计算机专业人士也能读懂。这篇论文出色的帮助我制定了本文的写作计划,它没有像本文那样专注于数据结构和算法,更多的讲了架构方面的概念。

    如果你仔细阅读了本文,你现在应该了解一个数据库是多么的强大了。鉴于文章很长,让我来提醒你我们都学到了什么:

    • B+树索引概述
    • 数据库的全局概述
    • 基于成本的优化概述,特别专注了联接运算
    • 缓冲池管理概述
    • 事务管理概述

    但是,数据库包含了更多的聪明巧技。比如,我并没有谈到下面这些棘手的问题:

    • 如何管理数据库集群和全局事务
    • 如何在数据库运行的时候产生快照
    • 如何高效地存储(和压缩)数据
    • 如何管理内存

    所以,当你不得不在问题多多的 NoSQL数据库和坚如磐石的关系型数据库之间抉择的时候,要三思而行。不要误会,某些 NoSQL数据库是很棒的,但是它们毕竟还年轻,只是解决了少量应用关注的一些特定问题。

    最后说一句,如果有人问你数据库的原理是什么,你不用逃之夭夭,现在你可以回答:

    展开全文
  • 数据库MYSQL底层原理分析-笔记-pdf
  • 数据库事务底层原理

    2019-07-22 16:50:19
    数据库事务特性: ACID 原子性:指的是我们的操作不可分,要么执行成功,要么执行失败。 隔离性:事务之前互相隔离互不影响 ...持久性:事务一旦提交,对数据库的更新就会持久保存到数据库中,...
  • 数据库底层存储原理

    千次阅读 2019-08-09 20:09:00
    Oracle架构,讲述了Oracle RDBMS的底层实现原理,是Oracle DBA**调优和排错的基础理论。深入理解Oracle架构,能够让我们在Oracle的路上走的更远。本文主要是在对RDBMS的底层组件功能和实现原理有一定的了解的情况下...
  • Neo4j图数据库简介和底层原理_1
  • Neo4j图数据库简介和底层原理_2
  • Neo4j图数据库简介和底层原理_3
  • Neo4j图数据库简介和底层原理_4
  • Neo4j图数据库简介和底层原理_5
  • Neo4j图数据库简介和底层原理_6
  • Neo4j图数据库简介和底层原理_8
  •   Oracle数据库 底层原理解析  全部课程学习网址:https://edu.csdn.net/course/detail/35647
  • 数据库索引底层原理及优化

    千次阅读 多人点赞 2018-09-11 14:11:18
    本文以MySQL数据库为研究对象,讨论与数据库索引相关的一些话题。特别需要说明的是,MySQL支持诸多存储引擎,而各种存储引擎对索引的支持也各不相同,因此MySQL数据库支持多种索引类型,如BTree索引,哈希索引,全文...
  • 1.首先简单说下mysql的两大...你去你的mysql安装目录下看两个数据库的文件就会发现,MyiSam的文件比InnoDB的多出了一个文件:MYI (存索引的文件) 为什么这样做呢 ?当然是适应不同业务场景,通常InnoDB适用于大多
  • 从IO看数据库底层实现原理

    千次阅读 2013-09-01 23:51:26
    最近研究了Hibernate中的一些问题,发现除了缓存机制,还有些问题也值得我们深思,在hibernate严格限定Java包装类和工具类与相应数据库底层数据类型的映射的时候,各位是否想过,为什么要这么映射,也许你会说这个是...
  • 数据库引擎底层原理B+树

    千次阅读 2017-04-07 21:00:35
    本文介绍MySQL的InnoDB索引相对底层原理相关知识,涉及到B+Tree索引和Hash索引,但本文主要介绍B+Tree索引,其中包括聚簇索引(InnoDB)和非聚簇索引(MyIASM),InnoDB数据页结构详解,B+Tree索引的使用以及优化,...
  • 本教程将给大家深度剖析数据库框架底层实现的原理,然后采用泛型、反射、注解机制来教大家做一个自己的数据库框架。 【课程收益】 深度了解数据库框架的实现原理  理解泛型、反射机制的使用  熟练掌握自定义注解...
  • 数据库索引的底层原理

    千次阅读 2015-03-18 20:29:46
    数据库索引的本质是空间换时间的解决办法,就是面试时经常问的数据结构排序等的具体应用。 索引就是在需要的字段另建了一张查询表。 其中查询表的数据结构就是B树 B树是一种应用到文件操作系统和数据库索引的数据...
  • Neo4j图数据库简介和底层原理   现实中很多数据都是用图来表达的,比如社交网络中人与人的关系、地图数据、或是基因信息等等。RDBMS并不适合表达这类数据,而且由于海量数据的存在,让其显得捉襟见肘。NoSQL...
  • Mybatis 连接mysql数据库底层运行原理

    千次阅读 2019-03-11 16:55:20
    工作中一直在用spring+springmvc+mybatis,只是知道它是用于持久层框架,但是一直不知道原理是什么,通过网上视频解释,自己做一个笔记,方便以后查阅。 什么是mybatis: MyBatis 是一款优秀的持久层框架,它支持...
  • MySQL源码分析之use database_name切换表空间切换表空间源码分析客户端流程服务端流程 说明: 以下所有说明都以 MySQL 5.7.25 源码为例 ,存储引擎为InnoDB。 切换表空间 mysql客户端登录之后,需要使用use ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 159,008
精华内容 63,603
关键字:

数据库底层原理