REVIEW 3 major objections 4 minor 2 cited by
JOB-Complex: A Challenging Benchmark for Traditional & Learned Query Optimization
T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read The paper claims that realistic query features missing from standard benchmarks—string joins, non-key joins, same-table comparisons, and complex predicates—make PostgreSQL and learned cost models select plans up to 11x slower than the…
desk verdict JOB-Complex is a useful benchmark resource, but the 11x/8x optimization gaps rest on measurement and enumeration choices that need tightening before the numbers are taken at face value. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the JOB-Complex benchmark itself plus its plan-selection dataset. JOB-Complex consists of 30 hand-crafted Select-Project-Aggregate-Join queries with 5–14 joins, derived from JOB queries by transforming key joins into string or non-key joins, adding same-table comparisons, and adding LIKE/IN predicates, while deliberately preserving each query's read-set so the underlying IMDB correlations carry over. The companion mechanism is the steered plan enumeration: one oracle-guided pass injects true intermediate cardinalities into PostgreSQL via a query hinting engine to find near-optimal plans, and a diversified random pass enforces only global join orders over tables with more than 10,000 rows, with a 30-second timeout per sub-plan, letting PostgreSQL fill in local nesting and operators. The optimization gap metric—selected plan runtime divided by enumerated optimal runtime—is what carries the evaluation across traditional and learned cost models.
What would settle it
For a subset of JOB-Complex queries, re-run the plan enumeration without the 30-second per-sub-plan timeout and without omitting small tables from the global join order, or use an independent exhaustive search with true cardinalities; if any query yields a plan that is materially faster than the released 'optimal' plan, the optimization gap is at least partly an artifact of the enumeration.
Extended reading notes
Core claim
On the paper's own terms, the discovery is that a benchmark built from JOB by adding four realistic properties—joins on string columns, joins on non-primary/foreign-key columns, comparisons between columns of the same table, and complex filter predicates—dramatically increases the optimization gap, defined as the runtime of the optimizer-selected plan divided by the runtime of the best plan in the enumerated set. The paper reports an optimization gap of 11.13 for PostgreSQL on JOB-Complex, versus 1.99 on JOB and 1.18 on JOB-Light, and a gap of 9.68 for the learned ZeroShot model, with the best learned cost models still around 8x. It also reports that median cardinality Q-errors on JOB-Complex are in a similar range to JOB, which the authors read as evidence that the bottleneck is not solely cardinality estimation but the cost models' ability to generalize to more complex query patterns. The companion claim is that the released plan-selection dataset, roughly 200 executed plans per query, makes this difficulty reproducible for cost-model evaluation and training.
Load-bearing premise
The reported gaps depend on the enumerated 'optimal' plans actually being the fastest available, but the enumeration is steered and constrained by a 30-second timeout per sub-plan and by omitting tables with fewer than 10,000 rows from the global join order.
Editorial extensions
If this is right
- On JOB-Complex, PostgreSQL's optimization gap is 11.13x and the best learned models such as T3 and FlatVector still sit around 8x, so near-optimal plan selection is not achieved by either paradigm on these queries.
- Because cardinality Q-errors on JOB-Complex are comparable to those on JOB, the large gaps suggest that cost models fail to translate reasonable cardinality estimates into good plan choices.
- The released plan-selection benchmark, with roughly 200 plans per query spanning a broad runtime distribution, gives learned cost models a ready-made training and evaluation set.
- Since JOB-Complex queries mirror JOB in the number of tables and filters, any difference in optimizer performance can be attributed to the added real-world properties rather than to query size.
- All JOB-Complex queries return non-empty results, which removes shortcuts optimizers could otherwise exploit through empty intermediate results.
Reading between the lines
- If the benchmark is correct, feeding PostgreSQL perfect cardinalities should close only part of the gap; a clean test is to compare PostgreSQL's plan choice when oracle cardinalities are injected against its default choice on the same queries.
- The transformation recipe—swap key joins for string or non-key joins, add same-table comparisons, and add complex LIKE/IN predicates—could be applied to other benchmarks such as TPC-H to generate hard queries systematically.
- The reported gaps are relative to the best plans the enumeration found, not to provably optimal plans; independently discovered better plans would change the measured gaps, so the benchmark numbers should be read with the enumeration constraints in mind.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces JOB-Complex, a 30-query benchmark derived from JOB by adding joins on non-key and string columns, same-table column comparisons, and complex filter predicates, together with a plan-selection dataset of roughly 6000 pre-executed plans. The authors evaluate PostgreSQL and nine learned cost models on JOB-Complex and report optimization gaps (selected-plan runtime divided by best-known-plan runtime) of up to 11.13x for PostgreSQL and roughly 8-9.7x for the best learned models, compared with roughly 2x on JOB. The paper argues that existing benchmarks overstate optimizer quality and that realistic query features break both traditional and learned optimizers.
Significance. If the reported numbers hold, this is a useful and timely result: it provides a concrete benchmark that stresses optimizers beyond PK/FK integer joins, and it ships a reusable plan-enumeration dataset that can support future cost-model research. The evaluation includes many third-party learned models and uses the established IMDB/JOB data, which reduces concerns about self-dealing. The central contribution—a benchmark with realistic optimizer-breaking features and a plan corpus—has clear value to the query-optimization community. However, the headline optimization gaps rest on a definition of 'optimal' that is not actually proven, and on runtime measurements that are not described with enough detail to rule out measurement bias.
major comments (3)
- [§2.2] The paper repeatedly calls the denominator of its headline ratio the 'optimal plan,' but Section 2.2 describes a steered enumeration with a 30-second timeout per sub-plan/join-pair and a heuristic that omits tables with fewer than 10,000 rows from the global join order. This procedure can only produce a best-found plan, not a proven optimum. Since Table 1 and Figures 1 and 3 compute optimization gaps as selected-runtime over this best-found runtime, the 11.13x and 9.68x numbers are not guaranteed to be properties of the queries; they may be artifacts of the enumeration budget or the table-size cutoff. The authors should either report the enumeration coverage (e.g., exhaustive enumeration for the smaller queries, number of join orders explored, and time spent), prove a lower bound on the optimal plan cost, or consistently relabel the denominator as 'best-known plan' rather than 'optimal plan.'
- [§3 (Experimental Setup)] The experimental section reports no repetitions, no cache-clearing procedure, no confidence intervals, and no details about whether plans were measured warm or cold, despite running on shared CloudLab instances. Because the paper's central quantitative claims are ratios of measured runtimes, an asymmetry—for example, enumerated plans executed warm while PostgreSQL-selected plans are executed cold—could substantially inflate the reported 11x gap. The authors should specify the physical run protocol, report per-query runtime distributions over multiple runs, clear OS and database caches between measured executions, and provide error bars or at least medians for all runtime-based figures and tables.
- [§2.1] The 30 queries are hand-picked from JOB and modified by hand, but the paper gives no explicit selection criteria or evidence that the chosen queries are representative of 'real-world' workloads rather than adversarially constructed to make optimizers look bad. Figure 2 and Table 1 show query-size distributions, but these do not establish that the added string/non-key joins and complex predicates mirror realistic workloads. Since the benchmark's validity as a general evaluation tool depends on this representativeness, the authors should document the query-selection and modification protocol, release the original-to-modified query mapping, and show that the hard cases are not isolated outliers.
minor comments (4)
- [§3.4] The conclusion that cardinality estimates on JOB-Complex are 'not drastically worse than on JOB' is based on median Q-error at the root operator; per-query distributions and percentiles should be reported, because medians can hide the long tail of bad estimates that matter most for plan selection.
- [§2.2] The paper says the plan set contains 'nearly 6000 execution plans' and 'on average around 200 enumerated plans per SQL query'; with 30 queries this is consistent, but the exact total and per-query counts should be stated in a table or appendix for reproducibility.
- [§1 and Abstract] There are small language issues, such as 'an high optimization gap' in the Introduction, and the footnote in Section 1 gives the artifact URL as https://github.com/DataManagementLab/JOB-Extended while the abstract and artifact-availability statement give https://github.com/DataManagementLab/JOB-Complex; these URLs should be reconciled.
- [References] Reference [23] is listed as '[n.d.]' with no publication venue; this should be completed before publication.
Circularity Check
No significant circularity: the 11.13x optimization gap is a measured runtime ratio against a disclosed, standard enumeration-based 'optimal'; the paper's self-citations are methodological rather than load-bearing.
full rationale
The paper's central quantitative claim—PostgreSQL and learned cost models show optimization gaps up to 11.13x on JOB-Complex—is an empirical runtime measurement, not a quantity forced by the benchmark's construction. The gap is selected-plan runtime divided by the best plan found in the authors' own enumeration, and the paper discloses this qualifier: 'the runtime of the optimal plan (from our enumerated set)' (Section 3.1). This denominator is self-built (oracle-guided true-cardinality plans plus diversified random enumeration, Section 2.2), but the enumeration methodology is the established JOB approach of Leis et al. [11], which the paper cites, and the identical procedure is applied to JOB and JOB-Light, the baselines against which JOB-Complex's relative difficulty is claimed. If the enumeration misses a faster true optimum, the reported gap is a lower bound, so any bias is conservative; the disclosed omission of small tables from the global join order (Section 2.2) likewise only risks understating the gap. The learned-model results (ZeroShot, T3, DACE, FlatVector, etc.) come from third parties or are measured in this paper; the one methodological self-citation ('we follow those described in [6]', Section 3) sets the training protocol but is not load-bearing for the core 11.13x PostgreSQL figure, which involves no learned model and no fitted parameter renamed as a prediction. No uniqueness theorem is imported from the authors, no ansatz is smuggled in via citation, and no known result is repackaged under new coordinates. The abstract's unqualified word 'optimal' overstates the body's careful 'from our enumerated set', but that is a disclosed labeling choice, not a hidden equivalence. Measurement concerns (no repetitions, no cache control on shared CloudLab nodes) are experimental-rigor risks that bear on the accuracy of the 11.13x ratio, not on whether the derivation reduces to its inputs. Under the evidentiary standard requiring an exhibited equation-level reduction, no circular step is present.
Assumptions & free parameters
free parameters (3)
- Sub-plan timeout =
30 seconds
- Table size threshold =
10,000 rows
- Number of enumerated plans per query =
~200 on average
assumptions (5)
- domain assumption IMDB dataset is representative of real-world analytical workloads
- domain assumption The steered plan enumeration yields a plan set that includes the true optimal plan for each query
- domain assumption PostgreSQL v16 and the selected nine learned cost models are representative of traditional and learned optimizers
- domain assumption Runtimes are stable and deterministic across executions
- domain assumption Current benchmarks (JOB, JOB-light, TPC-H) indeed overstate optimizer performance because they lack string/non-key joins and complex predicates
invented entities (1)
-
JOB-Complex benchmark
independent evidence
Cite this review
Pith. "Pith review of JOB-Complex: A Challenging Benchmark for Traditional & Learned Query Optimization." pith.science (2026). https://pith.science/paper/OC2QQ3GX
@misc{pith2026250707471,
author = {Pith},
title = {Pith review of: JOB-Complex: A Challenging Benchmark for Traditional & Learned Query Optimization},
year = {2026},
howpublished = {\url{https://pith.science/paper/OC2QQ3GX}},
note = {Machine review of arXiv:2507.07471}
}
read the original 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.
Figures
Forward citations
Cited by 2 Pith papers
-
Hollywood: Towards a Large Movie Dataset for Database Benchmarking
Hollywood is a synthetic IMDb-compatible benchmark generator whose 200K-movie instance induces cardinality-estimation errors comparable to or exceeding the original JOB/IMDb workload, enabling generalization testing b...
-
Redbench: Workload Synthesis From Cloud Traces
Redbench synthesizes cloud-shaped SQL workloads from traces and shows that result caching speedups of 1.1–2.98× appear on these workloads while standard JOB/CEB-style baselines show none.
Reference graph
Works this paper leans on
-
[1]
Bailu Ding, Surajit Chaudhuri, Johannes Gehrke, and Vivek Narasayya. 2021. DSB: A decision support benchmark for workload-driven and traditional database systems. Proceedings of the VLDB Endowment 14, 13 (2021), 3376–3388
work page 2021
-
[2]
Markus Dreseler, Martin Boissier, Tilmann Rabl, and Matthias Uflacker. 2020. Quantifying TPC-H choke points and their optimizations. Proceedings of the VLDB Endowment 13, 8 (2020), 1206–1220
work page 2020
-
[3]
Dmitry Duplyakin, Robert Ricci, Aleksander Maricq, Gary Wong, Jonathon Duerig, Eric Eide, Leigh Stoller, Mike Hibler, David Johnson, Kirk Webb, Aditya Akella, Kuang-Ching Wang, Glenn Ricart, Larry Landweber, Chip Elliott, Michael Zink, Emmanuel Cecchet, Snigdhaswin Kar, and Prabodh Mishra. 2019. The Design and Operation of CloudLab. In Proceedings of the ...
work page 2019
-
[4]
Archana Ganapathi, Harumi A. Kuno, Umeshwar Dayal, Janet L. Wiener, Ar- mando Fox, Michael I. Jordan, and David A. Patterson. 2009. Predicting Multiple Metrics for Queries: Better Decisions Enabled by Machine Learn- ing. In Proceedings of the 25th International Conference on Data Engineering, ICDE 2009, March 29 2009 - April 2 2009, Shanghai, China , Yann...
-
[5]
Naruhiko Hayashi and contributors. 2025. pg_hint_plan: PostgreSQL hinting engine. https://github.com/ossc-db/pg_hint_plan. Accessed: 2025-06-10
work page 2025
-
[6]
Roman Heinrich, Manisha Luthra, Johannes Wehrstein, Harald Kornmayer, and Carsten Binnig. 2025. How Good are Learned Cost Models, Really? Insights from Query Optimization Tasks. Proc. ACM Manag. Data 3, 3, Article 172 (June 2025), 27 pages. https://doi.org/10.1145/3725309
doi:10.1145/3725309 2025
-
[7]
Benjamin Hilprecht and Carsten Binnig. 2022. Zero-Shot Cost Models for Out- of-the-box Learned Cost Prediction. Proc. VLDB Endow. 15, 11 (2022), 2361–2374. https://doi.org/10.14778/3551793.3551799
arXiv 2022
- [8]
Show all 27 references
-
[9]
Matthias Jarke and Jürgen Koch. 1984. Query Optimization in Database Systems. ACM Comput. Surv. 16, 2 (1984), 111–152. https://doi.org/10.1145/356924.356928
1984
-
[10]
Boncz, and Al- fons Kemper
Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter A. Boncz, and Al- fons Kemper. 2019. Learned Cardinalities: Estimating Correlated Joins with Deep Learning. In 9th Biennial Conference on Innovative Data Systems Research, CIDR 2019, Asilomar, CA, USA, January 13-16...
2019
-
[11]
Boncz, Alfons Kemper, and Thomas Neumann
Viktor Leis, Andrey Gubichev, Atanas Mirchev, Peter A. Boncz, Alfons Kemper, and Thomas Neumann. 2015. How Good Are Query Optimizers, Really? Proc. VLDB Endow. 9, 3 (2015), 204–215. https://doi.org/10.14778/2850583.2850594
2015
-
[12]
Viktor Leis, Bernhard Radke, Andrey Gubichev, Atanas Mirchev, Peter Boncz, Alfons Kemper, and Thomas Neumann. 2018. Query optimization through the looking glass, and what we found running the join order benchmark. The VLDB Journal 27 (2018), 643–668
2018
-
[13]
Zibo Liang, Xu Chen, Yuyang Xia, Runfan Ye, Haitian Chen, Jiandong Xie, and Kai Zheng. 2024. DACE: A Database-Agnostic Cost Estimator. In 40th IEEE International Conference on Data Engineering, ICDE 2024, Utrecht, The Netherlands, May 13-16, 2024. IEEE, 4925–4937. https://doi....
2024
-
[14]
Ryan Marcus, Parimarjan Negi, Hongzi Mao, Nesime Tatbul, Mohammad Al- izadeh, and Tim Kraska. 2020. Bao: Learning to Steer Query Optimizers. CoRR abs/2004.03814 (2020). arXiv:2004.03814 https://arxiv.org/abs/2004.03814
2020 arXiv
-
[16]
Ryan Marcus and Olga Papaemmanouil. 2019. Plan-Structured Deep Neural Network Models for Query Performance Prediction. Proc. VLDB Endow. 12, 11 (2019), 1733–1746. https://doi.org/10.14778/3342263.3342646 7
2019
-
[17]
Parimarjan Negi, Laurent Bindschaedler, Mohammad Alizadeh, Tim Kraska, Jyoti Leeka, Anja Gruenheid, and Matteo Interlandi. 2023. Unshackling data- base benchmarking from synthetic workloads. In 2023 IEEE 39th International Conference on Data Engineering (ICDE) . IEEE, 3659–3662
2023
-
[18]
Friedman, and Alekh Jindal
Parimarjan Negi, Matteo Interlandi, Ryan Marcus, Mohammad Alizadeh, Tim Kraska, Marc T. Friedman, and Alekh Jindal. 2021. Steering Query Optimizers: A Practical Take on Big Data Workloads. In SIGMOD ’21: International Conference on Management of Data, Virtual Event, China, Jun...
2021
-
[19]
Maximilian Rieger and Thomas Neumann. 2025. T3: Accurate and Fast Per- formance Prediction for Relational Database Systems With Compiled Decision Trees. Proceedings of the ACM on Management of Data 3, 3 (2025), 1–27
2025
-
[20]
Ji Sun and Guoliang Li. 2019. An End-to-End Learning-based Cost Estimator.Proc. VLDB Endow. 13, 3 (2019), 307–319. https://doi.org/10.14778/3368289.3368296
2019
-
[21]
Transaction Processing Performance Council. 2010. TPC Benchmark H (Decision Support). http://www.tpc.org/tpch/. Standard Specification, Revision 2.17.1
2010
-
[22]
Alexander van Renen, Dominik Horn, Pascal Pfeil, Kapil Vaidya, Wenjian Dong, Murali Narayanaswamy, Zhengchun Liu, Gaurav Saxena, Andreas Kipf, and Tim Kraska. 2024. Why TPC Is Not Enough: An Analysis of the Amazon Redshift Fleet. Proc. VLDB Endow. 17, 11 (2024), 3694–3706. htt...
2024
-
[23]
Johannes Wehrstein, Carsten Binnig, Fatma Özcan, Shobha Vasudevan, Yu Gan, and Yawen Wang. [n.d.]. Towards Foundation Database Models. ([n. d.])
-
[24]
Ziniu Wu, Ryan Marcus, Zhengchun Liu, Parimarjan Negi, Vikram Nathan, Pascal Pfeil, Gaurav Saxena, Mohammad Rahman, Balakrishnan Narayanaswamy, and Tim Kraska. 2024. Stage: Query Execution Time Prediction in Amazon Redshift. In Companion of the 2024 International Conference on...
2024
-
[25]
Zongheng Yang, Wei-Lin Chiang, Sifei Luan, Gautam Mittal, Michael Luo, and Ion Stoica. 2022. Balsa: Learning a Query Optimizer Without Expert Demonstrations. In SIGMOD ’22: International Conference on Management of Data, Philadelphia, PA, USA, June 12 - 17, 2022 , Zachary G. I...
2022
-
[26]
Zongheng Yang, Amog Kamsetty, Sifei Luan, Eric Liang, Yan Duan, Xi Chen, and Ion Stoica. 2020. NeuroCard: One Cardinality Estimator for All Tables. Proc. VLDB Endow. 14, 1 (2020), 61–73. https://doi.org/10.14778/3421424.3421432
2020
-
[27]
Yue Zhao, Gao Cong, Jiachen Shi, and Chunyan Miao. 2022. QueryFormer: A Tree Transformer Model for Query Plan Representation. Proc. VLDB Endow. 15, 8 (2022), 1658–1670. https://doi.org/10.14778/3529337.3529349
2022
-
[28]
Rong Zhu, Wei Chen, Bolin Ding, Xingguang Chen, Andreas Pfadler, Ziniu Wu, and Jingren Zhou. 2023. Lero: A Learning-to-Rank Query Optimizer. Proc. VLDB Endow. 16, 6 (2023), 1466–1479. https://doi.org/10.14778/3583140.3583160 8
2023
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.