DuckDB 中的范围连接

Richard Wesley

2022-05-27 · 23 分钟

范围交叉连接是诸如 时间序列分析等领域中的一项重要操作，并且当连接谓词中存在两个不等式条件时会发生。数据库实现通常依赖于缓慢的 O(N^2) 算法，该算法比较这些操作的每一对行。相反，DuckDB 利用其快速排序逻辑来实现针对这些类型的范围谓词的两个高度优化的并行连接运算符，从而使查询速度提高 20-30 倍。借助这些运算符，DuckDB 可以有效地用于更多面向时间序列的用例。

介绍

逐行连接表是关系模型的基本且独特的运算之一。连接使用某些布尔条件（称为谓词）水平连接两个表。这听起来很简单，但是连接的执行速度取决于谓词中的表达式。这导致了不同连接算法的创建，这些算法针对不同的谓词类型进行了优化。

在本文中，我们将解释几种连接算法及其功能。特别是，我们将描述一种新添加的“范围连接”算法，该算法使连接重叠时间间隔或多个排序条件的表变得更快。

飞行数据

不，这部分与鸭子无关，而是关于太空堡垒卡拉狄加重启版中的空军小组飞行统计信息。我们将使用几个表：Pilots、Crafts、Missions 和 Battles。当舰队分散时，一些数据丢失了，但希望这足以提供一些“真实生活”的例子！

Pilots 表包含飞行员及其不变的数据（姓名、呼号、序列号）

Crafts 表包含所有各种战斗飞行器（忽略回收部件的“忒修斯之船”问题！）

Missions 表包含飞行员执行的所有任务。任务有一个 begin 和 end 时间，并记录在飞行甲板上。我们将使用一些常见的配对（以及最后的一个不寻常的任务，指挥官阿达玛驾驶着他的旧毒蛇）

Battles 表包含每次与赛昂人战斗的时间窗口。

最后两个表（Missions 和 Battles）是状态表的示例。状态表中的对象具有在两个时间点之间运行的状态。对于战斗，状态只是是/否。对于任务，状态是飞行员/飞行器组合。

相等谓词

最常见的连接类型涉及比较一个或多个表达式对的相等性，通常是主键和外键。例如，如果我们想要一个飞行员驾驶的飞行器列表，我们可以通过 Missions 表将 Pilots 表连接到 Craft 表

SELECT callsign, count(*), tailno
FROM Pilots p, Missions m, Crafts c
WHERE p.id = m.pid
  AND c.id = m.cid
GROUP BY ALL
ORDER BY 2 DESC;

这将给我们一个像这样的表

范围谓词

在此示例中需要注意的是，连接表的条件是用 AND 连接的相等性。但是可以使用任何布尔谓词（甚至是没有相等性或 AND 的谓词）来定义关系连接。

时间数据库中的一种常见操作是交叉两个状态表。假设我们想要找到每个飞行员参与战斗的时间间隔，以便我们可以计算用于资历的战斗时间？毒蛇发射得很快，但在战斗开始之前不会发射，并且可能会出现故障，或者飞行员可能会延迟到达飞行甲板。

SELECT callsign, battle,
    greatest(m.begin, b.begin) AS begin,
    least(m.end, b.end) AS end
FROM Pilots p, Missions m, Crafts c, Battles b
WHERE m.begin < b.end
  AND b.begin < m.end
  AND p.id = m.pid
  AND c.id = m.cid;

此连接创建一组记录，其中包含每个飞行员的呼号和战斗时间段。它可以处理飞行员返回新飞行器的情况，排除巡逻飞行，甚至可以处理巡逻飞行变成战斗的情况！这是因为以这种方式交叉状态表会产生联合状态表 – 一种重要的时间数据库操作。以下是结果中的几行

阿波罗在第一次赛昂袭击发生时已经在飞行中，因此查询将他的战斗 begin 时间设置为战斗开始的时间，而不是他发射进行退役飞行的时间。星巴克和布玛在战斗开始后紧急起飞，但布玛直到战斗有效结束后才返回，因此她的 end 时间被移回到战斗的官方结束时间。

这里重要的是，飞行员/任务/飞行器关系与战斗表之间的连接条件没有任何相等性。这种连接传统上计算起来非常昂贵，但正如我们将看到的，有一些方法可以加速它。

无限时间

