一种面向海量分布式数据库的嵌套查询策略

裴欧亚， 刘文洁， 李战怀， 田 征

（西北工业大学 计算机学院，西安 710129）

0 引 言

随着云计算、Web2.0等技术的进一步发展，NoSQL数据库不断发展壮大.NoSQL数据库放弃了传统关系型数据库严格的事务一致性和范式约束，采用弱一致性模型，支持分布式和水平扩展，满足了海量数据管理的需求.

为了信息安全及降低数据库系统升级维护费用，国内银行开始推进“去IOE化”战略.NoSQL数据库相较于传统关系型数据，具有超高的性价比和良好的可扩展性.这些特质促使NoSQL数据库成为国内银行业应对海量数据的首选数据库.

OceanBase是阿里集团研发的一个海量分布式关系数据库系统，采用了NoSQL数据库的架构，基于横向扩展模式，可以通过动态在线增加／减少服务器的方式调整系统负载，具有良好的可扩展性.而且，系统实现了关系数据库的重要特征，支持SQL语言查询，相对于其它的NoSQL数据库，更好地满足了金融业务的需求.

OceanBase的可扩展性、标准SQL查询和事务的强一致性功能，在应对银行业的金融业务上，具有很大优势.金融业务的一个特点是大量使用嵌套子查询，但是目前，OceanBase只支持简单的非嵌套的SQL，对于复杂的的嵌套子查询尚未实现，因此阻碍了金融业务的导入.

本文通过分析OceanBase的架构及现有查询策略，提出了一种基于BloomFilter和HashMap的子查询实现策略，以改进现有查询策略在查询性能上的不足和SQL功能上的缺陷，为金融业务提供更好的支持.实验验证该策略与现有的Oceanbase的查询策略相比，能更好提高查询速度并支持大数据查询.

1 相关研究进展

嵌套子查询是标准SQL的一个非常重要的功能.正是由于嵌套层数的任意性，才使得标准SQL具有强大的功能.

为了支持嵌套子查询，传统的关系数据库做了大量工作.IBM的WON KIM最早于1982年将嵌套SQL分为不同的嵌套类型，并为每一种嵌套类型提出了转化算法，将嵌套SQL尽可能转换为等价的非嵌套SQL，提升查询性能［1］.加州大学伯克利分校的Harry K T Wong对WON KIM的转换算法进行了研究，发现了转换算法中关于聚合函数和数据重复计算的BUG，并给出了改进的转换算法［2］.WON KIM和Harry K T Wong的研究主要集中在重写SQL，即将嵌套子查询改写为等价的非嵌套查询，为SQL重写技术的研究奠定了重要基础.突飞猛进的并行计算技术促进了SQL查询优化的另一个研究分支－查询分解策略，即将查询SQL按一定的策略拆分为一系列可并行执行的子查询.Kim，T.K等人充分利用网格计算和集群计算的并行能力，将嵌套子查询拆分为多个子查询，子查询被分发至网格／集群的不同节点并行执行［3－5］.Kang，Y.J等人同样提出了复杂SQL分解策略，并构建了多linux PCs的OLAP引擎HyperDB.TPC－R benchmark测试验证了HyperDB的优异性能［6］.

NoSQL数据库为了追求查询的高性能，都不内置支持嵌套子查询功能.NoSQL将嵌套子查询留给应用层实现，主要采用MapReduce框架实现［7－8］.但是，也有一些NoSQL系统提供了比较好的机制来实现复杂查询，例如，MongoDB可以设定复杂的查询条件［9］.部分NoSQL系统通过运行MapReduce，或者与Hadoop结合来支持大规模数据分析［10］.

OceanBase为了高效查询，只支持简单的非嵌套SQL，包含IN后接确定值的查询SQL.OceanBase的Filter条件过滤方式是逐一比对，因此如果表扫描策略为GET，在有主键索引的条件下，逐一比对不会耗费大量时间，具有很高的性能.但是如果表扫描策略为SCAN，数据表的每条记录都会和Filter过滤条件逐一比对，会耗费大量的时间，性能较差.除此之外，OceanBase不支持子查询，嵌套SQL的实现只能由应用程序负责，这不仅不方便使用，还耗费大量时间.

本文基于OceanBase的架构及设计思想，提出了一种基于HashMap和BloomFilter的嵌套子查询实现策略：当子查询结果集不大于阈值K时，直接将结果集绑定至主查询的Filter内，按OceanBase现有策略即可处理，其性能取决于OceanBase现有查询策略的性能，因为当阈值K足够小时，不大于K的子查询结果集的绑定耗时可忽略不计；当子查询结果集大于K时，启用BloomFilter和HashMap，BloomFilter和HashMap的构建会耗费一些时间，但是BloomFilter和HashMap在数据检索方面具有非常高的效率；当表扫描策略为SCAN、子查询结果集大于K且小于OceanBase现有的IN上限时，假定结果集大小为N，嵌套查询策略只需经过数次计算即可判定一行记录是否符合要求，而OceanBase现有的查询策略则需要每条记录平均比对N／2次（最差情况N次，最好情况1次）.因此在子查询结果集较大时，嵌套查询策略具有较好的性能.

