Enabling Incremental Query Re-Optimization

Summary: Presents an incremental, cost-based optimizer that re-plans as cost estimates change, with a focus on streaming workloads. Uses recursive Datalog for plan enumeration and pruning, enabling effective incremental re-optimization and applicability to conventional optimizers. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: ha345d1812d94435a
Venue: SIGMOD
Year: 2016
Pagerank: 6.0458446e-05
Overall Rank: 5,667 | 61.90%
DOI: 10.1145/2882903.2915212

Incoming Non-self Citations Over Time

Authors

1. Mengmeng Liu (University of Pennsylvania; Walmart Labs)
2. Zachary G. Ives (University of Pennsylvania)
3. Boon Thau Loo (University of Pennsylvania)

BibTeX Citation

@inproceedings{liu_sigmod16,
        title = {{Enabling Incremental Query Re-Optimization}},
        author = {Liu, Mengmeng and Ives, Zachary G. and Loo, Boon Thau},
        series = {{SIGMOD} '16},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2882903.2915212},
        url = {https://dl.acm.org/doi/10.1145/2882903.2915212},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,473	Voodoo - A Vector Algebra for Portable Database Performance on Modern Hardware	2016	VLDB	0.00010557973
7,249	Efficient Adaptive Detection of Complex Event Patterns	2018	VLDB	5.5745603e-05
8,332	Learned Offline Query Planning via Bayesian Optimization	2025	SIGMOD	5.3528188e-05
9,713	CHEX: Multiversion Replay with Ordered Checkpoints	2022	VLDB	5.1370211e-05
11,175	AJOSC: Adaptive Join Order Selection for Continuous Queries	2025	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 22 of 22 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
49	Dremel: Interactive Analysis of Web-Scale Datasets	2010	VLDB	0.00043160717
53	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.00040860054
62	Maintaining Views Incrementally	1993	SIGMOD	0.00039045511
88	Automated Selection of Materialized Views and Indexes for SQL Databases	2000	VLDB	0.00035351639
112	TelegraphCQ: Continuous Dataflow Processing for an Uncertain World	2003	CIDR	0.00032459277
129	Efficient and Extensible Algorithms for Multi Query Optimization	2000	SIGMOD	0.0003040756
149	Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans	1998	SIGMOD	0.00028981723
152	Query Processing, Resource Management, and Approximation in a Data Stream Management System	2003	CIDR	0.0002867034
272	An Overview of Query Optimization in Relational Systems	1998	PODS	0.00022509573
481	Robust Query Processing through Progressive Optimization	2004	SIGMOD	0.00017603972
594	Linear Road: A Stream Data Management Benchmark	2004	VLDB	0.00015823573
646	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD	0.0001520859
827	Adaptive Ordering of Pipelined Stream Filters	2004	SIGMOD	0.00013632674
1,030	Rate-Based Query Optimization for Streaming Information Sources	2002	SIGMOD	0.00012407749
1,987	Plan Bouquets: Query Processing without Selectivity Estimation	2014	SIGMOD	9.250242e-05
2,551	Aggregation and Relevance in Deductive Databases	1991	VLDB	8.3095988e-05
2,987	Adapting to Source Properties in Processing Data Integration Queries	2004	SIGMOD	7.7773398e-05
3,141	Evita Raced: Metacompilation for Declarative Networks	2008	VLDB	7.5995107e-05
3,371	Dynamic Plan Migration for Continuous Queries Over Data Streams	2004	SIGMOD	7.3693585e-05
4,366	Lifting the Burden of History from Adaptive Query Processing	2004	VLDB	6.6333069e-05
5,316	CliffGuard: A Principled Framework for Finding Robust Database Designs	2015	SIGMOD	6.1836681e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,487	Non-Invasive Progressive Optimization for In-Memory Databases	2016	VLDB
2	4,069	Dynamically Optimizing Queries over Large Scale Data Platforms	2014	SIGMOD
3	11,765	Asymptotically Better Query Optimization Using Indexed Algebra	2023	VLDB
4	5,078	Leveraging Re-costing for Online Optimization of Parameterized Queries with Guarantees	2017	SIGMOD
5	10,508	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD
6	1,030	Rate-Based Query Optimization for Streaming Information Sources	2002	SIGMOD
7	289	Optimization of Dynamic Query Evaluation Plans	1994	SIGMOD
8	4,980	An Incremental Anytime Algorithm for Multi-Objective Query Optimization	2015	SIGMOD
9	4,045	Adaptive Query Processing in the Looking Glass	2005	CIDR
10	4,693	Static Optimization of Conjunctive Queries with Sliding Windows Over Infinite Streams	2004	SIGMOD