SIGMOD 2026 | 北大×中兴提出 Divo：让查询优化器在多样化负载下保持稳定

按照计划生成策略的不同，学习型查询优化器（LQO）可分为生成式和引导式两类。生成式LQO如Balsa、LOGER等，直接生成执行计划而不依赖经验规则，其计划生成主要由一个延迟预测器（latency predictor）控制，该预测器预测子计划（subplan）的最小观测延迟，并通过强化学习迭代修正。引导式LQO如Lero、FASTgres等，则调用传统优化器（多为PostgreSQL的优化器）生成候选计划，再用计划比较器（plan comparator）从中选出最优，由于计划生成由传统优化器兜底，这类方法通常比生成式更稳定。

在训练充分的前提下，两类LQO在训练与测试使用相同查询模板时都能超越PostgreSQL优化器。然而当查询工作负载的多样性显著提升、更接近真实应用场景时，现有LQO普遍出现性能退化。图1展示了在由JOB、Extended JOB、DSB和Stack组成的混合负载上，各LQO相对PostgreSQL的加速比。实验中用一半的模板训练，其余模板用于测试。可以看到，生成式LQO连PostgreSQL一半的性能都达不到，而没有一种方法在未见过的测试负载上超过1倍加速比，这充分暴露了LQO在多负载学习上的困难。

图1：各LQO相对PostgreSQL的加速比（来源：原论文Figure 1）

近年来大语言模型（LLM）的进展揭示了训练数据的质量与多样性同模型性能之间的明确关联，因此提升训练查询与计划的有效性便成为一个自然的直觉。一个多样化的训练负载理应赋予LQO更充分的知识并带来更好的表现，但现有训练方案恰恰相反，面临三大挑战。

第一个挑战是缺乏多样且信息量充足的查询。最常用的负载如JOB、Stack等，只包含10到30个带复杂连接谓词的查询模板；DSB等基准虽然能从模板生成不同过滤谓词的查询，但这些查询往往信息量不足，因为同一模板下的大多数查询共享相同的最优连接顺序。例如DSB模板18的查询几乎都遵循先连接catalog_sales和date_dim、再连接item的近似最优连接顺序，无法提供超出模板本身的知识。因此，生成多样化模板的查询对LQO至关重要。同时，多项研究已经证明了保真度（fidelity），即合成数据与真实数据的相似性，对真实用户输入上的性能至关重要。一个查询生成器必须在规模上产出多样、信息充分且具有保真度的查询。

第二个挑战是计划探索与利用的障碍。LQO是从观测到的计划而非查询中学习来修正优化策略的，因此利用多样化训练查询本身就是一个关键问题。提升LQO需要从优于现有计划的执行计划中学习，这要求在指数级搜索空间中进行充分的探索，而大规模多样化的负载既给强化学习探索带来压力，又带来可观的开销。一个替代方案是提前为各查询收集子计划以绕过探索低效的问题，但收集到的观测延迟在训练中固定不变，会随着探索而逐渐过时，最终阻碍高效的计划生成。

第三个挑战是多样化训练查询的复杂分布。多样化训练负载虽然丰富了计划生成的知识，但延迟的量级差异会天然偏向延迟跨度大的查询，因为这类查询会产生更高的损失值。此外，延迟预测任务容易受到特征输入相同但延迟不同的情况影响。例如JOB的8c和8d两个查询具有相同的谓词选择性，但8c在PostgreSQL中约慢2倍，原因在于8c中连接ci与rt产生的数据量是8d的9倍。这种细微差异在查询之间间歇性显现，导致不一致的真值标签，最终破坏强化学习训练的稳定性。因此，一种能够灵活处理不一致性与固有偏置的训练方法对解决这些问题至关重要。

针对多样化训练查询缺失的问题，Divo提出模板演化查询生成器（template-evolving query generator），通过对现有负载执行连接图操作来合成新模板，并采用生成式与引导式混合的框架完成计划生成。图2展示了Divo的总体框架，包含模板演化查询生成、多样性增强的两阶段训练以及多样性感知损失三个部分。

图2：Divo框架总览（来源：原论文Figure 2）

