关系代数表达式在RDBMS查询优化中的应用

引言

查询优化是RDBMS中关系代数级别优化，即数据库系统尝试找到不同的关系代数表达式的等价表达，以期等价为更为高效的表达式。此外查询策略对查询性能也有很大的影响。

RDBMS处理一个给定的复杂查询通常会有很多种查询策略，而查询优化就是从这众多策略中找出最行之有效的查询执行方案。本文就如何书写高性能SQL的查询优化展开有关关系代数级别优化的探讨。我们以IBM DB2为例，结合关系代数等价规则的基础上，研讨一下DB2在关系代数级别优化的处理流程。

一、     关系代数表达式

在讨论关系代数表达式之前，我们需要引入数据库管理系统查询处理的基本流程：

这里我们要关注一下关系表达式这一步，因为，通过关系代数表达式的转化，我们可能存在查询到关系代数表达式一对多的实现情况。这就有可能导致关系型数据库在优化器参照统计信息生成查询结果过程中，其查询计划有很大差异。也就是通常所说的查询性能问题的关键所在。

首先我们来了解一下关系代数表达式的书写及基本类型。关系数据模型的数据操作是“数据库系统原理”的核心，理解关系代数基本运算，深入分析查询优化以及使用关系代数表达式改写查询有很大的帮助。通常在我们系统真实业务应用面临处理复杂业务查询时，数据库改写的关系代数表达式要进行相应的跟踪分析，尤其要明确各种运算的优先级。通常来讲我们采用查询树来辅助书写分析关系代数表达式。其次，文中论述了查询优化器产生给定表达式等价的表达式，并通过等价规则阐释如何将一个关系代数表达式转换成逻辑上的等价的关系代数表达式。最后，通过关系表达式的等价规则进行关系表达式转化，并通过基于代价的执行计划策略选取，我们选取最优的查询执行计划。

1.     关系代数表达式及基本类型

关系代数是一种抽象的查询语言，是关系数据库查询语言的理论基础。关系代数包括并（∪）、差（−）、笛卡尔积（×）、选择（σ）、投影（π）五种基本运算和交（∩）、自然连接（ ）、除法（÷）等组合运算。这些预算经过有限次的组合形成的表达式成为关系代数表达式，用来表达客户提出的查询请求。一般而言，关系代数表达式可以有如下集中常见的数据结构类型：

Ø  选择 (R)

Ø  投影 (R)

Ø  选择投影 ( (R))

Ø  选择自然连接投影 ( (R) S)

对于一些复杂的应用查询，可能有上述关系运算符多次运算。

2.     关系表达式的一般写法

对于给定的一些简单的查询，通过分析，大致可以写出关系代数表达式，一般遵循如下几步：

1)        确定目标属性，目标属性即用户所查询的属性列表；

2)        确定目标条件，分析查询要求，确定查询过程中的条件限定，一般式两个关系的等值连接、自然连接条件或某属性取值限定等；

3)        确定目标关系，参照目标属性、目标条件分析确定该查询所涉及的关系；

4)        画查询树，把目标关系当作叶子节点，对这些关系操作序列一次作为中间节点，画出查询所对应的语法树；

5)        写出关系代数表达式，按照从下向上的方式，即后序遍历查询树的方式一次将各节点写入关系代数表达式。每次写完，参照运算符和预算对象核实括号的存在必要性。

3.     关系代数表达式的等价原则

通常而言关系代数表达式的书写规范及经验，这里我们要着重强调关系代数表达式的等价原则，通过分析数据库管理系统从查询到关系代数表达式的转换的原理，逐步了解如何书写高效的应用查询。

查询通常在转化成不同的关系代数表达式时，其执行代价也有所不同。在关系代数中，如果两个关系代数表达式产生相同的元组集，则这两个关系代数表达式等价。RDBMS的优化器也是通过相应的规则列出等价的关系代数表达式，并产生其不同的执行代价估值，如果优化是基于代价的，则最终选定最小代价的关系代数表达式。

[引]下面我们列出关系代数表达式的一些通用等价规则。其中我们用 、 、 等表示谓词， 、 、 等表示属性列表，而 、 、 等表示关系代数表达式。关系名 是关系代数表达式的特例，在关系代数表达式中 出现的地方它均可出现。

(1)      级联，合取选择运算可分解为单个选择运算，此称之为 的级联：

(2)      交换律，选择运算满足交换律：

(3)      投影级联，一系列的投影运算，只有最后一个投影运算是必须的：

(4)      特别的谓词连接，选择操作可与笛卡尔及 连接相结合

a．  theta连接定义，

b． 

(5)      交换律，theta连接满足交换律

备注：左右两侧其属性 、 、 顺序不同，如考虑属性顺序，此等价规则不成立。自然连接作为theta连接特例，也满足交换律。

(6)      结合律，自然连接和theta的结合律

a．  自然连接结合律

b．  theta连接的结合律

备注1：其中 只涉及到 与 的属性，因此笛卡尔运算也满足结合律。

备注2：连接运算满足结合律、交换律在查询优化中对于重排连接顺序是很重要的。

备注3：谓词的相关性，要确定其属性涉及的关系表达式。

(7)      分配律，选择运算在下述条件下对 连接运算具有分配律：

a.      当选择条件 的所有属性只涉及参与连接运算的表达式之一时，满足分配律：（例如此处 只涉及到 ）

b.      当选择条件 只涉及 的属性，选择条件 只涉及 的属性时，满足分配律：

(8)      分配律，投影运算在下述条件下对 连接运算具有分配律：

a.      假定 、 分别代表 、 的属性。假定连接条件 只涉及 中的属性，则：

b.       考虑连接 ，假定 、 分别代表 、 的属性集；令 是 中出现在连接条件 中但不在 中的属性；令 是 中出现在连接条件 中但不在 中的属性。则：

备注1：本例同上述例子中的子查询col2的引入。

备注2：此种场景虽然看似条件限制苛刻，但是在降低IO方面效果比较显著。

(9)      交换律，集合的并与交满足交换律：

(10)  结合律，集合的并与交满足结合律：

(11)  分配律，选择运算对并、交、差具有分配律：

备注： 也成立。

(12)  分配律，投影运算对并运算具有分配律：

备注：我们不难看出就是选择、投影与交换律、分配律、结合律以及连接与集合的组合。

二、     RDBMS的查询优化

针对此前我们提及的关系代数表达式在数据库管理系统中的地位，进一步分析一下在数据库管理系统查询优化过程中。理清关系代数与关系SQL的对应转化关系对查询性能的影响。

在讨论查询优化的优化准则之前，首先我们应该清楚查询优化是为给定的查询选择最有效的查询执行计划的过程：

(1)      关系代数表达式优化，在关系代数级别，利用关系代数等价原则进行关系代数表达式优化；

(2)      查询语句处理策略的选择，即通常所讲的物理实现层面，通过语句处理策略，选择不同的连接算法、索引和估值方法进行优化。

三、     案例分析

下面就目前数据库市场上比较有代表性的商业产品IBM DB2为案例来分析一下优化处理的编译处理原理。IBM DB2的查询编译器将查询转化成其系统内部自识别的一棵运算树，然后在执行相应查询操作时，使用这棵运算数进行查询处理。DB2通过这棵运算树来支持丰富的查询操作，并通过它考虑更好的查询处理策略，并且使得复杂的查询变得更为灵活。

DB2将所有的SQL查询和语句转化成查询对应的运算树，运算树的基运算我们称之为访问方法，中间运算一般为关系代数运算。这棵运算树的根产生我们所期望的查询或查询结果。

备注：基运算：或者说是树的叶运算对数据库物理表中记录的进行的相关操作，通常我们称之为访问方法。

备注：中间运算，一般我们理解为关系代数运算，例如连接、结合运算和聚集等。

1.     基运算

IBM DB2 目前针对用户透明的一套关系表访问方法，其基运算包括：

Ø  表扫描

按页顺序存取表中所有记录

Ø  索引扫描

使用索引来选出满足查询的记录。使用RID访问符合条件的记录。并且数据库管理系统在侦测到数据访问的模式时，进行预取可能要访问的数据页。

Ø  块索引扫描

这主要是针对DB2特性表MDC的访问方法，一个块索引用来扫描一组特定的MDC数据块。使用BID访问符合条件的记录。

Ø  仅用索引

索引包含所有查询要求的属性，这种情况下，只要扫描索引项就可以满足要求了，单就性能而言，这种状况比较好，但是存储以及特殊环境不是太适用。

Ø  序列预取

适用场景是当对海量RID的非聚类索引进行扫描是。其原理是DB2对RID首先进行一个排序操作，并以排好的次序从数据存储页中顺序读取。此时排序访问将随机变为有序，为预读提供了可能。同样在BID也可以进行预读。

Ø  块和记录索引的“与”操作（blockand record index ANDing）

当数据库决定可以访问多于一个索引来限定基表中满足选择条件的记录时，采用此方法。其中最优选择性的索引用来生成BID或者RID序列，其余选中的索引用来返回满足条件的BID或者RID。此种实现较为复杂，只有两次扫描结果都出现的BID或者RID才能进行下一步处理。而从基表中取出的记录是两次扫描后的结果之后的交集（即为ANDing）。

Ø  块和记录索引的排序（blockand record index ordering）

如果场景需要两个或两个以上的块或者索引来满足由OR操作组合的谓词查询时，可采用此策略。DB2通过排序消除BID或者RID重复，然后输出结果记录。

上面所说的几种基运算也就是通常我们在执行计划中所常见的TBSCAN、IXSCAN、LPREFETCH、IXAND 和 IXOR等，这些元素对应DB2数据访问方法，并且只能应用于语句中引用的本地表。它们不能引用昵称（远程表）或派生的表（子选择的结果）。

2.     中间运算

DB2在中间运算方面主要集中于连接、聚集和集合操作等。对于连接，数据库管理系统可以选择嵌套循环、排序归并和散列连接等方法。（即通常我们所讲的NLJoin、MGJoin、HSJoin）

当查询要求连接表时，优化器可以选择三种基本连接策略中的一种策略：嵌套循环连接、合并连接或散列连接。

Ø  嵌套循环连接    

嵌套循环连接通常有以下两种执行方案：

(1)      对于外表中每个被访问的行，扫描内表；

(2)      对于外表每个被访问的行，对内表执行索引查找；

备注1：我们如何区分内外表？

如果在查询谓词中，存在如下格式的谓词，那内外表可以较为容易区分

expr(outer_table.column) relopinner_table.column

其中，relop是比较运算符（如 =,>,>=,<,<=等），而expr是基于外表的有效表达式。例如：t1.c1+t1.c2 <= t2.c1 （其中t1为outer_table，t2为inner_table）。

备注2：理想情况下，外表排序，内表使用集群索引，可使访问页的数目降至最少。因为DB2优化器在对嵌套连接进行求值时，执行连接前还将确定是否有必要对外表进行排序，如外表排序可以通过预取存入缓冲池，借此减少访问磁盘的操作次数。

Ø  合并连接

又称排序合并连接，前提条件是谓词格式为 table1.column = table2.column，即谓词格式必须为等式连接谓词。并且其连接输入数据需要是已排序的数据。合并连接中，DB2在实现过程中，同时扫描所连接的表。外表只扫描一次；如果外表值全部唯一则内表扫描一次，如果外表存在重复值，则内表参照重复次数多次扫描内表指定一组行。

备注1：如果字段为LONG字段或者大对象（LOB），无法使用合并连接。

Ø  散列连接

散列连接需要一个或多个格式为 table1.columnX = table2.columnY 的谓词，即需要谓词格式为等值谓词，且类型必须相同。

(1)      对于CHAR类型列，长度必须相同;

(2)      对于DECIMAL列，精度和小数位必须相同;

(3)      对于DECFLOAT列，精度必须相同;

(4)      等值谓词相关列不能是LONG列或者是大对象（LOB）列。

在我们分析DB2优化器执行散列连接的同时，我们首先要明确排序堆相关数据库参数sortheap以及实例参数sheapthres，理想情况下，实例参数sheapthres应该是最大sortheap的倍数，至少是其实例内数据库定义此参数最大值的两倍。

一般而言DB2在进行散列连接时，先将内表数据尽可能放之缓冲区，并参照连接谓词计算散列值，以此将排序指定内存区域分区，此时如果内表过大，可能会溢出至临时表。上述准备就绪后，扫描外表，计算散列值，并扫描内表散列值寻求匹配，此时需要判断内表对应外表所匹配的数据所处位置，如为临时表，则外表数据写入临时表，如为缓冲区，则外表数据也随之写入缓冲池，也就是说散列匹配时，外表数据的读取及存放参照内表而定。

备注1：计算用于每个数据库的典型排序堆大小：

  （对该数据库运行的并发代理程序的典型数目） * （为该数据库定义的 sortheap）

备注2：散列连接一般工作原理

