ACM SIGMOD Anthology VLDB dblp.uni-trier.de

R* Optimizer Validation and Performance Evaluation for Distributed Queries.

Lothar F. Mackert, Guy M. Lohman: R* Optimizer Validation and Performance Evaluation for Distributed Queries. VLDB 1986: 149-159
@inproceedings{DBLP:conf/vldb/MackertL86,
  author    = {Lothar F. Mackert and
               Guy M. Lohman},
  editor    = {Wesley W. Chu and
               Georges Gardarin and
               Setsuo Ohsuga and
               Yahiko Kambayashi},
  title     = {R* Optimizer Validation and Performance Evaluation for Distributed
               Queries},
  booktitle = {VLDB'86 Twelfth International Conference on Very Large Data Bases,
               August 25-28, 1986, Kyoto, Japan, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1986},
  isbn      = {0-934613-18-4},
  pages     = {149-159},
  ee        = {db/conf/vldb/MackertL86.html},
  crossref  = {DBLP:conf/vldb/86},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Few database query optimizer models have been validated against actual performance. This paper extends an earlier optimizer validation and performance evaluation of R* to distributed queries, i.e. single SQL statements having tables at multiple sites. Actual R* message, I/O, and CPU resources consumed - and the corresponding costs estimated by the optimizer - were written to database tables using new SQL commands, permitting automated control from application programs for collecting, reducing, and comparing test data. A number of tests were run over a wide variety of dynamically-created test databases, SQL queries, and system parameters. Both high-speed networks (comparable to a local area network) and medium-speed long-haul networks (for linking geographically dispersed hosts) were evaluated. The tests confirmed the accuracy of R*'s message cost model and the significant contribution of local (CPU and I/O) costs, even for a medium-speed network. Although distributed queries consume more resources overall, the response time for some execution strategies improves disproportionately by exploiting both concurrency and reduced contention for buffers. For distributed joins in which a copy of the inner table must be transferred to the join site, shipping the whole inner table dominated the strategy of fetching only those inner tuples that matched each outer-table value, even though the former strategy may require additional I/O. Bloomjoins (hashed semijoins) consistently performed better than semijoins and the best R* strategies.

Copyright © 1986 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.


Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Wesley W. Chu, Georges Gardarin, Setsuo Ohsuga, Yahiko Kambayashi (Eds.): VLDB'86 Twelfth International Conference on Very Large Data Bases, August 25-28, 1986, Kyoto, Japan, Proceedings. Morgan Kaufmann 1986, ISBN 0-934613-18-4
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[APER 83]
Peter M. G. Apers, Alan R. Hevner, S. Bing Yao: Optimization Algorithms for Distributed Queries. IEEE Trans. Software Eng. 9(1): 57-68(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ASTR 80]
Morton M. Astrahan, Mario Schkolnick, Won Kim: Performance of the System R Access Path Selection Mechanism. IFIP Congress 1980: 487-491 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BABB 79]
Edward Babb: Implementing a Relational Database by Means of Specialized Hardware. ACM Trans. Database Syst. 4(1): 1-29(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BERN 79]
...
[BERN 81A]
Philip A. Bernstein, Dah-Ming W. Chiu: Using Semi-Joins to Solve Relational Queries. J. ACM 28(1): 25-40(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BERN 81B]
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 Trans. Database Syst. 6(4): 602-625(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BLOO 70]
Burton H. Bloom: Space/Time Trade-offs in Hash Coding with Allowable Errors. Commun. ACM 13(7): 422-426(1970) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BRAT 84]
Kjell Bratbergsengen: Hashing Methods and Relational Algebra Operations. VLDB 1984: 323-333 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CHAM 81]
Donald D. Chamberlin, Morton M. Astrahan, W. Frank King III, Raymond A. Lorie, James W. Mehl, Thomas G. Price, Mario Schkolnick, Patricia G. Selinger, Donald R. Slutz, Bradford W. Wade, Robert A. Yost: Support for Repetitive Transactions and Ad Hoc Queries in System R. ACM Trans. Database Syst. 6(1): 70-94(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CHAN 82]
Jo-Mei Chang: A Heuristic Approach to Distributed Query Processing. VLDB 1982: 54-61 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CHU 82]
...
[DANI 82]
Dean Daniels, Patricia G. Selinger, Laura M. Haas, Bruce G. Lindsay, C. Mohan, Adrian Walker, Paul F. Wilms: An Introduction to Distributed Query Compilation in R*. DDB 1982: 291-309 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DEWI 79]
David J. DeWitt: Query Execution in DIRECT. SIGMOD Conference 1979: 13-22 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DEWI 85]
David J. DeWitt, Robert H. Gerber: Multiprocessor Hash-Based Join Algorithms. VLDB 1985: 151-164 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[EPST 78]
Robert S. Epstein, Michael Stonebraker, Eugene Wong: Distributed Query Processing in a Relational Data Base System. SIGMOD Conference 1978: 169-180 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[EPST 80]
Robert S. Epstein, Michael Stonebraker: Analysis of Distributed Data Base Processing Strategies. VLDB 1980: 92-101 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HEVN 79]
Alan R. Hevner, S. Bing Yao: Query Processing in Distributed Database Systems. IEEE Trans. Software Eng. 5(3): 177-187(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KERS 82]
Larry Kerschberg, Peter D. Ting, S. Bing Yao: Query Optimization in Star Computer Networks. ACM Trans. Database Syst. 7(4): 678-711(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LIND 83]
Bruce G. Lindsay, Laura M. Haas, C. Mohan, Paul F. Wilms, Robert A. Yost: Computation and Communication in R*: A Distributed Database Manager. ACM Trans. Comput. Syst. 2(1): 24-38(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LOHM 84]
Guy M. Lohman, Dean Daniels, Laura M. Haas, Ruth Kistler, Patricia G. Selinger: Optimization of Nested Queries in a Distributed Relational Database. VLDB 1984: 403-415 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LOHM 85]
Guy M. Lohman, C. Mohan, Laura M. Haas, Dean Daniels, Bruce G. Lindsay, Patricia G. Selinger, Paul F. Wilms: Query Processing in R*. Query Processing in Database Systems 1985: 31-47 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LU 85]
Hongjun Lu, Michael J. Carey: Some Experimental Results on Distributed Join Algorithms in a Local Network. VLDB 1985: 292-304 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MACK 85]
Lothar F. Mackert, Guy M. Lohman: Index Scans Using a Finite LRU Buffer: A Validated I/O Model. ACM Trans. Database Syst. 14(3): 401-424(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MACK 86]
Lothar F. Mackert, Guy M. Lohman: R* Optimizer Validation and Performance Evaluation for Local Queries. SIGMOD Conference 1986: 84-95 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MENO 85]
...
[ONUE 83]
...
[PERR 84]
William Perrizo: A Method for Processing Distributed Database Queries. IEEE Trans. Software Eng. 10(4): 466-471(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[RDT 84]
...
[SELI 79]
Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SELI 80]
Patricia G. Selinger, Michel E. Adiba: Access Path Selection in Distributed Database Management Systems. ICOD 1980: 204-215 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SEVE 76]
Dennis G. Severance, Guy M. Lohman: Differential Files: Their Application to the Maintenance of Large Databases. ACM Trans. Database Syst. 1(3): 256-267(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[STON 82]
Michael Stonebraker, John Woodfill, Jeff Ranstrom, Marguerite C. Murphy, Joseph Kalash, Michael J. Carey, Kenneth Arnold: Performance Analysis of Distributed Data Base Systems. IEEE Database Eng. Bull. 5(4): 58-65(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[VALD 84]
Patrick Valduriez, Georges Gardarin: Join and Semijoin Algorithms for a Multiprocessor Database Machine. ACM Trans. Database Syst. 9(1): 133-161(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[VTAM 85]
...
[WONG 83]
Eugene Wong: Dynamic Rematerialization: Processing Distributed Queries Using Redundant Data. IEEE Trans. Software Eng. 9(3): 228-232(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[YAO 79]
S. Bing Yao: Optimization of Query Evaluation Algorithms. ACM Trans. Database Syst. 4(2): 133-155(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[YU 83]
Clement T. Yu, C. C. Chang: On the Design of a Query Processing Strategy in a Distributed Database Environment. SIGMOD Conference 1983: 30-39 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Tue Mar 16 02:21:58 2010 by Michael Ley (ley@uni-trier.de)