高级数据库系统-查询

数据库查询可以看做是对数据集合做运算，运算的基本单位是算子。比如投影、扫描、选择、连接、排序等

在关系数据库及其基本实现原理 这篇博客中，我们初步了解了几种算子的功能以及如何实现的。

现在我们来介绍一下在执行查询的流程：

1. 首先SQL语言会被解析，并得到好几种不同的查询方案(plan)。 SQL$\rightarrow$ Plans 的过程被称为 Interpretation
2. 然后引擎会找出最佳的哪个执行方案。Plans$\rightarrow$ Best Plan 的过程被称为Query Optimization
3. 最后引擎会执行这个方案，并返回结果。Best Plans $\rightarrow$ Results 的过程为成为Query Execution

过程如下：

• 从逻辑上讲：
  • 查询 $\rightarrow$ 语法树 $\rightarrow$ 逻辑优化$\rightarrow$ 物理优化 $\rightarrow$ 查询执行
  • 逻辑优化是关系代数的等价变换
  • 物理优化是访问路径的选择，算子执行路径的选择
• 在实现中
  • 很可能发生耦合
  • 查询 $\rightarrow$ 语法树和数据结构 $\rightarrow$ 逻辑优化/物理优化耦合 $\rightarrow$ 执行

下图是PostgreSQL中查询引擎的组成部分：

引擎主要可以分为几个组件：

parser

首先是parser，它进行的是编译过程，对SQL进行词法和语法分析

SQL被编译过程中会形成这样一棵 Parse Tree(语法树)

Analyzer/Analyser

然后，Analyzer会对语法树做语义检查，一共是检查这几个方面：

1. 投影列是否存在与对应的关系中
2. 属性是否明确？是否有歧义？是否存在？
3. 类型检查(int ,double等)

Rewriter

Parse Tree经过 analyzer之后就变成了Query Tree, 在这里面有一个视图表 (蓝色的RTE_VIEW)。Rewriter的作用是展开视图表

Planner

Planner是对上面的完整的Query Tree进行处理，形成查询计划

SELECT * FROM tb1_a WHERE id < 300 ORDER BY data;

比如说对上面这句SQL语言，会生成如下一个plan tree

在这个过程之后会进行逻辑优化和物理优化，这部分我们放到最后一节去说。

我们可以使用EXPLAIN功能，输出物理计划：

Executor

最后交给执行器去执行，接下来我们就要学习查询执行过程中的火山模型

查询引擎-火山模型

我们从上面看出，物理计划是一颗树形的结构，那么以此提出了火山模型来实现查询引擎的功能。火山模型是一种通用的SQL执行引擎的实现方法，因此很多数据库都会使用。

• 操作流：从树顶依次往孩子节点要数据，直到底层算子提供数据
• 数据流：从叶子依次往上层返回数据

每个数据库操作，都会使用共同的结构：

• Open() ： 准备资源，准备获得第一个tuple
• Next(): 一次提供一个数据
• Close(): 释放资源

比如说上面这个执行树，投影、选择、扫描算子都有这三个接口。当我的SQL语句想要得到一行结果的时候， 首先会去调用投影的next接口，然后投影的next会去调选择的next接口，而选择的next又会去调扫描的next接口，只有满足了条件的数据才能够向上传递。

总而言之，就是父亲节点去调用孩子节点的next接口，直到获得一条数据为止。比如说第3条数据符合age<25的条件，那么，选择算子会循环调用3次扫描算子的next接口，才会拿到一条符合条件的数据，并向投影算子传递

比如说我们要实现一个排序算子，我们可以这样来实现

sqrt(){
	if(第一次){ // 这里需要判断是否为第一次执行，第一次执行需要将孩子节点的信息全部调用上来，后面则不用
	  while(true){
	    child.next
	  }
	  store sort
	  返回信息
	}else{
		store sort
	 	返回信息
	}
}

其实，上面的sort就是一种阻塞算子，我们也可以看到sort和扫描是完全两种不同的算子——sort需要拿到所有的数据，而扫描不需要。

因此，我们称 要把数据全部拿到再执行的算子称为阻塞算子

常见的阻塞算子是：构建哈希表(哈希连接)和排序(合并连接)

流水线概念

我们可以首先来对比批处理执行和流水线执行

如果是用批处理的话，我们可以写几个for循环，然后几行代码就可以搞定。虽然效率很高，但这样的可扩展性极差。

但是使用流水线来执行的话，虽然效率很低，但是可扩展。

