### 3.2.1 Performance Characteristics

At first glance, the plan bouquet approach, as described above, may appear to be utterly absurd and self-defeating because: (a) At compile time, considerable preprocessing may be required to identify the POSP plan set and the associated PIC; and (b) At run-time, the overheads may be hugely expensive since there are multiple plan executions for a single query – in the worst scenario, as many plans as are present in the bouquet!

However, we will now make the case that it is indeed possible, through careful design, to have * plan bouquets efficiently provide robustness profiles that are markedly superior to the native optimizer’s profile.* Specifically, the bouquet mechanism delivers substantial improvements with regard to **MSO**, the robustness metric defined in Section 2.

For instance, the runtime performance of the bouquet technique on the example query is profiled in Figure 8 (dark blue curve). We observe that its performance is much closer to the PIC (dark green) as compared to the worst case profile for the native optimizer (dark red), which is comprised of the supremum of the individual plan profiles. In fact, the MSO for the bouquet is only 3.6 (at 6.5%), whereas the native optimizer suffers a sub-optimality of around 100 when P5, which is optimal for large selectivities is mistakenly chosen to execute a query with a small selectivity of only 0.01%.

### 3.2.2 MSO Guarantees

Our motivation for the cost-based discretization of the PIC is that it leads to *guaranteed* bounds on the MSO value. For instance, we now prove that the cost-doubling strategy used in the 1D example results in an *MSO upper-bound of 4* – this bound is inclusive of all exploratory overheads incurred by the partial executions, and is *irrespective* of the query’s actual selectivity. In fact, we can go further to show that 4 is the best guarantee achievable by any deterministic algorithm.

By virtue of our assumptions on plan cost behavior, the PIC turns out to be a monotonically increasing and continuous function throughout the ESS; its minimum and maximum costs are denoted by *C _{min}* and

*C*, respectively. This PIC is discretized by projecting a graded progression of cost steps onto the curve. Specifically, consider the case wherein the steps are organized in a

_{max}*geometric*progression with initial value

*a*(

*a*> 0) and common ratio

*r*(

*r*> 1), such that the

Figure 9: ID selectivity space

For 1 ≤ *k* ≤ *m*, denote the selectivity location where the *k ^{th}* cost step (

*IC*) intersects the PIC by

_{k}*q*, and the corresponding bouquet plan as

_{k}*P*. All the

_{k}*q*locations are unique, by definition, due to the monotonicity and continuity features of the PIC. Finally, for mathematical convenience, assign

_{k}*q*to be 0.

_{0}With this framework, the bouquet execution algorithm, outlined in Algorithm 1, operates as follows in the most general case, where a different plan is associated with each step: We start with plan *P _{1}* and budget

*cost(IC*, progressively working our way up through the successive bouquet plans

_{1})*P*, … until we reach the first plan

_{2}, P_{3}*P*that is able to fully execute the query within its assigned budget

_{k}*cost(IC*. It is easy to see that the following lemma holds:

_{k})**Lemma 3.1.** *If q _{a} resides in the range (q_{k-1} , q_{k}], 1 ≤ k ≤ m, then plan P_{k} executes it to completion in the bouquet algorithm.*

**Proof.** We prove by contradiction: If *q _{a}* was located in the region (

*q*], then

_{k}, q_{k+1}*P*could not have completed the query due to the PCM restriction. Conversely, if

_{k}*q*was located in (

_{a}*q*],

_{k-2}, q_{k-1}*P*itself would have successfully executed the query to completion. With similar reasoning, we can prove the same for the remaining regions that are beyond

_{k-1}*q*or before

_{k+1}*q*

_{k-2}.**Performance Bounds** Consider the generic case where *q _{a}* lies in the range (

*q*]. Based on Lemma 1, the associated worst case cost of the bouquet execution algorithm is given by the following expression:

_{k-1}, q_{k}where the “*” in the *q _{e }*location indicates that, unlike conventional optimizers, the PlanBouquet algorithm does not make any such estimations. Further, note that the final expression is

*independent*of

*k*, and hence of the specific location of

*q*. Therefore, we can state, for the entire selectivity space, that:

_{a}