关系:实际上是一张二维表,表的每一行是一个元素,每一列是一项属性。 元组:指的是一个关系上属性集的笛卡尔积的一个元素。大部分情况一下,我们可以理解为表的一行数据。
五种基本操作:
并(Union):设关系R和关系S具有相同的属性n,且相应的属性取自同一个域,则关系R和关系S的并由属于R或属于S的元组组成,其结果仍为n元的关系
差(Difference):设关系R和关系S具有相同的属性n,且相应的属性取自同一个域,则关系R和关系S的差由属于关系R而不属于关系S的元组组成,其结果仍为n元的关系
笛卡尔积(Cartesian Product):设关系R和关系S的属性分别为r和s。定义R和S的笛卡尔积是一个(r+s)元的元组集合,每个元组的前r个分量来自R的一个元组,后s个分量来自S的一个元组
投影(Projection):对关系进行垂直分割,消去某些列,并重新安排列的顺序,再删去重复元组
选择(Selection):根据某些条件对关系做水平分割,即选择符合条件的元组
四种组合操作:
交(Intersection):设关系R和关系S具有相同的属性n,且相应的属性取自同一个域,则关系R和关系S的交由既属于关系R又属于关系S的元组组成,其结果仍为n元的关系。关系的交可以由关系的差来表示。
联接(Join):连接操作是笛卡尔积和选择操作的组合。
自然联接(Natural Join):是一种特殊的等值联接,它要求两个关系中进行比较的分量必须是相同的属性组,并且要在结果中把重复的属性去掉。
除(Division):设两个关系R和S的属性分别为r和s(设r>s>0),那么R除S是一个(r-s)元的元组的集合。它是满足下列条件的最大关系:其中每个元组t与S中的每个元组u组成的新元组<t,u>必在关系R中。除运算是笛卡尔积的逆运算。
SQL是关系模型操作的高层次抽象,所以SQL可以转化为一系列关系代数操作。执行关系代数操作的基本方法有扫描、散列、排序、索引等,这些方法对内存容量所做的假设也有所不同,一些算法假设内存可以容纳参与关系代数操作的数据对象,另外一些算法假设操作对象太大,内存无法容纳。这些算法在代价和结构上有明显的差别。
查询编译可以分为三大步骤:
a) 分析,建立查询的分析树。 b) 查询重写,分析树被转化为初始查询计划,这种查询计划通常是查询的代数表达式。然后初始查询计划被转化为一个预期所需执行时间较小的等价查询计划,也被成为逻辑查询计划。 c) 物理计划生成,通常是通过给b中产出的逻辑查询计划的每一个操作符选择实现算法并选择这些操作符的执行顺序,逻辑计划被转化为物理查询计划。物理查询计划也是用表达式树来表示,同时还包含很多细节,如被查询的关系是怎样被访问的,以及一个关系何时或是否应该被排序。
b和c部分通常被称作查询优化器,它们是查询编译的难点。为了选择最好的查询计划,我们需要判断:
这些选择都依赖关于数据库的元数据。
物理查询计划由操作符构成,每一个操作符实现物理查询计划中的一步。物理操作符常常是一个关系代数操作的特定实现,除此之外,也有一些无关任务,例如扫描表,将关系代数要操作的某个关系的每个元组调入内存。
读取一个关系R的整个内容,这个操作符的一个变体包含一个简单的谓词(仅读出关系R中满足这个谓词的元组)。
定位关系R中元组的基本方法
在读取一个关系的元组时,很多情况需要将关系排序。SQL中有 ORDER BY 语句会要求对关系排序,另外还有数据库关系代数操作的具体算法上也需要对关系进行排序(后面会讲到)。
排序-扫描的具体实现有多种方法,例如想产生关系R上按属性a排序的关系,假设a上有B-数索引或者R是按a排序的索引属性存储的,那么用索引扫描即可。假设关系R很小,则可以用表扫描,然后在内存中排序。假设关系R很大,那么后边会讲到用多路归并方法排序。
一个查询通常包括好几个关系代数操作,相应的物理查询计划由几个物理计划操作符组成。挑选最优的物理计划操作符需要预估每个操作符的代价。磁盘IO的数目是数据库衡量物理计划操作符代价的标准,这里有两个假设,第一操作符的对象位于硬盘、但结果在内存中,第二一个查询的中间操作结果也应该在内存中。
我们设定,内存的一个缓冲区大小和硬盘块大小一致,我们用M表示缓冲区的数目。
当描述一个关系R的大小时,绝大部分情况下,我们想知道的是关系R的所有元组所需要的硬盘块的数目。我们用B(R)表示聚集的关系R所占用的硬盘块数,简记为B。
我们用T(R)表示关系R的元组总数,简记为T,一个硬盘块能容纳的元组数表示为T/B。
我们用V(R,a)表示关系R中a属性的不同值数目,以此可推,V(R,a1,a2...an)=T(R)。
假设关系R是聚集的,那么表扫描操作符的代价近似为B,如果关系R能够全部装进内存,那排序扫描的代价也是B。
如果关系R不是聚集的,即元组分散在不同的硬盘块中,那么表扫描的代价就是T,如果关系R能够全部装进内存,那排序扫描的代价也是T。
许多物理操作符可以实现为迭代器。迭代器有三个方法,这三个方法允许使用者一次获得一个元组。
使用迭代器的好处:同一时刻活跃的操作有很多,元组按照需要在操作符之间传递,这样就减少了存储要求。
表扫描的迭代器实现,在open方法中获取第一个块的第一个元组,在next方法中判断加载下一个块和元组。
排序扫描的迭代器实现,在open方法中读取整个关系R,然后排序,在next方法中顺序读取。
并操作的迭代器实现,在open方法中先调用第一个关系的迭代器,在next方法中判断第一个关系是否结束,如果结束就打开第二个关系的迭代器。
如何执行逻辑查询计划中的每个单独步骤(例如连接或选择)?逻辑查询计划转为物理查询计划的一个部分就是选择算法。大体上分为三类:
按照算法难度和代价分为三个等级:
操作符的分类:
非常简单,如果关系R是聚集的,那么IO代价是B。如果是非聚集的,代价是T。
有一个例外,带有在索引上属性和常量比较的选择扫描,效率会显著提高,
在open方法中非阻塞
消除重复
一次读取一个块,但对于每个元组要进行判断:
要求:B(\delta(R)) <= M
在open方法中非阻塞
分组
在内存中为分组创建一个项,在项中存有分组的属性值和聚集的一个或者多个累计值。
这里需要注意,在open方法中,所有元组扫描完成后才能结束。
在open方法中阻塞
交、并、差、积和连接操作。为了操作集合操作和包操作,这里用B和S分别表示包和集合。为了简化连接的讨论,仅考虑自然连接,\theta连接可以被认为是积或自然连接后额外增加的条件。
包并
包的并可以通过一种非常简单的一趟算法计算出来。R\cup_BS,先复制关系R的元组到内存,再复制关系S的每一个元组到内存。IO代价为B(R)+B(S),M=1就够用。
在open方法中非阻塞
其他操作则需要将R和S中较小数量的关系读到内存并建立合适的数据结构。其内存要求是min(B(R),B(S)) <= M
集合并
将S读入内存,生成查找结构,Key为整个元组。然后一个一个地读取R的元组t,假如元组t在S中,就跳过,否则就输出。最后输出S的元组。
在open方法中非阻塞
集合交
将S读入内存,生成查找结构,Key为整个元组。然后一个一个地读取R的元组t,假如元组t在S中,就输出,否则就跳过。
在open方法中非阻塞
集合差
R-_SS:将S读入内存,生成查找结构,Key为整个元组。然后一个一个地读取R的元组t,假如元组t在S中,就跳过,否则输出。
S-_SR:将S读入内存,生成查找结构,Key为整个元组。然后一个一个地读取R的元组t,假如元组t在S中,那么删除内存中的元组t。处理完R的所有元组后,输出内存中剩余的元组。
在open方法中阻塞
包交
存储S的元组和元组出现的次数计数,注意,相同元组只存一份,计数加一。然后一个一个地读取R的元组t,假如元组t在S中,且计数不为0,则输出t并将计数减一。
在open方法中非阻塞
包差
S-_BR:存储S的元组和元组出现的次数计数,注意,相同元组只存一份,计数加一。然后一个一个地读取R的元组t,假如元组t在S中,且计数不为0,则将计数减一。最后输出内存中剩余元组,输出次数为计数值。
R-_BS:存储S的元组和元组出现的次数计数,注意,相同元组只存一份,计数加一。然后一个一个地读取R的元组t,假如元组t在S中,且计数不为0,则将计数减一,如果元组t不在S中或在S中且计数为0,则输出。
在open方法中阻塞
积
将S读入内存,不需要特殊结构。然后一个一个地读取R的元组t,与S的每一个元组连接并输出。
在open方法中非阻塞
自然连接
R(X,Y)和S(Y,Z)自然连接,Y表示R和S的所有公共属性。
在open方法中非阻塞
在讨论更复杂的方法之前,先来看看嵌套循环连接操作算法。这些算法某种意义上来说需要一趟半。因为两个操作对象中的一个对象元组只用读取一次,而另一个操作对象的元组需要重复读取。
嵌套循环连接可以用于任何大小的关系。
在一趟算法的积和自然连接中,要求一个关系可以完全读入内存。而实际上,我们每个关系只读入一个元组,或者一块。
如果按块读取,那么块少的关系应该在循环外侧。例如B(R)=1000,B(S)=500,M=100,先循环关系R、再循环关系S所需读取块数为:10次外循环乘100+10次外循环乘5次内循环乘100=6000,先循环关系S、再循环关系R所需读取块数为:5次外循环乘100+5次外循环乘10次内循环乘100=5500。
假设我们有M个内存缓冲区进行排序,可以通过两趟的算法对非常大的关系进行排序,这种算法叫做两阶段多路归并排序(Two-Phase, Multiway Merge-Sort, TPMMS)。
归并流程如下:
根据阶段1和阶段2可知,最多有M-1个子表,每个子表最多有M个块,所以关系R最多有(M-1)*M个块,近似表示为M^2。在整个过程中,需要读关系2两次,写关系1次。共计IO次数为3B。
例子:假设块大小为16KB,内存为1GB,那么M=1GB/16KB=16K,B最大为16K*16K=2^{28},总大小为4TB。
在阶段2的归并流程2中,找到所有块中的最小元素并移到输出缓冲区,在这个操作上,先检查输出缓冲区是否有相同元组,如果有就忽略。
在阶段1中,取分组属性作为排序关键字。在阶段2的归并流程2中,先判断是否有分组属性值相同的元组,有就做聚集操作,没有就直接输出。
包并(4.2.3)算法与操作对象无关,但集合并算法与操作对象大小有关系。
在阶段1中,对关系R和S分别创建排序子表。在阶段2归并流程1中,为关系R和S的每个子表都使用缓冲区。在流程2中,在把元组t输入输出缓冲区后,删除输入缓冲区中和元组t相同的元组。
算法和4.4.4节类似
R(X,Y)和S(Y,Z)自然连接,Y表示R和S的所有公共属性。
如果拥有公共值的元组太多,4.4.6算法就不可行。那么可以在排序的第二阶段和连接做合并。
思想如下,如果数据量太大不能存储内存,就使用一个合适的散列关键字散列一个或多个操作对象的所有元组。使用该算法,能使我们把所有需要一起考虑的元组分配到相同的桶。
消除重复、分组和聚集、交并差、连接
非聚簇的关系不可能有一个聚簇的索引,但聚簇的关系可以有非聚簇的索引。
基于索引的选择。在没有索引的情况下磁盘IO为B或T。如果选择的属性在索引上,那么磁盘IO为B(R)/V(R,a)。
使用索引的连接。磁盘IO最差情况为为T(R)T(S)/V(S,Y)、最好情况为T(R)B(S)/V(S,Y)
缓冲区管理策略
最近最少使用(LRU)
清空最长时间没有读写的块,这种方法要求保持一张缓冲区块的被访问最后一次时间的表。
先进先出(FIFO)
占用时间最长的块先被清空。B-数的根更容易被写回硬盘。
时钟算法(第二次机会)
该算法是LRU的最普遍的一个近似实现。实现方法是将缓冲区块看成一个环,每个块有一个标记(0或1,初始值为0),指针指向其中一个块。如果想读写某一个块,就把这个块的标志置为1。如果想找到一个可用的块,就顺时针旋转,找到第一个0,然后将其设置成1,在找的过程中扫过的块如果标志位1就将其标志设置成0。
略
语法分析器接收类似SQL的文本,并转换为语法分析树。树的节点由以下两者构成:
<Query>
表示select-from-where形式的查询,<Condition>
表示属于条件的表达式。如果一个节点是原子,那么该节点没有子节点。如果一个节点是语法类,则其子节点通过该语言的语法规则进行描述。
<Query> ::= SELECT <SelList> FROM <FromList> WHERE <Condition>
<SelList> ::= <Attrbute> , <SelList>
<SelList> ::= <Attrbute>
<FromList> ::== <Relation> , <FromList>
<FromList> ::== <Relation>
<Condition> ::== <Condition> AND <Condition>
<Condition> ::== <Attrbute> IN ( <Query> )
<Condition> ::== <Attrbute> = <Attrbute>
<Condition> ::== <Attrbute> like <Pattern>
<Attrbute> 为任意表示当前数据库模式的属性的字符串
<Relation> 为当前模式中作为关系而言的字符串
<Pattern> 为任何用引号括起来的字符串
虚视图替换,语义检查。
积,连接,并,交都满足交换律和结合律。
交换律
由于选择可以明显减少关系的大小,因此进行有效查询处理的最重要规则之一就是只要不改变表达式的结果,就把选择在语法树上尽可能的下移。
涉及\sigma的另一类定律允许我们对二元运算符进行下推选择:积、并、交、差、连接。有三中类型定律,这取决于下推选择到每个参数是可选的还是必须的。
因此对于并的定律是:
对于差的定律:
下面这些定律允许将选择下推到一个或者两个参数,对于选择\sigma _C,我们只能将其下推到包含C所涉及的全部属性的关系中。假设关系R中有C提及的所有属性,有以下定律:
如果C只涉及S的属性,则有:
对于其他3个运算符\Join 、 \Join_D 和 \cap 类似。如果关系R和S都包含C的属性,那么有诸如以下的定律:
一些平凡的定律
5.2.2节的规则是查询优化器的有力工具,在包含虚视图时,需要先将选择尽可能往树的上部移,然后再把选择下推到所有可能分支。
下推投影是有用的,但是一般而言不如下推选择那么有用,因为投影不改变元组数,只改变元组长度。
投影定律原理:
在5.1节,我们构造好了语法分析树,接下来需要把语法树转化为逻辑查询计划。
第一步,按适当的群组用一个或者多个关系代数运算符替代语法树上的节点和结构。第二步,利用第一步中产生的关系代数表达式,将其转换成我们所期待的可被转成最有效的物理查询计划的一个表达式。
select-from-where
结构的关系代数的非正式陈述为:
如果我们有一个包含<Condition>
的没有子查询的<Query>
,则可以用一个关系代数表达式替换整个成分——选择列表、from列表以及条件,其中代数表达式自底向上由下面这些内容组成:
<FromList>
中提及的全部关系的积是以下运算符的参数。对于<Condition>中包含子查询的语法树,我们将引入运算符的中间形式,他介于语法分析树的语法类与作用到关系上的关系代数运算符之间。该运算符通常被成为两参数选择。我们将不带参数的标签为
选择条件的限制 为什么要去除子查询?选择$\sigma$的条件实际上是针对每一个元组的筛选,即每拿出一个元组,都要执行一遍选择条件,判断满不满足。如果有子查询,则每拿出一个元组,就要执行一遍子查询,明显不现实。即使子查询与元组无关,那也对代价计算的影响很大。
规则的非正式描述,假设我们有一个两参数选择,其中第一个参数代表的关系R,第二个参数形如t in S
的<Condition>
,其中S是一个非相关子查询,t是R的元组。我们按照以下方式变换:
当我们把我们的查询语句转换为关系代数时,我们获得了一个可能的逻辑查询计划。下一步是在5.2节列出的代数定律上重写计划。
一下是优化器最常用到的:
逻辑查询计划会对应多个物理查询计划,如何评价每个物理查询计划、或者估计实现的代价。通过以下选择进行代价枚举:
为了做出每项选择,我们需要知道各个物理计划的代价是多少,在没有执行计划的前提下,我们不能准确地知道其代价。执行一个查询计划要比选一个计划所做的工作多,我们也不想同时执行多个查询计划。因此,我们必须能够预估某个计划的代价。
令 S=\sigma_{A=c}(R) ,有以下估计:
如果 S=\sigma_{a>=10}(R)
S=\sigma_{a!=10}(R) 我们认为取的是全量数据T(S)。
AND条件,建议是不同选择概率的乘积。
OR条件,大小难以估计,例如 S=\sigma_{C_1 \quad or \quad C_2}(R) 。当C1和C2相互独立,n为元组总数,m1表示满足C1的元组数,m2表示满足C2的元组数,有:
三种情况:
通常情况的估计:
并
较大者加较小者的一半
交
较小者的一半
差
T(R) - T(S)/2
消除重复
min(T(R)/2,\times V(R,a_i))
分组和聚集
T(R)/2
经过分析查询,转化为初始的逻辑查询计划和优化。基于代价估计选择物理查询计划。将逻辑计划转化为完整地物理计划还需要以下这些内容: