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.3873068e-05
Overall Rank: 8,159 | 45.15%
DOI: 10.14778/3275366.3275368

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,954	Robust Query Processing: Mission Possible	2020	VLDB	5.4190023e-05
8,389	PARQO: Penalty-Aware Robust Plan Selection in Query Optimization	2024	VLDB	5.3413016e-05
8,673	Adaptive Code Generation for Data-Intensive Analytics	2021	VLDB	5.2913671e-05
9,730	PAR2QO: Parametric Penalty-Aware Robust Query Optimization	2025	VLDB	5.1349531e-05
10,368	Coresets for Robust Query Optimization	2026	PODS	4.9793485e-05
11,283	Robust Plan Evaluation based on Approximate Probabilistic Machine Learning	2025	VLDB	4.9793485e-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.0023947656
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061066921
481	Robust Query Processing through Progressive Optimization	2004	SIGMOD	0.00017603972
836	Proactive Re-Optimization	2005	SIGMOD	0.00013557047
998	What happens during a Join? Dissecting CPU and Memory Optimization Effects	2000	VLDB	0.00012630367
1,298	Parametric Query Optimization for Linear and Piecewise Linear Cost Functions	2002	VLDB	0.00011120288
1,612	AniPQO: Almost Non-intrusive Parametric Query Optimization for Nonlinear Cost Functions	2003	VLDB	0.00010072731
1,987	Plan Bouquets: Query Processing without Selectivity Estimation	2014	SIGMOD	9.250242e-05
3,527	Identifying Robust Plans through Plan Diagram Reduction	2008	VLDB	7.2310714e-05
5,078	Leveraging Re-costing for Online Optimization of Parameterized Queries with Guarantees	2017	SIGMOD	6.2857912e-05
6,106	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB	5.8859291e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,777	Visualizing the robustness of query execution	2009	CIDR
2	7,487	Non-Invasive Progressive Optimization for In-Memory Databases	2016	VLDB
3	8,524	ROME: Robust Query Optimization via Parallel Multi-Plan Execution	2024	SIGMOD
4	6,106	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB
5	481	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,113	Robustness Metrics for Relational Query Execution Plans	2018	VLDB
8	3,527	Identifying Robust Plans through Plan Diagram Reduction	2008	VLDB
9	6,393	QUEST: An Exploratory Approach to Robust Query Processing	2014	VLDB
10	1,987	Plan Bouquets: Query Processing without Selectivity Estimation	2014	SIGMOD