DBScholar

Back to papers

Wander Join: Online Aggregation via Random Walks

Summary: Wander Join uses random walks over the join graph for online aggregation, beating ripple join without precomputed statistics. Statistics-free optimizer selects walk-based plans; strong for multi-table equality and group-by, validated on TPC-H in PostgreSQL. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
hecf2964f7edd6ac3
Venue
SIGMOD
Year
2016
Pagerank
0.00015814493
Overall Rank
594 | 96.02%
DOI
10.1145/2882903.2915235

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{li_sigmod16,
        title = {{Wander Join: Online Aggregation via Random Walks}},
        author = {Li, Feifei and Wu, Bin and Yi, Ke and Zhao, Zhuoyue},
        series = {{SIGMOD} '16},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2882903.2915235},
        url = {https://dl.acm.org/doi/10.1145/2882903.2915235},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 71 citing papers.

Rank Citing Paper Year Venue Pagerank
320 DeepDB: Learn from Data, not from Queries! 2020 VLDB 0.00021128745
508 NeuroCard: One Cardinality Estimator for All Tables 2021 VLDB 0.00017108973
770 VerdictDB: Universalizing Approximate Query Processing 2018 SIGMOD 0.00014086699
793 Random Sampling over Joins Revisited 2018 SIGMOD 0.00013903938
983 Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation 2022 VLDB 0.00012677179
1,064 Are We Ready For Learned Cardinality Estimation? 2021 VLDB 0.00012181459
1,065 Approximate Query Processing: No Silver Bullet 2017 SIGMOD 0.00012181098
1,681 Two-Level Sampling for Join Size Estimation 2017 SIGMOD 9.8821344e-05
1,740 Flow-Loss: Learning Cardinality Estimates That Matter 2021 VLDB 9.7289523e-05
1,804 IDEBench: A Benchmark for Interactive Data Exploration 2020 SIGMOD 9.5971444e-05
2,635 Neural Subgraph Counting with Wasserstein Estimator 2022 SIGMOD 8.1795762e-05
2,829 G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching 2020 SIGMOD 7.9469964e-05
2,852 FactorJoin: A New Cardinality Estimation Framework for Join Queries 2023 SIGMOD 7.9201312e-05
2,987 Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs 2022 VLDB 7.767043e-05
3,105 A Learned Sketch for Subgraph Counting 2021 SIGMOD 7.6278115e-05
3,428 Revisiting Reuse for Approximate Query Processing 2017 VLDB 7.2957009e-05
3,435 AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics 2018 SIGMOD 7.2845431e-05
4,011 Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins 2023 PODS 6.842581e-05
4,315 ALECE: An Attention-based Learned Cardinality Estimator for SPJ Queries on Dynamic Workloads 2024 VLDB 6.6545412e-05
4,479 Lightweight and Accurate Cardinality Estimation by Neural Network Gaussian Process 2022 SIGMOD 6.5665703e-05
4,661 Efficient Join Synopsis Maintenance for Data Warehouse 2020 SIGMOD 6.4656621e-05
5,271 Cardinality Estimation of Subgraph Matching: A Filtering-Sampling Approach 2024 VLDB 6.1891764e-05
5,399 At-the-time and Back-in-time Persistent Sketches 2021 SIGMOD 6.1336701e-05
5,435 Towards Distribution-aware Query Answering in Data Markets 2022 VLDB 6.1167862e-05
5,622 Responsible Data Integration: Next-generation Challenges 2022 SIGMOD 6.0460189e-05
5,671 PGMJoins: Random Join Sampling with Graphical Models 2021 SIGMOD 6.026372e-05
5,717 Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation 2021 SIGMOD 6.0067263e-05
5,752 Tailoring Data Source Distributions for Fairness-aware Data Integration 2021 VLDB 5.9890389e-05
5,841 Joins on Samples: A Theoretical Guide for Practitioners 2020 VLDB 5.9569427e-05
5,883 Leveraging Application Data Constraints to Optimize Database-Backed Web Applications 2023 VLDB 5.9423067e-05
5,885 BlinkML: Efficient Maximum Likelihood Estimation with Probabilistic Guarantees 2019 SIGMOD 5.9421702e-05
6,014 Approximate Query Engines: Commercial Challenges and Research Opportunities 2017 SIGMOD 5.8956963e-05
6,061 PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration 2021 SIGMOD 5.8831543e-05
6,485 Cardinality Estimation over Knowledge Graphs with Embeddings and Graph Neural Networks 2024 SIGMOD 5.7525455e-05
6,812 dbET: Execution Time Distribution-based Plan Selection 2023 SIGMOD 5.6597129e-05
6,840 ASM: Harmonizing Autoregressive Model, Sampling, and Multi-dimensional Statistics Merging for Cardinality Estimation 2024 SIGMOD 5.6513231e-05
7,175 Learning to Sample: Counting with Complex Queries 2020 VLDB 5.5779755e-05
7,387 Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021 SIGMOD 5.5212177e-05
7,624 Scalable Approximate Butterfly and Bi-triangle Counting for Large Bipartite Networks 2023 SIGMOD 5.4661079e-05
7,626 Privacy Amplification by Sampling under User-level Differential Privacy 2024 SIGMOD 5.4657865e-05
7,675 Continuous Prefetch for Interactive Data Applications 2020 VLDB 5.4565877e-05
7,720 Enabling Efficient and General Subpopulation Analytics in Multidimensional Data Streams 2022 VLDB 5.4542911e-05
7,902 Identifying Insufficient Data Coverage in Databases with Multiple Relations 2020 VLDB 5.4135994e-05
7,950 Biathlon: Harnessing Model Resilience for Accelerating ML Inference Pipelines 2024 VLDB 5.402957e-05
8,300 Subset Sampling over Joins 2026 PODS 5.3434957e-05
8,305 Experiences with Approximating Queries in Microsoft’s Production Big-Data Clusters 2019 VLDB 5.3427507e-05
8,685 ShadowAQP: Efficient Approximate Group-by and Join Query via Attribute-oriented Sample Size Allocation and Data Generation 2023 VLDB 5.2730954e-05
8,769 ProgressiveDB – Progressive Data Analytics as a Middleware 2019 VLDB 5.2691244e-05
8,872 SkinnerMT: Parallelizing for Efficiency and Robustness in Adaptive Query Processing on Multicore Platforms 2023 VLDB 5.2459616e-05
8,915 FastPDB: Towards Bag-Probabilistic Queries at Interactive Speeds 2025 SIGMOD 5.2361195e-05
Previous Page 1 / 2 Next

Outgoing Citations (Sorted by Pagerank)

Showing 30 of 30 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
9 Online Aggregation 1997 SIGMOD 0.00076079812
23 Spark SQL: Relational Data Processing in Spark 2015 SIGMOD 0.00055523999
57 On Random Sampling over Joins 1999 SIGMOD 0.0003999751
79 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00036394222
135 Ripple Joins for Online Aggregation 1999 SIGMOD 0.00029805026
153 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.0002855087
518 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.00016918797
752 Join Size Estimation Subject to Filter Conditions 2015 VLDB 0.00014234789
1,012 Query Size Estimation by Adaptive Sampling (Extended Abstract) 1990 PODS 0.00012489386
1,022 Online Aggregation for Large MapReduce Jobs 2011 VLDB 0.00012400958
1,077 Cache-Oblivious String B-trees 2006 PODS 0.00012122621
1,095 Scalable Approximate Query Processing With The DBO Engine 2007 SIGMOD 0.00012036913
1,254 Blink and It's Done: Interactive Queries on Very Large Data 2012 VLDB 0.00011314204
1,435 Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems 2014 SIGMOD 0.00010659454
1,668 Rapid Sampling for Visualizations with Ordering Guarantees 2015 VLDB 9.9190265e-05
1,832 A Scalable Hash Ripple Join Algorithm 2002 SIGMOD 9.5365548e-05
1,874 G-OLA: Generalized On-Line Aggregation for Interactive Analysis on Big Data 2015 SIGMOD 9.4470874e-05
1,924 The Analytical Bootstrap: a New Method for Fast Error Estimation in Approximate Query Processing 2014 SIGMOD 9.3535088e-05
2,191 Combining User Interaction, Speculative Query Execution and Sampling in the DICE System 2014 VLDB 8.8844453e-05
2,461 A Sampling Algebra for Aggregate Estimation 2013 VLDB 8.4123214e-05
2,504 Independent Range Sampling 2014 PODS 8.3571366e-05
3,092 Continuous Sampling for Online Aggregation Over Multiple Queries 2010 SIGMOD 7.638249e-05
3,220 Turbo-Charging Estimate Convergence in DBO 2009 VLDB 7.5077984e-05
3,825 Spatial Online Sampling and Aggregation 2016 VLDB 6.9795872e-05
3,890 Stochastic Database Cracking: Towards Robust Adaptive Indexing in Main-Memory Column-Stores 2012 VLDB 6.926806e-05
3,912 Distributed Online Aggregations 2009 VLDB 6.9103187e-05
5,149 Holistic Indexing in Main-memory Column-stores 2015 SIGMOD 6.2382463e-05
5,487 ABS: a System for Scalable Approximate Queries with Accuracy Guarantees 2014 SIGMOD 6.0974772e-05
5,600 Derby/S: A DBMS for Sample-Based Query Answering 2006 SIGMOD 6.052685e-05
6,013 Concurrency Control for Adaptive Indexing 2012 VLDB 5.8958102e-05
Previous Page 1 / 1 Next

Semantically Similar Papers