Article

Free access

A performance evaluation of pointer-based joins

Authors:

Eugene J. Shekita,

Michael J. CareyAuthors Info & Claims

SIGMOD '90: Proceedings of the 1990 ACM SIGMOD international conference on Management of data

Pages 300 - 311

https://doi.org/10.1145/93597.98739

Published: 01 May 1990 Publication History

Abstract

In this paper we describe three pointer-based join algorithms that are simple variants of the nested-loops, sort-merge, and hybrid-hash join algorithms used in relational database systems. Each join algorithm is described and an analysis is carried out to compare the performance of the pointer-based algorithms to their standard, non-pointer-based counterparts. The results of the analysis show that the pointer-based algorithms can provide significant performance gains in many situations. The results also show that the pointer-based nested-loops join algorithm, which is perhaps the most natural pointer-based join algorithm to consider using in an object-oriented database system, performs quite poorly on most medium to large joins.

References

[1]

M Blasgen and K Eswaran, "Storage and Access m Relational Databases," IBM Syst Journal, 16(4), 1977

Digital Library

[2]

M Carey et al, "A Data Model and Query Language for EXODUS," Proc of the 1988 ACM-SIGMOD Conf, Chicago, IL, 1988

Digital Library

[3]

M Carey et al, 'The EXODUS Extenslble DBMS Project An Overview," m Readings m Object-Ortented Databases, S Zdomk and D Maaer, eds, Morgan-Kaufman Publ Co, 1989

Digital Library

[4]

M Carey et al, "An Incremental Join Attachment for Starburst," submltted for pubhcatlon

[5]

A Chart, "Storage and Access Structures to Support a Semantic Data Model," Proc of the 1982 VLDB Conf, Mexico City, Mexico, 1982

Digital Library

[6]

D DeWltt and R Gerber, "Multaprocessor Hash-Based Join Algorithms," Proc of the 1985 VLDB Conf, Stockholm, Sweden, Aug 1985

[7]

O Deux et al, 'The Story of 02," IEEE Trans on Knowledge and Data Eng, March 1990

Digital Library

[8]

L Haas et al, "Starburst M~d-Fllght As the Dust Clears," IEEE Trans on Knowledge and Data Engineering, March 1990

Digital Library

[9]

W Kam, "A Model of Queries for Object-Oriented Databases," Proc of the 1989 VLDB Con:f, Amsterdam, The Netherlands, Aug 1989

Digital Library

[10]

L Mackert and G Lohman, "R* Optimizer Vahdatlon and Performance Evaluation for Local Quenes," Proc of the ACM-SIGMOD Conf, Washtngton, D C, 1986

Digital Library

[11]

L Mackert and G Lohman, "Index Scans Using a Finite LRU Buffer A Validated I/O Model," ACM Trans on Database Systems 14(3), Sept 1989

Digital Library

[12]

D Severance and G Lohman, "Differential Flies Their Apphcat~on to the Maintenance of Large Databases," ACM Trans on Database Systems 1(3), Sept 1976

Digital Library

[13]

L Shaptro, "Join Processing m Database Systems with Large Mare Memones," ACM Trans on Database Systems 11(3), Sept 1986

Digital Library

[14]

E Shekata and M Carey, "A Performance Evaluation of Pointer-Based Joins," Umv of Wisconsin Tech Report #916, March 1990

[15]

D Shipman, '"The Functional Data Model and the Data Language DAPLEX," ACM Trans on Database Sys 6(1), Sept 1987

Digital Library

[16]

P Valdunez, "Join indices," ACM Trans on Database Systems 12(2), June 1987

Digital Library

[17]

F Velez et al, 'The 02 Object Manager An Overview," Proc 1989 VLDB Conf, Amsterdam, The Netherlands, Aug 1989

Digital Library

[18]

S Yao, "Approxamatmg Block Accesses m Database Orgamzatlons," Comm of the ACM 20(4), April 1977

Digital Library

[19]

C Zamolo, "The Database Language GEM," Proc of the ACM-SIGMOD Conf, San Jose, CA, 1983

Digital Library

Cited By

Yadav ASingh KAmin AAlmutairi LAlsenani TAhmadian A(2023)A comparative study on consensus mechanism with security threats and future scopesComputer Communications10.1016/j.comcom.2023.01.018201:C(102-115)Online publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1016/j.comcom.2023.01.018
Chen MZhong Z(2014)Block Nested Join and Sort Merge Join Algorithms: An Empirical EvaluationAdvanced Data Mining and Applications10.1007/978-3-319-14717-8_56(705-715)Online publication date: 2014
https://doi.org/10.1007/978-3-319-14717-8_56
Graefe G(2012)New algorithms for join and grouping operationsComputer Science - Research and Development10.1007/s00450-011-0186-927:1(3-27)Online publication date: 1-Feb-2012
https://dl.acm.org/doi/10.1007/s00450-011-0186-9
Show More Cited By

