Distributed query adaptation and its trade-offs

ABSTRACT

Adaptive query processing in large distributed systems has seen increasing importance due to the rising environmental fluctuations in a growing Internet. We describe Ginga, an adaptive query processing engine that combines proactive (compile-time) alternative query plan generation with reactive (run-time) monitoring of network delays. The core of Ginga approach is the notion of adaptation space and mechanisms for coordinating and integrating different kinds of query adaptation. An adaptation space consists of a set of adaptation triggers and a set of adaptation cases associated with the triggers. Each adaptation case describes a specific adaptation opportunity of the query execution when changes to the runtime environment are detected. Our experimental results show that Ginga query adaptation can achieve significant performance improvements (up to 40% of response time gain) for processing distributed queries over the Internet.

REFERENCES

• 1: Laurent Amsaleg , Michael J. Franklin , Anthony Tomasic, Dynamic Query Operator Scheduling for Wide-Area Remote Access, Distributed and Parallel Databases, v.6 n.3, p.217-246, July 1998 [doi>10.1023/A:1008646115473]
• 2: Laurent Amsaleg , Michael J. Franklin , Anthony Tomasic , Tolga Urhan, Scrambling query plans to cope with unexpected delays, Proceedings of the fourth international conference on on Parallel and distributed information systems, p.208-219, December 18-20, 1996, Miami Beach, Florida, United States
• 3: 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
• 4: Françoise Fabret, Dynamic Query Scheduling in Data Integration Systems, Proceedings of the 16th International Conference on Data Engineering, p.425, February 28-March 03, 2000
• 5: Richard L. Cole , Goetz Graefe, Optimization of dynamic query evaluation plans, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.150-160, May 24-27, 1994, Minneapolis, Minnesota, United States
• 6: Yannis E. Ioannidis , Raymond T. Ng , Kyuseok Shim , Timos K. Sellis, Parametric Query Optimization, Proceedings of the 18th International Conference on Very Large Data Bases, p.103-114, August 23-27, 1992
• 7: Zachary G. Ives , Daniela Florescu , Marc Friedman , Alon Levy , Daniel S. Weld, An adaptive query execution system for data integration, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.299-310, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 8: 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
• 9: L. Liu. Adaptation cases and adaptation spaces: Notation, issues and applications (part i: Concepts and semantics). Technical report, OGI CSE Heterodyne Project, 1998.
• 10: L. Liu. Query routing in large-scale digital library systems. In ICDE, 1999.
• 11: L. Liu, C. Pu, and K. Richine. Distributed query scheduling service: An architecture and its implementation. JCIS, 7(2--3), 1998.
• 12: L. Liu, C. Pu, and W. Tang. Continual queries for internet-scale event-driven information delivery. IEEE Knowledge and Data Engineering, 1999. Special Issue on Web Technology.
• 13: Henrique Paques , Ling Liu , Calton Pu, Ginga: a self-adaptive query processing system, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584910]
• 14: Donovan A. Schneider , David J. DeWitt, Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines, Proceedings of the 16th International Conference on Very Large Data Bases, p.469-480, August 13-16, 1990
• 15: P. G. Selinger and M. Adiba. Access path selection in distributed database management systems. In VLDB, 1980.
• 16: Leonard D. Shapiro, Join processing in database systems with large main memories, ACM Transactions on Database Systems (TODS), v.11 n.3, p.239-264, Sept. 1986 [doi>10.1145/6314.6315]
• 17: Michael Stonebraker, The design and implementation of distributed INGRES, The INGRES papers: anatomy of a relational database system, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

Additional Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.0 General

General Terms:
Design, Experimentation, Performance, Reliability

Keywords:
distributed query processing, query adaptation