填充状态表的一个常见问题是如何表示开放边缘。例如，可能不知道第一个状态的开始时间，或者当前状态可能尚未结束。

通常，这些值由 NULL 表示，但这会使交叉查询复杂化，因为与 NULL 的比较会产生 NULL。可以使用 coalese(end, <large timestamp>) 来解决此问题，但这会向每行添加一个计算，其中大多数行不需要它。另一种方法是直接使用 <large timestamp> 而不是 NULL，这解决了表达式计算问题，但引入了任意时间值。在计算中使用此值时，可能会产生奇怪的结果。

DuckDB 提供了来自 Postgres 的第三种选择，可用于这些情况：无限时间值。无限时间值将按预期进行比较，但与它们的算术运算将产生 NULL 或无穷大，表明计算未明确定义。

常用连接算法

要了解为什么这些连接可能很昂贵，让我们首先看一下两种最常见的连接算法。

哈希连接

至少有一个相等条件与其余条件 ANDed 的连接称为等值连接。它们通常使用哈希表来实现，如下所示

hashes = {}
for b in build:
    hashes[b.pk] = b

result = []
for p in probe:
    result.append((p, hashes[p.fk], ))

计算一侧（构建侧）的表达式并进行哈希处理，然后查找哈希表中的另一侧（探测侧）的相应表达式并检查是否匹配。

当只有一些 ANDed 条件是相等性时，我们可以稍微修改一下，方法是在哈希表中找到相等性后检查其他条件。重要的一点是，我们可以使用哈希表使连接运行时间为 O(N)。这种修改是一种通用技术，可以与任何减少可能匹配项的连接算法一起使用。

嵌套循环连接

由于可以使用任何布尔谓词（甚至是没有相等性或 AND 的谓词）来定义关系连接，因此哈希连接并非总是有效。在这些情况下，最后的连接算法称为嵌套循环连接（或简称 NLJ），它包括仅将探测侧的每一行与构建侧的每一行进行比较

result = []
for p in probe:
    for b in build
        if compare(p, b):
            result.append((p, b, ))

这是 O(M x N) 行数，如果表很大，这可能会非常慢。更糟糕的是，大多数实际的分析查询（例如上面的战斗时间示例）都不会返回如此多的结果，因此可能会浪费大量精力。但是，如果没有针对某种谓词进行调整的算法，我们将不得不使用它。

范围连接

当我们将范围比较（<、<= >、>= 之一）作为连接条件之一时，我们可以通过对某些连接条件上的输入关系进行排序来利用它所暗示的排序。排序是 O(N log N)，这表明这可能比 NLJ 更快，而且实际上确实如此。

分段合并连接

在哈希连接出现之前，数据库通常会对连接输入进行排序以查找匹配项。对于等值连接，重复的二进制搜索然后在 O(M log N) 时间内在构建侧找到匹配的值。这称为合并连接，它的运行速度比 O(M x N) 快，但不如哈希连接的 O(N) 时间快。尽管如此，在只有一个范围比较的情况下，二进制搜索可以让我们找到探测值的第一个匹配项。然后，我们可以通过在第一个匹配项之后查找来找到所有剩余的匹配项。

如果我们也对探测侧进行排序，我们甚至可以知道从哪里开始搜索下一个探测值，因为它将在我们找到前一个值之后。这就是分段合并连接 (PWMJ) 的工作原理：我们对构建侧进行排序，以便这些值按谓词（ASC 或 DESC）排序，然后以相同的方式对每个探测块进行排序，以便我们可以快速扫描值集以查找可能的匹配项。对于这些类型的查询，这可能比 NLJ 快得多。如果存在更多连接条件，我们可以检查生成的匹配项以确保满足所有条件，因为排序再次显着减少了必须进行的检查次数。

不等式连接 (IEJoin)

对于两个范围条件（如战斗工资查询），还有更快的算法可用。我们最近添加了一个新的连接，称为 IEJoin，它对两个谓词进行排序以真正加快速度。

IEJoin 的工作方式是首先根据第一个条件的值对两个表进行排序，并将两个排序键合并到一个组合表中，该表跟踪两个输入表的行号。接下来，它根据第二个范围条件对组合表中的位置进行排序。然后，它可以快速扫描通过两个条件的匹配项。就像哈希连接一样，我们可以检查任何剩余的条件，因为我们希望已经显着减少了必须测试的对的数量。

