Please use this identifier to cite or link to this item:
Title: On optimizing relational self-joins
Authors: Cao, Y.
Zhou, Y.
Chan, C.-Y. 
Tan, K.-L. 
Keywords: join algorithms
join operation
query optimization
Issue Date: 2012
Citation: Cao, Y.,Zhou, Y.,Chan, C.-Y.,Tan, K.-L. (2012). On optimizing relational self-joins. ACM International Conference Proceeding Series : 120-131. ScholarBank@NUS Repository.
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 (Sort for Clustered Access with Lazy Evaluation), 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. © 2012 ACM.
Source Title: ACM International Conference Proceeding Series
ISBN: 9781450307901
DOI: 10.1145/2247596.2247612
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Nov 12, 2019

Page view(s)

checked on Oct 28, 2019

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.