acceptodds
Withdrawn from ICLR 2027

Selectivity Estimation in Databases via Online Learning

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Learning-based approaches for selectivity estimation in databases have gained significant traction in recent years. In this paper, we introduce a new framework for this problem that formulates selectivity estimation as an online learning problem. Unlike previous approaches, our framework does not require the underlying database or query distribution to remain fixed and naturally accommodates evolving data and query workloads. Within this framework, we derive tight regret bounds for a broad class of queries under standard loss functions. Furthermore, we complement our theoretical analysis with an extensive empirical evaluation on real-world datasets. Our theoretical and empirical results establish online learning as a principled framework for accurate and adaptive selectivity estimation in dynamic database environments.

Primary area:
learning theory
Keywords:
Online learning, regret analysis, selectivity estimation, query optimization, online convex optimization, databases, dynamic databases

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_1drWOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Cardinality estimation is an important research problem in modern ML-driven DBMSs. One particular technical challenge is that learned models become stale as the underlying database is updated. To address this problem, this paper adopts an online learning approach to update the model. However, the study is limited to selection queries over a single table, where there is little room for query optimization and the need for cardinality/selectivity estimation is relatively limited.

Critical strengths

S1. Adapting learned models to database updates and changes in query workloads is an important research problem.

S2. The paper is theoretically solid in the sense that it ensures the worst case regret for selectivity estimation based on both squared loss and absolute loss.

Critical weaknesses

W1. The problem setting is disconnected from practical scenarios. The paper states that selectivity estimation is a "key input to query optimizers choosing between candidate query execution plans, a central task in database management systems." However, this claim is not accurate. For single-table queries, there is only a single execution plan, or there can be multiple execution plans, but their cost difference is not large. Therefore, query plan optimization is of considerably less importance for single-table queries. Indeed, recent research on learned cardinality estimation has primarily focused on join queries, where the costs of alternative execution plans can differ substantially.

W2. The experimental evaluation is weak.

  • The proposed method is not compared with data-driven SOTA approaches that learn distributions directly from database contents, such as NeuroCard, Naru, and DeepDB.
  • From a practical perspective, the proposed method should also be compared with baseline methods in terms of training cost and inference performance.
Questions for authors

NA

Reviewer_GpFHOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

Selectivity estimation is core to database systems. Learning-based approaches have been studied a lot in the literature. Unlike existing work, this paper formulates selectivity as an online learning problem, where feedback from query executions is used to predict the selectivity of each incoming query.

Critical strengths

N/A

Critical weaknesses

The online learning for selectivity estimation has already been studied (see the following articles). Maybe the authors could have claimed a narrower contribution. However, I only review the intellectual merit based on what is currently written.

Park, Yongjoo, Shucheng Zhong, and Barzan Mozafari. "Quicksel: Quick selectivity learning with mixture models." Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. 2020.

Srivastava, Utkarsh, et al. "Isomer: Consistent histogram construction using query feedback." 22nd International Conference on Data Engineering (ICDE'06). IEEE, 2006.

Aboulnaga, Ashraf, and Surajit Chaudhuri. "Self-tuning histograms: Building histograms without looking at data." ACM SIGMOD Record 28.2 (1999): 181-192.

Bruno, Nicolas, Surajit Chaudhuri, and Luis Gravano. "STHoles: A multidimensional workload-aware histogram." Proceedings of the 2001 ACM SIGMOD international conference on Management of data. 2001.

Questions for authors

N/A

Reviewer_PPkcOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper formulates feedback-based selectivity estimation as online prediction over a probability simplex. Queries are linear functions of an unknown database histogram, and the learner observes their true selectivities after making predictions. For static databases, the proposed SeqMaxEnt algorithm achieves O(log k) cumulative squared loss and O(〖(k log k)〗^(1/2)) cumulative absolute loss, with matching or nearly matching lower bounds. For changing databases, the paper applies established online-learning algorithms and derives lower bounds against the best fixed histogram in hindsight.

Critical strengths
  1. The static absolute-loss analysis provides a meaningful characterization of the problem.

  2. The experiments demonstrate promising performance within the finite-histogram setting.

Critical weaknesses
  1. The novelty of a central theoretical result (e.g., the static squared-loss guarantee) and the main algorithmic principle is insufficiently distinguished from established work.

  2. The dynamic guarantees and experiments do not sufficiently establish the claimed ability to adapt accurately to changing databases. The experimental connection to the guarantee is also incomplete.

Questions for authors
  1. What does the static squared-loss result add beyond the specialization of Kivinen and Warmuth’s Theorem 5.10 above? How does SeqMaxEnt differ substantively from earlier maximum-entropy estimators such as ISOMER, beyond the regret analysis?

  2. Does the Euclidean-projection version of ONS retain a logarithmic-regret guarantee? If not, how do its accuracy and runtime compare with the analyzed generalized-projection algorithm at k = 200?

  3. Can you provide error trajectories immediately after database changes and comparisons with continuously updated feedback-based estimators under comparable update budgets? These would help determine whether the method improves tracking accuracy beyond what the fixed-comparator regret curves establish.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.