分布式顺序表类SQL技术的实现和优化

摘 要： 针对DOT系统，设计实现并优化了类SQL的查询技术，首先分析了传统数据库在查询上的优化策略，比较了传统数据库和DOT系统在查询方面的异同。通过参考一般数据库的SQL语句的设计规范，为DOT设计了一套类SQL语句。后续对设计的类SQL语句进行词法语法分析，构建查询树。同时，借鉴传统数据库的查询优化策略，结合DOT系统的特点对查询进行优化。最后在开源的ApacheHBase典型的DOT系统的基础上，实现了上述类SQL语句的所有解析和优化内容。

关键词： 分布式顺序表； 类SQL语句； 查询优化； HBase索引优化

中图分类号： TN911?34； TM417 文献标识码： A 文章编号： 1004?373X（2016）15?0103?05

Abstract： Aiming at the distributed ordered table （DOT） system， the SQL?like query technology was designed， implemented and optimized. In this paper， the optimization strategy of the traditional database is analyzed for query， and the query differences between the DOT system and traditional database are compared. Referring to the design specifications of the general database′s SQL statement， a set SQL?like statement was designed for DOT. The designed SQL?like statement is analyzed with morphology and grammar to establish the query tree. In combination with the query optimization scheme of the traditional database and cha?racteristics of DOT system， the query was optimized. All analysis and optimization contents of SQL?like statement were realized based on the open source ApacheHBase.

Keywords： distributed ordered table； SQL?like statement； query optimization； HBase index optimization

0 引 言

网络应用的普及对海量数据的存储和操作处理以及各种处理能力的可扩展性、可靠性和高效性提出了很大的挑战，而现有数据模型和相关技术已不能胜任[1]。为了应对上述挑战，业界提出了NoSQL数据库。这些NoSQL数据库可以模型化为分布式顺序表（DOT）系统，但是DOT系统对SQL规范中查询特性的支持并不完美[2]。

随着网络的发展，数据量出现爆炸式的增长，现有的关系型数据库处理这些大数据已经出现瓶颈。进而有了DOT系统的出现，但现有的DOT系统对SQL查询特性的支持并不是特别的理想[3]。

1 类SQL语句的设计与解析实现

在实现过程中首先根据SQL的设计规范，设计出一套适用于DOT系统的类SQL语句。用户根据类SQL规范提交查询请求，然后系统对类SQL查询语句进行词法分析、语法分析和语义分析，建立原始查询树。最后根据DOT的特点实现查询树的优化。对于语法分析中各操作语句类型的判断，采取保留类SQL语句第一个关键词的方法进行查询类型的匹配来识别具体的查询类型的方法来实现。类SQL语句解析流程如图1所示。

1.1 查询关系式的词法分析

利用有限自动机的方法对识别过程进行建模。通过词法分析自动机对where_list查询条件进行分析后就能够得到查询条件中的所有关键词，然后根据关键字出现的顺序确定输入是否符合语法分析的语法规定。根据需求，本自动机识别的关键字有关系符号、括号、整数、浮点数、字符串值、变量名[6]。

词法分析的结果记录在下面三个数组中：

keyWordList[wordIndex]，记录condition条件中的查询列。

keyValueList[valueIndex]=searSQL.substring（begIndex，endIndex），记录查询列的起始范围的值。

keyValueType[valueIndex]=DataType，记录查询列的范围值的数据类型。

stokenList[listIndex++]，记录condition条件中出现的每一个字符的标记token，token分为五类：逻辑与或非，查询条件列，条件列范围的起始值，范围起始值的类型和比较符号。

1.2 查询关系式的语法分析

类SQL语句和传统的SQL语句类似，包含固定的关键字和各关键字的出现顺序，并且每个关键字所起的引导作用也很清晰。本系统中的类SQL的语法表即是通过正则表达式实现的。语法中定义了类SQL语句的各关键词的出现顺序，并根据不同的关键字触发不同的动作。

在语法分析中还包括对查询条件中括号的匹配。待整个SQL语句的语法语义分析正确后，将语句中涉及的语法正确的tablename，select_list，condition等信息存储到响应的string数组里面。在词法语法分析正确的基础上对SQL语句中涉及的表和列是否存在部分完整性检查，如有错误，即时反馈错误信息。

1.3 查询树的构建

