Efficient Selection of Informative Alternative Relational Query Plans for Database Education

Given an arbitrary sql query, an rdbms generates a query execution plan (qep) to execute it. A qep consists of a collection of physical operators organized in form of a tree, namely the physical operator tree (operator tree for brevity). Fig. 1(a) depicts an example qep. Each physical operator, e.g., SEQUENTIAL SCAN, INDEX SCAN, takes as input one or more data streams and produces an output one. A qep explicitly describes how the underlying rdbms shall execute the given query. Notably, given a sql, there are many different query plans, other than the qep, for executing it. For instance, there are several physical operators in a rdbms that implement a join, e.g., HASH JOIN, SORT MERGE, NESTED LOOP. We refer to each of these different plans (other than the qep) as an alternative query plan (aqp). Fig. 1(b)-(d) depict three examples of aqp. It is well-known that the plan space is non-polynomial [7].

The informative plan selection (tips) problem aims to automatically select a small number of alternative plans that maximize plan informativeness. These plans are referred to as informative alternative plans (informative plans/aqps for brevity). The tips problem has two flavors:

• •

  Batch tips. A user may wish to view top-$k$ informative plans beside the qep;

• •

  Incremental tips. A user may iteratively view an informative plan besides what have been already shown to him/her;

Formally, we define these two variants of tips as follows.

In the next section, we shall elaborate on the notion of plan informativeness $U(\cdot)$ to capture informative plans.

Given a plan informativeness measure $U(\cdot)$ and the plan space $\Pi^{\ast}$, we can find an alternative plan for the i-tips problem in $O(|\Pi^{\ast}|)$ time. However, plan space increases exponentially with the increase in the number of joins and it is NP-hard to find the best join order [21]. Therefore, we need efficient solutions especially when there is a large number of joined tables.

In Section II, feedbacks from volunteers reveal that the selection of informative plans is influenced by the followings: (a) The structure, content, and cost differences of an alternative plan w.r.t. the qep (and other alterative plans) can be exploited to differentiate between informative and uninformative alternative plans. Hence, we need to quantify these differences for informative plan selection. (b) Volunteers typically do not prefer to view alternative plans that are very similar to the qep or other alternative plans already viewed by them. We now elaborate on the quantification approach to capture two factors and then utilizing them to quantify plan interestingness.

Broadly, $U(\cdot)$ should facilitate identifying specific alternative plans other than the qep such that by putting them together a user can acquire a comprehensive understanding of the alternative plan choices made by a query optimizer for her query (i.e., informative). This entails quantifying effectively differences between different plans w.r.t. their structure, content, and estimated cost. As $U(\cdot)$ is defined over a set of query plans, we shall first discuss the approach of quantifying these differences.

For example, the kernel score in Fig. 3 is $\kappa_{S}(T_{1},T_{2})=1\times 1+1\times 1=2$ because they share the substructures $f_{1}$, $f_{2}$. Since the subtree kernel is a similarity measure, we need to convert it to a distance. Moreover, each dimension may have different scale. Hence, it is necessary to normalize each distance dimension. For subtree kernel $\kappa\left(T_{a},T_{b}\right)$, we first compute the normalized kernel as follows and then define the structural distance:

It is worth noting that classical approach of computing subtree kernel using suffix tree will lead to quadratic time cost [39]. We advocate that this will introduce large computational cost in our problem scenario since we need to build a suffix tree for each alternative plan at runtime. To address this problem, we first serialize a tree bottom-up, and then use a hash table to record the number of different subtrees. When calculating the subtree kernel, we can directly employ a hash table to find the same subtree. Although the worst-case time complexity is still quadratic, as we shall see in Section VII, it is significantly faster than the classical suffix tree-based approach in practice.

Since we want to ensure that the content distance is a metric, we further normalize the edit distance [27]. Let $\Sigma$ be the alphabet, $\lambda\notin\Sigma$ is the null string and $\gamma$ is a non-negative real number which represents the weight of a transformation. Given two strings $X,Y$, the normalized edit distance is

where $\alpha=\max\{\gamma(a\rightarrow\lambda),\gamma(\lambda\rightarrow b),a,b\in\sum\}$ and $|X|$ is the length of $X$. This is proven to be a metric [27]. In our work, $\gamma=1$. So the content distance can be defined as follows.

Notably, join order difference is a special case where the content is the same while the order is different. Obviously, Defn. IV.4 is able to differentiate different join orders, e.g., AP1 and AP2 in Fig. 1(b) and 1(c). It is easy to infer that the distance presented above is able to differentiate these two plans.

