ALECE：基于注意力的学习基数估计器，用于动态工作负载的 SPJ 查询（扩展）

摘要。

为了实现高效的查询处理，DBMS 查询优化器几十年来一直依赖于精细的基数估计方法。 在这项工作中，我们为 SPJ 查询提出了一种基于注意力的学习卡丁岛估计器（简称 ALECE）。 核心思想是使用 ALECE 两个模块中的注意力机制来发现查询和底层动态数据之间的隐式关系，这两个模块构建在精心设计的数据和查询特征之上。 特别是，从数据库中的所有属性中，数据编码器模块获得有机且可学习的聚合，隐式表示属性之间的相关性，而查询分析器模块在查询特征化和数据聚合之间建立桥梁以预测查询的基数。 我们在多个动态工作负载上对 ALECE 进行了实验评估。 结果表明，ALECE 使 PostgreSQL 的优化器能够实现近乎最佳的性能，明显优于其内置基数估计器和其他替代方案。

PVLDB参考格式：
李鹏飞、魏文清、朱蓉、丁柏林、周静仁、卢华。 ALECE：一种基于注意力的学习基数估计器，用于动态工作负载的 SPJ 查询。 PVLDB，17（2）：197 - 210，2023。

doi:10.14778/3626292.3626302

PVLDB 工件可用性：
源代码、数据和/或其他工件已在 %leave␣empty␣if␣no␣availability␣url␣should␣be␣sethttps://github.com 提供/pfl-cs/ALECE。

1. 介绍

DBMS 中的基数估计器（Selinger 等人，1979；Graefe 和 McKenna，1993） 在查询执行之前估计 SQL 查询的结果元素数量，从而帮助查询优化器生成良好的查询计划。 过去，基数估计的主流一直是统计数据驱动的方法。 此类方法将数据信息浓缩为轻量级摘要，例如，直方图、草图和数据分布近似，并采用以摘要为输入的分析函数来估计 SQL 查询 （Selinger 等人，1979 年；Kaushik 等人，2005 年；Zhu 等人，2021 年）。 然而，现实世界的数据集通常很复杂，并且分析函数通常不够强大，无法在粗略数据摘要和 SQL 查询基数之间建立正确的映射。 此外，SQL 查询通常包含连接谓词，但为每个连接构建特定的摘要既困难又耗时。 由于高计算和存储开销，计算联合数据分布通常也很棘手。

最近，传统的基数估计器已被基于学习模型的估计器所颠覆。 数据驱动模型（Yang 等人，2019；Hilprecht 等人，2020；Yang 等人，2020；Wang 等人，2021a）从底层数据库中学习更严格的数据分布，并使用分析表达式进行估计基数。 相比之下，查询驱动模型（Kipf等人，2019；Zhao等人，2022）以监督方式利用执行查询的反馈。 后者学习基数和查询分布之间的关系，而不需要特别关注底层数据库。 然而，这两种模型都不能充分利用数据和查询。 他们很难为不同的查询提取个性化的有用信息。 一些模型（Dutt等人，2019；Kipf等人，2019；Negi等人，2023）同时考虑数据和查询。 然而，它们要么只使用简单琐碎的数据信息，需要对关系进行采样操作（Kipf等人，2019；Wu and Cong，2021），要么不支持使用连接处理查询（ Dutt 等人, 2019) 或复杂连接 (Negi 等人, 2023)。

此外，现有模型还有一个更关键的问题：它们在以下方面表现不佳 混合查询和数据操作语句（包括插入、删除和更新）的动态工作负载。 此类语句往往会使估计变得困难，因为它们会影响数据分布并改变真实基数和查询分布之间的映射。 当底层数据发生变化时，关系和属性之间的联合数据分布以及查询和真实基数之间的映射也会变得不同。 因此，纯数据或查询驱动的方法很难适用于动态工作负载。 一些方法（Kipf等人，2019；Wu和Cong，2021）虽然同时考虑了数据和查询，但由于其所需的特征化或采样方法不支持模型，因此在动态工作负载上的性能也会下降通过数据更新进行训练和推理。 更重要的是，现有方法没有回答如何合理链接 SQL 查询和底层数据以及如何在真实基数、查询和数据之间构建适当的映射，尤其是当数据是动态时。

为了解决这些缺点，我们为选择项目加入（SPJ）查询设计了一个基于注意力的学习基数估计器（ALECE）。 图 1 描述了 DBMS 查询执行上下文中的 ALECE。

图1。 基于 ALECE 的查询执行。

ALECE 既是数据驱动的，也是查询驱动的。 当估计 SPJ 查询的基数时，它会无损地将查询特征化为向量。 同时，它有效地将数据库中当前的底层数据特征化为一组向量，称为DB states，从而“压缩”整个数据库。 查询和数据特征化的空间开销都很低，并且可以有效地计算。 在数据库状态和查询特征之上，ALECE 构建了一个基于神经网络的模型，以在它们之间创建合理的连接。 该模型集成了数据库状态和查询特征的信息，并将它们输入前馈回归神经网络进行估计。 粗略地说，ALECE 首先学习为原始数据库状态 $𝑿$ 分配不同的权重，每个权重显示 $𝑿$ 中两个元素之间的相关性。 这种相关性是一种有用的分布信息，可用于在 SQL 查询的基数与基础数据之间构建适当的映射。 然后，$𝑿$被映射到另一组向量$𝒁$，它们是$𝑿$的加权组合并且更好地表示底层数据。 ALECE 还为 $𝒁$ 中的每个映射向量 ${𝒛}_i$ 和查询特征化 $𝚚$ 学习另一个权重，以衡量 ${𝒛}_i$ 对 $𝚚$ 的影响。 $𝒁$ 的加权组合是数据库状态和查询特征的卷积。 组合向量最终用于生成基数估计。

我们的 ALECE 的设计遇到了两个挑战。 首先，我们需要构建适合处理动态工作负载中数据变化的数据库状态，同时使其能够高效访问。 为此，我们提出了一种简单而有效的数据特征化方法，该方法可以很好地近似数据分布，对数据变化敏感且计算效率高。 这种方法根据数据库关系中每个属性的直方图，构建基础数据（即，数据库状态）的简明摘要。 每次插入、删除或更新记录时，我们只需要修改与更改的关系相关的数据库状态向量。 此外，数据库状态涵盖了基本的单属性分布甚至联合分布。 这些因素共同使我们能够利用数据库状态处理动态工作负载。 此外，根据分布逼近精度的要求，可以灵活调整直方图中的bin数。 此外，如果需要，可以无缝集成与基础数据相关的其他有用信息。

其次，我们需要提取SQL查询和相应的数据库状态之间的隐式相关性，并使这些信息有助于基数估计。 为此，我们在模型中采用注意力机制（Bahdanau等人，2015；Vaswani等人，2017；Kim等人，2017）来绘制SQL查询和底层数据之间的全局依赖关系。 注意力机制广泛应用于包括问答在内的各种任务（Hermann等人，2015；Sukhbaatar等人，2015）。 一般来说，它使用注意函数模拟从集合中进行选择的过程，该注意函数将两个主要组成部分作为输入：一组查询和一组键值对。 它以个性化的方式计算出数据的哪些部分对于不同的查询起着更重要的作用，为每个查询的更重要和相关的键分配更高的权重，并输出加权值的组合。 与数据库中的概念不同，注意力中的查询是我们需要学习表示的特定元素，键的作用是或多或少地响应查询，值用于组成答案。 尽管如此，选择过程与我们的设置完全匹配，其中 SQL 查询和底层数据分别类似于注意力中的查询和键值对。

我们的 ALECE 有两个模块，其中注意力的使用方式不同。 一方面，“数据编码器”模块使用自注意力机制，其查询、键和值的输入均来自数据库状态。 自注意力允许对应不同属性的数据库状态相互交互。 通过使用自注意力，数据编码器模块学习属性之间的隐式联合分布信息，并计算底层数据的更智能的表示。 另一方面，在“查询分析器”模块中，注意力的查询集恰好是仅覆盖 SQL 查询的一个特征向量的集合，而键和值来自数据编码器模块的输出。 查询分析器模块输出一个固定维度的“回答”向量，集成了查询和数据表示的信息。 然后，我们使用简单的线性回归模型将答案向量映射到基数估计。

与最先进的基数估计方法相比，ALECE 能够更合理地利用查询和基础数据。 在这两个注意力的帮助下，它回答了“SQL查询应该更关注数据的哪些部分？”和“如何找到更重要的数据？”属性。 此外，连接条件使特定元组对基数贡献更大。 此外，ALECE 能够适应动态工作负载。 在实践中，学习模型需要使用过去的查询和相应的数据库状态进行训练，并估计未来查询的基数。 在动态数据库上进行预测时，现有查询驱动模型的性能通常会急剧下降。 相比之下，ALECE可以通过修改数据库状态对数据变化做出立即、适当的反应，并学习真实基数和伴随相应数据库状态的查询特征之间的适当但隐式的映射。 我们的实验结果表明，即使基础数据的分布发生变化，ALECE 也能够做出准确的估计。 因此，ALECE 对数据更改不太敏感。

在我们的评估中，ALECE 在多个动态工作负载上实现了最佳基数估计性能。 实验结果表明，ALECE 在基准工作负载上将平均端到端查询时间提高了$2.7\times$，非常接近使用真实基数获得的最佳结果。 这表明我们的 ALECE 可以做出更准确的基数估计，并帮助查询优化器找到更好的查询计划。

我们在本文中做出了以下主要贡献：

• 我们提出了一种表征底层数据库数据和 SPJ 查询的方法的必要原则。 因此，我们设计了一种特征化模式来无损地特征化 SPJ 查询并对数据进行合理的压缩。 可以有效地更新特征以支持动态工作负载。

• 基于查询和数据的特征，我们提出了一种基于注意力的学习基数估计器 ALECE，并进行了详细分析。

• ALECE 被设计为一个“白盒”，它不仅提供估计值，还提供在处理动态工作负载时将 SPJ 查询和基础数据集成在一起的明确原理。

• 我们在真实数据集上通过实验验证了 ALECE 相对于六种以上代表性替代方案的优势。

本文的其余部分安排如下。 2 部分给出了初步知识。 3 部分介绍了数据和查询的特征。 4 节详细阐述了 ALECE，随后在 5 节中对其进行了分析。 6 部分报告了实验研究。 7 节回顾了相关工作。 8 部分总结了本文。 另外，由于篇幅限制，我们在附录中介绍了我们开发的基准测试，它将ALECE集成到PostgreSQL的查询优化器中，以及更多的实验分析。

2. 初步知识和问题

表1列出了本文中使用的重要符号。

表格1。 符号

$R_i$	A relation in the database
$A_j^i$	The $j$th attribute of the relation $R_i$
$N$, $T$	The number of relations/attributes in the database
$𝑿={\left\{{𝒙}_i\right\}}_{i=1}^T$	The set of data featurizations (a.k.a. DB states)
$d_x$	The number of histogram bins (dimensionality) for a DB state
$𝚚=⟨{𝚚}_{𝑱},{𝚚}_{𝑭}⟩$	A SQL query and its vectorized featurization
$d_q$	The dimension of a query featurization vector
$n_{\mathrm{𝖾𝗇𝖼}}$, $n_{\mathrm{𝖺𝗇𝖺}}$	The number of attention layers in the data-encoder/query-analyzer module
$𝑲,𝑽,𝑸$	The input keys/values/queries of an attention function

2.1. 基数估计问题

假设数据库$𝐃$有一组关系$\{R_1,\mathrm{\cdots },R_N\}$。 关系$R_i$具有$n_i$属性，即、$R_i=(A_1^i,\mathrm{\cdots },A_{n_i}^i)$。 每个属性$A_j^i$可以是分类或数值：分类属性的域是有限集，可以一对一映射到整数集$\{1,\mathrm{\cdots },{\mathrm{𝗆𝖺𝗑}}_j^i\}$；数字的定义域是$[{\mathrm{𝗆𝗂𝗇}}_j^i,{\mathrm{𝗆𝖺𝗑}}_j^i]$。

问题表述。 给定一个 SQL 查询 $𝚚$ 和一个动态数据库 $𝐃$，我们想要估计 $𝚚$ 的 基数，表示为 $𝖼(𝚚,𝐃)$,即，在$𝐃$上执行$𝚚$时生成的元组数量。

在本文中，我们重点关注带有联合过滤谓词的 select-project-join SQL 查询；基数$𝖼(𝚚,𝐃)$是连接和过滤后元组的数量，如以下计数查询：

(1) $𝖼(𝚚,𝐃):$ $\mathrm{𝚂𝙴𝙻𝙴𝙲𝚃}\mathrm{𝙲𝙾𝚄𝙽𝚃}(\ast )\mathrm{𝙵𝚁𝙾𝙼}{R}_{i_1},\mathrm{\cdots },R_{i_n}$

$\mathrm{𝚆𝙷𝙴𝚁𝙴}\mathrm{𝚓𝚘𝚒𝚗}\mathrm{𝚙𝚛𝚎𝚍𝚒𝚌𝚊𝚝𝚎𝚜}𝑱\mathrm{𝙰𝙽𝙳}\mathrm{𝚏𝚒𝚕𝚝𝚎𝚛}\mathrm{𝚙𝚛𝚎𝚍𝚒𝚌𝚊𝚝𝚎𝚜}𝑭$

其中$𝚚$涉及$n$关系$R_{i_1},\mathrm{\cdots },R_{i_n}$，以及一组连接谓词$𝑱$，它是连接条件的合取，每个连接条件的形式为“$R_i.A_x^i=R_j.A_y^j$”，以及过滤谓词的连词$𝑭$。 这个公式使我们不仅可以支持 PK-FK 连接，还可以通过在 $𝑱$ 中的可连接属性对（可能是也可能不是主键/外键）上指定连接谓词来支持更通用的连接。 过滤谓词是“$R_i.A_j^i\mathrm{𝚘𝚙}\mathrm{𝖼𝗈𝗇𝗌𝗍}$”形式的关系表达式，其中和$\mathrm{𝖼𝗈𝗇𝗌𝗍}$是固定值。 在 $𝚚$ 中，属性可以出现在连接谓词或过滤谓词中，或者同时出现在两者中。 对 $\mathrm{𝙻𝙸𝙺𝙴}$ 谓词的支持留待将来的工作。

SPJ 查询优化中的 ALECE。 (1) 格式的查询计数估计结果可用于支持更复杂查询的优化，例如、广泛使用的SPJ (select-project-join) 按以下格式查询：

(2) ${𝚚}_{\mathrm{𝖲𝖯𝖩}}:$ $\mathrm{𝚂𝙴𝙻𝙴𝙲𝚃}{\mathrm{𝙰𝙶𝙶}}_1,\mathrm{\cdots }{\mathrm{𝙰𝙶𝙶}}_m\mathrm{𝙵𝚁𝙾𝙼}{R}_{i_1},\mathrm{\cdots },R_{i_n}$

