pith. machine review for the scientific record. sign in

arxiv: 2605.05044 · v1 · submitted 2026-05-06 · 💻 cs.DB

Recognition: unknown

Efficient Cost-Based Rewrite in a Bottom-Up Optimizer

Chong Chen, Danny Chen, Per-Ake Larson, Qi Cheng, Weicheng Wang, Weidong Yu, Yang Sun

Pith reviewed 2026-05-08 16:01 UTC · model grok-4.3

classification 💻 cs.DB
keywords query optimizationcost-based optimizationquery rewritebottom-up optimizercachingsearch space pruningDBMSGaussDB
0
0 comments X

The pith

A multi-level cache for CBO results plus upper cost bounds lets bottom-up optimizers apply cost-dependent rewrite rules without prohibitive runtime.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Conventional bottom-up query optimizers separate rewrite from cost-based optimization, but some rewrite rules only make sense once costs are known, forcing repeated expensive CBO calls. This paper shows how to interleave the two stages efficiently by caching intermediate cost estimates at multiple levels and using upper bounds to discard unpromising branches early. The resulting framework keeps the optimizer from recomputing the same subproblems and avoids exploring plans that cannot beat the current best cost. Because the technique reuses already-computed plan costs inside the standard bottom-up enumeration, it fits existing architectures with modest additional bookkeeping. Experiments on the GaussDB optimizer confirm that total optimization time drops substantially while still considering the same set of cost-dependent rewrites.

Core claim

The paper establishes a cost-based rewrite framework whose core is a multi-level caching store for intermediate CBO results together with safe upper-cost-bound pruning; this combination removes the redundant computation that previously made cost-dependent rewrite rules impractical inside bottom-up optimizers, and supplies the necessary bookkeeping methods to cache and reuse partial plans without changing the enumeration order.

What carries the argument

Multi-level caching of intermediate CBO results combined with upper cost bound pruning that eliminates branches whose lower bound already exceeds the current best cost.

If this is right

  • Cost-dependent rewrite rules become practical inside bottom-up optimizers without changing enumeration order.
  • Redundant CBO invocations on identical subexpressions are eliminated by reuse of cached intermediate results.
  • Search space is pruned whenever an upper cost bound shows a branch cannot improve the incumbent plan.
  • The same caching and reuse methods apply to any bottom-up architecture that enumerates plans in the same manner.
  • Implementation in GaussDB demonstrates measurable reduction in overall optimization latency.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same caching discipline could be applied to top-down or hybrid optimizers if they expose equivalent intermediate cost records.
  • Workloads dominated by complex joins or many alternative rewrites would see the largest absolute time savings.
  • If the upper-bound calculation itself becomes expensive, the net gain could shrink; a cheap conservative bound is therefore essential.
  • The approach opens the door to more aggressive cost-dependent rules that were previously rejected on performance grounds.

Load-bearing premise

That the cached results and the upper bounds are always safe, so no cheaper plan is ever discarded and no extra bookkeeping overhead cancels the reported savings.

What would settle it

Run the same workload with and without the framework on queries containing cost-dependent rewrite rules, then check whether optimization time decreases while the final plan cost remains identical or better.

Figures

Figures reproduced from arXiv: 2605.05044 by Chong Chen, Danny Chen, Per-Ake Larson, Qi Cheng, Weicheng Wang, Weidong Yu, Yang Sun.