The aforementioned distance measures enable us to avoid choosing plans with structure, content, and cost differences that are inconsistent with the feedbacks from volunteers. They can prevent selection of an alternative plan that is similar to plans that have been already viewed by a user. However, these measures individually cannot distil informative plans from uninformative ones. Therefore, we propose another measure called relevance (denoted as $rel(\cdot)$), to evaluate the “value” of each plan, such that informative plans receive higher relevance scores. Recall from Section II the 8 types of alternative plans. We convert the differences in these types into binary form (Fig. 4(a)) where 1 indicates large. We can also represent the informative value of these types (based on learner feedback) in binary form (1 means informative). We can then employ a multivariate function fitting to find an appropriate relevance function such that alternative plans that are close to the informative ones receive high scores. Since 8 existing samples are insufficient for fitting a polynomial function with an order higher than 3 [22], it should appear in the following form: $\rho_{1}\times s+\rho_{2}\times c+\rho_{3}\times cost+\rho_{4}\times s\times c+\rho_{5}\times s\times cost+\rho_{6}\times c\times cost+\rho_{7}\times s\times c\times cost$ where $\rho_{1},\ldots,\rho_{7}$ are parameters to be fit. By fitting the above polynomial, we can define the relevance measure as follows.

The effect of $rel(\cdot)$ is shown in Fig. 4(b). The red vertices represent the plan types that learners consider the most informative, which can effectively be captured by $rel(\cdot)$. In addition, plans close to the informative ones receive high scores accordingly. In fact, each plan $\pi$ can be referred to as a 3-dimensional vector $\vec{\pi}$ in the space shown in Fig. 4(b), hence $rel(\cdot)$ transforms a vector to a scale value, we shall use $rel(\pi)$ instead of $rel(\vec{\pi})$ for short.

Intuitively, through the plan interestingness measure, we aim to maximize the minimum relevance and distance of the selected query plan set. To this end, we can exploit measures that have been used in diversifying search results such as MaxMin, MaxSum, DisC, etc. [10; 11]. An experimental study in [12] has reported the effect of these choices in diversifying search results. Specifically, MaxSum and k-medoids fail to cover all areas of the result space; MaxSum tends to focus on the outskirts of the results whereas k-medoids clustering reports only central points, ignoring sparser areas. MaxMin and DisC perform better in this aspect. However, in the DisC model, users need to select a radius $r$ instead of the number $k$ of diverse results [11]. As the distribution of plans is uncertain, it is difficult to choose a suitable radius for the DisC model. Hence, we utilize the MaxMin model.

Suppose the plan set is $\Pi$. Then the objective is to maximize the following condition where $\lambda>0$ is a parameter specifying the trade-off between relevance and distance.

According to [15], the above bi-criteria objective problem can be transformed to find the refined distance defined in Definition IV.8. Consequently, we can define the plan interestingness $U(\cdot)$ as follows.

Now we consider $U_{r}$ in Defn. III.2, notably, i-tips allows a user to explore AP iteratively based on what has been revealed so far. We take into account the user preference in the form of $r\in\{1,0\}$ (i.e., prefer or not) during the exploration. For example, a user may want to find only those plans with different join orders but not others. This scenario can be easily addressed by i-tips, which allows one to mark whether a newly generated plan is preferred. Consider Fig. 4b where each AP is represented as a 3-dimensional vector $\vec{\pi}$ w.r.t. the qep ($\vec{\pi^{*}}=\langle 0,0,0\rangle$). According to Defn. IV.7, a preferred AP (as well as its neighbors) should receive higher relevance scores (warmer in the heatmap). Intuitively, finding the category of the preferred AP (i.e., $AP_{II}\sim AP_{IV},AP_{VII}$), say $AP_{II}$ (according to Fig. 4a, we can denote $\vec{AP_{II}}=\langle 0,0,1\rangle$), and moving the next plan towards (resp., away from) it if $r=1$ (resp., $r=0$), e.g., $\vec{\pi}=\vec{\pi}+\epsilon(\vec{AP_{II}}-\vec{\pi})$ would address this ($\epsilon=0.05$ by default). However, this strategy can affect only a single AP in the current iteration but not later. Therefore, instead of moving a single AP, we select to update the origin of the 3-dimensional system, i.e., $\vec{\pi^{*}}=\vec{\pi^{*}}-\epsilon(\vec{AP_{pre}}-\vec{\pi})$, where $\pi$ refers to the latest plan seen so far, and $AP_{pre}$ refers to the category to which $\pi$ belongs. To find $AP_{pre}$ for a plan $\pi$, we only need to perform a nearest neighbor search over the set of $\{\vec{AP_{II}},\vec{AP_{III}},\vec{AP_{IV}},\vec{AP_{VII}}\}$ (each can be encoded according to Fig. 4a) with respect to $\vec{\pi}$.

