ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

PERF Join: An Alternative to Two-way Semijoin and Bloomjoin.

Zhe Li, Kenneth A. Ross: PERF Join: An Alternative to Two-way Semijoin and Bloomjoin. CIKM 1995: 137-144
@inproceedings{DBLP:conf/cikm/LiR95,
  author    = {Zhe Li and
               Kenneth A. Ross},
  title     = {PERF Join: An Alternative to Two-way Semijoin and Bloomjoin},
  booktitle = {CIKM '95, Proceedings of the 1995 International Conference on
               Information and Knowledge Management, November 28 - December
               2, 1995, Baltimore, Maryland, USA},
  publisher = {ACM},
  year      = {1995},
  pages     = {137-144},
  ee        = {db/conf/cikm/LiR95.html, http://doi.acm.org/10.1145/221270.221360},
  crossref  = {DBLP:conf/cikm/95},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

This paper presents "Positionally Encoded Record Filters" (PERFs) and describes their use in a distributed query processing technique called PERF join. A PERF is a novel two-way join reduction implementation primitive. While having the same storage and transmission efficiency as a hash filter (e.g., Bloom Filter), a PERF is based on the relation tuple scan order instead of hashing. Hence it doesn't suffer any loss of join information incurred by hash collisions. Using the query response time measured in terms of network cost as a comparison criterion, we demonstrate through analytical studies that PERF join performs significantly better than two-way Bloomjoin and two-way semijoin variants under a wide range of relevant cost parameter values. For the large number of distributed query processing algorithms relying on Bloomjoin or semijoin variants to reduce their network cost, we can sometimes gain an instant improvement in their response time by switching to PERF join instead. Other salient features of PERF join include cheap local join processing cost, and the capability to handle inequality and cyclic join queries.

Copyright © 1995 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.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 2 Issue 4, CIKM, DOLAP, GIS, SIGFIDET, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

CIKM '95, Proceedings of the 1995 International Conference on Information and Knowledge Management, November 28 - December 2, 1995, Baltimore, Maryland, USA. ACM 1995
Contents BibTeX

Online Edition

Citation Page BibTeX

References

[AHY83]
Peter M. G. Apers, Alan R. Hevner, S. Bing Yao: Optimization Algorithms for Distributed Queries. IEEE Trans. Software Eng. 9(1): 57-68(1983) BibTeX
[Bab79]
Edward Babb: Implementing a Relational Database by Means of Specialized Hardware. ACM Trans. Database Syst. 4(1): 1-29(1979) BibTeX
[BC81]
Philip A. Bernstein, Dah-Ming W. Chiu: Using Semi-Joins to Solve Relational Queries. J. ACM 28(1): 25-40(1981) BibTeX
[BG81]
Philip A. Bernstein, Nathan Goodman: Power of Natural Semijoins. SIAM J. Comput. 10(4): 751-771(1981) BibTeX
[BGW+81]
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) BibTeX
[Blo70]
Burton H. Bloom: Space/Time Trade-offs in Hash Coding with Allowable Errors. Commun. ACM 13(7): 422-426(1970) BibTeX
[CY93]
Ming-Syan Chen, Philip S. Yu: Combining Join and Semi-Join Operations for Distributed Query Processing. IEEE Trans. Knowl. Data Eng. 5(3): 534-542(1993) BibTeX
[Dan82]
...
[DNS91]
David J. DeWitt, Jeffrey F. Naughton, Donovan A. Schneider: An Evaluation of Non-Equijoin Algorithms. VLDB 1991: 443-452 BibTeX
[GL94]
Piyush Gupta, Eileen Tien Lin: DataJoiner: A Practical Approach to Multi-Database Access. PDIS 1994: 264 BibTeX
[Gra93]
Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993) BibTeX
[HS95]
Mauricio A. Hernández, Salvatore J. Stolfo: The Merge/Purge Problem for Large Databases. SIGMOD Conference 1995: 127-138 BibTeX
[HY79]
Alan R. Hevner, S. Bing Yao: Query Processing in Distributed Database Systems. IEEE Trans. Software Eng. 5(3): 177-187(1979) BibTeX
[LR94]
...
[LR95]
...
[ML86]
Lothar F. Mackert, Guy M. Lohman: R* Optimizer Validation and Performance Evaluation for Distributed Queries. VLDB 1986: 149-159 BibTeX
[Mul83]
James K. Mullin: A Second Look at Bloom Filters. Commun. ACM 26(8): 570-571(1983) BibTeX
[Mul90]
James K. Mullin: Optimal Semijoins for Distributed Database Systems. IEEE Trans. Software Eng. 16(5): 558-560(1990) BibTeX
[RK91]
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) BibTeX
[Seg86]
Arie Segev: Optimization of Join Operations in Horizontally Partitioned Database Systems. ACM Trans. Database Syst. 11(1): 48-80(1986) BibTeX
[Tem94]
Marjorie Templeton: InterViso: A Data Integration Server. PDIS 1994: 265-266 BibTeX
[WCS92]
...
[YC84]
Clement T. Yu, C. C. Chang: Distributed Query Processing. ACM Comput. Surv. 16(4): 399-433(1984) BibTeX
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
CIKM 1995 Proceedings, 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:01:48 2009