文档-关系数据查询执行技术研究与实现*

马志程，袁海峰，谷 洋，刘亚茹，张 孝+

1.国网甘肃省电力公司电力科学研究院，兰州 730070

2.数据工程与知识工程教育部重点实验室（中国人民大学），北京 100872

3.中国人民大学 信息学院，北京 100872

1 引言

近年来，数据已经渗透到当今每一个行业和业务职能领域，成为重要的生产因素。人们对于海量数据的挖掘和运用，预示着新一波生产率增长和消费者盈余浪潮的到来[1]。关系数据库是数据管理中不可或缺的技术，尤其在涉及到用户、财物等需要精细管理的应用领域时，更是具有不可替代的地位[2]。但是传统的关系型数据库在大数据背景下存在一些技术缺陷，尤其是在速度、存储量以及多样化结构数据的处理问题上存在一些短板。目前的大数据应用中包含的数据类型是多种多样的，既可以是结构化的关系数据与图数据等，还可以是JSON（Javascript object notation）、XML（extensible markup language）等半结构化数据，甚至是网页、视频等非结构化的数据[3]。数据模型是一个数据管理系统的核心，纯关系模型已经无法灵活地管理多种类型的数据。其次，在包含大量节点的集群中，高速处理海量数据也是一个难点。再次，在关系数据库上无法完成对数据的复杂分析[4]。

进入大数据时代之后，已经无法使用某种单一的数据库管理系统来完成所有应用的数据管理。和关系数据库不同的是，文档数据库往往是把某个对象的所有信息全部存储在一个集合中，并且集合中的每个对象的内部结构无需完全相同，这种设计思想极大地简化了从外部对象到数据库对象的映射处理[5]。NoSQL（not only structured query language）数据库目前处于百花齐放的状态，由于存储模式的不同，也没有提供统一的查询语言，也因此导致了NoSQL 数据库没有统一的数据访问接口[6]。需要一种更加开放的数据库管理系统。将具有丰富多样的数据类型的数据在同一个数据管理系统中进行存储、组织与管理。这也就意味着单一的数据库引擎必定无法完成数据的统一访问，需要能够容纳与支持多种数据模型的处理引擎并存于系统中。在异构数据的自适应存储前提下（即不同结构的数据可能被独立存储在不同的数据库中，或者为了更好地服务于查询，同样语义的数据被冗余地存储于不同结构的数据库中），如何基于关系数据库的架构融入NoSQL数据库引擎，怎样面对用户定义的操作，如何针对不同引擎的查询特点来实现跨引擎的查询以及如何处理大数据管理系统中的查询表达与查询优化并提高查询性能，是构建能容纳和支持多种不同结构数据处理引擎并存的大数据管理系统需要考虑的重点问题。

基于以上的研究背景，启动了将关系型数据库和NoSQL数据库进行集成的通用性大数据管理平台DataCloud 项目的研究设计。本文的研究是Data-Cloud 大数据管理平台的一个子课题。本文研究了关系型数据库和NoSQL文档数据库融合的查询处理技术，实现了一个执行引擎ENTIA，将支持结构化数据和半结构化数据的两种不同的数据库引擎集成在同一大数据管理系统中，提供统一的访问接口，来完成混合引擎的查询处理，并基于启发式规则完成部分查询优化功能，为构建支持多种数据模型的通用性大数据管理系统奠定基础。

此外，本文的研究内容也对解决实际工程中的问题，提高开发效率具有很重要的意义。由于NoSQL数据库采用非规范统一的存储方式，即一种数据库只服务于一种数据库类型，导致截至目前仍然没有统一的查询表达来访问所有的NoSQL数据库。在实际的项目开发中，当需要同时访问关系数据库和NoSQL 数据库时，往往需要程序员针对不同的数据库引擎分别创建连接，用相应的数据库引擎定义的查询语言给出查询请求，在获取各个处理引擎返回的查询结果之后，再以代码的方式手工合并各部分结果从而完成整体的功能需求。这种处理方式不仅要求程序员需要掌握多种数据库的查询语言，还增加了研发的工作量，降低了开发效率。此外，无法充分基于数据、查询与数据库引擎本身的特性来对整体查询做进一步的优化。

本文的主要贡献如下：