Give that the plan space can be very large for some queries, traversing all aqps to select informative plans can adversely impact efficiency of our solutions. Therefore, we need a strategy to quickly filter out uninformative aqps. According to feedbacks from volunteers (Section II), $AP_{VI}$ and $AP_{VIII}$ in Table I are uninformative. Observe that both these categories of plans have significant structural differences w.r.t. the qep. Hence, a simple approach to filter uninformative plans is to calculate the difference between each aqp and the qep and then discard aqps with very large differences. Although this approach can reduce the number of plans, we still need to traverse the entire plan space for computing the differences. Hence, we propose a group forest-based pruning strategy, which can not only reduce the number of aqps but also avoid accessing the entire plan space during the pruning process.

Cascade optimizers [16] utilize a memo structure (i.e., a forest of operator trees) to track all possible plans. A memo consists of a series of groups, each of which contains a number of expressions. An expression is employed to represent a logical/physical operator. Fig. 6a depicts an example of a memo, where each row represents a group and the square represents an expression in it. Each expression is associated with an id in the form of ‘GroupID.ExpressionID’, shown at the lower left corner (e.g., 3.1, 2.1). The lower right corner of an expression shows the id(s) of the child group(s) it points to. Different expressions in the same group are different operators that can achieve the same functionality. For example, both 3.1 (HashJoin) and 3.2 (NTLoop) implement the join operation. Suppose Group 3 is the root group. When we traverse down from the expression in the root group, we can get a plan. For example the id sequence (3.1, 2.1, 1.1) represents the plan HashJoin[TableScan, TableScan]. The upper right corner of each expression records the number of alternatives with this expression as the root node. For example, the number of expression 1.3 is 2, which includes 1.3$\rightarrow$1.1 and 1.3$\rightarrow$1.2.

Observe that the number of alternatives of the expression 3.1 in the root node is 8. That is, there are 8 different plans rooting at expression 3.1. However, there are only 2 tree structures over all these 8 plans as shown in Fig.  6b. The number in each node represents the id of the group. Since these trees represent connections between different groups, we refer to them collectively as group forest. Each group tree in a group forest represents multiple plans with the same structure and if the structure distance of a group tree and the qep is larger than a given distance threshold $\tau_{d}$, i.e., $s\_dist(\pi,\pi^{*})\geq\tau_{d}$, all the corresponding ids can be filtered out. Observe that the number of group trees is significantly smaller than the number of aqps. Therefore, uninformative plans can be quickly eliminated by leveraging them. In order to construct the group forest, we only need to traverse the memo in a bottom-up manner, which is extremely fast, i.e., time cost is linear to the height of the constructed tree.

Lastly, observe that if we filter based on $s\_dist$ only, informative plans of types $AP_{IV}$ and $AP_{VII}$ (Table I) may be abandoned. The difference between these two types of plans and $AP_{VI}$ and $AP_{VIII}$ is that the cost is smaller. Hence, we filter using both the structure and cost differences, i.e.,, $s\_dist(\pi,\pi^{*})\geq\tau_{d},cost\_dist(\pi,\pi^{*})\geq\tau_{c}$ where $\tau_{c}$ is a pre-defined cost threshold.

It is prohibitively expensive to enumerate the entire plan space to select informative plans when the number of joins is large (i.e., involving more than 10 relations). We may sample some plans from the entire plan space and select informative plans from them. However, simply deploying random sampling may discard many informative plans. To address that, we propose an importance-based plan sampling (ips) strategy that exploits the insights gained from feedbacks from volunteers in Section II to select plans for subsequent processing. The overall goal is to preserve the informative plans as much as possible during the sampling. However, retaining all informative plans will inevitably demand traversal of every aqp to compute plan interestingness. Hence, instead of preserving all informative plans, we select to keep the most important ones when the number of joined relations in a query is large. We exploit the feedbacks in Section II to sample plans. Observe that $AP_{II}$ plans receive a significant number of votes among all informative plans. Hence, we inject such plans as much as possible in our sample. Also, $AP_{II}$ plans have small structural differences with the qep. Hence, given a qep, we can easily determine whether an aqp belongs to $AP_{II}$ or not by finding all alternative plans with the same structure as qep. These plans are then combined with uniformly random sampled results. The pseudocode of the ips strategy is shown in Algorithm 1.

Algorithm 2 outlines the procedure to address the i-tips problem defined in Definition III.2. If the number of joined relations is greater than the predefined ips threshold $\tau_{\ell}$, we invoke ips (Line 2). In addition, if the number of aqps is greater than the predefined gfp threshold $\tau_{g}$, it invokes the group forest-based pruning strategy (Line 5), to filter out some uninformative plans early.