2 OceanBase现状

2.1 OceanBase架构

OceanBase的整体架构如图1所示.

图1 OceanBase整体架构图Fig.1 Architecture of OceanBase

OceanBase根据其设计目的，并结合淘宝业务特点，采用了“主—从”系统架构.

主节点，即RootServer，唯一，管理集群中的所有从节点服务器，子表数据分布以及副本管理.为了规避单主节点宕机的风险，RootServer采用了一主一备的结构，主备之间采用数据强同步策略，并通过心跳实现软件高可用性.

从节点被分为以下三种类型的节点：

（1）更新服务器，即UpdateServer，唯一，存储增量数据，其实现类似单机的内存数据库，高效支持跨行跨表事务.为了保证高可用性，UpdateServer同样采用了一主一备的结构.为了保证系统的高性能，UpdateServer主备间可配置不同的模式，异步模式主要用于异地容灾，异步模式支持最终一致性.

（2）基线数据服务器，即ChunkServer，多台，存储基线数据.

（3）合并服务器，即 MergeServer，对外提供标准的SQL访问接口，对内合并多台ChunkServer返回的数据集.

2.2 OceanBase现有查询策略

Oceanbase将数据分为基线数据和增量数据，分别存储在ChunkServer和UpdateServer.对于任何一次查询SQL请求，OceanBase都需要执行ChunkServer和MergeServer相关数据的合并.

OceanBase关于查询SQL的数据库结构如图2所示.

图2 Oceanbase数据库功能层整体结构Fig.2 Overall structure of OceanBase database function layer

用户通过MySQL客户端、ODBC等方式将SQL请求发送给某台MergeServer，MergeServer的MySQL协议模块从SQL请求中解析出SQL语句，并交给MS－SQL模块进行词法／语法解析，并生成逻辑计划和物理计划.MergeServer首先根据物理计划定位请求的数据所在的ChunkServer，接着将物理计划发往相应的ChunkServer.每个ChunkServer调用各自的CS－SQL模块完成SQL查询.如果需要增量数据，ChunkServer的CS－SQL模块自动从UpdateServer读取修改增量，完成增量数据与本地基线数据的融合.ChunkS－erver最终将查询结果返回给请求的MergeServer.MergeServer的CS－SQL模块执行多个ChunkServer返回结果的合并，获取最终结果.

OceanBase支持的SQL语句比较简单，绝大部分针对单张表格，只有很少一部分操作涉及多张表格，例如join操作.OceanBase目前只对主键有索引，OceanBase表扫描策略分为GET和SCAN两种，GET策略当且仅当过滤条件包含全部主键列时启用.SQL执行本地化亦是OceanBase查询策略的基本设计原则，即尽量支持SQL计算本地化，保持数据节点和计算节点一致.

3 基于OceanBase的嵌套IN子查询策略

本文主要针对非相关的嵌套IN子查询.非相关的嵌套IN子查询是指外查询依赖于内查询，内查询不依赖外查询且可以独立先执行（下文的嵌套查询策略就是嵌套IN子查询策略）.

嵌套查询策略包含：嵌套查询SQL的查询树构建；查询树的执行引擎；两阶段数据过滤.

3.1 查询树

策略没有采用传统关系数据库的SQL重写技术，而是采用“内查询先执行，外查询绑定内查询的结果（集）后执行”的方案.该方案实现简便，而且相较于SQL重写技术，降低了传送到MergeServer的数据量，节省了带宽，减小了嵌套查询对并发查询的影响.

查询树的节点的部分主要数据结构如下.

注：phy内保｝存子节点执行结果填充位置标记；phy内的位置标记和next＿child一一对应.

查询树可以借助传统关系型数据库的SQL语句解析结果进行构建.示例嵌套SQL和其查询树如图3所示.

图3 示例SQL及其查询树Fig.3 Sample SQL and its query tree

3.2 执行引擎

执行引擎的主要功能就是按照一定的策略执行查询树.依据策略构建的查询树，具有“兄弟节点相互独立”和“父节点依赖子节点”的特性.查询引擎根据查询树的特性，采用从叶节点到根节点的递归计算算法.

递归算法如下：

算法的核心：串行执行每个节点；除根节点外，每个节点执行结束，将本节点从查询树移除，以确保查询树的正确执行.

