Computing Data Distribution from Query Selectivities

Pankaj K. Agarwal, Rahul Raychaudhury, Stavros Sintos, Jun Yang

Abstract

Reconstructing an underlying data distribution from a set of query selectivities is a fundamental problem at the intersection of database systems and computational geometry. This paper demonstrates that while finding an exact solution is NP-hard for dimensions $d \ge 2$, a near-linear time approximation algorithm is achievable. By integrating the Multiplicative Weights Update (MWU) method with geometric sampling techniques, the authors present a framework for building compact data synopses that satisfy observed query results within provable error bounds.

Introduction

In modern database systems, selectivity estimation—predicting the fraction of rows a query will return—is critical for efficient query optimization. While databases typically rely on histograms or random sampling of raw data, this paper explores the "inverse" problem: constructing a synthetic data distribution based solely on a workload of previous queries and their observed selectivities. This is particularly relevant in scenarios where raw data is inaccessible due to privacy constraints or massive scale.

The primary challenge lies in the computational complexity of the task. In a $d$-dimensional space, the number of potential "cells" formed by the intersection of $n$ queries grows polynomially as $O(n^d)$. Consequently, finding a distribution that perfectly matches all observations becomes intractable as the number of queries and dimensions increases.

Problem Formulation and Complexity

The authors frame the problem as finding a discrete distribution—a set of points with associated weights—that minimizes the discrepancy between the model's predicted selectivities and the actual observed values.

Geometric arrangement of queries (rectangles) and data points (p and q).

A key contribution of the paper is the proof that this problem is NP-complete for axis-aligned rectangles in two or more dimensions, regardless of whether the error is measured using $L_1, L_2, \text{ or } L_\infty$ metrics. This hardness result justifies the shift from seeking exact solutions to developing efficient approximation algorithms.

Algorithmic Approach

To overcome the limitations of exact Linear Programming (LP) formulations, which require $O(n^d)$ variables, the authors employ several advanced techniques:

  1. Multiplicative Weights Update (MWU): This iterative meta-algorithm reduces the global optimization problem into a sequence of simpler decision problems. In each round, the algorithm adjusts the weights of the queries based on how well the current distribution satisfies them.
  2. Geometric Implicit Representation: Rather than materializing every possible cell in the arrangement, the distribution is represented implicitly. The core task in each MWU iteration becomes finding the "weighted deepest point"—the location covered by the maximum total weight of query regions.
  3. Sampling and $\epsilon$-Approximations: To accelerate the search for the deepest point, the authors use random sampling. This allows the algorithm to find an approximately deepest point in time that scales primarily with the desired error bound $\delta$ rather than the total number of queries $n$.

Key Results

The theoretical analysis yields several significant findings:

  • Efficient Approximation: The developed Monte Carlo algorithm constructs a distribution of size $O(\delta^{-2})$ with an additive error of at most $\delta$.
  • Near-Linear Runtime: The algorithm achieves a runtime of $O((n + \delta^{-d})\delta^{-2} \text{polylog } n)$. For a fixed dimension and error tolerance, this performance is nearly linear relative to the number of queries.
  • Generality: The framework is not limited to rectangles; it extends to more complex semi-algebraic shapes, including balls and half-spaces.
  • Conditional Optimality: Based on the $FPT \neq W[1]$ conjecture, the authors suggest that the exponential dependence on dimension $d$ is likely unavoidable, making their algorithm near-optimal for this class of problems.

Conclusion and Future Work

This research provides a robust theoretical framework for learning data distributions from query feedback. While the algorithm is highly efficient in low-dimensional spaces, the "curse of dimensionality" remains a challenge for high-attribute datasets. Future work may involve extending these geometric techniques to handle more complex database operations, such as joins and aggregations, where query structures are significantly more intricate.

Summary updated

Abstract

We are given a set 𝒵 = {(R_1,s_1), …, (R_n,s_n)}, where each R_i is a range in ℝ^d, such as rectangle or ball, and s_i ∈ [0,1] denotes its selectivity. The goal is to compute a small-size discrete data distribution 𝒟 = {(q₁,w₁),…, (q_m,w_m)}, where q_j ∈ ℝ^d and w_j ∈ [0,1] for each 1 ≤ j ≤ m, and ∑_{1≤j≤m} w_j = 1, such that 𝒟 is the most consistent with 𝒵, i.e., err_p(𝒟,𝒵) = 1/n ∑_{i = 1}ⁿ |s_i - ∑_{j=1}^m w_j⋅1(q_j ∈ R_i)|^p is minimized. In a database setting, 𝒵 corresponds to a workload of range queries over some table, together with their observed selectivities (i.e., fraction of tuples returned), and 𝒟 can be used as compact model for approximating the data distribution within the table without accessing the underlying contents. In this paper, we obtain both upper and lower bounds for this problem. In particular, we show that the problem of finding the best data distribution from selectivity queries is NP-complete. On the positive side, we describe a Monte Carlo algorithm that constructs, in time O((n+δ^{-d}) δ^{-2} polylog n), a discrete distribution 𝒟̃ of size O(δ^{-2}), such that err_p(𝒟̃,𝒵) ≤ min_𝒟 err_p(𝒟,𝒵)+δ (for p = 1,2,∞) where the minimum is taken over all discrete distributions. We also establish conditional lower bounds, which strongly indicate the infeasibility of relative approximations as well as removal of the exponential dependency on the dimension for additive approximations. This suggests that significant improvements to our algorithm are unlikely.
BibTeX
@inproceedings{agarwal2024computing,
  author = {Pankaj K. Agarwal and Rahul Raychaudhury and Stavros Sintos and Jun Yang},
  title = {{Computing Data Distribution from Query Selectivities}},
  booktitle = {Icdt},
  year = {2024},
  doi = {10.4230/lipics.icdt.2024.18},
}
Figure