Self-tuning query mesh for adaptive multi-route query processing

ABSTRACT

In real-life applications, different subsets of data may have distinct statistical properties, e.g., various websites may have diverse visitation rates, different categories of stocks may have dissimilar price fluctuation patterns. For such applications, it can be fruitful to eliminate the commonly made single execution plan assumption and instead execute a query using several plans, each optimally serving a subset of data with particular statistical properties. Furthermore, in dynamic environments, data properties may change continuously, thus calling for adaptivity. The intriguing question is: can we have an execution strategy that (1) is plan-based to leverage on all the benefits of traditional plan-based systems, (2) supports multiple plans each customized for different subset of data, and yet (3) is as adaptive as "plan-less" systems like Eddies? While the recently proposed Query Mesh (QM) approach provides a foundation for such an execution paradigm, it does not address the question of adaptivity required for highly dynamic environments. In this work, we fill this gap by proposing a Self-Tuning Query Mesh (ST-QM) --- an adaptive solution for content-based multi-plan execution engines. ST-QM addresses adaptive query processing by abstracting it as a concept drift problem --- a well-known subject in machine learning. Such abstraction allows to discard adaptivity candidates (i.e., the cases indicating a change in the environment) early in the process if they are insignificant or not "worthwhile" to adapt to, and thus minimize the adaptivity overhead. A unique feature of our aproach is that all logical transformations to the execution strategy get translated into a single inexpensive physical operation --- the classifier change. Our experimental evaluation using a continuous query engine shows the performance benefits of ST-QM approach over the alternatives, namely the non-adaptive and the Eddies-based solutions.

REFERENCES