（1）系统地介绍了执行引擎ENTIA 的整体架构与设计实现。ENTIA包含四大模块：查询解析模块、查询优化模块、查询翻译模块和查询执行模块。并具体地阐述了各个模块的功能与实现原理。

（2）提供了统一的数据访问接口。设计了全局视图来屏蔽底层数据的结构类型与物理存储的位置，并基于此定义查询语言，使得用户仍然采用熟悉的SQL（structured query language）来完成包含一种或多种存储引擎、多种数据模型的混合查询，大大提高了开发效率。

（3）基于启发式规则进行查询优化。在数据冗余存储的前提下，将原查询分解成若干子查询，进而把计算推向合适的存储引擎，充分利用各数据库引擎的查询优势，从而提高整体查询的性能。

（4）进行充分的实验，并对实验结果进行分析。通过实验证明：与传统方案对比，多引擎、多数据模型下的混合查询在保证查询结果正确的前提下，不降低查询性能，证明了方法的正确性；与任一单独数据库的查询性能进行对比，表明了优化方法对数据库性能提升的有效性。

2 相关工作

异构数据库集成的研究初期是以外部数据的管理开始的。Melton 等提出了一种称为SQL/MED 的架构设计[7]。MED 的含义是Management of External Data。SQL/MED 提供了对SQL 语法的扩展，以及一组用于开发和管理访问SQL 数据和NoSQL（也称为外部）数据的应用程序的例程。SQL/MED 可以分为两大部分。第一部分称为包装接口（wrapper inter-face），提供了可以查看由一个或多个外部服务器上外部数据的功能。外部数据可以存储在文件系统、HTML 格式的网页、XML 文档或其他一些专门的存储库中[8-9]。SQL/MED 的第二部分称为数据链（data-links），它提供了一些工具，使一个SQL Server能够控制对驻留在一个或多个文件系统中的数据的引用完整性、恢复和授权的管理。

Tatemura等给出了一个原型系统Partiqle[10]，它将SQL引擎集成在基于键值存储NoSQL数据库HBase之上，以达到支持关系数据库中的OLTP（on-line transaction process）特性的目的。在这个原型系统中，重点研究了如何将关系数据库中的事务引入到HBase 中。Partiqle系统定义了一种“事务类”的声明规范，来约束工作负载中的事务。给定一个SPJ（select-project-join）查询，系统的编译模块会基于键值存储的查询优化器之上产生一个新的执行计划。执行引擎和事务管理器会以一种乐观的并发控制方式来执行此查询计划。所谓乐观的并发控制方式就是，系统会缓冲写操作，来提交HBase中的check-and-put的原子操作[10]。

Vilaça 等针对NoSQL 数据库中的查询需要手工编写的缺陷[11]，在HBase 基础之上集成了SQL 的引擎。在保留了NoSQL数据库的高可扩展性与模式灵活性的前提下，融入了SQL 查询，为NoSQL 数据库增加了原来所不能支持的一些操作符，比如join等[12]。文中采用的方法是重写关系数据库的内部架构，在保留一部分原来组件的基础之上，增加了NoSQL 数据库的部分组件。查询处理器将以SQL表达的访问请求进行翻译、编译和执行，同时包括底层存储的数据类型、存储模式、索引以及各类操作符的一系列转换，最终完成数据查询[13]。该研究中采用了开源、轻量级用Java 编写的Apache Derby 数据库和HBase 来作为NoSQL数据库[11]。

无论是同构数据库的集成还是异构数据库的集成，数据模式都是非常核心与具有挑战性的研究工作。Mason等在研究如何集成同构数据库时提出了一种基于“注解”的方法来动态地生成全局语义视图[14]。“注解”方法将复杂的语义识别任务转移到局部注释器而不是全局集成器，从而消除了全局视图构建的瓶颈。这使得集成更加自动化、可扩展和可快速部署。数据源管理员使用有意义的名称（可能使用本体）对架构进行注释，并在XML文档中导出具有注释的架构设计。系统会加载每个单独的注释，匹配注释中的名称以生成集成视图，然后标识用于跨数据库连接全局键，最终得到一份数据模式的全局视图[15]。

3 查询引擎的实现

