Guaranteeing the Õ(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins

Kyoungmin Kim, Jaehyun Ha, George Fletcher, Wook-Shin Han

Introduction

In database management systems, join operations are fundamental yet computationally expensive. Often, rather than computing a full join, applications require only an estimate of the result size (cardinality estimation) or a uniform random sample of the results. These tasks are critical for query optimization and for training machine learning models on relational data.

The theoretical "Holy Grail" for these operations is a runtime complexity of $\tilde{O}(AGM/OUT)$, where $AGM$ represents the theoretical upper bound on the join size and $OUT$ is the actual output size. Such a bound implies that the algorithm is highly efficient when the result set is large and only works harder when the answer is difficult to find. This paper introduces Degree-based Rejection Sampling (DRS), the first algorithm to achieve this optimal runtime for both size estimation and uniform sampling across arbitrary join queries.

The Problem: The $O(IN)$ Bottleneck

Previous state-of-the-art methods for join sampling and estimation faced two primary hurdles. First, many algorithms were restricted to specific query types, such as unlabeled graph patterns. Second, general-purpose methods like GJ-Sample suffered from a mandatory $O(IN)$ overhead—where $IN$ is the size of the input relations. This overhead stems from the need to scan the entire input to calculate sampling probabilities before the actual sampling can begin. In scenarios involving massive, skewed datasets, this linear-time preprocessing makes the algorithms prohibitively slow, preventing them from reaching the sublinear performance suggested by the $AGM/OUT$ ideal.

Methodology: Degree-based Rejection Sampling

To overcome the $O(IN)$ barrier, the authors propose a Generic Sampling-based Framework (GenericCardEst) that unifies existing approaches like WanderJoin and GJ-Sample. Within this framework, they introduce the Degree-based Rejection Sampling (DRS) algorithm.

The DRS Mechanism

Instead of pre-calculating a global probability distribution across all input tuples, DRS utilizes a clever rejection-sampling loop:

  1. Meta-Sampling: The algorithm selects a relation at random and samples a tuple from it.
  2. Local Degree Check: It examines the "relative degree" of the sampled tuple—essentially determining how many potential join results that specific tuple can participate in relative to others.
  3. Rejection Step: Rather than exhaustive calculation, DRS uses rejection sampling. Tuples with lower relative degrees are more likely to be rejected. This process mathematically ensures that the final accepted samples are distributed uniformly across the join result, without ever requiring a full scan of the input data.

Handling Cyclic Queries

For complex, cyclic queries, the authors extend DRS using Generalized Hypertree Decompositions (GHDs). This technique decomposes cyclic queries into smaller, acyclic components. This structural decomposition allows the algorithm to maintain high performance even when the output size is extremely small and sparse, where standard sampling methods typically struggle.

Key Insights and Theoretical Results

The paper's contributions are primarily theoretical, providing rigorous proofs for the following:

  • Optimal Complexity: DRS is proven to achieve a $(1 \pm \epsilon)$-approximation of the join size in $\tilde{O}(AGM/OUT)$ time. This matches the theoretical lower bounds and eliminates the $O(IN)$ overhead.
  • Universality: Unlike previous sublinear estimators, DRS supports any join query, including those with non-binary relations and complex cycles.
  • The GHD Advantage: The authors demonstrate a "phase shift" in efficiency. While standard DRS is optimal for large outputs, the GHD-based approach becomes asymptotically faster when the output size $OUT$ is very small (specifically smaller than $\tilde{O}(IN^{w - fhtw})$).
  • Algorithmic Unification: By framing various sampling methods within the GenericCardEst template, the authors show that many disparate algorithms are actually variations of the same recursive sampling logic.

Limitations and Future Work

While the paper establishes a new theoretical benchmark, several avenues for future research remain:

  • Sampling for Cyclic Joins: While GHDs work for size estimation, extending this efficiency to uniform sampling for arbitrary cyclic joins remains a complex challenge.
  • Heuristic Switching: In practice, an implementation would need to decide when to use standard DRS versus the GHD-based version. Developing a robust heuristic to "guess" the output size and switch dynamically is a pending practical requirement.
  • Leveraging Schema Constraints: The current bounds are based on cardinality. Future work could incorporate functional dependencies or specific degree constraints to provide even tighter runtime guarantees.

Conclusion

By replacing expensive pre-sampling calculations with a local rejection-sampling mechanism, this work successfully bridges the gap between theory and practice in join sampling. The DRS algorithm provides a robust, general-purpose solution that finally achieves the elusive $\tilde{O}(AGM/OUT)$ runtime, offering a significant leap forward for database query processing and data analysis.

Summary updated

Abstract

We propose a new method for estimating the number of answers OUT of a small join query Q in a large database D, and for uniform sampling over joins. Our method is the first to satisfy all the following statements.Support arbitrary Q, which can be either acyclic or cyclic, and contain binary and non-binary relations.Guarantee an arbitrary small error with a high probability always in O(AGM/OUT ) time, where AGM is the AGM bound (an upper bound of OUT), and O hides the polylogarithmic factor of input size.We also explain previous join size estimators in a unified framework. All methods including ours rely on certain indexes on relations in D, which take linear time to build offline. Additionally, we extend our method using generalized hypertree decompositions (GHDs) to achieve a lower complexity than O(AGM/OUT ) when OUT is small, and present optimization techniques for improving estimation efficiency and accuracy.
BibTeX
@inproceedings{kim2023guaranteeing,
  author = {Kyoungmin Kim and Jaehyun Ha and George Fletcher and Wook-Shin Han},
  title = {{Guaranteeing the Õ(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins}},
  booktitle = {PODS},
  year = {2023},
  doi = {10.1145/3584372.3588676},
}
Figure