Load balancing in a locally distributed DB system

ABSTRACT

Most previous work on query optimization in distributed database systems has focused on finding optimal or near-optimal processing plans based solely on static system characteristics, and few researchers have addressed the problem of copy selection when data is replicated. This paper describes a new approach to query processing for locally distributed database systems. Our approach uses load information to select the processing site(s) for a query, dynamically choosing from among those sites that have copies of relations referenced by the query. Query compilation is used to produce a statically-optimized logical plan for the query, and then a dynamic optimization phase converts this logical plan into an executable physical plan at runtime. This paper motivates the separation of static and dynamic optimization, presents algorithms for the various phases of the optimization process, and describes a simulation study that was undertaken to investigate the performance of this approach. Our simulation results indicate that load-balanced query processing can provide improvements in both query response times and overall system throughput as compared to schemes where execution sites are either statistically or randomly selected.

REFERENCES

• Alon84: R Alonso, "Query opum#zauon m &stnbutcd database management systems through load balancing," talk presented at UW-Madmon, Apnl 1984
• Aper83: P M G Apcrs, A R Hevncr, and S B Yao, "OpUmlzauon algonthms for dlstnbuted quenes," IEEE Transactions on Software Engmeermg, SE-9, I, January 1983
• Bern81: Philip A. Bernstein , Nathan Goodman , Eugene Wong , Christopher L. Reeve , James B. Rothnie, Jr., Query processing in a system for distributed databases (SDD-1), ACM Transactions on Database Systems (TODS), v.6 n.4, p.602-625, Dec. 1981 [doi>10.1145/319628.319650]
• Brya81: R Bryant and R Fmkel, "A stable distributed scheduling algonthm," Proceedings of the 2rid Internanonal Conference on Distributed Compunng Systems, Apnl 1981
• Care85a: M J Carey, M Lwny, and H Lu, "Dynarmc task allocataon m a d#stnbuted database system," Proceedmgs of the 5th lnternattonal Conference on Dtstrtbuted Compunng Systems, Denver, May 1985
• Care85b: M J Carey and H Lu, "Load Balancing m a Locally D#smbuted Database System," Computer Sciences Techmcal Report #625, Computer Sciences Department, Umverslty of Wmconsm-Madlson, December 1985
• Chiu80: D. M. Chiu , Y. C. Ho, A methodology for interpreting tree queries into optimal semi-join expressions, Proceedings of the 1980 ACM SIGMOD international conference on Management of data, May 14-16, 1980, Santa Monica, California [doi>10.1145/582250.582277]
• DeWi85: D J DeWltt, R Fmkel, and M Solomon, "The Crystal mulucomputer design and #mplementalaon experience," Computer Sciences Techrncal Report #553, Computer Sciences Department, Umverstty of W#sconsm- Madison, September 1984
• Eage85: Derek L. Eager , Edward D. Lazowska , John Zahorjan, A comparison of receiver-initiated and sender-initiated adaptive load sharing (extended abstract), Proceedings of the 1985 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.1-3, August 1985, Austin, Texas, United States
• Epst78: Robert Epstein , Michael Stonebraker , Eugene Wong, Distributed query processing in a relational data base system, Proceedings of the 1978 ACM SIGMOD international conference on management of data, May 31-June 02, 1978, Austin, Texas [doi>10.1145/509252.509292]
• Hevn79: A R Hevner and S B Yao, "Query processing m &stnbuted database systems," IEEE Transacuons on Software Engmeermg, SE-5, 3, May 1979
• Jark84: Matthias Jarke , Jurgen Koch, Query Optimization in Database Systems, ACM Computing Surveys (CSUR), v.16 n.2, p.111-152, June 1984 [doi>10.1145/356924.356928]
• Kamb82: Yahiko Kambayashi , Masatoshi Yoshikawa , Shuzo Yajima, Query processing for distributed databases using generalized semi-joins, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida [doi>10.1145/582353.582381]
• Liu82: A C Lm and S K Chang, "Site selectaon m &stnbuted query processing," Proceedings of the Thtrd Internanonal Conference on Dtstrtbuted Computmg Systems, M#amt/Ft. Lauderdale, Honda, October 1982
• Livn82: Miron Livny , Myron Melman, Load balancing in homogeneous broadcast distributed systems, Proceedings of the Computer Network Performance Symposium, p.47-55, April 13-14, 1982, College Park, Maryland, United States
• Livn85: M Llvny, "DENET m a Modula-2 based s#mulatton language," Computer Sciences Department, Umvers#ty of W#sconsm-Ma&son, m preparauon
• Lohm85: G M Lohman, C Mohan, L M Haas, D Darnels, B G Lmdsay, P G Sehnger, and P F Wdms, "Query processing m R*," m Query Processing m Database Systems, W Klm, D S Remer, and D S Batory (editors), Spnnger-Vedag, Berlin/Heidelberg, 1985
• Lu85a: H Lu and M Carey, "Some expenmental results on dlsmbuted join algonthms m a local area network," Proceedings of the 11th Internauonal Conference on Very Large Data Bases, Stockholm, August 1985
• Lu85b: Hongjun Lu, Distributed query processing with load balancing in local area networks, 1985
• McCo81: Rob McCord, Sizing and data distribution for a distributed database machine, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582348]
• Ni82: L Nl, "A dlsmbuted load balancing algonthm for pomt-to-pomt local computer networks," Proceedings of COMPCON, Fall 1982
• Seli79: 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]
• Seli80: P G Sellnger and M Adlba, "Access path seleclaon m d#smbuted Database management systems," Proceedmgs of the First Internauonal Conference on Dzstrtbuted Data Bases, Aberdeen, 1980
• Ston85: M Stonebraker, "The case for shared nottung," presented at the International Workshop on Htgh Performance Transacuon Processmg, Asflomar, September 1985
• Wang85: Y T Wang and R J T Morns, "Load shanng m &smbuted systems," IEEE Transacuons on Computers, C- 34, 3, March 1985
• Wong77: E Wong, "Retrieving &spersed data from SDD-1 a system for distributed databases," Proceedings of the 2nd Berkeley Workshop on Dzstrtbuted Data Management and Computer Networks, May 1977
• Yu83: C. T. Yu , C. C. Chang, On the design of a query processing strategy in a distributed database environment, Proceedings of the 1983 ACM SIGMOD international conference on Management of data, May 23-26, 1983, San Jose, California
• Yu84: C. T. Yu , C. C. Chang, Distributed query processing, ACM Computing Surveys (CSUR), v.16 n.4, p.399-433, Dec. 1984 [doi>10.1145/3872.3874]

INDEX TERMS

Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

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

General Terms:
Algorithms, Design, Management, Performance