Pith. sign in

REVIEW 3 major objections 6 minor 70 references

Conformal Prediction for Verifiable Learned Query Optimization

T0 review · 3 major / 6 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper claims that conformal prediction can give learned query optimizers statistically guaranteed bounds on actual query latency before execution, and can detect or guide around slow plans during construction.

desk verdict Applies conformal prediction to learned query optimizers with real experiments, but the per-plan coverage guarantee rests on an exchangeability assumption the paper never tests, and the conclusion overstates a planning-time win as a latency win. read the letter →

arxiv 2505.02284 v1 pith:YO7FA3LM submitted 2025-05-04 cs.DB

Hanwen Liu , Shashank Giridhara , Ibrahim Sabek This is my paper · ORCID
classification cs.DB
keywords conformalpredictionlearnedqueryoptimizationruntimeverificationlatencyboundsdistributionshiftadaptiveplansearchsignaltemporallogic
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper sets out to make learned query optimizers verifiable rather than taken on faith. It defines a latency-cost non-conformity score as the absolute difference between a plan's predicted cost and its actual latency, and applies conformal prediction so that, with a user-chosen probability 1-delta, a test plan's latency falls inside the interval predicted cost plus or minus an upper bound C. For white-box optimizers that build plans step by step, the same conformal construction is applied to the robustness of a temporal constraint, yielding an early check that flags a violating plan before it is completed. An adaptive version adjusts C when the workload shifts, and a CP-guided search uses the latency upper bound to steer plan construction. If the guarantees hold, users can specify confidence levels for latency constraints and detect or avoid slow plans without executing them.

What carries the argument

The load-bearing object is the latency-cost non-conformity score R := |t - c_hat|, whose empirical quantile over a calibration workload becomes the upper bound C. Around it are the STL robustness measure rho_phi, used to express latency constraints and to compare the current partial plan estimate with the final complete plan, and the adaptive adjustment of the uncertainty probability through the distribution-shift correction of Equation 5. The CP upper bound is the mechanism that converts predicted costs into pre-execution latency intervals, and the comparison rho_phi(x_hat) > C is the mechanism that converts partial-plan prefixes into early violation signals.

What would settle it

Run a white-box LQO on a fixed workload, compute C from a calibration set, and measure on held-out queries whether at least 1-delta of actual latencies fall within predicted cost plus or minus C; coverage persistently below 1-delta, or a rank test rejecting exchangeability of the partial-plan scores, would falsify the central claim.

Watch

Extended reading notes

Core claim

The central discovery is that verification of learned query optimizers can be formulated as a conformal prediction problem. For each plan define R := |t - c_hat|; taking C as the (1-delta)th quantile of the calibration scores yields the marginal guarantee P(c_hat - C <= t <= c_hat + C) >= 1 - delta, so the actual latency of an unseen plan has a bounded range before execution. For white-box LQOs that construct plans operator by operator, the paper verifies STL constraints on robustness values: with non-conformity score rho_phi(x_hat) - rho_phi(x), the condition rho_phi(x_hat) > C implies P(X satisfies phi) >= 1 - delta. The framework also adapts C under distribution shift and uses the upper bound c_hat + C as a heuristic in beam search, reporting plan quality improvements up to 9.84x and planning time reductions up to 74.4% for a single query.

Load-bearing premise

The guarantees rest on the assumption that latency-cost error scores from calibration plans and test plans are exchangeable draws from one distribution; if sequentially generated partial plans within a query are correlated, or the workload shifts beyond the estimated amount, the stated 1-delta coverage is not assured.

Editorial extensions

If this is right

  • Users can set a confidence level and receive pre-execution latency bounds for LQO-generated plans, making plan behavior auditable before spending execution time.
  • White-box LQOs can be stopped mid-construction when the current partial plan suggests a constraint violation, and the query can be re-planned by a traditional optimizer.
  • When workloads drift, adaptive CP preserves the nominal 1-delta coverage by inflating the bound according to an estimated distribution shift.
  • CP-guided plan search improves both plan quality and planning time, especially for moderately trained LQOs, and can restructure plans, for example from left-deep to bushy trees.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial extension: a natural next step is to apply the same conformal verification to other learned database components, such as cardinality estimators or cost models, wherever a measurable error between prediction and observation exists.
  • Editorial extension: the exchangeability assumption is most fragile for sequential partial plans within one query; if intra-query correlation is strong, block-wise or adaptive conformal schemes may be needed to preserve the stated coverage.
  • Editorial extension: the CP-guided search could double as a planning-time budget mechanism, pruning partial plans whose optimistic latency upper bound already exceeds the user's constraint.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. This paper proposes a conformal prediction (CP) framework for learned query optimizers (LQOs). It defines a latency-cost non-conformity score, derives bounded latency ranges for partial and complete plans, extends the method to adaptive CP for distribution shift, and introduces an STL-based runtime verification module with a fallback to a traditional optimizer. It also proposes a CP-guided plan search algorithm. The evaluation covers three LQOs (Balsa, Lero, RTOS) and four workloads (JOB, TPC-H, CEB, JOBLight-train), reporting empirical coverage, violation detection and handling, plan quality, and planning time.

