Database Paper Browser

Back to papers

Ripple Joins for Online Aggregation

Summary: Ripple joins: online-aggregation join family for multi-table queries; incremental estimates with confidence intervals, not exact answers. Adaptive, data-driven, with tunable tradeoffs between update cadence and CI shrink; iterator-based Postgres implementation; up to two orders of magnitude faster online estimates than offline joins. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
3108
Venue
SIGMOD
Year
1999
Pagerank
0.00033560137
Overall Rank
216 | 98.51%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 84 citing papers.

Rank Citing Paper Year Venue Pagerank
116 Eddies: Continuously Adaptive Query Processing 2000 SIGMOD 0.00046191288
316 Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports 2001 VLDB 0.00027981848
325 The History of Histograms (abridged) 2003 VLDB 0.00027398081
430 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.00023406426
550 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.00020346247
617 On Computing Correlated Aggregates Over Continual Data Streams 2001 SIGMOD 0.00019048986
673 Supporting Top-k Join Queries in Relational Databases 2003 VLDB 0.00018325667
736 Congressional Samples for Approximate Answering of Group-By Queries 2000 SIGMOD 0.00017414831
941 Wander Join: Online Aggregation via Random Walks 2016 SIGMOD 0.00015147831
1,065 Processing Complex Aggregate Queries over Data Streams 2002 SIGMOD 0.00014344675
1,123 A Transducer-Based XML Query Processor 2002 VLDB 0.00013836955
1,139 Feeding Frenzy: Selectively Materializing Users' Event Feeds 2010 SIGMOD 0.0001371195
1,161 VerdictDB: Universalizing Approximate Query Processing 2018 SIGMOD 0.00013579831
1,202 SPARK: Top-k Keyword Query in Relational Databases 2007 SIGMOD 0.0001333126
1,207 RankSQL: Query Algebra and Optimization for Relational Top-k Queries 2005 SIGMOD 0.0001327437
1,229 Toward a Progress Indicator for Database Queries 2004 SIGMOD 0.00013153898
1,372 Random Sampling over Joins Revisited 2018 SIGMOD 0.0001233325
1,425 Scalable Approximate Query Processing With The DBO Engine 2007 SIGMOD 0.00012044433
1,451 Online Aggregation for Large MapReduce Jobs 2011 VLDB 0.00011925842
1,531 Online Dynamic Reordering for Interactive Data Processing 1999 VLDB 0.00011467334
1,574 Approximate Query Processing: No Silver Bullet 2017 SIGMOD 0.00011289028
1,798 Online Processing Algorithms for Influence Maximization 2018 SIGMOD 0.00010500792
1,917 Dynamic Pipeline Scheduling for Improving Interactive Query Performance 2001 VLDB 0.00010104953
2,113 When Can We Trust Progress Estimators for SQL Queries? 2005 SIGMOD 9.5207583e-05
2,208 A Scalable Hash Ripple Join Algorithm 2002 SIGMOD 9.2887018e-05
2,249 Rank-aware Query Optimization 2004 SIGMOD 9.1956569e-05
2,377 Online Maintenance of Very Large Random Samples 2004 SIGMOD 8.9359321e-05
2,995 A Sampling Algebra for Aggregate Estimation 2013 VLDB 7.7606324e-05
3,133 Relational Confidence Bounds Are Easy With The Bootstrap* 2005 SIGMOD 7.4979168e-05
3,331 Adapting to Source Properties in Processing Data Integration Queries 2004 SIGMOD 7.2094696e-05
3,384 Scalable and Adaptive Online Joins 2014 VLDB 7.153329e-05
3,386 Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration 2020 PODS 7.151562e-05
3,441 Interactive Data Exploration Using Semantic Windows 2014 SIGMOD 7.0891447e-05
3,553 Approximate Selection with Guarantees using Proxies 2020 VLDB 6.9763548e-05
3,596 Continuous Sampling for Online Aggregation Over Multiple Queries 2010 SIGMOD 6.9342283e-05
3,770 Dynamic Plan Migration for Continuous Queries Over Data Streams 2004 SIGMOD 6.7743365e-05
3,808 Turbo-Charging Estimate Convergence in DBO 2009 VLDB 6.7416988e-05
3,809 Supporting Ad-hoc Ranking Aggregates 2006 SIGMOD 6.7413981e-05
4,020 Revisiting Reuse for Approximate Query Processing 2017 VLDB 6.5209063e-05
4,032 Spatial Online Sampling and Aggregation 2016 VLDB 6.5131946e-05
4,083 Distributed Online Aggregations 2009 VLDB 6.4583812e-05
4,161 Scalable Distributed Stream Join Processing 2015 SIGMOD 6.3883784e-05
4,239 Statistical Analysis of Sketch Estimators 2007 SIGMOD 6.3273184e-05
4,244 A Disk-Based Join With Probabilistic Guarantees* 2005 SIGMOD 6.3228453e-05
4,431 Lightweight and Accurate Cardinality Estimation by Neural Network Gaussian Process 2022 SIGMOD 6.1870601e-05
4,787 The Relational Data Borg is Learning 2020 VLDB 5.9168117e-05
4,902 Online Feedback for Nested Aggregate Queries with Multi-Threading 1999 VLDB 5.8415033e-05
4,926 On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms 2023 PODS 5.8184457e-05
4,934 Static Optimization of Conjunctive Queries with Sliding Windows Over Infinite Streams 2004 SIGMOD 5.815192e-05
5,128 Efficient Join Synopsis Maintenance for Data Warehouse 2020 SIGMOD 5.6728511e-05
Previous Page 1 / 2 Next

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 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 Implementation Techniques For Main Memory Database Systems 1984 SIGMOD 0.001426258
14 Online Aggregation 1997 SIGMOD 0.0010813443
37 Statistical Estimators for Relational Algebra Expressions 1988 PODS 0.00075597514
133 Processing Aggregate Relational Queries with Hard Time Constraints 1989 SIGMOD 0.00043220055
699 Query Execution Techniques for Caching Expensive Methods 1996 SIGMOD 0.0001794078
803 On the Relative Cost of Sampling for Join Selectivity Estimation 1994 PODS 0.00016438972
1,531 Online Dynamic Reordering for Interactive Data Processing 1999 VLDB 0.00011467334
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
673 Supporting Top-k Join Queries in Relational Databases 2003 VLDB 0.00018325667
1,675 Adaptive Parallel Aggregation Algorithms 1995 SIGMOD 0.00010937908
12,199 Efficient Rank Join with Aggregation Constraints 2011 VLDB 4.1905499e-05
1,712 Approximate Join Processing Over Data Streams 2003 SIGMOD 0.00010786152
14 Online Aggregation 1997 SIGMOD 0.0010813443
4,244 A Disk-Based Join With Probabilistic Guarantees* 2005 SIGMOD 6.3228453e-05
8,685 Wander Join: Online Aggregation for Joins 2016 SIGMOD 4.4624568e-05
941 Wander Join: Online Aggregation via Random Walks 2016 SIGMOD 0.00015147831
8,993 PR-Join: A Non-Blocking Join Achieving Higher Early Result Rate with Statistical Guarantees 2010 SIGMOD 4.4105266e-05
2,208 A Scalable Hash Ripple Join Algorithm 2002 SIGMOD 9.2887018e-05