$\mathrm{𝚆𝙷𝙴𝚁𝙴}\mathrm{𝚓𝚘𝚒𝚗}\mathrm{𝚙𝚛𝚎𝚍𝚒𝚌𝚊𝚝𝚎𝚜}𝑱\mathrm{𝙰𝙽𝙳}\mathrm{𝚏𝚒𝚕𝚝𝚎𝚛}\mathrm{𝚙𝚛𝚎𝚍𝚒𝚌𝚊𝚝𝚎𝚜}𝑭$

$\mathrm{𝙾𝚁𝙳𝙴𝚁}\mathrm{𝙱𝚈}\mathrm{𝚊𝚝𝚝𝚛𝚒𝚋𝚞𝚝𝚎}\mathrm{\_}\mathrm{𝚜𝚎𝚝}\mathrm{\_}\mathrm{𝟷}\mathrm{𝙶𝚁𝙾𝚄𝙿}\mathrm{𝙱𝚈}\mathrm{𝚊𝚝𝚝𝚛𝚒𝚋𝚞𝚝𝚎}\mathrm{\_}\mathrm{𝚜𝚎𝚝}\mathrm{\_}\mathrm{𝟸}$

其中每个 ${\mathrm{𝙰𝙶𝙶}}_k$ ($k=1,\mathrm{\cdots },m$) 是一个或多个属性的聚合函数，这些属性可以是 $\mathrm{𝙲𝙾𝚄𝙽𝚃}$、$\mathrm{𝙰𝚅𝙶}$、$\mathrm{𝙼𝙸𝙽}$ 和 $\mathrm{𝙼𝙰𝚇}$、etc，或者可以简单地省略。 连接谓词集$𝑱$和过滤谓词集$𝑭$与(1)中的含义相同。

为了搜索最佳执行计划，像 PostgreSQL 这样的现代 DBMS 的查询优化器首先将 ${𝚚}_{\mathrm{𝖲𝖯𝖩}}$ 按某种固定顺序（隐式）分解为一系列子查询 （Han 等人，2021） 。 然后使用内置估计器估计这些子查询的基数。 因此，枚举候选查询执行计划，并且还使用固定成本模型来计算给定基数估计的它们的估计执行成本。 选择具有最小估计成本的计划来物理执行查询。 显然，查询${𝚚}_{\mathrm{𝖲𝖯𝖩}}$的执行性能基本上由其子查询的基数估计决定。 我们的 ALECE 的设计使其能够提供更准确的估计。 我们开发的基准测试可以将外部基数估计器插入优化器以取代内置基数估计器。 因此，ALECE能够改进${𝚚}_{\mathrm{𝖲𝖯𝖩}}$子查询的基数估计，并进一步使查询优化器能够选择一个好的执行计划。

ALECE 适用于优化更复杂的查询。 对于它支持的子查询，它给出了更好的基数估计；对于ALECE不支持的子查询，优化器仍然可以使用其默认的基数估计器。

动态工作负载的估计模型。 实际上，DBMS 中的数据很少是静态的，而是经常不断更新。 因此，设计能够准确估计动态工作负载的基数估计器是有益的，即包括查询、插入、删除和更新的 SQL 语句序列。 我们的 ALECE 旨在支持动态工作负载，并在工作负载期间随时为查询提供最新的基数估计。

对于学习基数估计器来说，无需重新训练即可处理基础数据分布的频繁变化，一个简单的想法是使用数据库 $𝐃$ 本身作为输入特征的一部分来训练估计模型。 然而，这是不可行的，因为 $𝐃$ 的大小可能很大并且不断变化。 相反，我们使用数据库的简洁摘要(例如，固定大小的直方图），称为数据库状态，作为训练 ALECE 输入特征的一部分。 当数据库$𝐃$更新时，数据库状态应该相应地（并且有效地）更新，以便它们可以被输入到经过训练的模型中以产生基数估计。 有关将 $𝐃$ 特征化为数据库状态的详细信息，请参见第 3.1 节。 我们假设 $𝐃$ 的模式是静态的。 对动态模式的支持留待将来的工作。

2.2. ALECE 概述

ALECE的模型结构及其在查询引擎中的作用概述如图1所示。 动态数据和查询的特征由 ALECE 中的两个模块解耦和处理。 data-encoder 模块采用 DB 状态的自注意力结构来找出所有属性之间的相关性并学习它们的联合分布，而 query-analyzer 模块采用数据查询交叉注意力，用于发现数据编码器的输出和（子）查询的基数之间的相关性。 ALECE 中的查询分析器最终生成的基数估计取决于数据（数据库状态）和查询。

离线训练。 训练 ALECE 需要一个查询数据集、它们的真实基数以及执行这些查询时相应的数据库信息。 训练数据集是通过收集一段时间内在动态数据库上执行的历史查询的真实基数来获得的。 我们首先通过生成一组具有固定维度的向量(即，数据库状态）来对初始数据库进行特征化（第3.1节）。 SQL 工作负载中的语句是按顺序处理的。 对于插入、删除和更新语句，我们相应地修改数据库状态。 当查询到来时，它也会被特征化为具有固定维度的向量（第 3.2 节）。 查询特征和当前数据库状态将打包在一起作为训练样本，并以真实基数作为其标签。 收集足够的训练样本后，ALECE 使用梯度下降方法进行训练。

在线估算。 训练有素的 ALECE 可以对静态和动态工作负载进行在线估计。 给定一个新查询，我们将其特征化和最新的数据库状态输入 ALECE 以获得估计值。 如果工作负载是静态的，即，它不包含数据更新语句，则数据库状态是恒定的。 否则，数据库状态会不断变化，并且将始终使用最新的状态。

3. 数据和查询的特征

底层数据库数据和 SQL 查询需要以数字方式进行特征化，以便我们的 ALECE 可以处理。 任何特征化方法只要满足一定的原则，都可以被ALECE灵活采用。 首先，需要将底层数据特征化为一组覆盖足够分布信息的固定维度向量。 其次，任何 SPJ 查询都应该无损地映射到固定维度的向量，以便 ALECE 可以更好地理解它。 此外，为了有效支持动态工作负载，特征化方法应该高效且存储开销低。 遵循这些原则，我们提出了一种以数字方式表征数据库数据和 SQL 查询的方法。 详细信息分别在3.1和3.2节中给出。 此外，第 3.3 节讨论了我们的特征化方法的属性以及它如何帮助处理动态工作负载。 值得注意的是，我们的特征化方法是专门为 ALECE 设计的，它完全符合 ALECE 输入的要求。

3.1. 数据特征化

在我们的设置中，数据特征化$𝑿$，也称为“数据库状态”，是对整个数据库的压缩，可以粗略地描述每个属性的数据以及它们之间的关系。 我们的 ALECE 要求数据特征化是一组相同维度的向量。 这里我们使用每个属性的直方图集作为数据库状态，即 $𝑿=\{{𝒙}_1,\mathrm{\cdots },{𝒙}_T\}$，其中${𝒙}_i$是$i$的直方图>th 属性，$T={\sum }_{i=1}^N{n}_i$ 是数据库中所有属性的数量。 如何对$T$属性进行排序将在3.2节中介绍。 这种特征化方法简单但功能强大，我们可以有效地访问和更新直方图。

特别是，分类属性的值首先被转换为从 1 开始编号的连续整数。 给定属性 $A_i$，如果 $A_i$ 是分类的，我们使用 $\mathrm{𝖽𝗈𝗆}(A_i)$ 来表示其域或转换后的整数集。 很容易证明 $\mathrm{𝖽𝗈𝗆}(A_i)\subseteq 𝖣(A_i)=[l,u)$ 其中 $l=inf\mathrm{𝖣𝗈𝗆}(A_i)$ 和 $u=sup\mathrm{𝖣𝗈𝗆}(A_i)+ϵ$ 与 $ϵ$$\to$$0^{+}$。 然后，给定时间戳 $t$ 和 $t$ 处的数据库数据，我们为每个 $A_i$ 创建一个 ${𝒅}_{𝒙}$-bin-histogram。 特别是，令 $a=\frac{u-l}{d_x}$ 和 ${\beta }_j$ 为 $1\le j\le d_x$ 的 $[l+(j-1)\cdot a,l+j\cdot a)$ 中 $A_i$ 值的数量，可以使用 ${𝒙}_i=[{\beta }_1,\mathrm{\cdots },{\beta }_{d_x}]$ 轻松访问属性 $A_i$ 的直方图 ${𝒙}_i$。 我们的数据库状态在任何时候都只是一组 $T$ 元素，每个元素都是一个 $d_x$-dim 直方图向量。 实际上，所有直方图向量中的每个${\beta }_i$都将通过适当的仿射变换缩放到范围[0, 1]。 $d_x$的值可以根据数据分布的复杂程度灵活修改。 显然，较大的 $d_x$ 将使数据特征化捕获更多属性之间的分布信息，但会导致额外的时间和存储开销。 通常，当属性之间存在较强的相关性时，$d_x$倾向于使用较大的值。

3.2. 查询特征化

继并扩展现有工作（Zhao等人，2022；Wang等人，2021b），我们将SQL查询$𝚚$特征化为固定长度向量$𝚚$. 它是两个单独生成的部分 ${𝚚}_{𝑱}$ 和 ${𝚚}_{𝑭}$ 的简单串联，分别具有连接谓词 $𝑱$ 和过滤谓词 $𝑭$ 的特征。

加入特征化。 对于从 1 到 $N$ 编号的 $N$ 关系，我们使用 $m_1=\lceil {\log }_2(N+1)\rceil$ 位来表征每个关系的 id。 类似地，$m_2=\lceil {\log }_2(n_{max}+1)\rceil$位可以表征任何关系中所有属性的id，其中$n_{max}=\max (\{n_1,\mathrm{\cdots },n_N\})$是关系中属性的最大数量。 因此，任何属性$R_i.A_j^i$都可以用维度$m=m_1+m_2$的二元向量唯一标识。 第一个$m_1$维和最后一个$m_2$维子向量分别标识关系和属性。 然后，连接谓词 $P$ 由 $2m$-dim 二进制向量 $E_J(P)$ 表征，前半部分和后半部分子向量分别指左侧和右侧分别为$P$。

假设有 $\mathrm{\Delta }$ 种可能的连接模式，SQL 查询 $𝚚$ 的连接特征 ${𝚚}_{𝑱}$ 是一个 $(2m\cdot \mathrm{\Delta })$-dim 二进制向量，包含$\mathrm{\Delta }$ $2m$-暗淡子向量，指示哪些连接模式$𝚚$覆盖并表征其引用的属性。 如果 $𝚚$ 的连接谓词包含第 $i$ 个连接模式 $P_i$，则 ${𝚚}_{𝑱}$ 的第 $i$ 个子向量等于 $E_J(P_i)$。 否则，该子向量被设置为零。 通常，$\mathrm{\Delta }$的值并不大，与属性的数量近乎线性相关（吴等人，2023；朱等人，2021）。 与简单地表征每个连接条件是否出现在查询中的现有工作（Zhao等人，2022）不同，我们的特征化方式更加紧凑，并包含更多有关连接的有用信息。

在实践中，我们将连接谓词左侧和右侧的属性定义为“等效”，并在 $𝑱$ 中查找所有等效类。之后，我们根据等价类重新组织连接谓词。 给定一个等价类 $C=[A_1,\mathrm{\cdots },A_t]$ 包含 $t$ 属性（按 $m$ 的特征排序），我们重新创建 $(t-1)$ 连接谓词，其中 $i$ 连接谓词是 $A_i=A_{i+1}$。 通过对每个等价类执行此操作并将相应的连接谓词打包在一起，我们生成一个新的连接谓词集${𝑱}^{\mathbf{\prime }}$。 连接特征化实际上是使用 ${𝑱}^{\mathbf{\prime }}$ 而不是 $𝑱$ 执行的。 这样，两个具有显式不同形式的等价连接谓词集将被特征化为相同。 例如，在以下公式中，连接谓词集 ${𝑱}_{\mathrm{𝟏}}$ 和 ${𝑱}_{\mathrm{𝟐}}$ 都有两个相同的等价类。 它们将被转换为另一组${𝑱}^{\mathbf{\prime }}$。

滤波器特征化。 我们根据所有属性的 $m$-dim 特征对所有属性进行排序，并使用 $A_k$ 表示 $T$ 属性中的第 $k$ 属性。 不失一般性，我们假设每个属性 $A_k$ 的 $𝖣(A_k)$ 是 $[0,1)$。 因此，产品空间$𝖣(A_1)\times \mathrm{\cdots }𝖣(A_k)\times \mathrm{\cdots }\times 𝖣(A_T)={[0,1)}^T$。显然，过滤谓词$𝑭$相当于一个超矩形$[l_1,u_1)\times \mathrm{\cdots }[l_T,u_T)$，它是${[0,1)}^T$的子集。特别是，对于属性 $A_k$ 上的任何过滤条件，我们将其转换为类似 形式的等效条件。 然后，将$l_k$和$u_k$的值分别设置为$lb$和$ub$。 具体来说，

上面的 $\sim$ 表示等价运算符。

因此，过滤器谓词${𝚚}_{𝑭}$的特征化是由搜索超矩形的边界点组成的$2T$-dim向量，即 $E_f=[l_1,u_1,l_2,u_2,\mathrm{\cdots },l_T,u_T]$。 实际上，每个 $l_i$ 和 $u_i$ 将被标准化为 [0, 1]。

串联。 通过连接${𝚚}_{𝑱}$和${𝚚}_{𝑭}$，我们得到了SQL查询$𝚚$的$d_q$-dim特征向量。图2展示了一个例子。

$\text{SQL query}𝚚:$	$\mathrm{𝚂𝙴𝙻𝙴𝙲𝚃}\ast \mathrm{𝙵𝚁𝙾𝙼}{𝚁}_{\mathrm{𝟷}},{𝚁}_{\mathrm{𝟸}},{𝚁}_{\mathrm{𝟹}},\mathrm{\cdots }\mathrm{𝚆𝙷𝙴𝚁𝙴}$
	$R_1.A_1^1=R_2.A_1^2\mathrm{𝙰𝙽𝙳}{R}_2.A_2^2=R_3.A_3^3\mathrm{𝙰𝙽𝙳}\mathrm{\cdots }$
$\text{Featurization}𝚚:$ $\text{with}{m}_1=m_2=2$

图 2. 查询特征化的示例。

3.3. 讨论

3.3.1. 特征化属性。

正如我们所声称的，我们特征化数据库数据和 SQL 查询的方法具有以下属性：

1）效率。 构建静态数据库的数据特征只需要检查每个关系一次。 插入/删除/更新语句仅影响一个关系，修改相关直方图需要 $O(v)$ 时间，其中 $v$ 是涉及的记录数。 特征化 SQL 查询的时间复杂度为 $O(|𝑱|+|𝑭|)$，该时间复杂度很小，通常可以忽略。

2) 空间开销低。 DB 状态仅包含 $T\cdot d_x$ 浮点数。 在实际应用中，我们通常将$d_x$设置为小于100。 查询特征化的维度是$2m\cdot \mathrm{\Delta }+2T$。 通常，$m$的值较小。 在我们的实验中，$m$ 小于 10。 我们基于等价类重新生成连接谓词的方法通常会减少可能连接的数量 $\mathrm{\Delta }$。 此外，连接往往在具有主键的属性上执行。 根据我们的观察，$\mathrm{\Delta }$ 通常小于 $N^2$，并且在 8 关系数据库上进行查询需要少于 1000 个浮点数。

3）稳定性。 无论数据库或查询如何变化，数据和查询特征的维度都是固定的。 这确保了可以使用学习模型轻松处理特征。

3.3.2. 为什么我们的特征适用于动态工作负载？

值得注意的是，无论底层数据如何变化，给定查询的特征化都不会改变。 相反，DB状态会随着数据库中数据的变化而变化。 它是对整个数据库的压缩，能够捕捉到每个属性的分布特征。 我们的模型将两个特征作为输入，并且能够将查询特征与数据库状态进行“卷积”。 因此，当数据发生变化时，它可以做出正确的反应，并对具有不同数据库状态的同一查询给出不同的预测。 附录中第 6 节和第 C 节中的实验表明，我们的模型在静态和动态工作负载上均优于其他最先进的方法。

4. ALECE的设计

给定数据库状态 $𝑿$ 和 SQL 查询特征 $𝚚$，我们的 ALECE 可以合理地发现基数估计所需的它们之间的隐式关系。 背后的奥秘在于我们的 ALECE 中两次使用的注意力机制（Vaswani 等人，2017）。 在本节中，我们将回顾 ALECE 的设计动机，介绍 ALECE 的详细信息，包括分别处理 $𝑿$ 和 $𝚚$ 的两个模块，以及 ALECE 的训练过程。

4.1. 动机和 ALECE 概述

注意力函数将查询和一组键值对映射到输出，其中查询、键、值和输出都是向量（Vaswani等人，2017）。 这里，键值对和查询的概念可以类似于检索系统。 以用户在亚马逊等电商平台上的搜索行为为例。 当搜索引擎收到查询（搜索栏中的文本）时，它会将查询映射到与值（候选项目）关联的一组键（项目名称、标签和描述，等)在数据库中并输出最匹配的项目。 输出是值的加权和，其中每个权重由测量查询和键之间的相关性的兼容性函数计算。

