An initial study of overheads of eddies

ABSTRACT

An eddy [2] is a highly adaptive query processing operator that continuously reoptimizes a query in response to changing runtime conditions. It does this by treating query processing as routing of tuples through operators and making per-tuple routing decisions. The benefits of such adaptivity can be significant, especially in highly dynamic environments such as data streams, sensor query processing, web querying, etc. Various parties have asserted that the cost of making per-tuple routing decisions is prohibitive. We have implemented eddies in the PostgreSQL open source database system [1] in the context of the TelegraphCQ project. In this paper, we present an "apples-to-apples" comparison of PostgreSQL query processing overhead with and without eddies. Our results show that with some minor tuning, the overhead of the eddy mechanism is negligible.

REFERENCES

• 1: PostgreSQL Data Management System. http://www.postgresql.org.
• 2: Ron Avnur , Joseph M. Hellerstein, Eddies: continuously adaptive query processing, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.261-272, May 15-18, 2000, Dallas, Texas, United States
• 3: Sirish Chandrasekaran and Michael J. Franklin. Streaming queries over streaming data. In VLDB, 2002.
• 4: David J. DeWitt. The Wisconsin Benchmark: Past, present, and future. In The Benchmark Handbook Database and Transaction Systems (2nd Edition). 1993.
• 5: Joe Hellerstein et al. Adaptive query processing: Technology in evolution. IEEE Data Engineering Bulletin, 2000.
• 6: Sailesh Krishnamurthy et al. TelegraphCQ: An architectural status report. IEEE Data Engineering Bulletin, 2003.
• 7: Sirish Chandrasekaran et al. TelegraphCQ: Continuous dataflow processing for an uncertain world. In CIDR, 2003.
• 8: Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993 [doi>10.1145/152610.152611]
• 9: Ravi Krishnamurthy , Haran Boral , Carlo Zaniolo, Optimization of Nonrecursive Queries, Proceedings of the 12th International Conference on Very Large Data Bases, p.128-137, August 25-28, 1986
• 10: Samuel Madden , Mehul Shah , Joseph M. Hellerstein , Vijayshankar Raman, Continuously adaptive continuous queries over streams, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564698]
• 11: Vijayshankar Raman, Amol Deshpande, and Joe Hellerstein. Using state modules for adaptive query processing. In ICDE, 2003.
• 12: Feng Tian and David J. DeWitt. Tuple routing strategies for distributed eddies. In VLDB, 2003.