JOB-Complex : A Challenging Benchmark for Traditional & Learned Query Optimization

Johannes Wehrstein, Timo Eckmann, Roman Heinrich, Carsten Binnig · 2025

Read JOB-Complex : A Challenging Benchmark for Traditional & Learned Query Optimization by Johannes Wehrstein, Timo Eckmann, Roman Heinrich, Carsten Binnig (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-07471.txt.

Introduction

Johannes Wehrstein and three co-authors argue that database query optimizers have been graded on too easy a test, in this 2025 paper. Optimizers pick the execution plan for a query, and their quality decides database speed. The standard JOB benchmark, they say, misses real-world wrinkles, flattering both classic and learned optimizers.

Their new benchmark, JOB-Complex, adds realistic complications: joins over text columns and tangled filter conditions among them. It holds thirty queries plus a plan-selection set of nearly six thousand execution plans for cost-model testing. In their evaluation, traditional and learned cost models both stumbled, sometimes landing on plans eleven times slower than the best available. The authors offer the benchmark as a sterner, fairer yardstick for the field, and as a resource for training the next generation of learned optimizers.

Catalog record

CREATORJohannes Wehrstein, Timo Eckmann, Roman Heinrich, Carsten Binnig
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE37 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-07471

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

JOB-Complex : A Challenging Benchmark for Traditional & Learned Query Optimization Johannes Wehrstein, Timo Eckmann, Roman Heinrich, Carsten Binnig Abstract . Query optimization is a fundamental task in database systems that is crucial to providing high performance. To evaluate learned and traditional optimizer’s performance, several benchmarks, such as the widely used JOB benchmark, are used. However, in this paper, we argue that existing benchmarks are inherently limited, as they do not reflect many real-world properties of query optimization, thus overstating the performance of both traditional and learned optimizers. In fact, simple but realistic properties, such as joins over string columns or complex filter predicates, can drastically reduce the performance of existing query optimizers. Thus, we introduce JOB-Complex , a new benchmark designed to challenge traditional and learned query optimizers by reflecting real-world complexity. Overall, JOB-Complex contains 30 SQL queries and comes together with a plan-selection benchmark containing nearly 6000 execution plans, making it a valuable resource to evaluate the performance of query optimizers and cost models in real-world scenarios. In our evaluation, we show that traditional and learned cost models struggle to achieve high performance on JOB-Complex , providing a runtime of up to 11x slower compared to the optimal plans. LCM Learned Cost Model † † authors: . VLDB Workshop Reference Format: VLDB 2025 Workshop: Applied AI for Database Systems and Applications (AIDB 2025). † † This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing [email protected] . Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment. ISSN 2150-8097. VLDB Workshop Artifact Availability: The source code, data, and/or other artifacts have been made available at https://github.com/DataManagementLab/JOB-Complex . 1. Introduction Figure 1. Query optimization performance for PostgreSQL and a selected learned cost model Zero-Shot ( Hilprecht and Binnig 2022 ) over JOB-Light, JOB and JOB-Complex (ours). Here, we report the sum of the selected plan runtimes, normalized by the optimal runtime (optimization gap). In contrast to existing benchmarks, JOB-Complex poses significant challenges for query optimization by showing an high optimization gap of up to 11.13. The State of Query Optimization . Efficient query optimization is the backbone of providing high-performance database management systems. For a given SQL statement, the query optimizer has to choose optimally among many logical execution plans. This is highly important, as a bad plan may take orders of magnitude longer than the fastest one ( Leis et al. 2015 ; Heinrich et al. 2025 ) . Thus, query optimizers aim to minimize the query runtime, e.g., by enumerating different join orders or selecting between physical join operators. However, query optimization is a highly challenging task, as the number of plan candidates grows quickly with the query complexity. For that reason, query optimizers have been under constant improvement for decades ( Jarke and Koch 1984 ) . While commercial database systems today typically apply static rule-based optimizations and hand-crafted cost models, machine learning approaches have been proposed in recent years to further improve query optimization ( Wu et al. 2024 ; Negi et al. 2021 ) , covering LCM ( Hilprecht and Binnig 2022 ; Liang et al. 2024 ; Rieger and Neumann 2025 ) , learned cardinalities ( Hilprecht et al. 2020 ; Wehrstein et al. [n.d.] ; Yang et al. 2020 ) , learned query hinting ( Marcus et al. 2020 ) , and even end-to-end learned query optimizers ( Marcus et al. 2019 ; Yang et al. 2022 ; Zhu et al. 2023 ) . Is Query Optimization A Solved Problem (in times of AI)? To exercise the performance of query optimizers, many benchmarks were proposed, such as JOB-light ( Kipf et al. 2019 ) , JOB ( Leis et al. 2015 ) and TPC-H ( Transaction Processing Performance Council 2010 ) . Particularly, JOB and JOB-light specifically evaluate the performance of query optimizers and cost models in choosing good join orders (hence the name Join-Order-Benchmark). However, in this paper, we examined classical optimizers like PostgreSQL and learned optimizers such as ZeroShot ( Hilprecht and Binnig 2022 ) and our findings, and find, that these optimizers provide already almost optimal performance on these benchmarks, as shown in Figure 1 . For instance, on JOB-light, PostgreSQL achieves to select plans only 1.18x slower than the optimal plan which we refer to as an optimization gap of 1.18. While JOB is significantly more complex than JOB-light, the overall performance is still remarkably high. Here, PostgreSQL chooses for 50% of the queries a plan that is less than 29% slower than the optimal plan. On the whole benchmark, the optimization gap amounts to only 1.99, as shown in Figure 1 . Similarly, LCM like Zero-Shot ( Hilprecht and Binnig 2022 ) achieve a similar quality of plan selection with optimization gaps of 1.12 for JOB-light and 2.39 for JOB. Hence, we want to raise the question in this paper: Do we need to further invest in query optimization and learned models, or is query optimization an already solved problem in times of AI? Benchmark Number of Queries Number of Joins String Filters Join on Non-PK/FK columns Join on String Columns Runtime of Optimal Plans (s) Runtime of PG selected Plans (s) Optimization Potential JOB-light ( Kipf et al. 2019 ) 70 1-3 – – – 2359.72 2795.53 1.18 JOB ( Leis et al. 2015 ) 113 3-14 ✓ – – 156.79 312.23 1.99 JOB-Complex (ours) 30 5-14 ✓ ✓ ✓ 53.34 593.50 11.13 Table 1. Key characteristics of existing benchmarks. JOB-Complex comes with real-world query properties that pose a significant challenge for query optimizers, as reflected in a very high runtime of selected plans by PostgreSQL, that is 11.13x slower than the optimal plans. The runtimes are aggregated over all queries in each benchmark. The Need For A New Benchmark. While these standard benchmarks have been a valuable tool for evaluating query optimizers, our experience with them revealed that they lack many complex real-world challenges. As a result, these benchmarks (while valuable) do not effectively stress query optimizers or expose their limitations. For instance, TPC-H uses synthetic data lacking real-world correlations and complex data distributions, often leading to overly accurate cardinality estimates, as recently discussed ( van Renen et al. 2024 ) . JOB & JOB-light were proposed to address this using the IMDB movie dataset, a real-world dataset with complex correlations. While these benchmarks capture varying levels of query complexity, they, however, still largely operate under simplifying assumptions, such that data exists in a normalized schema or that primary/foreign key (PK/FK) constraints are rigidly enforced. However, the scenarios faced by modern database systems often extend far beyond these assumptions ( van Renen et al. 2024 ; Ding et al. 2021 ; Dreseler et al. 2020 ; Leis et al. 2018 ; Negi et al. 2023 ) . For instance, users frequently join on non-key columns ( Ding et al. 2021 ) , use string-based join conditions, or employ complex filter predicates involving LIKE or IN clauses with many values ( Ding et al. 2021 ; Leis et al. 2018 ; Dreseler et al.

Read the complete text