Please use this identifier to cite or link to this item:
https://doi.org/10.1145/2247596.2247612
Title: | On optimizing relational self-joins | Authors: | Cao, Y. Zhou, Y. Chan, C.-Y. Tan, K.-L. |
Keywords: | join algorithms join operation query optimization self-join |
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. https://doi.org/10.1145/2247596.2247612 | 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 | URI: | http://scholarbank.nus.edu.sg/handle/10635/41923 | 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.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.