算法中的threshold控制着是否启用HashMap和BloomFilter.threshold为可变参数，可变化范围为（0，511］，因为OceanBase的IN操作符支持的操作数上限不大于511组.当子查询结果集不大于threshold时，直接将子查询结果集写入主查询的物理计划内，接下来的物理计划的执行等处理遵循OceanBase现有的查询处理流程.当子查询结果集大于threshold时，将主查询的物理计划连同子查询结果集生成的BloomFilter一起发送至ChunkServer处理，MergeServer利用子查询结果集生成的HashMap过滤以获取最终的结果集.

3.3 两阶段数据过滤

两阶段数据过滤：首先ChunkServer进行非严格的BloomFiter过滤，获得最终结果集的超集；其次MergeServer进行严格的HashMap过滤，获得最终结果集.

两阶段数据过滤如图4所示.

图4 两阶段数据过滤Fig.4 Two－phase data filtering

ChunkServer进行数据表扫描时，每读取一行，都执行BloomFilter检查，检查通过则发送至MergeServer，否则继续读取下一行，直至读取完毕.MergeServer对ChunkServer发送来的每一条数据，都执行HashMap过滤，将过滤生成的结果返回给用户.因为BloomFilter的固有的误报特性，ChunkServer发送给MergeServer的结果集是包含最终结果集的超集，因此MergeServer必须进行一次严格过滤，去除误报记录，获取最终结果.

3.3.1 BloomFilter过滤

分布式架构下，将作为主查询过滤条件的超大的子查询结果集分发至不同的数据节点的方案会占用大量传输带宽.为了降低带宽占用率且加速查找，嵌套查询策略使用了一种多哈希函数映射的快速查找数据结构——布隆过滤器.相较于其他的数据结构，布隆过滤器在空间和时间方面都有巨大的优势，特别适合于海量数据集的表示和查找.

策略所构建的BloomFilter采用如下的公式：

其中p：误判率.m：位数组大小.n：总数据数目.k：所需哈希函数数目.

BloomFilter的构建由MergeServer负责，构建算法如下.

Input：子查询结果集S

①依据上述公式及S、误报率p（默认），计算BloomFilter所需位数组大小m，所需哈希函数数目k.

②读取S的一条记录R，如果R为NULL，转⑤.

③将R依次带入k个哈希函数H1（R），...，Hk（R）得到k个值V1，...，Vk.

④将BloomFilter的位数组的V1，...，Vk位设置为True，转②.

⑤构建结束，返回BloomFilter.

BloomFilter的查找算法如下.

①读入一条记录R.

②将R依次带入k个哈希函数H1（R），...，Hk（R）得到k个值V1，...，Vk.

③比对BloomFilter的位数组的V1，...，Vk位.如果k个位全为True，则返回查找成功，否则返回查找失败.

3.3.2 HashMap过滤

由于BloomFilter的误报特性，MergeServer得到的结果集是最终结果集的超集.因此MergeServer必须进行严格的数据过滤，以获得最终结果集.

MergeServer严格的数据过滤条件就是海量的子查询结果集.如何组织子查询结果集，以提供高效的查找是一个关乎性能的重要问题.在当今服务器普遍支持大内存的状况下，嵌套查询策略采用全内存的HashMap存储子查询结果集.

HashMap的高效查找依赖于哈希函数的均匀散列和低冲突率.均匀散列保证每一个桶内的数据检索时间大致相同；低冲突率保证快速定位.本文设计的HashMap采用链表法解决地址冲突，链表的每一个节点只保存key.

MergeServer负责构建HashMap，且利用构建的HashMap进行严格的数据过滤.

HashMap的构建算法如下.

Input：子查询结果集S

①初始化HashMap，分配哈希桶空间.

②读取S的一条记录R，如果R为NULL，转⑤.

③将R带入哈希函数H（R），依据得到的哈希值确定待插入的哈希桶BUCKET BT.

④将R以链表的形式挂在BT的链表末尾，转②.

⑤构建结束，返回HashMap.

HashMap的查找算法如下.

①读入一条记录R.

②将R带入哈希函数H（R），依据得到的哈希值确定待查询的哈希桶BUCKET BT.

③遍历BT内的链表节点，逐个比对.如果相同则返回查找成功，否者返回查找失败.

查询树的每一个非叶子节点的执行都需要两阶段数据过滤，即首先根据孩子节点的结果集构建HashMap和BloomFilter，接着将BloomFilter连同本节点的物理计划分发至数据节点，数据节点依据物理计划及过滤条件BloomFilter，将最终结果集的超集返回给MergeServer，最后MergeServer利用HashMap执行最后的严格的数据过滤，获得最终结果集.

4 实验结果

OceanBase单服务器部署.服务器由1T硬盘，16 G内存，16核CPU，一块网卡组成.服务器操作系统是Red Hat6.2，内核是2.6.32－220.el6.x86＿64.

4.1 实验一

