自DuckDB v1.1.0起，spatial扩展通过R树扩展索引类型提供对空间索引的基本支持。
我为什么要使用R树索引？
在使用地理空间数据集时，根据行与特定感兴趣区域的空间关系进行过滤是非常常见的需求。不幸的是，尽管DuckDB的向量化执行引擎非常快，但这种操作对于大型数据集来说扩展性不佳，因为它总是需要对整个表进行全表扫描以检查每一行。然而，通过使用R树对表进行索引，可以显著加速这些类型的查询。
R树索引如何工作？
R树是一种平衡的树形数据结构，它在叶节点中存储每个几何体的近似最小边界矩形（以及相应行的内部ID），并在每个内部节点中存储包含所有子节点的边界矩形。
几何体的最小边界矩形（MBR）是完全包围该几何体的最小矩形。通常当我们谈论几何体的边界矩形（或在2D几何体上下文中的边界“框”）时，我们指的是最小边界矩形。此外，我们倾向于假设边界框/矩形是轴对齐的，即矩形不旋转——其边始终与坐标轴平行。点的MBR就是点本身。
通过自上而下遍历R树，可以非常快速地在R树索引表中搜索那些索引几何列与特定感兴趣区域相交的行，因为如果父节点的边界矩形根本不与查询区域相交，则可以跳过搜索整个子树。一旦到达叶节点，只需从磁盘中获取那些几何体与查询区域相交的特定行，并且通常更昂贵的精确空间谓词检查（以及任何其他过滤器）也只需对这些行执行。
DuckDB中R树索引的局限性有哪些？
在开始使用R树索引之前，需要注意一些限制：
- R树索引仅支持
GEOMETRY数据类型。 - R树索引仅在表使用以下空间谓词函数之一（因为它们都意味着交集）进行过滤（使用
WHERE子句）时，才用于执行“索引扫描”：ST_Equals,ST_Intersects,ST_Touches,ST_Crosses,ST_Within,ST_Contains,ST_Overlaps,ST_Covers,ST_CoveredBy,ST_ContainsProperly。 - 空间谓词函数的一个参数必须是“常量”（即，在查询规划时其结果已知的表达式）。这是因为查询规划器需要在查询实际执行之前知道查询区域的边界框，以便使用R树索引扫描。
未来，我们希望R树索引能够用于加速额外的谓词函数和更复杂的查询，例如空间连接。
如何在DuckDB中使用R树索引
要创建R树索引，只需使用带有USING RTREE子句的CREATE INDEX语句，并在括号内传入要索引的几何列。例如：
-- Create a table with a geometry column
CREATE TABLE my_table (geom GEOMETRY);
-- Create an R-tree index on the geometry column
CREATE INDEX my_idx ON my_table USING RTREE (geom);
在创建R树索引时，您还可以使用WITH子句传入其他选项来控制R树索引的行为。例如，要指定R树中每个节点的最大条目数，可以使用max_node_capacity选项：
CREATE INDEX my_idx ON my_table USING RTREE (geom) WITH (max_node_capacity = 16);
调整这些选项对性能的影响高度依赖于DuckDB运行的系统设置、数据集的空间分布以及您的特定工作负载的查询模式。默认值应该足够好，但如果您想尝试不同的参数，请参阅此处完整的选项列表。
示例
这是一个示例，展示了如何在几何列上创建R树索引，并且我们可以看到当表通过空间谓词进行过滤时，使用了RTREE_INDEX_SCAN操作符：
INSTALL spatial;
LOAD spatial;
-- Create a table with 10_000_000 random points
CREATE TABLE t1 AS SELECT point::GEOMETRY AS geom
FROM st_generatepoints({min_x: 0, min_y: 0, max_x: 100, max_y: 100}::BOX_2D, 10_000, 1337);
-- Create an index on the table.
CREATE INDEX my_idx ON t1 USING RTREE (geom);
-- Perform a query with a "spatial predicate" on the indexed geometry column
-- Note how the second argument in this case, the ST_MakeEnvelope call is a "constant"
SELECT count(*) FROM t1 WHERE ST_Within(geom, ST_MakeEnvelope(45, 45, 65, 65));
390
我们可以通过使用EXPLAIN语句来验证是否使用了R树索引扫描：
EXPLAIN SELECT count(*) FROM t1 WHERE ST_Within(geom, ST_MakeEnvelope(45, 45, 65, 65));
┌───────────────────────────┐
│ UNGROUPED_AGGREGATE │
│ ──────────────────── │
│ Aggregates: │
│ count_star() │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ FILTER │
│ ──────────────────── │
│ ST_Within(geom, '...') │
│ │
│ ~2000 Rows │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ RTREE_INDEX_SCAN │
│ ──────────────────── │
│ t1 (RTREE INDEX SCAN : │
│ my_idx) │
│ │
│ Projections: geom │
│ │
│ ~10000 Rows │
└───────────────────────────┘
性能考量
批量加载与维护
在已填充的表上创建R树比先创建索引再插入数据要快得多。这是因为R树在插入后节点达到最大容量时，需要定期进行自我再平衡并执行代价较高的分裂操作，这可能会导致额外的分裂向上级联。然而，当R树索引在已填充的表上创建时，会使用一种特殊的自下而上的“批量加载算法”（Sort-Tile-Recursive），该算法将所有条目划分到已平衡的树中，因为所需的节点总数可以从一开始就计算出来。
此外，使用批量加载算法往往会创建结构更好的R树（边界框之间的重叠较少），这通常会带来更好的查询性能。如果您发现R树的查询性能在大量更新或删除后开始下降，则删除并重新创建索引可能会生成更高质量的R树。
内存使用
与DuckDB内置的ART索引一样，所有包含R树的相关缓冲区将从磁盘惰性加载（当DuckDB以磁盘支持模式运行时），但除非索引被删除，否则它们目前不会被卸载。这意味着如果您最终扫描整个索引，整个索引将被加载到内存中并在数据库连接期间保持在那里。但是，R树索引使用的所有内存（即使在批量加载期间）都由DuckDB跟踪，并将计入由memory_limit配置参数设置的内存限制。
调优
根据您的具体工作负载，您可能希望尝试max_node_capacity和min_node_capacity选项，以改变R树的结构以及它对插入和删除的响应方式，请参阅此处完整的选项列表。通常，节点总数更多（即max_node_capacity较低）的树可能会产生更细粒度的结构，从而在查询执行期间实现更积极的子树剪枝，但它也需要更多内存来存储树本身，并且在查询较大区域时会带来更大的性能损失，因为需要遍历更多的内部节点。
选项
创建R树索引时，可以将以下选项传递给WITH子句：（例如，CREATE INDEX my_idx ON my_table USING RTREE (geom) WITH (option = value);）
| 选项 | 描述 | 默认值 |
|---|---|---|
max_node_capacity |
R树中每个节点的最大条目数 | 128 |
min_node_capacity |
R树中每个节点的最小条目数 | 0.4 * max_node_capacity |
*如果节点在删除后条目数低于最小值，该节点将被解散，所有条目将从树的顶部重新插入。这是R树实现中常见的操作，旨在防止树变得过于不平衡。
R树表函数
rtree_index_dump(VARCHAR)表函数可用于返回R树索引中的所有节点，这在调试、性能分析或仅仅检查索引结构时可能很有用。该函数将R树索引的名称作为参数，并返回一个包含以下列的表：
| 列名 | 类型 | 描述 |
|---|---|---|
level |
INTEGER |
节点在R树中的层级。根节点层级为0。 |
bounds |
BOX_2DF |
节点的边界框 |
row_id |
ROW_TYPE |
如果这是一个叶节点，则为表中行的rowid，否则为NULL。 |
示例
-- Create a table with 64 random points
CREATE TABLE t1 AS SELECT point::GEOMETRY AS geom
FROM st_generatepoints({min_x: 0, min_y: 0, max_x: 100, max_y: 100}::BOX_2D, 64, 1337);
-- Create an R-tree index on the geometry column (with a low max_node_capacity for demonstration purposes)
CREATE INDEX my_idx ON t1 USING RTREE (geom) WITH (max_node_capacity = 4);
-- Inspect the R-tree index. Notice how the area of the bounding boxes of the branch nodes
-- decreases as we go deeper into the tree.
SELECT
level,
bounds::GEOMETRY AS geom,
CASE WHEN row_id IS NULL THEN st_area(geom) ELSE NULL END AS area,
row_id,
CASE WHEN row_id IS NULL THEN 'branch' ELSE 'leaf' END AS kind
FROM rtree_index_dump('my_idx')
ORDER BY area DESC;
┌───────┬──────────────────────────────┬────────────────────┬────────┬─────────┐
│ level │ geom │ area │ row_id │ kind │
│ int32 │ geometry │ double │ int64 │ varchar │
├───────┼──────────────────────────────┼────────────────────┼────────┼─────────┤
│ 0 │ POLYGON ((2.17285037040710… │ 3286.396482226409 │ │ branch │
│ 0 │ POLYGON ((6.00962591171264… │ 3193.725100864862 │ │ branch │
│ 0 │ POLYGON ((0.74995160102844… │ 3099.921458393704 │ │ branch │
│ 0 │ POLYGON ((14.6168870925903… │ 2322.2760491675654 │ │ branch │
│ 1 │ POLYGON ((2.17285037040710… │ 604.1520104388514 │ │ branch │
│ 1 │ POLYGON ((26.6022186279296… │ 569.1665467030252 │ │ branch │
│ 1 │ POLYGON ((35.7942314147949… │ 435.24662436250037 │ │ branch │
│ 1 │ POLYGON ((62.2643051147460… │ 396.39027683023596 │ │ branch │
│ 1 │ POLYGON ((59.5225715637207… │ 386.09153403820187 │ │ branch │
│ 1 │ POLYGON ((82.3060836791992… │ 369.15115640929434 │ │ branch │
│ · │ · │ · │ · │ · │
│ · │ · │ · │ · │ · │
│ · │ · │ · │ · │ · │
│ 2 │ POLYGON ((20.5411434173584… │ │ 35 │ leaf │
│ 2 │ POLYGON ((14.6168870925903… │ │ 36 │ leaf │
│ 2 │ POLYGON ((43.7271652221679… │ │ 39 │ leaf │
│ 2 │ POLYGON ((53.4629211425781… │ │ 44 │ leaf │
│ 2 │ POLYGON ((26.6022186279296… │ │ 62 │ leaf │
│ 2 │ POLYGON ((53.1732063293457… │ │ 63 │ leaf │
│ 2 │ POLYGON ((78.1427154541015… │ │ 10 │ leaf │
│ 2 │ POLYGON ((75.1728591918945… │ │ 15 │ leaf │
│ 2 │ POLYGON ((62.2643051147460… │ │ 42 │ leaf │
│ 2 │ POLYGON ((80.5032577514648… │ │ 49 │ leaf │
├───────┴──────────────────────────────┴────────────────────┴────────┴─────────┤
│ 84 rows (20 shown) 5 columns │
└──────────────────────────────────────────────────────────────────────────────┘