作者来自 Elastic Thomas Veasey 及 Jan Kuipers解释我们用来获得快速近似 ES|QL 查询的方法以及我们对误差估计所做的测试。动手实践 Elasticsearch深入了解我们在 Elasticsearch Labs 仓库中的示例 notebooks开始免费的云试用或现在就在本地机器上尝试 Elastic。正如我们在之前的博客中讨论的我们正在引入快速近似 ES|QL STATS 查询该功能将在 Elasticsearch 和 Elastic Stack 的 9.4 版本中提供。此功能允许用户通过放宽返回精确值的约束来估计一个高成本的分析查询其速度通常比运行完整查询快几个数量级。我们认为这有很多用途例如我们计划将其集成到 Kibana 中以便在可能的情况下获得快速图表预览。为了让你能够信任我们的估计我们提供误差估计。此外由于误差估计中存在一些边界情况我们会在估计值和误差可信时进行认证。在这篇博客中我们将深入探讨对这类查询进行近似和误差估计的理论并讨论我们所做的测试。背景为了高效地估计 ES|QL STATS 查询我们利用了许多统计量共有的一个性质从数据集中大量独立样本计算得到的估计值会逼近其真实值。在一个包含某字段的索引中我们可以将统计量的真实值看作是在上具有均匀离散分布的随机变量所计算得到的值。下面我们用表示这个量它可以是 AVG、MEDIAN 等。如果我们从中进行 n 次独立抽样记为使得每个值被选中的概率为那么我们就得到了该随机变量的 n 个独立副本。我们依赖的性质意味着从 S 计算得到的样本统计值 θ^ 会随着 n 的增大而逼近 θ。例如如果 θ 是某些度量值的平均值那么当足够大时成立。事实上对于许多统计量其极限误差分布已知为正态分布。此外它只依赖于的分布、样本大小 n 以及聚合类型。这意味着支持的 STATS 查询可以在与索引大小 |X| 无关的固定精度下进行近似。从 Apache Lucene 索引中随机抽取值是很容易的创建一个过滤器以指数分布的跳跃在数据集中移动其中期望跳跃大小由所需的采样概率控制。该过滤器与任何其他 Lucene 查询进行 AND 运算时效率极高因为对过滤查询进行 AND 运算正是其优化重点之一。在我们的另一篇文章中我们讨论了一些真实查询示例以展示在不同精度水平下获得的加速效果。到目前为止我们只讨论了如何获得查询的估计值。虽然这样的点估计器可能有用但如果不了解其误差其用途是有限的。我们发现 ES|QL 具有现有能力使得同时引入低成本、灵活且准确的误差估计变得相对容易。接下来我们将讨论这一点。误差估计我们认为对估计中的不确定性提供准确理解对用户信任该近似结果至关重要。虽然仅仅提供快速估计 ES|QL 查询的能力在某些场景下也有用但我们希望提供更丰富的功能使客户端能够做出更智能的选择。例如如果一个近似查询用于预览图表而误差只有几个像素那么再运行一次昂贵查询来重绘就没有太大意义。我们选择用置信区间来表示误差更准确地说是中心置信区间。它可以用被估计统计量的累积分布函数来表示。具体而言它是一个区间该区间以概率包含真实值其端点分别为及。置信区间的计算实际上非常微妙。同时对于我们的使用场景还存在一些重要约束使得标准方法并不理想。接下来我们将更详细地讨论我们采用的方法的动机与设计。整个项目的一个关键需求是大幅加速昂贵的分析查询。因此至关重要的是估计不确定性的开销不能相对于查询结果本身的估计过大。我们也希望该功能尽可能通用同时在语言内部保持 “隔离”。换句话说ES|QL 是一种非常灵活的语言我们希望估计能力尽可能覆盖其中的表达方式。同时我们也不希望引入一个横跨所有功能的特性从而对每一个新特性开发都造成额外成本。基于这些考虑我们选择通过对样本集进行分区并在每个子样本上计算查询输出来估计置信区间。这这类似于 bootstrap自助法方法然而由于我们保证每个分区都来自不相交的随机样本子集因此我们知道它们构成了该统计量分布的真实估计。为了尽可能准确地估计统计量本身我们仍然在完整样本上计算其值。例如为了估计均值及其分布该过程可以表示如下FROM data | SAMPLE probability | EVAL bucketId RANDOM(B) // B is the number of buckets | STATS avg AVG(x) avg_0 AVG(x) WHERE bucketId0 (...) avg_B-1 AVG(x) WHERE bucketIdB-1 BY grouping | EVAL confidence_interval CONFIDENCE_INTERVAL(avg, avg_0, ..., avg_B-1)这引入了一个需要处理的复杂性需要考虑用于估计查询统计量的值的数量与用于采样其分布的值的数量之间的不一致。这是一个缺点不过它也带来了一些显著优势。大多数分析查询的计算工作都集中在聚合统计的计算上在 STATS 归约之后的后处理作用于一个小得多的表其成本通常相对较低。在这种方案中与仅仅估计统计量相比输入到 STATS 命令的每一行数据都会被精确处理两次。因此粗略来说我们为估计不确定性所付出的开销与估计查询本身的成本处于同一数量级。由于我们通常能比精确查询快几个数量级这样的开销是可以接受的。由于该过程使用的是一个普通的表结构只是在其中增加了用于分布采样的额外列因此我们可以将整个表传递通过任何 ES|QL 管道并在最终结果上计算置信区间。例如如果我们在上述管道中加入 EVAL square_avg avg * avg那么我们将得到完全对应的 square_avg、square_avg_0、…、square_avg_B-1 这些额外值。在管道结束时我们得到了原始统计量及其所有派生量的分布样本。因此我们可以应用标准的置信区间计算机制来对表进行归约并将这些样本进一步转换为派生量的置信区间。整个过程对于 ES|QL 语言的其余部分来说基本是透明的正如我们上面展示的它可以通过查询重写来实现。置信区间计算我们有该统计量分布的独立样本。然而这些样本是在比我们的估计使用更少的值的情况下计算得到的。我们同时只有相对较少的分布样本这是为了避免样本数量差异过大并防止表格膨胀。因此我们更倾向于使用参数化方法来估计置信区间。对于我们支持估计的这些统计量其误差在由大量样本计算时其极限分布通常趋近于正态分布。因此一个自然的选择 —— 标准区间 —— 是从样本中估计均值和标准差并报告相应的正态置信区间。 这里表示标准正态分布函数。对于重尾数据以及对异常值敏感的统计函数例如 STD_DEV收敛到正态分布的速度可能较慢从而导致置信区间校准不佳。简要来说为了评估这些区间的质量可以检查它们的校准情况。具体而言可以计算一个称为 coverage覆盖率的量。对于中心置信区间它在次试验中应当有大约次包含真实统计值。实际上由于我们使用的是中心置信区间可以做出更强的表述真实值应当在置信区间上界之上或下界之下的次数在次试验中分别约为。经验覆盖率就是在大量试验中计算得到的这一比例。它使我们能够通过模拟比较不同方法。我们将在报告测试结果时再次回到这一点。为了获得更好的置信区间我们尝试了几种不同方法分位数的 Cornish–Fisher 校正以及偏差校正加速bias-corrected accelerated - BCa置信区间的改编版本。模拟结果显示 BCa 在不同置信水平下提供了更稳定的校准因此我们选择了该方法。其基本思想由 Efron 提出即假设存在一个关于底层统计量的单调变换 g g(θ)当作用于分布样本时可以将其分布 “正态化”(1)这里而是标准正态随机变量。这显然是在放宽“统计量本身服从正态分布”这一假设而标准区间正是基于该假设推导出来的。实际上这一类模型包含了许多分布形式因为只被要求是单调函数。你可以把看作是一个一阶泰勒展开用于描述方差是真实参数值某个任意函数的情况。这进一步放宽了“标准化变换同时稳定方差”的假设。这种方法的一个优点是本身不需要被显式计算并且可以从分布样本中用标准方法估计参数和。对于可以通过让估计值落在变换后分布的中位数来处理。如果假设 θ 空间中的累积分布函数为那么其中是估计的统计量值如前所述是标准正态分布函数。通常 Fθ 会用经验分布函数近似而经验分布函数通常通过 bootstrap 间接计算。然而有些出人意料的是大量模拟结果显示我们在这里使用对样本值的正态近似反而得到了更好的校准效果即 其中和分别是经验均值和标准差。为了完成整个过程可以将 (1) 式重新整理从而得到的分位数如下其中是对应分位数的标准正态 z 分数。通常会使用经验累积分布函数的逆来把分位数转换回置信区间。然而由于用于计算分布样本的值的数量与查询估计之间存在不匹配我们需要做某种缩放处理。通过模拟实验探索不同方案后我们再次发现使用正态近似效果最好其中是我们使用的分布样本数量。这相当于对方差按进行常规缩放。Efron 表明在服从分布即仅依赖于真实值的情况下加速项可以在不需要任何的知识下估计。特别地在我们的假设下这些统计量在均值为时趋向于正态分布。由于偏度skew对平移和缩放是不变的因此有即为分布样本的偏度的六分之一。这里有一点被简化掉的是偏度以及因此加速参数对样本大小的依赖性。我们知道它会随着样本数量增加而趋近于 0。事实上偏度也以的速度衰减因此我们进一步将加速项调整为以补偿样本与估计之间的数量不一致。尽管通过更好的方法我们显著提升了置信区间的校准效果但在某些 STATS 函数的底层分布具有非常重尾的情况下仍然会出现问题。因此我们接下来引入一些额外的保护机制。保护机制Guard rails为了避免用户需要理解过多边界情况当我们无法确认分布样本是否按预期行为时会提供额外的安全机制。这通常发生在在给定度量分布的情况下用于计算统计量的值的数量不足时。对于高度偏斜的指标数据以及某些对异常值敏感的聚合函数例如 STD_DEV这种问题会更加严重。我们对用于估计统计量的最小值数量设有一些全局约束只有满足这些约束时我们才会进行认证。例如如果任何 bucket 为空那么我们就无法依赖这些分布样本。这是因为 ES|QL 允许混合使用近似统计而这些统计在处理空 bucket 时的行为可能不同。例如考虑以下查询SET approximationtrue; FROM data | STATS avg AVG(x), sum SUM(y) | EVAL mix avg sum对于空 bucket没有一种自洽的方法可以正确为 mix 赋值因为求和操作要求我们将其视为 0在这种情况下会对 avg 的估计引入偏差。另一方面如果忽略空 bucket则会在 sum 上引入偏差。我们还设置了一个全局最小值数量阈值在该阈值下我们确认认证方法足够可靠该值为 10。我们探索了多种额外的测试方法来对结果进行认证。这些方法既基于对底层数据分布的检验特别是 Hill 估计器也基于统计量分布本身的性质。如果统计量的真实分布足够接近正态分布那么我们的估计及置信区间计算就会符合预期区间校准良好区间宽度能够反映实际误差。因此最终我们选择了一种基于分布样本的偏度skewness和峰度kurtosis相对于正态分布零假设的 p 值检验方法。为了认证一个结果我们要求这两个检验的双尾 p 值都大于 0.05。如下所示这一测试与我们的实际需求高度一致用于区分哪些估计及其置信区间更可靠。我们可以使用一个简单技巧来提升该测试的准确性构造多个独立的分布样本并进行投票。给定一个失败率为 f 的认证测试在零假设即估计是可靠的成立的情况下次失败在次测试中的分布为例如对于多数投票majority vote假设 0.05 且 3那么该测试的显著性为也就是说我们对可信结果误拒绝的概率低于 1%。注意我们可以通过使用不同 RANDOM bucket 标识符的 seed很容易地计算多个试验。这一额外检查使我们能够认证我们信任估计值及其误差。在近似查询结果中我们会展示这一信息。当无法通过认证时结果不一定是不准确的但应当被更谨慎地对待。测试Testing这里讨论的测试主要有两个目标一是理解置信区间的校准情况二是观察它们对统计量估计误差的刻画程度。count 函数的行为特别良好其误差分布是二项分布因此我们的大部分测试集中在度量聚合metric aggregations上。我们研究了平滑分布同时确保覆盖不同的尾部行为范围。异常值的存在是降低统计估计精度的关键因素。例如如果某个异常值完全没有被采样到它可能会显著影响某些统计量的结果。我们探索了一系列轻尾分布例如均匀分布和正态分布以及偏斜和重尾分布例如指数分布、对数正态分布、柯西分布和帕累托分布。对于每一类分布我们使用了多种参数化方式主要关注尺度参数的变化。总共我们使用了 24 种不同的数据分布。图 1 展示了该集合中的一些示例采样分布。需要注意的是我们对图表进行了截断以移除极端异常值这些异常值在柯西分布和对数正态分布中都存在。图 1 - 示例度量采样分布对于每种数据分布我们评估了 14 种不同的样本规模范围从 1000 到 500000。随后对于每一组样本我们分别计算了 AVG、COUNT、MEDIAN_ABSOLUTE_DEVIATION、MEDIAN、PERCENTILE[25, 75, 90, 95, 99]、SUM 和 STD_DEV并在两个置信水平下进行评估50% 和 90%。总共我们进行了大约 7500 个不同实验。对于每个实验我们通过 100 次运行来评估区间校准情况并统计真实统计值落在置信区间内的次数。这使得我们得到一个二项分布的覆盖率coverage估计。我们预期的覆盖率波动会随着置信水平略有变化例如在 50% 置信水平下我们主要观察到的值在 0.44 到 0.56 之间在 90% 置信水平下在 100 次试验中我们主要观察到的值在 0.86 到 0.94 之间。图 2 展示了所有实验在两个置信水平下的经验覆盖率箱线图。在所有情况下置信区间的校准都相当良好。极端分位数在小样本情况下存在偏差这会导致小样本时异常值数量增加。经验法则是为了确保在相应尾部有足够样本样本数量应大致满足图 2 - 已认证结果中 50% 和 90% 置信区间的经验覆盖率接下来我们考察置信区间在多大程度上能够刻画估计误差的典型大小。为此我们对所有已认证结果计算“估计统计量误差”与“置信区间宽度的一半”的比值分布。置信度越高区间越宽因此不同置信水平会改变该分布的均值位置。图 3 展示了在 90% 置信区间下计算得到的该分布。如预期所示该分布大致呈正态形状但在尾部存在一些较大的误差值。在所有情况下我们都观察到置信区间的宽度能够正确反映估计统计量实际误差的数量级。图 3 - 查询误差与已认证置信区间宽度的关系我们已经证明已认证结果几乎总是可靠的然而我们也希望了解在未通过认证的结果中有多少实际上仍然是可靠的以确认该测试与我们的目标一致。这里我们将 “可靠” 定义为一个较强的含义置信区间是校准良好的。具体而言对于 50% 和 90% 的置信区间我们统计那些未认证结果中其置信区间经验校准在给定试验次数下仍处于可接受误差范围内的比例。通过该方法我们发现所有实验中的假阳性率约为 1%。这一结果与基于测试参数所预期的随机失败率高度一致并验证了该测试背后的假设。最后为了更好地理解已认证与未认证结果之间的差异图 4 分别展示了 “已认证” 和 “未认证” 结果中估计统计误差与 90% 置信区间宽度一半的比值分布。需要注意的是我们对未认证区间的范围进行了截断处理。图 4 - 已认证与未认证置信区间下的查询误差分布总结Wrapping up在本文中我们介绍了用于快速估计 ES|QL 查询并提供其误差提示的方法背景。为此我们开发了一种有效的置信区间机制使我们能够提供误差估计。该方法还允许我们通过其他 pipeline 操作对由采样统计量推导出的量计算置信区间。与仅仅进行查询估计相比误差量化的额外开销相对较小。最后我们设计了一种统计测试来对返回结果进行认证。未通过认证的值仍然可能是准确的但我们对其置信度较低。除了在多种真实世界用例上测试该功能我们在配套文章中进行了讨论之外我们还通过大规模模拟对误差估计进行了测试覆盖了不同的数据特征、样本大小、聚合函数以及置信水平。这表明置信区间具有良好的校准性并且区间本身能够很好地近似我们在估计中观察到的实际误差。最后我们证明了可以以较低的假阴性率对区间进行认证。我们计划在未来将该功能集成到 Elastic 技术栈的其他能力中敬请期待。原文https://www.elastic.co/search-labs/blog/fast-approximate-esql-part-2