Skip to main content

Optimization of continuous queries with shared expensive filters

Publication ,  Conference
Munagala, K; Srivastava, U; Widom, J
Published in: Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems
October 29, 2007

We consider the problem of optimizing and executing multiple continuous queries, where each query is a conjunction of filters and each filter may occur in multiple queries. When filters are expensive, significant performance gains are achieved by sharing filter evaluations across queries. A shared execution strategy in our scenario can either be fixed, in which filters are evaluated in the same predetermined order for all input, or adaptive, in which the next filter to be evaluated is chosen at runtime based on the results of the filters evaluated so far. We show that as filter costs increase, the best adaptive strategy is superior to any fixed strategy, despite the overhead of adaptivity. We show that itis NP-hard to find the optimal adaptive strategy, even if we are willing to approximate within any factor smaller than m where m is the number of queries. We then present a greedy adaptive execution strategy and show that it approximates the best adaptive strategy to within a factor O(log 2m log n) where n is the number of distinct filters. We also give a precomputation technique that can reduce the execution overhead of adaptive strategies. Copyright 2007 ACM.

Duke Scholars

Altmetric Attention Stats
Dimensions Citation Stats

Published In

Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems

DOI

Publication Date

October 29, 2007

Start / End Page

215 / 224
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Munagala, K., Srivastava, U., & Widom, J. (2007). Optimization of continuous queries with shared expensive filters. In Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (pp. 215–224). https://doi.org/10.1145/1265530.1265561
Munagala, K., U. Srivastava, and J. Widom. “Optimization of continuous queries with shared expensive filters.” In Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 215–24, 2007. https://doi.org/10.1145/1265530.1265561.
Munagala K, Srivastava U, Widom J. Optimization of continuous queries with shared expensive filters. In: Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. 2007. p. 215–24.
Munagala, K., et al. “Optimization of continuous queries with shared expensive filters.” Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2007, pp. 215–24. Scopus, doi:10.1145/1265530.1265561.
Munagala K, Srivastava U, Widom J. Optimization of continuous queries with shared expensive filters. Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. 2007. p. 215–224.

Published In

Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems

DOI

Publication Date

October 29, 2007

Start / End Page

215 / 224