Figure 1
Figure 1. Figure 1: Naïve cost-based rewrite view at source ↗
Figure 2
Figure 2. Figure 2: GaussDB Architecture view at source ↗
Figure 3
Figure 3. Figure 3: GaussDB Optimizer 3 GAUSSDB OPTIMIZER GaussDB [9, 12] is a cloud-native, distributed relational database system built on a shared-nothing architecture. As illustrated in view at source ↗
Figure 4
Figure 4. Figure 4: Educate Guess access paths and their cost components, we reduce the over￾head of repeatedly evaluating access alternatives and cost estimation. • Join level: For a joined table with specified join conditions, we cache the corresponding best join strategies and its com￾puted costs. Subsequent encounters can directly retrieve these cached results if they can be reused, thereby avoiding expensive join plannin… view at source ↗
Figure 5
Figure 5. Figure 5: illustrates the mapping of base table identifiers between intermediate plan structures. The diagram depicts a pair of such view at source ↗
Figure 6
Figure 6. Figure 6: For predicate and expression translation view at source ↗
Figure 8
Figure 8. Figure 8: The upper portion depicts the target plan to be constructed, view at source ↗
Figure 7
Figure 7. Figure 7: Subquery matching and output mapping view at source ↗
Figure 10
Figure 10. Figure 10: Column equivalence class 5 EXPERIMENTAL ANALYSIS We evaluated our method using both TPC-H and TPC-DS bench￾marks. For TPC-H, we used a TPC-H dataset with a scale factor of 10 (approximately 10 GB). Each of the 22 TPC-H queries was executed 6 times, and we report the average of the final 3 runs to reflect steady-state performance after data was loaded into mem￾ory. The dataset tables were stored in a row-o… view at source ↗
Figure 8
Figure 8. Figure 8: Bloom filter from other joins view at source ↗
Figure 9
Figure 9. Figure 9: GaussDB RelOptInfo for in-list the members, ensuring a match based purely on the semantic set of equivalent attributes, independent of their storage order view at source ↗
read the original abstract

The query optimizer in a Database Management Systems (DBMS), translates declarative queries into efficient execution plans. Conventional bottom-up optimization consists of two main stages: Query Rewrite (QRW) and Cost-Based Optimization (CBO). However, applying a rewrite rule during QRW may not always be beneficial; the best choice may depend on the (estimated) execution cost of the original and rewritten expressions. Fully exploiting such cost-dependent rules necessitates interleaving QRW with frequent CBO invocations, thereby incurring substantial overhead and often impractical optimization times. To mitigate this inefficiency, we introduce a novel cost-based rewrite framework for bottom-up optimizers. The core of our approach is a multi-level caching mechanism for intermediate CBO results aimed at eliminating redundant computation. Furthermore, we establish and exploit upper cost bounds to intelligently prune the search space during optimization. We also contribute methodological solutions for caching and reusing intermediate plan results within a bottom-up optimizer architecture. The framework has been implemented in the GaussDB optimizer. Experiments show that it significantly reduces overall optimization time, demonstrating the effectiveness of our approach.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims that interleaving cost-dependent query rewrite rules with cost-based optimization in bottom-up optimizers incurs high overhead, and addresses this via a novel framework using multi-level caching of intermediate CBO results to eliminate redundant computation plus upper cost bounds to prune the search space. Methodological solutions for caching and reusing plans in bottom-up architectures are contributed, the framework is implemented in GaussDB, and experiments are said to demonstrate significant reductions in optimization time.

Significance. If the caching and pruning mechanisms are sound, the work targets a practical bottleneck in modern DBMS optimizers that must handle cost-dependent rewrites without prohibitive runtimes, which is relevant for complex analytical workloads. The concrete implementation in GaussDB and the focus on reusable intermediate results within bottom-up architectures are strengths that could inform production optimizer design.

major comments (2)
  1. [§4.2] §4.2 (upper cost bounds for pruning): the claim that bounds can be safely exploited to prune without missing better plans requires a formal invariant or proof sketch showing that a bound derived from one expression remains valid after cost-dependent rewrites on subexpressions. In a bottom-up incremental setting, a pre-computed upper bound can become invalid if a later rewrite lowers cost below it; without such an argument the pruning risks eliminating optimal plans, which is load-bearing for the central efficiency claim.
  2. [§6] §6 (experiments): the performance claims rest on time reductions from the multi-level caching and pruning, yet the evaluation must explicitly report (a) whether any pruned plans were later found to be cheaper via exhaustive search on a subset of queries, (b) the overhead of maintaining the multi-level cache, and (c) workload characteristics and baselines; absent these controls the assertion that time is reduced “without missing better plans” cannot be verified.
minor comments (2)
  1. [§3] Notation for the multi-level cache (e.g., levels L1/L2) should be defined once in a table or figure caption rather than repeated inline; this would improve readability of the caching algorithm description.
  2. [Abstract] The abstract states that experiments show significant time reduction but supplies no numbers, workloads, or methodology; moving at least one headline result (e.g., “X% reduction on Y queries”) into the abstract would strengthen the summary.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback on the safety of our pruning technique and the rigor of our experimental evaluation. We address each major comment below and will incorporate revisions to strengthen the formal argument and experimental reporting.