注意力机制背后的思想是对输入键值对集进行编码，并以灵活的方式利用键中与值关联的最相关部分进行查询。 通过所有编码输入向量的加权组合，该机制用最相关的向量获得最高权重来“回答”查询。 这个想法非常适合我们的研究问题，因为 SQL 查询的特征 $𝚚$ 是一个自然的查询向量。 此外，DB状态$𝑿$可以看作是上例中的项目信息，并用作注意力函数中的键和值。 因此，我们扩展了这个想法并设计了 ALECE，它充分利用注意力机制来准确估计动态工作负载上 SQL 查询的基数。 图3说明了ALECE的结构。

图 3. ALECE结构。

我们基于注意力的模型 ALECE 的设计就像一个软查找表。 它使用 $𝚚$ 转换中的特征作为索引，从更好地代表数据库状态 $𝑿$ 中获取信息。 它由两个模块组成。 左侧的data-encoder模块将$𝑿=\{{𝒙}_1,\mathrm{\cdots },{𝒙}_T\}$映射到另一组表示$𝒁=\{{𝒛}_1,\mathrm{\cdots },{𝒛}_T\}$。 它通过一堆自注意力层计算任意一对数据库状态之间的相关性，从而学习所有属性之间的隐式联合分布信息。 该分布信息体现在集合$𝒁$中。 给定$𝒁$，右侧query-analyzer模块采用另一堆注意力层来衡量查询特征$𝚚$和$𝒁$之间的相关性>，并生成“答案”向量$𝒚$。 最后，向量 $𝒚$ 被输入线性回归层，并且估计并返回给定数据库状态 $𝑿$ 的 $𝚚$ 基数。

表 2. ALECE 两个模块的整体情况，给定数据库状态 $𝑿$ 和 SQL 查询特征 $𝚚$

Data-encoder (Self-attention)			Query-analyzer (Data-query cross attention)
Input source	What to learn?	Output	Input source	What to learn?	Output
Keys: $𝑿$ Values: $𝑿$ Queries: $𝑿$	Relevance among the DB states $𝑿$, and thus the joint distribution inf- ormation of multiple attributes.	Another vector set $𝒁$ cov- ering joint distribution information of attributes	Keys: $𝒁$ Values: $𝒁$ Queries: $𝚚$	Relevance between $𝚚$ with the ele- ments in $𝒁$, showing which parts of data are more important.	Final ‘answering’ vector $𝒚$ wh- ich will be directly turned into the cardinality estimate $𝖼$.

4.2. ALECE注意事项

注意背景。 在展示 ALECE 中的数据编码器和查询分析器模块之前，有必要简单介绍一下注意力机制。 在神经网络中，注意力是一种旨在模仿认知注意力的技术。 其背后的动机是网络应该更多地关注数据的重要部分，而不是平等对待所有数据。 它使用注意力函数来发现应该强调数据的哪些部分。 该函数将一个查询和一组键值对映射到一个输出，该输出是值的加权和。 通常，该函数使用某种度量计算每对查询和键之间的相似性（相关性），并使用它来生成分配给相应值的权重。

我们的 ALECE 使用“缩放点积注意力”(Vaswani 等人, 2017)，即 $\mathrm{𝖠𝗍𝗍𝗇}$，作为来自数据编码器和查询分析器模块。 输入键和值分别打包成维度为 $S\times d_k$ 和 $S\times d_v$ 的矩阵 $𝑲$ 和 $𝑽$，其中 $S$表示原始键值对集合的大小。 $d_k$-dim 查询向量转换为 $1\times d_k$ 矩阵 $𝑸$。 函数$\mathrm{𝖠𝗍𝗍𝗇}$计算给定查询$𝑸$与所有键$𝑲$的点积，将每个除以$\sqrt{d_k}$，并应用softmax函数获取值 $𝑽$ 的权重：

$\mathrm{𝖠𝗍𝗍𝗇}(𝑸\mathbf{,}𝑲\mathbf{,}𝑽)$ $=\text{softmax}\left({\displaystyle \frac{𝑸\cdot {𝑲}^T}{\sqrt{d_k}}}\right)𝑽$

上面的点积用作相似性度量。 为了防止点积变得太大而导致 softmax 函数的梯度“消失”，我们将点积除以因子$\sqrt{d_k}$。 实际上，函数$\mathrm{𝖠𝗍𝗍𝗇}$是通过批量查询同时计算来提高效率的。 在将输入输入到$\mathrm{𝖠𝗍𝗍𝗇}$之前，我们采用多头投影机制（Vaswani等人，2017）首先使用$h$不同的线性投影。 该操作能够增强ALECE的表示能力。 由于篇幅限制，更多详细信息在附录A部分给出。

ALECE的两个模块中的注意点。多头注意力层在 ALECE 中出现了两次。 第一个是数据编码器模块中的自注意力层。 它被输入相同的查询、维度为 $T$$\times$$d_x$ 的键和值矩阵 $𝑿$，并输出矩阵 ${𝒁}^{\mathbf{\prime }}\in {ℝ}^{T\times d_x}$ 稍后将投影到另一个矩阵 $𝒁\in {ℝ}^{T\times d_q}$。 然后，$𝒁$被用作查询分析器模块中另一个注意力层的键值矩阵，其中输入查询集仅包含一个SQL查询特征向量。 值得注意的是，自注意力层中设置的“查询”并非来自 SQL 查询。 此外，我们不需要对 DB 状态中的向量进行排序。 因此，与处理序列的类似 Transformer 的模型（Devlin 等人，2019；Brown 等人，2020）不同，ALECE 不需要位置编码（Vaswani 等人，2017）（Vaswani 等人，2017） t1> 或注意力层输入的位置嵌入(Gehring 等人, 2017)。

表2列出了两个模块注意力层的输入源和输出，以及每个模块能够学习什么。 以下两小节给出了它们背后的基本原理。

4.3. 数据编码器

假设随机变量 $V$ 的值是从属性的可能值中以相同的可能性随机获取的。 由此，对应的直方图可以视为$V$的粗略分布函数。因此，数据库状态由一系列描述单个属性的“边际”分布组成。 然而，SQL查询往往涵盖需要知道多个属性之间的联合分布信息的连接谓词。 通常，不同属性的分布不是独立的。 直接从边际分布导出联合分布是困难且不切实际的。 为了解决这个问题，我们设计了利用注意力的数据编码器模块，在边缘分布和联合分布之间建立桥梁。

数据编码器将数据库状态 $𝑿$ 作为输入，并将其输入到 ${𝒏}_{\mathrm{𝗲𝗻𝗰}}$ 堆叠层中。 每一层都是相同的，并且有两个子层。 第一个是多头自注意力子层 ${𝖭}_{\mathrm{𝗌𝖺}}$，它采用相同的键、值和查询输入 - 三个矩阵等于 $𝑿$ 或最后一层的输出，并输出另一个 $T$ 元素集 ${\stackrel{\mathbf{~}}{𝒁}}_i$。 在 ${𝖭}_{\mathrm{𝗌𝖺}}$ 之上，前馈子层 $\mathrm{𝖥𝖥}$ 使用堆叠式全连接网络和非线性激活函数(例如 ReLU）来映射 ${\stackrel{\mathbf{~}}{𝒁}}_i$ 进入数据表示集${𝒁}_i^{\prime }$。 此外，为了解决退化问题并简化模型训练，我们在每个子层周围采用残差连接（He等人，2016），然后进行层归一化（Ba等人， 2016)，遵循(Vaswani 等人, 2017)中的设置。 因此，每个子层的输出为LayerNorm($𝑽+\text{sub-layer}(𝑽))$. 子层是${𝖭}_{\mathrm{𝗌𝖺}}$或$\mathrm{𝖥𝖥}$。 输出表示${𝒁}^{\mathbf{\prime }}$的解析表达式描述如下。

${𝒁}^{\mathbf{\prime }}$ $={𝒁}_{n_{\mathrm{𝖾𝗇𝖼}}}^{\prime },\text{where}{𝒁}_0^{\prime }=𝑿,\text{and}\forall 1\le i\le n_{\mathrm{𝖾𝗇𝖼}},$

${\stackrel{\mathbf{~}}{𝒁}}_{𝒊}$ $=\mathrm{𝖫𝖺𝗒𝖾𝗋𝖭𝗈𝗋𝗆}\left({𝒁}_{i-1}^{\prime }+{𝖭}_{\mathrm{𝗌𝖺}}(\stackrel{\text{keys}}{\overbrace{{𝒁}_{i-1}^{\prime }}},\stackrel{\text{values}}{\overbrace{{𝒁}_{i-1}^{\prime }}},\stackrel{\text{queries}}{\overbrace{{𝒁}_{i-1}^{\prime }}})\right),$

${𝒁}_i^{\prime }$ $=\mathrm{𝖫𝖺𝗒𝖾𝗋𝖭𝗈𝗋𝗆}\left({\stackrel{\mathbf{~}}{𝒁}}_i+\mathrm{𝖥𝖥}\left({\stackrel{\mathbf{~}}{𝒁}}_i\right)\right),\text{with}\mathrm{𝖥𝖥}\left(𝑽\right)=\text{ReLU}\left(𝑾𝑽+𝒃\right)$

最后，输出矩阵${𝒁}^{\mathbf{\prime }}$将线性投影到表示矩阵$𝒁\in {ℝ}^{T\times d_q}$。 此投影旨在将 $𝒁$ 的维度与查询特征化 $𝚚$ 的维度对齐。

注意层中的键、值和查询是同一组。 它们要么是数据库状态$𝑿$，要么是前一个堆叠层的输出。 此设置使层的输出集中的每个元素关注前一层的所有输出，从而关注所有数据库状态。 更重要的是，自注意力层定量地“计算”任意两个直方图中一对元素之间的相关性。 值得注意的是，直方图的每个元素描述了属性的局部分布。 因此，数据编码器模块能够更有效地发现任何一对数据库状态之间的隐式连接，从而表现出与输出集中多个属性的联合分布相关的行为。 与多层感知器（MLP）等其他神经网络架构（Hastie等人，2009）相比，自注意力可以产生更多的可解释性并具有更高的代表性能力。 通过自注意力层，我们在所有数据库状态之间创建链接，或者等效地，在数据库中的所有属性之间创建链接。 罚款后——

调整自注意力和前馈层的参数，对基数估计任务有帮助的关系信息被隐式覆盖并编码到数据编码器模块的输出$𝒁$中。 该信息将在查询分析器模块中进行处理和利用。

4.4. 查询分析器

查询分析器模块尝试通过数据查询交叉关注层来发现和测量 SQL 查询与 $𝒁$ 的每个元素之间的相关性，数据编码器模块的输出涵盖了之间的联合分布信息属性。

该模块也是由${𝒏}_{\mathrm{𝗮𝗻𝗮}}$相同层组成的堆叠结构。 与数据编码器模块类似，这里的每一层都由多头注意力子层和全连接子层组成。 此外，在每个子层周围采用残差连接，然后进行层归一化。 与数据编码器模块不同，这里的键值对输入集和“数据查询”注意子层的查询不是来自同一个地方。 我们使用数据编码器模块的输出$𝒁$作为输入键和值矩阵，而这里的查询集来自查询特征化或上一层的输出。 值得注意的是，每个注意力子层的输入查询集和输出集只有一个 $d_q$-dim 元素。

数据查询注意力子层在查询和数据之间建立了一座桥梁。 它个性化每个 SQL 查询特征，并通过增强输入键值对集 $𝒁$ 的某些部分的影响，同时减少其他部分来呈现不同的“答案”。 学习数据的哪一部分更重要取决于查询和键之间的关系，这是通过注意力函数来衡量的。 假设 SQL 查询包含连接谓词 $R_1.A_1^1=R_2.A_2^2$ 和过滤谓词 $R_1.A_2^1>1$，以及属性 $R_1.A_1^1$、$R_2.A_2^2$ 和 $R_1.A_2^1$ 分别编号为 $i$、$j$ 和 $k$。 数据查询注意力子层将更多地关注集合$𝒁$中与${𝒙}_i$、${𝒙}_j$和${𝒙}_k$。 通过两个模块中不同层的合适参数可以实现特别关注的效果。

访问最终查询分析器层的输出 $𝒚$ 后，我们使用简单的线性回归层 $\mathrm{𝖫𝖱}$ 来计算标量值作为基数估计 $𝖼$ 。 通过$𝒁$和$𝚚$的输入访问$𝖼$的过程如下。

