在海山数据库(He3DB)+AI（三）中，先容了四种旋钮调优方法：基于启发式，基于贝叶斯，基于深度学习和基于强化学习，还先容了迁移学习技巧。本文带来2024 VLDB的论文：An Efficient Transfer Learning Based Configuration Adviser for Database Tuning，先容一种基于迁移学习的启发式数据库调优方法。
1 OpAdviser
一个数据库在执行差别的调优任务时，可以积累丰富的汗青经验。对当前任务，找到雷同的汗青任务，从汗青任务中发掘有效的信息，来指导当前的任务。
那么怎样来量化当前任务和汗青任务的相似性呢？
通过考虑两个任务在差别配置下是否具有相似的性能分布来解决这个问题。
假设用 ( θ , f ( θ ) ) (\theta,f(\theta)) (θ,f(θ))来形貌参数配置和性能。汗青任务 m m m在数据仓库中有一组性能数据 ( θ 1 m , f ( θ 1 m ) ) , ( θ 2 m , f ( θ 2 m ) ) , . . . ( θ n m , f ( θ n m ) ) {(\theta^m_1,f(\theta^m_1)),(\theta^m_2,f(\theta^m_2)),...(\theta^m_n,f(\theta^m_n))} (θ1m,f(θ1m)),(θ2m,f(θ2m)),...(θnm,f(θnm))，并基于这组性能数据在离线阶段使用随机丛林训练了性能函数 f ′ f' f′ 。当前任务在迭代执行得到一组性能参数 ( θ 1 , f ( θ 1 ) ) , ( θ 2 , f ( θ 2 ) ) , . . . ( θ , f ( θ n ) ) {(\theta_1,f(\theta_1)),(\theta_2,f(\theta_2)),...(\theta_,f(\theta_n))} (θ1,f(θ1)),(θ2,f(θ2)),...(θ,f(θn))。OpAdviser通过计算两个任务之间 θ \theta θ变化导致的 f ( ) f() f()变化是否划一来判断任务的相似性，即导数方向是否划一，其相似性计算公式如公式1所示：
S ( i , t ) = 2 ∣ H t ∣ ( ∣ H t ∣ − 1 ) F ( i , t ) F ( i , t ) = ∑ j = 1 ∣ H t ∣ ∑ k = j + 1 ∣ H t ∣ 1 ( f ( θ j ) ≤ f ( θ k ) ) ⊗ 1 ( f ′ ( θ j , w i ) ≤ f ′ ( θ k , w i ) ) (1) \begin{array}{l} \begin{array}{l} S(i, t)=\frac{2}{\left|H^{t}\right|\left(\left|H^{t}\right|-1\right)} F(i, t) \\ F(i, t)=\sum_{j=1}^{\left|H^{t}\right|} \sum_{k=j+1}^{\left|H^{t}\right|} \mathbb{1}\left(f\left(\theta_{j}\right) \leq f\left(\theta_{k}\right)\right) \otimes \mathbb{1}\left(f^{\prime}\left(\theta_{j}, w_{i}\right) \leq f^{\prime}\left(\theta_{k}, w_{i}\right)\right) \end{array}\\ \tag{1} \end{array} S(i,t)=∣Ht∣(∣Ht∣−1)2F(i,t)F(i,t)=∑j=1∣Ht∣∑k=j+1∣Ht∣1(f(θj)≤f(θk))⊗1(f′(θj,wi)≤f′(θk,wi))(1)
公式中， F ( i , t ) F(i,t) F(i,t)是性能变化划一性的样本数量， H t H^t Ht是现有任务的观察样本数量， 2 ∣ H t ∣ ( ∣ H t ∣ − 1 ) \frac{2}{|H^t|(|H^t|-1)} ∣Ht∣(∣Ht∣−1)2则表现全部样本的组合，OpAdviser使用性能变化划一性样本数量占全部样本组合的比例来表现两个任务之间的相似性。
在判断任务相似性时，设定阈值为0.5，当相似度小于0.5时，将其过滤掉。
2.2 有效区域提取
当找到了与当前任务相似度高的汗青任务，怎样从中获取有效信息，来资助缩小搜索的范围？
可以将其建模为一个优化问题，在包管最优参数在其范围内时最小化搜索空间，最优化公式如下所示：
arg min Φ i Λ ( Φ i ) , s.t. ∀ θ ∈ G , θ ∈ Θ ^ ( Φ i ) . (2) \begin{array}{cc} & \underset{\Phi^{i}}{\arg \min } \Lambda\left(\Phi^{i}\right), \\ \text { s.t. } & \forall \theta \in G, \theta \in \hat{\Theta}\left(\Phi^{i}\right) . \tag{2} \end{array} s.t. ΦiargminΛ(Φi),∀θ∈G,θ∈Θ^(Φi).(2)
在公式中，优化目标是最小化搜索空间 Θ ^ ( Φ i ) \hat{\Theta}\left(\Phi^{i}\right) Θ^(Φi)，约束条件是这个空间中要包含全部的有希望的配置 G G G。 G G G通过已有的观察点和随机采样的一组配置来确定，若在该组配置下，模型性能超过肯定阈值 f b i f_b^i fbi，就将其加入集合。而阈值 f b i f_b^i fbi简直定由以下公式确定：
f b i = f d e f a u l t i + 2 ( f b e s t i − f d e f a u l t i ) ( S ( i , t ) − 0.5 ) (3) f_b^i = f_{default}^i+2(f^i_{best}-f^i_{default})(S(i,t)-0.5) \tag{3} fbi=fdefaulti+2(fbesti−fdefaulti)(S(i,t)−0.5)(3)
公式中， f d e f a u l t i f^i_{default} fdefaulti是汗青任务在默认配置下的性能， f b e s t i f^i_{best} fbesti是观察到的最好性能， S ( i , t ) S(i,t) S(i,t)是汗青任务和当前任务的相似度。
操持这个计算公式的来由如下：
如果汗青任务和当前任务高度相似，那么 f b i f_b^i fbi的值会和 f b e s t i f^i_{best} fbesti很接近，那么搜索的空间很小。
如果汗青任务和当前任务高度相似性不高，那么搜索空间就会变大。
搜索空间的面积由以下公式确定：
Λ ( Φ i ) = ∏ k j i ∈ K 1 ( u ^ j i − l ^ j ) ∏ k t i ∈ K 2 ∣ s ^ t i ∣ (4) \Lambda\left(\Phi^{i}\right)=\prod_{k_{j}^{i} \in K 1}\left(\hat{u}_{j}^{i}-\hat{l}_{j}\right) \prod_{k_{t}^{i} \in K 2}\left|\hat{s}_{t}^{i}\right| \tag{4} Λ(Φi)=kji∈K1∏(u^ji−l^j)kti∈K2∏ s^ti (4)
公式中， K 1 K_1 K1表现连续的旋钮， K 2 K_2 K2表现离散的旋钮。对于连续旋钮，其上界和下界分别为 u ^ j i \hat{u}_{j}^{i} u^ji和 l ^ j i \hat{l}_{j}^{i} l^ji，其公式如下所示：
l ^ j i = min { θ j ∣ θ ∈ G } , u ^ j i = max { θ j ∣ θ ∈ G } (5) \hat{l}_{j}^{i}=\min \left\{\theta_{j} \mid \theta \in G\right\}, \quad \hat{u}_{j}^{i}=\max \left\{\theta_{j} \mid \theta \in G\right\} \tag{5} l^ji=min{θj∣θ∈G},u^ji=max{θj∣θ∈G}(5)
对于离散旋钮，其值由以下公式计算：
s ^ t i = { θ t ∣ θ ∈ G } (6) \hat{s}_{t}^{i}=\left\{\theta_{t} \mid \theta \in G\right\} \tag{6} s^ti={θt∣θ∈G}(6)
接下来，为了更进一步缩小搜索空间，使用特征算法[5]基于汗青的观测信息来选择重要的旋钮。本文使用SHAP[1]，SHAP是一个通过配置之间的性能变化来衡量特征重要性的工具，移除一些不值得调优的旋钮，从而进一步缩小搜索空间。
2.3 多数加权投票
通过以上两步，从每个候选任务中提取了有效区域，根据这些信息，来生成最后的目标搜索空间，包括哪些是重要的旋钮和其调参范围。
本文操持了一个多数加权投票策略来聚合来自候选任务的建议，根据每个汗青任务和当前任务的相似度来计算其权重，计算公式如下所示：
w i = S ( i , t ) ∑ j = 1 m S ( j , t ) (7) w_{i}=\frac{S(i, t)}{\sum_{j=1}^{m} S(j, t)} \tag{7} wi=∑j=1mS(j,t)S(i,t)(7)
将总权重阈值设为50%，具有多数同意删除的旋钮被删除，多数同意保留的旋钮被保留，对于每个保留的旋钮，罗列其提取的有效范围和具有多数投票的区域，生成一个紧凑的区域将其包括在内。
为了避免负迁移，使用两条策略。 策略一：
根据在上一轮迭代中的观察样本和训练好的性能函数 f ′ f' f′，在获得新的配置参数 θ \theta θ后，使用3.2节的方法提取有效区域，公式如下：
S ( t , t ) = 2 ∣ H t ∣ ( ∣ H t ∣ − 1 ) F ( t , t ) F ( t , t ) = ∑ j = 1 ∣ D t ∣ ∑ k = j + 1 ∣ D t ∣ 1 ( f ( θ j ) ≤ f ( θ k ) ) ⊗ 1 ( f − j ′ ( θ j ) ≤ f − k ′ ( θ k ) ) , (8) \begin{array}{l} \begin{array}{l} S(t, t)=\frac{2}{\left|H^{t}\right|\left(\left|H^{t}\right|-1\right)} F(t, t) \\ F(t, t)=\sum_{j=1}^{\left|D^{t}\right|} \sum_{k=j+1}^{\left|D^{t}\right|} \mathbb{1}\left(f\left(\theta_{j}\right) \leq f\left(\theta_{k}\right)\right) \otimes \mathbb{1}\left(f_{-j}^{\prime}\left(\theta_{j}\right) \leq f_{-k}^{\prime}\left(\theta_{k}\right)\right), \end{array}\\ \tag {8} \end{array} S(t,t)=∣Ht∣(∣Ht∣−1)2F(t,t)F(t,t)=∑j=1∣Dt∣∑k=j+1∣Dt∣1(f(θj)≤f(θk))⊗1(f−j′(θj)≤f−k′(θk)),(8)
随着模型的迭代， f ′ f' f′渐渐提升，相似度渐渐提升。下图为基于候选任务举行搜索空间提取的过程，其中第一举动上一轮迭代中拟合的模型，第二至第四举动汗青任务。随着迭代开始，不断获取新的采样点，根据这些采样点，计算与各个候选模型的相似度，然后基于相似度计算当前任务的权重。从图中可以看到，随着样本数量的增加，自身模型的权重不断上升。
策略二：
对于候选任务，采样其中的 k k k个（不是全部使用），根据其相似度来计算权重，采样是为了加入随机性，避免优化器陷入局部最优。
3确定优化器
使用收集到的数据，开始构建学习模型，本文接纳了LambdaMART[3]算法，将优化器的选择问题转化为排序问题。LambdaMar将任务元特征和两个候选优化器作为输入举行比力，产生在给定任务上的相对性能排名。
模型输入：( m , o i , o j , I m,o_i,o_j,I m,oi,oj,I)
模型输出：1或0
其中， m m m表现元特征， o i o_i oi和 o j o_j oj为优化器的独热编码， I I I是一个标识符。当 o i o_i oi的性能优于 o j o_j oj时，输出为1，否则为0。
具体地，OpAdviser从目标任务中提取元特征，将该特征与候选优化器对一起输入到元排序器中，并推荐排名靠前的优化器。
元排序方法与其他方法相比，其上风如下：
1）与分类模型相比，通过考虑成对性能可以提取更多的信息；
2）与回归模型相比，只需要举行两两优化器之间的比力，可以更好地处理噪声数据和差别规模的数据。
4 参考文献
[1]Scott M. Lundberg and Su-In Lee. 2017. A Unified Approach to Interpreting Model Predictions. In NIPS. 4765–4774.
[2]David D. Lewis and Jason Catlett. 1994. Heterogeneous Uncertainty Sampling for Supervised Learning. In ICML. Morgan Kaufmann, 148–156.
[3]Christopher JC Burges. 2010. From ranknet to lambdarank to lambdamart: An overview. Learning 11, 23-581 (2010), 81.