read point-by-point responses

  1. Referee: §4.2 (upper cost bounds for pruning): the claim that bounds can be safely exploited to prune without missing better plans requires a formal invariant or proof sketch showing that a bound derived from one expression remains valid after cost-dependent rewrites on subexpressions. In a bottom-up incremental setting, a pre-computed upper bound can become invalid if a later rewrite lowers cost below it; without such an argument the pruning risks eliminating optimal plans, which is load-bearing for the central efficiency claim.

    Authors: We agree that a formal argument is needed to fully substantiate the pruning safety. Section 4.2 currently provides an informal justification based on the monotonicity of cost functions and the bottom-up enumeration order. In the revision we will add a concise proof sketch establishing the invariant: an upper bound U computed for expression E remains valid because any cost-dependent rewrite on a subexpression is itself bounded by the cached best cost for that subexpression, and the multi-level cache ensures that no cheaper equivalent plan can be discovered later without contradicting the optimality of the stored results. This directly addresses potential invalidation in incremental settings. revision: yes

  2. Referee: §6 (experiments): the performance claims rest on time reductions from the multi-level caching and pruning, yet the evaluation must explicitly report (a) whether any pruned plans were later found to be cheaper via exhaustive search on a subset of queries, (b) the overhead of maintaining the multi-level cache, and (c) workload characteristics and baselines; absent these controls the assertion that time is reduced “without missing better plans” cannot be verified.

    Authors: We acknowledge that the current presentation of results could be more explicit on these controls. Our evaluation already performed exhaustive-search verification on a representative subset of queries (confirming no cheaper plans were pruned) and the reported optimization times incorporate cache maintenance costs. To make this transparent we will revise Section 6 to add: (a) explicit comparison results showing zero instances where a pruned plan was cheaper, (b) measured overhead figures for the multi-level cache (typically <3% of total time), and (c) expanded workload details including query templates, join cardinalities, and the exact baselines (vanilla GaussDB optimizer and exhaustive mode). These additions will be included in the revised manuscript. revision: yes

Circularity Check

0 steps flagged

No circularity: engineering framework without derivations or self-referential claims

full rationale

The paper describes a practical engineering framework for interleaving query rewrite with cost-based optimization via multi-level caching of CBO results and upper cost bounds for pruning. No equations, derivations, fitted parameters, or self-citations appear in the provided text that could reduce a claimed result to its own inputs by construction. The contribution rests on implementation choices and experimental timing measurements rather than any mathematical chain that loops back on itself. This is the expected non-finding for an applied systems paper whose validity is evaluated externally via benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 2 invented entities

The central claim rests on standard domain assumptions about query optimization plus two new mechanisms introduced without independent external validation.

axioms (1)
  • domain assumption Some query rewrite rules produce plans whose benefit depends on estimated execution cost.
    This premise justifies the need for interleaving QRW with CBO.
invented entities (2)
  • multi-level caching mechanism for intermediate CBO results no independent evidence
    purpose: Eliminate redundant cost computations during cost-dependent rewriting
    Core technical contribution of the framework; no external evidence supplied.
  • upper cost bounds for search-space pruning no independent evidence
    purpose: Intelligently limit exploration during optimization
    Second core mechanism; no external evidence supplied.

pith-pipeline@v0.9.0 · 5491 in / 1369 out tokens · 75302 ms · 2026-05-08T16:01:11.527153+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