演练

因为该算法有点棘手，所以让我们逐步完成一个小示例。（如果您正在阅读本文，这是 §4.3 中“联合数组”优化的简化版本，但我发现此版本的算法比 §3.1 中的版本更容易理解。）我们将查看本文中的 Qp，它是对表“West”的自连接

我们正在寻找第二个 id 的时间比第一个短但成本更高的计费 id 对

SELECT s1.t_id, s2.t_id AS t_id2
FROM west s1, west s2
WHERE s1.time > s2.time
  AND s1.cost < s2.cost;

有两个符合此标准的对

（这是另一种双重范围查询的示例，我们正在寻找异常。）

首先，我们根据第一个条件键 (time) 对两个输入表进行排序。（我们对 DESC 进行排序，因为我们希望这些值从左到右满足连接条件 (>)。）

因为它们以相同的方式排序，所以我们可以将来自排序表的条件键合并到一个名为 L1 的新表中，在标记每行来自哪个表之后（使用负行号表示右表）

rid 列允许我们将 L1 中的行映射回原始表。

接下来，我们构建一个带有第二个条件键 (cost) 和 L1 的行位置 (P) 的第二个表 L2（不是原始表中的行号！）我们对 L2 进行排序，依据 cost（这次再次是 DESC，因为现在我们希望连接条件从右到左保持）

L1 行位置的排序列称为置换数组，我们可以使用它来找到给定 cost 的 time 值的对应位置。

此时，我们有两个表（L1 和 L2），每个表都根据其中一个连接条件排序，并指向它所派生的表。此外，选择排序顺序是为了使条件从左到右（分别为从右到左）保持。由于条件是可传递的，这意味着无论何时我们在表中某一点有一个满足条件的值，它也满足该点右侧（分别为左侧）的所有条件！

使用此设置，我们可以从左到右扫描 L2，使用两个索引查找匹配两个条件的行

• i 从左到右在 L2 中迭代；
• off2 跟踪 i，用于识别与 i 相比满足连接条件的 costs。（请注意，对于松散的不等式，这可能位于 i 的右侧）；

我们使用位图 B 来跟踪 L2 扫描已识别为与 L2 扫描位置 i 相比满足 cost 条件的 L1 中的哪些行。

因为我们只想要一个左行和一个右行之间的匹配，所以我们可以跳过 rid 具有不同符号的匹配。为了利用这种观察，我们只处理左手表中的 i 值（rid[P[i]] 为正），并且我们只标记右手表中的行的位（rid[P[i]] 为负）。在此示例中，右侧行是 P 中的奇数编号值（它们也恰好是 i 的奇数值），这使得它们易于在示例中进行跟踪。

对于其他行，以下是发生的情况

每当我们找到与扫描位置左侧的条件 (off2 和 i 之间) 满足的 cost 时，我们使用 P[off2] 在 B 中标记与 L1 中引用右侧行的那些位置对应的位。这记录了这些行的 cost 条件已满足。然后，每当我们有一个位置 P[i] 在 L1 中，我们可以扫描 B 到右侧以找到也满足 cost 条件的值。这是因为 L1 中 P[i] 右侧的所有内容都满足 price 条件，这要归功于 L1 的排序顺序和比较运算的可传递性。

更详细地说

1. 当 i 和 off2 为 0 时，不满足 cost 条件 <，因此不会发生任何事情；
2. 当 i 为 1 时，我们正在查看连接右侧的行，因此我们跳过它并继续；
3. 当 i 为 2 时，我们现在正在查看左侧的行，因此我们将 off2 向前移动，直到 cost 条件失败，并在 P[1] = [1] 成功时标记 B；
4. 然后，我们从位置 P[i=2] = 6 向右扫描 L1 中的 time 值，并且在 B 中找不到匹配项；
5. 当 i 为 4 时，我们再次将 off2 向前移动，在 P[3] = [7] 处标记 B；
6. 然后，我们从位置 2 扫描 time，并在 [6,7] 处找到匹配项，其中一个 (6) 来自右侧表；
7. 当 i 为 6 时，我们再次将 off2 向前移动，在 P[5] = [3] 处标记 B；
8. 然后，我们从位置 4 扫描 time，并再次在 [6,7] 处找到匹配项；
9. 最后，当 i 运行结束时，我们没有新的 cost 值，因此不会发生任何事情；

