Fast Joins Using Join Indices.

Zhe Li, Kenneth A. Ross: Fast Joins Using Join Indices. VLDB J. 8(1): 1-24(1999)

@article{DBLP:journals/vldb/LiR99,
  author    = {Zhe Li and
               Kenneth A. Ross},
  title     = {Fast Joins Using Join Indices},
  journal   = {VLDB J.},
  volume    = {8},
  number    = {1},
  year      = {1999},
  pages     = {1-24},
  ee        = {db/journals/vldb/LiR99.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Two new algorithms, "Jive join" and "Slam join," are proposed for computing the join of two relations using a join index. The algorithms are duals: Jive join range-partitions input relation tuple ids and then processes each partition, while Slam join forms ordered runs of input relation tuple ids and then merges the results. Both algorithms make a single sequential pass through each input relation, in addition to one pass through the join index and two passes through a temporary file, whose size is half that of the join index. Both algorithms require only that the number of blocks in main memory is of the order of the square root of the number of blocks in the smaller relation. By storing intermediate and final join results in a vertically partitioned fashion, our algorithms need to manipulate less data in memory at a given time than other algorithms. The algorithms are resistant to data skew and adaptive to memory fluctuations. Selection conditions can be incorporated into the algorithms. Using a detailed cost model, the algorithms are analyzed and compared with competing algorithms. For large input relations, our algorithms perform significantly better than Valduriez's algorithm, the TID join algorithm, and hash join algorithms. An experimental study is also conducted to validate the analytical results and to demonstrate the performance characteristics of each algorithm in practice.

Key Words

Query processing - Decision support systems

Copyright © 1999 by Springer, Berlin, Heidelberg. Permission to make digital or hard copies of the abstract is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice along with the full citation.

Online Edition (Springer)

Citation Page

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 5 Issue 2, JACM, VLDB-J, POS, ..." and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/An5-2 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD2 or /dvd

References

[Agrawal et al. 1994]: Rakesh Agrawal, Michael J. Carey, Christos Faloutsos, Sakti P. Ghosh, Maurice A. W. Houtsma, Tomasz Imielinski, Balakrishna R. Iyer, A. Mahboob, H. Miranda, Ramakrishnan Srikant, Arun N. Swami: Quest: A Project on Database Mining. SIGMOD Conference 1994: 514
[Batory 1979]: Don S. Batory: On Searching Transposed Files. ACM Trans. Database Syst. 4(4): 531-544(1979)
[Bitton et al. 1983]: Dina Bitton, David J. DeWitt, Carolyn Turbyfill: Benchmarking Database Systems A Systematic Approach. VLDB 1983: 8-19
[Blakeley and Martin 1990]: José A. Blakeley, Nancy L. Martin: Join Index, Materialized View, and Hybrid-Hash Join: A Performance Analysis. ICDE 1990: 256-263
[Blasgen and Eswaran 1977]: Mike W. Blasgen, Kapali P. Eswaran: Storage and Access in Relational Data Bases. IBM Systems Journal 16(4): 362-377(1977)
[Bratbergsengen 1984]: Kjell Bratbergsengen: Hashing Methods and Relational Algebra Operations. VLDB 1984: 323-333
[Brown et al. 1992]: ...
[Cheng et al. 1991]: Josephine M. Cheng, Donald J. Haderle, Richard Hedges, Balakrishna R. Iyer, Ted Messinger, C. Mohan, Yun Wang: An Efficient Hybrid Join Algorithm: A DB2 Prototype. ICDE 1991: 171-180
[Chou et al. 1985]: 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)
[Colby et al. 1994]: Latha S. Colby, Nancy L. Martin, Robert M. Wehrmeister: Query Processing for Decision Support: The SQLmpp Solution. PDIS 1994: 121-130
[DeWitt et al. 1984]: David J. DeWitt, Randy H. Katz, Frank Olken, Leonard D. Shapiro, Michael Stonebraker, David A. Wood: Implementation Techniques for Main Memory Database Systems. SIGMOD Conference 1984: 1-8
[Dozier 1992]: Jeff Dozier: Access to Data in NASA's Earth Observing System. SIGMOD Conference 1992: 1
[Graefe 1992]: ...
[Graefe et al. 1994]: Goetz Graefe, Ann Linville, Leonard D. Shapiro: Sort versus Hash Revisited. IEEE Trans. Knowl. Data Eng. 6(6): 934-944(1994)
[Gupta and Mumick 1997]: ...
[Haas et al. 1997]: ...
[Haas et al. 1997]: Laura M. Haas, Michael J. Carey, Miron Livny, Amit Shukla: Seeking the Truth About ad hoc Join Costs. VLDB J. 6(3): 241-256(1997)
[Hoare 1962]: C. A. R. Hoare: Quicksort. Comput. J. 5(1): 10-15(1962)
[Kemper and Moerkotte 1990]: Alfons Kemper, Guido Moerkotte: Access Support in Object Bases. SIGMOD Conference 1990: 364-374
[Kim 1980]: Won Kim: A New Way to Compute the Product and Join of Relations. SIGMOD Conference 1980: 179-187
[Kimball and Strehlo 1995]: Ralph Kimball, Kevin Strehlo: Why Decision Support Fails and How To Fix It. SIGMOD Record 24(3): 92-97(1995)
[Kooi 1980]: Robert Kooi: The Optimization of Queries in Relational Databases. Ph.D. thesis, Case Western Reserve University 1980
[Lei and Ross 1998]: Hui Lei, Kenneth A. Ross: Faster Joins, Self-Joins and Multi-Way Joins Using Join Indices. Data Knowl. Eng. 28(3): 277-298(1998)
[Li and Ross 1995]: ...
[Li and Ross 1996]: ...
[Lu and Han 1992]: Wei Lu, Jiawei Han: Distance-Associated Join Indices for Spatial Range Search. ICDE 1992: 284-292
[MacNicol 1997]: ...
[Mishra and Eich 1992]: Priti Mishra, Margaret H. Eich: Join Processing in Relational Databases. ACM Comput. Surv. 24(1): 63-113(1992)
[Mohan et al. 1990]: C. Mohan, Donald J. Haderle, Yun Wang, Josephine M. Cheng: Single Table Access Using Multiple Indexes: Optimization, Execution, and Concurrency Control Techniques. EDBT 1990: 29-43
[Murphy and rotem 1993]: Marguerite C. Murphy, Doron Rotem: Multiprocessor Join Scheduling. IEEE Trans. Knowl. Data Eng. 5(2): 322-338(1993)
[O'Neilland Graefe 1995]: Patrick E. O'Neil, Goetz Graefe: Multi-Table Joins Through Bitmapped Join Indices. SIGMOD Record 24(3): 8-11(1995)
[Ross 1995]: Kenneth A. Ross: Efficiently Following Object References for Large Object Collections and Small Main Memory. DOOD 1995: 73-90
[Rotem 1991]: Doron Rotem: Spatial Join Indices. ICDE 1991: 500-509
[Shapiro 1986]: Leonard D. Shapiro: Join Processing in Database Systems with Large Main Memories. ACM Trans. Database Syst. 11(3): 239-264(1986)
[Shekita and Carey 1990]: Eugene J. Shekita, Michael J. Carey: A Performance Evaluation of Pointer-Based Joins. SIGMOD Conference 1990: 300-311
[Silberschatz et al. 1997]: Abraham Silberschatz, Henry F. Korth, S. Sudarshan: Database System Concepts, 3rd Edition. McGraw-Hill Book Company 1997, ISBN 0-07-044756-X
[Stonebraker 1981]: Michael Stonebraker: Operating System Support for Database Management. Commun. ACM 24(7): 412-418(1981)
[Valduriez 1987]: Patrick Valduriez: Join Indices. ACM Trans. Database Syst. 12(2): 218-246(1987)
[Xie and Han 1994]: Zhaohui Xie, Jiawei Han: Join Index Hierarchies for Supporting Efficient Navigations in Object-Oriented Databases. VLDB 1994: 522-533
[Yao 1977]: S. Bing Yao: Approximating the Number of Accesses in Database Organizations. Commun. ACM 20(4): 260-261(1977)