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


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


[img] 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




Dieser Eintrag ist Teil der Universitätsbibliographie.

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




Metadaten-Export


Zitation


+ Suche Autoren in

+ Download-Statistik

Downloads im letzten Jahr

Detaillierte Angaben



Sie haben einen Fehler gefunden? Teilen Sie uns Ihren Korrekturwunsch bitte hier mit: E-Mail


Actions (login required)

Eintrag anzeigen Eintrag anzeigen