ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Some Experimental Results on Distributed Join Algorithms in a Local Network.

Hongjun Lu, Michael J. Carey: Some Experimental Results on Distributed Join Algorithms in a Local Network. VLDB 1985: 292-304
@inproceedings{DBLP:conf/vldb/LuC85,
  author    = {Hongjun Lu and
               Michael J. Carey},
  editor    = {Alain Pirotte and
               Yannis Vassiliou},
  title     = {Some Experimental Results on Distributed Join Algorithms in a
               Local Network},
  booktitle = {VLDB'85, Proceedings of 11th International Conference on Very
               Large Data Bases, August 21-23, 1985, Stockholm, Sweden},
  publisher = {Morgan Kaufmann},
  year      = {1985},
  pages     = {292-304},
  ee        = {db/conf/vldb/LuC85.html},
  crossref  = {DBLP:conf/vldb/85},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

This paper presents some experimental results on the performance of distributed join algorithms in a local network. Eight different join methods have been implemented in an experimental distributed system, the Crystal multicomputer, and tested for join queries with a variety of relation sizes, join selectivities, and join column value distributions. The results obtained indicate that pipelined join methods outperform sequential methods over a wide range of join queries. It was also found that the communications costs in a local network environment are not a dominant factor with respect to performance, and that shipping a whole relation from one site to another is not an unreasonahle decison as long as it is done in the framework of pipelined algorithms. Two pipelined variants of a centralized nested loops join algorithm (with an index) were found to perform well for many of the queries tested.

Copyright © 1985 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 ... BibTeX

Printed Edition

Alain Pirotte, Yannis Vassiliou (Eds.): VLDB'85, Proceedings of 11th International Conference on Very Large Data Bases, August 21-23, 1985, Stockholm, Sweden. Morgan Kaufmann 1985
Contents BibTeX

References

[Bern79a]
...
[Bern79b]
...
[Bern81a]
Philip A. Bernstein, Dah-Ming W. Chiu: Using Semi-Joins to Solve Relational Queries. J. ACM 28(1): 25-40(1981) BibTeX
[Bern81b]
Philip A. Bernstein, Nathan Goodman: Power of Natural Semijoins. SIAM J. Comput. 10(4): 751-771(1981) BibTeX
[Bitt83]
Dina Bitton, David J. DeWitt, Carolyn Turbyfill: Benchmarking Database Systems A Systematic Approach. VLDB 1983: 8-19 BibTeX
[Blas76]
...
[Brab84]
Kjell Bratbergsengen: Hashing Methods and Relational Algebra Operations. VLDB 1984: 323-333 BibTeX
[Care85]
Michael J. Carey, Miron Livny, Hongjun Lu: Dynamic Task Allocation in a Distributed Database System. ICDCS 1985: 282-291 BibTeX
[Chou83]
Hong-Tai Chou, David J. DeWitt, Randy H. Katz, Anthony C. Klug: Design and Implementation of the Wisconsin Storage System. Softw., Pract. Exper. 15(10): 943-962(1985) BibTeX
[DeWi84]
David J. DeWitt, Raphael A. Finkel, Marvin H. Solomon: The Crystal Multicomputer: Design and Implementation Experience. IEEE Trans. Software Eng. 13(8): 953-966(1987) BibTeX
[DeWi85]
...
[Epst80]
Robert S. Epstein, Michael Stonebraker: Analysis of Distributed Data Base Processing Strategies. VLDB 1980: 92-101 BibTeX
[Kers82]
Larry Kerschberg, Peter D. Ting, S. Bing Yao: Query Optimization in Star Computer Networks. ACM Trans. Database Syst. 7(4): 678-711(1982) BibTeX
[Lohm84]
...
[Nieb76]
...
[Page83]
...
[Seli79]
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 BibTeX
[Seli80]
Patricia G. Selinger, Michel E. Adiba: Access Path Selection in Distributed Database Management Systems. ICOD 1980: 204-215 BibTeX
[Smit75]
John Miles Smith, Philip Yen-Tang Chang: Optimizing the Performance of a Relational Algebra Database Interface. Commun. ACM 18(10): 568-579(1975) BibTeX
[Ullm82]
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX
[Wong76]
Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing. ACM Trans. Database Syst. 1(3): 223-241(1976) BibTeX
[Yao78]
S. Bing Yao, D. DeJong: Evaluation of Database Access Paths. SIGMOD Conference 1978: 66-77 BibTeX
[Yao79]
S. Bing Yao: Optimization of Query Evaluation Algorithms. ACM Trans. Database Syst. 4(2): 133-155(1979) BibTeX

Referenced by

  1. Mary Tork Roth, Peter M. Schwarz: Don't Scrap It, Wrap It! A Wrapper Architecture for Legacy Data Sources. VLDB 1997: 266-275
  2. Michael J. Franklin, Björn Þór Jónsson, Donald Kossmann: Performance Tradeoffs for Client-Server Query Processing. SIGMOD Conference 1996: 149-160
  3. Manish Mehta, David J. DeWitt: Managing Intra-operator Parallelism in Parallel Database Systems. VLDB 1995: 382-394
  4. Jörg Liebeherr, Edward Omiecinski, Ian F. Akyildiz: The Effect of Index Partitioning Schemes on the Performance of Distributed Query Processing. IEEE Trans. Knowl. Data Eng. 5(3): 510-522(1993)
  5. Priti Mishra, Margaret H. Eich: Join Processing in Relational Databases. ACM Comput. Surv. 24(1): 63-113(1992)
  6. Nick Roussopoulos, Hyunchul Kang: A Pipeline N-way Join Algorithm Based on the 2-way Semijoin Program. IEEE Trans. Knowl. Data Eng. 3(4): 486-495(1991)
  7. Donovan A. Schneider, David J. DeWitt: Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines. VLDB 1990: 469-480
  8. Hongjun Lu, Kian-Lee Tan, Ming-Chien Shan: Hash-Based Join Algorithms for Multiprocessor Computers. VLDB 1990: 198-209
  9. Clement T. Yu, Chengwen Liu: Experiences with Distributed Query Processing. ICDE 1990: 192-199
  10. Arie Segev, Himawan Gunadhi: Event-Join Optimization in Temporal Relational Databases. VLDB 1989: 205-215
  11. Ming-Chien Shan: Optimal Plan Search in a Rule-Based Query Optimizer. EDBT 1988: 92-112
  12. James P. Richardson, Hongjun Lu, Krishna P. Mikkilineni: Design and Evaluation of Parallel Pipelined Join Algorithms. SIGMOD Conference 1987: 399-409
  13. Roger Shultz, Ila Miller: Tree Structured Multiple Processor Join Methods. ICDE 1987: 190-199
  14. Stéphane Lafortune, Eugene Wong: A State Transition Model for Distributed Query Processing. ACM Trans. Database Syst. 11(3): 294-322(1986)
  15. Lothar F. Mackert, Guy M. Lohman: R* Optimizer Validation and Performance Evaluation for Distributed Queries. VLDB 1986: 149-159
  16. Lothar F. Mackert, Guy M. Lohman: R* Optimizer Validation and Performance Evaluation for Local Queries. SIGMOD Conference 1986: 84-95
  17. Michael J. Carey, Hongjun Lu: Load Balancing in a Locally Distributed Database System. SIGMOD Conference 1986: 108-119
  18. Stanley Y. W. Su, Krishna P. Mikkilineni, Raymond A. Liuzzi, Yuan-Chieh Chow: A Distributed Query Processing Strategy Using Decomposition, Pipelining and Intermediate Result Sharing Techniques. ICDE 1986: 94-102
  19. Guy M. Lohman: Do semantically equivalent SQL queries perform differently? ICDE 1986: 225-226
  20. Jiawei Han, Hongjun Lu: Some Performance Results on Recursive Query Processing in Relational Database Systems. ICDE 1986: 533-541
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
 ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:45:24 2009