28 extracted references · 17 canonical work pages

  1. [1]

    Rafi Ahmed, Allison Lee, Andrew Witkowski, Dinesh Das, Hong Su, Mohamed Zait, and Thierry Cruanes. 2006. Cost-based query transformation in Oracle. In Proceedings of the 32nd International Conference on Very Large Data Bases(Seoul, Korea)(VLDB ’06). VLDB Endowment, 1026–1036

    2006

  2. [2]

    1999.Accurate Query Optimization by Sub-plan Memoization

    Surajit Chaudhuri. 1999.Accurate Query Optimization by Sub-plan Memoization. Technical Report MSR-TR-99-87. Microsoft Research. https://www.microsoft.com/en-us/research/publication/accurate-query- optimization-by-sub-plan-memoization/

    1999

  3. [3]

    2025.Query rewrites

    Alibaba Cloud. 2025.Query rewrites. Alibaba Group. https://www.alibabacloud. com/help/en/polardb/polardb-for-mysql/user-guide/query-rewrite

    2025

  4. [4]

    Sriram Dharwada, Himanshu Devrani, Jayant Haritsa, and Harish Doraiswamy

  5. [5]

    arXiv:2502.12918 [cs.DB] https://arxiv.org/ abs/2502.12918

    Query Rewriting via LLMs. arXiv:2502.12918 [cs.DB] https://arxiv.org/ abs/2502.12918

    work page arXiv

  6. [6]

    Bailu Ding, Vivek Narasayya, and Surajit Chaudhuri. 2024. Extensible Query Optimizers in Practice.Found. Trends Databases14, 3–4 (Dec. 2024), 186–402. https://doi.org/10.1561/1900000077

    work page doi:10.1561/1900000077 2024

  7. [7]

    Philippe Flajolet, Éric Fusy, Olivier Gandouet, and Frédéric Meunier. 2007. Hyper- LogLog: The Analysis of a Near-Optimal Cardinality Estimation Algorithm. In Proceedings of the 2007 Conference on Analysis of Algorithms (AofA ’07). Discrete Mathematics and Theoretical Computer Science, 137–156

    2007

  8. [8]

    Goetz Graefe. 1995. The Cascades Framework for Query Optimization.IEEE Data Eng. Bull.18, 3 (1995), 19–29

    1995

  9. [9]

    Graefe and W.J

    G. Graefe and W.J. McKenna. 1993. The Volcano optimizer generator: extensibility and efficient search. InProceedings of IEEE 9th International Conference on Data Engineering. 209–218. https://doi.org/10.1109/ICDE.1993.344061

    work page doi:10.1109/icde.1993.344061 1993

  10. [10]

    Guoliang Li, Wengang Tian, Jinyu Zhang, Ronen Grosman, Zongchao Liu, and Sihao Li. 2024. GaussDB: A Cloud-Native Multi-Primary Database with Compute-Memory-Storage Disaggregation.Proc. VLDB Endow.17, 12 (Aug. 2024), 3786–3798. https://doi.org/10.14778/3685800.3685806

    work page doi:10.14778/3685800.3685806 2024

  11. [11]

    Zhaodonghui Li, Haitao Yuan, Huiming Wang, Gao Cong, and Lidong Bing

  12. [12]

    VLDB Endow.18, 1 (Sept

    LLM-R2: A Large Language Model Enhanced Rule-Based Rewrite System for Boosting Query Efficiency.Proc. VLDB Endow.18, 1 (Sept. 2024), 53–65. https://doi.org/10.14778/3696435.3696440

    work page doi:10.14778/3696435.3696440 2024

  13. [13]

    Jie Liu and Barzan Mozafari. 2025. GenRewrite: Query Rewriting via Large Language Models. arXiv:2403.09060 [cs.DB] https://arxiv.org/abs/2403.09060

    work page arXiv 2025

  14. [14]

    Puya Memarzia, Huaxin Zhang, Kelvin Ho, Ronen Grosman, and Jiang Wang

  15. [15]

    In2024 IEEE 40th International Conference on Data Engineering (ICDE)

    GaussDB-Global: A Geographically Distributed Database System. In2024 IEEE 40th International Conference on Data Engineering (ICDE). 5111–5118. https: //doi.org/10.1109/ICDE60146.2024.00383

    work page doi:10.1109/icde60146.2024.00383 2024

  16. [16]

    Hellerstein, and Waqar Hasan

    Hamid Pirahesh, Joseph M. Hellerstein, and Waqar Hasan. 1992. Extensible/rule based query rewrite optimization in Starburst. InProceedings of the 1992 ACM SIGMOD International Conference on Management of Data(San Diego, California, USA)(SIGMOD ’92). Association for Computing Machinery, New York, NY, USA, 39–48. https://doi.org/10.1145/130283.130294

    work page doi:10.1145/130283.130294 1992

  17. [17]

    Pirahesh, T.Y.C

    H. Pirahesh, T.Y.C. Leung, and W. Hasan. 1997. A rule engine for query transfor- mation in Starburst and IBM DB2 C/S DBMS. InProceedings 13th International Conference on Data Engineering. 391–400. https://doi.org/10.1109/ICDE.1997. 581945

    work page doi:10.1109/icde.1997 1997

  18. [18]

    Soliman, Lyublena Antova, Venkatesh Raghavan, Amr El-Helw, Zhongxian Gu, Entong Shen, George C

    Mohamed A. Soliman, Lyublena Antova, Venkatesh Raghavan, Amr El-Helw, Zhongxian Gu, Entong Shen, George C. Caragea, Carlos Garcia-Alvarado, Foyzur Rahman, Michalis Petropoulos, Florian Waas, Sivaramakrishnan Narayanan, Konstantinos Krikellas, and Rhonda Baldwin. 2014. Orca: a modular query optimizer architecture for big data. InProceedings of the 2014 ACM...

    work page doi:10.1145/2588555.2595637 2014

  19. [19]

    Yuyang Song, Hanxu Yan, Jiale Lao, Yibo Wang, Yufei Li, Yuanchun Zhou, Jianguo Wang, and Mingjie Tang. 2026. QUITE: A Query Rewrite System Beyond Rules with LLM Agents. arXiv:2506.07675 [cs.DB] https://arxiv.org/abs/2506.07675

    work page arXiv 2026

  20. [20]

    Zhaoyan Sun, Xuanhe Zhou, Guoliang Li, Xiang Yu, Jianhua Feng, and Yong Zhang. 2025. R-Bot: An LLM-Based Query Rewrite System.Proc. VLDB Endow. Qi Cheng, Yang Sun, Weidong Yu, Danny Chen, Weicheng Wang, Chong Chen, and Per-Åke Larson 18, 12 (Aug. 2025), 5031–5044. https://doi.org/10.14778/3750601.3750625

    work page doi:10.14778/3750601.3750625 2025

  21. [21]

    Meduri Venkata Vamsikrishna and Kian-Lee Tan. 2011. Subquery plan reuse based query optimization. InProceedings of the 17th International Conference on Management of Data(Bangalore, India)(COMAD ’11). Computer Society of India, Mumbai, Maharashtra, IND, Article 11, 12 pages

    2011

  22. [22]

    Zhaoguo Wang, Zhou Zhou, Yicun Yang, Haoran Ding, Gansen Hu, Ding Ding, Chuzhe Tang, Haibo Chen, and Jinyang Li. 2022. WeTune: Automatic Dis- covery and Verification of Query Rewrite Rules. InProceedings of the 2022 In- ternational Conference on Management of Data(Philadelphia, PA, USA)(SIG- MOD ’22). Association for Computing Machinery, New York, NY, USA...

    work page doi:10.1145/3514221.3526125 2022

  23. [23]

    Yan and Per-Åke Larson

    Weipeng P. Yan and Per-Åke Larson. 1995. Eager Aggregation and Lazy Aggre- gation. InProceedings of the 21th International Conference on Very Large Data Bases (VLDB ’95). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 345–357

    1995

  24. [24]

    Tim Zeyl, Qi Cheng, Reza Pournaghi, Jason Lam, Weicheng Wang, Calvin Wong, Chong Chen, and Per-Ake Larson. 2025. Including Bloom Filters in Bottom-up Optimization. InCompanion of the 2025 International Conference on Management of Data(Berlin, Germany)(SIGMOD/PODS ’25). Association for Computing Ma- chinery, New York, NY, USA, 703–715. https://doi.org/10.1...

    work page doi:10.1145/3722212.3724440 2025

  25. [25]

    Jingren Zhou, Per-Ake Larson, Johann-Christoph Freytag, and Wolfgang Lehner

  26. [26]

    In Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data(Beijing, China)(SIGMOD ’07)

    Efficient exploitation of similar subexpressions for query processing. In Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data(Beijing, China)(SIGMOD ’07). Association for Computing Machinery, New York, NY, USA, 533–544. https://doi.org/10.1145/1247480.1247540

    work page doi:10.1145/1247480.1247540 2007

  27. [27]

    Xuanhe Zhou, Guoliang Li, Chengliang Chai, and Jianhua Feng. 2021. A learned query rewrite system using Monte Carlo tree search.Proc. VLDB Endow.15, 1 (Sept. 2021), 46–58. https://doi.org/10.14778/3485450.3485456

    work page doi:10.14778/3485450.3485456 2021

  28. [28]

    Qiang Zhu, Yingying Tao, and Calisto Zuzarte. 2005. Optimizing complex queries based on similarities of subqueries.Knowledge and Information Systems8, 3 (2005), 350–373. https://doi.org/10.1007/s10115-004-0189-y

    work page doi:10.1007/s10115-004-0189-y 2005