Significance. Conditional on the formal guarantees being valid, the paper addresses a genuine gap: LQOs are opaque and can produce tail-latency disasters, and existing robustness-oriented work such as Kepler and Roq does not provide per-plan formal latency guarantees. The paper's strengths include a clean problem formulation, the use of external adaptive-CP and STL machinery, an explicit lower bound on the calibration set size in Lemma 1, and a broad empirical study across multiple LQOs and workloads. The proposed framework could be a useful building block for production LQO deployment if the exchangeability assumption and the runtime-verification semantics are made sound.

major comments (3)
  1. [Sec. 3.3 and Eq. (2)-(4)] The central finite-sample guarantee in Eq. (4) requires the test non-conformity score to be exchangeable with the calibration scores. The framework pools scores from all partial and complete plans in the calibration workload and then applies the resulting bound to every operator or pattern of test queries. However, partial plans within one query are generated sequentially by the same LQO and their residual distributions are likely to change with construction step, so the pooled score vector is not obviously exchangeable; the i.i.d. assertion in Section 2.2 is an assumption, not a demonstrated property. Consequently, Eq. (4) is not a validated per-step or per-plan guarantee as stated. The paper should either treat each query as a single calibration unit, use a blockwise conformal construction that accounts for intra-query dependence, or provide empirical evidence such as an exchangeability test and per-step coverage breakdowns.
  2. [Sec. 4 and Lemma 2] Lemma 2 is worded as an 'only if' condition, but the proof establishes only sufficiency: if rho_phi(x_hat) > C, then P(X satisfies phi) >= 1 - delta. The sentence 'Otherwise, the resulting complete plan will cause a violation' is not a logical consequence; failure of the condition merely means the method cannot certify the plan, and the fallback may fire on plans that would have satisfied the constraint. In addition, Eq. (7) constructs x_hat using only the observed prefix and the next predicted step, whereas the STL specification G[0,N-1] phi in Section 2.3 requires all N steps; the paper does not define robust semantics for truncated signals or justify that rho_phi(x_hat) computed on this prefix upper-bounds or reflects the robustness of the full plan. The runtime verification claim needs a precise statement of what exactly is verified at each step.
  3. [Abstract, Sec. 6.6.2, and Sec. 8] The reported 9.96% improvement across all test queries is a planning-time reduction in Section 6.6.2, and the 74.4% figure is also a planning-time improvement for a single query. The Abstract states this correctly as planning time, but the Conclusion says 'CP-guided LQOs show a 9.96% reduction in actual latency', which is not supported by the experiments. The execution-latency improvement is reported per query (up to 9.84x for Query 27b), not as an aggregate 9.96% reduction. The Abstract and Conclusion should be aligned so that each number is attributed to the metric actually measured.
minor comments (6)
  1. [Sec. 2.2] The text says the scores R(0),...,R(K) are i.i.d., but the proofs and the standard conformal argument only require exchangeability; please align the terminology throughout.
  2. [Sec. 3.1, Lemma 1] The expression '1−δ/δ' in the lemma statement is ambiguous; it should be written as '(1−δ)/δ'.
  3. [Sec. 6.1] The normalization constants f(c)=c/40 for Lero and f(c)=c/100 for RTOS are introduced without justification or sensitivity analysis; since these constants rescale the non-conformity scores and directly affect the tightness of C, a brief rationale or robustness check is needed.
  4. [Fig. 6] The legend labels for the least-popular patterns appear as garbled characters and should be fixed.
  5. [Artifact availability] The artifact URL is the placeholder 'URL_TO_YOUR_ARTIFACTS'; the actual artifact link must be provided for the artifact availability claim.
  6. [Sec. 6.4] The runtime verification validation uses 30 test queries and reports counts such as 27/30 and 28/30; this sample is too small to confirm a 90% coverage guarantee, and the paper should report confidence intervals or a larger evaluation.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central CP bounds and runtime-verification condition are standard split-conformal results with external support, and the plan-search heuristic is empirically evaluated rather than derived from its own outputs.

full rationale

