Selectivity Estimation in Databases via Online Learning

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.