The 3D hash join: Building on non-unique join attributes

Flachs, Daniel ; Müller, Magnus ; Moerkotte, Guido

[img] PDF
p18-flachs.pdf - Published

Download (780kB)

Additional URL:
URN: urn:nbn:de:bsz:180-madoc-623657
Document Type: Conference or workshop publication
Year of publication: 2022
Book title: 12th Conference on Innovative Data Systems Research, CIDR 2022, Chaminade, Ca, USA, January 9-12, 2022
Page range: 1-9
Conference title: CIDR 2022
Location of the conference venue: Chaminade, CA, Hybrid
Date of the conference: 09.-12.01.2022
Place of publication: Chaminade
Publishing house: CIDR
Publication language: English
Institution: School of Business Informatics and Mathematics > Practical Computer Science III (Moerkotte 1996-)
Pre-existing license: Creative Commons Attribution 3.0 Unported (CC BY 3.0)
Subject: 004 Computer science, internet
Keywords (English): hash join , hash table , skew , query processing , physical algebra
Abstract: One of the most prominent ways to evaluate an equi-join is based on hashing. We consider the problem of non-unique join attributes on the build side. In conventional hash tables where collisions are resolved by chaining, duplicates inevitably lead to long collision chains. This causes a high number of expensive main memory accesses and join predicate evaluations during the probe phase, increasing the runtime of the overall join. A related problem occurs when the query optimizer cannot determine the uniqueness of the join attribute of the build side. We present the 3D Hash Join to efficiently evaluate main-memory hash joins in the presence of duplicate build keys and skew. The main idea is to cluster the hash table collision chains based on the distinct values of the build attribute. We further introduce a technique called deferred unnesting to speed up the evaluation of multiple joins. In an experimental comparison with an implementation of a chaining hash table, our approach achieves a speedup of up to a factor of 3.53 for a single key/foreign key join and 5.67 for many-to-many joins.
Additional information: Online-Ressource

Dieser Eintrag ist Teil der Universitätsbibliographie.

Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt.

Metadata export


+ Search Authors in

+ Download Statistics

Downloads per month over past year

View more statistics

You have found an error? Please let us know about your desired correction here: E-Mail

Actions (login required)

Show item Show item