(3) $𝖼$ $=\mathrm{𝖫𝖱}\left(𝒚\right),\text{where}𝒚={𝒚}_{n_{\mathrm{𝖺𝗇𝖺}}},{𝒚}_0=𝚚,\text{and}\forall 1\le i\le n_{\mathrm{𝖺𝗇𝖺}},$

${𝒚}_i^{\prime }$ $=\mathrm{𝖫𝖺𝗒𝖾𝗋𝖭𝗈𝗋𝗆}\left({𝒚}_{i-1}+{𝖭}_{\mathrm{𝖽𝗊}}(\stackrel{\text{keys}}{\overbrace{𝒁}},\stackrel{\text{values}}{\overbrace{𝒁}},\stackrel{\text{queries}}{\overbrace{{𝒚}_{i-1}}})\right),$

${𝒚}_i$ $=\mathrm{𝖫𝖺𝗒𝖾𝗋𝖭𝗈𝗋𝗆}\left({𝒚}_i^{\prime }+\mathrm{𝖥𝖥}\left({𝒚}_i^{\prime }\right)\right)$

4.5. ALECE 训练

微调 ALECE 的参数需要一个训练数据集，其中每个元素都是 3 元组 $({𝚚}_i,{𝑿}_i,{𝖼}_i^{\prime })$，其中 ${𝚚}_i$ 是 SQL 查询 ${𝚚}_i$ 的查询特征化> 和${𝑿}_i$ 是动态数据库的关联DB 状态。 通过在数据库声明为${𝑿}_i$的数据库上执行${𝚚}_i$，我们将得到真正的基数${𝖼}_i^{\prime }$，它将用作标签。 在实际应用中，我们会对${𝖼}_i^{\prime }$取对数，以使标签的范围不会太大。 收集训练数据集并不困难。 通常，我们只需要收集动态数据库上执行查询的反馈。 然后，我们将获得包含三个列表 $𝓧=[{𝑿}_i]$、$𝑸=[{𝚚}_i]$ 和 ${𝗰}^{\mathbf{\prime }}=[{𝖼}_i^{\prime }]$ 的训练数据集。 他们将被分成批次来训练我们的 ALECE。

我们使用均值加权平方误差函数 $\mathrm{𝖬𝖶𝖲𝖤}$ 获取批次卡预测 ${𝗰}_{𝒃}$ 和真实卡 ${𝗰}_{𝒃}^{\mathbf{\prime }}$ 及其权重 ${𝒘}_{𝒃}$ 以批量大小 $B$ 作为损失函数，即 $\mathrm{𝖬𝖶𝖲𝖤}({𝗰}_{𝒃},{𝗰}_{𝒃}^{\mathbf{\prime }})=\frac{1}{B}{\sum }_{i=1}^B{w}_i{({𝖼}_i-{𝖼}_i^{\prime })}^2$。 两个模块中的线性回归层、注意力子层和前馈子层的参数均通过梯度下降以端到端的方式进行批量训练。 这里，值$w_i$与$\log {𝖼}_i$的值成比例。 特别是$w_i=\frac{\log {𝖼}_i}{{\sum }_j\log {𝖼}_j}$。 我们在损失函数中使用权重$w_i$，因为强调具有较大真实基数的查询通常是有益的，因为它们的执行时间往往较长。 使用这些列表$𝓧$、$𝑸$和${𝗰}^{\mathbf{\prime }}$训练ALECE的过程在算法1中有详细说明。

1

2

Input : Three data lists: $𝓧=\left[{𝑿}_i\right]$, $𝑸=\left[{𝒒}_{𝒊}\right]$, ${𝗰}^{\mathbf{\prime }}=\left[{𝖼}_i^{\prime }\right]$

The maximum number of training epochs $M_e$

Output : Well-trained ALECE

3

4Compute the weight vector $𝒘=\left[w_i\right]$ according to ${𝗰}^{\mathbf{\prime }}$.

5 for $i\leftarrow 0$ to $M_e$ do

6 $\text{Train-Epoch}(𝓧,𝑸,{𝗰}^{\mathbf{\prime }},𝒘)$

7 if ALECE performs better on validation set then

8 Assign current parameters to ALECE.

9return ALECE whose parameters are fine-tuned.

10Function Train-Epoch($𝓧,𝐐\mathbf{,}{𝗰}^{\mathbf{\prime }}\mathbf{,}𝐰$):

11 Shuffle and split $𝓧,𝑸\mathbf{,}𝒄\mathbf{,}{𝒘}^{\prime }$, generate $n_B$ equal-size batches $[({𝓧}_b,{𝑸}_b,𝗰_{}^{\mathbf{\prime }}{}_b{}^{}),{𝒘}_b]$, $b=1,\mathrm{\cdots },n_B$.

12 for $b\leftarrow 0$ to $n_B$ do

13 Compute the vector ${𝗰}_b$ with Eq (3).

14 Compute the $\mathrm{𝖬𝖶𝖲𝖤}$ loss given ${𝗰}_b$, $𝗰_{}^{\mathbf{\prime }}{}_b{}^{}$ and ${𝒘}_b$, and apply gradient descent to tune model parameters.

Algorithm 1 Train-ALECE

在实践中，训练数据集分为两部分：第一部分是用于拟合学习过程中的参数的三个数据列表（第7-10行）；第二部分用作验证集，为 ALECE 选择最佳参数并避免过度拟合（第 4-5 行）。 此外，我们将应用早期停止策略（Prechelt，2012），以在验证集上的错误增加时停止训练过程。

5. ALECE分析

在本节中，我们将讨论为什么 ALECE 适合动态工作负载并进一步分析其属性。

5.1. 动态工作负载上的 ALECE

对于数据库来说，处理动态工作负载（即查询和数据操作的混合负载）至关重要。 这要求 DBMS 的查询优化器能够准确预测在不断变化的数据库上执行的（子）查询的基数。 为了减少相关开销，DBMS 定期维护其

基数估计器，而不是在每次更新后立即修改它。 在两个模型维护时间点之间，基数估计器模型通常是固定的，但仍有望做出准确的估计。

传统的基于直方图的基数估计器（Selinger等人，1979；Poosala和Ioannidis，1997；Gunopulos等人，2000；Deshpande等人，2001）目前在PostgreSQL等系统中使用（Group ，1996）做出简单且通常不合理的假设，例如属性的相互独立性。 他们的估计不准确，尤其是当数据是动态的时候。 这使得优化器很难选择好的查询计划。 现有的学习基数估计方法要么不支持动态工作负载（赵等人，2022），要么需要在模型维护时间点完全重新构建模型（朱等人，2021； Hilprecht 等人, 2020; Yang 等人, 2020)。 这个过程往往过于耗时而不可行。

与现有方法(Hilprecht 等人, 2020; Zhu 等人, 2021; Yang 等人, 2020)相比，ALECE 的训练是高效的。 而且，它很容易维护：它可以在模型维护时间点增量更新。 而且其架构设计合理，适合处理动态工作负载。 值得注意的是，SQL 查询和底层数据在 ALECE 中是解耦的，这样只要数据库状态 $𝑿$ 或训练数据集中的查询特征 $𝚚$ 发生变化，ALECE 就可以学到一些东西。 因此，ALECE 能够避免过度拟合某些数据集。 相反，它在两个模块上应用注意力机制来学习“生成”底层数据的数据分布的属性，以及这些属性如何影响 SQL 查询的基数。 它能够合理地近似 $𝖼(𝚚,\mathrm{𝖣𝖡})$，即查询、动态数据和基数之间真实但隐式的映射。 当查询特征或数据库状态或两者都发生变化时，ALECE 仍然可以输出准确的结果。 我们的实验结果表明，即使训练数据和测试数据之间存在分布差异，ALECE 也能取得良好的性能。

无需关注的简单基线。 3.3节提到，当向数据库插入/删除数据时，数据库状态会动态修改。 这使得使用稳定的、训练有素的模型来预测动态工作负载上的查询基数成为可能。 由于数据库状态和查询特征的维度是固定的，我们也可以采用直接的方法而不需要注意来处理它们。 例如，对于每一对数据特征化 ${𝑿}_i$ 和查询特征化 ${𝚚}_i$，我们都会将矩阵 ${𝑿}_i$ 扁平化为一个向量，并将该向量与 ${𝚚}_i$ 连接，生成另一个向量 ${𝒗}_i$。 随后，${𝒗}_i$ 和相关层被输入到通用监督神经网络，如多层感知器 (MLP) （Hastie 等人，2009）。 然而，像 MLP 这样的简单神经网络通常不足以发现 SQL 查询和底层数据之间的隐式关系。 它的性能在很大程度上依赖于训练和测试数据集分布之间的相似性。 当工作负载是静态的，即数据库数据从未发生变化时，直接的方法性能良好。 然而，基数估计器模型需要使用它观察到的当前训练数据来预测“未来”数据。 未来数据库状态的分布可能与当前数据的分布有很大不同。 相比之下，即使基础数据的分布发生变化，我们的 ALECE 中注意力机制的应用也可以做出准确的估计。 6部分的实验结果表明，ALECE在处理动态工作负载方面相对于MLP具有巨大优势。

5.2. ALECE 及其扩展的开销

其他几个良好的属性使 ALECE 作为现代 DBMS 查询优化器中的基数估计方法更加实用和有吸引力。 首先，ALECE 的存储和训练开销是可以承受的。 一方面，我们实验中三个数据集上的 ALECE 大小均小于 23 MB。 另一方面，从头开始训练 ALECE 需要不到 12 分钟。 此外，ALECE 的估计延迟小于 11 ms。 这些开销使 ALECE 能够处理现实世界的工作负载。

其次，与 FLAT (Zhu 等人, 2021) 和 DeepDB (Hilprecht 等人, 2020) 不同，ALECE 直接估计基数而不是 SQL 查询的选择性。 为了获得基数，选择性估计方法通常需要使用基于采样的技术来估计相应连接表的大小（Zhao等人，2018）。 然而，当涉及多种关系时，统计方差通常会变大并导致估计非常不准确。

最后但更重要的是，ALECE 建立了一个不限于基数估计任务的通用框架。 通过将$\mathrm{𝖢𝖮𝖴𝖭𝖳}(\ast )$替换为其他聚合函数，可以将Format(2)的特殊聚合分析查询进一步转化为更通用的聚合分析查询。 事实上，ALECE 可以轻松扩展以近似更一般的聚合分析查询的结果。 当使用其他类型的聚合函数处理查询时，我们只需要对数据和查询特征进行轻微修改，包括在查询特征中特征化额外的聚合函数和可选的$\mathrm{𝖦𝖱𝖮𝖴𝖯}\mathrm{𝖡𝖸}$子句，并合并更多的数据描述特定于聚合查询的信息。 我们将一般聚合分析查询的支持留给未来的工作。

6. 实验研究

本节报告将 ALECE 与选定替代方案进行比较的实验。 所有方法均在 Python 3.9 中实现，并在具有 96 核 Xeon(R) Platinum 8163 CPU 和 376GB 内存的 Linux 服务器上进行评估。 ALECE的实现是开放的(cod, line)。 由于篇幅限制，我们在附录的C节中提供了额外的实验结果和分析。

6.1. 实验设置

数据集。 我们使用三个真实数据集来评估所有模型。

• STATS 包含 8 个关系(用户、帖子、postLinks、postHistory、评论、投票、徽章、标签)以及 43 个属性（STA、行） 。 总共有 1,029,842 条记录。 具有 146 个查询的现有开放工作负载被标记为“测试查询”。 它们与 2,603 个子查询相关联。 我们创建了另外 1000 个带有子查询的不同查询，用作训练和验证数据。

• Job-light 是 IMDB 数据集 (imd, line) 的子集。 它包含 6 个关系(cast_info、movie_info、movie_companies、movie_keyword、movie_info_idx、title)和 14 个属性。 总共有 62,118,470 条记录。 测试查询集包含 208 个查询，与 3,248 个子查询关联。 同样，为训练模型创建了另外 2,000 个查询及其子查询。

• TPCH (1 GB) (tpc, line) 是一组广泛使用的面向业务关系的基准数据集(客户、订单项、国家、订单、零件、零件供应商、地区和供应商)。 我们从每个关系中删除字符串类型“comment”属性，因为 ALECE 或其他方法不支持它。 我们使用剩余的 46 个属性。 总共有 8,661,245 条记录。 我们随机创建 123 个测试查询和 1,554 个测试子查询进行评估。 另外 2,000 个查询及其子查询用于训练。

这些数据集中关系之间的连接信息如附录中的图5所示。 Job-light 数据集上的查询中的所有连接都是 PK-FK 连接，而其他数据集上的查询涉及更复杂的多对多连接。

动态工作负载。 对于每个数据集，我们创建三个不同的动态工作负载，每个工作负载都是插入、删除、更新和查询语句的随机组合。 这些工作负载是不同的

根据插入、删除、更新次数的比例以及插入记录的分布情况来确定：

• 插入重: #inserts：#deletes：#updates = $2:1:1$。

• 重更新: #inserts：#deletes：#updates = $1:1:2$。

• Dist-shift 是一种特殊的Insert-heavy 工作负载，但插入记录的分布不均匀。 特别是，插入的记录是有意选择的，使得它们的第一个属性值是所有数据中前 30% 最小的。

为了生成动态工作负载，我们随机选择大约 $\frac{2}{3}$ 条记录作为初始数据集来批量加载所有关系。 随后，动态工作负载中的插入和更新语句会将剩余的$\frac{1}{3}$记录插入数据库，而删除和更新语句将删除或更改一些记录。 为了简单和清楚起见，我们假设每个删除或更新语句仅影响一条记录。 这些陈述同样分为两部分：前者是“训练”部分，后者是“评估”部分。 为了确保 ALECE 从足够的特征中学习，我们制作了三个训练查询及其子查询的副本，并将它们与训练部分随机混合。 工作负载的训练部分用作构建所有基数估计方法的训练数据集。 请注意，训练部分中查询的真实基数也适用于所有方法。

在评估部分将测试查询与数据操作语句混合的方式略有不同。 对于每个测试查询，我们将其与其子查询打包在一起。 然后，在评估部分，这些包被打乱并与数据操作语句随机混合。 另外，我们想知道当数据库中一定量的数据发生变化时，基数估计器如何执行。 因此，假设当执行每个测试查询时，底层数据库数据的关联变化率$\rho$大于预定义的阈值。 我们使用 $H$ 来表示执行完训练部分中的所有语句后数据库中所有记录的集合。 给定评估部分中的任何查询$q_i$，假设$B_i$是执行$q_i$时数据库中所有记录的集合，以及插入、删除的次数迄今为止评估部分的更新分别为 ${𝙸}_{𝚒}$、${𝙳}_{𝚒}$ 和 ${𝚄}_{𝚒}$。 变化率${\rho }_i$定义为$\rho (t)=\frac{|H\mathrm{△}{B}_i|}{|H|}=\frac{{𝙸}_{𝚒}+{𝙳}_{𝚒}+2{𝚄}_{𝚒}}{|H|}$，其中$\mathrm{△}$表示两个集合的对称差分运算。 当没有歧义时，省略下标$i$。