本章将系统阐述基于关系型数据库PostgreSQL和NoSQL 数据库MongoDB 所实现的执行引擎ENTIA 的架构设计，分析各个关键模块的功能与实现细节。并以具体实例介绍如何通过该引擎来完成异构数据库的混合查询。

3.1 ENTIA的系统架构

ENTIA 主要用于解决在集成关系数据库与NoSQL数据库的系统中的查询处理问题。该引擎包含查询解析、查询优化、查询重写和查询执行四个模块，其系统架构如图1所示。

Fig.1 Architecture diagram of ENTIA system图1 ENTIA系统架构图

从图1 中可以看到，不同的客户端应用通过ENTIA提供的统一访问接口来向服务器发出查询请求。查询解析模块与元数据模块协作完成查询请求的解析工作，其中元数据模块存储着多源异构数据库的数据模式的全局视图，查询解析后的结果以Java对象的形式来表示。查询优化模块基于解析后的结果与元数据信息给出执行效率最高的查询计划。根据优化器给出的查询计划，查询翻译模块会将原本的查询进行翻译，即以SQL 表达的查询请求转换为该查询计划中所参与的各个数据库引擎所能识别接受的查询语言，最终给出与用户原查询等价的查询任务列表。查询执行模块负责接收所有查询任务，并给出最终的查询结果。查询执行器集成了不同数据库引擎的访问驱动，它既可访问关系数据库，又可访问NoSQL数据库。查询执行器将查询任务进行分发，不同数据库引擎执行各自查询任务，各数据库引擎完成查询后，将查询结果全部返回给查询执行器，查询执行器完成全局的连接工作，得到最终的查询结果，返回给客户端。

从ENTIA 的架构中能够看出，该引擎主要从三方面来实现跨引擎的混合查询：首先，查询执行模块向上提供了统一的数据访问接口，从而屏蔽了存储层数据存储的不一致。一份完整的数据既可部分存储在关系数据库，部分存储在NoSQL数据库，也可以不同的结构冗余存储在多种数据库中。无论采用怎样的存储策略，向上的访问接口是一致的。其次，混合查询使用全局数据模式和统一的查询优化器来保证查询的正确性和性能。再次，向客户端提供统一的查询语言，在查询表达层做到了统一和规范。

3.2 全局视图设计

全局视图的设计主要是为了解决底层各个数据库引擎存储模式之间的差异问题。

全局视图中，每一个数据元素都有两个名称：一个是该数据元素的“原始名称”；另一个是该数据元素在全局视图下的“语义名称”。“语义名称”并不具有唯一性，不同的数据元素可能具有相同的“语义名称”。针对“表”或者“集合”，全局视图会给出“语义名称”“数据源”“数据库”“数据域”“主键”“外键”共六个属性。“数据源”为该表或集合的存储引擎。“数据库”为该表或集合所属的数据库名称。“数据域”为该表所包含的字段或属性。主、外键属性用来完成多表之间的连接操作。针对数据库元素中的“字段”或者“属性”，全局视图会给出“字段名称”“语义名称”和“数据类型”三个属性。全局视图由数据库管理员生成，以JSON文件的形式保存在系统中。当系统中任意一个数据库引擎的数据模式发生变化时，需要更新JSON 文件来保持全局视图与各个数据库引擎之间的同步。ENTIA系统中的全局视图设计示例如下所示：

3.3 查询语言设计

本文中的研究内容暂时只支持数据查询语言（data query language，DQL）[16-17]。由于MongoDB 中没有数据模式的概念，ENTIA 所支持的SQL 是基于全局视图中的语义名称来构成。其基本语法如下：

SELECT[ALL|DISTINCT]<全局视图-目标列表达式>[,<全局视图-目标列表达式>]……

FROM<全局视图-表名>[,<全局视图-表名>]……

[WHERE <条件表达式>]

[GROUP BY<全局视图-列名1>[HAVING<条件表达式>]]

[ORDER BY<全局视图-列名2>[ASC|DESC]]

3.4 查询实例

本节按照查询处理的顺序来介绍ENTIA对用户的访问请求的处理流程。以查询Q3.1为例：

其中，字段name、stars 存储在PostgreSQL 中，属性attribute存储在MongoDB中。

ENTIA 收到查询之后，首先会基于JSqlParser 对查询进行解析，生成一个代表该SQL 查询的Java 对象ParseNode。

针对Q3.1，ENTIA 的查询优化模块给出的逻辑查询计划如图2所示。

Fig.2 Logical plan query diagram of Q3.1图2 Q3.1逻辑计划查询图

4 查询优化

4.1 查询优化概述

在跨引擎的混合查询中，如何将计算任务合理地分配到每一个数据源直接决定了结果的正确性与查询效率。本节中的查询优化的目标就是基于优化规则，把数据推向合适的计算引擎，将查询任务尽量下推到各个数据库引擎，而针对分离后的查询子任务的更为具体的查询计划则是由各个数据库引擎给出。查询优化的策略是由用户查询的特点与数据的存储情况所共同决定的。

在混合存储引擎系统中，数据的存储情况在字段的粒度上可分为冗余存储与非冗余存储两种情况。非冗余存储是指，字段被唯一地存储于众多数据库引擎当中的某一个数据库引擎中，该字段的数据仅此一份。冗余存储是指，字段在至少两个甚至多个数据库引擎中都有所存储，该字段拥有多份不同结构类型的数据，虽然存储形式不同，但所表达的语义相同。

用户的查询特点是查询优化中优化策略的另一决定因素。经前期实验测试：与PostgreSQL 相比，MongoDB在聚合操作与选择全表扫描策略时的字段投影操作具有明显的查询优势，而在表连接的操作上，性能远不如PostgreSQL。此外，数据查询语言DQL中，不相关子查询是较为具有代表性、更容易解析与判断的复杂查询。因此基于前期的实验结论，当用户的查询中具备上述特点时，ENTIA 可对此类查询进行优化。

图3 是ENTIA 查询优化模块的工作流程图。目前ENTIA能够优化的查询为包含聚合操作或者全表扫描操作的不相关子查询。ENTIA根据查询解析之后的ParseNode以及数据存储的元信息进行判断：用户查询的所有数据是否冗余存储，若非冗余存储，则进一步判断当前查询是否为跨引擎查询。若数据全部存储在某一引擎中，显然该查询会被完整地在该引擎中完成，若查询是跨引擎的混合查询，查询模块将分离原查询中各个操作符，使得各引擎单独完成分解之后的查询，并保证各部分查询之后返回的结果与用户的原请求查询等价。当查询数据被冗余存储在不同结构的数据库引擎中时，需要进一步判断是否为可优化的查询。若不满足可优化规则，则ENTIA统一将查询交由PostgreSQL来完成。若满足优化规则，再根据查询中是否包含聚合操作，或者全表扫描操作来选择对应的规则进行优化。

4.2 优化规则

4.2.1 聚合操作规则

规则1（聚合操作规则）由于MongoDB 中聚合操作采用管道流水线来处理管道中的一个个功能节点，大大提高了聚合操作的效率，其性能远远高于PostgreSQL。因此，聚合操作优化规则是指当查询符合以下形式时：

即，如果整体查询为不相关子查询，并且子查询中包含聚合操作，那么该查询会被分解成两个子任务：子查询被重写为MongoDB 查询，外层查询仍然由PostgreSQL 执行，两个子任务并行执行，两数据库引擎返回各自查询结果，最后连接两部分查询结果得到用户原查询的结果。其中，含有聚合操作的子查询重写为MongoDB查询的方式为：

Fig.3 Query optimization workflow of ENTIA图3 ENTIA查询优化的工作流程图

聚合操作优化规则的伪代码如算法1所示。

算法1聚合操作优化规则

输入：参数1，形式为包含聚合操作的不相关子查询；参数2，保存全局视图的JSON文件的路径。

输出：重写后的PostgreSQL查询和MongoDB查询。

4.2.2 全表扫描规则

经过前期的实验测试，当查询请求的执行计划为全表扫描时，MongoDB 的查询速度要远远快于PostgreSQL 的查询速度。因为在MongoDB 中，当数据库启动时，会将磁盘的数据加载到内存中，充分利用系统的内存资源，磁盘的I/O效率与内存的查询导致两者查询速度的差异自然十分明显。全表扫描优化规则是指，当查询符合以下形式时：