• 1: Ms sql server. http://www.microsoft.com/sql/default.mspx.
• 2: Arvind Arasu , Brian Babcock , Shivnath Babu , Jon McAlister , Jennifer Widom, Characterizing memory requirements for queries over continuous data streams, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543642]
• 3: Amol Deshpande , Zachary Ives , Vijayshankar Raman, Adaptive query processing, Foundations and Trends in Databases, v.1 n.1, p.1-140, January 2007 [doi>10.1561/1900000001]
• 4: Amol Deshpande , Joseph M. Hellerstein, Lifting the burden of history from adaptive query processing, Proceedings of the Thirtieth international conference on Very large data bases, p.948-959, August 31-September 03, 2004, Toronto, Canada
• 5: A. Kumaran , Pavan K. Chowdary , Jayant R. Haritsa, On Pushing Multilingual Query Operators into Relational Engines, Proceedings of the 22nd International Conference on Data Engineering, p.98, April 03-07, 2006 [doi>10.1109/ICDE.2006.107]
• 6: Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543615]
• 7: I. M. Chakravarti and et.al. Handbook of Methods of Applied Statistics, volume I. John Wiley & Sons, 1967.
• 8: S. Christodoulakis, Implications of certain assumptions in database performance evauation, ACM Transactions on Database Systems (TODS), v.9 n.2, p.163-186, June 1984 [doi>10.1145/329.318578]
• 9: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 10: Donald Michie , D. J. Spiegelhalter , C. C. Taylor , John Campbell, Machine learning, neural and statistical classification, Ellis Horwood, Upper Saddle River, NJ, 1995
• 11: DB2. http://www.ibm.com/software/data/db2/.
• 12: Amol Deshpande, An initial study of overheads of eddies, ACM SIGMOD Record, v.33 n.1, March 2004 [doi>10.1145/974121.974129]
• 13: Elke A. Rundensteiner , Luping Ding , Timothy Sutherland , Yali Zhu , Brad Pielech , Nishant Mehta, CAPE: continuous query engine with heterogeneous-grained adaptivity, Proceedings of the Thirtieth international conference on Very large data bases, p.1353-1356, August 31-September 03, 2004, Toronto, Canada
• 14: Gerhard Widmer , Miroslav Kubat, Effective Learning in Dynamic Environments by Explicit Context Tracking, Proceedings of the European Conference on Machine Learning, p.227-243, April 05-07, 1993
• 15: Haixun Wang , Wei Fan , Philip S. Yu , Jiawei Han, Mining concept-drifting data streams using ensemble classifiers, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956778]
• 16: David J. Hand , Padhraic Smyth , Heikki Mannila, Principles of data mining, MIT Press, Cambridge, MA, 2001
• 17: Geoff Hulten , Laurie Spencer , Pedro Domingos, Mining time-changing data streams, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.97-106, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502529]
• 18: Zachary George Ives , Alon Halevy, Efficient query processing for data integration, University of Washington, 2002
• 19: Johannes Gehrke , Raghu Ramakrishnan , Venkatesh Ganti, RainForest—A Framework for Fast Decision Tree Construction of Large Datasets, Data Mining and Knowledge Discovery, v.4 n.2-3, p.127-162, July 2000 [doi>10.1023/A:1009839829793]
• 20: Jeffrey C. Schlimmer et.al. Beyond incremental processing: Tracking concept drift. In AAAI, pages 502--507, 1986.
• 21: K. Claypool et.al. Teddies: Trained eddies for reactive stream processing. In DASFAA, pages 220--234, 2008.
• 22: Kien A. Hua , Yo Lung Lo , Honesty C. Young, Considering data skew factor in multi-way join query optimization for parallel execution, The VLDB Journal — The International Journal on Very Large Data Bases, v.2 n.3, July 1993
• 23: Miroslav Kubat , Gerhard Widmer, Adapting to Drift in Continuous Domains (Extended Abstract), Proceedings of the 8th European Conference on Machine Learning, p.307-310, April 25-27, 1995
• 24: James F. Kurose , Keith Ross, Computer Networking: A Top-Down Approach Featuring the Internet, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2002
• 25: Mohamed Medhat Gaber , Arkady Zaslavsky , Shonali Krishnaswamy, Mining data streams: a review, ACM SIGMOD Record, v.34 n.2, June 2005 [doi>10.1145/1083784.1083789]
• 26: Michael Stillger , Guy M. Lohman , Volker Markl , Mokhtar Kandil, LEO - DB2's LEarning Optimizer, Proceedings of the 27th International Conference on Very Large Data Bases, p.19-28, September 11-14, 2001
• 27: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 28: Navin Kabra , David J. DeWitt, Efficient mid-query re-optimization of sub-optimal query execution plans, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.106-117, June 01-04, 1998, Seattle, Washington, United States
• 29: Oracle. http://www.oracle.com/index.html.
• 30: Pedro Bizarro , Shivnath Babu , David DeWitt , Jennifer Widom, Content-based routing: different plans for different data, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 31: Q. Li et.al. Adaptively reordering joins during query execution. In ICDE, pages 26--35, 2007.
• 32: Rakesh Agrawal , Sakti P. Ghosh , Tomasz Imielinski , Balakrishna R. Iyer , Arun N. Swami, An Interval Classifier for Database Mining Applications, Proceedings of the 18th International Conference on Very Large Data Bases, p.560-573, August 23-27, 1992
• 33: 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
• 34: Richard J. Lipton , Jeffrey F. Naughton , Donovan A. Schneider , S. Seshadri, Efficient sampling strategies for relational database operations, Theoretical Computer Science, v.116 n.1, p.195-226, Aug. 2, 1993
• 35: R. Nehme et.al. Query mesh: An efficient multi-route approach to query optimization. Technical Report CSD TR #08--009, Purdue University, April 2008.
• 36: Shivnath Babu , Rajeev Motwani , Kamesh Munagala , Itaru Nishizawa , Jennifer Widom, Adaptive ordering of pipelined stream filters, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007615]
• 37: Surajit Chaudhuri , Arnd Christian König , Vivek Narasayya, SQLCM: A Continuous Monitoring Framework for Relational Database Engines, Proceedings of the 20th International Conference on Data Engineering, p.473, March 30-April 02, 2004
• 38: Sudipto Guha , Nick Koudas , Kyuseok Shim, Data-streams and histograms, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.471-475, July 2001, Hersonissos, Greece [doi>10.1145/380752.380841]
• 39: 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]
• 40: Stratis D. Viglas , Jeffrey F. Naughton, Rate-based query optimization for streaming information sources, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564697]
• 41: Feng Tian , David J. DeWitt, Tuple routing strategies for distributed eddies, Proceedings of the 29th international conference on Very large data bases, p.333-344, September 09-12, 2003, Berlin, Germany
• 42: A. Tsymbal. The problem of concept drift: definitions and related work. Technical Report TCD-CS-2004-15, The University of Dublin, Trinity College, 2004.
• 43: V. Raman et.al. Using state modules for adaptive query processing. In ICDE, pages 353--365, 2003.
• 44: Venkatesh Ganti , Johannes Gehrke , Raghu Ramakrishnan, Mining data streams under block evolution, ACM SIGKDD Explorations Newsletter, v.3 n.2, January 2002 [doi>10.1145/507515.507517]
• 45: H. Wang and J. Pei. A random method for quantifying changing distributions in data streams. In PKDD, pages 684--691, 2005.
• 46: Ziv Bar-Yossef , T. S. Jayram , Robert Krauthgamer , Ravi Kumar, Approximating Edit Distance Efficiently, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.550-559, October 17-19, 2004 [doi>10.1109/FOCS.2004.14]