PostBOUND: PostgreSQL with Upper Bound SPJ Query Optimization
Research output: Contribution to book/Conference proceedings/Anthology/Report › Conference contribution › Contributed › peer-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 language | English |
|---|---|
| Title of host publication | Datenbanksysteme fur Business, Technologie und Web, BTW 2023 |
| Editors | Birgitta Konig-Ries, Stefanie Scherzinger, Wolfgang Lehner, Gottfried Vossen |
| Publisher | Gesellschaft fur Informatik (GI) |
| Pages | 283-304 |
| Number of pages | 22 |
| ISBN (electronic) | 9783885797258 |
| Publication status | Published - 2023 |
| Peer-reviewed | Yes |
Publication series
| Series | Lecture Notes in Informatics (LNI), Proceedings - Series of the Gesellschaft fur Informatik (GI) |
|---|---|
| Volume | P-331 |
| ISSN | 1617-5468 |
Symposium
| Title | 20th Conference on Database Systems for Business, Technology and Web |
|---|---|
| Abbreviated title | BTW 2023 |
| Conference number | 20 |
| Duration | 6 - 10 March 2023 |
| Location | Technische Universität Dresden |
| City | Dresden |
| Country | Germany |
External IDs
| ORCID | /0000-0001-8107-2775/work/194824067 |
|---|
Keywords
ASJC Scopus subject areas
Keywords
- generalization, join cardinalities, join order, SPJ queries, upper bound