训练和测试查询都是随机生成的。 特别是，为了生成查询，我们使用 $p$$=$$0.5$ 运行一系列伯努利测试来确定出现哪些关系。 然后，我们枚举所选关系之间连接条件的所有可能子集，以便它们可以通过这些连接条件连接。 随机选择子集之一作为连接谓词集$𝑱$。 过滤谓词 $𝑭$ 中的属性及其运算符($\le ,\ge$、等)是通过类似的伯努利测试确定的。 过滤器谓词的右侧值是从初始数据集中随机采样的。

竞争对手。 我们包括以下代表性方法：

• PG 是 PostgreSQL （Group，1996） 中使用的最简单的基于一维直方图的基数估计方法。

• Uni-Samp (Liang 等人, 2021) 对每个关系以给定概率 $p$ 统一采样一组元组。 查询$q$的基数估计等于$N_q/p^m$，其中$N_q$是通过在样本集上执行$q$返回的元组数量，$m$是$q$中涉及的关系数。 我们调整$q$的值，使Uni-Samp的存储开销或延迟与其他方法相当。 STATS、Job-light和TPCH数据集的采样率$p$值分别设置为0.1、0.06和0.04。

• DeepDB （Hilprecht 等人，2020） 基于 Sum-Product-Network (SPN) （Poon 和 Domingos，2011）。 它学习一个纯数据驱动的模型来捕获数据的联合概率分布。 按照(Hilprecht等人, 2020)中的相同设置，我们将RDC独立性阈值设置为0.3，并用至少1%的输入数据分割每个SPN节点。

• FLAT (朱等人, 2021)基于分解求和分裂积网络(FSPN)改进SPN (吴等人, 2020)，图形模型，自适应地对属性的联合概率密度函数进行建模。 它是数据驱动的。

• NeuroCard (Yang 等人, 2020) 是一种数据驱动的方法，将 Naru (Yang 等人, 2019) 扩展到多表中情况，而 Naru 是一种基于深度自回归 (DAR) (Gregor 等人, 2014) 的单表基数估计算法。 NeuroCard模型的采样大小设置为8000，遵循论文中的设置。

• FactorJoin (Wu 等人, 2023) 将经典的连接直方图方法与学习的单表基数估计结合到因子图中。

• MLP (Rumelhart 等人, 1986) 是 5.1 节中介绍的基于基线神经网络的方法。

• MSCN (Kipf 等人, 2019) 是一个多集卷积网络，它采用来自查询和数据的信息。

• NNGP (Zhao 等人, 2022) 采用神经网络高斯过程 (NNGP) 模型 (Lee 等人, 2018) 从查询中学习以及它们的真实基数以受监督的方式进行。

此外，我们还包括与真实基数生成的结果的比较。 此最佳方法衡量方法可以实现的最佳性能。

选择这些竞争对手是因为它们比其他统计和学习基数估计器具有更好的整体性能。 比较结果在基准和评估论文（Han 等人，2021；Sun 等人，2021）和其他现有著作中进行了报告，例如（Zhu 等人，2021；Wu 和 Shaikhha，2020；杨等人，2020）。 表3总结了所有方法的属性。 更好的性能以粗体表示。

表3。 不同方法的属性

Method	Data- driven	Query- driven	Building time	Space overhead	Suitable for dy- namic workload
PG (Group, 1996)	$\mathbf{✓}$	$\times$	small	low	$\times$
Uni-Samp (Liang et al., 2021)	$\mathbf{✓}$	$\times$	small	medium	$\times$
DeepDB (Hilprecht et al., 2020)	$\mathbf{✓}$	$\times$	medium	medium	$\times$
FLAT (Zhu et al., 2021)	$\mathbf{✓}$	$\times$	large	high	$\times$
NeuroCard (Yang et al., 2020)	$\mathbf{✓}$	$\times$	medium	medium	$\times$
FactorJoin (Wu et al., 2023)	$\mathbf{✓}$	$\times$	medium	small	$\times$
MLP (Rumelhart et al., 1986)	$\times$	$\mathbf{✓}$	small	low	$\times$
MSCN (Kipf et al., 2019)	$\mathbf{✓}$	$\mathbf{✓}$	small	small	$\times$
NNGP (Zhao et al., 2022)	$\times$	$\mathbf{✓}$	small	medium	$\times$
ALECE (ours)	$\mathbf{✓}$	$\mathbf{✓}$	small	medium	$\mathbf{✓}$

表 4. 基数估计模型在动态工作负载上的整体性能

Data	Model	Insert-heavy												Update-heavy
		E2E Time(S)	Q-error				P-error				Size (MB)	Building Time(Min)	Latency (ms)	E2E Time(S)	Q-error				P-error
			50%	90%	95%	99%	50%	90%	95%	99%					50%	90%	95%	99%	50%	90%	95%	99%
STATS	PG	$7,790$	$190$	$1.4$$\cdot$${10}^5$	$1.1$$\cdot$${10}^6$	$1.8$$\cdot$${10}^7$	$2.60$	$25.44$	$41.23$	$243$	-	-	-	$4,337$	$524$	$43,096$	$3.7$$\cdot$${10}^5$	$1.1$$\cdot$${10}^7$	$1.78$	$19.52$	$29.01$	$178$
	Uni-Samp	$6,646$	$1.35$	$12.47$	¿${10}^{10}$	¿${10}^{10}$	$2.71$	$16.77$	$21.65$	$201$	$3.34$	$\mathbf{0.02}$	$239$	$6,002$	$\mathbf{1.27}$	$9.3$$\cdot$${10}^9$	¿${10}^{10}$	¿${10}^{10}$	$1.10$	$12.86$	$33.19$	$153.11$
	NeuroCard	¿$30,000$	$17.37$	$1,388$	$7,402$	$3.0$$\cdot$${10}^5$	$2.38$	$39.18$	$824$	$84,415$	$90.76$	$23.69$	$32.42$	$22,193$	$18.49$	$1,252$	$6,784$	$3.1$$\cdot$${10}^5$	$2.10$	$31.75$	$347$	$11,730$
	FLAT	¿$30,000$	$12.77$	$1,979$	$12,897$	$8.6$$\cdot$${10}^5$	$2.22$	$70.08$	$2,202$	$8,738$	$210.33$	$53.77$	$13.67$	$24,319$	$16.00$	$2,376$	$17,811$	$9.4$$\cdot$${10}^5$	$2.20$	$29.76$	$724$	$1.4$$\cdot$${10}^5$
	FactorJoin	¿$30,000$	$22.62$	$2,593$	$31,936$	$1.6$$\cdot$${10}^6$	$2.35$	$66.12$	$876$	$8,384$	$1.64$	$0.42$	$1.33$	¿$30,000$	$23.76$	$2,939$	$36,198$	$2.4$$\cdot$${10}^6$	$2.75$	$115$	$912$	$4,409$
	MLP	¿$30,000$	$2.4$$\cdot$${10}^6$	¿${10}^{10}$	¿${10}^{10}$	¿${10}^{10}$	$7.35$	$491$	$2,294$	$6,887$	$8.63$	$3.11$	$3.17$	¿$30,000$	$2.3$$\cdot$${10}^6$	¿${10}^{10}$	¿${10}^{10}$	¿${10}^{10}$	$6.66$	$502$	$3,025$	$11,584$
	MSCN	$27,758$	$20.09$	$2,870$	$17,037$	$2.6$$\cdot$${10}^5$	$2.46$	$87.23$	$736$	$8,738$	$\mathbf{1.61}$	$11.87$	$\mathbf{1.02}$	$25,766$	$18.89$	$2,382$	$16,947$	$1.8$$\cdot$${10}^6$	$2.56$	$64.64$	$246$	$46,721$
	NNGP	$12,883$	$9.88$	$827$	$4,652$	$2.6$$\cdot$${10}^5$	$1.41$	$5.31$	$27.33$	$3,588$	$32.44$	$0.89$	$32.66$	$11,985$	$8.15$	$567$	$3,639$	$2.5$$\cdot$${10}^5$	$1.52$	$5.62$	$13.81$	$2,753$
	ALECE	$\mathrm{𝟐}\mathbf{,}\mathrm{𝟗𝟎𝟏}$	$\mathbf{1.29}$	$\mathbf{5.07}$	$\mathbf{11.54}$	$\mathbf{62.52}$	$\mathbf{1.07}$	$\mathbf{1.34}$	$\mathbf{1.59}$	$\mathbf{2.32}$	$22.31$	$9.25$	$8.25$	$\mathrm{𝟐}\mathbf{,}\mathrm{𝟒𝟎𝟐}$	$1.42$	$\mathbf{5.06}$	$\mathbf{10.40}$	$\mathbf{44.69}$	$\mathbf{1.08}$	$\mathbf{1.45}$	$\mathbf{2.13}$	$\mathbf{2.86}$
	Optimal	$2,871$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	-	-	-	$2,349$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$
Job- light	PG	$6,128$	$1.59$	$7.14$	$20.85$	$223$	$1.10$	$1.32$	$1.48$	$2.89$	-	-	-	$4,747$	$1.67$	$6.20$	$14.09$	$70.13$	$1.10$	$1.39$	$1.64$	$3.06$
	Uni-Samp	$6,401$	$1.23$	$2.59$	$6.53$	¿${10}^{10}$	$1.08$	$1.85$	$2.79$	$146$	$23.95$	$\mathbf{0.52}$	$163$	$4,491$	$1.33$	$3.61$	$7.50$	¿${10}^{10}$	$1.12$	$1.71$	$2.26$	$3.67$
	DeepDB	$26,636$	$11.31$	$663$	$6,328$	$5.4$$\cdot$${10}^5$	$1.66$	$13.71$	$26.01$	$49.57$	$11.52$	$11.93$	$11.92$	$23,190$	$10.64$	$628$	$4,883$	$8.8$$\cdot$${10}^5$	$1.50$	$11.81$	$27.71$	$135$
	NeuroCard	$27,744$	$14.73$	$978$	$6,766$	$4.7$$\cdot$${10}^5$	$1.81$	$12.40$	$37.25$	$144$	$42.93$	$9.11$	$15.90$	$16,553$	$13.49$	$1,000$	$6,489$	$1.5$$\cdot$${10}^6$	$1.60$	$15.10$	$25.94$	$50.68$
	FLAT	$23,876$	$11.22$	$626$	$5,786$	$4.4$$\cdot$${10}^5$	$1.66$	$13.98$	$27.26$	$89.67$	$11.10$	$17.83$	$3.96$	$22,531$	$10.13$	$490$	$4,221$	$1.1$$\cdot$${10}^6$	$1.42$	$12.87$	$34.54$	$195$
	FactorJoin	$16,665$	$25.14$	$3,456$	$27,938$	$2.5$$\cdot$${10}^6$	$1.52$	$5.45$	$10.23$	$47.09$	$4.66$	$26.22$	$1.33$	$13,071$	$27.31$	$6,134$	$36,155$	$2.2$$\cdot$${10}^6$	$1.42$	$4.83$	$9.43$	$22.75$
	MLP	$5,610$	$4.30$	$23.14$	$59.37$	$2,411$	$1.13$	$1.70$	$2.10$	$3.12$	$6.19$	$2.68$	$2.28$	$5,351$	$5.59$	$62.02$	$138$	$1,441$	$1.17$	$2.02$	$2.88$	$4.09$
	MSCN	$26,665$	$24.42$	$1,809$	$9,217$	$1.4$$\cdot$${10}^5$	$2.07$	$20.98$	$28.58$	$106$	$\mathbf{1.56}$	$33.37$	$\mathbf{0.77}$	$29,118$	$26.77$	$1,448$	$7,980$	$1.5$$\cdot$${10}^5$	$2.59$	$19.87$	$61.18$	$257$
	NNGP	$15,430$	$4.5$$\cdot$${10}^8$	¿${10}^{10}$	¿${10}^{10}$	¿${10}^{10}$	$3.57$	$8.39$	$11.97$	$24.47$	$32.44$	$0.83$	$29.86$	$4,959$	$4.99$	$59.86$	$190$	$50,036$	$1.20$	$2.05$	$2.99$	$4.96$
	ALECE	$\mathrm{𝟓}\mathbf{,}\mathrm{𝟏𝟔𝟖}$	$\mathbf{1.14}$	$\mathbf{2.08}$	$\mathbf{3.85}$	$\mathbf{14.82}$	$\mathbf{1.07}$	$\mathbf{1.24}$	$\mathbf{1.32}$	$\mathbf{1.77}$	$22.25$	$7.73$	$7.28$	$\mathrm{𝟑}\mathbf{,}\mathrm{𝟖𝟑𝟗}$	$\mathbf{1.09}$	$\mathbf{1.93}$	$\mathbf{3.63}$	$\mathbf{16.28}$	$\mathbf{1.07}$	$\mathbf{1.23}$	$\mathbf{1.29}$	$\mathbf{1.57}$
	Optimal	$5,063$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	-	-	-	$3,792$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$
