Distributive Join: A New Algorithm for Joining Relations.

Mauro Negri, Giuseppe Pelagatti: Distributive Join: A New Algorithm for Joining Relations. ACM Trans. Database Syst. 16(4): 655-669(1991)
  author    = {Mauro Negri and
               Giuseppe Pelagatti},
  title     = {Distributive Join: A New Algorithm for Joining Relations},
  journal   = {ACM Trans. Database Syst.},
  volume    = {16},
  number    = {4},
  year      = {1991},
  pages     = {655-669},
  ee        = {, db/journals/tods/NegriP91.html},
  bibsource = {DBLP,}


This paper describes a new algorithm for performing joins in the absence of access paths. This algorithm is shown to perform better than the Merging Scan algorithm, which can be considered the paradigm of join algorithms. Finally this algorithm is compared with another recent sub-sort-merge algorithm.

Copyright © 1991 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 2, TODS 1991-1995, TKDE 1989-1992" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Online Edition: ACM Digital Library

[Index Terms and Review]
[Full Text in PDF Format, 823 KB]


Mike W. Blasgen, Kapali P. Eswaran: Storage and Access in Relational Data Bases. IBM Systems Journal 16(4): 362-377(1977) BibTeX
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
Won Kim: A New Way to Compute the Product and Join of Relations. SIGMOD Conference 1980: 179-187 BibTeX
John Miles Smith, Philip Yen-Tang Chang: Optimizing the Performance of a Relational Algebra Database Interface. Commun. ACM 18(10): 568-579(1975) BibTeX
S. Bing Yao: Optimization of Query Evaluation Algorithms. ACM Trans. Database Syst. 4(2): 133-155(1979) BibTeX
Mauro Negri, Giuseppe Pelagatti: Join During Merge: An Improved Sort Based Algorithm. Inf. Process. Lett. 21(1): 11-16(1985) BibTeX
Giovanni Maria Sacco: Fragmentation: A Technique for Efficient Query Processing. ACM Trans. Database Syst. 11(2): 113-133(1986) BibTeX
Leonard D. Shapiro: Join Processing in Database Systems with Large Main Memories. ACM Trans. Database Syst. 11(3): 239-264(1986) BibTeX
Won Kim: On Optimizing an SQL-like Nested Query. ACM Trans. Database Syst. 7(3): 443-469(1982) BibTeX
Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984) BibTeX
Dina Bitton, David J. DeWitt: Duplicate Record Elimination in Large Data Files. ACM Trans. Database Syst. 8(2): 255-265(1983) BibTeX
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
W. D. Maurer, T. G. Lewis: Hash Table Methods. ACM Comput. Surv. 7(1): 5-19(1975) BibTeX
Clifford A. Lynch: Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distribution of Column Values. VLDB 1988: 240-251 BibTeX

Referenced by

  1. Lars Bækgaard, Leo Mark: Incremental Computation of Nested Relational Query Expressions. ACM Trans. Database Syst. 20(2): 111-148(1995)
  2. Soon Myoung Chung, Jaerheen Yang: Distributive Join Algorithm for Cube-Connected Multiprocessors. DASFAA 1993: 253-260
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Tue Jun 24 18:39:11 2008