Composition can be faster than join

Yao Nan Lien, Chih Lin Hu

Research output: Contribution to journalConference articlepeer-review


In relational databases, a composition requires three operations: join, projection and duplicate elimination. An expensive external sort is required to eliminate duplicates in a large file. Most conventional composition algorithms take join and duplicate elimination as separate operations to reduce overhead on either operation, but not both. Direct composition algorithms outperform all these algorithms by executing the composition as a single primitive. In this paper, we show that the direct composition can even outperform its component operation, join, under various conditions. Moreover, when the density of the joining attribute is high enough, the hot-spot direct composition may even run faster as the operand relations become bigger. These results can encourage real DBMSs to remove duplicates in some relational operations, and thus, to preserve the closure property of the relational data model.

Original languageEnglish
Pages (from-to)204-209
Number of pages6
JournalProceedings - IEEE Computer Society's International Computer Software and Applications Conference
StatePublished - 1997
EventProceedings of the 1997 21st Annual International Computer Software & Applications Conference, COMPSAC'97 - Washington, DC, USA
Duration: 13 Aug 199715 Aug 1997


Dive into the research topics of 'Composition can be faster than join'. Together they form a unique fingerprint.

Cite this