在本节中，我们首先解释了在问题中使用蒙特卡罗树搜索的动机，说明mcts在索引推荐方面的缺陷，针对这些缺陷提出了我们的改进，然后给出了我们模型的总体框架，介绍如何基于工作负载特征有效地推荐以及更新索引。
5.1 MCTS-based Index Selection
The motivation of using MCTS
在本小节中，我们将介绍如何基于MCTS高效地进行索引推荐。第一，由于通常一个工作负载的候选索引空间都很大，MCTS通过随机化搜索和动态调整搜索策略，能够在庞大的候选索引空间中高效地进行探索。相比于传统的穷举搜索或贪婪算法，MCTS能够有效地在大规模空间中找到最优解，节省了大量的搜索时间和计算资源。第二，对于动态的工作负载，MCTS能够在候选索引集合发生变化时，快速地调整搜索策略，以适应新的索引配置。具体来说，当数据库中的索引发生变化（例如添加新的索引、删除旧的索引或修改索引参数）时，传统的索引选择方法往往需要重新建立索引模型或者重新优化查询计划，耗费大量的时间和计算资源。然而，利用MCTS的增量更新方法，可以在不重新建模或者重新优化的情况下，快速地调整搜索策略，以适应新的索引配置。增量更新方法的基本思想是在原有的搜索树基础上，根据新的索引配置信息，动态地调整节点的选择概率和收益估计，以反映新的索引效果。通过在原有搜索树上进行局部的更新和调整，可以快速地适应新的索引配置，并继续搜索最优的索引解决方案。这种增量更新方法能够显著提高索引更新的效率和准确性，减少了重新建模或者重新优化的成本。第三，（+例子）指标与工作负载之间存在相关性，贪婪地选择高效益指标可能属于次优状态。例如，在TPC-DS中，在imactid和日期dim上分别创建索引可能有很小的好处（在爬山算法中直接下降）。相反，如果我们同时创建这两个索引，那么查询Q32的执行时间就会大大减少，因为只有当这两个索引可用时，在Q32中的子查询才会得到增强。
定义
MCTS [23]的核心思想是在策略树上搜索时，在开发（高收益）和探索（低频率）之间取得平衡，这有助于避免次优。要应用MCTS，第一步是定义策略树中节点效用。
节点效用：如果一个节点位于从根节点到最优节点的路径上，那么它就具有更高的节点效用。但是，由于每个节点可能有许多子节点，因此很难预测该节点是否在最优路径上。为了解决这个问题，给定一个节点，我们通过考虑两个主要因素来计算其节点效用：
- 节点效益$B(v_i)$。给定一个策略树，我们将节点$v_i$的全局节点效益定义为$v_i$或$v_i$的子节点的最高成本降低值，$B(v_i) = \begin{cases}
cost(W) - cost(W, I_i) & \text{leaf node} \
\max(cost(W) - cost(W, I_i)), \quad v_j \in V_i & \text{otherwise}
\end{cases}$，$V_i$表示$v_i$的后代节点。如果$v_i$是叶节点，则$B(v_i)$等于有、无当前索引配置的Workload下Cost的差值；否则，$B(v_i)$是其子节点的Cost提升的最大值。由于$v_i$可能有大量的子节点，我们随机探索几个基于$v_i$的叶节点或到达存储约束的子节点（例如，数十个索引的5个叶节点），以增强探索过程。
显然，我们希望以高效益访问节点。然而，估计的收益可能并不准确，如果我们总是访问这样的节点，我们可能会错过真正的最优节点。为了解决这个问题，我们还考虑了一个节点的访问频率，并平衡了收益和频率，以避免陷入局部最优或错误的方向。
- 探索频率$F(v_i)$。访问频率表示选择新子节点时节点vi的访问次数。除了节点的效益外，我们还倾向于选择很少被访问的节点，以尝试更多可能的索引，避免陷入局部最优。例如，在图4中，当从候选索引中选择时，如果我们贪婪地选择I3 c，我们只能进一步选择I1 c或I2 c作为存储限制。相反，I1 c和I2 c的组合可以获得更高的好处，因此我们需要尝试更少频繁地选择的节点。这样，我们将节点的效用定义为节点在从根节点到最优节点的路径上的概率的上限置信界（UCB），通过考虑节点利益$B(v_i)$和访问频率$F(v_i)$，
$U(v_i) = B(v_i) + \gamma \cdot \frac{\sqrt{\ln(F(v_0))}}{F(v_i)}$
，其中，$F(v_0)=\sum_{i \geq 1} F(v_i)$为总访问量，$γ$为调整未发现索引组合的探索量的探索参数。
基于MCTS的索引更新。如图所示，为了有效地更新所选的索引（已探索的节点）和探索新的索引（未探索的节点），完整的基于MCTS的索引推荐过程包括四个步骤。
第一步：Selection（选择）：在树中找到一个最优的值得探索的节点。通常情况下，首选未被探索过的子节点，如果所有子节点都已被探索，则选择具有最高UCB值的子节点。
第二步：Expansion（扩展）：在选定的子节点中，向前迈出一步，创建一个新的子节点。这个新节点代表了对索引空间的额外探索。通常，我们会采取随机操作的方式，并确保所选操作与已探索的路径不重复。
第三步：Simulation（模拟）：在新创建的扩展节点上，模拟游戏或应用场景，直到达到结束状态。在模拟的过程中，计算结束状态下索引配置的成本收益，以评估当前扩展节点的性能。
第四步：Backpropagation（更新）：将扩展节点的得分反馈到其所有父节点中，更新这些节点的质量值和访问次数。通过这种方式，我们不仅更新了已经探索过的节点的信息，还为未来的节点选择提供了更准确的指导。
通过这四个步骤，基于MCTS的索引更新过程能够有效地同时更新已探索的索引节点和探索新的索引节点，从而全面地探索索引空间，提高索引推荐的准确性和效率。
DTA等greedy的缺陷:
在DTA等传统的贪心算法中，单步最优的选择候选索引，会导致无法识别出一些索引的组合收益，如[I(C income_band.ib_income_band_sk), I(C catalog_sales.cs_ship_customer_sk), I(C date_dim.d_moy,C date_dim.d_year)]三个索引的单个收益分别为2.8、0.0、 36434。但是组合收益为63782。这三个优秀的索引不会被DTA选择到。传统的贪心算法可能无法识别出一些索引的组合收益，导致无法选择到潜在的更优秀的索引组合。这表明在处理索引推荐问题时，仅仅依赖单步最优的选择可能会忽略掉一些潜在的高收益索引组合，从而影响最终的性能表现。
MCTS的缺陷
- 计算成本高: MCTS在模拟阶段，需要大量的计算资源和时间来达到良好的性能。尤其是在搜索空间庞大或搜索树深度较大时，计算成本可能会显著增加。
- expand阶段：因为候选索引空间可能非常庞大，MCTS在扩展阶段会对所有没有探索过的节点进行扩展。这可能导致对很多无效的索引进行了扩展，因为其中某些索引可能不会在后续搜索中产生显著的性能提升。对所有未探索过的节点进行扩展可能需要大量的时间和计算资源。如果候选索引空间非常庞大，那么扩展所有节点可能会导致搜索过程变得非常耗时。扩展了大量无效的节点可能会分散搜索的精力，使得MCTS算法难以集中在潜在的高质量索引上。这可能会导致无法找到最佳索引或者陷入次优解。
- 采样偏差: MCTS使用随机采样来探索搜索空间，但随机性可能导致采样偏差。不同的随机采样可能导致不同的搜索结果，从而影响最终的决策。
我们的方案
为了解决上述基于MCTS的索引选择中的问题，我们提出了多种改进的策略。我们的策略有
1、模拟阶段引入索引动作能带来的潜在收益，使用Boltzmann探索，引导mcts向有价值的区域进行探索，
2、expand阶段，只选择前1/2个提升潜力值最大的节点进行扩展
3、使用超过提升潜力80%的查询组合进行reward计算，在保证效果的同时，可以有效的提升效率，极大的减少了what-if调用次数。我们将在接下来的部分详细介绍这些改进措施。
5.2 Selection
在这种情况下，你希望根据先验知识中提供的收益值来优先选择节点进行扩展，以便更加智能地探索搜索空间。
因此，在MCTS算法中，可以根据每个节点的收益值来选择需要扩展的节点。具体来说，可以按照收益值对所有未探索的节点进行排序，然后选择收益值较高的前1/2个节点进行扩展。这样做可以确保在有限的计算资源下，将重点放在对性能改进有更大希望的节点上，从而提高算法的效率。
尽管收益值是估计值并可能存在不确定性，但利用这些先验知识来指导节点扩展仍然是一种合理的策略，可以在搜索过程中提供更多的方向性和引导，有助于提高算法的性能。
5.3 Expansion and Stimulation
- 利用Boltzmann探索，引导mcts向有价值的区域进行探索
- 使用潜在收益的查询组合优化方法，减少what-if优化器的调用次数
- 根据节点的潜在收益值选择需要扩展的节点，提高搜索效率和准确性
Stimulation:
- （+ 例子-单个收益小的索引也能被识别为高潜力索引、而且具有随机性选择可以避免greedy无法识别组合收益的情况）将提升潜力大的索引进行优先组合，说明比DTA好的原因
在MCTS的模拟阶段中，首先，我们根据上文模型一获取每个候选索引对整个工作负载的潜在收益值-A。这个A反映了每个索引在当前工作负载下对性能的预期提升程度，是我们指导索引选择的重要线索。我们可以结合候选索引的潜在收益A和MCTS树的高度来进行Boltzmann探索。这样可以使得探索更加集中于具有更高潜力的区域，而不是随机地探索整个搜索空间。Boltzmann探索是一种基于概率的探索方法，它使用了一个称为Boltzmann分布的概率分布来选择动作。Boltzmann分布的公式如下所示：
$$
P(a_i) = \frac{e^{Q(a_i)/T}}{\sum_{j=1}^n e^{Q(a_j)/T}}
$$
在这个公式中，$P(a_i)$ 是选择动作 $a_i$ 的概率，$Q(a_i)$ 是动作 $ai$ 的价值（在索引选择中对应的是潜在收益-A），$T$ 是温度参数。温度 $T$ 控制了概率分布的形状，越高的温度值意味着更多的随机性，而较低的温度值则更倾向于选择具有较高价值的动作。在模拟阶段，我们根据每个候选索引的潜在收益（即 $Q(a_i)$）和MCTS树的高度来调整温度值 $T$。设计一个函数，将MCTS树的高度映射到温度值上。例如，可以使用线性或指数衰减函数，随着MCTS树的高度增加，候选索引的置信度逐渐降低，将温度值逐渐增大，从而增加随机探索的程度。这种方法充分利用了模型一中得到的每个候选索引的先验信息，引导mcts向更有价值的区域进行探索 ，会对潜力大的候选索引进行更多的探索，但也不忽略对潜力小的候选索引的探索，防止算法陷入局部最优解，尤其是在搜索空间庞大或者存在多个局部最优解的情况下。并结合了MCTS树的状态动态调整探索策略，（+为什高度越高，随机性越大），使得索引选择更加智能高效。Boltzmann探索算法的灵活性允许我们根据不同问题的特性和MCTS树的状态动态调整温度值，从而更好地平衡探索和开发，提高索引选择的效率和准确性
reward：
这里是query的potential+影响力，所以不会照顾不到没有选中的query
将重点聚焦于提升潜力大的查询
在MCTS的模拟阶段，面临的挑战之一是计算成本和资源消耗较高，主要源于每次探索都需要对整个工作负载的所有查询都进行一次成本收益也就是what-if优化器调用计算。在大规模查询和复杂工作负载下，这样需要调用大量的wha-if优化器。因此，我们提出了一种基于潜在收益的查询组合优化方法。具体而言，我们利用了先前模型得出的每个查询的潜在收益作为指导，在模拟阶段计算reward的时候，只选择潜在收益之和达到一定阈值的查询组合进行整体成本收益计算，例如，我们可以选择总潜在收益达到80%的查询集合进行计算。这一改进策略有效地减少了每次探索时what-if优化器的调用次数，提高了算法的效率，并在实验中取得了良好的性能表现。
然而，这种方法存在一个潜在的问题，即未被选中的查询无法得到优化。这可能导致一些查询无法获得性能提升，因为它们未被包含在计算中。针对这个问题，我们可以考虑一些额外的策略，如周期性地重新评估未被选中的查询，或者在每次迭代中随机选择一小部分未被选中的查询进行优化。这样可以确保整个工作负载中的所有查询都能得到一定程度的关注和优化，从而提高整体性能。
Expansion：
在节点的扩展阶段，mcts在继续向下扩展节点前会先探索完同一层的所有其他节点，由于候选索引的空间可能非常大，存在很多无效的候选索引是不需要进行选择的，所以当使用MCTS算法进行节点扩展时，我们可以根据上文获得的每个节点的潜在收益值来选择需要扩展的节点。具体来说，可以优先选择潜在收益值较高的节点进行扩展，以提高搜索效率和准确性。在实现中，可以将所有未探索的节点按照其潜在收益值进行排序，然后选择前1/2个提升潜力值最大的节点进行扩展，例如在候选索引个数为200的空间下，算法最终选择的索引个数一般不会超过50个。这样做可以确保在有限的计算资源下，将重点放在对性能改进最有希望的节点上，而忽略那些潜在收益值较低的节点，从而提高算法的效率。通过这种策略，MCTS算法可以更加智能地选择需要扩展的节点，从而更有效地探索搜索空间，提高问题求解的性能和准确性。
要点
- INCREMENTAL INDEX MANAGEMENT 动态性
- 针对组合收益的探索
- 模拟阶段为什么越低会越随机：影响力是对整个workload的影响，在后面可能建立了其他索引的基础上，这个影响力就没有一开始没有建立索引时那么准确
- 与DTA相比的优势怎么体现