Pith. sign in

REVIEW 2 major objections 6 minor 50 references

Selectivity Estimation for Linear Queries via Online Learning

T0 review · 2 major / 6 minor · reviewed 2026-07-12 · grok-4.5

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

Pith's one-line read Online learning gives nearly tight regret bounds for selectivity estimation of linear queries on both static and dynamic data.

desk verdict Clean, nearly tight regret theory for selectivity estimation under adversarial data and queries; the fixed-comparator modeling choice is necessary and well-justified. read the letter →

arxiv 2607.02895 v1 pith:OTMA6WQS submitted 2026-07-03 cs.DB cs.LG

Fangzhu Shen , Debmalya Panigrahi , Sudeepa Roy This is my paper · ORCID
classification cs.DBcs.LG
keywords selectivityestimationonlinelearningregretanalysislinearquerieshistogramsstaticdatabasesdynamiclossfunctions
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

Selectivity estimation is the problem of guessing how many rows a query will hit before it runs. Most theory for learned estimators still assumes a fixed query distribution and a frozen database. This paper drops those assumptions and treats estimation as online learning: queries arrive one by one, the algorithm predicts, the true selectivity is revealed, and a loss is charged. Performance is measured by regret against the single best fixed database state in hindsight. For the standard histogram model of linear queries (point, range, subset, and general linear), the authors prove nearly matching upper and lower bounds under squared and absolute loss, for both static and fully dynamic databases. The results show that sublinear regret is possible without any distributional assumptions, and that the two loss functions separate polynomially in the dominant parameter.

What carries the argument

Regret against a fixed comparator database (Eqs. 1–2), realized by SeqMaxEnt (maximum-entropy projection on the nested feasible region of consistent weight vectors) for static data and by EWOO / FTRL for dynamic data.

What would settle it

Exhibit any algorithm whose cumulative squared loss on static range queries grows slower than c log k for large k, or show that every algorithm’s absolute-loss regret on static subset queries is o(√(k / log k)).

Watch

Extended reading notes

Core claim

For histogram-based linear queries under squared and absolute loss, online algorithms achieve nearly tight regret against the best fixed database: Θ(log k) and Θ̃(√k) on static data, and Θ(log T), Θ(√T), and Θ(√(T log k)) on dynamic data, depending on the loss and query class.

Load-bearing premise

The performance benchmark is required to be a single unchanging database vector for the whole sequence; a fully dynamic benchmark would make every algorithm suffer linear regret.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 6 minor

Summary. The paper casts selectivity estimation for histogram-based linear queries (point, range, subset, and general linear) as an online learning problem. Performance is measured by regret against the best fixed database vector in hindsight under squared and absolute loss, for both static and fully dynamic databases. The authors give nearly tight bounds (Tables 1–2): for static data, Θ(log k) under squared loss via SeqMaxEnt and Θ̃(√k) under absolute loss; for dynamic data, Θ(log T) under squared loss (up to a k factor in the upper bound) and Θ(√T) / Θ(√(T log k)) under absolute loss via EWOO and FTRL. Matching lower bounds are obtained by Yao minimax with Hadamard, Beta-posterior, and Rademacher constructions. The fixed-comparator choice is justified by showing that any dynamic benchmark forces linear regret (Example 1.1).

Significance. This is a clean, distribution-free theoretical foundation for learned selectivity estimation that removes the i.i.d./static assumptions of prior PAC-style analyses. The nearly matching upper and lower bounds, explicit algorithms (SeqMaxEnt, CoordMem, EWOO, FTRL), and careful modeling justification constitute a solid contribution that links online convex optimization to a core database primitive. Proofs rely on standard, correctly applied tools (KL projection + Pinsker + Pythagorean, exp-concavity, FTRL diameter/Lipschitz arguments, concentration). The open gaps (k-factor for dynamic squared loss; absolute-loss range queries) are acknowledged and do not undermine the stated theorems. For a theory-oriented database or learning-theory venue this is a significant and publishable result.

major comments (2)
  1. §3 and Corollary C.3 vs Theorem 3.1: the dynamic squared-loss upper bound is O(k log T) while the lower bound is only Ω(log T). The paper correctly treats T as the dominant parameter and labels the result “nearly tight,” yet the k-factor gap is the largest remaining quantitative hole. A short discussion of whether the k dependence is inherent (e.g., via an information-theoretic argument) or an artifact of EWOO would make the claim sharper; the current future-work sentence in §5 is too brief for a load-bearing open question.
  2. §2.1 / Algorithm 1 and Appendix C: SeqMaxEnt requires an exact entropy maximizer over a polytope each round, and EWOO requires integration over the simplex. Both are polynomial-time in principle but expensive for large k. The theoretical claims do not depend on practicality, yet a one-paragraph remark on approximate solvers (or the weaker O(k^{3/2} log T) Online Newton Step bound already stated in (16)) would better serve a database audience without changing any theorem.