即整体查询为不相关子查询，子查询的查询计划是全表扫描操作时，该查询可被进一步优化，原查询被拆解成两部分执行，子查询被重写为MongoDB 的查询，外层查询仍然交给PostgreSQL来执行，两引擎并行执行各自的查询任务，最后将返回的两部分查询结果连接起来完成原来的查询任务。其中子查询被重写为MongoDB的查询的形式为：

在MongoDB 中查询条件是由多个键值对的形式来表达的，将多个查询条件组合在一起，即完成了“条件1 AND 条件2 OR 条件3”的表达。键为列名、值为1的形式用来表示此列被投影出来，与SQL中的project语义相同。另外，在对当前查询判断是否符合全表扫描优化规则时，在程序中需要基于EXPLAIN SQL 来获取该子查询的查询计划，再进一步判断是否由全表扫描操作完成。全表操作优化规则的伪代码与算法1类似。

5 实验分析

5.1 实验说明

5.1.1 实验环境

实验在普通PC 机上进行，基本的硬件配置如表1所示。

Table 1 Hardware configuration表1 硬件配置

5.1.2 实验数据集

本实验所使用的数据集是美国最大的点评网站Yelp 所公开的内部数据集。该数据集的内容是Yelp所涵盖的商家数据、用户数据和点评数据的一个子集。目前Yelp 提供了这个数据集的JSON 文件。该数据集被广泛用于自然语言处理和情感分析、数据库、图像挖掘等领域。本文将该数据集的JSON格式数据存储于MongoDB 中，共有business、user 和rev-iew三个集合。利用该JSON文件生成结构化的关系数据，存储于PostgreSQL 数据库中。三个集合（表）的数据量分别为20 万条、150 万条、600 万条记录。为进一步测试，根据原有数据，为每一个集合（表）又进一步生成了两倍数据和四倍数据。

5.2 前期实验

本节介绍优化规则设定的前期实验，证明优化规则设定的合理性。本节的实验从单字段查询、表连接查询、聚合操作查询三方面，对比关系数据库PostgreSQL 和文档数据库MongoDB 在简单查询上的查询性能。

（1）单字段查询

单字段查询从整型、字符型、日期型、JSON 字符串类型四种数据类型测试。测试所使用的查询实例如下：

PostgreSQL 与MongoDB 在以上查询上的时间消耗与对比分别如表2 和图4 所示。在单字段上的简单查询以及聚合操作上，MongoDB 的性能远高于PostgreSQL，但是当涉及到表连接操作时，哪怕是简单的两表连接，PostgreSQL的查询性能远高于Mongo-DB的查询性能。

Table 2 Simple query time consumption of PostgreSQL and MongoDB表2 PostgreSQL 与MongoDB 简单查询时间消耗

Fig.4 Comparison of simple query time between PostgreSQL and MongoDB图4 PostgreSQL 与MongoDB 简单查询时间对比

5.3 功能符合型测试

本实验的目的是测试执行引擎ENTIA对既涉及MongoDB 又涉及PostgreSQL 的混合查询的查询处理的正确性，通过与传统方法的查询结果与查询时间对比，证明ENTIA 对跨引擎查询处理的可行性。本实验中采取的查询实例为查询Q3.1。针对Q3.1，传统的解决思路是，程序员手动分别写出PostgreSQL与MongoDB 两个查询，分别向两个数据库引擎发送查询请求，获取两部分查询结果之后，再手动连接两部分结果，得到最终的查询结果。

将查询Q3.1访问的表business以及集合business的元组（文档）数量N分别设为20万、40万、80万组，对ENTIA 的执行情况与传统思路各测试10 次，记录时间（单位为ms），并取平均值。ENTIA 与传统方法分别使用ENTIA-U 与TRAN-U 表示，其查询时间对比如表3所示。

Table 3 Query time comparison between ENTIA and traditional method表3 ENTIA与传统方法查询时间对比

从表3中可以看出，两种方法的查询时间几乎相同。ENTIA由于要将混合查询进行解析、重写，进而再分发给相应的数据库引擎查询，因此在查询时间上要略大于传统思路的查询时间，两种方法性能差在0.15%左右，在可接受范围之内。但是ENTIA大大提高了程序开发效率，降低了程序员对数据库能力的要求，通过访问ENTIA的接口即可完成跨引擎查询。

5.4 性能测试

