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: 11919
Venue: VLDB
Year: 2018
Pagerank: 5.5082745e-05
Overall Rank: 8,004 | 45.09%
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,829	Robust Query Processing: Mission Possible	2020	VLDB	5.5360082e-05
8,305	PARQO: Penalty-Aware Robust Plan Selection in Query Optimization	2024	VLDB	5.4568571e-05
8,636	Adaptive Code Generation for Data-Intensive Analytics	2021	VLDB	5.3954959e-05
10,151	Coresets for Robust Query Optimization	2026	PODS	5.093636e-05
10,881	Robust Plan Evaluation based on Approximate Probabilistic Machine Learning	2025	VLDB	5.093636e-05
10,986	PAR2QO: Parametric Penalty-Aware Robust Query Optimization	2025	VLDB	5.093636e-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.0024089429
18	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059284255
492	Robust Query Processing through Progressive Optimization	2004	SIGMOD	0.0001756877
829	Proactive Re-Optimization	2005	SIGMOD	0.00013769838
987	What happens during a Join? Dissecting CPU and Memory Optimization Effects	2000	VLDB	0.00012814017
1,321	Parametric Query Optimization for Linear and Piecewise Linear Cost Functions	2002	VLDB	0.00011162369
1,645	AniPQO: Almost Non-intrusive Parametric Query Optimization for Nonlinear Cost Functions	2003	VLDB	0.00010129244
1,987	Plan Bouquets: Query Processing without Selectivity Estimation	2014	SIGMOD	9.3517129e-05
3,506	Identifying Robust Plans through Plan Diagram Reduction	2008	VLDB	7.3581509e-05
5,281	Leveraging Re-costing for Online Optimization of Parameterized Queries with Guarantees	2017	SIGMOD	6.2842378e-05
6,009	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB	6.0113733e-05

Semantically Similar Papers

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