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

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

PDF
p18-flachs.pdf - Veröffentlichte Version
Download (780kB)

Weitere URL:	https://dblp.org/db/conf/cidr/cidr2022.html#Flachs...
URN:	urn:nbn:de:bsz:180-madoc-623657
Dokumenttyp:	Konferenzveröffentlichung
Erscheinungsjahr:	2022
Buchtitel:	12th Conference on Innovative Data Systems Research, CIDR 2022, Chaminade, Ca, USA, January 9-12, 2022
Seitenbereich:	1-9
Veranstaltungstitel:	CIDR 2022
Veranstaltungsort:	Chaminade, CA, Hybrid
Veranstaltungsdatum:	09.-12.01.2022
Ort der Veröffentlichung:	Chaminade
Verlag:	CIDR
Sprache der Veröffentlichung:	Englisch
Einrichtung:	Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik > Practical Computer Science III (Moerkotte 1996-)
Bereits vorhandene Lizenz:	Creative Commons Namensnennung 3.0 Unported (CC BY 3.0)
Fachgebiet:	004 Informatik
Freie Schlagwörter (Englisch):	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.
Zusätzliche Informationen:	Online-Ressource