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 18 of 68 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,878	PRICE: A Pretrained Model for Cross-Database Cardinality Estimation	2025	VLDB	4.2656547e-05
9,949	AB-tree: Index for Concurrent Random Sampling and Updates	2022	VLDB	4.2421586e-05
10,096	NeuSO: Neural Optimizer for Subgraph Queries	2026	SIGMOD	4.1945683e-05
10,254	Secure Multi-Party Sampling over Joins	2026	VLDB	4.1945683e-05
10,377	FastPDB: Towards Bag-Probabilistic Queries at Interactive Speeds	2025	SIGMOD	4.1945683e-05
10,481	FAAQP: Fast and Accurate Approximate Query Processing based on Bitmap-augmented Sum-Product Network	2025	SIGMOD	4.1945683e-05
10,632	Efficient and Accurate Subgraph Counting: A Bottom-up Flow-learning Based Approach	2025	VLDB	4.1945683e-05
10,941	PECJ: Stream Window Join on Disorder Data Streams with Proactive Error Compensation	2024	SIGMOD	4.1945683e-05
10,948	gSWORD: GPU-accelerated Sampling for Subgraph Counting	2024	SIGMOD	4.1945683e-05
10,981	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	4.1945683e-05
10,994	Towards a Converged Relational-Graph Optimization Framework	2024	SIGMOD	4.1945683e-05
11,074	Confidence Intervals for Private Query Processing	2024	VLDB	4.1945683e-05
11,194	A Step Toward Deep Online Aggregation	2023	SIGMOD	4.1945683e-05
11,384	BABOONS: Black-Box Optimization of Data Summaries in Natural Language	2022	VLDB	4.1945683e-05
11,514	ATLANTIC: Making Database Differentially Private and Faster with Accuracy Guarantee	2021	VLDB	4.1945683e-05
11,552	BitGourmet: Deterministic Approximation via Optimized Bit Selection	2020	CIDR	4.1945683e-05
11,585	Demonstration of BitGourmet: Data Analysis via Deterministic Approximation	2020	SIGMOD	4.1945683e-05
11,711	Demonstration of VerdictDB, the Platform-Independent AQP System	2018	SIGMOD	4.1945683e-05

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

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