Database Paper Browser

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
5262
Venue
SIGMOD
Year
2016
Pagerank
0.00015145883
Overall Rank
943 | 93.45%
DOI
10.1145/2882903.2915235

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 68 citing papers.

Rank Citing Paper Year Venue Pagerank
608 DeepDB: Learn from Data, not from Queries! 2020 VLDB 0.00019235898
910 NeuroCard: One Cardinality Estimator for All Tables 2021 VLDB 0.00015423056
1,204 VerdictDB: Universalizing Approximate Query Processing 2018 SIGMOD 0.00013319541
1,369 Random Sampling over Joins Revisited 2018 SIGMOD 0.00012339777
1,574 Approximate Query Processing: No Silver Bullet 2017 SIGMOD 0.00011287495
1,638 Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation 2022 VLDB 0.00011049779
1,703 Are We Ready For Learned Cardinality Estimation? 2021 VLDB 0.00010836769
2,129 IDEBench: A Benchmark for Interactive Data Exploration 2020 SIGMOD 9.480002e-05
2,254 Two-Level Sampling for Join Size Estimation 2017 SIGMOD 9.1897043e-05
2,783 Flow-Loss: Learning Cardinality Estimates That Matter 2021 VLDB 8.1293383e-05
3,001 Neural Subgraph Counting with Wasserstein Estimator 2022 SIGMOD 7.7404487e-05
3,511 Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs 2022 VLDB 7.0254052e-05
3,646 G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching 2020 SIGMOD 6.8853079e-05
3,778 A Learned Sketch for Subgraph Counting 2021 SIGMOD 6.7747398e-05
3,944 AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics 2018 SIGMOD 6.6078243e-05
3,990 FactorJoin: A New Cardinality Estimation Framework for Join Queries 2023 SIGMOD 6.5581983e-05
4,030 Revisiting Reuse for Approximate Query Processing 2017 VLDB 6.5129665e-05
4,434 Lightweight and Accurate Cardinality Estimation by Neural Network Gaussian Process 2022 SIGMOD 6.1929999e-05
5,024 Towards Distribution-aware Query Answering in Data Markets 2022 VLDB 5.7535043e-05
5,104 Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins 2023 PODS 5.6946113e-05
5,150 Efficient Join Synopsis Maintenance for Data Warehouse 2020 SIGMOD 5.6626586e-05
5,401 ALECE: An Attention-based Learned Cardinality Estimator for SPJ Queries on Dynamic Workloads 2024 VLDB 5.5285035e-05
5,806 BlinkML: Efficient Maximum Likelihood Estimation with Probabilistic Guarantees 2019 SIGMOD 5.3200643e-05
5,909 At-the-time and Back-in-time Persistent Sketches 2021 SIGMOD 5.2769377e-05
5,951 PGMJoins: Random Join Sampling with Graphical Models 2021 SIGMOD 5.2592385e-05
5,976 Responsible Data Integration: Next-generation Challenges 2022 SIGMOD 5.245976e-05
6,208 PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration 2021 SIGMOD 5.1568586e-05
6,289 Cardinality Estimation of Subgraph Matching: A Filtering-Sampling Approach 2024 VLDB 5.1275309e-05
6,411 Approximate Query Engines: Commercial Challenges and Research Opportunities 2017 SIGMOD 5.0752468e-05
6,467 Tailoring Data Source Distributions for Fairness-aware Data Integration 2021 VLDB 5.0528156e-05
6,493 Joins on Samples: A Theoretical Guide for Practitioners 2020 VLDB 5.0424713e-05
6,704 Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation 2021 SIGMOD 4.9554912e-05
6,714 Cardinality Estimation over Knowledge Graphs with Embeddings and Graph Neural Networks 2024 SIGMOD 4.9512171e-05
6,907 Continuous Prefetch for Interactive Data Applications 2020 VLDB 4.8925595e-05
7,123 ASM: Harmonizing Autoregressive Model, Sampling, and Multi-dimensional Statistics Merging for Cardinality Estimation 2024 SIGMOD 4.8251036e-05
7,251 Learning to Sample: Counting with Complex Queries 2020 VLDB 4.7890519e-05
7,358 Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021 SIGMOD 4.7529363e-05
7,451 Scalable Approximate Butterfly and Bi-triangle Counting for Large Bipartite Networks 2023 SIGMOD 4.7263711e-05
7,534 Enabling Efficient and General Subpopulation Analytics in Multidimensional Data Streams 2022 VLDB 4.7180004e-05
7,714 Identifying Insufficient Data Coverage in Databases with Multiple Relations 2020 VLDB 4.6700455e-05
7,854 dbET: Execution Time Distribution-based Plan Selection 2023 SIGMOD 4.6350172e-05
8,080 Biathlon: Harnessing Model Resilience for Accelerating ML Inference Pipelines 2024 VLDB 4.5911668e-05
8,240 Experiences with Approximating Queries in Microsoft’s Production Big-Data Clusters 2019 VLDB 4.5522563e-05
8,622 ProgressiveDB – Progressive Data Analytics as a Middleware 2019 VLDB 4.4834877e-05
8,775 SkinnerMT: Parallelizing for Efficiency and Robustness in Adaptive Query Processing on Multicore Platforms 2023 VLDB 4.4553047e-05
8,873 Privacy Amplification by Sampling under User-level Differential Privacy 2024 SIGMOD 4.4313867e-05
9,410 Leveraging Application Data Constraints to Optimize Database-Backed Web Applications 2023 VLDB 4.3441378e-05
9,621 ShadowAQP: Efficient Approximate Group-by and Join Query via Attribute-oriented Sample Size Allocation and Data Generation 2023 VLDB 4.3167167e-05
9,652 Secure Sampling for Approximate Multi-party Query Processing 2023 SIGMOD 4.3109001e-05
9,845 Path-centric Cardinality Estimation for Subgraph Matching 2025 VLDB 4.2721228e-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
14 Online Aggregation 1997 SIGMOD 0.0010801504
18 On Random Sampling over Joins 1999 SIGMOD 0.00092385438
66 Spark SQL: Relational Data Processing in Spark 2015 SIGMOD 0.00061639801
92 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00051315959
184 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.00036625711
217 Ripple Joins for Online Aggregation 1999 SIGMOD 0.00033536712
530 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.00020803682
762 Query Size Estimation by Adaptive Sampling (Extended Abstract) 1990 PODS 0.00017036868
1,117 Cache-Oblivious String B-trees 2006 PODS 0.00013882205
1,152 Blink and It's Done: Interactive Queries on Very Large Data 2012 VLDB 0.00013645792
1,193 Join Size Estimation Subject to Filter Conditions 2015 VLDB 0.00013414989
1,425 Scalable Approximate Query Processing With The DBO Engine 2007 SIGMOD 0.00012051353
1,464 Online Aggregation for Large MapReduce Jobs 2011 VLDB 0.00011865546
1,846 Combining User Interaction, Speculative Query Execution and Sampling in the DICE System 2014 VLDB 0.00010335419
1,874 Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems 2014 SIGMOD 0.00010244443
2,011 Rapid Sampling for Visualizations with Ordering Guarantees 2015 VLDB 9.7964875e-05
2,202 A Scalable Hash Ripple Join Algorithm 2002 SIGMOD 9.2987417e-05
2,203 Independent Range Sampling 2014 PODS 9.2981095e-05
2,355 G-OLA: Generalized On-Line Aggregation for Interactive Analysis on Big Data 2015 SIGMOD 8.9677847e-05
2,365 The Analytical Bootstrap: a New Method for Fast Error Estimation in Approximate Query Processing 2014 SIGMOD 8.9551432e-05
2,995 A Sampling Algebra for Aggregate Estimation 2013 VLDB 7.7587199e-05
3,594 Continuous Sampling for Online Aggregation Over Multiple Queries 2010 SIGMOD 6.9381343e-05
3,842 Turbo-Charging Estimate Convergence in DBO 2009 VLDB 6.7102374e-05
4,029 Spatial Online Sampling and Aggregation 2016 VLDB 6.51315e-05
4,093 Distributed Online Aggregations 2009 VLDB 6.4558147e-05
4,506 Stochastic Database Cracking: Towards Robust Adaptive Indexing in Main-Memory Column-Stores 2012 VLDB 6.1319277e-05
5,376 Holistic Indexing in Main-memory Column-stores 2015 SIGMOD 5.5417421e-05
5,817 Derby/S: A DBMS for Sample-Based Query Answering 2006 SIGMOD 5.3156799e-05
5,868 ABS: a System for Scalable Approximate Queries with Accuracy Guarantees 2014 SIGMOD 5.2959352e-05
6,201 Concurrency Control for Adaptive Indexing 2012 VLDB 5.1600319e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
8,680 A Practical Approach to Groupjoin and Nested Aggregates 2021 VLDB 4.4694927e-05
1,369 Random Sampling over Joins Revisited 2018 SIGMOD 0.00012339777
10,324 Towards Efficient Random-Order Enumeration for Join Queries 2026 VLDB 4.1945683e-05
12,191 Efficient Rank Join with Aggregation Constraints 2011 VLDB 4.1945683e-05
2,275 Adopting Worst-Case Optimal Joins in Relational Database Systems 2020 VLDB 9.1262202e-05
2,202 A Scalable Hash Ripple Join Algorithm 2002 SIGMOD 9.2987417e-05
8,205 PR-Join: A Non-Blocking Join Achieving Higher Early Result Rate with Statistical Guarantees 2010 SIGMOD 4.5593375e-05
3,048 Fast, Randomized Join-Order Selection — Why Use Transformations? 1994 VLDB 7.6543116e-05
217 Ripple Joins for Online Aggregation 1999 SIGMOD 0.00033536712
8,689 Wander Join: Online Aggregation for Joins 2016 SIGMOD 4.4667389e-05