Quality of service in an information economy

ABSTRACT

Accessing and processing distributed data sources have become important factors for businesses today. This is especially true for the emerging virtual enterprises with their data and processing capabilities spread across the Internet. Unfortunately, however, query processing on the Internet is not predictable and robust enough to meet the requirements of many business applications. For instance, the response time of a query can be unexpectedly high; or the monetary cost might be too high if the partners charge for the usage of their data or processing capabilities; or the result of the query might be useless because it is based on outdated data or only on parts (rather than all) of the available data. In this work, we show how a distributed query processor can be extended in order to support quality of service (QoS) guarantees. We propose ways to integrate QoS management into the various phases of query processing: (1) Query optimization uses a multi-dimensional assessment (cost, time and result quality) of query plans, (2) query plan instantiation comprises an admission control for sub-plans, and (3) during query plan execution the QoS of the query is monitored and a fuzzy controller initiates repairing actions if needed. The goal of our work is to provide an initial step towards QoS management in distributed query processing systems and do significantly better than current distributed database systems, which are based on a best-effort policy.

REFERENCES

• 1: Ashraf Aboulnaga , Surajit Chaudhuri, Self-tuning histograms: building histograms without looking at data, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.181-192, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 2: Gennady Antoshenkov , Mohamed Ziauddin, Query processing and optimization in Oracle Rdb, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.4, p.229-237, December 1996 [doi>10.1007/s007780050026]
• 3: Cristina Aurrecoechea , Andrew T. Campbell , Linda Hauw, A survey of QoS architectures, Multimedia Systems, v.6 n.3, p.138-151, May 1998 [doi>10.1007/s005300050083]
• 4: 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
• 5: Kevin S. Beyer , Miron Livny , Raghu Ramakrishnan, Protecting the Quality of Service of Existing Information Systems, Proceedings of the 3rd IFCIS International Conference on Cooperative Information Systems, p.74-85, August 20-22, 1998
• 6: R. Braumandl , M. Keidl , A. Kemper , D. Kossmann , A. Kreutz , S. Seltzsam , K. Stocker, ObjectGlobe: Ubiquitous query processing on the Internet, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.1, p.48-71, August 2001
• 7: Kurt P. Brown , Manish Mehta , Michael J. Carey , Miron Livny, Towards Automated Performance Tuning for Complex Workloads, Proceedings of the 20th International Conference on Very Large Data Bases, p.72-84, September 12-15, 1994
• 8: Michael J. Carey , Donald Kossmann, Reducing the Braking Distance of an SQL Query Engine, Proceedings of the 24rd International Conference on Very Large Data Bases, p.158-169, August 24-27, 1998
• 9: Francis Chu , Joseph Y. Halpern , Praveen Seshadri, Least expected cost query optimization: an exercise in utility, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.138-147, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303990]
• 10: Daniela Florescu , Daphne Koller , Alon Y. Levy, Using Probabilistic Information in Data Integration, Proceedings of the 23rd International Conference on Very Large Data Bases, p.216-225, August 25-29, 1997
• 11: Sumit Ganguly , Waqar Hasan , Ravi Krishnamurthy, Query optimization for parallel execution, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.9-18, June 02-05, 1992, San Diego, California, United States
• 12: Minos N. Garofalakis , Yannis E. Ioannidis, Parallel Query Scheduling and Optimization with Time- and Space-Shared Resources, Proceedings of the 23rd International Conference on Very Large Data Bases, p.296-305, August 25-29, 1997
• 13: G. Graefe , K. Ward, Dynamic query evaluation plans, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.358-366, June 1989, Portland, Oregon, United States
• 14: Jean-Robert Gruser , Louiqa Raschid , Vladimir Zadorozhny , Tao Zhan, Learning response time for WebSources using query feedback and application in query optimization, The VLDB Journal — The International Journal on Very Large Data Bases, v.9 n.1, p.18-37, March 2000 [doi>10.1007/s007780050081]
• 15: 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
• 16: 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
• 17: 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
• 18: George J. Klir , Bo Yuan, Fuzzy sets and fuzzy logic: theory and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
• 19: Alon Y. Levy , Anand Rajaraman , Joann J. Ordille, Querying Heterogeneous Information Sources Using Source Descriptions, Proceedings of the 22th International Conference on Very Large Data Bases, p.251-262, September 03-06, 1996
• 20: Li, B. and Nahrstedt, K. 1999. A control-based middleware framework for quality of service adaptations. IEEE J. Sel. Areas Comm. 17, 9, 1632--1650.
• 21: HweeHwa Pang , Michael J. Carey , Miron Livny, Multiclass Query Scheduling in Real-Time Database Systems, IEEE Transactions on Knowledge and Data Engineering, v.7 n.4, p.533-551, August 1995 [doi>10.1109/69.404028]
• 22: C. H. Papadimitriou , M. Yannakakis, On the approximability of trade-offs and optimal access of Web sources, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.86, November 12-14, 2000
• 23: Petit, J. 1999. Real Estate DTD. http://www.4thworldtele.com.
• 24: Viswanath Poosala , Peter J. Haas , Yannis E. Ioannidis , Eugene J. Shekita, Improved histograms for selectivity estimation of range predicates, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.294-305, June 04-06, 1996, Montreal, Quebec, Canada
• 25: Mary Tork Roth , Fatma Ozcan , Laura M. Haas, Cost Models DO Matter: Providing Cost Information for Diverse Data Sources in a Federated System, Proceedings of the 25th International Conference on Very Large Data Bases, p.599-610, September 07-10, 1999
• 26: A. Prasad Sistla , Ouri Wolfson , Yelena Yesha , Robert Sloan, Towards a theory of cost management for digital libraries and electronic commerce, ACM Transactions on Database Systems (TODS), v.23 n.4, p.411-452, Dec. 1998 [doi>10.1145/296854.277641]
• 27: Michael Stonebraker , Paul M. Aoki , Witold Litwin , Avi Pfeffer , Adam Sah , Jeff Sidell , Carl Staelin , Andrew Yu, Mariposa: a wide-area distributed database system, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.1, p.048-063, January 1996 [doi>10.1007/s007780050015]
• 28: Tolga Urhan , Michael J. Franklin , Laurent Amsaleg, Cost-based query scrambling for initial delays, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.130-141, June 01-04, 1998, Seattle, Washington, United States
• 29: VLDB 1997. Proceedings of the Conference on Very Large Data Bases (VLDB). Athens, Greece.
• 30: Weikum, G. 1999. Towards guaranteed quality and dependability of information services. In Proceedings of the GI Conference on Database Systems for Office, Engineering, and Scientific Applications (BTW). Informatik aktuell. Springer-Verlag, New York, Berlin.
• 31: Annita N. Wilschut , Peter M. G. Apers, Dataflow query execution in a parallel main-memory environment, Proceedings of the first international conference on Parallel and distributed information systems, p.68-77, December 1991, Miami, Florida, United States
• 32: Rich Wolski , Neil Spring , Chris Peterson, Implementing a performance forecasting system for metacomputing: the Network Weather Service, Proceedings of the 1997 ACM/IEEE conference on Supercomputing (CDROM), p.1-19, November 15-21, 1997, San Jose, CA [doi>10.1145/509593.509600]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Information networks

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Commercial services

General Terms:
Design, Performance

Keywords:
Quality of Service