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.
Raychaudhury et al. (Tue,) studied this question.