PostGIS霸主地位不保! DuckDB SPATIAL 400倍性能傲视群雄
digoal约 22 分钟继图、向量、湖仓领域/赛道之后, 又一个领域/赛道被DuckDB拿下了, 那就是GIS.
图、向量、湖仓领域请看回顾文章:
这个赛道没戏了｜DuckDB 正式发布PGQ，附详细使用说明
DuckDB出手，图数据库赛道将不复存在
让ETL工程师失业的论文 | DuckDB深度集成 LLMs
DuckDB进军DB4AI｜“语义(向量)搜索、全文检索、BM25、模糊检索”一网打尽
DuckDB 暴露野心，日后与PG必有一战
智能BI基座三件套 | LLM + DuckDB + ECharts
DuckDB朝云边一体演进，商业逻辑显现
PostGIS霸主地位不保! DuckDB SPATIAL傲视群雄
提起GIS应用, 数据库没有第二选项, 只能选PostgreSQL+PostGIS插件. (当然如果你使用商业数据库, PolarDB Ganos比PostGIS更胜一筹.) 有兴趣可以关注它家公众号, 但是今天这篇的重点当然不是ganos.
正式开始前，插一句，我找GIS专家用本文同样的数据集测过PostGIS了（含空间索引），结果拿不出手。
自从DuckDB推出spatial插件以来, 经过不断优化, PostGIS霸主地位正在被撼动, 我们先拿GIS应用里最为常见的空间分析为例.
多边形 join 多边形/轨迹/点 通常出现在空间统计分析中, 例如 想找出人流量大的热门街区、出租车早上最热门的起点和终点 ...
这些都需要大量轨迹数据 JOIN 大量行政区块(甚至细到小区/写字楼), PostGIS里只能使用nestloop join来完成此操作, 非常非常耗时.
DuckDB spatial扩展插件类似JOIN操作是如何做到400倍性能提升的?
核心是DuckDB提供了一个新的JOIN算子: SPATIAL_JOIN
除了常见的hash join , merge join , nestloop join. SPATIAL_JOIN 是什么鬼? 如何实现了空间运算的并行HASH JOIN类似效果.
别急, 往下看, 以下内容翻译自:
https://duckdb.org/2025/08/08/spatial-joins.html
PS: 从功能角度看, DuckDB spatial插件还需要追赶PostGIS. 但是, 别忘了它是Duck, 持续关注吧
DuckDB 中的 SPATIAL_JOIN 算子
TL;DR：DuckDB v1.3.0+ 通过SPATIAL_JOIN专用运算符显著提高了地理空间连接(join)的可扩展性、性能。高达400倍提升.
介绍
空间连接是基于列（或列）之间（地理）空间关系来匹配行的连接操作。在实践中，它们常用于回答诸如“这些点中的哪些位于哪个多边形内？”之类的问题。能够根据数据集所建模的物理位置来连接数据集，是整个地理空间数据科学领域的基础，但从更高层次来看，它也是关联和丰富原本分散的数据源、将洞察锚定在现实世界中，以及通常情况下通过分析讲述精彩故事的一种极其强大的方法。
DuckDB 的spatial扩展插件自诞生之日起就提供了一种GEOMETRY列类型来表示位置、区域和形状，以及丰富的空间谓词函数供JOIN连接时使用。然而，直到最近在DuckDB v1.3.0中，由于引入了SPATIAL_JOIN专用查询运算符，空间连接才真正变得可扩展(指JOIN算子可扩展、性能大幅度提升, 例如JOIN时动态构建rtree索引结构提升性能)。
DuckDB 在v1.3.0 发行说明的末尾匆匆地透露了一些关于这个新运算符的信息，但我们认为内容已经足够详尽，值得另写一篇博文。因此，在本文中，我们将深入探讨优化空间连接所面临的一些挑战，以及这个新SPATIAL_JOIN运算符如何应对这些挑战，从而实现更高的效率。
空间连接又是什么样的？
在 SQL 中执行空间连接实际上非常简单。不需要特殊的语法或魔法咒语。正如你可能已经猜到的那样，你只需要使用一些空间谓词将两个表的GEOMETRY列JOIN连接起来即可。下面是一个简单的示例，它使用ST_Intersects空间谓词函数连接some_table和another_table两个表，条件是 some_table.geom 和 another_table.geom 中的几何形状使用“相交”连接 ：
SELECT *
FROM some_table
JOIN another_table
ON ST_Intersects(some_table.geom, another_table.geom);
让我们尝试做一些更高级的事情。我们将分析纽约市花旗自行车行程数据集，该数据集包含大约 5800 万行代表纽约市租赁自行车行程的数据，包括每次行程的起点和终点。我们希望找到纽约市内自行车行程最多的街区。因此，我们将自行车行程数据与纽约市街区多边形数据集连接起来。然后，我们计算并分组从每个街区开始的行程次数，最后对结果进行排序和limit，以返回行程最多的前 3 个街区。我们已经编译了数据集并将此示例的相关列提取到两个表中，rides和hoods，放入一个218 MB 的 DuckDB 数据库文件。
让我们确保spatial扩展插件已安装并加载：
INSTALL spatial; -- Install the spatial extension
LOAD spatial; -- Load the spatial extension
我们的查询如下所示：
SELECT neighborhood, count(*) AS num_rides
FROM rides
JOIN hoods ON ST_Intersects(rides.start_geom, hoods.geom)
GROUP BY neighborhood
ORDER BY num_rides DESC
LIMIT 3;
┌──────────────┬───────────┐
│ neighborhood │ num_rides │
│ varchar │ int64 │
├──────────────┼───────────┤
│ Midtown │ 6253835 │
│ Chelsea │ 6238693 │
│ East Village │ 4047396 │
└──────────────┴───────────┘
该查询将 58,033,724 个骑行路线与 310 个邻域多边形连接起来，在我的笔记本电脑（配备 M3 Pro CPU 和 36 GB RAM 的 MacBook）上运行大约需要30 秒。
虽然乍一看 30 秒似乎并不令人印象深刻（HASH_JOIN类似大小的输入会快一个数量级），但实际上我很高兴 DuckDB 能够在如此短的时间内执行如此规模的空间连接，即使不是很棒，对于探索性分析来说仍然可接受（在笔记本电脑上也一样！）。为了理解spatial JOIN与例如HASH_JOIN相比执行时间的差异，我们首先需要仔细研究 DuckDB 过去是如何进行空间连接的，以及为什么空间连接如此难以优化。然后，我们将深入探讨新的SPATIAL_JOIN运算符如何改变游戏规则。
DuckDB 如何进行空间连接
空间谓词
首先要理解的是，空间谓词实际上只是一个函数，它计算a、b两个geometry之间的某种空间关系，并返回true或false，例如“a 包含 b” 或 “b 离 a 在距离 x 以内”。理论上，你可以编写自己的空间谓词函数，但实际上，你可能会使用spatial扩展插件附带的众多函数之一。不同空间谓词之间的细微差别超出了本文的讨论范围，但这里简要概述了最常用的几个谓词，它们分别采用两个geometrya和b：
ST_Intersects(a, b) | |
ST_Contains(a, b) | |
ST_ContainsProperly(a, b) | |
ST_Within(a, b) | |
ST_Overlaps(a, b) | |
ST_Touches(a, b) | |
ST_Equals(a, b) | |
ST_Crosses(a, b) | |
ST_Covers(a, b) | |
ST_CoveredBy(a, b) | |
ST_DWithin(a, b, x) |
更多ST函数可参考: https://duckdb.org/docs/stable/core_extensions/spatial/functions#function-index
我们在上面的示例查询中使用
ST_Intersects来保持其简单，即使ST_Contains或ST_ContainsProperly可能更适合点与多边形的连接。
由于上述所有空间谓词都存在于spatial扩展插件中，DuckDB 的查询规划器实际上对它们一无所知，除了它们的名称以及它们是接受两个GEOMETRY参数并返回布尔值的函数之外。这意味着原生 DuckDB 本身无法对它们应用任何特殊优化，而必须像对待数据库中的其他函数一样对待它们。
优化挑战
当 DuckDB 规划一个连接操作，其中连接条件是任意函数时，它通常无法使用任何高级内置连接策略，例如HASH_JOIN或RANGE_JOIN (merge join) ，这些策略针对相等性或范围比较进行了优化。相反，DuckDB 必须回退到最简单的连接策略，即执行嵌套循环连接(NLJ / nestloop join)，即对两个表中所有可能的行都评估连接条件(运算次数达到笛卡尔乘积数)。用伪代码来表示，嵌套循环连接如下所示：
for row_a in table_a:
for row_b in table_b:
if join_condition(row_a, row_b):
emit(row_a, row_b)
这是实现连接最常用的方法，但效率也是最低的。由于连接的复杂度为O(n*m)，其中n和m分别是两个表中的行数，因此执行连接所需的时间会随着输入的大小呈二次方增长。
复杂性挑战
显然，二次方复杂度对于大型连接来说很快就会变得不可行，但 DuckDB 的原始执行能力通常使其在连接中小型表时可以忍受。
然而，嵌套循环连接策略对于空间连接尤其不切实际，即使在中小规模的情况下也是如此，因为首先评估空间谓词的计算成本就非常高昂。这主要是由于所涉及算法的复杂性，也是由于几何的非规范化性质，其中单个几何类型就可以包含大量点。此外，除了固有的理论复杂性之外，实际情况是，借助第三方库实现的大多数空间谓词都需要反序列化步骤，将GEOMETRY列的内部二进制格式转换为可执行的数据结构。这通常还需要在 DuckDB 自身的内存管理系统之外分配内存，这会增加全局内存分配器的压力和锁争用，从而限制额外并行性的有效性。
为了说明这在实践中是如何实现的，让我们看一下上面示例查询的查询计划，但禁用SPATIAL_JOIN优化以强制 DuckDB 使用嵌套循环连接：
实验
LOAD spatial; -- Load the spatial extension
-- Disable the spatial join optimizer
SET disabled_optimizers = 'extension';
-- Print the new plan, using EXPLAIN to verify
-- that we are using a nested loop join
EXPLAIN SELECT neighborhood, count(*) AS num_rides
FROM rides
JOIN hoods ON ST_Intersects(rides.start_geom, hoods.geom)
GROUP BY neighborhood
ORDER BY num_rides DESC
LIMIT 3;
EXPLAIN 的结果
┌───────────────────────────┐
│ TOP_N │
│ Top: 3 │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ HASH_GROUP_BY │
│ ... │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ PROJECTION │
│ ... │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ BLOCKWISE_NL_JOIN │
│ ──────────────────── │
│ Join Type: INNER │
│ ├──────────────┐
│ Condition: │ │
│ ST_Intersects(start_geom, │ │
│ geom) │ │
└─────────────┬─────────────┘ │
┌─────────────┴─────────────┐┌─────────────┴─────────────┐
│ SEQ_SCAN ││ SEQ_SCAN │
│ ──────────────────── ││ ──────────────────── │
│ Table: rides ││ Table: hoods │
│ ... ││ ... │
│ ~58033724 Rows ││ ~310 Rows │
└───────────────────────────┘└───────────────────────────┘
现在，在我的笔记本电脑上执行这个使用BLOCKWISE_NL_JOIN逐块嵌套循环连接的查询需要30 分钟。我还使用rides表中行数的子集(100万和1000万)运行了该查询，以查看性能如何随输入大小的变化。结果如下：
这显然不太好。运行完整数据集的 1/58 已经比启用空间连接优化(SPATIAL_JOIN优化)的原始查询花费了更长的时间。而处理完整数据集则需要将近半个小时！这清楚地表明嵌套循环连接策略不适合大规模空间连接(spatial 类型的join运算)，我们确实需要采取措施。
IE-Join (inequality join) 优化
为了改善这种情况，spatial扩展插件早期版本中实现的首批优化之一是重写查询计划器的规则。
由于评估空间谓词函数本身的开销非常高，因此最好先尝试对潜在的连接匹配进行一些低成本的过滤，以减少实际需要进行精确空间关系检查的对的数量。幸运的是，对于大多数空间谓词来说，这样做相对容易，因为它们都具有一个共同的属性。几乎所有空间谓词都以某种方式暗示相交，并且如果两个geometry相交，它们的边界框也必须相交。
geometry的边界框，有时也称为最小边界矩形(MBR minimum bounding rectangle)，是完全包含该geometry的最小矩形。由于边界框表示geometry中所有点x、y 坐标的最小值和最大值，因此只需一次扫描即可相对高效地计算。此外，检查两个边界框是否相交也非常高效，只需几个简单的小于和大于比较操作即可在常数时间内完成。
由于边界框相交可以表示为一系列不等式检查，我们可以利用 DuckDB 现有的不等式连接功能来执行边界框连接！解释不等式连接的内部工作原理超出了本文的范围，因为 Richard 在他的关于范围连接的博客文章中已经对此做了很好的阐述。但其要点是，它是一种可以使用一系列不等式运算符（例如<、>、<=、>=等）高效地连接两个表的连接类型。
为了利用这一点，我们对spatial扩展插件做了以下更改：
在GEOMETRY列的 序列化二进制表示中，为每个几何图形缓存一个近似边界框(预先计算MBR)，这样我们就不必在每次需要评估空间谓词时重新计算它。引入重写规则(query rewrite)，将任何带有空间谓词的内部嵌套循环连接运算符(inner join)更改为两个新运算符： PIECEWISE_MERGE_JOIN，一个“IE”（不等）范围连接运算符，用于连接边界框的交集，写成关于边界框最小值/最大值的一系列BETWEEN子句FILTER，根据实际的空间谓词函数来过滤结果行的运算符。
为了展示这如何影响查询计划，我们将使用 DuckDB 旧版本 v1.2.0（它包含PIECEWISE_MERGE_JOIN优化，但不包含SPATIAL_JOIN算子）重新运行上面的查询。
LOAD spatial; -- Load the spatial extension
-- Check that we are using DuckDB v1.2.0
PRAGMA version;
┌─────────────────┬────────────┐
│ library_version │ source_id │
│ varchar │ varchar │
├─────────────────┼────────────┤
│ v1.2.0 │ 5f5512b827 │
└─────────────────┴────────────┘
-- Print the new query plan, using EXPLAIN
EXPLAIN SELECT neighborhood, count(*) AS num_rides
FROM rides
JOIN hoods ON ST_Intersects(rides.start_geom, hoods.geom)
GROUP BY neighborhood
ORDER BY num_rides DESC
LIMIT 3;
EXPLAIN 的结果
┌───────────────────────────┐
│ TOP_N │
│ ──────────────────── │
│ Top: 3 │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ HASH_GROUP_BY │
│ ──────────────────── │
│ ... │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ PROJECTION │
│ ... │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ FILTER │
│ ──────────────────── │
│ ST_Intersects(start_geom, │ -- Here we evaluate the actual
│ geom) │ -- precise spatial predicate
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ PIECEWISE_MERGE_JOIN │
│ ──────────────────── │
│ Join Type: INNER │
│ │
│ Conditions: │
│ ST_XMin(ST_Extent_Approx │ -- Very complex join condition,
│ (start_geom)) <= ST_XMax │ -- but its all just inequality checks!
│ (ST_Extent_Approx(geom)) │
│ ST_XMax(ST_Extent_Approx │
│ (start_geom)) >= ST_XMin ├──────────────┐
│ (ST_Extent_Approx(geom)) │ │
│ ST_YMin(ST_Extent_Approx │ │
│ (start_geom)) <= ST_YMax │ │
│ (ST_Extent_Approx(geom)) │ │
│ ST_YMax(ST_Extent_Approx │ │
│ (start_geom)) >= ST_YMin │ │
│ (ST_Extent_Approx(geom)) │ │
│ │ │
│ ~58033724 Rows │ │
└─────────────┬─────────────┘ │
┌─────────────┴─────────────┐┌─────────────┴─────────────┐
│ SEQ_SCAN ││ SEQ_SCAN │
│ ──────────────────── ││ ──────────────────── │
│ ... ││ ... │
│ ~58033724 Rows ││ ~310 Rows │
└───────────────────────────┘└───────────────────────────┘
如您所见，PIECEWISE_MERGE_JOIN运算符已替换掉BLOCKWISE_NL_JOIN运算符，并且连接条件已被重写(query rewrite)为使用几何类型的近似边界框（ST_Extent_Approx），而不是直接在空间谓词上进行连接。FILTER运算符被添加到顶部，以便仅对通过初始边界框检查的行应用空间谓词函数。
这看起来比原始的嵌套循环连接复杂得多，那么它的性能如何？
我们成功地将完整数据集的执行时间从 30 分钟缩短到了不到 2 分钟！这是一个巨大的进步。无需任何自定义操作符(operator)代码，我们都能够利用 DuckDB 现有的不等式连接功能来显著加快空间连接的速度。
然而，这种方法仍然存在一些缺点：
此重写仅适用于 INNER连接。我们现在必须在每个geometry的二进制表示中存储 边界框，这会增加GEOMETRY列的内存占用，并且每次创建或修改GEOMETRY列时我们还必须重新计算它。PIECEWISE_MERGE_JOIN操作符(operator)必须对两个输入表进行排序，这需要大量内存，并且对于大表来说，一旦数据在内存中放不下时，速度会非常慢。
虽然DuckDB 此后版本对排序进行了大幅优化，spatial插件及其函数也进行了多项优化，略微提升了性能。尽管如此，这始终只是权宜之计，至少是为了使空间连接在常见情况下可用。我们该如何做得更好呢？
空间连接运算符
R树索引
快速回顾一下Rtree的工作原理：它是一种平衡树数据结构，其中内部节点包含覆盖其子节点边界框的边界框，叶节点包含geometry的边界框以及指向其对应表行的指针。这样，只需从上向下遍历树，并沿着与搜索框相交的分支，即可快速查找与给定边界框相交的所有geometry。
去年在spatial扩展插件中实现RTREE索引的动机之一是希望最终能够用基于索引的连接策略取代PIECEWISE_MERGE_JOIN优化。然而，在RTREE实现之后，我们意识到在现有数据之上创建基于 R 树的索引实际上速度惊人。与其要求用户为了加速空间连接而总是将数据加载到表中然后对其进行索引，不如在执行连接时动态创建一个临时的 R 树索引，效果如何？这有点像我们在执行HASH_JOIN时创建临时哈希表一样。
使用 R 树进行JOIN
这正是新SPATIAL_JOIN运算符的作用。它接收两个输入表，缓冲“右”表（即连接顺序优化器预期较小的表）的所有输入，在收集到的右表输入之上构建 R 树索引，然后通过在 R 树索引中查找“左”表的每一行来执行连接。其思路与 HASH_JOIN 完全相同，但我们不使用哈希表，而是使用 R 树 作为加速数据结构来查找匹配的行。
虽然与基于PIECEWISE_MERGE_JOIN的方法相比实现起来要复杂得多，但它有几个优点：
查询重写规则要简单得多，我们只需检测带有空间谓词的嵌套循环连接并将其替换为 SPATIAL_JOIN运算符即可。无需对查询计划进行任何其他修改。只需将较小的侧输入 物化并排序以构建R 树。左侧输入可以并行传输，找到匹配的tuple后即可立即发送。R 树的层次结构使我们能够更准确地修剪右侧输入 由于所有逻辑都在一个运算符中，我们不需要依赖单独的 FILTER运算符，因此可以支持LEFT、RIGHT和FULL OUTER连接以及INNER连接。
实验
为了展示这个计划的样子，这是在启用了SPATIAL_JOIN运算符的 DuckDB v1.3.0 或更高版本上运行相同查询时得到的结果：
LOAD spatial; -- Load the spatial extension
-- Print the new query plan, using EXPLAIN
EXPLAIN SELECT neighborhood, count(*) AS num_rides
FROM rides
JOIN hoods ON ST_Intersects(rides.start_geom, hoods.geom)
GROUP BY neighborhood
ORDER BY num_rides DESC
LIMIT 3;
EXPLAIN 的结果
┌───────────────────────────┐
│ TOP_N │
│ ──────────────────── │
│ Top: 3 │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ HASH_GROUP_BY │
│ ──────────────────── │
│ ... │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ PROJECTION │
│ ──────────────────── │
│ ... │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ SPATIAL_JOIN │
│ ──────────────────── │
│ Join Type: INNER │
│ │
│ Conditions: ├──────────────┐
│ ST_Intersects(start_geom, │ │
│ geom) │ │
│ │ │
│ ~58033724 Rows │ │
└─────────────┬─────────────┘ │
┌─────────────┴─────────────┐┌─────────────┴─────────────┐
│ SEQ_SCAN ││ SEQ_SCAN │
│ ──────────────────── ││ ──────────────────── │
│ ... ││ ... │
│ ~58033724 Rows ││ ~310 Rows │
└───────────────────────────┘└───────────────────────────┘
很好，我们又回到了单个连接条件。那么它的性能如何呢？我们已经在第一个示例中看到，DuckDB v1.3.2 使用该SPATIAL_JOIN运算符能够在大约 30 秒内执行原始查询，以下是所有不同大小和连接策略的精确结果，以供比较。所有查询均在同一台 Apple MacBook M3 Pro（36 GB 内存）上运行，并计算了 3 次运行的平均时间：
该SPATIAL_JOIN运算符执行完整的 5800 万行数据集的速度，比原始的嵌套循环连接执行 100 万行数据集的速度还要快。 58 倍的提升！
局限性和未来工作
尽管我们已经做出了很多改进，但 DuckDB 中的空间连接功能目前还不够完善。和往常一样，还有很多工作要做，并且我们有一些关于如何进一步改进SPATIAL_JOIN运算符的想法。
大于内存的构建面(即右表)
SPATIAL_JOIN运算符当前实现会将右侧的整个输入缓存在内存中，以构建 R 树索引。这意味着它只能处理内存可容纳的右侧输入。我们计划添加对大于内存的 R 树的支持，方法是将右侧划分为较小的独立 R 树，然后合并每个分区的连接结果，类似于HASH_JOIN运算符处理大于内存的哈希表的方式。 (划分多个hash table, 妙啊!!!)
提高并行性
DuckDB 的执行引擎会根据扫描的行数动态调整查询中使用的线程数，但由于空间谓词的评估成本非常高，我们可能会从更高的并行度中受益，因为空间连接通常受 CPU 限制。具体来说，我们正在考虑对连接的左侧进行缓冲和分区，这将使我们能够在运算符中生成自己的工作任务，以跨多个与输入基数分离的线程来评估连接条件。这会增加内存使用量并阻止连接流式传输，但我们已经在vss扩展插件中构建HNSW（分层可导航小世界）索引时能够采用类似的技术，并取得了良好的效果。
更快的谓词函数
spatial扩展插件中的大多数谓词函数都是使用第三方库实现的，这会带来一些开销，因为我们无法将它们与 DuckDB 的执行引擎和内存管理紧密集成，通常需要某种反序列化或转换步骤。这可能会非常昂贵，尤其是对于大型geometry类型而言。为了在实践中展示这一点的影响，我们可以比较ST_Intersects(x, y)和功能等效的ST_DWithin(x, y, 0)的JOIN性能，方法是将之前的结果与以下查询的时间进行比较：
SELECT neighborhood, count(*) AS num_rides
FROM rides
JOIN hoods ON ST_DWithin(rides.start_geom, hoods.geom, 0)
GROUP BY neighborhood
ORDER BY num_rides DESC
LIMIT 3;
尽管从技术层面来看，ST_DWithin还需要做更多工作，但其在spatial扩展插件中的实现最近已更改为我们自主研发的高度优化的原生实现，从而避免了额外的内存分配和复制。这清晰地展现了优化空间谓词函数本身如何显著提升空间连接的性能。我们正在积极地将其余常用空间谓词（例如ST_Intersects、ST_Contains、ST_Within等）的优化版本添加到spatial扩展插件中，并期望在各个方面都能实现类似的性能提升。
所以使用dwithin在58倍基础上又提升了7倍, 这就是406倍啊!!!
高级连接条件
SPATIAL_JOIN运算符目前仅支持连接条件为单个空间谓词函数的情况。我们计划添加对更复杂的连接条件的支持，这些连接条件可以包含比较、算术运算以及其他与空间谓词结合的函数。这将允许用户在连接中表达更复杂的空间关系，例如。JOIN ... ON ST_Intersects(a.geom, b.geom) AND a.id = b.id
ANTI/SEMI 加入
SPATIAL_JOIN运算符目前仅支持INNER、LEFT和RIGHT、FULL OUTER连接。我们计划在未来添加对ANTI和SEMI JOIN的支持。
结论
空间连接是一种基于地理空间关系连接和丰富数据集的有效方法。DuckDB 的spatial扩展插件提供了丰富的空间谓词函数，可用于在 SQL 中执行空间连接。虽然过去由于空间谓词的复杂性和连接策略的局限性，空间连接的性能一直难以应对，但DuckDB v1.3.0 中引入的新运算符SPATIAL_JOIN 显著提高了这些工作负载的效率和可扩展性，使空间连接成为 DuckDB 执行引擎中的一等公民。
在本地Mac中试一试上文的例子
我的环境是mac book pro m2芯片, 和作者文中说的性能差不多.
下载数据
curl https://blobs.duckdb.org/data/biketrips.duckdb -o ./biketrips.duckdb
启动duckdb
$ duckdb ./biketrips.duckdb
DuckDB v1.3.2 (Ossivalis) 0b83e5d2f6
Enter ".help"for usage hints.
安装插件, 查看数据文件中的表、结构、记录条数
D install spatial;
100% ▕████████████████████████████████████████████████████████████▏
D load spatial;
D show tables;
┌─────────┐
│ name │
│ varchar │
├─────────┤
│ hoods │
│ rides │
└─────────┘
D desc rides;
┌─────────────┬─────────────┬─────────┬─────────┬─────────┬─────────┐
│ column_name │ column_type │ null │ key │ default │ extra │
│ varchar │ varchar │ varchar │ varchar │ varchar │ varchar │
├─────────────┼─────────────┼─────────┼─────────┼─────────┼─────────┤
│ bikeid │ BIGINT │ YES │ NULL │ NULL │ NULL │
│ start_geom │ GEOMETRY │ YES │ NULL │ NULL │ NULL │
└─────────────┴─────────────┴─────────┴─────────┴─────────┴─────────┘
D desc hoods;
┌──────────────┬─────────────┬─────────┬─────────┬─────────┬─────────┐
│ column_name │ column_type │ null │ key │ default │ extra │
│ varchar │ varchar │ varchar │ varchar │ varchar │ varchar │
├──────────────┼─────────────┼─────────┼─────────┼─────────┼─────────┤
│ neighborhood │ VARCHAR │ YES │ NULL │ NULL │ NULL │
│ geom │ GEOMETRY │ YES │ NULL │ NULL │ NULL │
└──────────────┴─────────────┴─────────┴─────────┴─────────┴─────────┘
D select * from pg_indexes;
┌────────────┬───────────┬───────────┬────────────┬──────────┐
│ schemaname │ tablename │ indexname │ tablespace │ indexdef │
│ varchar │ varchar │ varchar │ int32 │ varchar │
├────────────┴───────────┴───────────┴────────────┴──────────┤
│ 0 rows │
└────────────────────────────────────────────────────────────┘
D select count(*) from hoods;
┌──────────────┐
│ count_star() │
│ int64 │
├──────────────┤
│ 310 │
└──────────────┘
D select count(*) from rides;
┌─────────────────┐
│ count_star() │
│ int64 │
├─────────────────┤
│ 58033724 │
│ (58.03 million) │
└─────────────────┘
空间JOIN查询
D .timer on
D explain SELECT neighborhood, count(*) AS num_rides
FROM rides
JOIN hoods ON ST_Intersects(rides.start_geom, hoods.geom)
GROUP BY neighborhood
ORDER BY num_rides DESC
LIMIT 3;
┌─────────────────────────────┐
│┌───────────────────────────┐│
││ Physical Plan ││
│└───────────────────────────┘│
└─────────────────────────────┘
┌───────────────────────────┐
│ TOP_N │
│ ──────────────────── │
│ Top: 3 │
│ │
│ Order By: │
│ count_star() DESC │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ HASH_GROUP_BY │
│ ──────────────────── │
│ Groups: #0 │
│ │
│ Aggregates: │
│ count_star() │
│ │
│ ~294 Rows │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ PROJECTION │
│ ──────────────────── │
│ neighborhood │
│ │
│ ~58033724 Rows │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ SPATIAL_JOIN │
│ ──────────────────── │
│ Join Type: INNER │
│ │
│ Conditions: ├──────────────┐
│ ST_Intersects(start_geom, │ │
│ geom) │ │
│ │ │
│ ~58033724 Rows │ │
└─────────────┬─────────────┘ │
┌─────────────┴─────────────┐┌─────────────┴─────────────┐
│ SEQ_SCAN ││ SEQ_SCAN │
│ ──────────────────── ││ ──────────────────── │
│ Table: rides ││ Table: hoods │
│ Type: Sequential Scan ││ Type: Sequential Scan │
│ ││ │
│ Projections: ││ Projections: │
│ start_geom ││ geom │
│ ││ neighborhood │
│ ││ │
│ ~58033724 Rows ││ ~310 Rows │
└───────────────────────────┘└───────────────────────────┘
Run Time (s): real 0.003 user 0.001973 sys 0.001212
D SELECT neighborhood, count(*) AS num_rides
FROM rides
JOIN hoods ON ST_Intersects(rides.start_geom, hoods.geom)
GROUP BY neighborhood
ORDER BY num_rides DESC
LIMIT 3;
100% ▕████████████████████████████████████████████████████████████▏
┌──────────────┬───────────┐
│ neighborhood │ num_rides │
│ varchar │ int64 │
├──────────────┼───────────┤
│ Midtown │ 6253835 │
│ Chelsea │ 6238693 │
│ East Village │ 4047396 │
└──────────────┴───────────┘
Run Time (s): real 30.466 user 230.098026 sys 0.773706
D SELECT neighborhood, count(*) AS num_rides
FROM rides
JOIN hoods ON ST_DWithin(rides.start_geom, hoods.geom, 0)
GROUP BY neighborhood
ORDER BY num_rides DESC
LIMIT 3;
100% ▕████████████████████████████████████████████████████████████▏
┌──────────────┬───────────┐
│ neighborhood │ num_rides │
│ varchar │ int64 │
├──────────────┼───────────┤
│ Midtown │ 6253835 │
│ Chelsea │ 6238693 │
│ East Village │ 4047396 │
└──────────────┴───────────┘
Run Time (s): real 7.714 user 57.342933 sys 0.205164
加索引后, 性能没有变化, 因为spatial_join算子是动态物化右表并构建rtree索引, 而且右表才300多条记录, 所以不会有性能变化.
所以加不加索引都无所谓, 因为spatial_join时会自动动态构建rtree索引.
而且如果右表很大, 未来spatial_join算子有个优化方法: 可能会和类似hash join多个hash bucket一样进行优化, 无法使用表上已有的rtree索引.
D create index idx1 on rides using rtree (start_geom);
Run Time (s): real 0.000 user 0.000140 sys 0.000051
D create index idx2 on hoods using rtree (geom);
Run Time (s): real 8.796 user 17.761472 sys 11.309780
D SELECT neighborhood, count(*) AS num_rides
FROM rides
JOIN hoods ON ST_Intersects(rides.start_geom, hoods.geom)
GROUP BY neighborhood
ORDER BY num_rides DESC
LIMIT 3;
100% ▕████████████████████████████████████████████████████████████▏
┌──────────────┬───────────┐
│ neighborhood │ num_rides │
│ varchar │ int64 │
├──────────────┼───────────┤
│ Midtown │ 6253835 │
│ Chelsea │ 6238693 │
│ East Village │ 4047396 │
└──────────────┴───────────┘
Run Time (s): real 28.112 user 210.793171 sys 0.788443
D SELECT neighborhood, count(*) AS num_rides
FROM rides
JOIN hoods ON ST_DWithin(rides.start_geom, hoods.geom, 0)
GROUP BY neighborhood
ORDER BY num_rides DESC
LIMIT 3;
100% ▕████████████████████████████████████████████████████████████▏
┌──────────────┬───────────┐
│ neighborhood │ num_rides │
│ varchar │ int64 │
├──────────────┼───────────┤
│ Midtown │ 6253835 │
│ Chelsea │ 6238693 │
│ East Village │ 4047396 │
└──────────────┴───────────┘
Run Time (s): real 8.324 user 56.901637 sys 0.356781
D explain SELECT neighborhood, count(*) AS num_rides
FROM rides
JOIN hoods ON ST_Intersects(rides.start_geom, hoods.geom)
GROUP BY neighborhood
ORDER BY num_rides DESC
LIMIT 3;
┌─────────────────────────────┐
│┌───────────────────────────┐│
││ Physical Plan ││
│└───────────────────────────┘│
└─────────────────────────────┘
┌───────────────────────────┐
│ TOP_N │
│ ──────────────────── │
│ Top: 3 │
│ │
│ Order By: │
│ count_star() DESC │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ HASH_GROUP_BY │
│ ──────────────────── │
│ Groups: #0 │
│ │
│ Aggregates: │
│ count_star() │
│ │
│ ~294 Rows │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ PROJECTION │
│ ──────────────────── │
│ neighborhood │
│ │
│ ~58033724 Rows │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ SPATIAL_JOIN │
│ ──────────────────── │
│ Join Type: INNER │
│ │
│ Conditions: ├──────────────┐
│ ST_Intersects(start_geom, │ │
│ geom) │ │
│ │ │
│ ~58033724 Rows │ │
└─────────────┬─────────────┘ │
┌─────────────┴─────────────┐┌─────────────┴─────────────┐
│ SEQ_SCAN ││ SEQ_SCAN │
│ ──────────────────── ││ ──────────────────── │
│ Table: rides ││ Table: hoods │
│ Type: Sequential Scan ││ Type: Sequential Scan │
│ ││ │
│ Projections: ││ Projections: │
│ start_geom ││ geom │
│ ││ neighborhood │
│ ││ │
│ ~58033724 Rows ││ ~310 Rows │
└───────────────────────────┘└───────────────────────────┘
Run Time (s): real 0.002 user 0.001979 sys 0.000221
验证前面的想法, 删除rtree索引后, 性能无变化.
D drop index idx1;
Run Time (s): real 0.010 user 0.003936 sys 0.006691
D drop index idx2;
Run Time (s): real 0.001 user 0.000806 sys 0.000179
D SELECT neighborhood, count(*) AS num_rides
FROM rides
JOIN hoods ON ST_Intersects(rides.start_geom, hoods.geom)
GROUP BY neighborhood
ORDER BY num_rides DESC
LIMIT 3;
100% ▕████████████████████████████████████████████████████████████▏
┌──────────────┬───────────┐
│ neighborhood │ num_rides │
│ varchar │ int64 │
├──────────────┼───────────┤
│ Midtown │ 6253835 │
│ Chelsea │ 6238693 │
│ East Village │ 4047396 │
└──────────────┴───────────┘
Run Time (s): real 28.221 user 210.012643 sys 0.748281
参考
https://duckdb.org/docs/stable/core_extensions/spatial/overview.html
https://duckdb.org/2025/08/08/spatial-joins.html
你有什么想法?
欢迎留言, 反正我觉得PostGIS在开源GIS数据库领域的霸主地位到头了!