连续查询硬处理器及相关算法研究

论文摘要

数据流的高速性和无限性以及计算机资源的有限性使得提高数据处理的速度成为数据流管理系统的关键。目前已有的数据流管理原型系统都是从查询优化、系统调度等方面来提高速度，在高速数据流环境下都存在明显的不足。降载策略是解决高速数据流处理的一个方法，但也有局限性，如可用于聚集计算，但不能应用于连接操作。本文基于数据管理技术发展的前瞻性考虑，以高速数据流为处理对象，不局限于通过查询优化、系统调度等方法来提高数据流的处理速度，而是考虑采用一种全新的体系结构来加速数据处理。国内外尚没有这方面的研究报道，具有较高的创新性。本文内容涉及多个研究领域，除数据库技术外，还涉及具体的机器指令设计、硬处理器设计和编译技术等。本文的主要研究工作有以下几方面： 1．在深入研究国际上先进的数据流管理原型系统基础上，提出了一种适合数据流并发连接处理的方法M3Join。该方法充分考虑数据的“流”特性，体现数据驱动特点，以多线程并行和类似路由器的处理方式保证数据的高速处理，同时注重查询间和查询内的并行。M3Join可用于硬件实现，为更高速度地处理数据流提供了可能。实验结果表明，M3Join具有良好的性能，能够满足多流多窗口的并发连接查询的需要。 2．提出适合数据流连续查询处理的架构SeuStreams。在传统数据库中，由于需求是即时查询而不是连续查询，因此通常不考虑并发查询处理。一般处理原则是尽可能将选择、投影操作移向查询树的叶节点。而在连续查询中，由于存在大量并发查询，如果先执行选择将破坏对于连接结果的共享性，而恰恰此时的连接操作是最耗时的。本文深入研究了适合SeuStreams查询处理的三种可共享连接结果的策略：Shared PushDown、PullUp和Filtered PullUp。通过理论分析和实验证明，在数据流的连续查询处理中，PullUp策略性能较低，而Filtered PullUp和Shared PushDown策略各有优势。由于Filtered PullUp处理简单，消耗内存相对较少，因此一般情况下Filtered PullUp是适合SeuStreams的最佳方案。 3．为进一步提高系统处理的效率，我们也对并发连接查询的优化算法作了深入研究，提出数据流窗口连接的近似优化算法SQFGS。在并发查询条件下，一条查询的优化可能会牵涉到其它许多的查询，迫使它们的修正正在执行的查询计划。而查询计划的调整是非常复杂和耗资源的。我们提出的SQFGS优化策略简单易行，对一条查询的优化不会牵涉到其它查询，理论和实验证明其性能在可接受的范围内。SQFGS策略尤其适用于硬件处理的查询计划生成，当然，SQFGS策略也适合于查询更新频率很高的系统。 4．绝大多数连续查询处理算法是用软件实现的，我们提出了用硬件加速数据流连接处理的方法，极大地提高了处理的速度。为了处理不同的连接条件，我们设计并实现了用于数据流连接的处理器WJSP及其指令系统WJSI，并提出集成方法以提高WJSP的扩展性和并行性，同时也提高处理的速度。我们将WJSP与STREAM原型作了比较，结果显示WJSP比STREAM的速度提高20多倍，说明WJSP具有相当高的处理性能。WJSP可嵌入到路由器、交换机、传感器等设备中，提供高速的数据流连接处理。廉价且高性能的连接操作协处理器能够增强DSMS的处理能力，尤其是在类似网络监控等性能要求较高的领域。 本文的研究旨在拓展提高数据流处理速度的新方法，探索提高数据流管理系统性能的新路子，为许多重要的数据流处理领域提供更为先进、实用的解决方案，同时也为数据管理技术理论、方法的发展作出新贡献。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景
• 1.1.1 数据库技术发展简史
• 1.1.2 数据流应用
• 1.1.3 DSMS与DBMS区别
• 1.1.4 基本概念
• 1.1.5 问题和挑战
• 1.2 研究现状
• 1.3 研究内容及创新
• 1.4 论文结构
• 第二章 多数据流滑动窗口并发连接方法
• 2.1 引言
• 2.2 实现架构Roujoin
• 2.3 多流多任务连接方法M3Join
• 2.3.1 架构Roujoin初始化
• 2.3.2 流元组执行连接
• 2.4 分析和实验
• 2.4.1 顺序连接与索引连接比较
• 2.4.2 实验结果
• 2.5 小结
• 第三章 共享连接结果的连续查询处理
• 3.1 连续查询处理的不同策略
• 3.2 选择与连接的顺序
• 3.3 实验结果
• 3.4 小结
• 第四章 数据流窗口连接优化算法
• 4.1 相关工作
• 4.2 单条连接查询的优化
• 4.2.1 数据流连接图
• 4.2.2 最优探测序列算法
• 4.3 并发连接查询的优化
• 4.3.1 共享中间结果的优化方法
• 4.3.2 并发连接查询处理算法
• 4.3.3 并发连接性能分析
• 4.4 实验结果
• 4.5 小结
• 第五章 连续查询硬处理器研究
• 5.1 序言
• 5.1.1 数据库领域的软硬件协同技术
• 5.1.2 ASIC与FPGA
• 5.2 WJSP处理器
• 5.3 特殊指令集WJSI
• 5.4 可扩展性和局限性
• 5.5 进一步提高处理的并行度
• 5.6 实验结果与性能估算
• 5.6.1 实验结果
• 5.6.2 性能估算
• 5.7 完整的连续查询处理框架
• 5.7.1 集成方法
• 5.7.2 其它相关技术
• 5.8 小结
• 第六章 总结与展望
• 6.1 工作总结
• 6.2 研究展望
• 参考文献
• 致谢
• 附录
• 附录1 参与的科研项目
• 附录2 攻读博士学位期间论文成果