PostBOUND: PostgreSQL with Upper Bound SPJ Query Optimization

Research output: Contribution to book/Conference proceedings/Anthology/ReportConference contributionContributedpeer-review

Contributors

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

Original languageEnglish
Title of host publicationDatenbanksysteme fur Business, Technologie und Web, BTW 2023
EditorsBirgitta Konig-Ries, Stefanie Scherzinger, Wolfgang Lehner, Gottfried Vossen
PublisherGesellschaft fur Informatik (GI)
Pages283-304
Number of pages22
ISBN (electronic)9783885797258
Publication statusPublished - 2023
Peer-reviewedYes

Publication series

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

Symposium

Title20th Conference on Database Systems for Business, Technology and Web
Abbreviated titleBTW 2023
Conference number20
Duration6 - 10 March 2023
LocationTechnische Universität Dresden
CityDresden
CountryGermany

External IDs

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

Keywords

ASJC Scopus subject areas

Keywords

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