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
3107
Venue
SIGMOD
Year
1999
Pagerank
0.00033536712
Overall Rank
217 | 98.50%
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
115 Eddies: Continuously Adaptive Query Processing 2000 SIGMOD 0.00046221215
308 Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports 2001 VLDB 0.00028142852
325 The History of Histograms (abridged) 2003 VLDB 0.00027378328
449 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.00022846068
549 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.00020376603
619 On Computing Correlated Aggregates Over Continual Data Streams 2001 SIGMOD 0.00019066583
674 Supporting Top-k Join Queries in Relational Databases 2003 VLDB 0.00018327585
739 Congressional Samples for Approximate Answering of Group-By Queries 2000 SIGMOD 0.00017401518
943 Wander Join: Online Aggregation via Random Walks 2016 SIGMOD 0.00015145883
1,064 Processing Complex Aggregate Queries over Data Streams 2002 SIGMOD 0.00014356481
1,123 A Transducer-Based XML Query Processor 2002 VLDB 0.00013849322
1,139 Feeding Frenzy: Selectively Materializing Users' Event Feeds 2010 SIGMOD 0.00013725337
1,201 SPARK: Top-k Keyword Query in Relational Databases 2007 SIGMOD 0.0001334371
1,204 VerdictDB: Universalizing Approximate Query Processing 2018 SIGMOD 0.00013319541
1,228 Toward a Progress Indicator for Database Queries 2004 SIGMOD 0.00013164884
1,262 RankSQL: Query Algebra and Optimization for Relational Top-k Queries 2005 SIGMOD 0.00012986539
1,369 Random Sampling over Joins Revisited 2018 SIGMOD 0.00012339777
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,531 Online Dynamic Reordering for Interactive Data Processing 1999 VLDB 0.00011482597
1,574 Approximate Query Processing: No Silver Bullet 2017 SIGMOD 0.00011287495
1,801 Online Processing Algorithms for Influence Maximization 2018 SIGMOD 0.00010510943
1,912 Dynamic Pipeline Scheduling for Improving Interactive Query Performance 2001 VLDB 0.00010118187
2,111 When Can We Trust Progress Estimators for SQL Queries? 2005 SIGMOD 9.5286436e-05
2,202 A Scalable Hash Ripple Join Algorithm 2002 SIGMOD 9.2987417e-05
2,368 Online Maintenance of Very Large Random Samples 2004 SIGMOD 8.9501526e-05
2,393 Rank-aware Query Optimization 2004 SIGMOD 8.9016542e-05
2,995 A Sampling Algebra for Aggregate Estimation 2013 VLDB 7.7587199e-05
3,167 Relational Confidence Bounds Are Easy With The Bootstrap* 2005 SIGMOD 7.4523397e-05
3,330 Adapting to Source Properties in Processing Data Integration Queries 2004 SIGMOD 7.2150831e-05
3,382 Scalable and Adaptive Online Joins 2014 VLDB 7.1597145e-05
3,387 Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration 2020 PODS 7.1573735e-05
3,441 Interactive Data Exploration Using Semantic Windows 2014 SIGMOD 7.0914601e-05
3,558 Approximate Selection with Guarantees using Proxies 2020 VLDB 6.9765724e-05
3,594 Continuous Sampling for Online Aggregation Over Multiple Queries 2010 SIGMOD 6.9381343e-05
3,761 Dynamic Plan Migration for Continuous Queries Over Data Streams 2004 SIGMOD 6.7804871e-05
3,807 Supporting Ad-hoc Ranking Aggregates 2006 SIGMOD 6.747576e-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,030 Revisiting Reuse for Approximate Query Processing 2017 VLDB 6.5129665e-05
4,093 Distributed Online Aggregations 2009 VLDB 6.4558147e-05
4,167 Scalable Distributed Stream Join Processing 2015 SIGMOD 6.3919506e-05
4,237 Statistical Analysis of Sketch Estimators 2007 SIGMOD 6.3333486e-05
4,245 A Disk-Based Join With Probabilistic Guarantees* 2005 SIGMOD 6.3272687e-05
4,434 Lightweight and Accurate Cardinality Estimation by Neural Network Gaussian Process 2022 SIGMOD 6.1929999e-05
4,787 The Relational Data Borg is Learning 2020 VLDB 5.9224501e-05
4,896 Online Feedback for Nested Aggregate Queries with Multi-Threading 1999 VLDB 5.8469503e-05
4,930 Static Optimization of Conjunctive Queries with Sliding Windows Over Infinite Streams 2004 SIGMOD 5.8213082e-05
4,953 On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms 2023 PODS 5.8085795e-05
5,150 Efficient Join Synopsis Maintenance for Data Warehouse 2020 SIGMOD 5.6626586e-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.0014279444
14 Online Aggregation 1997 SIGMOD 0.0010801504
39 Statistical Estimators for Relational Algebra Expressions 1988 PODS 0.00074745564
134 Processing Aggregate Relational Queries with Hard Time Constraints 1989 SIGMOD 0.00042452811
703 Query Execution Techniques for Caching Expensive Methods 1996 SIGMOD 0.00017916705
811 On the Relative Cost of Sampling for Join Selectivity Estimation 1994 PODS 0.00016425612
1,531 Online Dynamic Reordering for Interactive Data Processing 1999 VLDB 0.00011482597
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
674 Supporting Top-k Join Queries in Relational Databases 2003 VLDB 0.00018327585
1,674 Adaptive Parallel Aggregation Algorithms 1995 SIGMOD 0.0001094787
12,191 Efficient Rank Join with Aggregation Constraints 2011 VLDB 4.1945683e-05
1,717 Approximate Join Processing Over Data Streams 2003 SIGMOD 0.00010793312
14 Online Aggregation 1997 SIGMOD 0.0010801504
4,245 A Disk-Based Join With Probabilistic Guarantees* 2005 SIGMOD 6.3272687e-05
8,689 Wander Join: Online Aggregation for Joins 2016 SIGMOD 4.4667389e-05
943 Wander Join: Online Aggregation via Random Walks 2016 SIGMOD 0.00015145883
8,205 PR-Join: A Non-Blocking Join Achieving Higher Early Result Rate with Statistical Guarantees 2010 SIGMOD 4.5593375e-05
2,202 A Scalable Hash Ripple Join Algorithm 2002 SIGMOD 9.2987417e-05