Cost-based query scrambling for initial delays

ABSTRACT

Remote data access from disparate sources across a wide-area network such as the Internet is problematic due to the unpredictable nature of the communications medium and the lack of knowledge about the load and potential delays at remote sites. Traditional, static, query processing approaches break down in this environment because they are unable to adapt in response to unexpected delays. Query scrambling has been proposed to address this problem. Scrambling modifies query execution plans on-the-fly when delays are encountered during runtime. In its original formulation, scrambling was based on simple heuristics, which although providing good performance in many cases, were also shown to be susceptible to problems resulting from bad scrambling decisions. In this paper we address these shortcomings by investigating ways to exploit query optimization technology to aid in making intelligent scrambling choices. We propose three different approaches to using query optimization for scrambling. These approaches vary, for example, in whether they optimize for total work or response-time, and whether they construct partial or complete alternative plans. Using a two-phase randomized query optimizer, a distributed query processing simulator, and a workload derived from queries of the TPCD benchmark, we evaluate these different approaches and compare their ability to cope with initial delays in accessing remote sources. The results show that cost-based scrambling can effectively hide initial delays, but that in the absence of good predictions of expected delay durations, there are fundamental tradeoffs between risk aversion and effectiveness.

REFERENCES

• ABF+97: L. Amsaleg, P. Bonnet, M. Franklin, A. Tomasic, and T. Urhan Improving Responsiveness for Wide-Area Data Access. IEEE Data Engineering Bulletin, Vol. 20, No. 3.
• AFT98: 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]
• AFTU96: 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
• Ant93: Gennady Antoshenkov, Dynamic Query Optimization in Rdb/VMS, Proceedings of the Ninth International Conference on Data Engineering, p.538-547, April 19-23, 1993
• Bro92: K. Brown. Prpl: A database workload specification language. Master's thesis, University of Winsconsin, Madison, Winsconsin, 1992.
• CBTY89: A. Chen, D. Brill, M. Templeton, and C. Yu. Distributed Query Processing in a Multiple Database System. IEEE Journal on Selected Areas in Communications, 7(3), 1989.
• CD96: Michael J. Carey , David J. DeWitt, Of Objects and Databases: A Decade of Turmoil, Proceedings of the 22th International Conference on Very Large Data Bases, p.3-14, September 03-06, 1996
• CG94: 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
• DSD95: Weimin Du , Ming-Chien Shan , Umeshwar Dayal, Reducing multidatabase query response time by tree balancing, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.293-303, May 22-25, 1995, San Jose, California, United States
• GHK92: 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
• Gra93: 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]
• IK90: Y. E. Ioannidis , Younkyung Kang, Randomized algorithms for optimizing large join queries, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.312-321, May 23-26, 1990, Atlantic City, New Jersey, United States
• INSS92: 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
• IW87: Yannis E. Ioannidis , Eugene Wong, Query optimization by simulated annealing, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.9-22, May 27-29, 1987, San Francisco, California, United States
• Kim95: Won Kim, Modern database systems: the object model, interoperability, and beyond, ACM Press/Addison-Wesley Publishing Co., New York, NY, 1995
• MMM97: Alberto O. Mendelzon , George A. Mihaila , Tova Milo, Querying the World Wide Web, Proceedings of the fourth international conference on on Parallel and distributed information systems, p.80-91, December 18-20, 1996, Miami Beach, Florida, United States
• ML86: Lothar F. Mackert , Guy M. Lohman, R* optimizer validation and performance evaluation for local queries, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.84-95, May 28-30, 1986, Washington, D.C., United States
• ONK+97: E Ozcan, S. Nural, P. Koksal, C. Evrendilek, A. Dogac. Dynamic Query optimization in Multidatabases. Data Engineering Bulletin, Vol. 20, No. 3, September, 1997.
• RAH+96: M. Tork Roth , M. Arya , L. Haas , M. Carey , W. Cody , R. Fagin , P. Schwarz , J. Thomas , E. Wimmers, The Garlic project, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.557, June 04-06, 1996, Montreal, Quebec, Canada
• SAC+79: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• SAD+95: Ming-Chien Shan , Rafi Ahmed , Jim Davis , Weimin Du , William Kent, Pegasus: a heterogeneous information management system, Modern database systems: the object model, interoperability, and beyond, ACM Press/Addison-Wesley Publishing Co., New York, NY, 1995
• Sha86: 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]
• SLR97: Praveen Seshadri , Miron Livny , Raghu Ramakrishnan, The Case for Enhanced Abstract Data Types, Proceedings of the 23rd International Conference on Very Large Data Bases, p.66-75, August 25-29, 1997
• THMB95: Marjorie Templeton , Herbert Henley , Edward Maros , Darrel J. Van Buer, InterViso: dealing with the complexity of federated database access, The VLDB Journal — The International Journal on Very Large Data Bases, v.4 n.2, p.287-318, April 1995 [doi>10.1007/BF01237922]
• Tra97: Transaction Processing Council. TPC Benchmark D Standard Specification, Rev. 1.2.3.
• TRV96: Scaling heterogeneous databases and the design of Disco, Proceedings of the 16th International Conference on Distributed Computing Systems (ICDCS '96), p.449, May 27-30, 1996

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Experimentation, Measurement