A concave path to lowoverhead robust query processing

To address the classical selectivity estimation problem in database systems, a radically different query processing technique called PlanBouquet was proposed in 2014. In this approach, the estimation process is completely abandoned and replaced with a calibrated selectivity discovery mechanism. The beneficial outcome is that provable guarantees are obtained on worst-case execution performance, thereby facilitating robust query processing. An improved version of PlanBouquet, called SpillBound (SB), which significantly accelerates the selectivity discovery process, and provides platform-independent performance guarantees, was presented two years ago. Notwithstanding its benefits, a limitation of SpillBound is that its guarantees are predicated on expending enormous preprocessing efforts during query compilation, making it suitable only for canned queries that are invoked repeatedly. In this paper, we address this limitation by leveraging the fact that plan cost functions typically exhibit concave down behavior with regard to predicate selectivities. Specifically, we design FrugalSpillBound, which provably achieves extremely attractive tradeoffs between the performance guarantees and the compilation overheads. For instance, relaxing the performance guarantee by a factor of two typically results in at least two orders of magnitude reduction in the overheads. Further, when empirically evaluated on benchmark OLAP queries, the decrease in overheads is even greater, often more than three orders of magnitude. Therefore, FrugalSpillBound substantively extends robust query processing towards supporting ad-hoc queries.