The paper's derivation chain is self-contained and non-circular at every load-bearing step. The non-conformity score in Eq. 2, R(i) = |t - c_hat|, defines a residual between predicted cost and actual latency; C is then computed as the (1-delta) quantile of calibration residuals (Algorithm 1), which is the standard split-conformal construction. Equation 4 is merely the algebraic rearrangement of Eq. 3 and does not define the predicted latency in terms of the calibration data; it states a coverage property for the interval c_hat +/- C. Lemma 1 is the standard rank-based coverage argument for exchangeable scores, and Lemma 2 is explicitly imported from external STL-conformal prediction work (references [12,29]), not from the authors' own prior results. The adaptive CP construction in Section 3.2 is likewise based on external results ([37,64]) with an explicit epsilon >= TV(D,D0) condition, and the paper states this assumption rather than smuggling it in. The CP-guided search in Section 5 uses U = c_hat + C as a heuristic and then reports empirical plan quality; this is an experimental application, not a prediction derived from its own fitted values. The only noteworthy weakness is the exchangeability assumption for pooled per-step non-conformity scores (Section 2.2 and the evaluation's per-operator coverage calculation). If intra-query step scores are not exchangeable, the 1-delta guarantee would not hold; however, this is a correctness/validity risk, not a circularity. The paper explicitly acknowledges the exchangeability assumption and even extends to adaptive CP for distribution shift. No load-bearing self-citations or fitted parameters renamed as predictions were found, so the appropriate finding is no significant circularity.

Assumptions & free parameters 4 free parameters · 4 assumptions · 0 invented entities

The central claim depends on exchangeability of non-conformity scores, the assumption that predicted cost is a meaningful proxy for latency, and the reliability of the TV-distance estimates used to set epsilon. Two numeric constants for Lero and RTOS cost normalizations are fitted to align scales, and two epsilon values are set from empirical estimates; these are the main free parameters. No new entities are postulated.

free parameters (4)
  • Lero cost normalization constant = 1/40
    Section 6.1: predicted costs in Lero are normalized as f(c)=c/40 to align with actual latencies. The constant is chosen by hand and affects all non-conformity scores and the resulting CP bound.
  • RTOS cost normalization constant = 1/100
    Section 6.1: predicted costs in RTOS are normalized as f(c)=c/100. This is a fitted scaling factor with the same effect as the Lero constant.
  • Distribution shift allowance epsilon for JOB to CEB = 0.08
    Section 6.3: epsilon is set to 0.08 after empirically estimating the TV distance as 0.0736 from 500 sampled plans. The estimate is data-dependent and not accompanied by uncertainty bounds.
  • Distribution shift allowance epsilon for JOB to JOBLight = 0.25
    Section 6.3: epsilon is set to 0.25 after estimating the TV distance as 0.24916. Again the estimate is empirical and data-dependent.
assumptions (4)
  • domain assumption Exchangeability of non-conformity scores across calibration and testing plans
    Section 2.2 states that training, calibration, and testing data originate from the same distribution so that R(0), R(1), ..., R(K) are exchangeable. All CP guarantees in Sections 3 and 4 depend on this. The paper does not address dependence among scores from partial plans of the same query.
  • domain assumption Predicted cost is indicative of actual latency
    Section 2.1 footnote: 'we assume that the cost of a plan is indicative of its actual latency, where a higher cost corresponds to longer latency.' This monotonicity is needed for the bounded latency range and for the CP-guided search to be meaningful.
  • domain assumption The distribution shift can be quantified by total variation distance and reliably estimated via KDE
    Section 3.2 uses TV(D,D0) estimated by kernel density estimators to set epsilon. The adaptive CP guarantee requires epsilon to be at least the true TV, but the estimate is a random quantity with no reported confidence interval.
  • domain assumption STL robust semantics with a linear predicate correctly captures the latency constraint
    Section 2.3 and Section 6.4 define rho_phi(x) = threshold - x for the always operator. The runtime verification results depend on this particular robust semantics being a faithful representation of the performance constraint.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Conformal Prediction for Verifiable Learned Query Optimization." pith.science (2026). https://pith.science/paper/YO7FA3LM

@misc{pith2026250502284,
  author       = {Pith},
  title        = {Pith review of: Conformal Prediction for Verifiable Learned Query Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YO7FA3LM}},
  note         = {Machine review of arXiv:2505.02284}
}
read the original abstract