Divo将查询模板建模为连接图（join graph）G，顶点集V包含所有表，边集E描述连接谓词。两个表只有当存在连接谓词（即E中存在对应边）时才能在不产生笛卡尔积的情况下连接，因此连接图结构决定了有效计划的搜索空间。基于查询与连接图的对应关系，对连接图的变换能生成语法上有效的查询表达式。Divo使用两类核心操作来改变模板的连接图结构。其一是归约（reduction），即从连接图中随机删除顶点形成子图；其二是组合（combination），即合并两个共享公共子图的连接图。图3展示了连接图表示以及归约与组合的示例。归约通过类似广度优先搜索的算法实现，时间复杂度为O（V+E），并天然保证所得子图的连通性，从而消除笛卡尔积。组合则直接合并两个连接图，并要求二者共享一个连通的最大公共子图以强化保真度。

图3：模板演化查询生成器示意（来源：原论文Figure 3）

在模板演化过程中，Divo采用加权采样策略，既能防止特定连接图被偏好从而保证查询多样性，又能保护对原始负载的保真度。每次迭代从工作负载中以权重采样模板并用归约或组合演化连接图，每个生成的连接图被赋予新的采样权重并加入负载供后续使用。其中参数λ控制模板保留的最小权重（实验中取1/3），γ控制权重分割比例（归约取1/2、组合取1/3）。此外，为给模板附加过滤谓词，Divo在生成过程中保留源模板的过滤谓词，并以0.25的概率将其替换为负载中同类型的另一个谓词。组合的保真度约束在JOB上有直观体现。JOB的1a与7a拥有一个不连通的最大公共子图，1a查询由it指定的电影，而7a查询的是出现在电影演员表中、由it指定的人物，二者合并很可能不在真实场景中出现；相比之下，1a与2a共享title与movie_companies的连通最大公共子图，都指向特定电影的片名与公司，可以安全合并。为此Divo设定了组合的规模阈值，若合并后连接图规模超出限制，则对其中一个做归约删除多余的表，既保留结构又维持保真度。

Divo将查询生成器应用于JOB与Extended JOB、DSB以及Stack三组负载，各生成1000条查询，最终得到3000条查询、覆盖1800个不同模板，为Divo提供了充分的训练知识。在性质上，归约与组合带来了查询级与负载级的双重多样性，且归约天然保证非空结果、连通性约束消除了笛卡尔积，从而保证了信息量与保真度。图4展示了在JOB上以最大连接图规模17生成10000条查询的实验结果，Divo在4.86小时内生成了5116个不同的连接图，多样性随时间近似线性增长，且连接图复杂度分布保持稳定。其中验证非空结果耗时4.01小时，占总运行时间的82.5%，共发现89条空查询，这些空查询因连接图归约的有效性保证而被削减。由于Divo将验证限制在连接图组合上，这一保证显著提升了整体效率。

图4：验证开销占比与不同规模连接图数量随时间的变化（来源：原论文Figure 6）

生成多样化查询只是第一步，如何有效地从这些查询中学习才是关键。Divo设计了多样性增强的两阶段训练管线：第一阶段一次性收集静态经验，第二阶段进行参数共享的强化学习训练，并进一步提出多样性感知的概率分布损失以稳定训练。

Divo的模型架构由三个组件构成：查询编码器（query encoder）、延迟预测器和计划比较器。查询编码器接收查询并输出表嵌入，供下游的延迟预测与比较任务使用，它沿用GLO的编码器，将查询与数据库统计信息嵌入为一张图，并用两层的Graphormer模型输出各表的顶点嵌入。延迟预测器采用四层的QueryFormer处理子计划的表示，将计划树森林聚合成输出嵌入向量，再经多层感知机得到该子计划最小观测延迟的预测。计划比较器同样使用QueryFormer获取每个计划的嵌入，比较Divo生成的计划与PostgreSQL默认计划，输出一个仅当生成计划更优时才小于0的标签。