Index Terms

A performance evaluation of pointer-based joins
1. Information systems
  1. Data management systems
    1. Database design and models
    2. Database management system engines
      1. Database query processing
2. Theory of computation
  1. Design and analysis of algorithms
    1. Data structures design and analysis
      1. Sorting and searching
  2. Theory and algorithms for application domains
    1. Database theory
      1. Database query processing and optimization (theory)

Recommendations

A performance evaluation of pointer-based joins

In this paper we describe three pointer-based join algorithms that are simple variants of the nested-loops, sort-merge, and hybrid-hash join algorithms used in relational database systems. Each join algorithm is described and an analysis is carried out ...
Interprocedural pointer alias analysis

We present practical approximation methods for computing and representing interprocedural aliases for a program written in a language that includes pointers, reference parameters, and recursion. We present the following contributions: (1) a framework ...
Using slice join for efficient evaluation of multi-way joins

A standard hash join algorithm joins two relations at a time and requires reading the entire smaller input before results are generated. There has been recent focus on constructing join algorithms that produce results faster and can join more than two ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '90: Proceedings of the 1990 ACM SIGMOD international conference on Management of data

May 1990

398 pages

ISBN:0897913655

DOI:10.1145/93597

Chairman:
Hector Garcia-Molina
Princeton Univ., Princeton, NJ

ACM SIGMOD Record Volume 19, Issue 2
Jun. 1990
392 pages
ISSN:0163-5808
DOI:10.1145/93605
Editor:
H. V. Jagadish
AT&T Bell Laboratories, Murray Hill, NJ
Issue’s Table of Contents

Copyright © 1990 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1990

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGMOD 90

Sponsor:

SIGMOD

SIGMOD 90: SIGMOD'90

May 23 - 26, 1990

New Jersey, Atlantic City, USA

Acceptance Rates

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

75
Total Citations
View Citations
638
Total Downloads

Downloads (Last 12 months)90
Downloads (Last 6 weeks)17

Reflects downloads up to 28 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yadav ASingh KAmin AAlmutairi LAlsenani TAhmadian A(2023)A comparative study on consensus mechanism with security threats and future scopesComputer Communications10.1016/j.comcom.2023.01.018201:C(102-115)Online publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1016/j.comcom.2023.01.018
Chen MZhong Z(2014)Block Nested Join and Sort Merge Join Algorithms: An Empirical EvaluationAdvanced Data Mining and Applications10.1007/978-3-319-14717-8_56(705-715)Online publication date: 2014
https://doi.org/10.1007/978-3-319-14717-8_56
Graefe G(2012)New algorithms for join and grouping operationsComputer Science - Research and Development10.1007/s00450-011-0186-927:1(3-27)Online publication date: 1-Feb-2012
https://dl.acm.org/doi/10.1007/s00450-011-0186-9
Dogac AAltinel MOzkan CArpinar BDurusoy IAltintas I(2006)METU Object-Oriented DBMS kernelDatabase and Expert Systems Applications10.1007/BFb0049101(14-27)Online publication date: 1-Feb-2006
https://doi.org/10.1007/BFb0049101
Kemper AWiesner C(2005)Building Scalable Electronic Market Places Using HyperQuery-Based Distributed Query ProcessingWorld Wide Web10.1023/B:WWWJ.0000047379.18584.318:1(27-60)Online publication date: 1-Mar-2005
https://dl.acm.org/doi/10.1023/B%3AWWWJ.0000047379.18584.31
Bremer JGertz M(2005)Integrating document and data retrieval based on XMLThe VLDB Journal10.1007/s00778-005-0150-zOnline publication date: 12-Aug-2005
https://doi.org/10.1007/s00778-005-0150-z
Tang ZGardarin GSmahi V(2005)Optimizing path expressions using navigational algebraic operatorsDatabase and Expert Systems Applications10.1007/BFb0034712(574-583)Online publication date: 26-Jun-2005
https://doi.org/10.1007/BFb0034712
Gesmann M(2005)Mapping a parallel complex-object DBMS to operating system processesEuro-Par'96 Parallel Processing10.1007/BFb0024786(852-861)Online publication date: 10-Jun-2005
https://doi.org/10.1007/BFb0024786
Steenhagen Hde By RBlanken H(2005)Translating OSQL queries into efficient set expressionsAdvances in Database Technology — EDBT '9610.1007/BFb0014152(183-197)Online publication date: 10-Jun-2005
https://doi.org/10.1007/BFb0014152
Al-Khalifa SJagadish HKoudas NPatel JSrivastava DYuqing Wu (2002)Structural joins: a primitive for efficient XML query pattern matchingProceedings 18th International Conference on Data Engineering10.1109/ICDE.2002.994704(141-152)Online publication date: 2002
https://doi.org/10.1109/ICDE.2002.994704
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten