A Concave Path to Low-overhead Robust Query Processing

Summary: FrugalSpillBound exploits concave-down plan costs to slash SpillBound’s compilation overhead while retaining robust-query guarantees. Relaxing guarantees 2× cuts overhead by 100–1000×, extending worst-case query processing from canned to ad-hoc OLAP workloads. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h6a7aba3e044af83f
Venue: VLDB
Year: 2018
Pagerank: 5.3847569e-05
Overall Rank: 8,165 | 45.13%
DOI: 10.14778/3275366.3275368
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Srinivas Karthik (Indian Institute of Science)
2. Jayant R. Haritsa (Indian Institute of Science)
3. Sreyash Kenkre (IBM)
4. Vinayaka Pandit (IBM)

BibTeX Citation

@article{karthik_vldb18,
        title = {{A Concave Path to Low-overhead Robust Query Processing}},
        author = {Karthik, Srinivas and Haritsa, Jayant R. and Kenkre, Sreyash and Pandit, Vinayaka},
        journal = {PVLDB},
        series = {{VLDB} '18},
        volume = {11},
        number = {13},
        pages = {2183--2195},
        doi = {10.14778/3275366.3275368},
        url = {https://doi.org/10.14778/3275366.3275368},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,958	Robust Query Processing: Mission Possible	2020	VLDB	5.4164639e-05
8,393	PARQO: Penalty-Aware Robust Plan Selection in Query Optimization	2024	VLDB	5.3387995e-05
8,681	Adaptive Code Generation for Data-Intensive Analytics	2021	VLDB	5.288863e-05
9,735	PAR2QO: Parametric Penalty-Aware Robust Query Optimization	2025	VLDB	5.1325223e-05
10,380	Coresets for Robust Query Optimization	2026	PODS	4.9769913e-05
11,291	Robust Plan Evaluation based on Approximate Probabilistic Machine Learning	2025	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 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.0023943337
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061067652
471	Robust Query Processing through Progressive Optimization	2004	SIGMOD	0.00017744392
837	Proactive Re-Optimization	2005	SIGMOD	0.00013551072
997	What happens during a Join? Dissecting CPU and Memory Optimization Effects	2000	VLDB	0.00012628913
1,298	Parametric Query Optimization for Linear and Piecewise Linear Cost Functions	2002	VLDB	0.00011122244
1,612	AniPQO: Almost Non-intrusive Parametric Query Optimization for Nonlinear Cost Functions	2003	VLDB	0.00010068388
1,989	Plan Bouquets: Query Processing without Selectivity Estimation	2014	SIGMOD	9.2469024e-05
3,527	Identifying Robust Plans through Plan Diagram Reduction	2008	VLDB	7.2283486e-05
5,081	Leveraging Re-costing for Online Optimization of Parameterized Queries with Guarantees	2017	SIGMOD	6.2830143e-05
6,108	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB	5.8831615e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,860	Optimizing Disjunctive Queries with Expensive Predicates	1994	SIGMOD
2	7,492	Non-Invasive Progressive Optimization for In-Memory Databases	2016	VLDB
3	8,531	ROME: Robust Query Optimization via Parallel Multi-Plan Execution	2024	SIGMOD
4	6,108	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB
5	471	Robust Query Processing through Progressive Optimization	2004	SIGMOD
6	5,988	On the Stability of Plan Costs and the Costs of Plan Stability	2010	VLDB
7	6,114	Robustness Metrics for Relational Query Execution Plans	2018	VLDB
8	3,527	Identifying Robust Plans through Plan Diagram Reduction	2008	VLDB
9	6,396	QUEST: An Exploratory Approach to Robust Query Processing	2014	VLDB
10	1,989	Plan Bouquets: Query Processing without Selectivity Estimation	2014	SIGMOD