Performance tradeoffs for client-server query processing

ABSTRACT

The construction of high-performance database systems that combine the best aspects of the relational and object-oriented approaches requires the design of client-server architectures that can fully exploit client and server resources in a flexible manner. The two predominant paradigms for client-server query execution are data-shipping and query-shipping We first define these policies in terms of the restrictions they place on operator site selection during query optimization. We then investigate the performance tradeoffs between them for bulk query processing. While each strategy has advantages, neither one on its own is efficient across a wide range of circumstances. We describe and evaluate a more flexible policy called hybrid-shipping, which can execute queries at clients, servers, or any combination of the two. Hybrid-shipping is shown to at least match the best of the two "pure" policies, and in some situations, to perform better than both. The implementation of hybrid-shipping raises a number of difficult problems for query optimization. We describe an initial investigation into the use of a 2-step query optimization strategy as a way of addressing these issues.

REFERENCES

• Bro92: K. Brown. PRPL: A database workload specification language~ Master's thesis, Univ. of Wisconsin, 1992.
• C+94: Michael J. Carey , David J. DeWitt , Michael J. Franklin , Nancy E. Hall , Mark L. McAuliffe , Jeffrey F. Naughton , Daniel T. Schuh , Marvin H. Solomon , C. K. Tan , Odysseas G. Tsatalos , Seth J. White , Michael J. Zwilling, Shoring up persistent applications, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.383-394, May 24-27, 1994, Minneapolis, Minnesota, United States
• Cat94: Roderick G. Cattell , Tom Atwood, Object Database Standard: ODMG-93, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• CL86: Michael J. Carey , Hongjun Lu, Load balancing in a locally distributed DB system, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.108-119, May 28-30, 1986, Washington, D.C., United States
• D+90: David J. DeWitt , Philippe Futtersack , David Maier , Fernando Velez, A study of three alternative workstation server architectures for object-oriented database systems, Proceedings of the sixteenth international conference on Very large databases, p.107-121, September 1990, Brisbane, Australia
• Fra96: M. Franklin. Client Data Caching. Kluwer Academic Press, Boston, 1996.
• 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]
• GW93: S. Ganguly and W. Wang. Optimizing queries for coarse grain parallelism. Technical report, Rutgers University, 1993.
• HF86: Robert Brian Hagmann , Domenico Ferrari, Performance analysis of several back-end database architectures, ACM Transactions on Database Systems (TODS), v.11 n.1, p.1-26, March 1986 [doi>10.1145/5236.5242]
• 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
• J+90: B. Paul Jenq , Darrell Woelk , Won Kim , Wan-Lik Lee, Query processing in distributed ORION, Proceedings of the international conference on extending database technology on Advances in database technology, p.169-187, March 1990, Venice, Italy
• KF95: Donald Kossmann , Michael J. Franklin, A study of query execution strategies for client-server database systems, University of Maryland at College Park, College Park, MD, 1995
• Kul94: Krishna G. Kulkarni, Object-oriented extensions in SQL3: a status report, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.478, May 24-27, 1994, Minneapolis, Minnesota, United States
• LC85: H. Lu and M. Carey. Some experimental results on distributed join algorithms in a local network. 11th VLDB Conf., Stockholm, 1985.
• LVZ93: Rosana S. G. Lanzelotte , Patrick Valduriez , Mohamed Zaït, On the Effectiveness of Optimization Search Strategies for Parallel Execution Spaces, Proceedings of the 19th International Conference on Very Large Data Bases, p.493-504, August 24-27, 1993
• ML86: Lothar F. Mackert , Guy M. Lohman, R* Optimizer Validation and Performance Evaluation for Distributed Queries, Proceedings of the 12th International Conference on Very Large Data Bases, p.149-159, August 25-28, 1986
• MLR90: T. P. Martin , K. H. Lam , Judy I. Russell, An evaluation of site selection algorithms for distributed query processing, The Computer Journal, v.33 n.1, p.61-70, Feb. 1990 [doi>10.1093/comjnl/33.1.61]
• PCV94: Jignesh M. Patel , Michael J. Carey , Mary K. Vernon, Accurate modeling of the hybrid hash join algorithm, Proceedings of the 1994 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.56-66, May 16-20, 1994, Nashville, Tennessee, United States
• R+95: N. Roussopoulos, et al. The ADMS project: Views "R" us. IEEE Data Engeneering Bulletin, 18(2), 1995.
• S+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]
• S+90: M. Stonebraker, et aI. Third generation data base system manifesto. Technical Report, UC Berkeley, t990.
• S+94: Michael Stonebraker , Paul M. Aoki , Robert Devine , Witold Litwin , Michael A. Olson, Mariposa: A New Architecture for Distributed Data, Proceedings of the Tenth International Conference on Data Engineering, p.54-65, February 14-18, 1994
• SE93: Jaideep Srivastava, Optimizing multi-join queries in parallel relational databases, Proceedings of the second international conference on Parallel and distributed information systems, p.84-92, January 1993, San Diego, California, United States
• 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]

INDEX TERMS

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

General Terms:
Measurement, Performance, Theory