PostBOUND: PostgreSQL with Upper Bound SPJ Query Optimization

Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/GutachtenBeitrag in KonferenzbandBeigetragenBegutachtung

Beitragende

Abstract

A variety of query optimization papers have shown the disastrous effect of poor cardinality estimates on the overall runtime for arbitrary select-project-join (SPJ) queries. Especially, underestimating join cardinalities for multi-joins can lead to catastrophic join orderings. A promising solution to overcome this problem is query optimization based on upper bounds for the join cardinalities. In this domain, our proposed UES concept is presently the most efficient technique featuring a simple, yet effective upper bound for an arbitrary number of joins. To foster research in that direction, we introduce PostBOUND, our generalized framework to seamlessly integrate upper bound SPJ query optimization in PostgreSQL. PostBOUND provides abstractions to calculate arbitrary upper bounds, to model joins required by an SPJ query and to iteratively construct an optimized join order. To highlight the extensibility of PostBOUND, and to show the research potential, we additionally present two tighter upper bound UES variants using top-k statistics in this paper. In our evaluation, we show the efficiency and applicability of PostBOUND on different workloads as well as using different PostgreSQL versions. Additionally, we evaluate both presented tighter upper bound variant ideas.

Details

OriginalspracheEnglisch
TitelDatenbanksysteme fur Business, Technologie und Web, BTW 2023
Redakteure/-innenBirgitta Konig-Ries, Stefanie Scherzinger, Wolfgang Lehner, Gottfried Vossen
Herausgeber (Verlag)Gesellschaft fur Informatik (GI)
Seiten283-304
Seitenumfang22
ISBN (elektronisch)9783885797258
PublikationsstatusVeröffentlicht - 2023
Peer-Review-StatusJa

Publikationsreihe

ReiheLecture Notes in Informatics (LNI), Proceedings - Series of the Gesellschaft fur Informatik (GI)
BandP-331
ISSN1617-5468

(Fach-)Tagung

Titel20. Fachtagung “Datenbanksysteme für Business, Technologie und Web” des Fachbereichs “Datenbanken und Informationssysteme” (DBIS) der Gesellschaft fürInformatik (GI)
KurztitelBTW 2023
Veranstaltungsnummer20
Dauer6 - 10 März 2023
OrtTechnische Universität Dresden
StadtDresden
LandDeutschland

Externe IDs

ORCID /0000-0001-8107-2775/work/194824067

Schlagworte

ASJC Scopus Sachgebiete

Schlagwörter

  • generalization, join cardinalities, join order, SPJ queries, upper bound