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.00029866033
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.00040860054
255	The History of Histograms (abridged)	2003	VLDB	0.00022981861
267	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00022722971
372	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.00019720059
428	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.0001845349
524	Supporting Top-k Join Queries in Relational Databases	2003	VLDB	0.00016909926
564	Congressional Samples for Approximate Answering of Group-By Queries	2000	SIGMOD	0.00016296665
566	On Computing Correlated Aggregates Over Continual Data Streams	2001	SIGMOD	0.00016295476
596	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00015785583
784	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00014012614
795	Random Sampling over Joins Revisited	2018	SIGMOD	0.00013938779
842	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00013540697
942	SPARK: Top-k Keyword Query in Relational Databases	2007	SIGMOD	0.00012956137
961	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD	0.0001282305
1,022	Online Aggregation for Large MapReduce Jobs	2011	VLDB	0.00012438826
1,082	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012122749
1,090	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012077577
1,111	A Transducer-Based XML Query Processor	2002	VLDB	0.00011984202
1,159	Toward a Progress Indicator for Database Queries	2004	SIGMOD	0.00011771949
1,474	Online Processing Algorithms for Influence Maximization	2018	SIGMOD	0.00010556999
1,701	Feeding Frenzy: Selectively Materializing Users' Event Feeds	2010	SIGMOD	9.8371359e-05
1,703	Online Dynamic Reordering for Interactive Data Processing	1999	VLDB	9.8315219e-05
1,773	Rank-aware Query Optimization	2004	SIGMOD	9.6719067e-05
1,796	Dynamic Pipeline Scheduling for Improving Interactive Query Performance	2001	VLDB	9.6193021e-05
1,820	A Scalable Hash Ripple Join Algorithm	2002	SIGMOD	9.5690887e-05
2,318	When Can We Trust Progress Estimators for SQL Queries?	2005	SIGMOD	8.6464837e-05
2,322	Online Maintenance of Very Large Random Samples	2004	SIGMOD	8.6361485e-05
2,456	A Sampling Algebra for Aggregate Estimation	2013	VLDB	8.4377192e-05
2,677	Relational Confidence Bounds Are Easy With The Bootstrap*	2005	SIGMOD	8.1461074e-05
2,757	Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration	2020	PODS	8.0525756e-05
2,776	Approximate Selection with Guarantees using Proxies	2020	VLDB	8.0309448e-05
2,953	Scalable and Adaptive Online Joins	2014	VLDB	7.8137255e-05
2,987	Adapting to Source Properties in Processing Data Integration Queries	2004	SIGMOD	7.7773398e-05
3,087	Continuous Sampling for Online Aggregation Over Multiple Queries	2010	SIGMOD	7.6624333e-05
3,201	Interactive Data Exploration Using Semantic Windows	2014	SIGMOD	7.5428462e-05
3,213	Turbo-Charging Estimate Convergence in DBO	2009	VLDB	7.5328015e-05
3,371	Dynamic Plan Migration for Continuous Queries Over Data Streams	2004	SIGMOD	7.3693585e-05
3,419	Revisiting Reuse for Approximate Query Processing	2017	VLDB	7.3190065e-05
3,494	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	7.2582926e-05
3,603	Scalable Distributed Stream Join Processing	2015	SIGMOD	7.173496e-05
3,782	Supporting Ad-hoc Ranking Aggregates	2006	SIGMOD	7.0230959e-05
3,818	Spatial Online Sampling and Aggregation	2016	VLDB	7.0060535e-05
3,905	Distributed Online Aggregations	2009	VLDB	6.9335334e-05
3,927	Statistical Analysis of Sketch Estimators	2007	SIGMOD	6.9192361e-05
4,161	The Relational Data Borg is Learning	2020	VLDB	6.7700593e-05
4,217	A Disk-Based Join With Probabilistic Guarantees*	2005	SIGMOD	6.7271293e-05
4,457	Lightweight and Accurate Cardinality Estimation by Neural Network Gaussian Process	2022	SIGMOD	6.5913732e-05
4,642	Efficient Join Synopsis Maintenance for Data Warehouse	2020	SIGMOD	6.4898745e-05
4,693	Static Optimization of Conjunctive Queries with Sliding Windows Over Infinite Streams	2004	SIGMOD	6.4662079e-05
5,198	QuERy: A Framework for Integrating Entity Resolution with Query Processing	2016	VLDB	6.2338998e-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.00081992507
9	Online Aggregation	1997	SIGMOD	0.00076195956
58	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00040035279
181	Processing Aggregate Relational Queries with Hard Time Constraints	1989	SIGMOD	0.00026389403
821	Query Execution Techniques for Caching Expensive Methods	1996	SIGMOD	0.00013660347
1,467	On the Relative Cost of Sampling for Join Selectivity Estimation	1994	PODS	0.00010567959
1,703	Online Dynamic Reordering for Interactive Data Processing	1999	VLDB	9.8315219e-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,677	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,217	A Disk-Based Join With Probabilistic Guarantees*	2005	SIGMOD
7	8,216	Wander Join: Online Aggregation for Joins	2016	SIGMOD
8	596	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD
9	9,184	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