使最近值查询速度提高数百倍

作者：Nga Tran / Andrew Lamb / 开发者
2024年3月18日

导航到

本文解释了数据库如何优化查询，这可以使查询运行速度提高数百倍。虽然我们专注于InfluxDB 3.0重要的特定查询类型，但我们描述的优化过程适用于任何数据库。

优化查询就像玩乐高

您可以使用相同的乐高积木组合出不同的结构，如图1所示。虽然您通常使用相同的砖块来构建您想要的任何结构，但在某些情况下，您需要不同形状的零件（例如，微小的星星）来完成特定项目。

lego-structure

图1：由相同的乐高方块和长方形组合出的两种不同结构

在数据库中，运行查询意味着运行一个查询计划，这是一个由不同运算符组成的树，用于处理和流式传输数据。每个运算符就像一个乐高积木：根据它们的连接方式，它们可以计算出相同的结果，但性能不同。查询优化的大部分工作涉及交换或移动现有的运算符，以形成一个更好的查询计划，但在一些罕见的情况下，需要一个新的特殊运算符来更好地完成任务。

让我们通过创建一个专门的运算符和重新组合现有运算符来形成一个具有优越性能的查询计划，来举例说明如何通过优化查询。

查询最新的值

作为时序数据库，一个常见的用例是管理来自许多设备的信号数据。一个常见的问题是：“指定的设备（例如，设备编号10）最后发送了什么信号？” 这个问题的答案（或其变体）通常用于驱动UI或监控仪表板。使用SQL，可以回答这个问题的查询是

SELECT   …
FROM     signal
WHERE    device = 10
       AND time BETWEEN now() - interval 'X days' and now()
ORDER BY time DESC
LIMIT    1;

过滤器 time BETWEEN now() - interval 'X days' and now() 稍微缩小了问题的范围：“过去X天内，设备编号10最后发送了什么信号？”

虽然这个查询很简单，但实际的查询可能更复杂。例如，“查找过去五个值的平均值”，因此我们的解决方案必须能够处理这些更通用的查询。

这些查询返回结果以毫秒为单位也非常重要，因为每个设备所有者都频繁请求值。一个挑战是所有者不知道最后信号发生的时间——可能是五分钟前或几个月前。因此，时间范围X的值可能非常大，查询运行时间也可能很长。除非用户非常小心地编写他们的查询，否则将读取和处理大量数据，增加查询返回时间。

与传统的关系型或时间序列数据库不同，InfluxDB 3.0以Parquet文件的形式存储数据，而不是自定义文件格式和专用索引。我们的目标是使这类查询无论时间范围X有多大，都能在毫秒内运行，而不引入特殊索引。

改进前后的运行时间

在解释我们的方法之前，让我们看看图2中的结果。蓝色代表改进前不同时间范围内查询的标准化运行时间，绿色代表改进后的。查询在运行30个单位后超时，因此达到30个单位的查询的实际运行时间更高。如图所示，我们的改进使长时间范围查询的运行速度提高了数百倍，并将所有查询的运行时间降低到客户要求的水平。

Before-after

图2：改进前后查询运行时间

接下来，让我们看看我们是如何实现这一点的。

改进前的查询计划

图3显示了改进前的查询计划的简化版本，使用了排序合并算法。我们从底部向上读取查询计划。输入包括四个文件，四个相应的扫描操作员并行读取。每个扫描输出经过相应的排序操作员，按降序时间戳排序数据。四个排序输出流被发送到一个合并操作员，该操作员将它们合并成一个单一的排序流，并在达到限制行数后停止，在这个例子中为1。在signal表中还有许多其他文件，但InfluxDB首先根据查询的过滤器修剪不必要的文件。

Query plan using sort merge algorithm

图3：使用排序合并算法的查询计划

当文件重叠时，InfluxDB可能需要‌去重数据。图4显示了更准确的计划，它首先将重叠文件（文件2和文件3）的数据排序在一起，并在将数据发送到排序和合并操作员之前进行去重。

InfluxDB query plan using sort merge algorithm but grouping overlapped files first

图4：使用排序合并算法的InfluxDB查询计划，但首先分组重叠文件

下一节中描述的优化仅依赖于计划顶部的操作员，因此图5中的简化计划更清楚地说明了解决方案。请注意，我们省略了计划中的许多其他细节——例如，由于查询中的LIMIT 1，排序操作员并不对整个文件进行排序，而是简单地保留Top “K” 行。

