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: 3169
Venue: SIGMOD
Year: 1999
Pagerank: 0.00030424509
Overall Rank: 131 | 99.11%
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.00041071971
255	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00023174541
257	The History of Histograms (abridged)	2003	VLDB	0.00023154793
363	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.0002005475
418	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00018812821
509	Supporting Top-k Join Queries in Relational Databases	2003	VLDB	0.00017220967
551	On Computing Correlated Aggregates Over Continual Data Streams	2001	SIGMOD	0.00016635191
553	Congressional Samples for Approximate Answering of Group-By Queries	2000	SIGMOD	0.00016590619
593	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00016027871
772	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00014147905
802	Random Sampling over Joins Revisited	2018	SIGMOD	0.00013907725
817	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00013823702
930	SPARK: Top-k Keyword Query in Relational Databases	2007	SIGMOD	0.0001312728
973	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD	0.00012874284
1,009	Online Aggregation for Large MapReduce Jobs	2011	VLDB	0.00012684342
1,064	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012336248
1,082	A Transducer-Based XML Query Processor	2002	VLDB	0.00012257574
1,108	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012145154
1,143	Toward a Progress Indicator for Database Queries	2004	SIGMOD	0.00011999403
1,478	Online Processing Algorithms for Influence Maximization	2018	SIGMOD	0.00010651983
1,676	Feeding Frenzy: Selectively Materializing Users' Event Feeds	2010	SIGMOD	0.00010034449
1,680	Online Dynamic Reordering for Interactive Data Processing	1999	VLDB	0.00010024295
1,759	Rank-aware Query Optimization	2004	SIGMOD	9.8160244e-05
1,763	Dynamic Pipeline Scheduling for Improving Interactive Query Performance	2001	VLDB	9.8124899e-05
1,785	A Scalable Hash Ripple Join Algorithm	2002	SIGMOD	9.7702627e-05
2,270	When Can We Trust Progress Estimators for SQL Queries?	2005	SIGMOD	8.8310714e-05
2,271	Online Maintenance of Very Large Random Samples	2004	SIGMOD	8.8254873e-05
2,413	A Sampling Algebra for Aggregate Estimation	2013	VLDB	8.6116764e-05
2,633	Relational Confidence Bounds Are Easy With The Bootstrap*	2005	SIGMOD	8.3224527e-05
2,777	Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration	2020	PODS	8.1352657e-05
2,892	Scalable and Adaptive Online Joins	2014	VLDB	7.9852178e-05
2,898	Approximate Selection with Guarantees using Proxies	2020	VLDB	7.978725e-05
2,997	Adapting to Source Properties in Processing Data Integration Queries	2004	SIGMOD	7.8745158e-05
3,042	Continuous Sampling for Online Aggregation Over Multiple Queries	2010	SIGMOD	7.8231049e-05
3,144	Interactive Data Exploration Using Semantic Windows	2014	SIGMOD	7.7134729e-05
3,157	Turbo-Charging Estimate Convergence in DBO	2009	VLDB	7.6911286e-05
3,321	Dynamic Plan Migration for Continuous Queries Over Data Streams	2004	SIGMOD	7.5216049e-05
3,370	Revisiting Reuse for Approximate Query Processing	2017	VLDB	7.4700891e-05
3,453	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	7.4004131e-05
3,532	Scalable Distributed Stream Join Processing	2015	SIGMOD	7.3369085e-05
3,706	Supporting Ad-hoc Ranking Aggregates	2006	SIGMOD	7.1819534e-05
3,741	Spatial Online Sampling and Aggregation	2016	VLDB	7.1586403e-05
3,844	Distributed Online Aggregations	2009	VLDB	7.0782059e-05
4,128	The Relational Data Borg is Learning	2020	VLDB	6.8850804e-05
4,138	A Disk-Based Join With Probabilistic Guarantees*	2005	SIGMOD	6.8779166e-05
4,142	Statistical Analysis of Sketch Estimators	2007	SIGMOD	6.8764637e-05
4,368	Lightweight and Accurate Cardinality Estimation by Neural Network Gaussian Process	2022	SIGMOD	6.7393882e-05
4,596	Static Optimization of Conjunctive Queries with Sliding Windows Over Infinite Streams	2004	SIGMOD	6.6133976e-05
4,630	Efficient Join Synopsis Maintenance for Data Warehouse	2020	SIGMOD	6.5955933e-05
5,142	Online Feedback for Nested Aggregate Queries with Multi-Threading	1999	VLDB	6.3482762e-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.00083340894
9	Online Aggregation	1997	SIGMOD	0.00077458002
55	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00040746149
178	Processing Aggregate Relational Queries with Hard Time Constraints	1989	SIGMOD	0.00026881845
801	Query Execution Techniques for Caching Expensive Methods	1996	SIGMOD	0.00013909408
1,440	On the Relative Cost of Sampling for Join Selectivity Estimation	1994	PODS	0.00010778889
1,680	Online Dynamic Reordering for Interactive Data Processing	1999	VLDB	0.00010024295

Semantically Similar Papers

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