minor comments (6)
  1. Lemma B.1 and B.3 titles: “Ineqality” → “Inequality”.
  2. Proposition A.1 title: “Point qeries” → “Point queries”; also missing space after “CoordMem” in the body text.
  3. Observation 1 proof: the claim “after at most k−1 linearly independent queries w* can be uniquely determined” is correct under the simplex constraint, but a parenthetical note that the queries must be linearly independent of the all-ones vector would avoid a possible reader confusion.
  4. Table 1 / Table 2: the shaded-box highlight mentioned in §1.5 is not visible in the text-only rendering; ensure the camera-ready version marks the three highlighted results clearly.
  5. §4 Related Work: the brief comparison to nested convex-body chasing is helpful; a sentence on why movement-cost lower bounds do not transfer (different cost measure) would make the distinction even clearer.
  6. Throughout: “Loss_t := Loss(σ_t, σ̂_t)” is overloaded with the functional form Loss_t(w); a consistent notation (e.g., ℓ_t vs L_t) would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: regret bounds are derived from first-principles online-learning arguments against an external fixed-comparator benchmark.

full rationale

The paper defines regret against the best fixed database vector in hindsight (Eqs. 1–2) and then proves upper and lower bounds by standard, self-contained arguments: KL projection + Pinsker + Pythagorean for SeqMaxEnt (Thm 2.1, Lemmas 2.2/B.1–B.2), Hadamard/Beta constructions for matching lower bounds (Thms 2.4, 3.1, D.1–D.2), exp-concavity of squared loss for EWOO (Lem C.1 / Cor C.3), and FTRL diameter/Lipschitz arguments for absolute loss (Thms D.6–D.14). No parameters are fitted to data and then re-presented as predictions; no uniqueness theorem or ansatz is imported from overlapping authors as a load-bearing premise; the fixed-comparator choice is explicitly justified by Example 1.1 rather than smuggled in. The derivation chain is therefore independent of its own outputs.

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

The paper rests on standard online-learning and information-theoretic primitives plus the modeling choice that databases are histograms on a known discrete support of size k and that queries are linear. No free parameters are fitted; the only modeling axioms are the histogram representation and the fixed-comparator definition of regret.

assumptions (4)
  • domain assumption Database state is a vector in the probability simplex Δ_k (histogram of relative frequencies).
    Stated in Section 1.1; all algorithms and bounds are derived inside this representation.
  • domain assumption Queries are linear functionals v ∈ [0,1]^k; selectivity is the inner product ⟨v,w⟩.
    Section 1.1; point/range/subset queries are special cases.
  • domain assumption Regret is measured against the single best fixed database vector in hindsight (Eqs. 1–2).
    Justified by Example 1.1 showing that a fully dynamic comparator forces linear regret.
  • standard math Pinsker’s inequality, Pythagorean theorem for KL divergence, Hölder’s inequality, Hoeffding’s inequality, Yao’s minimax principle.
    Invoked throughout Sections 2–3 and Appendices B–D.
invented entities (1)
  • Sequential Maximum Entropy (SeqMaxEnt) algorithm
    purpose: Achieves O(log k) squared-loss and O(√(k log k)) absolute-loss regret for static databases by always predicting with the max-entropy vector consistent with observed equalities.
    Introduced in Algorithm 1 and Theorem 2.1; the KL-telescoping analysis is original to this paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Selectivity Estimation for Linear Queries via Online Learning." pith.science (2026). https://pith.science/paper/OTMA6WQS

@misc{pith2026260702895,
  author       = {Pith},
  title        = {Pith review of: Selectivity Estimation for Linear Queries via Online Learning},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OTMA6WQS}},
  note         = {Machine review of arXiv:2607.02895}
}
read the original abstract

Learning-based approaches for selectivity estimation in databases have gained significant traction in recent years. However, theoretical studies of these learning-based approaches are essentially limited to fixed query distributions on static databases. In practice, both the underlying database and the query workload can dynamically change over time. In this work, we propose an algorithmic framework for learning selectivity of queries in this more general dynamic setup. Inspired by online learning, we measure the performance of the learning algorithm in this setting by its regret, which compares the cumulative loss incurred by the learning algorithm to that of the best fixed strategy. We establish upper and lower bounds on regret for histogram-based linear queries, such as point, range, and subset selection queries, under standard loss functions, in both static and dynamic database settings.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