请注意，进入合并操作员的数据流不重叠。

Figure-5

图5：计划顶部包括合并操作员的非重叠数据流的部分

分析计划和识别改进

通常在合并多个流时，必须先知道所有输入，然后才能产生任何输出（因为第一行可能来自任何一个输入）。这意味着在上述计划中，我们必须读取并排序所有输入流。然而，如果我们知道流的时序范围不重叠，我们可以简单地逐个读取并排序流，直到找到所需的行数。这不仅比合并数据的工作量小，而且如果所需的行数很少，可能只需要读取单个流。

幸运的是，InfluxDB在读取文件之前有关于每个文件中数据时序范围的统计数据，并将重叠的文件分组以产生非重叠的流，如图5所示。因此，我们可以利用这一观察结果来制定一个更快的查询计划，而无需额外的索引或统计数据。然而，逐个读取流并在达到限制时停止的行为已不再是合并。我们需要一个新的操作符。

新的查询计划

考虑到上述观察结果，图6说明了新的查询计划

  1. 非重叠数据流按时间降序排序。
  2. 一个新的操作符，ProgressiveEval，取代了merge操作符。

新的ProgressiveEval操作符按顺序从其输入流中拉取数据，并在达到请求的限制时停止。与merge操作符相比，ProgressiveEval的主要区别在于，merge操作符只能在其所有输入排序操作符完成之后开始合并数据，而ProgressiveEval可以在第一个排序操作符完成之后立即开始拉取数据。

Figure-6

图6：优化后的查询计划在达到限制时停止逐个读取数据

当图6中的查询计划执行时，它只运行图7中显示的操作符。InfluxDB有一个基于拉取的执行器（基于Apache Arrow DataFusion的执行），这意味着当ProgressiveEval开始时，它将请求第一个sort，然后它反过来请求其输入的数据。然后对数据进行排序，并将排序后的结果发送到ProgressiveEval。

Figure-7

图7：如果指定设备的最新信号在最新时间范围的文件中，则需要执行的操作符

由于有device = 10参数，查询在扫描时过滤数据，并且我们不知道哪个文件包含设备编号10的最新信号。此外，由于每个sort操作符的完成需要时间，当ProgressiveEval从流中拉取数据时，它还开始执行下一个流以预取必要的数据，如果第一个流不包含所需的设备编号10的数据。

图8显示，当从第一个Sort的Stream 1中拉取数据时，第二个Sort同时执行，以便如果Stream 1不包括设备编号10所需的数据，Stream 2中的数据就准备好了。如果设备编号10的数据在Stream 1中，ProgressiveEval一旦达到限制就停止，并取消Stream 2。如果从ProgressiveEval拉取Stream 2的数据，它也将开始预执行Stream 3的Sort，依此类推。

Figure-8

图8：如果指定设备的最新信号在最新时间范围的文件中，实际执行的操作符

分析改进的优点

让我们比较图5中的原始计划和图8中的优化计划

  1. 更快返回结果：原始计划必须扫描和排序可能包含数据的所有文件，无论所需的行数多少，然后才能产生结果。因此，时间范围越长，要读取的文件就越多，原始计划的速度就越慢。这也解释了为什么我们的结果表明对于较长的时间范围有改进。
  2. 资源更少和更高的并发性：除了更快地生成数据外，优化的计划还要求更少的内存和CPU——它通常只会扫描和排序两个文件（最新的一个和预取下一个最旧的）。这意味着可以同时使用相同的资源运行更多查询。

受益于此工作的查询类型

截至目前（2024年3月），此优化仅适用于一种查询类型，即“最新的/最旧的是哪些值……？”换句话说，查询的SQL必须包含ORDER BY time DESC/ASC LIMIT n，其中‘n’可以是任何数字，时间可以按升序或降序排列。所有其他支持的SQL查询都将正常工作，但可能无法从这种优化中受益。我们正在继续努力改进它们。

结论

此优化不仅使最新值查询更快，还降低了资源使用率并提高了系统的并发水平。一般来说，如果查询计划包括对可能不重叠的数据流的排序合并，则此优化适用。我们已发现许多此类查询计划，并正在努力改进它们。

我们想感谢Paul Dix，他根据ELK堆栈中Elastic的渐进式扫描行为提出了此设计方案。