The complete story of joins (in hyper)

Neumann T, Leis V, Kemper A (2017)

Publication Type: Conference contribution

Publication year: 2017

Publisher: Gesellschaft fur Informatik (GI)

Book Volume: 265

Pages Range: 31-50

Conference Proceedings Title: Lecture Notes in Informatics (LNI), Proceedings - Series of the Gesellschaft fur Informatik (GI)

Event location: Stuttgart DE

ISBN: 9783885796596

Abstract

SQL has evolved into an (almost) fully orthogonal query language that allows (arbitrarily deeply) nested subqueries in nearly all parts of the query. In order to avoid recursive evaluation strategies which incur unbearable O(n2) runtime we need an extended relational algebra to translate such subqueries into non-standard join operators. This paper concentrates on the non-standard join operators beyond the classical textbook inner joins, outer joins and (anti) semi joins. Their implementations in HyPer were covered in previous publications which we refer to. In this paper we cover the new join operators mark-join and single-join at both levels: At the logical level we show the translation and reordering possibilities in order to effectively optimize the resulting query plans. At the physical level we describe hash-based and block-nested loop implementations of these new joins. Based on our database system HyPer, we describe a blue print for the complete query translation and optimization pipeline. The practical need for the advanced join operators is proven by an analysis of the two well known TPC-H and TPC-DS benchmarks which revealed that all variants are actually used in these query sets.

Authors with CRIS profile

Viktor Leis

Involved external institutions

Technische Universität München (TUM) DE Germany (DE)

How to cite

APA:

Neumann, T., Leis, V., & Kemper, A. (2017). The complete story of joins (in hyper). In Bernhard Mitschang, Daniela Nicklas, Frank Leymann, Harald Schoning, Melanie Herschel, Jens Teubner, Theo Harder (Eds.), Lecture Notes in Informatics (LNI), Proceedings - Series of the Gesellschaft fur Informatik (GI) (pp. 31-50). Stuttgart, DE: Gesellschaft fur Informatik (GI).

MLA:

Neumann, Thomas, Viktor Leis, and Alfons Kemper. "The complete story of joins (in hyper)." Proceedings of the Datenbanksysteme fur Business, Technologie und Web, BTW 2017, 17. Fachtagung des GI-Fachbereichs "Datenbanken und Informationssysteme", DBIS - Database Systems for Business, Technology and Web, BTW 2017, 17th Symposium of the GI Department "Databases and Information Systems", DBIS, Stuttgart Ed. Bernhard Mitschang, Daniela Nicklas, Frank Leymann, Harald Schoning, Melanie Herschel, Jens Teubner, Theo Harder, Gesellschaft fur Informatik (GI), 2017. 31-50.

BibTeX: Download