Efficient Incrementialization of Correlated Nested Aggregate Queries using Relative Partial Aggregate Indexes (RPAI)

Summary: Introduces Relative Partial Aggregate Indexes (RPAI) for incrementalizing correlated nested-aggregate queries in streaming, latency-critical settings. Shows asymptotic improvement with up to 1100x speedups vs. prior IVM approaches (e.g., DBToaster). (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h75cb351d3d3d9f81
Venue: SIGMOD
Year: 2022
Pagerank: 5.3118554e-05
Overall Rank: 8,567 | 42.43%
DOI: 10.1145/3514221.3517889
PDF: Download (CC BY 4.0)

Incoming Non-self Citations Over Time

Authors

1. Supun Abeysinghe (Purdue University)
2. Qiyang He (Purdue University)
3. Tiark Rompf (Purdue University)

BibTeX Citation

@inproceedings{abeysinghe_sigmod22,
        title = {{Efficient Incrementialization of Correlated Nested Aggregate Queries using Relative Partial Aggregate Indexes (RPAI)}},
        author = {Abeysinghe, Supun and He, Qiyang and Rompf, Tiark},
        series = {{SIGMOD} '22},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3514221.3517889},
        url = {https://dl.acm.org/doi/10.1145/3514221.3517889},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,675	DBSP: Automatic Incremental View Maintenance for Rich Query Languages	2023	VLDB	7.1058941e-05
7,533	Foreign Keys Open the Door for Faster Incremental View Maintenance	2023	SIGMOD	5.4991257e-05

Outgoing Citations (Sorted by Pagerank)

Showing 24 of 24 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
62	Maintaining Views Incrementally	1993	SIGMOD	0.00039040346
218	MillWheel: Fault-Tolerant Stream Processing at Internet Scale	2013	VLDB	0.00024379041
388	Incremental Maintenance of Views with Duplicates	1995	SIGMOD	0.00019342096
408	DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views	2012	VLDB	0.00018894165
442	Differential dataflow	2013	CIDR	0.00018201988
552	Orthogonal Optimization of Subqueries and Aggregation	2001	SIGMOD	0.00016530708
813	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.00013722638
977	Incremental Query Evaluation in a Ring of Databases	2010	PODS	0.00012730241
1,149	Algorithms for Deferred View Maintenance	1996	SIGMOD	0.00011804215
1,780	Lazy Maintenance of Materialized Views	2007	VLDB	9.654014e-05
2,420	How to Architect a Query Compiler, Revisited	2018	SIGMOD	8.4883426e-05
3,128	How to Win a Hot Dog Eating Contest: Distributed Incremental View Maintenance with Batch Updates	2016	SIGMOD	7.611678e-05
4,402	Shared Arrangements: practical inter-query sharing for streaming dataflows	2020	VLDB	6.6120647e-05
5,147	Conjunctive Queries with Inequalities Under Updates	2018	VLDB	6.2536517e-05
6,220	iOLAP: Managing Uncertainty for Efficient Incremental OLAP	2016	SIGMOD	5.8447948e-05
6,389	Maintaining Acyclic Foreign-Key Joins under Updates	2020	SIGMOD	5.8014043e-05
6,601	AStream: Ad-hoc Shared Stream Processing	2019	SIGMOD	5.737728e-05
6,710	Tempura: A General Cost-Based Optimizer Framework for Incremental Data Processing	2021	VLDB	5.7022785e-05
6,801	Intermittent Query Processing	2019	VLDB	5.6776677e-05
7,728	Resource-efficient Shared Query Execution via Exploiting Time Slackness	2021	SIGMOD	5.4649863e-05
7,780	DBToaster: Agile Views in a Dynamic Data Management System	2011	CIDR	5.4528185e-05
8,019	AJoin: Ad-hoc Stream Joins at Scale	2020	VLDB	5.4045347e-05
8,137	Thrifty Query Execution via Incrementability	2020	SIGMOD	5.391109e-05
9,701	Grosbeak: A Data Warehouse Supporting Resource-Aware Incremental Computing	2020	SIGMOD	5.1372006e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,023	A Nested Relational Approach to Processing SQL Subqueries	2005	SIGMOD
2	6,223	Incremental View Maintenance For Collection Programming	2016	PODS
3	977	Incremental Query Evaluation in a Ring of Databases	2010	PODS
4	8,137	Thrifty Query Execution via Incrementability	2020	SIGMOD
5	10,555	Approximate Query Processing under Updates	2026	SIGMOD
6	10,894	Storing and Indexing Multiple Tables by Interesting Orderings: For Efficient Joins, Groupings, and Updates in Relational Databases	2026	VLDB
7	5,663	Enabling Incremental Query Re-Optimization	2016	SIGMOD
8	11,771	Asymptotically Better Query Optimization Using Indexed Algebra	2023	VLDB
9	3,874	DBToaster: A SQL Compiler for High-Performance Delta Processing in Main-Memory Databases	2009	VLDB
10	5,275	Efficient Approximation of Optimization Queries Under Parametric Aggregation Constraints	2003	VLDB