Query optimization is critical in relational databases. Recently, numerous Learned Query Optimizers (LQOs) have been proposed, demonstrating superior performance over traditional hand-crafted query optimizers after short training periods. However, the opacity and instability of machine learning models have limited their practical applications. To address this issue, we are the first to formulate the LQO verification as a Conformal Prediction (CP) problem. We first construct the CP model and obtain user-controlled bounded ranges for the actual latency of LQO plans before execution. Then, we introduce CP-based runtime verification along with violation handling to ensure performance prior to execution. For both scenarios, we further extend our framework to handle distribution shifts in the dynamic environment using adaptive CP approaches. Finally, we present CP-guided plan search, which uses actual latency upper bounds from CP to heuristically guide query plan construction. We integrated our verification framework into three LQOs (Balsa, Lero, and RTOS) and conducted evaluations on the JOB and TPC-H workloads. Experimental results demonstrate that our method is both accurate and efficient. Our CP-based approaches achieve tight upper bounds, reliably detect and handle violations. Adaptive CP maintains accurate confidence levels even in the presence of distribution shifts, and the CP-guided plan search improves both query plan quality (up to 9.84x) and planning time, with a reduction of up to 74.4% for a single query and 9.96% across all test queries from trained LQOs.

Figures

Figures reproduced from arXiv: 2505.02284 by the authors.

