Coresets for Robust Query Optimization
Proceedings of the ACM on Management of Data · 12.05.2026 · 4 (2) · 1-23
DOI: 10.1145/3801896 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 14.05.2026. Verfasst von Rahul Raychaudhury und 4 weiteren Autor:innen. Die Arbeit nennt 54 Literaturangaben.
Abstract (Originalsprache)
Query optimizers must efficiently choose a query plan using noisy estimates of cardinalities. We study robust query optimization, where the optimizer is made aware of the uncertainty in cardinality estimates and needs to select the most ''robust'' plan. A key empirical observation is that a small set of plans often suffices as robust plan candidates for all queries following a given template. We formalize this phenomenon by introducing coresets of plans and extend this notion to robust coresets, which incorporate uncertainty. We prove positive and negative results on the sizes of such coresets for common cost-function classes. Because our lower bounds suggest that the size of a coreset can be large in the worst case, we exploit the fact that in practice queries arise from workload distributions, rather than being arbitrary. We present algorithms that construct workload-aware coresets whose size and performance closely match those of the optimal workload-specific coresets.
Zitieren
APA
Raychaudhury, R., Xiu, H., Agarwal, P. K., Sintos, S., & Yang, J. (2026). Coresets for Robust Query Optimization. Proceedings of the ACM on Management of Data, 4(2), 1-23. https://doi.org/10.1145/3801896
Vancouver
Raychaudhury R, Xiu H, Agarwal PK, Sintos S, Yang J. Coresets for Robust Query Optimization. Proceedings of the ACM on Management of Data. 2026;4(2):1-23. doi:10.1145/3801896
BibTeX
@article{Raychaudhury2026,
author = {Raychaudhury, Rahul and Xiu, Haibo and Agarwal, Pankaj K. and Sintos, Stavros and Yang, Jun},
title = {Coresets for Robust Query Optimization},
journal = {Proceedings of the ACM on Management of Data},
year = {2026},
volume = {4},
number = {2},
pages = {1--23},
doi = {10.1145/3801896}
}
EUVIMED