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.00029805026
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.00040739114
254	The History of Histograms (abridged)	2003	VLDB	0.00022999992
268	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00022654182
374	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.00019698889
432	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00018400309
505	Supporting Top-k Join Queries in Relational Databases	2003	VLDB	0.00017162373
564	Congressional Samples for Approximate Answering of Group-By Queries	2000	SIGMOD	0.00016251304
566	On Computing Correlated Aggregates Over Continual Data Streams	2001	SIGMOD	0.00016236872
594	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00015814493
770	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00014086699
793	Random Sampling over Joins Revisited	2018	SIGMOD	0.00013903938
844	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00013498392
941	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD	0.00012938573
947	SPARK: Top-k Keyword Query in Relational Databases	2007	SIGMOD	0.00012910239
1,022	Online Aggregation for Large MapReduce Jobs	2011	VLDB	0.00012400958
1,065	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012181098
1,095	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012036913
1,115	A Transducer-Based XML Query Processor	2002	VLDB	0.00011939087
1,159	Toward a Progress Indicator for Database Queries	2004	SIGMOD	0.00011739527
1,396	Online Processing Algorithms for Influence Maximization	2018	SIGMOD	0.00010774759
1,705	Feeding Frenzy: Selectively Materializing Users' Event Feeds	2010	SIGMOD	9.8056169e-05
1,712	Rank-aware Query Optimization	2004	SIGMOD	9.7961248e-05
1,713	Online Dynamic Reordering for Interactive Data Processing	1999	VLDB	9.7948649e-05
1,809	Dynamic Pipeline Scheduling for Improving Interactive Query Performance	2001	VLDB	9.5834851e-05
1,832	A Scalable Hash Ripple Join Algorithm	2002	SIGMOD	9.5365548e-05
2,329	When Can We Trust Progress Estimators for SQL Queries?	2005	SIGMOD	8.6188984e-05
2,335	Online Maintenance of Very Large Random Samples	2004	SIGMOD	8.6050778e-05
2,461	A Sampling Algebra for Aggregate Estimation	2013	VLDB	8.4123214e-05
2,682	Relational Confidence Bounds Are Easy With The Bootstrap*	2005	SIGMOD	8.1203255e-05
2,766	Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration	2020	PODS	8.0221503e-05
2,777	Approximate Selection with Guarantees using Proxies	2020	VLDB	8.0101016e-05
2,972	Scalable and Adaptive Online Joins	2014	VLDB	7.7844791e-05
3,001	Adapting to Source Properties in Processing Data Integration Queries	2004	SIGMOD	7.7492907e-05
3,092	Continuous Sampling for Online Aggregation Over Multiple Queries	2010	SIGMOD	7.638249e-05
3,213	Interactive Data Exploration Using Semantic Windows	2014	SIGMOD	7.5144638e-05
3,220	Turbo-Charging Estimate Convergence in DBO	2009	VLDB	7.5077984e-05
3,380	Dynamic Plan Migration for Continuous Queries Over Data Streams	2004	SIGMOD	7.3415892e-05
3,428	Revisiting Reuse for Approximate Query Processing	2017	VLDB	7.2957009e-05
3,502	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	7.2308675e-05
3,610	Scalable Distributed Stream Join Processing	2015	SIGMOD	7.1463915e-05
3,793	Supporting Ad-hoc Ranking Aggregates	2006	SIGMOD	6.9967739e-05
3,825	Spatial Online Sampling and Aggregation	2016	VLDB	6.9795872e-05
3,912	Distributed Online Aggregations	2009	VLDB	6.9103187e-05
3,931	Statistical Analysis of Sketch Estimators	2007	SIGMOD	6.900756e-05
4,174	The Relational Data Borg is Learning	2020	VLDB	6.750725e-05
4,236	A Disk-Based Join With Probabilistic Guarantees*	2005	SIGMOD	6.7028998e-05
4,479	Lightweight and Accurate Cardinality Estimation by Neural Network Gaussian Process	2022	SIGMOD	6.5665703e-05
4,661	Efficient Join Synopsis Maintenance for Data Warehouse	2020	SIGMOD	6.4656621e-05
4,708	Static Optimization of Conjunctive Queries with Sliding Windows Over Infinite Streams	2004	SIGMOD	6.4419838e-05
5,206	QuERy: A Framework for Integrating Entity Resolution with Query Processing	2016	VLDB	6.2160113e-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.00081781676
9	Online Aggregation	1997	SIGMOD	0.00076079812
58	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00039922419
183	Processing Aggregate Relational Queries with Hard Time Constraints	1989	SIGMOD	0.00026316699
822	Query Execution Techniques for Caching Expensive Methods	1996	SIGMOD	0.00013616674
1,469	On the Relative Cost of Sampling for Join Selectivity Estimation	1994	PODS	0.00010533259
1,713	Online Dynamic Reordering for Interactive Data Processing	1999	VLDB	9.7948649e-05

Semantically Similar Papers

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