因此我们可以做出预测：

火山模型的优点：

1. 实现简单易扩展
2. 节省内存资源

1. 冗余的流控指令
2. 效率低：虚函数嵌套，CPU的分支预测不友好

流水线在内存数据库中的优化

这实际上是一个并行的概念，也就是一次next并不是只取一条数据，而是取一批数据：

Join 算子实现

这里我们主要学习连接算子join的实现过程。两张表的Join的效果如下

连接算法一共有三种：Nest Loop Join、 Hash Join、 Merge Join. 目的就是将相同属性的pair给找出来

Nest Loop Join

Nest Loop Join就是对 R 和 S 进行双循环匹配。如果 $R\bowtie S$ 的话，R为内表，S为外表

Function : nljoin (R,S,p)
/* outer relation S */
foreach record s in S do
		/* inner relation R */
		foreach record r in R do
			/* <s,r> denotes record concatenation */
        if <s,r> satisfies p then
            append <s,rs> to result

Hash Join

如果采用Hash Join方法，可以对内表(这里是R表)构建哈希表，然后用S表去做哈希探测

Merge Join

如果采用Merge Join,需要分别对 R 和 S 进行排序，然后用归并算法得到Join结果

连接算法结合火山模型

现在我们来看三种算法在火山模型下该如何实现。

Nest Loop的火山模型

我们可以简单画出 Nest Loop Join的查询计划表

我们看到，由于Join算子需要对两张表进行连接，那么他一定是由两个孩子算子的

事实上，在数据库系统中，有三种不同类型的算子：

• 没孩子的，比如Scan算子
• 单孩子的，比如Sort算子、投影算子
• 双孩子的，比如Join算子

首先我们列出比较简单的open接口和close接口

Function: open()
R.open();
S.open();
r <- R.next;

Function: close()
R.close()
S.close()

接下来给出next()接口的伪代码，本质上就是两重扫描：伪代码也非常直接

While (r != <EOF> )do
    while ((s<- S.next())!=<EOP>) do
        if p(r,s) then
          /*向上传递连接后的结果*/
          return <r,s>
        /*一遍循环完了，现在重置内表，继续循环*/
        S.close();
        S.open();
        r <- R.next();
return <EOF>;

Hash Join的火山模型

Hash Join 用到了多个算子：Hash算子用来创建哈希表，Hash Join算子用来探索哈希表

Hash Join的火山模型有两种实现方式：

open(){
		R.open();
		while((r=R.next())!=EOF)
				将 r 加入哈希表h (内表构造哈表h)
		S.open();
}

Next(){
		while(){
				s = S.next();
				用s探索哈希表h；
				if(找到一个匹配的<r,s>)
						return <r,s>
		}
}

在这中写法中，open接口其实是做一个准备工作，也就是将内表打开并将其扫入内存、构建哈希表了。这样在next接口中只需要做扫描即可。实际应用中这种方式更加常见

open(){
		R.open();
		r = R.next();
		S.open();
}

next(){
		if(r是R的第一个元组){
				将r加入哈希表h
				while((r=R.next())!=EOF)
						将r加入哈希表h
		}
		while(){
				s = S.next();
				用s探索哈希表h；
				if(找到一个匹配的<r,s>)
						return <r,s>
		}
}

如果采用这种写法，需要在next的时候多加一层判断，实际上开销是差不多的。

Merge Join的火山模型

Merge Join 用到了多个算子：Sort、Merge Join 等，下面是其查询计划表：

Merge Join 下面有两个Sort算子，负责对两张表的数据进行排序。Sort算子在之前我们说过会维护一个缓冲区，用一个while循环不断地向Scan算子要数据，然后在缓冲区中进行排序。

两个Sort都排序完成后，进行Merge Join算子的操作，也就是会从两个Sort算子各取一条数据，比较它们是否相等，如果相等说明满足条件，return，否则就继续取下面两条数据。

Join算子并不是阻塞算子，Sort算子才是阻塞算子

基于块数据的连接算法

现在很多数据库的底层是LSM Tree，在那种数据库环境下谈基于块数据的算法是没有意义的，这里我们讨论的是传统数据库中的基于块数据的连接方法

由于在传统数据库中，数据库以Block/Page为基本存储单位，因此缓冲区可能会存在内存不足的问题，导致无法将数据全部加载到内存中进行计算。