文中类SQL的查询关系式查询树的构建是用二叉查询树构建的。建立的二叉查询树为中序遍历二叉树，通过对查询树进行中序遍历可以得到查询关系式。在查询树的构建中，根据二叉树的特点采用递归算法，先判断出左右子树的范围并完成构建，然后完成其父节点的构建，组成树结构。

2 查询树的优化

DOT系统为分布式结构，所有的数据均存储在集群中，在并行操作中具有很强的性能优势。为了提高查询统计的速度，让查询开启多线程进行并行化查询是较好的解决方案。本文并行化的解决方案是将查询关系式解析成析取范式的形式，程序为每一个析取项启动一个查询线程，首先将查询关系式转化成析取范式矩阵。为了不让并行化执行的查询进程之间出现重复的结果，即并行化执行的析取查询项之间没有交集，最后需要将查询关系式解析成等价的主析取范式矩阵。

2.1 查询关系式并行化优化

2.1.1 查询关系式优化成析取范式矩阵

对整个二叉查询树的优化算法思想为：

（1） 自根节点遍历整个查询树；

（2） 如果没有发现父节点是and节点或or节点则优化完成，程序返回；否则，定义发现的or节点为当前节点，跳转到（3）；

（3） 对当前节点的各个分支按下文中三种逻辑节点（与或非）中的一种进行方式转换，对查询树进行旋转，完成后跳转到（1）。

对查询树的优化采用递归调用的流程来实现，对于每一个节点采用先优化左子树，再优化右子树，后优化当前节点的优化流程。

2.1.2 查询关系式逻辑“或”节点的优化

逻辑“或”节点的优化和逻辑“与”节点的优化不同。它只有当其左右孩子都为数据节点且数据节点为同一个变量的表达式的情况下，逻辑“或”节点才需要进行优化。如图2为整棵树的一部分，节点[B]为逻辑节点，节点[m]和[n]为数据节点，[A]节点为[B]节点的父节点。

