Thrifty Query Execution via Incrementability

Summary: Proposes incrementability, a metric to gauge cost-effective incremental view maintenance for queries amid streaming data. Introduces InQP with decomposed control and a cost-model; Spark prototype shows reduced resource use with latency comparable to IVM. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hf9d2c744487ef72b
Venue: SIGMOD
Year: 2020
Pagerank: 5.3936608e-05
Overall Rank: 8,131 | 45.34%
DOI: 10.1145/3318464.3389756

Incoming Non-self Citations Over Time

Authors

1. Dixin Tang (University of Chicago)
2. Zechao Shang (University of Chicago)
3. Aaron J. Elmore (University of Chicago)
4. Sanjay Krishnan (University of Chicago)
5. Michael J. Franklin (University of Chicago)

BibTeX Citation

@inproceedings{tang_sigmod20,
        title = {{Thrifty Query Execution via Incrementability}},
        author = {Tang, Dixin and Shang, Zechao and Elmore, Aaron J. and Krishnan, Sanjay and Franklin, Michael J.},
        series = {{SIGMOD} '20},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3318464.3389756},
        url = {https://dl.acm.org/doi/10.1145/3318464.3389756},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,722	Resource-efficient Shared Query Execution via Exploiting Time Slackness	2021	SIGMOD	5.467573e-05
8,560	Efficient Incrementialization of Correlated Nested Aggregate Queries using Relative Partial Aggregate Indexes (RPAI)	2022	SIGMOD	5.3142933e-05
9,064	A Design Space Exploration and Evaluation for Main-Memory Hash Joins in Storage Class Memory	2023	VLDB	5.2283159e-05
9,320	CrocodileDB in Action: Resource-Efficient Query Execution by Exploiting Time Slackness	2020	VLDB	5.1946265e-05
10,169	Transactional Panorama: A Conceptual Framework for User Perception in Analytical Visual Interfaces	2023	VLDB	5.0682654e-05
11,248	Agamotto: Scheduling of Deadline-Oriented Incremental Query Execution under Uncertain Resource Price	2025	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 32 of 32 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0023947656
9	Online Aggregation	1997	SIGMOD	0.00076195956
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061066921
25	NiagaraCQ: A Scalable Continuous Query System for Internet Databases	2000	SIGMOD	0.00053930011
39	Efficiently Updating Materialized Views	1986	SIGMOD	0.00046602544
62	Maintaining Views Incrementally	1993	SIGMOD	0.00039045511
98	LEO - DB2's LEarning Optimizer	2001	VLDB	0.00034106982
112	TelegraphCQ: Continuous Dataflow Processing for an Uncertain World	2003	CIDR	0.00032459277
145	Neo: A Learned Query Optimizer	2019	VLDB	0.0002908188
388	Incremental Maintenance of Views with Duplicates	1995	SIGMOD	0.00019350381
397	R* Optimizer Validation and Performance Evaluation for Local Queries	1986	SIGMOD	0.00019157058
408	DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views	2012	VLDB	0.00018900199
685	Trill: A High-Performance Incremental Query Processor for Diverse Analytics	2015	VLDB	0.00014782777
688	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR	0.00014753664
812	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.00013729015
1,030	Rate-Based Query Optimization for Streaming Information Sources	2002	SIGMOD	0.00012407749
1,047	Chain: Operator Scheduling for Memory Minimization in Data Stream Systems	2003	SIGMOD	0.00012308922
1,108	Maximizing the Output Rate of Multi-Way Join Queries over Streaming Information Sources	2003	VLDB	0.00011991195
1,150	Algorithms for Deferred View Maintenance	1996	SIGMOD	0.00011809311
1,160	P-Store: An Elastic Database System with Predictive Provisioning	2018	SIGMOD	0.00011769228
1,465	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	0.00010576304
1,779	Lazy Maintenance of Materialized Views	2007	VLDB	9.6583009e-05
2,172	A Black-Box Approach to Query Cardinality Estimation	2007	CIDR	8.9214171e-05
2,500	Operator Scheduling in a Data Stream Manager	2003	VLDB	8.3809217e-05
2,801	Supporting Multiple View Maintenance Policies	1997	SIGMOD	7.9914879e-05
3,128	How to Win a Hot Dog Eating Contest: Distributed Incremental View Maintenance with Batch Updates	2016	SIGMOD	7.6151967e-05
4,693	Static Optimization of Conjunctive Queries with Sliding Windows Over Infinite Streams	2004	SIGMOD	6.4662079e-05
5,199	Exact Cardinality Query Optimization with Bounded Execution Cost	2019	SIGMOD	6.2327836e-05
6,030	RPJ: Producing Fast Join Results on Streams through Rate-based Optimization	2005	SIGMOD	5.9105381e-05
6,227	iOLAP: Managing Uncertainty for Efficient Incremental OLAP	2016	SIGMOD	5.8452386e-05
6,796	Intermittent Query Processing	2019	VLDB	5.6803529e-05
6,880	Estimating the Impact of Unknown Unknowns on Aggregate Query Results	2016	SIGMOD	5.6573214e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,542	High-Performance Query Processing with NVMe Arrays: Spilling without Killing Performance	2024	SIGMOD
2	7,722	Resource-efficient Shared Query Execution via Exploiting Time Slackness	2021	SIGMOD
3	7,487	Non-Invasive Progressive Optimization for In-Memory Databases	2016	VLDB
4	6,219	Incremental View Maintenance For Collection Programming	2016	PODS
5	10,544	Approximate Query Processing under Updates	2026	SIGMOD
6	4,321	Generalized Scale Independence Through Incremental Precomputation	2013	SIGMOD
7	9,320	CrocodileDB in Action: Resource-Efficient Query Execution by Exploiting Time Slackness	2020	VLDB
8	4,980	An Incremental Anytime Algorithm for Multi-Objective Query Optimization	2015	SIGMOD
9	5,667	Enabling Incremental Query Re-Optimization	2016	SIGMOD
10	6,796	Intermittent Query Processing	2019	VLDB