Technical Summary: Selectivity Estimation for Linear Queries via Online Learning

Problem Statement

Selectivity estimation is a fundamental component of query optimization, enabling database optimizers to choose efficient execution plans. While traditional methods rely on strong assumptions (e.g., attribute independence) and precomputed statistics (histograms, sketches), recent learning-based approaches have shown empirical promise by leveraging machine learning to capture complex data distributions. However, existing theoretical studies of these learning-based approaches are largely limited to static databases with fixed query distributions.

In practice, real-world database environments are dynamic: data is continuously inserted, updated, and deleted, and query workloads may shift unpredictably without following a stationary distribution. Static models trained on historical data can become stale, leading to degraded accuracy or necessitating expensive retraining. This paper addresses the gap by proposing a theoretical framework for selectivity estimation in a fully dynamic, distribution-free setting.

The core problem is formulated as an online learning task where:

1. In each round $t$, a query vector $v_t$ arrives.
2. The learner predicts the selectivity $\hat{\sigma}_t$.
3. The true selectivity $\sigma_t = \langle v_t, w_t \rangle$ is revealed, where $w_t$ is the underlying database state (a vector in the $k$-dimensional simplex $\Delta_k$).
4. The learner incurs a loss based on the prediction error.

The goal is to minimize regret, defined as the difference between the learner's cumulative loss and the cumulative loss of the best fixed database vector (chosen in hindsight). The paper explicitly rejects comparing against a dynamic benchmark (where the database changes every round) because, as demonstrated, no algorithm can achieve non-trivial regret guarantees against such a benchmark in an adversarial setting.

Methodology and Framework

The authors analyze two distinct database settings:

1. Static Databases: The underlying database vector $w^*$ is fixed but unknown, while queries may be arbitrary.
2. Dynamic Databases: The database vector $w_t$ may change arbitrarily from round to round, in addition to the queries.

The study focuses on linear queries (including point, range, and subset queries) represented by vectors $v \in [0, 1]^k$. Two standard loss functions are considered:

• Squared Loss: $(\sigma_t - \hat{\sigma}_t)^2$, penalizing large errors heavily.
• Absolute Loss: $|\sigma_t - \hat{\sigma}_t|$, capturing average error.

Key Algorithms

• Sequential Maximum Entropy (SeqMaxEnt): Proposed for the static setting. This algorithm maintains a feasible region of database vectors consistent with all observed query-selectivity pairs. In each round, it predicts the selectivity of the maximum entropy distribution within this feasible region. The intuition is that if the algorithm suffers a large loss, the true database must be "far" from the current maximum entropy estimate, ensuring significant progress in identifying the true state.
• Exponentially Weighted Online Optimization (EWOO): Applied to the dynamic setting for squared loss.
• Follow-the-Regularized-Leader (FTRL): Applied to the dynamic setting for absolute loss, utilizing different regularizers ($\ell_2$ for point queries and negative entropy for subset/linear queries).

Key Results and Regret Bounds

The paper establishes nearly tight upper and lower bounds on regret, summarized below. The bounds depend on the support size $k$ (number of bins) and the time horizon $T$.

1. Static Databases

In this setting, regret depends primarily on $k$ and is independent of $T$.

• Squared Loss:
  • Upper Bound: $O(\log k)$ achieved by SeqMaxEnt for range, subset, and linear queries.
  • Lower Bound: $\Omega(\log k)$ for range queries.
  • Result: $\Theta(\log k)$ regret.
• Absolute Loss:
  • Upper Bound: $O(\sqrt{k \log k})$ achieved by SeqMaxEnt for general linear queries.
  • Lower Bound: $\Omega(\sqrt{k / \log k})$ for subset queries.
  • Result: $\tilde{\Theta}(\sqrt{k})$ regret.
• Point Queries: Regret is constant ($O(1)$) under both loss functions, as the database can be identified quickly.

2. Dynamic Databases

In this setting, regret depends primarily on $T$.

• Squared Loss:
  • Lower Bound: $\Omega(\log T)$ for point queries.
  • Upper Bound: $O(k \log T)$ using EWOO.
  • Result: A gap exists between $\Omega(\log T)$ and $O(k \log T)$.
• Absolute Loss:
  • Point Queries: Tight bound of $\Theta(\sqrt{T})$.
  • Subset/Linear Queries: Tight bound of $\Theta(\sqrt{T \log k})$.
  • Result: There is a polynomial separation in the dominant parameter ($T$) between squared loss ($\log T$) and absolute loss ($\sqrt{T}$).

Lower Bound Techniques

• Static Absolute Loss: The authors construct a lower bound using a normalized Hadamard matrix. They encode independent random variables into a single fixed database vector. The query sequence reveals these variables piecemeal, forcing the learner to incur expected loss in each round. A trade-off is managed between the magnitude of perturbation (to ensure the vector stays in the simplex) and the resulting loss.
• Dynamic Squared Loss: The lower bound is derived by reducing the problem to estimating a parameter $\mu$ drawn from a Uniform distribution, where the database state is a Bernoulli($\mu$) sample. The regret corresponds to the posterior variance of $\mu$, which sums to a harmonic series, yielding $\Omega(\log T)$.

Significance and Contributions

The paper claims the following contributions:

1. Distribution-Free Formulation: It provides an online-learning formulation of selectivity estimation that imposes no distributional assumptions on data or queries, addressing the limitations of prior PAC-learning based studies which assume fixed distributions.
2. Theoretical Guarantees: It establishes (nearly) tight regret bounds for common query classes (point, range, subset, linear) across both static and dynamic database settings under both squared and absolute loss functions.
3. Algorithmic Framework: It introduces the SeqMaxEnt algorithm, which leverages maximum entropy principles to achieve logarithmic regret in the static setting, and applies standard online optimization techniques (EWOO, FTRL) to the dynamic setting.
4. Insight into Loss Functions: The work highlights a fundamental difference between squared and absolute loss functions, showing a polynomial separation in their regret scaling under dynamic conditions.

The authors note that while practical systems often use periodic retraining, this work provides a rigorous theoretical foundation for understanding the limits of learning in dynamic environments without distributional assumptions. Future work directions identified include closing the gap between the upper and lower bounds for dynamic squared loss, determining optimal bounds for range queries under absolute loss, and extending the framework to richer query classes like joins.