因为数据节点[m]和[n]为同一个变量的关系式，这样的话数据节点[m]和[n]与逻辑节点[B]就可能存在合并成一个数据节点[mn]的情况，从而可以简化树结构。例如，[B]节点为“或”节点，[m]节点为[-6

2.1.3 查询关系式逻辑“非”节点的优化

逻辑“非”节点的优化目标是消除非节点，将非节点等价转化成逻辑“与或”节点连接数据节点的形式。在建立查询树时，规定了逻辑“非”节点的孩子为左子树，并且逻辑“非”节点的孩子只是一个节点。根据孩子节点的类型可以将非节点的优化分为两种情况：该逻辑“非”的孩子节点为数据节点；该逻辑“非”的孩子节点为逻辑节点。为便于后续继续优化处理，在本类SQL查询技术中用矩阵表示最终的析取范式，具体实现算法如下：

（1） 读入要转换的树结构；

（2） 若当前节点为“或”节点，则对左右子树分别转入（1）；

（3） 若当前节点为“与”节点，则开始遍历该节点下的所有子节点，组成一个条件的“与”集合；

（4） 作为数组的一行。若当前节点为叶子节点，则当前节点为一个“与”集合；

（5） 最后收集所有的“与”集合，构成所要的析取范式。

2.2 查询关系式算术优化

当一个用户的输入含有冗余的where查询条件，如a>1 or a>3或者b4时，底层根据这些条件也可以执行查询并返回正确结果。对于数据少的情况下，查询速度可以忽略，但当数据量很庞大时，查询的速度就会受影响。本系统中实现的条件冗余优化分为以下几种情形：or节点的左右子节点是同一变量并且变量的数据范围集合有交集；and节点的左右子节点是同一变量并且变量的数据范围有交集；在从析取范式转化成主析取范式的过程中，冗余条件的产生。

具体的实现方法和过程如下：在处理三种逻辑节点“与或非”的过程中，冗余节点的合并剪枝；在析取范式向主析取范式的转化过程中，表示各析取项的数组中，数组行与行之间的重复项的优化和行内析取项的代数冗余优化。

3 多种数据类型查询优化

3.1 Int，Long类型数据的正负号支持优化

Int和Long类型的数据在转换成Bytes之后，会造成所有负数比所有正数大的情况。通过对原有关系式进行变换来保证查询条件在转换成Bytes之后与原数据进行比较的正确性。

为保证查询关系式转换成字节流之后可以直接通过字节流进行比较就能得到正确的结果，将原来的一个关系式单元分成两个关系式单元，并且这两个关系式单元之间是逻辑“或”的关系。在真实比较的过程中首先将int数据转换成字节流存储到数据库中，然后将转换后的比较条件转换成字节流与扫描到数据库中的字节流进行比较，如表1所示。

5 系统优化结果的实验和验证

实验 1：查询计划优化效果分析

查询语句条件中无rowkey情况的查询语句如下，其设计用意在于验证类SQL语句的解析和三种优化能够正确执行，其中：查询语句为selectf1：c2，f3：c8fromt6where（f3：c8>2andf3：c8

按照查询条件where_list，f1：c3>1000andf1：c3>100andf3：c9>10存在冗余的情况下，在没有优化前的查询平均时间为395 266 ms，经过冗余和并行化优化后，速度明显提高了一个数量级，查询平均时间是97 025 ms，优化后查询时间减少了75.45%。

实验2：索引优化效果分析

（1） 优化后选择CCIndex索引表

该查询的数据分布情况为：数据分布f1：c1

如图4查询结果显示，优化后的时间和f2：c5列建立的CCIndex索引表的时间接近，可以认为经过优化后，查询条件结果集预估算法选择了以f2：c5列建立的索引表进行了扫描和条件筛选。其查询速度只占f3：c8和f1：c1建立的ImpSecondaryindex索引表和Secondaryindex索引表查询时间的0.192%和0.195%，分别提高了521.6倍和512.3倍。

（2） 优化后选择部分聚簇索引表

选择部分聚簇索引表的结果，如图5所示。查询语句中数据的分布情况为：数据分布f1：c1

（3） 优化后选择二级索引表

选择二级索引表的查询语句中数据分布情况为数据分布f1：c1=1 624的数据占列数据总量的0.000 1%，f3：c8

综合上面三组实验，索引优化后的查询结果和中等索引时间提高的倍数分别是512.3，23.91和22.37倍，取三者的平均值为186倍。

6 结 论

本文完成了分布式顺序表类SQL查询技术的实现和优化工作。给DOT系统设计了一套类似SQL的查询语句，并结合传统数据库和DOT系统的特点，实现了该套类SQL查询语句的语法语义分析，构建查询树并对查询关系式进行了算术优化、并行化优化和加多种数据类型查询优化三方面的优化内容。最后在典型的DOT系统，即ApacheHBase上实现了整个类SQL的解析和优化，并针对中科院在DOT系统上实现的三种索引机制进行了优化，使得整个系统的查询性能得到了显著的提升。最后通过实验，分析验证了查询优化和索引优化后查询速度明显提升。

参考文献

[1] 郭珉.Oracle数据库SQL优化原则[J].计算机应用系统，2010，19（4）：171?173.

[2] SILBERSCHATZ A， KORTH H F.数据库系统概念[M].北京：机械工业出版社，2006：293?400.

[3] CHANG F， DEAN J， GIHEMAWAT S， et al. Bigtable： a distributed storage system for structured data [C]// Proceedings of 2006 USENIX Symposium on Operation System Design and Implementation. Berkeley： ACM， 2006： 205?218.

[4] COOPER B F， RAMAKRISHNAN R， SRIVASTAVA U， et al. PNUTS： Yahoo！'s hosted data serving platform [J]. Proceedings of the VLDB endowment， 2008， 1（2）： 1277?1288.

[5] ZOU Y Q， LIU J， WANG S， et al. CCIndex： a complemental clustering index on distributed ordered tables for multi?dimensional range queries [C]// Proceedings of 2010 IFIP International Conference on Network and Parallel Computing. Zhengzhou， China： Springer， 2010： 247?261.

[6] 江凌，杨平利，杨梅，等.基于技术访问SQL Server数据库的编程实现[J].现代电子技术，2014，37（8）：95?98.

[7] 谭龙丹，郭睿志，王帅，等.基于C#与SQL Server的装备电子档案系统的设计与实现[J].现代电子技术，2014，37（14）：40?42.

[8] 任诗兵，邹海.基于关系代数的分布式数据库的查询优化[J].福建电脑，2008（2）：4?5.