使其快速的原因是我们只需要检查几个位即可找到匹配项。当我们确实需要执行比较时，我们可以使用来自我们的排序代码的快速基数比较代码，该代码不需要每个数据类型的特殊模板化版本。这不仅减少了代码大小和复杂性，而且还“面向未来”以应对新的数据类型。

更多细节

该演练是实际算法的稍微简化、单线程版本。还有一些可能感兴趣的更多细节

• 扫描大型、几乎为空的位图可能很慢，因此我们使用 §4.2 中的布隆过滤器优化。
• 已发布的算法假设任何一个表中都没有重复的 L1 值。为了处理一般情况，我们使用指数搜索来找到满足相对于当前位置的谓词的第一个 L1 值，并从该点向右扫描；
• 我们还通过连接排序代码在单独的线程上生成的排序块对来改编 §5 中的分布式算法 3。这允许我们首先使用并行排序，然后将连接分解为独立的部分来完全并行化运算符；
• 为并行执行分解部分还允许我们将未被处理的连接块假脱机到磁盘，从而使连接可扩展。

特殊连接

IEJoin 的优点之一是它非常通用，并且可以合理有效地实现许多更专业的连接类型。例如，上面的状态交叉查询是间隔连接的一个示例，我们正在寻找在两个间隔的交集上进行连接。

可以使用 IEJoin 加速的另一个专用连接是频带连接。这可用于连接彼此“接近”的值

SELECT r.id, s.id
FROM r, s
WHERE r.value - s.value BETWEEN a AND b;

这转化为双重不等式连接条件

SELECT r.id, s.id
FROM r, s
WHERE s.value + a <= r.value AND r.value <= s.value + b;

这正是 IEJoin 处理的连接表达式类型。

性能

那么 IEJoin 有多快？它非常快，以至于很难将其与以前的范围连接算法进行比较，因为改进如此之大以至于其他算法无法在合理的时间内完成！

简单测量

为了给出一个例子，这里有一些员工税务和工资数据的 10 万个自连接的运行时间，目标是找到一个人的工资较高但另一个人的税率较高的 1001 对员工

SELECT
    r.id,
    s.id
FROM Employees r
JOIN Employees s
    ON r.salary < s.salary
    AND r.tax > s.tax;

另一个例子是自连接以在 3 万个事件表中查找 3772 个重叠事件

SELECT
    r.id,
    s.id
FROM events r
JOIN events s
    ON r.start <= s.end
    AND r.end >= s.start
    AND r.id <> s.id;

在这两种情况下，我们都看到了 20-100 倍的性能提升，当您运行大量此类查询时，这非常有帮助！

优化测量

第三个示例演示了连接对过滤和指数搜索优化的重要性。这些数据是来自另一个 间隔连接论文的 图书馆流通数据的状态表，并且该查询是用于生成图 4d 的周期内时间点查询

SELECT x, count(*) AS y
FROM books,
    (SELECT x FROM range('2013-01-01'::TIMESTAMP, '2014-01-01'::TIMESTAMP, INTERVAL 1 DAY) tbl(x)) dates
WHERE checkout <= x AND x <= return
GROUP BY ALL
ORDER BY 1;

结果是每天午夜签出的书籍数量的计数。这些是在 18 核 iMac Pro 上的运行时间

该查询将一个 3500 万行的表与一个 365 行的表连接起来，因此大部分数据来自左侧。通过避免为左侧的匹配行设置位，我们几乎消除了所有 L1 检查。这大大减少了运行时间并提高了 CPU 利用率。

这些数据还有大量对应于年初签出的书籍的行，所有这些行都具有相同的 checkout 日期。在第一个块中线性地向左搜索以找到扫描的第一个匹配项导致重复运行约 12 万次比较。这导致运行时间完全由处理第一个块主导。通过将这些行的比较次数从平均约 6 万次减少到 16 次，运行时间下降了 10 倍，并且 CPU 利用率翻了一番。

结论与反馈

在这篇博文中，我们解释了新的 IEJoin 运算符提供的新 DuckDB 范围连接改进。这应大大提高状态表连接和异常检测连接的响应时间。我们希望这使您的 DuckDB 体验更好 – 如果您遇到任何问题，请告诉我们！请随时访问我们的 GitHub 页面或我们的 Discord 服务器。