分布式数据流管理系统的物理查询计划生成与优化

摘要

近年来，一些数据密集型应用大量涌现，例如网络监控、电信数据管理、传感器网络等应用。这些应用需要对地理上分布的结点中多样的、大量的数据流进行实时的连续查询。这些数据通常具有实时，有序，无限等“流”的特征，并且往往由分布在不同地理位置上的设备产生。为处理相对静态的磁盘数据优化的关系数据库无法高效地处理这类实时数据。而这些实时数据的分布性从数据传输、可靠性和处理能力等方面向集中式的处理方式提出了挑战。通用的数据流管理系统不可避免地向分布式系统发展。于是分布式数据流管理系统(DDSMS)应运而生，相关的研究大量展开。
　　 查询处理在DDSMS系统中是一种非常关键的技术。DDSMS的查询处理过程包括查询预处理、逻辑查询计划的生成、物理查询计划的生成、优化处理以及查询的执行。根据逻辑计划生成物理查询计划是数据流查询过程中的重要步骤，它的合理有效是系统实时性保证的关键问题之一。在此过程中，不仅需要特定的转换规则，定义合适的数据结构，还要制定各种物理算子的实现算法等。
　　 在关系数据库中，查询优化一般基于表的“势”的基础之上来评估一个查询计划的开销。但是由于数据流的无界性，这种查询优化的方法就失去意义了。DDSMS系统并行运行着大量的连续查询。生成初始查询计划时应同时考虑查询优化和算子部署问题。数据流的特性和查询工作负载随时间不断变化，一个连续查询的初始查询计划可能变得效率低下。因此，查询优化器要在运行时根据当前统计数据进行再优化。
　　 分布式数据流管理系统的物理查询计划的生成与优化是DDSMS的重要研究内容。针对这些问题给出各种物理算子的具体实现，介绍了物理查询计划的生成过程，并引入了一种优化框架，给出此系统中查询优化的正式定义、代价模型以及一些优化策略。