TPCH	PG	$\mathrm{𝟑}\mathbf{,}\mathrm{𝟐𝟑𝟎}$	$1.35$	$4.88$	$7.90$	$16.16$	$1.44$	$\mathbf{1.57}$	$\mathbf{1.59}$	$\mathbf{1.62}$	-	-	-	$2,385$	$1.33$	$5.01$	$6.87$	$14.64$	$\mathbf{1.41}$	$\mathbf{1.56}$	$\mathbf{1.59}$	$\mathbf{1.62}$
	Uni-Samp	¿$30,000$	$1.22$	$2.94$	¿${10}^{10}$	¿${10}^{10}$	$1.81$	$2.22$	$45.60$	$514$	$23.29$	$\mathbf{0.17}$	$24.52$	¿$30,000$	$1.30$	$3.41$	¿${10}^{10}$	¿${10}^{10}$	$1.75$	$19.35$	$50.34$	$211$
	NeuroCard	$10,616$	$43.43$	$7,071$	$27,735$	$3.5$$\cdot$${10}^5$	$3.75$	$10.91$	$22.48$	$106$	$704.98$	$34.38$	$34.77$	$6,562$	$45.73$	$5,896$	$20,931$	$1.2$$\cdot$${10}^5$	$3.16$	$11.04$	$16.49$	$245$
	FLAT	$11,428$	$46.04$	$12,236$	$70,383$	$8.4$$\cdot$${10}^7$	$3.56$	$10.91$	$25.71$	$1,182$	$168.65$	$41.42$	$10.06$	$7,864$	$42.32$	$7,328$	$26,470$	$3.7$$\cdot$${10}^5$	$3.56$	$15.82$	$21.70$	$425$
	MLP	$7,261$	$51,475$	$1.4$$\cdot$${10}^7$	$3.5$$\cdot$${10}^7$	$4.7$$\cdot$${10}^9$	$4.71$	$14.11$	$22.74$	$36.09$	$8.63$	$3.57$	$3.62$	$8,342$	$79,317$	$3.7$$\cdot$${10}^7$	$9.1$$\cdot$${10}^7$	¿${10}^{10}$	$5.12$	$17.63$	$32.74$	$63.39$
	MSCN	$7,718$	$36.36$	$6,709$	$26,744$	$4.4$$\cdot$${10}^5$	$3.58$	$15.11$	$25.71$	$387$	$\mathbf{1.58}$	$23.43$	$\mathbf{0.79}$	$8,353$	$41.66$	$5,457$	$21,433$	$1.7$$\cdot$${10}^5$	$3.80$	$14.86$	$25.69$	$472$
	NNGP	$18,618$	$1.3$$\cdot$${10}^9$	¿${10}^{10}$	¿${10}^{10}$	¿${10}^{10}$	$5.56$	$47.40$	$59.18$	$99.55$	$32.44$	$0.92$	$41.76$	$3,128$	$25.88$	$432$	$986$	$4,968$	$1.54$	$7.98$	$10.90$	$20.66$
	ALECE	$3,233$	$\mathbf{1.15}$	$\mathbf{2.29}$	$\mathbf{3.37}$	$\mathbf{8.86}$	$\mathbf{1.43}$	$\mathbf{1.57}$	$1.60$	$\mathbf{1.62}$	$22.34$	$11.62$	$10.35$	$\mathrm{𝟐}\mathbf{,}\mathrm{𝟑𝟖𝟎}$	$\mathbf{1.25}$	$\mathbf{2.11}$	$\mathbf{2.95}$	$\mathbf{10.87}$	$\mathbf{1.41}$	$\mathbf{1.56}$	$\mathbf{1.59}$	$\mathbf{1.62}$
	Optimal	$3,227$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	-	-	-	$2,378$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$

评估指标。 我们使用三个指标来评估所有方法：

• E2E 时间 是工作负载评估部分中所有查询的总执行时间，其中我们向查询优化器提供所有相关子查询的估计基数。 这些估计结果是使用基数估计方法获得的。 它是最重要的评估指标，因为它直接连接到查询优化器，并客观地显示基数估计方法是否有助于提高 DBMS 的查询性能。 此类评估需要对现有工作进行改进的基准（Han等人，2021）。 该基准测试可以通过外部方法将估计结果集成到 PostgreSQL 中。 我们在附录中的 B 节中显示了其详细信息。

• P-error (Han 等人, 2021) 在不执行给定查询的情况下，根据估计的基数测量最优查询计划与生成计划之间的差距。 特别是，给定查询 $𝚚$、查询计划 $P$ 以及 $𝚚$ 的所有估计/真实基数集 $𝗰$子查询时，DBMS 将使用成本函数 $𝒞$ 输出估计成本 $𝒞(P,𝗰)$。 通过向查询优化器 ${𝗰}^T$（$𝚚$ 的所有子查询的真奇数集）提供信息，我们可以得到 $𝚚$ 的最优计划 $P^T$。 类似地，基数估计方法$𝖠$为$𝚚$输出一组${𝗰}^E$，这会产生另一个查询计划$P^E$。 然后，$\text{P-error}(𝖠,𝚚)=\frac{𝒞(P^E,{𝗰}^T)}{𝒞(P^T,{𝗰}^T)}$，其中分母$𝒞(P^T,{𝗰}^T)$是最优执行成本，分子$𝒞(P^E,{𝗰}^T)$是将子查询的真实基数输入到由方法$𝖠$生成的查询计划。 换句话说，如果采用$𝖠$方法，$𝒞(P^E,{𝗰}^T)$就是$𝚚$的实际执行成本。

• Q-error (Moerkotte 等人, 2009) 测量估计基数 $P$ 与真实基数 $T$ 之间的距离一个问题。 特别是$𝖰\text{-}\mathrm{𝖾𝗋𝗋𝗈𝗋}(P,T)=\max (\frac{T}{P},\frac{P}{T})$。

• 存储开销是方法使用的内存大小。

• 构建时间表示查询驱动方法的离线训练时间或数据驱动方法的构建时间。

• 估计延迟是基数估计方法使用的每个子查询的平均估计时间。

由于优化器只需要子查询的基数估计，因此我们的评估也仅涉及测试子查询。

参数设置。 我们对每个属性使用 40-bin 直方图，即、$d_x=40$。 $n_{\mathrm{𝖾𝗇𝖼}}$和$n_{\mathrm{𝖺𝗇𝖺}}$的值，即，数据编码器和查询分析器中堆叠注意力层的数量，分别设置为4. 为了训练我们的 ALECE，我们使用 Adam 优化器（Kingma and Ba，2015），学习率为 0.01，批量大小为 128。

6.2. 动态工作负载的性能

对于每个动态工作负载，我们使用训练部分中的数据构建所有方法，以对评估部分中的测试子查询进行估计。 训练查询和子查询的特征以及训练部分中相应的数据库状态和真实基数形成了训练数据。 我们使用训练数据来训练查询驱动模型，包括 ALECE、MLP、MSCN 和 NNGP。 数据驱动模型，即 DeepDB、NeuroCard、FLAT 和 FactorJoin，是在执行工作负载训练部分的所有语句后使用数据库数据构建的。 此设置与现实世界场景兼容，因为基数估计模型会定期更新。 在我们的实验中，每个测试查询的相关变化率$\rho$大于20%。 换句话说，当执行测试查询时，相比之下，至少 20% 的底层数据发生了变化。

构建基数估计器时写入数据库。

不同方法的估计结果将被输入到我们改进的基准中，以比较所有方法在动态工作负载上的端到端查询时间（E2E时间）。 为了研究这些方法与最佳方法之间的性能差距，我们还将真实基数提供给基准以获得最佳执行时间。 我们不会在 STATS 和 TPCH 数据集上与 DeepDB 进行比较，因为它仅支持 PK-FK 连接。 Factorjoin 的开放实现针对 STATS 和 Job-light 数据集进行了硬编码，并且不支持 TPCH 数据集。 因此，Factorjoin 未在此数据集上进行测试。 除了E2E时间之外，我们还记录了所有方法在不同工作负载上的Q错误和P错误分布、构建时间、存储开销和延迟。 这些结果如表4所示。 Update-heavy 工作负载上的存储开销、构建时间和延迟结果与 Insert-heavy 工作负载上的对应结果类似，因此被省略。

端到端评估。 参考表4，ALECE相对于其他方法在E2E时间上有明显的优势。 一方面，与 PostgreSQL 的内置基数估计器相比，ALECE 使查询执行速度提高了 2.7$\times$。 它的 E2E 时间仅比 TPCH 的 Insert-heavy 工作负载上的 PG 稍长一些。 然而，在这个工作负载上，PG 和 Optimal 的性能几乎没有差距。 与 Optimal 相比，ALECE 最多仅导致 2.2% 的额外 E2E 时间。 考虑到 ALECE 在这些工作负载上的优越性，我们自信地声称 ALECE 的性能比 PostgreSQL 中的内置估计器要好得多，并且能够极大地提高动态工作负载上的查询执行性能。 另一方面，除了 ALECE 之外，只有 MLP 和 Uni-Samp 在少数工作负载上优于 PG。 DeepDB、NeuroCard、FLAT、FactorJoin 和 NNGP 的 E2E 时间在所有情况下都大于 PG。 与最佳方法相比，这些方法在大多数工作负载上导致 E2E 时间增加一倍以上。 这些结果表明，这些现有方法无法对 DBMS 对动态工作负载做出令人满意的估计。

P 误差比较表明 ALECE 的结果是 ef-

从另一个角度有效的查询执行。 大多数查询上 ALECE 的 P 错误接近 1。 换句话说，通过 ALECE 的输出，大多数查询的执行速度几乎与使用真实基数进行优化一样快。 在 95% 分位数处，ALECE 在 P 误差方面优于 PG、Uni-Samp、DeepDB、NeuroCard、FLAT、FactorJoin、MLP、MSCN 和 NNGP，高达 26、32、21、518、1,385、551、分别为 1,443、463 和 37 次。 这些都表明ALECE在帮助PostgreSQL更高效地处理查询方面比竞争对手取得了很大的优势。

值得注意的是，ALECE 在连接模式更复杂的 STATS 数据集上具有更明显的优势。 这反映出我们的 ALECE 能够比其他替代方案更好地掌握复杂连接模式和底层数据之间的隐式关系。 此外，ALECE 在 E2E 时间和 P 错误方面优于 MLP。 ALECE和MLP的主要结构差异体现在ALECE模块中注意力的采用上。 这验证了注意力机制在从底层数据和 SQL 查询中提取有用信息方面的积极作用。

估计准确性。 表 4 还报告了所有方法的 Q 误差分布。 总的来说，ALECE 在所有三个数据集上都明显优于 PG。 这验证了PG中的独立性假设对于某些场景来说是不合理的。 在所有情况下，ALECE 仍然是所有方法中表现最好的。 在大多数分位数处，ALECE 会产生最小的最大 Q 误差。 所有情况下 ALECE 的中值 Q 误差都接近最优值 1。 在 95% 分位数处，所有情况下 ALECE 的 Q 误差均小于 10。 相比之下，其他方法都无法达到这种性能水平。 同样在 95% 分位数处，Uni-Samp、DeepDB、NeuroCard、FLAT、FactorJoin、MLP、MSCN 和 NNGP 的结果高达或超过 ${10}^9\times$、84$\times$、1,643$\times$、8,220$\times$、${10}^4\times$、3,480$\times$、${10}^4\times$、7,927$\times$、 ${10}^4\times$ Q 误差比 ALECE 更大。 在其他分位数上，这些方法仍然无法与 ALECE 相比。 这些结果表明 ALECE 更加准确，能够发现属性之间以及查询与属性之间的隐式关系。 另一个间

测试的结果是，较小的 Q-error 并不一定会导致较小的 E2E 时间，这一点在现有工作 (Negi 等人, 2021) 中得到了声称，并通过 NNGP、DeepDB 和 NeuroCard 之间的比较得到了证明， etc，在 Job-light 数据集上。 对单个子查询的不准确估计往往会生成错误的查询计划和较长的执行时间。 有必要确保所有子查询的准确估计。

模型构建效率。 参见表4，ALECE的训练成本很小。 分别需要不到 10 分钟、8 分钟和 13 分钟的时间来调节 STATS、Job-light 和 TPCH 数据集的参数。 相比之下，DeepDB、NeuroCard、FLAT 和 MSCN 消耗更多的构建时间。 虽然Uni-Samp和Factorjoin在某些情况下需要较少的构建时间，但它们的E2E时间、P错误和Q错误性能要差得多。 与 ALECE 相比，MLP 和 NNGP 的结构更简单，因此需要更少的训练时间。 不过，他们的表现能力并不如ALECE那么强大。 ALECE 在 E2E 时间上的压倒性优势说明了更复杂的结构和稍微更多的训练时间的必要性。

在延迟方面，Uni-Samp 的性能最差。 FactorJoin、MLP 和 MSCN 进行估计所需的平均时间最少，小于 10 毫秒。 ALECE 的延迟稍大，但比其他的要小。 考虑到对所有数据集执行查询平均需要超过 10 秒的时间，因此小于 10 毫秒的估计延迟在整体情况下并不重要。

存储开销。 一般来说，查询驱动方法的存储开销比数据驱动方法小。 查询驱动方法只需要维护固定数量的参数，这些参数的大小通常比数据驱动方法保存的“数据摘要”小得多，例如 DeepDB 中的 SPN 或 FSPN 以及分别为平坦。 FactorJoin 和 MSCN 的内存成本最小。 由于其结构更复杂，ALECE 比 MLP 和 NNGP 消耗更多的内存。 与 NeuroCard 和 FLAT 相比，ALECE 在 STATS 数据集上分别节省了高达 75.4% 和 89.4% 的内存成本。 在 Job-light 数据集上，ALECE 的内存成本比 FLAT 和 DeepDB 稍高。 考虑到现代计算机通常具有大内存，并且 ALECE 在 E2E 时间、P 错误和 Q 错误方面表现更好，额外的存储开销会带来很高的回报。

6.3. 分布转移的影响

为了研究当底层数据的分布发生巨大变化时 ALECE 是否仍然可以正常工作，我们进行了实验来比较 Dist-shift 工作负载上的不同方法。 值得注意的是，Dist-shift 工作负载的评估部分涵盖了高度倾斜的插入语句。 表5报告了ALECE、PG、NeuroCard、MSCN、NNGP和Optimal之间的E2E时间、Q误差和P误差分布比较。 选择这些竞争对手是因为它们在插入繁重和更新繁重工作负载上具有更好的整体性能。 由于空间限制，省略了存储开销、构建时间和延迟比较。 这些结果与其他两个工作负载的对应结果类似。

表 5. Dist-shift 工作负载上的方法性能

Data	Model	E2E Time(S)	Q-error				P-error
			50%	90%	95%	99%	50%	90%	95%	99%
STATS	PG	$8,432$	$189$	$1.4$$\cdot$${10}^5$	$1.1$$\cdot$${10}^6$	$1.9$$\cdot$${10}^7$	$2.60$	$25.50$	$42.65$	$300$
	Uni-Samp	$7,524$	$\mathbf{1.32}$	¿${10}^{10}$	¿${10}^{10}$	¿${10}^{10}$	$1.19$	$12.62$	$38.63$	$87.59$
	NeuroCard	$27,252$	$14.30$	$996$	$5,051$	$3.9$$\cdot$${10}^5$	$2.08$	$25.69$	$108$	$3,318$
	MSCN	$26,697$	$20.08$	$2,802$	$15,576$	$4.9$$\cdot$${10}^5$	$2.75$	$46.51$	$465$	$83,452$
	NNGP	$10,537$	$9.47$	$785$	$4,370$	$2.4$$\cdot$${10}^5$	$1.45$	$7.19$	$25.19$	$3,318$
	ALECE	$\mathrm{𝟔}\mathbf{,}\mathrm{𝟖𝟕𝟔}$	$1.40$	$\mathbf{5.46}$	$\mathbf{11.75}$	$\mathbf{118.36}$	$\mathbf{1.07}$	$\mathbf{1.38}$	$\mathbf{1.71}$	$\mathbf{11.18}$
	Optimal	$6,770$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$