Figure 1
Figure 1. ML Decisions in Learned Query Optimizers (LQOs). [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 3
Figure 3. shows an example of using both unified and pattern￾based upper bounds to calculate the bounded latency ranges for one testing query plan. Here, we assume a white-box LQO that constructs the plan from the bottom up. Initially, it constructs a Hash Join (HJ) at the first level, with Sequential Scan (SS) operations as left and right children. This parent-children pattern is labeled as (HJ, SS, SS) 4 . Similarly, the pa… view at source ↗
Figure 4
Figure 4. CP-based Runtime Verification Framework. [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗
Figures from the paper (12 more)
Figure 6
Figure 6. Figure 6: Valid Pattern-based Upper Bounds (Balsa on JOB) [PITH_FULL_IMAGE:figures/full_fig_p009_6.png]
Figure 5
Figure 5. Figure 5: Unified-cased Upper Bounds. Pattern-based Upper Bound. Pattern-based upper bound pro￾vides finer granularity for generating a bounded range. In this experiment, we examine the top 3 and least 3 frequently occurring patterns in Balsa on the JOB workload [PITH_FULL_IMAG…
Figure 7
Figure 7. Figure 7: JOB distribution shift with Adaptive CP ( [PITH_FULL_IMAGE:figures/full_fig_p009_7.png]
Figure 8
Figure 8. Figure 8: RTOS distribution shift with Adaptive CP ( [PITH_FULL_IMAGE:figures/full_fig_p010_8.png]
Figure 10
Figure 10. Figure 10: Violation Detection [PITH_FULL_IMAGE:figures/full_fig_p010_10.png]
Figure 9
Figure 9. Figure 9: Non-conformity Scores in Runtime Verification. [PITH_FULL_IMAGE:figures/full_fig_p010_9.png]
Figure 11
Figure 11. Figure 11: Plan Quality Comparison: CP Guided Algorithm [PITH_FULL_IMAGE:figures/full_fig_p011_11.png]
Figure 13
Figure 13. Figure 13: Planning Time Comparison: CP Guided Algorithm [PITH_FULL_IMAGE:figures/full_fig_p011_13.png]
Figure 12
Figure 12. Figure 12: Plan Quality Comparison. We also observe that our algorithm achieves greater improve￾ments in plan quality during the early training stages of Balsa. This aligns with the intuition that it is easier to make improvements within a larger discovery space. As the number o…
Figure 14
Figure 14. Figure 14: Planning Time Comparison: CP Guided Algorithm [PITH_FULL_IMAGE:figures/full_fig_p011_14.png]
Figure 15
Figure 15. Figure 15: Impact of Changing the Sampling Iterations. [PITH_FULL_IMAGE:figures/full_fig_p012_15.png]
Figure 16
Figure 16. Figure 16: Impact on Choice of 𝛿. 7 Related Work Learned Query Optimization (LQO). In recent years, numer￾ous ML-based techniques have been proposed to improve query optimization. One direction is to use ML to improve cardinality estimates for query outputs and use them to predi…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

70 extracted references · 30 canonical work pages

  1. [1]

    Angelopoulos and Stephen Bates

    Anastasios N. Angelopoulos and Stephen Bates. 2022. A Gentle Introduc- tion to Conformal Prediction and Distribution-Free Uncertainty Quantification. arXiv:2107.07511 [cs.LG] https://arxiv.org/abs/2107.07511

    arXiv 2022

  2. [2]

    Angelopoulos and Stephen Bates

    Anastasios N. Angelopoulos and Stephen Bates. 2023. Conformal Prediction: A Gentle Introduction. Found. Trends Mach. Learn. 16, 4 (mar 2023), 494–591. https://doi.org/10.1561/2200000101

    doi:10.1561/2200000101 2023

  3. [3]

    Brian Babcock and Surajit Chaudhuri. 2005. Towards a robust query optimizer: a principled and practical approach. In Proceedings of the 2005 ACM SIGMOD international conference on Management of data . 119–130

    work page 2005

  4. [4]

    Rina Foygel Barber, Emmanuel J Candes, Aaditya Ramdas, and Ryan J Tibshirani

  5. [5]

    Stephen Bates, Emmanuel Candès, Lihua Lei, Yaniv Romano, and Matteo Sesia

    work page

  6. [6]

    Andreas Bauer, Martin Leucker, and Christian Schallhart. 2011. Runtime Verifi- cation for LTL and TLTL. ACM Trans. Softw. Eng. Methodol. 20, 4, Article 14 (sep 2011), 64 pages. https://doi.org/10.1145/2000799.2000800

    arXiv 2011

  7. [7]

    The Annals of Statistics 51, 1 (Feb

    Testing for outliers with conformal p-values. The Annals of Statistics 51, 1 (Feb. 2023). https://doi.org/10.1214/22-aos2244

    doi:10.1214/22-aos2244 2023

  8. [8]

    Smolka, and Scott D

    Luca Bortolussi, Francesca Cairoli, Nicola Paoletti, Scott A. Smolka, and Scott D. Stoller. 2019. Neural Predictive Monitoring. In Runtime Verification, Bernd Finkbeiner and Leonardo Mariani (Eds.). Springer International Publishing, Cham, 129–147

    work page 2019

Show all 70 references
  1. [9]

    TPC-H Benchmark. [n. d.]. http://www.tpc.org/tpch/

  2. [10]

    Simin Cai, Barbara Gallina, Dag Nyström, and Cristina Seceleanu. 2019. Statistical Model Checking for Real-Time Database Management Systems: A Case Study. In 2019 24th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA) (Zaragoza, Spain). IEEE ...

    2019

  3. [11]

    Simin Cai, Barbara Gallina, Dag Nyström, and Cristina Seceleanu. 2016. A Formal Approach for Flexible Modeling and Analysis of Transaction Timeliness and Isolation. In Proceedings of the 24th International Conference on Real-Time Networks and Systems (Brest, France) (RTNS ’16)...

    2016

  4. [12]

    Francesca Cairoli, Nicola Paoletti, and Luca Bortolussi. 2023. Conformal Quan- titative Predictive Monitoring of STL Requirements for Stochastic Processes. In Proceedings of the 26th ACM International Conference on Hybrid Systems: Computation and Control (San Antonio, TX, USA)...

    2023

  5. [13]

    Simin Cai, Barbara Gallina, Dag Nyström, and Cristina Seceleanu. 2018. Specifi- cation and Formal Verification of Atomic Concurrent Real-Time Transactions. In 2018 IEEE 23rd Pacific Rim International Symposium on Dependable Computing (PRDC). 104–114. https://doi.org/10.1109/PR...

    2018

  6. [14]

    Xu Chen, Zhen Wang, Shuncheng Liu, Yaliang Li, Kai Zeng, Bolin Ding, Jingren Zhou, Han Su, and Kai Zheng. 2023. BASE: Bridging the Gap between Cost and Latency for Query Optimization. Proc. VLDB Endow. 16, 8 (April 2023), 1958–1966. https://doi.org/10.14778/3594512.3594525

    2023

  7. [15]

    Cauchois, S

    M. Cauchois, S. Gupta, A. Ali, and J. C. Duchi. 2020. Robust validation: Confident predictions even when distributions shift.arXiv preprint arXiv:2008.04267 (2020)

    2020 arXiv

  8. [16]

    Luc Devroye, László Györfi, and Gábor Lugosi. 2013. A probabilistic theory of pattern recognition. Vol. 31. Springer Science & Business Media

    2013

  9. [17]

    PostgreSQL DBMS. [n. d.]. PostgreSQL DBMS. https://www.postgresql.org/

  10. [18]

    Doshi et al

    L. Doshi et al. 2023. Kepler: Robust Learning for Parametric Query Optimization. In SIGMOD

    2023

  11. [19]

    Alexandre Donzé and Oded Maler. 2010. Robust Satisfaction of Temporal Logic over Real-Valued Signals. In Proceedings of the 8th International Conference on Formal Modeling and Analysis of Timed Systems (Klosterneuburg, Austria) (FOR- MATS’10). Springer-Verlag, Berlin, Heidelbe...

    2010

  12. [20]

    Daniele Foffano, Alessio Russo, and Alexandre Proutiere. 2023. Conformal Off- Policy Evaluation in Markov Decision Processes. arXiv:2304.02574 [cs.LG] https://arxiv.org/abs/2304.02574

    2023 arXiv

  13. [21]

    Fainekos and George J

    Georgios E. Fainekos and George J. Pappas. 2009. Robustness of temporal logic specifications for continuous-time signals. Theoretical Computer Science 410, 42 (2009), 4262–4291. https://doi.org/10.1016/j.tcs.2009.06.021

    2009 doi

  14. [22]

    Isaac Gibbs and Emmanuel J. Candès. 2021. Adaptive conformal inference under distribution shift. In Proceedings of the 35th International Conference on Neural Information Processing Systems (NIPS ’21) . Curran Associates Inc., Red Hook, NY, USA, Article 128, 13 pages

    2021

  15. [23]

    Fontana, G

    M. Fontana, G. Zeni, and S. Vantini. 2023. Conformal prediction: A unified review of theory and new challenges. Bernoulli 29, 1 (2023), 1–23

    2023

  16. [24]

    Andreas Kipf, Michael Freitag, Dimitri Vorona, Peter Boncz, Thomas Neumann, and Alfons Kemper. 2019. Estimating Filtered Group-By Queries is Hard: Deep Learning to the Rescue. In 1st International Workshop on Applied AI for Database Systems and Applications

    2019

  17. [25]

    Amin Kamali, Verena Kantere, Calisto Zuzarte, and Vincent Corvinelli. 2024. Roq: Robust Query Optimization Based on a Risk-aware Learned Cost Model. arXiv:2401.15210 [cs.DB] https://arxiv.org/abs/2401.15210

    2024 arXiv

  18. [26]

    Sanjay Krishnan, Zongheng Yang, Ken Goldberg, Joseph Hellerstein, and Ion Stoica. 2018. Learning to optimize join queries with deep reinforcement learning. arXiv preprint arXiv:1808.03196 (2018)

    2018 arXiv

  19. [27]

    Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter Boncz, and Alfons Kemper. 2019. Learned Cardinalities: Estimating Correlated Joins with Deep Learning. In 9th Biennial Conference on Innovative Data Systems Research (CIDR ’19)

    2019

  20. [28]

    Viktor Leis, Andrey Gubichev, Atanas Mirchev, Peter Boncz, Alfons Kemper, and Thomas Neumann. 2015. How Good Are Query Optimizers, Really? Proc. VLDB Endow. 9, 3 (nov 2015), 204–215. https://doi.org/10.14778/2850583.2850594

    2015

  21. [29]

    J. Lei, M. G’Sell, A. Rinaldo, R. J. Tibshirani, and L. Wasserman. 2018. Distribution- free predictive inference for regression. J. Amer. Statist. Assoc. 113, 523 (2018), 1094–1111

    2018

  22. [30]

    Jeremiah Zhe Liu, Zi Lin, Shreyas Padhy, Dustin Tran, Tania Bedrax-Weiss, and Balaji Lakshminarayanan. 2020. Simple and Principled Uncertainty Estimation with Deterministic Deep Learning via Distance Awareness. In Proceedings of the 34th International Conference on Neural Info...

    2020

  23. [31]

    Deshmukh, and George J

    Lars Lindemann, Xin Qin, Jyotirmoy V. Deshmukh, and George J. Pappas

  24. [32]

    In Proceedings of the ACM/IEEE 14th International Conference on Cyber-Physical Systems (with CPS-IoT Week 2023) (San Antonio, TX, USA) (ICCPS ’23)

    Conformal Prediction for STL Runtime Verification. In Proceedings of the ACM/IEEE 14th International Conference on Cyber-Physical Systems (with CPS-IoT Week 2023) (San Antonio, TX, USA) (ICCPS ’23). Association for Computing Ma- chinery, New York, NY, USA, 142–153. https://doi...

    2023

  25. [33]

    Marcus et al

    R. Marcus et al. 2021. Bao: Making Learned Query Optimization Practical. In SIGMOD

    2021

  26. [34]

    Bruce P Lowerre and B Raj Reddy. 1976. Harpy, a connected speech recognition system. The Journal of the Acoustical Society of America 59, S1 (1976), S97–S97

    1976

  27. [35]

    Oded Maler and Dejan Nickovic. 2004. Monitoring Temporal Properties of Continuous Signals. In Formal Techniques, Modelling and Analysis of Timed and Fault-Tolerant Systems, Yassine Lakhnech and Sergio Yovine (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 152–166

    2004

  28. [36]

    Ryan Marcus and Olga Papaemmanouil. 2019. Plan-structured deep neural network models for query performance prediction. Proc. VLDB Endow. 12, 11 (July 2019), 1733–1746. https://doi.org/10.14778/3342263.3342646

    2019

  29. [38]

    Ryan Marcus and Olga Papaemmanouil. 2018. Deep reinforcement learning for join order enumeration. In Proceedings of the First International Workshop on Exploiting Artificial Intelligence Techniques for Data Management . 1–4

    2018

  30. [39]

    Marcus, Andreas Kipf, Hongzi Mao, Nesime Tatbul, Tim Kraska, and Mohammad Alizadeh

    Parimarjan Negi, Ryan C. Marcus, Andreas Kipf, Hongzi Mao, Nesime Tatbul, Tim Kraska, and Mohammad Alizadeh. 2021. Flow-Loss: Learning Cardinality Estimates That Matter. Proc. VLDB Endow. 14, 11 (2021), 2019–2032. https: //doi.org/10.14778/3476249.3476259

    2021

  31. [40]

    Alnur Ali Maxime Cauchois, Suyash Gupta and John C. Duchi. 2024. Robust Validation: Confident Predictions Even When Distributions Shift. J. Amer. Statist. Assoc. 119, 548 (2024), 3033–3044

    2024

  32. [42]

    Aleksandr Podkopaev and Aaditya Ramdas. 2022. Tracking the risk of a deployed model and detecting harmful distribution shifts. arXiv:2110.06177 [stat.ML] https://arxiv.org/abs/2110.06177

    2022 arXiv

  33. [43]

    Parimarjan Negi, Ziniu Wu, Andreas Kipf, Nesime Tatbul, Ryan Marcus, Sam Madden, Tim Kraska, and Mohammad Alizadeh. 2023. Robust query driven cardinality estimation under changing workloads. Proceedings of the VLDB Endowment 16, 6 (2023), 1520–1533

    2023

  34. [44]

    Baptiste Pelletier, Charles Lesire, Christophe Grand, David Doose, and Mathieu Rognant. 2023. Predictive Runtime Verification of Skill-based Robotic Systems using Petri Nets. In2023 IEEE International Conference on Robotics and Automation (ICRA). 10580–10586. https://doi.org/1...

    2023

  35. [45]

    P Griffiths Selinger, Morton M Astrahan, Donald D Chamberlin, Raymond A Lorie, and Thomas G Price. 1979. Access path selection in a relational database management system. In Proceedings of the 1979 ACM SIGMOD international conference on Management of data . 23–34

    1979

  36. [46]

    PostgreSQL. [n. d.]. PostgreSQL Explain Analyze. https://www.postgresql.org/ docs/current/sql-explain.html

  37. [47]

    Deshmukh

    Xin Qin, Yuan Xia, Aditya Zutshi, Chuchu Fan, and Jyotirmoy V. Deshmukh

  38. [48]

    Ji Sun and Guoliang Li. 2019. An end-to-end learning-based cost estimator. Proc. VLDB Endow. 13, 3 (Nov. 2019), 307–319. https://doi.org/10.14778/3368289. 3368296

    2019 doi

  39. [49]

    Ji Sun, Jintao Zhang, Zhaoyan Sun, Guoliang Li, and Nan Tang. 2021. Learned Cardinality Estimation: A Design Space Exploration and a Comparative Eval- uation. Proc. VLDB Endow. 15, 1 (sep 2021), 85–97. https://doi.org/10.14778/ 3485450.3485459

    2021

  40. [50]

    Glenn Shafer and Vladimir Vovk. 2007. A tutorial on conformal prediction. arXiv:0706.3188 [cs.LG] https://arxiv.org/abs/0706.3188

    2007 arXiv

  41. [51]

    Alaa, and Mihaela van der Schaar

    Kamile Stankeviciute, Ahmed M. Alaa, and Mihaela van der Schaar

  42. [52]

    Tibshirani, Rina Foygel Barber, Emmanuel J

    Ryan J. Tibshirani, Rina Foygel Barber, Emmanuel J. Candès, and Aaditya Ram- das. 2019. Conformal Prediction under Covariate Shift. In Proceedings of the 33rd International Conference on Neural Information Processing Systems . Curran Associates Inc., Red Hook, NY, USA, Article...

    2019

  43. [53]

    Tibshirani, Rina Foygel Barber, Emmanuel J

    Ryan J. Tibshirani, Rina Foygel Barber, Emmanuel J. Candes, and Aaditya Ramdas

  44. [54]

    Denis Volkhonskiy, Evgeny Burnaev, Ilia Nouretdinov, Alexander Gammerman, and Vladimir Vovk. 2017. Inductive Conformal Martingales for Change-Point Detection. In Proceedings of the Sixth Workshop on Conformal and Probabilistic Prediction and Applications (Proceedings of Machin...

    2017

  45. [55]

    Kai Sheng Tai, Richard Socher, and Christopher D Manning. 2015. Improved se- mantic representations from tree-structured long short-term memory networks. arXiv preprint arXiv:1503.00075 (2015)

    2015 arXiv

  46. [56]

    M. F. Taufiq, J.-F. Ton, R. Cornish, Y. W. Teh, and A. Doucet. 2022. Conformal off- policy prediction in contextual bandits. arXiv preprint arXiv:2206.04405 (2022)

    2022 arXiv

  47. [57]

    Wilcox and Brian C

    Cristina M. Wilcox and Brian C. Williams. 2010. Runtime Verification of Sto- chastic, Faulty Systems. In Proceedings of the First International Conference on Runtime Verification (St. Julians, Malta) (RV’10). Springer-Verlag, Berlin, Heidel- berg, 452–459

    2010

  48. [58]

    Peizhi Wu and Zachary G. Ives. 2024. Modeling Shifting Workloads for Learned Database Systems. Proc. ACM Manag. Data 2, 1, Article 38 (March 2024), 27 pages. https://doi.org/10.1145/3639293

    2024 doi

  49. [59]

    Peizhi Wu, Ryan Marcus, and Zachary G. Ives. 2023. Adding Domain Knowledge to Query-Driven Learned Databases. arXiv:2312.01025 [cs.DB] https://arxiv. org/abs/2312.01025

    2023 arXiv

  50. [60]

    Yang et al

    Z. Yang et al. 2022. Balsa: Learning a Query Optimizer Without Expert Demon- strations. In SIGMOD

    2022

  51. [61]

    Vladimir Vovk. 2021. Testing Randomness Online. Statist. Sci. 36, 4 (Nov. 2021). https://doi.org/10.1214/20-sts817

    2021 doi

  52. [62]

    Vladimir Vovk, Alex Gammerman, and Glenn Shafer. 2005. Algorithmic Learning in a Random World. Springer-Verlag, Berlin, Heidelberg

    2005

  53. [63]

    Xiang Yu, Guoliang Li, Chengliang Chai, and Nan Tang. 2020. Reinforcement learning with tree-lstm for join order selection. In 2020 IEEE 36th International Conference on Data Engineering (ICDE) . IEEE, 1297–1308

    2020

  54. [64]

    Yiqi Zhao, Bardh Hoxha, Georgios Fainekos, Jyotirmoy V Deshmukh, and Lars Lindemann. 2024. Robust conformal prediction for STL runtime verification under distribution shift. In 2024 ACM/IEEE 15th International Conference on Cyber-Physical Systems (ICCPS). IEEE, 169–179

    2024

  55. [65]

    Rong Zhu, Wei Chen, Bolin Ding, Xingguang Chen, Andreas Pfadler, Ziniu Wu, and Jingren Zhou. 2023. Lero: A learning-to-rank query optimizer. Proceedings of the VLDB Endowment 16, 6 (2023), 1466–1479. 14

    2023

  56. [67]

    Zongheng Yang, Amog Kamsetty, Sifei Luan, Eric Liang, Yan Duan, Xi Chen, and Ion Stoica. 2020. NeuroCard: One Cardinality Estimator for All Tables. arXiv:2006.08109 [cs] (June 2020). arXiv:2006.08109 [cs]

    2020 arXiv

  57. [68]

    Hellerstein, Sanjay Krishnan, and Ion Stoica

    Zongheng Yang, Eric Liang, Amog Kamsetty, Chenggang Wu, Yan Duan, Xi Chen, Pieter Abbeel, Joseph M. Hellerstein, Sanjay Krishnan, and Ion Stoica

  58. [2019]

    Deep Unsupervised Cardinality Estimation. Proc. VLDB Endow. 13, 3 (nov 2019), 279–292. https://doi.org/10.14778/3368289.3368294

    2019

  59. [2020]

    arXiv:1904.06019 [stat.ME] https://arxiv.org/abs/1904.06019

    Conformal Prediction Under Covariate Shift. arXiv:1904.06019 [stat.ME] https://arxiv.org/abs/1904.06019

    1904 arXiv

  60. [2021]

    In Advances in Neural In- formation Processing Systems , M

    Conformal Time-series Forecasting. In Advances in Neural In- formation Processing Systems , M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (Eds.), Vol. 34. Curran Associates, Inc., 6216–6228. https://proceedings.neurips.cc/paper_files/paper/2021/fil...

    2021

  61. [2022]

    In 2022 ACM/IEEE 13th International Conference on 13 Cyber-Physical Systems (ICCPS)

    Statistical Verification of Cyber-Physical Systems using Surrogate Models and Conformal Inference. In 2022 ACM/IEEE 13th International Conference on 13 Cyber-Physical Systems (ICCPS). 116–126. https://doi.org/10.1109/ICCPS54341. 2022.00017

    2022

  62. [2023]

    The Annals of Statistics 51, 2 (2023), 816–845

    Conformal prediction beyond exchangeability. The Annals of Statistics 51, 2 (2023), 816–845

    2023

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.