Lune

VLDB2020Top-tier venue

Learning to Sample: Counting with Complex Queries

Brett Walenz, Stavros Sintos, Sudeepa Roy, Jun Yang

Abstract

We study the problem of efficiently estimating counts for queries involving complex filters, such as user-defined functions, or predicates involving self-joins and correlated subqueries. For such queries, traditional sampling techniques may not be applicable due to the complexity of the filter preventing sampling over joins, and sampling after the join may not be feasible due to the cost of computing the full join. The other natural approach of training and using an inexpensive classifier to estimate the count instead of the expensive predicate suffers from the difficulties in training a good classifier and giving meaningful confidence intervals. In this paper we propose a new method of learning to sample where we combine the best of both worlds by using sampling in two phases. First, we use samples to learn a probabilistic classifier, and then use the classifier to design a stratified sampling method to obtain the final estimates. We theoretically analyze algorithms for obtaining an optimal stratification, and compare our approach with a suite of natural alternatives like quantification learning, weighted and stratified sampling, and other techniques from the literature. We also provide extensive experiments in diverse use cases using multiple real and synthetic datasets to evaluate the quality, efficiency, and robustness of our approach.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

5 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • JanusAQP: Efficient Partition Tree Maintenance for Dynamic Approximate Query Processing cites Approximate Partition Selection for Big-Data Workloads using Summary Statistics
  • JanusAQP: Efficient Partition Tree Maintenance for Dynamic Approximate Query Processing cites Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing
  • Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing cites Approximate Partition Selection for Big-Data Workloads using Summary Statistics
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers5

  1. Accelerating Approximate Aggregation Queries with Expensive PredicatesDaniel Kang, John Guibas, Peter Bailis, Tatsunori Hashimoto et al.VLDB 2021 · 34 citations
  2. Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query ProcessingXi Liang, Stavros Sintos, Zechao Shang, Sanjay KrishnanSIGMOD 2021 · 27 citations
  3. Consistent and Flexible Selectivity Estimation for High-Dimensional DataYaoshu Wang, Chuan Xiao, Jianbin Qin, Rui Mao et al.SIGMOD 2021 · 12 citations
  4. Approximate Partition Selection for Big-Data Workloads using Summary StatisticsKexin Rong, Yao Lu, Peter Bailis, Srikanth Kandula et al.VLDB 2020 · 8 citations
  5. JanusAQP: Efficient Partition Tree Maintenance for Dynamic Approximate Query ProcessingXi Liang, Stavros Sintos, Sanjay KrishnanICDE 2023 · 3 citations

Related papers

  1. Small Selectivities Matter: Lifting the Burden of Empty SamplesAxel Hertzschuch, Guido Moerkotte, Wolfgang Lehner, Norman May et al.SIGMOD 2021 · 4 citations
  2. Improved Correlated Sampling for Join Size EstimationTaiNing Wang, Chee-Yong ChanICDE 2020 · 19 citations
  3. ASM: Harmonizing Autoregressive Model, Sampling, and Multi-dimensional Statistics Merging for Cardinality EstimationKyoungmin Kim, Sangoh Lee, Injung Kim, Wook-Shin HanSIGMOD 2024 · 18 citations
  4. Efficiently Approximating Selectivity Functions using Low Overhead Regression ModelsAnshuman Dutt, Chi Wang, Vivek R. Narasayya, Surajit ChaudhuriVLDB 2020 · 45 citations
  5. From Single to Multiple Attributes: Experimental Insights on Sampling-Based Distinct Combination Estimation in Group-by QueriesYujie Zhang, Xiaochun Yang, Bin Wang, Yuan SuiICDE 2026
Dusk over the sea between two cliffs drawn in fine vertical lines