Job- light	PG	$5,608$	$1.58$	$6.12$	$14.22$	$76.30$	$1.10$	$1.32$	$1.48$	$2.89$
	Uni-Samp	$5,906$	$1.44$	$3.46$	$10.78$	¿${10}^{10}$	$1.16$	$1.68$	$1.90$	$3.28$
	NeuroCard	$17,720$	$14.15$	$822$	$4,799$	$3.5$$\cdot$${10}^5$	$1.81$	$12.40$	$37.25$	$144$
	MSCN	$25,157$	$28.54$	$1,592$	$5,261$	$99,178$	$2.06$	$15.01$	$27.77$	$84.35$
	NNGP	$11,698$	$4.6$$\cdot$${10}^8$	¿${10}^{10}$	¿${10}^{10}$	¿${10}^{10}$	$3.50$	$7.90$	$11.24$	$23.38$
	ALECE	$\mathrm{𝟒}\mathbf{,}\mathrm{𝟕𝟔𝟑}$	$\mathbf{1.16}$	$\mathbf{2.23}$	$\mathbf{4.34}$	$\mathbf{16.22}$	$\mathbf{1.07}$	$\mathbf{1.24}$	$\mathbf{1.32}$	$\mathbf{1.77}$
	Optimal	$4,708$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$
TPCH	PG	$3,377$	$1.23$	$3.94$	$5.85$	$10.28$	$1.10$	$1.39$	$1.64$	$3.06$
	Uni-Samp	¿$30,000$	$1.29$	$3.24$	¿${10}^{10}$	¿${10}^{10}$	$1.79$	$2.28$	$62.54$	$301$
	NeuroCard	$11,362$	$44.65$	$9,151$	$34,541$	$2.8$$\cdot$${10}^5$	$1.60$	$15.10$	$25.94$	$50.68$
	MSCN	$7,062$	$41.62$	$6,571$	$28,837$	$2.4$$\cdot$${10}^5$	$3.64$	$9.17$	$22.00$	$202$
	NNGP	$18,244$	$1.4$$\cdot$${10}^9$	¿${10}^{10}$	¿${10}^{10}$	¿${10}^{10}$	$5.54$	$46.30$	$59.12$	$99.12$
	ALECE	$\mathrm{𝟑}\mathbf{,}\mathrm{𝟐𝟑𝟎}$	$\mathbf{1.18}$	$\mathbf{2.66}$	$\mathbf{4.46}$	$\mathbf{11.23}$	$\mathbf{1.07}$	$\mathbf{1.23}$	$1.29$	$\mathbf{1.57}$
	Optimal	$3,226$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$

参考表5，所有方法在Dist-shift工作负载上的整体Q错误和P错误性能都比Insert-shift工作负载上的对应方法差。繁重的工作负载。 这是合理的，因为与构建这些方法所依据的数据相比，执行测试查询时底层数据的分布发生了很大的变化。 尽管如此，ALECE 仍然在所有数据集上实现了最佳 E2E 时间。 执行所有测试查询所需的时间比 PG 减少 18.5%。 它在所有三个工作负载上的 E2E 时间都接近最佳结果，并且远小于其他竞争对手。 在Q误差和P误差方面，ALECE也表现最好。 在 95% 分位数处，ALECE 的最大 Q 误差和 P 误差分别为 11.75 和 1.71。 相比之下，其他竞争对手的 Q 误差和 P 误差分别至少大 $2.48$ 和 $1.44$ 倍。 所有这些都表明，ALECE 对分布变化的敏感度较低，即使基础数据的分布发生显着变化，也能够做出准确的估计。

7. 相关工作

数据驱动的基数估计器。 数据驱动方法旨在用统计或机器学习模型来描述底层数据。 简单而高效的一维直方图（Selinger等人，1979）被用于许多著名的DBMS，如PostgreSQL。 它假设所有属性都是相互独立的，并为每个属性维护一个一维（累积）直方图。 为了解决不合理的独立性假设问题，基于M-D直方图的方法(Deshpande等人，2001；Gunopulos等人，2000；Poosala和Ioannidis，1997；Wang和Sevcik，2003)构建多维直方图对属性依赖关系进行建模。 尽管此类方法提高了精度，但联合属性的分解仍然是有损的。 此外，它们几乎不适用于具有复杂连接的查询。 基于采样的方法（Chaudhuri等人，1999；Chen和Yi，2017；Kipf等人，2019；Qiu等人，2021；Li等人，2016）解决连接查询，但它们存在高方差的风险当数据分布或查询复杂时，采样失败。 基于贝叶斯网络（BN）的方法（Chow and Liu，1968；Getoor 等人，2001；Tzoumas 等人，2011）使用有向无环图来建模属性之间的依赖关系，假设每个属性是考虑到其父母的分布，有条件地独立于其余属性。 BayesCard （Wu and Shaikhha，2020）使用概率编程重振BN，以提高其推理和模型构建速度。 最近，机器学习技术被应用于数据驱动方法中。 Naru (Yang 等人, 2019) 和 NeuroCard (Yang 等人, 2020) 采用深度自回归模型将属性的联合分布分解为条件分布的乘积。 DeepDB （Hilprecht 等人，2020） 建立在 Sum-Product Network (SPN) （Poon 和 Domingos，2011） 之上，它使用多个本地和简单的 PDF 来近似联合分布。 FLAT (Zhu 等人, 2021) 通过采用因式分解和积网络 (FSPN) (Wu 等人, 2020) 自适应分解关节来改进 SPN根据属性依赖程度进行分布。

查询驱动的基数估计器。 此类估计器专注于对查询及其真实基数之间的关系进行建模。 利用过去查询的反馈来纠正和自调整直方图（Bruno等人，2001；Fuchs等人，2007；Khachatryan等人，2015；Srivastava等人，2006）并更新统计摘要（Stillger等人，2001；吴等人，2018）。 LW-XGB 和 LW-NN (Dutt 等人, 2019) 将基数估计表述为回归问题，并分别应用梯度提升树和神经网络进行回归。 UAE-Q (Wu 等人, 2022) 通过 Gumbel-Softmax 技巧应用深度自回归模型和可微渐进采样来从查询中学习隐藏信息。 基于 KDE 的连接估计器（Kiefer 等人，2017） 将核密度估计 (KDE) 与查询驱动的调整机制相结合，以估计关系的多元概率分布和连接的基数。 Fauce (Liu 等人, 2021) 和 NNGP (Zhao 等人, 2022) 假设查询的基数遵循高斯分布，并采用 Deep Ensemble (Lakshminarayanan 等人) ，2017）和神经网络高斯过程（Lee等人，2018）来预测分布的均值和方差。

一些工作还考虑了数据和 SQL 查询。 吴等。 （Wu 和 Cong，2021） 提出了一种统一的深度自回归模型，利用数据作为无监督信息，将查询工作负载作为监督信息。 基普夫等。 al. (Kipf 等人, 2019) 将基本关系信息和查询特征连接在一起，并使用多集卷积神经网络对其进行处理和估计。 内吉等。 (Negi 等人, 2023) 提出了在连接键上构建示例表并使用神经网络从查询中提取信息的技术。 然而，这些方法要么需要对连接属性进行采样，这会导致高采样开销，要么需要对静态数据进行不可更新的特征化/采样，这不适用于动态数据库。 此外，与 ALECE 相比，这些方法无法解释数据、查询和真实基数之间的联系。 此外，Negi的工作(Negi等人, 2023)仅支持PK-FK连接。 杜特等。 al. (Dutt 等人, 2019) 使用神经网络和基于树的集成从数据和查询中提取信息，以解决单个关系的选择性估计问题。 因此，他们的方法不支持连接。 此外，Hanet。 al. (Han 等人, 2021) 提出了基数估计器的端到端评估基准。 我们使用的基准测试是它的改进版本。 太阳等。 al. (Sun 等人, 2021) 对现有的基数估计器进行了全面的比较。

8. 结论和未来的工作

在这项工作中，我们设计了 ALECE，这是一种多功能的学习基数估计模型，可以对 SQL 查询进行准确且高质量的估计。 基于两种微妙的方法分别对底层数据库数据和 SQL 查询进行特征化，ALECE 在其两个模块中采用了注意力机制来理解数据和查询之间的隐式关系。 数据编码器模块中的自注意力层找出所有数据库属性之间的链接。 查询分析器采用查询特征化的输入和数据编码器的输出，并关注数据中更重要的部分。 大量的实验结果表明，ALECE 在多个评估指标方面明显优于最先进的替代方案。

对于未来的工作，通过用其他聚合函数替换 $\mathrm{𝙲𝙾𝚄𝙽𝚃}(\ast )$ 来将 ALECE 扩展到更通用的聚合分析查询是很有趣的。 此外，探索是否存在更好的数据和查询特征化方法也很重要。 此外，在 ALECE 中使用其他类型的注意力函数也是有意义的。

附录

由于篇幅限制，我们在本附录中介绍了一些细节和相对不太重要的实验结果和分析。

附录A多头注意力

为了增强 ALECE 的表示能力，我们在两个模块中采用多头注意力机制（Vaswani 等人，2017），而不是执行单一功能。 图4描绘了其细节。

图 4. 多头注意力机制，改编自(Vaswani 等人, 2017)。

多头注意力使用 $h$ 不同的线性投影多次投影查询、键和值，然后使用投影的查询、键和值的输入执行注意力函数 $\mathrm{𝖠𝗍𝗍𝗇}$在平行下。 与单个注意力头相比，它可以共同关注来自不同投影空间的信息，因此更强大。 其解析表达式如下：

$\text{MutliHead}(𝑸\mathbf{,}𝑲\mathbf{,}𝑽)$ $=\text{concat}({\text{head}}_1,\mathrm{\cdots },{\text{head}}_h){𝑾}^M,$

${\text{where head}}_i$ $=\mathrm{𝖠𝗍𝗍𝗇}(𝑸{𝑾}_i^{𝑸},𝑲{𝑾}_i^K,𝑽{𝑾}_i^V)$

上面，${𝑾}_i^Q\in {ℝ}^{d_k\times d_m}$、${𝑾}_i^Q\in {ℝ}^{d_k\times d_m}$和${𝑾}_i^Q\in {ℝ}^{d_v\times d_m}$分别将每个查询、键和值向量投影到${ℝ}^{d_m}$空间中； ${𝑾}^M\in {ℝ}^{d_m\times d_v}$ 将加权值的输出投影回${ℝ}^{d_v}$。 在我们的实验中，$h$的值设置为8，遵循（Vaswani等人，2017）中的设置。

值得注意的是，注意力函数$\mathrm{𝖠𝗍𝗍𝗇}$的选择并不是唯一的，除了多头注意力之外，还可能存在其他类型的$\mathrm{𝖠𝗍𝗍𝗇}$集成注意力机制。 注意力层可以根据情况灵活设计。

图 5. 连接三个数据集中的关系。

附录 B改进的基准

CardEst 基准测试（Han 等人，2021） 提供了一种将外部基数估计器集成到 PostgreSQL 内置查询优化器中的方法。 特别是，给定要执行的 SQL 查询，PostgreSQL 的查询优化器需要以固定顺序获取一系列子查询的估计基数。 通过启用旋钮，基准测试提供了从给定文件读取基数估计的功能，而不是使用 PostgreSQL 内置估计器的估计。 因此，如果我们知道子查询是什么并提供通过外部估计器访问的相应基数估计，我们可以通过观察端到端查询执行时间来直接比较其生成的查询计划的质量。

上面的想法简单而有吸引力。 然而，原始基准（Han等人，2021）无法为动态工作负载和复杂连接谓词的查询生成正确的子查询。 换句话说，它仅适用于非常有限的情况。 这些缺点促使我们改进基准以支持动态工作负载和更通用的连接模式。 我们改进的基准(cod, line)实现了正确的子查询生成功能，并继承了基数估计读取功能。 我们通过对 STATS、Job-light 和 TPCH 数据集的大量查询对其进行了验证。

使用指导。 我们的基准主要提供两个功能：子查询生成和基数估计替换。 我们留下了多个旋钮，让用户决定何时生成子查询以及使用哪种方法的估计结果来为工作负载 $𝑾$ 上的查询生成查询计划。

1）子查询生成。 该功能仅与一个旋钮相关：print_sub_queries。 给定一个查询，优化器需要对两种类型的子查询进行基数估计：single子查询仅涉及单个表，而join子查询涵盖连接状况。 通过将旋钮的值设置为True，并对$𝑾$上的每个查询执行​​Explain语句，将在数据目录中生成两个文件PostgreSQL：“single_sub_queries.txt”和“join_sub_queries.txt”。 他们分别记录了上述两类子查询。 任一文件的每一行都是 $𝑾$ 上的查询 $𝚚$ 的子查询。 此外，该行还将包括所有查询中 $𝚚$ 的出现排名。 此信息可帮助用户了解查询和子查询之间的联系。

2) 基数估计替换。 在使用外部方法（例如 ALECE）估算出两个文件中子查询的心数后，我们就可以将它们 "注入 "到 PostgreSQL 中，以替换内置结果。 首先，我们需要将估计结果保存到两个文件中，每个文件对应一种类型的子查询，并将它们复制到PostgreSQL的数据目录中。 然后，应该打开两个旋钮，即read_single_cards和read_join_cards。 同时，我们应该将配置参数single_cards_fname和join_cards_fname分别设置为上述两个文件的名称。 经过这些设置后，我们就可以按照通常的方式运行工作负载了。 值得注意的是，查询优化器将使用外部方法的基数估计来生成查询计划。 假设单个子查询和连接子查询的文件分别命名为“single_cards.txt”和“join_cards.txt”。 旋钮及配置参数的设置语句如下所示。

⬇

SET read_single_cards=true;

SET read_join_cards=true;

SET single_cards_fname=’single_cards.txt’;

SET join_cards_fname=’join_cards.txt’;

通常，PostgreSQL 的内置估计器能够为单个子查询提供足够准确的基数估计。 因此，大多数情况下，我们只需要估计连接子查询的基数，打开read_join_cards旋钮并设置参数join_cards_fname即可。

另请参阅我们的 github 存储库 (cod, line) 了解更多详细信息。

附录 C其他实验结果

本节介绍由于篇幅限制无法放入论文主体的额外实验结果。

C.1。 连接关系之间的信息

图5显示了STATS、Job-light和TPCH数据集中关系之间的连接信息。 为了清楚起见，仅显示部分连接。

C.2。 静态工作负载的性能

我们还进行了实验来比较仅包含查询语句的静态工作负载上的所有方法。 特别是，我们使用整个 STATS、Job-light 和 TPCH 数据集来构建数据驱动的方法。 在整个数据集之上，训练查询和子查询及其真实基数用作查询驱动方法的训练和验证数据。 因此，所有数据驱动和查询驱动的方法都会估计测试子查询的基数。 这些估计依次用于生成 E2E 评估结果、Q 误差等等。表6报告了相关的比较结果。

表 6. 静态工作负载上方法的性能

Data	Model	E2E Time(S)	Q-error				Size (MB)	Building Time(Min)	Latency (ms)
			50%	90%	95%	99%
