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: h24f3ab9175eae0e1
Venue: SIGMOD
Year: 1999
Pagerank: 0.00029858107
Overall Rank: 135 | 99.10%
DOI: 10.1145/304182.304208

Incoming Non-self Citations Over Time

Authors

1. Peter J. Haas (IBM)
2. Joseph M. Hellerstein (University of California Berkeley)

BibTeX Citation

@inproceedings{haas_sigmod99,
        title = {{Ripple Joins for Online Aggregation}},
        author = {Haas, Peter J. and Hellerstein, Joseph M.},
        series = {{SIGMOD} '99},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/304182.304208},
        url = {https://dl.acm.org/doi/10.1145/304182.304208},
        year = {1999}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 88 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
53	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.000408505
255	The History of Histograms (abridged)	2003	VLDB	0.00022974524
267	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00022713652
372	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.0001971778
429	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00018445263
524	Supporting Top-k Join Queries in Relational Databases	2003	VLDB	0.00016902116
564	Congressional Samples for Approximate Answering of Group-By Queries	2000	SIGMOD	0.00016297598
566	On Computing Correlated Aggregates Over Continual Data Streams	2001	SIGMOD	0.00016288241
596	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00015782051
772	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.0001409096
795	Random Sampling over Joins Revisited	2018	SIGMOD	0.00013934719
843	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00013534623
942	SPARK: Top-k Keyword Query in Relational Databases	2007	SIGMOD	0.00012950177
962	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD	0.00012818013
1,021	Online Aggregation for Large MapReduce Jobs	2011	VLDB	0.00012437619
1,061	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012208639
1,090	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012074369
1,111	A Transducer-Based XML Query Processor	2002	VLDB	0.00011978534
1,158	Toward a Progress Indicator for Database Queries	2004	SIGMOD	0.00011767292
1,474	Online Processing Algorithms for Influence Maximization	2018	SIGMOD	0.00010552001
1,701	Feeding Frenzy: Selectively Materializing Users' Event Feeds	2010	SIGMOD	9.8324792e-05
1,703	Online Dynamic Reordering for Interactive Data Processing	1999	VLDB	9.8269486e-05
1,773	Rank-aware Query Optimization	2004	SIGMOD	9.6683429e-05
1,796	Dynamic Pipeline Scheduling for Improving Interactive Query Performance	2001	VLDB	9.6147923e-05
1,820	A Scalable Hash Ripple Join Algorithm	2002	SIGMOD	9.5651265e-05
2,320	When Can We Trust Progress Estimators for SQL Queries?	2005	SIGMOD	8.6429103e-05
2,324	Online Maintenance of Very Large Random Samples	2004	SIGMOD	8.6332031e-05
2,455	A Sampling Algebra for Aggregate Estimation	2013	VLDB	8.4377251e-05
2,672	Relational Confidence Bounds Are Easy With The Bootstrap*	2005	SIGMOD	8.1456115e-05
2,757	Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration	2020	PODS	8.0487636e-05
2,773	Approximate Selection with Guarantees using Proxies	2020	VLDB	8.0318294e-05
2,956	Scalable and Adaptive Online Joins	2014	VLDB	7.8100535e-05
2,989	Adapting to Source Properties in Processing Data Integration Queries	2004	SIGMOD	7.7736772e-05
3,085	Continuous Sampling for Online Aggregation Over Multiple Queries	2010	SIGMOD	7.6607519e-05
3,203	Interactive Data Exploration Using Semantic Windows	2014	SIGMOD	7.5392994e-05
3,213	Turbo-Charging Estimate Convergence in DBO	2009	VLDB	7.5304969e-05
3,371	Dynamic Plan Migration for Continuous Queries Over Data Streams	2004	SIGMOD	7.3659127e-05
3,417	Revisiting Reuse for Approximate Query Processing	2017	VLDB	7.3184905e-05
3,494	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	7.2548566e-05
3,603	Scalable Distributed Stream Join Processing	2015	SIGMOD	7.1701004e-05
3,784	Supporting Ad-hoc Ranking Aggregates	2006	SIGMOD	7.0197908e-05
3,819	Spatial Online Sampling and Aggregation	2016	VLDB	7.0027383e-05
3,904	Distributed Online Aggregations	2009	VLDB	6.9307047e-05
3,928	Statistical Analysis of Sketch Estimators	2007	SIGMOD	6.9160175e-05
4,161	The Relational Data Borg is Learning	2020	VLDB	6.7669004e-05
4,218	A Disk-Based Join With Probabilistic Guarantees*	2005	SIGMOD	6.7242128e-05
4,459	Lightweight and Accurate Cardinality Estimation by Neural Network Gaussian Process	2022	SIGMOD	6.5883555e-05
4,644	Efficient Join Synopsis Maintenance for Data Warehouse	2020	SIGMOD	6.4869417e-05
4,695	Static Optimization of Conjunctive Queries with Sliding Windows Over Infinite Streams	2004	SIGMOD	6.4632424e-05
5,199	QuERy: A Framework for Integrating Entity Resolution with Query Processing	2016	VLDB	6.2309669e-05

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
7	Implementation Techniques For Main Memory Database Systems	1984	SIGMOD	0.00081971778
9	Online Aggregation	1997	SIGMOD	0.00076265429
58	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00040025054
181	Processing Aggregate Relational Queries with Hard Time Constraints	1989	SIGMOD	0.00026384065
821	Query Execution Techniques for Caching Expensive Methods	1996	SIGMOD	0.00013655214
1,467	On the Relative Cost of Sampling for Join Selectivity Estimation	1994	PODS	0.00010563809
1,703	Online Dynamic Reordering for Interactive Data Processing	1999	VLDB	9.8269486e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	524	Supporting Top-k Join Queries in Relational Databases	2003	VLDB
2	1,628	Adaptive Parallel Aggregation Algorithms	1995	SIGMOD
3	12,683	Efficient Rank Join with Aggregation Constraints	2011	VLDB
4	1,431	Approximate Join Processing Over Data Streams	2003	SIGMOD
5	9	Online Aggregation	1997	SIGMOD
6	4,218	A Disk-Based Join With Probabilistic Guarantees*	2005	SIGMOD
7	8,223	Wander Join: Online Aggregation for Joins	2016	SIGMOD
8	596	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD
9	9,194	PR-Join: A Non-Blocking Join Achieving Higher Early Result Rate with Statistical Guarantees	2010	SIGMOD
10	1,820	A Scalable Hash Ripple Join Algorithm	2002	SIGMOD