Notably, i-tips allows a user to explore AP iteratively based on what have been shown. We take into account user-preference during the exploration. For instance, a user may want to find only those plans with different join orders but not others. Such scenario can be easily addressed by i-tips, which enables one to mark whether a newly generated plan is preferred. Consider Fig. 4b where each AP is represented as a 3-dimensional vector $\vec{\pi}$ w.r.t. the qep ($\vec{\pi^{*}}=\langle 0,0,0\rangle$). According to Definition IV.7, a preferred AP (as well as its neighbors) should receive higher relevance scores (warmer in the heatmap). Intuitively, finding the category (Line 9) of the preferred AP (i.e., $AP_{II}\sim AP_{IV},AP_{VII}$), say $AP_{II}$ ($\vec{AP_{II}}=\langle 0,0,1\rangle$), and moving it towards it, e.g., $\vec{\pi}=\vec{\pi}+\epsilon(\vec{AP_{II}}-\vec{\pi})$ would address this ($\epsilon=0.05$ by default). However, this strategy can only affect a single AP in the current iteration but not the ones afterwards. Therefore, instead of moving a single AP, we select to update the origin for the 3-dimensional system, i.e., $\vec{\pi^{*}}=\vec{\pi^{*}}-\epsilon(\vec{AP_{pre}}-\vec{\pi})$ (Line 10), where $AP_{pre}$ refers to the category that $\pi$ belongs to.

We propose two flavors of the algorithm to address b-tips, namely, b-tips-basic and b-tips-heap.

b-tips-basic algorithm. We can exploit Algorithm 2 to address the b-tips problem. We first add the qep $\pi^{*}$ to the final set $\Pi$. Then iteratively invoke the Algorithm 2 until there are $k+1$ plans in $\Pi$. Each time we just need to add the result of Algorithm 2 to $\Pi$. This algorithm has a time complexity of $O\left(k|\Pi^{\ast}|\right)$.

b-tips-heap algorithm. Since the minimum distance between plans in $\Pi^{*}-\Pi$ and $\Pi$ decrease monotonically with the increase of $|\Pi|$, we can use a max-heap to filter plans with very small distances to avoid unnecessary computation. Algorithm 3 describes the procedure. We first invoke our two pruning strategies (Line 1). In Line 6, we add a tuple which consists of the ID of an alternative plan $\pi$ and a distance to the heap, which indicates the minimum distance between $\pi$ and the plans in $\Pi$. Each time we choose a plan to add into $\Pi$, we do not update the distance of all tuples. Instead, we only need to check if this distance is correct (Line 17) and update it (Line 18). We select the alternative plan with the maximum minimum distance during each iteration. Observe that the worst-case time complexity is also $O\left(k|\Pi^{\ast}|\right)$. However, it is significantly more efficient than b-tips-basic in practice (detailed in Section VII).

For a MaxMin problem, a polynomial-time approximation algorithm provides a performance guarantee of $\rho\geq 1$, if for each instance of the problem, the minimum distance of the result set produced by the algorithm is at least $1/\rho$ of the optimal set minimum distance. We will also refer to such an algorithm as a $\rho$-approximation algorithm.

Datasets. We use two datasets. The first is the Internet Movie Data Base (IMDb) dataset [2; 25], containing two largest tables, cast_info and movie_info have 36M and 15M rows, respectively. The second one is the TPC-H dataset [3]. We use the TPC-H v3 and 1 GB data generated using dbgen [3].

Since the number of candidate plans impacts the performance of tips, which is mainly affected by the sql statement, we choose different sql queries to vary the plan size. For IMDb,  [25] provides 113 sql queries. We choose 8 of them for our experiments. For the TPC-H dataset, there are 22 standard sql statements. Because the uneven distribution of the plan space of these queries, it is difficult to find sql statements that are evenly distributed as in IMDb dataset. We select 6 sql queries from them for our experiments. These selected queries and the plan space size are reported in Table II. Note that the space sizes are the entire plan spaces from orca.

Baselines. We are unaware of any existing informative plan selection technique. Hence, we are confined to compare arena with the following baselines. (a) We implemented a random selection algorithm (denoted by random). It is executed repeatedly $n$ times and each time a result is randomly generated. The best result is returned after $n$ iterations. In our experiment, we set $n=30$. (b) A simple solution for tips is to return those with the least cost besides the qep. Hence, we implement a cost-based approach that returns the top-$k$ plans with the least cost in $\Pi^{\ast}$ (denoted by cost) besides the QEP. (c) We also implemented an embedding-based approach (denoted by embedding), where we embed each aqp into a vector by feeding its estimated time cost and tree structure into an autoencoder following [5] and then rank the aqps according to their Euclidean distance w.r.t. the qep. Afterwards, the plan informativeness of the top-$k$ can be computed following Defn. IV.10 accordingly.