50 extracted references · 1 canonical work pages

  1. [1]

    Aaron Anderson and Michael Benedikt. 2025. From learnable objects to learnable random objects.arXiv preprint arXiv:2504.00847(2025)

    arXiv 2025

  2. [2]

    Daniel Berend and Aryeh Kontorovich. 2013. A sharp estimate of the binomial mean absolute deviation with applications.Statistics & Probability Letters83, 4 (2013), 1254–1259

    2013

  3. [3]

    2013.Statistical decision theory and Bayesian analysis

    James O Berger. 2013.Statistical decision theory and Bayesian analysis. Springer Science & Business Media

    2013

  4. [4]

    2004.Convex Optimization

    Stephen Boyd and Lieven Vandenberghe. 2004.Convex Optimization. Cambridge University Press

    2004

  5. [5]

    Sébastien Bubeck, Bo’az Klartag, Yin Tat Lee, Yuanzhi Li, and Mark Sellke. 2020. Chasing nested convex bodies nearly optimally. InProceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1496–1508

    2020

  6. [6]

    2006.Prediction, learning, and games

    Nicolo Cesa-Bianchi and Gábor Lugosi. 2006.Prediction, learning, and games. Cambridge university press

    2006

  7. [7]

    Yuvaraj Chesetti and Prashant Pandey. 2026. To Adapt or Not to Adapt, That is the Ski Question.Proceedings of the ACM on Management of Data4, 3 (SIGMOD (2026), 1–27

    2026

  8. [8]

    Haas, and Chris Jermaine

    Graham Cormode, Minos Garofalakis, Peter J. Haas, and Chris Jermaine. 2012. Synopses for Massive Data: Samples, Histograms, Wavelets, Sketches.Foundations and Trends in Databases4, 1–3 (2012), 1–294

    2012

Show all 50 references
  1. [9]

    1999.Elements of information theory

    Thomas M Cover. 1999.Elements of information theory. John Wiley & Sons

    1999

  2. [10]

    2011.Information theory: coding theorems for discrete memoryless systems

    Imre Csiszár and János Körner. 2011.Information theory: coding theorems for discrete memoryless systems. Cambridge University Press

    2011

  3. [11]

    Narasayya, and Surajit Chaudhuri

    Anshuman Dutt, Chi Wang, Azade Nazi, Srikanth Kandula, Vivek R. Narasayya, and Surajit Chaudhuri. 2019. Selectivity Estimation for Range Predicates using Lightweight Models. InProceedings of the VLDB Endowment, Vol. 12. 1044–1057

    2019

  4. [12]

    Joel Friedman and Nathan Linial. 1993. On Convex Body Chasing.Discret. Comput. Geom.9 (1993), 293–321. doi:10.1007/BF02189324

    1993 doi

  5. [13]

    David Haussler. 1992. Decision theoretic generalizations of the PAC model for neural net and other learning applications. Inf. Comput.100, 1 (Sept. 1992), 78–150. doi:10.1016/0890-5401(92)90010-D

    1992 doi

  6. [14]

    Elad Hazan. 2016. Introduction to online convex optimization.Foundations and Trends in Optimization2, 3-4 (2016), 157–325

    2016

  7. [15]

    Elad Hazan, Amit Agarwal, and Satyen Kale. 2007. Logarithmic Regret Algorithms for Online Convex Optimization. Machine Learning69, 2–3 (2007), 169–192

    2007

  8. [16]

    Wassily Hoeffding. 1963. Probability Inequalities for Sums of Bounded Random Variables.J. Amer. Statist. Assoc.58, 301 (1963), 13–30

    1963

  9. [17]

    2012.Hadamard matrices and their applications

    Kathy Horadam. 2012.Hadamard matrices and their applications. Princeton university press

    2012

  10. [18]

    Xiao Hu, Yuxi Liu, Haibo Xiu, Pankaj K Agarwal, Debmalya Panigrahi, Sudeepa Roy, and Jun Yang. 2022. Selectivity functions of range queries are learnable. InProceedings of the 2022 International Conference on Management of Data. 959–972

    2022

  11. [19]

    Yannis Ioannidis. 2003. The History of Histograms (Abridged). InProceedings of the 29th International Conference on Very Large Data Bases (VLDB). 19–30

    2003

  12. [20]

    Ioannidis and Stavros Christodoulakis

    Yannis E. Ioannidis and Stavros Christodoulakis. 1991. On the Propagation of Errors in the Size of Join Results. In Proceedings of the 1991 ACM SIGMOD International Conference on Management of Data. ACM, 268–277

    1991

  13. [21]

    2022.Bayes rules!: An introduction to applied Bayesian modeling

    Alicia A Johnson, Miles Q Ott, and Mine Dogucu. 2022.Bayes rules!: An introduction to applied Bayesian modeling. Chapman and Hall/CRC

    2022

  14. [22]

    Kyoungmin Kim, Jisung Jung, In Seo, Wook-Shin Han, Kangwoo Choi, and Jaehyok Chong. 2022. Learned cardinality estimation: An in-depth study. InProceedings of the 2022 international conference on management of data. 1214–1227

    2022

  15. [23]

    Jyrki Kivinen and Manfred K Warmuth. 1997. Exponentiated gradient versus gradient descent for linear predictors. Information and computation132, 1 (1997), 1–63

    1997

  16. [24]

    Beibin Li, Yao Lu, and Srikanth Kandula. 2022. Warper: Efficiently adapting learned cardinality estimators to data and workload drifts. InProceedings of the 2022 International Conference on Management of Data. 1920–1933

    2022

  17. [25]

    Pengfei Li, Wenqing Wei, Rong Zhu, Bolin Ding, Jingren Zhou, and Hua Lu. 2023. ALECE: An Attention-based Learned Cardinality Estimator for SPJ Queries on Dynamic Workloads.Proceedings of the VLDB Endowment17, 2 (2023), 197–210

    2023

  18. [26]

    Richard J Lipton, Jeffrey F Naughton, and Donovan A Schneider. 1990. Practical selectivity estimation through adaptive sampling. InProceedings of the 1990 ACM SIGMOD international conference on Management of data. 1–11

    1990

  19. [27]

    Ryan Marcus, Parimarjan Negi, Hongzi Mao, Nesime Tatbul, Mohammad Alizadeh, and Tim Kraska. 2020. Bao: Learning to steer query optimizers.arXiv preprint arXiv:2004.03814(2020). Selectivity Estimation for Linear Queries via Online Learning 17

    2020 arXiv

  20. [28]

    Ryan Marcus, Parimarjan Negi, Hongzi Mao, Chi Zhang, Mohammad Alizadeh, Tim Kraska, Olga Papaemmanouil, and Nesime Tatbul23. [n. d.]. Neo: A Learned Query Optimizer.Proceedings of the VLDB Endowment12, 11 ([n. d.])

  21. [29]

    Yossi Matias, Jeffrey Scott Vitter, and Min Wang. 1998. Wavelet-based histograms for selectivity estimation. In Proceedings of the 1998 ACM SIGMOD international conference on Management of data. 448–459

    1998

  22. [30]

    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 Endowment16, 6 (2023), 1520–1533

    2023

  23. [31]

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

    2020

  24. [32]

    Viswanath Poosala, Peter J Haas, Yannis E Ioannidis, and Eugene J Shekita. 1996. Improved histograms for selectivity estimation of range predicates.ACM Sigmod Record25, 2 (1996), 294–305

    1996

  25. [33]

    Ioannidis

    Viswanath Poosala and Yannis E. Ioannidis. 1997. Selectivity Estimation Without the Attribute Value Independence Assumption. InProceedings of the 23rd International Conference on Very Large Data Bases (VLDB). 486–495

    1997

  26. [34]

    Shai Shalev-Shwartz. 2012. Online Learning and Online Convex Optimization.Foundations and Trends®in Machine Learning4, 2 (2012), 107–194

    2012

  27. [35]

    Stein and Rami Shakarchi

    Elias M. Stein and Rami Shakarchi. 2005.Real Analysis: Measure Theory, Integration, and Hilbert Spaces. Princeton Lectures in Analysis, Vol. 3. Princeton University Press, Princeton, NJ

    2005

  28. [36]

    Ji Sun, Jintao Zhang, Zhaoyan Sun, Guoliang Li, and Nan Tang. 2021. Learned Cardinality Estimation: A Design Space Exploration and a Comparative Evaluation.Proceedings of the VLDB Endowment15, 1 (2021), 85–97

    2021

  29. [37]

    James Joseph Sylvester. 1867. LX. Thoughts on inverse orthogonal matrices, simultaneous signsuccessions, and tessellated pavements in two or more colours, with applications to Newton’s rule, ornamental tile-work, and the theory of numbers.The London, Edinburgh, and Dublin Phil...

  30. [38]

    L. G. Valiant. 1984. A theory of the learnable. InProceedings of the Sixteenth Annual ACM Symposium on Theory of Computing (STOC ’84). Association for Computing Machinery, New York, NY, USA, 436–445. doi:10.1145/800057.808710

    1984 doi

  31. [39]

    Xiaoying Wang, Changbo Qu, Weiyuan Wu, Jiannan Wang, and Qingqing Zhou. 2021. Are We Ready For Learned Cardinality Estimation?. InProceedings of the VLDB Endowment, Vol. 14. 1640–1654

    2021

  32. [40]

    Zilong Wang, Qixiong Zeng, Ning Wang, Haowen Lu, and Yue Zhang. 2023. Ceda: learned cardinality estimation with domain adaptation.Proceedings of the VLDB Endowment16, 12 (2023), 3934–3937

    2023

  33. [41]

    Peizhi Wu and Zachary G Ives. 2024. Modeling shifting workloads for learned database systems.Proceedings of the ACM on Management of Data2, 1 (2024), 1–27

    2024

  34. [42]

    Peizhi Wu, Haoshu Xu, Ryan Marcus, and Zachary G. Ives. 2025. A Practical Theory of Generalization in Selectivity Learning.Proc. VLDB Endow.18, 6 (Feb. 2025), 1811–1824. doi:10.14778/3725688.3725708

    2025 doi

  35. [43]

    Zongheng Yang, Amog Kamsetty, Sifei Luan, Eric Liang, Yan Duan, Xi Chen, and Ion Stoica. 2020. NeuroCard: One Cardinality Estimator for All Tables. InProceedings of the VLDB Endowment, Vol. 14. 61–73

    2020

  36. [44]

    Andrew Chi-Chin Yao. 1977. Probabilistic computations: Toward a unified measure of complexity. In18th Annual Symposium on Foundations of Computer Science (sfcs 1977). IEEE, 222–227

    1977

  37. [45]

    Sepanta Zeighami and Cyrus Shahabi. 2024. Theoretical analysis of learned database operations under distribution shift through distribution learnability. InProceedings of the 41st International Conference on Machine Learning(Vienna, Austria)(ICML’24). JMLR.org, Article 2404, 23 pages

    2024

  38. [46]

    Sepanta Zeighami and Cyrus Shahabi. 2024. Towards Establishing Guaranteed Error for Learned Database Operations. InThe Twelfth International Conference on Learning Representations

    2024

  39. [47]

    Tianjing Zeng, Junwei Lan, Jiahong Ma, Wenqing Wei, Rong Zhu, Yingli Zhou, Pengfei Li, Bolin Ding, Defu Lian, Zhewei Wei, et al. 2024. PRICE: A Pretrained Model for Cross-Database Cardinality Estimation.Proceedings of the VLDB Endowment18, 3 (2024), 637–650

    2024

  40. [48]

    Martin Zinkevich. 2003. Online convex programming and generalized infinitesimal gradient ascent. InProceedings of the 20th international conference on machine learning (icml-03). 928–936. 18 Fangzhu Shen, Debmalya Panigrahi, and Sudeepa Roy A Static Databases: Point Queries Si...

    2003

  41. [49]

    min w∗ ∈Δ𝑘 𝑇∑︁ 𝑡=1 Loss𝑡 (w∗) # =E

    Choosing 𝛼= 1 2 satisfies the condition uniformly overΔ 𝑘, establishing𝛼-exp-concavity of Loss 𝑡.□ By exploiting this exp-concavity, we achieve logarithmic regret via the Exponentially Weighted Online Optimization (EWOO) algorithm [15]; we follow the description given in [14]....

  42. [50]

    The minimum∥w∥ 2 2 =1/𝑘is achieved at the uniform distributionw=(1/𝑘,

    Therefore: ∥w∥ 2 2 ≥1/𝑘. The minimum∥w∥ 2 2 =1/𝑘is achieved at the uniform distributionw=(1/𝑘, . . . ,1/𝑘). 28 Fangzhu Shen, Debmalya Panigrahi, and Sudeepa Roy Therefore: 𝑅(u) −min w∈Δ 𝑘 𝑅(w)= 1 𝜂 ∥u∥ 2 2 −min w∈Δ 𝑘 ∥w∥ 2 2 = 1 𝜂 ∥u∥ 2 2 − 1 𝑘 ≤ 1 𝜂 1− 1 𝑘 ≤ 1 𝜂 . □ Corollary...

Pith tools

Reviewed July 12, 2026 · model on record in the stance chip above.