在第一阶段，Divo从多样化查询中收集大量执行计划以建立静态经验集合S，这里的静态指完整计划拥有稳定的延迟值，无需在训练中更新。与需要持续更新最小观测延迟的子计划不同，完整计划具有确定的延迟值，不会因过时的生成策略而污染训练；同时预收集的计划可以在不同训练配置间复用而无需从头探索。具体实现上，Divo将生成查询与公开负载（JOB、DSB、Extended JOB、Stack）合并形成大规模负载，并将其切分为每100条查询一组的子集，分别收集计划。对每个子集，Divo通过强化学习探索生成完整计划并送入PostgreSQL获取执行时间，重复直到计划数量达到4000条的阈值，最终在所有子集上共收集了132000个计划形成静态经验集合。为缓解探索不足的问题，Divo在完成每个子集的收集后重置模型参数，避免部分或过时知识带来的污染。

在第二阶段，Divo以价值驱动的强化学习范式训练延迟预测器与计划比较器，并通过静态经验增强。关键设计是参数共享的模型架构：Divo的延迟预测器与计划比较器共享来自查询编码器的表嵌入，但使用各自任务专属的参数。图5对比了Divo与AlphaJoin、GLO的架构。AlphaJoin的延迟预测器与比较器完全独立、无法相互促进；GLO则用同一模型处理两个任务，延迟预测器直接复用于计划比较，导致比较器难以识别失败生成出的坏计划。Divo的设计让两个任务既相互增强，又能独立决策。

图5：Divo与AlphaJoin、GLO的模型架构对比（来源：原论文Figure 4）

参数共享架构的价值在于，Divo用静态经验中的完整计划以监督方式训练计划比较器，再通过共享查询编码器间接提升计划生成，从而避免了预收集子计划带来的过时策略问题。一个直观的例子是，PostgreSQL为JOB的17b查询建议了次优的第一步连接，产生4.2秒的延迟，而更优的选择只有2.5秒；若直接用于训练，这个次优观测会被永久固化。训练比较器则聚焦于始终有效的最终延迟，绕过了被淘汰策略的干扰。

针对多样化查询的复杂分布，Divo提出了多样性感知损失函数，以KL散度损失补充延迟预测的均方误差（MSE）损失。大多数生成式LQO使用MSE损失，它存在两个关键缺陷：其一是尺度相关的偏置，JOB中6c查询的延迟跨度在20到400毫秒，而DSB的q100超过2000毫秒，MSE会过度加权高量级误差而忽略小延迟查询的优化；其二是MSE无法处理特征相似但延迟不同的输入，如前述JOB的8c与8d。

在实现上，Divo假设最小延迟服从对数正态分布，因为执行代价大致与谓词选择性成正比。对于观测延迟为T的子计划，用均值为log10T、方差为σ平方的正态分布来描述其对数延迟。σ的取值通过收集DSB模板查询上PostgreSQL对数延迟的平均方差估算，得到约0.121，故实验中取σ为1/8。延迟值被离散为24个类别，由于实验中所有查询都能在10的6次方毫秒内完成，故假设对数延迟落在0到6区间，每个区间长度为0.25。例如当观测延迟为1031毫秒时，代表3.0到3.25区间的类别应具有最大概率。Divo为延迟预测器增加一个预测概率分布的辅助输出，以KL散度作为目标函数。概率分布带来了尺度不变性、对不一致标签的鲁棒性，并让隐状态更具信息量。

这一概率分布还进一步增强了计划比较。Divo的比较器预测生成计划与PostgreSQL默认计划的相对延迟分布，并计算相对延迟的数学期望来做细粒度决策，取代了Lero等的二分类比较。由于相对延迟带有指数增长的系数，Divo将比较的范围限制在一个有限区间内以避免数值爆炸。相比二分类标签，概率分布能够精确揭示计划间的性能差异，让Divo在选择输出计划时更加稳健。

在推理阶段，Divo沿用典型的强化学习搜索流程生成计划，并在必要时用比较器剔除坏计划。对每条查询，Divo从所有表未连接的状态开始，逐步枚举当前子计划可能的连接动作得到候选子计划集合，用延迟预测器预测各候选的最小观测延迟，选择预测延迟最低的子计划，重复直到生成完整计划。随后Divo调用PostgreSQL优化器得到默认计划，用比较器评估生成计划相对默认计划的延迟，选择更优者作为最终输出。这种生成式与引导式相结合的混合策略，使Divo既能享受生成式方法广阔搜索空间带来的高性能潜力，又能借助比较器兜底保证可靠性。