STATS	PG	$12,777$	$1.80$	$21.84$	$106$	$7,950$	-	-	-
	Uni-Samp	$15,397$	$\mathbf{1.33}$	$6.64$	¿${10}^{10}$	¿${10}^{10}$	$4.44$	$\mathbf{0.02}$	$413$
	NeuroCard	$19,847$	$2.91$	$192$	$1,511$	$1.5\cdot {10}^5$	$121.88$	$27.77$	$40.16$
	MLP	$7,823$	$1.58$	$4.62$	$9.22$	$76.97$	$8.52$	$3.10$	$3.10$
	MSCN	$15,162$	$3.85$	$39.56$	$99.81$	$1,273$	$\mathbf{1.61}$	$12.41$	$\mathbf{0.79}$
	NNGP	$20,181$	$8.10$	$694$	$3,294$	$2.3$$\cdot$${10}^5$	$9.56$	$0.68$	$21.28$
	ALECE	$\mathrm{𝟕}\mathbf{,}\mathrm{𝟕𝟎𝟒}$	$1.47$	$\mathbf{4.86}$	$\mathbf{9.11}$	$\mathbf{56.98}$	$22.31$	$6.44$	$8.64$
	Optimal	$7,622$	$1$	$1$	$1$	$1$	-	-	-
Job- light	PG	$19,820$	$1.70$	$9.41$	$16.25$	$50.19$	-	-	-
	Uni-Samp	$19,146$	$\mathbf{1.32}$	$3.31$	$6.00$	¿${10}^{10}$	$31.83$	$\mathbf{0.48}$	$187$
	NeuroCard	$18,153$	$1.37$	$4.16$	$6.35$	$15.22$	$49.96$	$9.83$	$16.76$
	MLP	$18,413$	$1.40$	$3.78$	$7.00$	$76.30$	$6.19$	$1.83$	$2.25$
	MSCN	$24,829$	$10.94$	$200$	$396$	$2,741$	$\mathbf{1.56}$	$31.68$	$\mathbf{1.04}$
	NNGP	¿$30,000$	$6.66$	$121$	$414$	$1.5$$\cdot$${10}^5$	$32.44$	$\mathbf{0.88}$	$30.35$
	ALECE	$\mathrm{𝟏𝟖}\mathbf{,}\mathrm{𝟎𝟏𝟓}$	$1.44$	$\mathbf{3.23}$	$\mathbf{5.75}$	$\mathbf{47.28}$	$22.25$	$5.88$	$7.32$
	Optimal	$17,939$	$1$	$1$	$1$	$1$	-	-	-
TPCH	PG	$12,217$	$1.23$	$3.95$	$6.22$	$11.33$	-	-	-
	Uni-Samp	$19,319$	$1.16$	$3.09$	¿${10}^{10}$	¿${10}^{10}$	$30.95$	$\mathbf{0.14}$	$26.24$
	NeuroCard	$12,020$	$\mathbf{1.09}$	$2.97$	$395$	$450$	$850.53$	$44.39$	$35.98$
	MLP	$8,957$	$1.44$	$2.50$	$3.79$	$10.91$	$8.63$	$2.68$	$3.67$
	MSCN	$11,893$	$4.29$	$36.76$	$83.76$	$321$	$\mathbf{1.58}$	$24.17$	$\mathbf{0.80}$
	NNGP	$13,183$	$31.89$	$1,052$	$2,104$	$11,811$	$32.44$	$0.91$	$39.66$
	ALECE	$\mathrm{𝟖}\mathbf{,}\mathrm{𝟕𝟏𝟕}$	$1.24$	$\mathbf{2.36}$	$\mathbf{4.26}$	$\mathbf{10.73}$	$22.34$	$7.15$	$10.31$
	Optimal	$8,706$	$1$	$1$	$1$	$1$	-	-	-

如表6所示，基数估计器在静态工作负载上的端到端性能与动态工作负载上的对应性能不同。 总体而言，这些方法在静态工作负载上的性能优于动态工作负载上的性能。 尽管如此，ALECE 仍然是所有方法中表现最好的。 ALECE 的查询执行速度分别比 PG、Uni-Samp、NeuroCard、MSCN 和 NNGP 快 1.66、2.00、2.58、1.97 和至少 3 倍。 ALECE的E2E时间最多只比Optimal长1.1%。 接下来，在所有数据集上，在大多数分位数上，ALECE 的 Q 误差都小于其他的 Q 误差。 在 95% 分位数处，ALECE 达到或超过 $11.64\times$、${10}^9\times$、$166\times$、$77\times$ 和 $494\times$ 分别与 PG、Uni-Samp、NeuroCard、MSCN 和 NNGP 相比，Q 误差更小。 ALECE 在训练时间、延迟和内存成本方面并不是最好的。 然而，ALECE 的结果与竞争对手相当。 考虑到 ALECE 实现的更好的 E2E 时间和估计精度，稍微额外的开销是可以接受的。

ALECE 与 MLP 在静态工作负载上的比较。 参考表6，MLP 实现了与 ALECE 的同类产品相当的 E2E 时间和 Q 错误，甚至还具有更少的存储开销、延迟和训练时间。 背后的原因是，在处理静态工作负载上的查询时，ALECE 几乎等同于 MLP，其中查询的数据库状态是恒定的。 在这种情况下，数据编码器模块中自注意力层的键、值和查询的输入集中仅存在一个元素。 这与查询分析器模块中的三组注意力层相同。 因此，两个注意力层几乎没有任何作用，整个 ALECE 网络退化为 MLP。 因此，如果没有基础数据变化，我们可以简单地训练 MLP 来估计基数。

C.3。 $d_x$的效果

参数$d_x$用于控制数据特征覆盖的分布信息量。 较大的 $d_x$ 通常意味着更多的信息特征，但会导致更多的存储和延迟开销。 为了研究 $d_x$ 的影响，我们构建了四个具有不同 $d_x$ 值的 ALECE 版本，并观察它们在 STATS 数据集的 Insert-heavy 工作负载上的性能。 其他数据集和其他工作负载的结果类似，因此省略。 表7显示了不同$d_x$值的ALECE结果。 随着 $d_x$ 值的增加，ALECE 能够做出更准确的估计。 同时，构建时间并没有太大变化。 存储开销和延迟略有增加。 特别是，当$d_x$的值从$10$增加到$40$时，ALECE的内存消耗仅增加$0.51$MB。 此外，$d_x$ 的值不会影响执行数据操作语句时更新数据库状态的成本。 因此，我们建议使用更大的 $d_x$ 在可承受的内存和延迟成本内构建数据库状态。

表 7. 超参数$d_x$的影响

$d_x$	Q-error				Size (MB)	Building Time(Min)	Latency (ms)
	50%	90%	95%	99%
10	$1.26$	$5.52$	$13.57$	$78.16$	$\mathbf{22.15}$	$9.47$	$\mathbf{8.08}$
20	$1.33$	$5.49$	$12.65$	$65.52$	$22.21$	$\mathbf{8.83}$	$8.11$
40	$1.29$	$5.07$	$11.54$	$\mathbf{62.52}$	$22.31$	$9.25$	$8.25$
80	$\mathbf{1.24}$	$\mathbf{5.00}$	$\mathbf{10.76}$	$64.25$	$22.56$	$9.66$	$8.78$

C.4。 超参数研究

为了研究更多超参数的影响，我们构建了不同的 ALECE 版本并观察它们的性能。 同样，我们仅显示 STATS 数据集的 Insert-heavy 工作负载上的比较结果。 其他数据集和其他工作负载的结果类似，因此省略。

$n_{\mathrm{𝖾𝗇𝖼}}$ 和 $n_{\mathrm{𝖺𝗇𝖺}}$ 的效果。 $n_{\mathrm{𝖾𝗇𝖼}}$ 和 $n_{\mathrm{𝖺𝗇𝖺}}$ 分别是 ALECE 数据编码器和查询分析器模块中堆叠多头注意力层的数量。 为了研究它们是否影响 ALECE 的性能，我们训练了一系列具有不同 $n_{\mathrm{𝖾𝗇𝖼}}$ 和 $n_{\mathrm{𝖺𝗇𝖺}}$ 值的 ALECE。 表8报告了比较结果。

表 8. 超参数$n_{\mathrm{𝖾𝗇𝖼}}$和$n_{\mathrm{𝖺𝗇𝖺}}$的影响

$n_{\mathrm{𝖾𝗇𝖼}}$	$n_{\mathrm{𝖺𝗇𝖺}}$	Q-error				Size (MB)	Building Time(Min)	Latency (ms)
		50%	90%	95%	99%
2	2	$1.37$	$6.33$	$13.69$	$90.04$	$\mathbf{10.36}$	$\mathbf{7.12}$	$\mathbf{6.13}$
2	4	$1.32$	$5.95$	$11.77$	$67.02$	$16.33$	$8.43$	$7.47$
4	2	$1.35$	$5.88$	$11.27$	$78.26$	$16.33$	$7.69$	$7.62$
4	4	$\mathbf{1.29}$	$5.07$	$11.54$	$\mathbf{62.52}$	$22.31$	$9.25$	$8.25$
4	6	$1.32$	$5.57$	$11.01$	$73.36$	$28.29$	$10.17$	$8.80$
6	4	$1.45$	$5.59$	$11.60$	$69.10$	$28.29$	$9.05$	$8.92$
6	6	$\mathbf{1.29}$	$\mathbf{4.74}$	$\mathbf{10.45}$	$75.22$	$34.26$	$9.92$	$9.19$

如表8所示，ALECE的存储开销明显受到$n_{\mathrm{𝖾𝗇𝖼}}$和$n_{\mathrm{𝖺𝗇𝖺}}$的影响。 当$n_{\mathrm{𝖾𝗇𝖼}}$和$n_{\mathrm{𝖺𝗇𝖺}}$的值变大时，ALECE也会导致更大的内存消耗。 然而，ALECE 的 Q 错误性能并不一定与其两个模块中注意力层的数量呈正相关。 当$n_{\mathrm{𝖾𝗇𝖼}}$和$n_{\mathrm{𝖺𝗇𝖺}}$的值设置为较小的2时，ALECE的估计精度最差。 当$n_{\mathrm{𝖾𝗇𝖼}}$和$n_{\mathrm{𝖺𝗇𝖺}}$都等于4或6时，ALECE具有整体最佳的Q误差性能。 但是，较大的 $n_{\mathrm{𝖾𝗇𝖼}}$ 或 $n_{\mathrm{𝖺𝗇𝖺}}$ 将导致较大的存储和延迟开销。 因此，我们将两个参数的值都设置为 4。

连接条件特征化方式的影响。 在3.2节中，我们提到，与简单地特征化每个连接谓词是否出现在SQL查询中相比，我们额外特征化连接中涉及的关系的方式更加紧凑、信息丰富并且有助于估计。 为了验证这一说法，我们通过构建两个具有不同连接谓词特征化方式的 ALECE 版本并观察它们的性能来进行消融研究。 比较结果如表9所示。

表 9. 连接谓词特征化方式的影响

Featurization way	Q-error				Size (MB)	Building Time(Min)	Latency (ms)
	50%	90%	95%	99%
Simple (Zhao et al., 2022)	$1.36$	$5.78$	$\mathbf{11.48}$	$73.85$	$\mathbf{22.28}$	$9.42$	$\mathbf{8.20}$
Ours	$\mathbf{1.29}$	$\mathbf{5.07}$	$11.54$	$\mathbf{62.52}$	$22.31$	$\mathbf{9.25}$	$8.25$

显然，我们的连接谓词特征化方法可以带来更好的 Q 错误性能，但会稍微增加内存成本和延迟。

C.5。 连接中关系数量的影响

我们还研究了 ALECE 查询中涉及的关系数量及其替代方案的影响。 根据涉及的关系数量，STATS Insert-heavy工作负载的测试子查询分为两类。 两个类别中的子查询分别涵盖 $\le 3$ 和 $\ge 4$ 连接谓词。 然后，我们观察每种方法在不同类别上的 Q 误差分布。 如图6中的结果所示，ALECE能够实现最佳的整体性能。 所有方法在涉及较少关系的查询上都具有更好的 Q 错误分布性能。 然而，ALECE 在关系越来越少的查询上实现的 Q 错误之间的差距远远小于竞争对手。 这意味着 ALECE 可以有效地理解真实基数和复杂连接模式之间的隐式关系。

图 6. 具有连接数量的 Q 错误分布

C.6。 DB 状态类型的影响

我们进行了额外的实验来研究数据库状态类型的影响。 我们构建了三个具有不同类型数据库状态的 ALECE 变体：

• Histogram 是我们在论文中使用的 DB 状态类型。

• Sample是通过从底层数据中均匀采样构建的。 对于每个关系$R$，我们维护一个固定大小$M$的样本集$S_R$。当引用关系 $R$ 的数据操作语句出现时，$S_R$ 可能会被更新。 保证$R$中的每个元组都被等可能采样。 在我们的实验中，$M$的值设置为512。 换句话说，每个DB状态向量的维度为512。

• NE-Hist 是所有属性值范围内大小不等分区的直方图集。 具体来说，我们首先从初始数据集中提取属性 $A$ 的所有值。 然后 $A$ 的范围被划分为 $d_x$ 部分，每个部分覆盖相同数量的值。 NE-Hist 数据特征的每个元素都是通过对齐每个 $i$ 的值频率 $f_i$ 生成的向量，其中 $f_i$ 指落入其中的值的数量第 $i$ 个分区。 值得注意的是，所有$f_i$的值最初都是相同的。 随着工作负载中数据操作语句的执行，$f_i$的值会不断变化。

表 10 显示了 STATS 数据集的 Insert-heavy 工作负载上具有不同类型数据库状态的三个 ALECE 变体的 Q 错误分布、存储开销和延迟。 其他数据集和其他工作负载的结果类似，因此省略。

表 10. DB 状态类型的影响

DB state type	Q-error				Size (MB)	Latency (ms)
	50%	90%	95%	99%
Histogram	$\mathbf{1.29}$	$\mathbf{5.07}$	$\mathbf{11.54}$	$62.52$	$\mathbf{22.31}$	$8.25$
Sample	$1.52$	$5.95$	$12.86$	$\mathbf{60.87}$	$23.23$	$8.67$
NE-hist	$1.41$	$6.01$	$13.93$	$77.74$	$\mathbf{22.31}$	$\mathbf{8.23}$

参考表10，所有三种数据库状态类型都能够帮助ALECE实现准确的估计。 值得注意的是，所有这些特征都可以被视为单个属性的边际分布近似。 ALECE 的数据编码器模块在边缘分布和联合分布之间建立了一座桥梁。 它可以定量地“计算”任意两个数据库状态的一对元素之间的相关性。 因此，它可以有效地发现任意一对属性之间的隐式联系，这有助于基数估计任务。

尽管如此，当数据操作语句出现时更新直方图的成本比更新其他类型的数据库状态的成本要小。 因此，我们的 ALECE 采用简单的直方图作为论文中的 DB 状态。 未来，我们将研究更多类型的 DB 状态。