假设内存有B个Block用于Join，其中一个Block用于缓存Join的结果(在火山模型中并不需要缓存所有结果)。基于上面这种情况，我们再来讨论三种算法的实现

Nest Loop Join

首先我们来回顾一下Nest Loop Join算法：对于 $S\bowtie R$, $S$ 为内表，$R$ 为外表。那么需要做一个双重循环，将$$ 一一比较后得出结果,s>

当块和Next Loop Join结合起来会变成什么样？

我们假定 R 和 S 的blocks数量分别为$N_R$ 和 $N_S$ ，那么对于外表来说，其每一个块都需要放到内存里面一遍，对于内表来说，外表的元素每改变一次，就要将所有的块放入内存中访问一遍，因此总的块访问次数为 $N_R+\abs{R} \cdot N_S$

Index Nest Loop join

实际上我们可以对Nest Loop做一定的优化：改进成了 Indexed Nest Loop Join

对R表的每个数据，直接对S表做Index Scan，以此减少磁盘访问次数和访问数据量。

Function : index_nljoin(R,S,p)
foreach record r in R do
		scan S-index using (key value in) r 
		and concatenate r with all match tuples s;

appand <r,s> to result;

前提条件是，在S表上的那一列需要对其构建索引。然后，对于R表中的每个元素，对S表做索引的查询，这样复杂度就可以降下来了。对块的访问次数也没有之前多——不用再扫描全表的块$N_s$了

Block Nest Loop Join

我们可以再进行一次优化来减少磁盘的访问次数

假设缓冲区中 $b_r$ 和 $b_s$ 个块用于缓存R和S的数据，$b_r+b_s=B-1$(B为内存可分配的块数量), 剩下1个block是用来存放输出的。

Function: block_nljoin (R, S, p)
foreach b_r-sized block in R do
		build an in-memory hash table H for the current R-block;
		foreach b_s-sized block in S do
				foreach record s in current S-block do
						probe H and append matching (r, s) tuples to result

也就是说，一次读入 $b_r,b_s$ 个块读入内存，对其进行比较、连接。

因此，总的磁盘访问次数为： $\lceil N_R/b_r\rceil\cdot\lceil N_S/b_s\rceil $ (默认块是连续的)

访问block数量为： $N_R\cdot N_S$

通常来说，我们会取 $b_r = B-2,b_s = 1$ ，内存中建立哈希表优化匹配 .(如果R表可以一次性全部放进内存，事实上和哈希连接比较相近)

Block Hash Join

如果R表可以完全放入内存，那么R和S只访问一遍，和上面我们说的Nest Loop算法相近

那么如果R表无法完全放入内存的话，就需要对R表进行Block Hash 算法了：

我们可以建 B-1 个桶， 每个桶写满一个Block就刷盘，一个桶可能占多个Block，如下所示：

对S表也可以做这样一个Block Hash算法，此时，R表和S表都按照桶分配到磁盘上了。然后，对每个Partition做一趟哈希连接

伪代码如下：

当然，这种Block Hash Join算法存在一定的限制

如果每个Partition中R表的Block数量都少于B-1的话，那么算法需要对R、S表进行两趟访问：

• 第一趟将他们读入内存然后进行 Partition, 再将它们刷盘
• 第二趟将每个Partition读入内存，进行Hash Join

但是，如果有Partition中的R表的Block数量大于B-1的话，需要在此基础上继续进行Partition，因此需要多趟算法

如果按照正常的都小于B-1来说，Hash Join访问磁盘Block的次数为：$3N_R+3N_S$ 。 其中，第一趟算法读取和刷盘就包含了$2N_R+2N_S$ ，第二次读取包含了 $N_R+N_S$

Hybrid Hash Join

还可以对Block Hash Join做进一步优化，也就是对部分 Partition 做一趟算法，部分用两趟算法

• 假设构建k个桶，对其中m个桶完全保留在内存中，其他k-m个桶只保留一个block

基于块的排序算法

同样的，对于另外一个阻塞算子——排序，如果是基于块的情况下，是怎么样的？

首先，我们有$N_R$ 个块，但内存只有 B-1 个块，$N_R>B-1$ ， 此时该如何借助内存进行排序

我们可以从$N_R$ 个块中每次取出 $B-1$ 个块，然后对其进行排序，排序完以后将其刷回磁盘，记为部分1；这样一直记录到部分x。

这样一共会得到 x个排好序的部分，如果$xB-1$ ，那么再对一些部分做归并。

因此可能是两趟，也可能是多趟排序

查询优化器