On Optimizing Relational Self-Joins

Yu Cao, Yongluan Zhou, Chee Yong Chan, Kian-Lee Tan

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearch

Abstract

Self-join, which joins a relation with itself, is a prevalent operation in relational database systems. Despite its wide applicability, there has been little attention devoted to improving its performance. In this paper, we present SCALE (<u>S</u>ort for <u>C</u>lustered <u>A</u>ccess with <u>L</u>azy <u>E</u>valuation), an efficient self-join algorithm, which takes advantage of the fact that both inputs of a self-join operation are instances of the same relation. SCALE first sorts the relation on one join attribute, say R. A. In this way, for every value of the other join attribute, say R. B, its matching R. A tuples are essentially clustered. As SCALE scans the sorted relation, each tuple is joined with its matching tuples co-existing in memory. For tuples where full-range clustered accesses to their matching tuples are not possible, they are buffered and the unfinished part of join processing deferred. Such lazy evaluation minimizes the need for "random" access to the matching tuples. SCALE further optimizes the memory allocation for clustered access and lazy evaluation to keep the processing cost minimal. Our analytical study shows that SCALE degenerates gracefully to a Sort-Merge Join in the worst case. We have also implemented SCALE in PostgreSQL, and results of our extensive experimental study show that it outperforms both Sort-Merge Join and Hybrid Hash Join by a wide margin in (almost) all cases.
Original languageEnglish
Title of host publicationProceedings of the 15th International Conference on Extending Database Technology
Place of PublicationNew York
PublisherAssociation for Computing Machinery
Publication date2012
Pages120-131
ISBN (Electronic)978-1-4503-0790-1
DOIs
Publication statusPublished - 2012

Fingerprint Dive into the research topics of 'On Optimizing Relational Self-Joins'. Together they form a unique fingerprint.

Cite this