首先，扫描指定的内表并且将行复制到从排序堆中划出的内存缓冲区，该排序堆由 sortheap 数据库配置参数指定。根据使用连接谓词的列计算而得的散列值，将内存缓冲区分为若干部分。如果内表的大小超出可用的排序堆空间，那么将所选部分的缓冲区写入临时表。

处理内表完毕后，通过首先比较对连接谓词的列计算的散列值，扫描第二个表（外表）并将该表的行与内表的行匹配。如果外表行列的散列值与内表行列的散列值匹配，那么将比较实际的连接谓词列值。

与未被写入临时表的表部分相对应的外表行将立即与内存中的内表行匹配。如果内表的对应部分已被写入临时表，那么也将外表行写入临时表。最后，从临时表中读取匹配的表部分对，比较它们的行的散列值，然后检查连接谓词。如果能够避免散列循环以及溢出到磁盘，那么散列连接的性能最佳。要调整散列连接性能，请估算可供 sheapthres 使用的最大内存量，然后调整 sortheap 参数。增大它的设置，尽可能避免散列循环和磁盘溢出，但不要达到 sheapthres 参数指定的限制。

为了描述连接和集合的二元运算，我们通常采用外部表和内部表概念来区分二元运算的输入流。

l  当内部表很小或者在连接谓词上使用一个索引来访问时，嵌套循环比较适合。

l  排序归并连接和散列连接在内、外表都比较大时比较有效。

DB2通过排序和归并实现集合运算。

l  集合合并在并的时候会消除重复；

l  集合在交的时候，不会消除重复；

DB2在处理聚集运算时，一般采用“下推”模式处理。例如对输入按分组列进行排序时，同时执行聚集运算。

3.     查询优化

为了进行转化和优化，首先，DB2查询编译器使用查询的内部表示，我们称之为查询图模型（QGM）。解析完SQL语句之后，DB2在QGM上执行语义转换来实施约束、参照完整性和触发器。这些转化的结果是加强的QGM。（如下图）

第二步，DB2视图执行查询重写，通常查询重写大致包括以下几种情况：

Ø  相关子查询的解相关；

Ø  使用提前约束处理将子查询变为连接；

Ø  适当情况下，将groupby 操作下推，部分情况下可能下推到连接一下；

Ø  对原始部分查询使用物化视图；

备注1：下推分析（仅限于联合数据库）

此步骤中的主要任务是，向优化器建议是否可以在数据源处以远程方式对操作进行求值（即下推）。此类下推活动仅适用于数据源查询，这是对一般谓词下推操作的扩展。

备注2：通过上述查询优化器描述我们可以推断一个SQL文报错提示信息的顺序。

例如 select * from syscat.tables where tabname like ‘tab%’;--正确写法

查询优化器处理顺序是：语法-语义-重写，以“select *from syscat.table where tabnames like as‘tab%’;”（有误写法）为例，数据库系统错误提示如下：

DB2的查询优化器使用QGM作为优化的输入。优化器工作是基于代价的，并使用一个可扩展、规则驱动的决策系统框架。可以配置成在不同优化级别上进行代价决策。在最高级，使用一个动态程序设计算法来计算所有查询计划，并挑选代价最小的计划。在中级，优化器不再考虑特定的计划或者访问方法，也就是不再考虑TBSCAN、IXSCAN、LPREFETCH、IXAND 和 IXOR等操作，并且也不再考虑重写规则。在最低级的优化处理中，DB2优化器采用贪心启发法选择一个较好但是不一定是最佳的查询计划。优化器参照系统资源评估，并依据统计信息估计相关查询操作的基数及选择性。最终优化器将查询计划转化成查询操作符的线程和相关数据库管理系统内部的数据结构，让数据库管理系统的处理引擎执行。

备注1：DB2优化器使用查询处理操作的细节模型来获取对I/O和CPU开销的精确估计。依赖统计数据估计操作的基数及选择性。并且DB2允许用户生成列级分布的直方图以及runstats工具将列进行组合。细节直方图包含了最常出现的值以及属性的基本分位数表示的频度分布。

四、     总结

通过IBM DB2中基运算以及中间运算的访问方式的分析，我们在数据库管理系统的查询编译器中明确了关系代数表达式在查询编译器查询处理流程中的位置，明确了关系代数表达式在查询优化过程中的应用场景以及查询优化过程中的理论依据。为应用系统建设过程中，查询语句优化、查询优化的提供理论参考。