该实验衡量小规模子查询数据集状况下嵌套IN子查询策略的性能.测试表test，共计100万条记录，包含id、name共计两个字段，其中id为主键列.启用BloomFilter和Hash－Map的阈值设置为20，即子查询结果集不大于20条.

测试SQL语句模板如下所示.

①：一层嵌套SQL：Select count（＊）from test where［id／name］in（select［id／name］from test Where id＜ConstValue）

②：与①等价SQL：Select count（＊）from test where［id／name］in（ConstValue，ConstValue，...）

①和②等价：如果①的子查询结果和②绑定的ConstValue完全相同.

OceanBase现有查询策略由于不支持子查询，为了和嵌套查询策略作对比，因此执行嵌套子查询的等价SQL，即②形式的SQL.

小规模子查询数据集下，有主键索引的OceanBase已有查询策略性能测试结果及嵌套查询策略性能测试结果如表1所示.嵌套查询SQL已转化为OceanBase支持的非嵌套SQL.

表1 小规模子查询数据集下两种策略的结果，有主键索引Tab.1 Results of two strategies with small subquery dataset，primary key index

小规模子查询数据集下，无主键索引的OceanBase已有查询策略性能测试结果及嵌套查询策略性能测试结果如表2所示.

表2 小规模子查询数据集下两种策略的结果，无主键索引Tab.2 Results of two strategies with small subquery dataset，without primary key index

表1和表2表明：嵌套IN子查询的性能虽然低于OceanBase现有的有主键索引的查询性能，但是却远远高于OceanBase现有的非主键列的查询性能.

4.2 实验二

该实验衡量大规模子查询数据集状况下嵌套子查询策略的性能，实验环境同实验一.大规模子查询数据集下的嵌套查询策略的性能测试结果及Mysql5.1.52的性能测试结果如表3所示.

表3 大规模子查询数据集下嵌套查询策略的结果Tab.3 Results of nested query strategy with massive subquery dataset

表3验证了嵌套IN子查询的高性能，在同等条件下，其耗时远远低于Mysql耗时.

5 总 结

NoSQL数据库内置复杂SQL语句查询功能是一个重要的趋势.本文的主要目的就是提出一种查询策略，用于支持复杂SQL的子集——嵌套子查询，且改进OceanBase现有的查询策略.

嵌套查询策略通过构建查询树和查询引擎实现了嵌套子查询功能.嵌套子查询策略还通过两阶段数据过滤，即HashMap过滤和BloomFilter过滤，改善了OceanBase现有的查询策略，并保证了查询的高效.实验一和实验二结果表明，通过采用嵌套子查询策略，Ocean－Base实现了对嵌套子查询功能的支持，同时其嵌套查询性能优于Mysql的嵌套查询.

当然，嵌套查询策略在小规模子查询数据集且有主键索引的条件下，相较于OceanBase现有策略有明显的性能差异，虽然嵌套查询语句的复杂性是一个重要因素，但是嵌套查询策略在查询优化方面的不足也是一个重要因素.因此，未来的一个重要工作就是优化嵌套查询策略.

［1］ KIM W.On optimizing an SQL－like nested query［J］.ACM Transactions on Database Systems（TODS），1982，7（3）：443－469.

［2］ GANSKI R A，WONG H K T.Optimization of nested SQL queries revisited［C］／／ACM SIGMOD Record.ACM，1987，16（3）：23－33.

［3］ KIM T K，JUNG S H，KIM K R，et al.：HyperDB：A PC－based database cluster system for efficient OLAP query processing［C］／／Proc of 19th IASTED International Conference on Parallel and Distributed Computing and Systems（PDCS2007）.Cambridge，USA（November 2007）.

［4］ KIM T K，OH S K，CHO W S，et al.：A lanlinux－based grid system for bioinformatics applications［C］／／Proc.of International Conference on Advanced Communication Technology（ICACT）.2006，3：2187－2192.

［5］ KIM T K，KIM K R，OH S K，et al.A Hybrid Grid and Its Application to Clustering Orthologous Groups for Multiple Genomes［C］／／Proc International Symposium on Computational Life Science.2006：20－10.

［6］ KANG Y J，TIM T K，YANG K E，et al.：An OLAP query decomposition technique for PC－based database cluster systems［C］／／Proc of the 18th IASTED International Conference on Parallel and Distributed Computing and Systems(PDCS2009).Innsbruck，Austria(February 2009).

［7］申德荣，于戈，王习特，等.支持大数据管理的NoSQL系统研究综述［Ｊ］.软件学报，2013，8：008.

［8］POKORNY Y.NoSQL databases:a step to database scalability in web environment[C]//The 13th International Conference on Information Integration and Web-based Applications＆Services(iiWAS).2011:278-283.

[9]BROWN A，WILSON G.The Architecture of Open Source Applications[M].Lulu.com,2011.