本实验的目的是测试可优化查询在PostgreSQL、MongoDB以及本文提出的基于启发式规则的优化方法的查询时间，对比三种方法的性能，验证两种优化方法的正确性和效果。

将上述查询实例访问的表（集合）business、user和review 的元组（文档）数量N分别设为（20 万、150万、600万）、（40万、300万、1 200万）、（80万、600万、2 400 万）三组数据，对PostgreSQL、MongoDB、ENTIA 的执行情况各测试十次，记录时间（单位为ms），并取平均值。基于聚合操作优化规则的性能对比结果如表4所示，基于全表扫描优化规则的性能对比结果如表5所示。

Table 4 Performance comparison based on aggregation operation optimization rules表4 基于聚合操作优化规则的性能对比结果

Table 5 Performance comparison based on full table scan optimization rules表5 基于全表扫描优化规则的性能对比结果

图5为基于聚合操作优化规则下，可优化查询在三种引擎中的查询性能对比图。从图5中可以看出，每个数量级下ENTIA的执行均具有明显的优势。其次，由于MongoDB 在聚合操作上的查询性能较高，每个数量级下MongoDB 的查询时间均少于Post-greSQL 中的查询时间。重写后的查询，充分利用MongoDB 聚合操作的查询优势，各引擎并行执行查询任务，大大提高了查询效率。

Fig.5 Performance comparison graph based on aggregation operation optimization rules图5 基于聚合操作优化规则的性能对比图

图6为基于聚合操作优化规则下，ENTIA相对于PostgreSQL和MongoDB性能提升的趋势图。从图6中可以看出，随着数据量的增大，性能提升的效果越来越明显。ENTIA使PostgreSQL避免了执行聚合操作，使MongoDB避免了执行NoSQL数据库所不擅长的连接操作。随着数据量的增大，对于包含聚合操作的不相关子查询而言，聚合操作所耗费的时间要远远大于连接查询所耗费的时间，也因此，ENTIA相对于两种数据库引擎而言，性能提升越来越明显，且相对PostgreSQL的性能提升要高于相对于MongoDB的性能提升。

Fig.6 Performance improvement trend graph based on aggregation operation optimization rules图6 基于聚合操作优化规则的性能提升趋势图

Fig.7 Performance comparison graph based on full table scan optimization rules图7 基于全表扫描优化规则的性能对比图

图7为基于全表扫描优化规则下，可优化查询在三种引擎中的查询性能对比图。从图7中可以看出，每个数量级下ENTIA的执行均具有明显的优势。分析可优化查询的查询计划，时间耗费为子查询中的全表扫描操作和两表的Join 操作。当执行计划为全表扫描时，其MongoDB 的查询速度远远快于在PostgreSQL 中的查询速度。因此，将子查询重写为MongoDB的查询，大大提高了整个查询的速度。

图8为基于全表扫描优化规则下，ENTIA相对于PostgreSQL和MongoDB性能提升的趋势图。从图8中可以看出，随着数据量的增大，性能提升效果越来越明显。ENTIA 避免了执行MongoDB 所不擅长的连接操作与PostgreSQL在大数据量下的全表扫描操作。由于表与表之间的连接操作所耗费的时间性能的因素比单字段查询所耗费的时间性能因素更加明显，导致ENTIA相对MongoDB的性能提升要高于相对于PostgreSQL的性能提升。

Fig.8 Performance improvement trend graph based on full table scan optimization rules图8 基于全表扫描优化规则的性能提升趋势图

6 结束语

本文基于关系数据库PostgreSQL和文档数据库MongoDB 对查询处理进行探索研究，实现执行引擎ENTIA，给出了混合查询的查询处理，并基于启发式规则对混合引擎进行查询优化，提高了查询效率。在未来的研究工作中，希望进行扩展，加入更多NoSQL数据库，使系统支持更加丰富的数据类型。

致谢本文工作得到国家电网有限公司科技项目（合同号：SGGSKY00FJJS1900296）的部分支持，也得到了中国人民大学信息技术与管理国家级实验教学示范中心的部分支持。感谢审稿专家们的宝贵修改意见和建议，同时感谢中国人民大学数据工程与知识工程教育部重点实验室人大行云云平台为本论文项目提供的实验环境。