面向大数据近似查询应用的在线聚集融合机制与优化研究

There are several factors that can affect the application of approximate query processing, which are the usage scenarios, execution performance and the reliability. This project thus propose to make current approximate query processing technologies or systems much more general, efficient and reliable from three key aspects: the hybrid framework of online aggregation, the execution cost model and scheduling, the sampling model and estimation failure diagnostic method. Firstly, this project proposes a confidence adjustment mechanism to make the CLT-based online aggregation to support complex queries. Then, a hybrid online aggregation framework is presented to combine the extended CLT-based online aggregation and the bootstrap-based online aggregation together, which can satisfy majority of query workload, improving the overall generality. Secondly, an execution model for both CLT-based and bootstrap-based online aggregation is proposed, and then a query scheduling algorithm is proposed based on such cost model to optimize the query processing, improving the overall performance. Thirdly, this project presents a clustering-based two-level sampling method to improve the sample quality, which can reduce the estimation failure of online aggregation to some extent. And then a progressive estimation method is proposed to reduce the false positive of estimation failure diagnostic procedure, making it much more reliable. In summary, this project enacts a practical solution for the efficient execution of big data approximate query processing application.

本项目针对大数据近似查询应用的执行优化问题，围绕近似查询的适用场景普适性问题、近似查询的执行性能问题以及近似查询的近似估计可靠性问题，从在线聚集融合架构、执行代价模型与调度、抽样模型与估计失效预判三方面入手，开展在线聚集方法的融合处理机制与执行优化研究。首先提出基于复杂查询分解的置信度缩放机制，在此基础上设计在线聚集融合处理架构，形成面向大数据查询应用的一体化解决方案。其次，为两类主要在线聚集方法建立执行代价模型，在此基础上，提出融合处理架构下的多执行模式调度机制，实现执行过程的优化和执行效率的提升；第三，提出基于聚类的两级分层抽样模型，以提高样本质量，在此基础上，提出渐进式的近似估计失效预判机制，在提高预判机制执行效率的同时保证较低的误判率，实现近似查询应用的可靠执行。本项目将为大数据近似查询应用提供切实有效的解决方案，具有重要的理论意义和应用价值。

本项目针对大数据近似查询应用的执行优化问题，依次从在线聚集适用范围、执行效率、近似估计可靠性三方面入手，研究多种在线聚集方法的融合处理模型与架构、执行代价估算模型及多查询模式动态调度机制、面向单表与多表的在线聚集高效采样算法，并基于典型大数据处理平台开发与部署在线聚集融合架构原型系统，以验证理论研究成果。具体而言：本项目首先考虑两类主流在线聚集方法在适用查询场景、执行模式上的差异以及近似估计可靠性等因素，设计了一套在线聚集融合处理架构，提出了近似查询处理的一体化解决方案，实现了各类查询场景的全面覆盖和灵活适配。其次，针对CLT-based在线聚集对复杂查询支持度不够的问题，提出了一种基于精度参数自适应调整的扩展方法，提高了混合近似查询架构的执行效率。在此基础上，本项目结合两类主流在线聚集方法的执行逻辑，建立了相应的执行代价模型，进而提出了融合处理架构下的多执行模式调度机制，优化了执行过程进而提高执行效率。第三，本项目针对连接查询中采样效率较低的问题，提出了基于索引的带权抽样算法，提高了样本采集的效率。在此基础上，提出了渐进式的近似估计失效预判机制，通过合理设置估计结果的失效预判间隔，提高了预判机制执行效率。最后，本项目针对上述理论研究成果，基于大数据处理平台设计并实现了云环境下在线聚集融合处理架构原型系统，通过部署真实应用数据以验证了理论成果的可行性、有效性、可靠性和可扩展性。