周虹+富春岩+支援+刘越+于占龙+薛佳楣+韦韫韬+王超+张立铭+李微娜
摘要：目前在金融、移动数据、网络监控及物联网等领域中，经常会需要处理一些海量的、实时的、需要快速响应的数据流。为了对这些数据流进行有效的管理，提出了基于硬件预处理的数据流管理系统，并对相应的数据流并发连接算法进行了优化，以得到数据流预处理器所需的控制信息。
关键词：数据流管理系统；连续查询；查询优化
中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）33-0025-02
数据流的特点是：数据具有实时性，需要即时响应；数据量大，而且无界；它还具有不可预知性，不可预期、无法控制数据流中元素的到达次序。以上这些特点都决定了，对数据流的查询只能近似实时。而且，目前大多数基于软件实现的数据流管理系统的处理速度都是有一定限制的。当数据流的流速达到一定的速度之后，就会出现瓶颈，利用软件就难以实现了。目前看来，比较可行的方法是来设计专门的硬件进行预处理来解决这个问题，即将数据流处理的某些操作利用硬件来实现。
提高对数据流连接操作的处理效率，是解决数据流管理系统中，如何提高处理速度的关键问题。利用多条数据流并发执行连接理论上可以提高处理效率，但是如何处理连接顺序又在很大程度上影响了系统的速度。因此，如何优化数据流并发连接查询算法则成为了研究数据流管理系统的关键技术之一。
1 基于硬件预处理的数据流管理系统
目前基于硬件预处理的数据流管理系统主要由两部分组成，包括：位于前端的预处理器和位于后端的数据引擎部分。位于前端的预处理器主要功能是完成对数据流的预处理操作。可以对后端传输过来的一些控制命令进行初始化处理，还可以对数据流中的数据进行滤波、压缩和加标记等处理工作。这种位于前端的预处理器，采用的是软、硬件协同的方式进行工作的，可以大大提高数据的处理速度。经过前端预处理之后的数据通过网络被传输到后端的数据引擎部分。
系统后端的数据引擎主要的功能是进行连续查询的语法分析、生成要进行并行查询的计划、将经过预处理的元组分到相应的数据缓存中，将通过并行处理后得到的查询结果再进行组装分发，后端数据引擎还负责负载的均衡、服务质量的监控等功能。用户提交的查询要经过词法及语义的分析、要进行查询优化才能得到所需的查询抽象语法树，在后端要对生成的抽象语法树用相应的算法进行处理，得到所需控制信息，再将这些控制信息，经过查询输出控制器交给前端的硬件查询处理模块进行相应的处理。
2 基于硬件预处理的数据流连续查询语言X-SQL
在传统的关系数据库中，常用的查询语言是SQL，它不能用于数据流查询中，不支持数据流中的连续查询语义。为了处理数据流中的数据，就需要使用专门处理数据流查询的语言。目前，用于数据流研究的查询语言主要有：基于关系的、基于对象的和基于过程的这三种语言[1]。
在研究过程中，我们数据流管理系统使用的是基于硬件预处理的数据流连续流查询语言X-SQL。它是一种基于关系查询语言，具有类SQL 的句法规则，它还可以提供对窗口以及对排序的支持。通过基于关系的流语言，用户即可指定查询的语义，也定义数据流的采样率。
X-SQL是用滑动窗口来实现连续查询中的抽象语义的。我们可在系统后端进行X-SQL连续查询的输入，再进行交叉编译得出相应的一些查询指令和信息，再通过网络传输，将这些指令和数据输送到硬件的预处理器中，即可进行对数据流的各种查询。
X-SQL由数据流定义语言和数据流查询语言两种语言构成。其中，数据流定义语言是用来给数据流管理系统输入元数据信息的，而数据流查询语言则是实现对数据流进行查询的。
在X-SQL语言中，也是用SELECT语句来实现查询功能的。只不过除了像传统SQL语言一样给出要返回的属性选择列表、要检索数据的流的流列表和条件外，还有窗口声明部分。窗口声明部分是用来声明相应的滑动窗口大小的。语法如下所示：
X-SQL查询语句通过WINDOW子句就可以实现对滑动窗口查询，也就可以实现对数据流的连续查询操作。
3 并发连接查询的优化算法
在基于硬件预处理的数据流管理系统中，当用户提交了查询，该查询首先要经过编译器的词法分析、语法分析和语义分析。在进行了这些分析之后，才能得一棵语义正确的查询语法树。然后再依据这棵语意正确的语法树生成相应的目标代码。但是，只是可以生成目标代码，用这种方法生成的代码执行效率并不高，我们为了提高查询系统的工作效率，就需要对一些查询进行优化。
3.1 对谓词进行化简的优化算法
对谓词进行化简就是利用应用逻辑运算的相应规则，将用到的谓词表达式，等价地置换成更简单的式子。谓词化简的逻辑运算规则如下表1所示：
根据规则，我们设计出谓词化简算法，如下所示：
3.2 对谓词进行规范化优化算法
除了可以对谓词进行化简，我们还可以在X-SQL查询中对谓词的规则进行规范化优化，规谓词范化优化算法如下所示：
4 结论
目前来看，大多数的数据流管理系统基本还是基于软件系统来实现管理的。那幺，当数据流速过快时，处理速度就出现问题。为了能提高数据流的处理速度，我们采用了基于硬件预处理的数据流管理系统。并对数据流查询语言X-SQL进行了优化。通过查询优化，可得到查询语法树，再对相应的语法树进行处理，即可生成基于硬件预处理的数据流管理系统所需的优化的控制信息。
参考文献：
[1] Qian Jiang-bo， Xu Hong-bing， Dong Yi-sheng， et al. FPGA Acceleration window Joins over Multiple Data Stream， Journal of Circuits， Systems， and Computers， 2012，14（4）：813-830.
[2] Babcock B， Babu S， Datar M， et al. Models and Issues in Data Stream Systems [J]. In Proc. of the 2014 ACM Symp， In Principles of Database Systems， 2014：12-16.