Divo在PostgreSQL上，以JOB、DSB、Extended JOB、Stack以及生成查询组成的复杂混合负载进行评估。实验设置了三种富有挑战性的负载划分：Mixed（各负载取一半模板测试、其余训练）、Gen-only（用生成查询测试、公开负载训练）以及Stack-only（用Stack测试、其他负载训练），测试集模板在训练负载中均不可见。主要指标是相对PostgreSQL的加速比，辅以几何平均相对延迟（GMRL）。对比方法包括生成式的Balsa、HybridQO、LOGER、GLO，引导式的Lero、FASTgres，以及计划比较器Eraser和动态负载扩展LIMAO。

表1：Divo与对比LQO在不同负载划分测试集上的性能（来源：原论文Table 1）

表1汇总了各方法的加速比与GMRL。在Mixed测试负载上，Divo取得1.33倍加速比，而表现最好的生成式LQO（GLO）仅0.37倍，Divo领先3.6倍；在Gen-only测试负载上，Divo为1.28倍，是表现最好的生成式LQO（LOGER的0.55倍）的2.3倍。在完全未见过的Stack测试负载上，Divo在不确定性较高时保守地回退到PostgreSQL的计划，取得1.00倍的加速比（与PostgreSQL持平），但仍优于所有生成式竞争者。图6展示了Gen-only测试负载上逐查询的相对延迟，Divo有效避免了坏计划的选择，偶发的失误并未削弱其在慢查询上的显著优势。

图6：Divo在Gen-only测试负载上逐查询的性能（按执行延迟排序）（来源：原论文Figure 5）

为确认对比LQO的性能退化是否源于挑战性的负载设定，实验还在两个简化负载上评估：JOB-Balsa（测试模板包含在训练负载中）与JOB-Half（仅用JOB查询、测试模板训练时不可见）。结果显示，在JOB-Balsa上所有竞争者都恢复了性能，而在更具挑战性的JOB-Half上大多数LQO仍略逊于PostgreSQL，但生成式与引导式方法的表现均优于多样化负载划分。这印证了性能退化主要源于处理多样化查询的能力不足，未见测试模板也起了部分作用。

表2给出了各方法的训练与推理开销。所有竞争者均训练60轮以保证公平。Balsa与HybridQO每轮训练耗时很高，Lero每轮从头重训练进一步增加了开销。Divo每轮训练仅18.1分钟，快于GLO的24.7分钟，因为静态经验可作为延迟查找表、减少冗余执行。虽然Divo需要约157小时（9416分钟）的一次性收集阶段，但这些经验可在不同配置间复用，不带来额外训练开销。推理时间上，Divo为0.91秒，与LOGER、GLO相当，明显低于Lero的3.96秒。

表2：各方法的训练轮数、数据收集开销、平均训练时间与推理时间（来源：原论文Table 2）

为验证Divo处理不同复杂度查询的能力，实验在逐步扩大的负载上训练并在Gen-only上测试。训练从3到6张表的查询开始，每16轮扩张一次训练负载，每次增加20条查询、连接图规模增大1，直到第120轮达到12张表。图7显示，初始以3到6张表训练的Divo平均加速比仅为0.65倍，随后逐步提升，最终在测试负载上达到1.12倍，印证了多样化训练查询覆盖复杂度谱系的必要性。

图7：随连接图规模增大Divo加速比的变化（来源：原论文Figure 7）

在动态负载切换场景中，Divo同样表现稳健。实验测试了两个动态设定：IMDB-LIMAO（两个基于IMDB的划分每5轮周期切换）和Mixed-Shift（训练测试负载在JOB、Extended JOB、DSB、Stack间周期轮换）。图8显示Divo在IMDB-1与IMDB-2上均持续提升。表3对比了LIMAO-Balsa：LIMAO-Balsa在部分重叠的IMDB查询上有竞争力，但在Mixed-Shift的完全不同负载间切换时难以适应，而Divo的计划比较器有效过滤坏计划、保持了更稳定的性能。值得注意的是，Divo在Mixed-Shift上的总测试集加速比为1.17倍，低于静态Mixed设定下的1.33倍，表明无法同时访问多个负载来源会限制动态场景下的表现。

图8：IMDB-LIMAO动态负载切换下的加速比（来源：原论文Figure 8）

表3：动态负载下Divo与LIMAO-Balsa的测试集加速比（来源：原论文Table 3）

消融实验验证了各组件的贡献，实验名称与说明见表5。图9对比了直接扩大训练负载与用静态经验增强两条路线，结果表明直接扩大训练负载不仅大幅增加训练开销，还会生成灾难性的坏计划，证明现有训练方法无法在大规模多样负载上正常工作。图10展示了生成计划相对延迟的百分比分布，从Gen-only子图可见，去掉静态经验后Divo无法削减坏计划、性能显著退化。从表4的数值看，随着静态经验从无到半再到完整，Mixed测试集加速比从1.12提升到1.21再到1.33。移除生成查询的静态经验（NoGen）使Mixed从1.33降至1.12、Gen-only从1.28降至1.16，凸显了模板演化查询生成器的关键作用。

图9：不同静态经验设计下Divo在Mixed测试负载的加速比（来源：原论文Figure 9）

图10：不同测试负载上生成计划相对延迟的百分比分布（来源：原论文Figure 10）

表4：消融实验结果（NoCmp列表示计划比较前的性能）（来源：原论文Table 4）

表5：消融实验名称与对应说明（来源：原论文Table 5）

在多样性感知损失上，图11显示移除KL散度损失（NoKL）后Divo几乎总是劣于原始版本，验证了KL散度损失在训练稳定性上的收益；而移除MSE损失（NoMSE）后，Divo即使配合计划比较也无法超越PostgreSQL，说明MSE提供的显式延迟预测对计划生成不可或缺。图12检验了架构选择：若复用延迟预测器做计划比较（单一模型），计划生成与比较可能同时失败，导致性能波动，印证了独立模型参数的必要性。

图11：移除KL散度损失或MSE损失后Mixed负载上的加速比（来源：原论文Figure 11）

图12：复用延迟预测器做计划比较时Mixed负载上的加速比（来源：原论文Figure 12）

学习型查询优化器按计划生成方式分为生成式与引导式两类。以ReJOIN和DQ为原型，Balsa、HybridQO、LOGER等生成式LQO通过连续选择连接操作来构造计划，并借助延迟预测器估计子计划的最小延迟；引导式LQO则调用底层传统优化器生成候选计划集，再由比较器选出最优，Bao通过禁用特定连接或扫描算子、Lero通过改变代价估计、FOSS通过修改候选计划来实现候选的多样化，GLO则借鉴这一思路在生成计划与PostgreSQL计划之间做选择。在合成查询生成方面，早期方法如RAGS和SQLSmith随机生成查询但无法产生LQO训练所需的多样连接谓词；TPC和DSB等模板方法通过参数化模板产生固定变体，但同一模板的查询通常共享最优计划；TreeGAN和LearnedSQLGen等学习方法虽然改进了生成质量，但需要额外的训练开销且主要产出低于3个连接的低复杂度查询。在深度强化学习方面，大多数生成式LQO采用深度Q网络（DQN）的改进实现，建立经验回放记忆以提升数据效率并降低样本相关性。Divo沿用了这一实现，并借鉴了以分类任务训练价值模型的研究思路，提出延迟分布的多样性感知损失。

Divo提出了一个建立在多样化工作负载之上的学习型查询优化器。其一，通过模板演化查询生成器对现有模板执行连接图操作，在规模上产出多样、信息充分且具有保真度的查询；其二，设计两阶段训练管线，通过参数共享的强化学习训练为Divo配备多样化的静态经验；其三，引入多样性感知的概率分布损失，在多样化查询上确保训练稳定并支持细粒度的计划比较。实验表明，Divo在三个富有挑战性的负载划分上整体不逊于PostgreSQL内置优化器（Mixed和Gen-only上优于，Stack-only上持平），且各组件对性能均有明显贡献。

Divo仍处于走向实用的进程中。作者指出，未来将探索更复杂的技术以加速推理、集成物理连接与扫描算子的选择以追求更高性能，并让Divo适配分布式数据库系统的场景。在多样化负载这一此前被低估的维度上，Divo迈出了重要一步，为学习型查询优化器的真实部署提供了可复用的训练范式。