Selectivity Estimation for Linear Queries via Online Learning
2026-07-03 • Databases
DatabasesMachine Learning
AI summaryⓘ
The authors study how to estimate how many database entries match certain queries when both the data and the types of queries change over time. Unlike earlier work that assumed fixed data and query patterns, they look at a more realistic situation where things evolve. They use ideas from online learning to measure how well their method does compared to the best fixed approach, using a concept called regret. They prove mathematical limits on this regret for common query types like point and range queries, in both stable and changing database environments.
selectivity estimationonline learningregrethistogramlinear queriespoint queriesrange queriessubset selectiondynamic databasesquery workload
Authors
Fangzhu Shen, Debmalya Panigrahi, Sudeepa Roy
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.