High performance stream query processing with correlation-aware partitioning
Authors:
Open Access
- 1 December 2013
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 7 (4) , 265-276
Abstract
State-of-the-art optimizers produce one single optimal query plan for all stream data, in spite of such a singleton plan typically being sub-optimal or even poor for highly correlated data. Recently a new stream processing paradigm, called multi-route approach, has emerged as a promising approach for tackling this problem. Multi-route first divides data streams into several partitions and then creates a separate query plan for each combination of partitions. Unfortunately current approaches suffer from severe shortcomings, in particular, the lack of an effective partitioning strategy and the prohibitive query optimization expense. In this work we propose the first practical multi-route optimizer named correlation-aware multi-route stream query optimizer (or CMR) that solves both problems. By exploiting both intra- and inter-stream correlations of streams, CMR produces effective partitions without having to undertake repeated expensive query plan generation. The produced partitions not only are best served by distinct optimal query plans, but also leverage the partition-driven pruning opportunity. Experimental results with both synthetic and real life stream data confirm that CMR outperforms the state-of-the-art solutions up to an order of magnitude in both the query optimization time and the run-time execution performance.Keywords
This publication has 16 references indexed in Scilit:
- Approximating and testing k-histogram distributions in sub-linear time2012
- On Testing Expansion in Bounded-Degree Graphs2011
- Sharing-aware horizontal partitioning for exploiting correlations during query processingProceedings of the VLDB Endowment, 2010
- SPADE2008
- Adaptive ordering of pipelined stream filters2004
- CAPE2004
- Bell numbers, their relatives, and algebraic differential equationsJournal of Combinatorial Theory, Series A, 2003
- Maximizing the Output Rate of Multi-Way Join Queries over Streaming Information Sources2003
- Eddies2000
- Approximating discrete probability distributions with dependence treesIEEE Transactions on Information Theory, 1968