我们在CockroachDB中建立了可扩展的空间索引

支持空间数据和空间索引是CockroachDB历史上最需要的功能之一。 CockroachDB中要求空间数据的第一个问题于2017年10月打开，并于2020年11月12日随着CockroachDB 20.2中空间数据存储的发布而关闭。

空间数据有时也称为地理空间数据，是包含有关地理（和几何）特征的信息的数据，而PostGIS是使用中最受欢迎的空间数据扩展之一。 CockroachDB的空间数据存储和处理功能与PostGIS兼容，同时还提供了CockroachDB的规模和弹性。

这篇博客文章讨论了我们如何在水平可扩展的动态分片数据库中构建空间索引。它还涵盖了为什么不能仅在CockroachDB之上使用PostGIS是不可行的选择的原因，因为PostGIS依赖的R树索引与CockroachDB如何实现动态水平缩放不兼容。

当前的空间索引方法分为两类。一种方法是“划分对象”。通过将对象插入平衡树中来工作，平衡树的结构取决于所索引的数据。另一种方法是“划分空间”。这通过创建索引到各种大小的存储桶中的空间的分解来起作用。

在这两种方法中，当对一个对象/形状进行索引时，都会构造一个“覆盖”的形状（例如边界框），该形状完全包含被索引的对象。索引查询通过查找查询对象/形状的覆盖形状与索引的覆盖形状之间的包含/相交来工作。这将检索到误报，但不会检索到误报。例如，下图以虚线显示了三个形状A，B，C和相应的覆盖形状。 A和B的覆盖物彼此相交，但不与C的覆盖物相交。使用索引计算的相交会产生A和B相交的假阳性，这将通过对实际面积进行精确的相交评估而消除。形状。

PostGIS是划分对象的显着实现。它维护一个“ R树”（矩形树），该树被实现为Postgres“ GiST”索引。 PostGIS使用的覆盖形状是“边界框”，是包围索引形状的最小矩形。下面显示了R树的示例，其中红色（实心）矩形显示边界框，并且是相应树中的叶节点。蓝色（虚线）矩形是中间节点，并且在其子树中包含所有边界框。从根开始的搜索可以省略没有重叠的子树。例如，考虑搜索与标记为B的黄色三角形相交的形状，并用其边界框显示。从根开始的搜索将省略R2。然后在孩子处，它将省略R3，并同时探索R4和R5。探索R5时，R13，R14都不相关，而在R4中，仅R11相关。

空间索引的另一种方法是将空间“划分”为具有一定数量的级别和数据独立形状的四叉树（或一组四叉树）。四叉树中的每个节点（一个“单元”）代表索引空间的一部分，并且被水平和垂直划分一次，以在下一级产生4个子级。四叉树中的每个节点都有一个唯一的数字ID。

划分空间算法倾向于对唯一的数字单元格ID使用巧妙的策略，并具有重要的保证：

Google的S2库就是这种方法的一个示例，该方法用于划分地球并使用希尔伯特曲线分配单元ID。

下图显示了在四叉树中索引的点（用小圆圈表示），其中各种大小的正方形是四叉树像元。

在为对象编制索引时，通常使用一些预定义的单元格来计算覆盖率。可以通过使用上面的cell-ID属性来检索祖先和后代。

覆盖单元的数量可以随每个索引对象而变化。在用来表示索引中对象的像元数量上有一个重要的权衡：更少的像元使用更少的空间，但覆盖范围更小。较宽松的覆盖范围可从索引中检索更多误报，这很昂贵，因为在索引查询后执行的准确答案计算非常昂贵。但是，检索较少的误报的好处可能会被扫描大索引所花费的时间所抵消。下图显示了使用S2库构建的巴黎市的4和8个单元覆盖物。用户可以使用CockroachDB的ST_S2Covering函数和geojson.io构建这种可视化效果，如此处所述。

由于空间是预先划分的，因此必须具有有限的边界。这意味着当将要使用的平面的一部分有界时，“划分空间”适用于GEOGRAPHY（球面/椭球形几何体）和GEOMETRY（平面几何体）。稍后我们将讨论如何配置GEOMETRY的边界，以及如何处理超出边界的形状的情况。

CockroachDB是一个动态分片，水平可伸缩的SQL数据库，它将所有数据按字典顺序排列。随着工作负载的增加，表和索引将按照此顺序分成多个范围，并且在节点之间移动范围以平衡负载。以后，当负载减少时，可以合并范围。与范围拆分/合并/重新平衡有关的活动仅限于受影响的范围，不会影响其他范围，这对于实现水平缩放至关重要。对象划分方法与该方案不兼容，因为：

中间节点的形状取决于许多索引形状，从而创建了非本地化的依赖关系。

由于这些原因，CockroachDB使用了S2库来实现空间分割。 CockroachDB的词典总顺序很容易表示出完全有序的单元ID。

此选择具有一些其他优点：（a）批量提取变得简单，并且（b）在我们的日志结构合并树（LSM tree）中，用于组织存储的压缩可以以流方式在整个输入文件中进行，从而最大程度地减少了内存消费。相比之下，作为对象划分方法的BKD树也允许采用日志结构的存储组织，但是就我们所知，压缩需要加载所有输入文件以重新分配对象。

空间数据被索引为包含表的单元格ID和主键的反向索引。

在下面的示例中，主键是城市名称，并显示我们之前示例中使用4个单元ID索引的城市，其中，使用S2库计算单元ID以进行单元覆盖和ID分配。

请注意，可以在封面中为多个表行使用特定的单元格ID，并且每个表行在封面中可以具有多个单元格ID，即，它是多对多关系。

现在我们来介绍最有趣的部分-如何使用这种反向索引来评估查询。

考虑一个查询，该查询试图计算哪些索引形状包含给定的形状，或更一般地说，基于此包含关系尝试连接两个表。例如，如果我们有两个包含城市和公园及其相应几何形状的表，则可以执行以下操作将每个公园与其所在的城市配对。

我们可以将这个问题简化为：给定实际形状g，找到包含g的索引形状。在连接的情况下，g将在连接的一侧连续采用每个几何的值。

以下抽象示例说明了如何使用索引对其进行评估。在此示例中，c [i]是一个单元号。考虑到g在以c [0]为根的四叉树中具有覆盖c [213]，c [61]，c [64]的单元。在这里的编号中，单元格c [i]的子代编号为c [4 * i + 1]…c [4 * i + 4]（为便于说明，我们未使用希尔伯特曲线进行编号）。下面将这种覆盖物描绘为一棵树，其中叶单元格为覆盖单元格。请注意，从叶到根的路径长度不相同。

所有包含g的形状都必须具有包含c [213]，c [61]和c [64]的覆盖。假定符号index（c），其中c是一个单元格，它返回在单元格c的索引中有一个条目的所有形状。满足包含功能的索引形状为：

（索引（c [213]）索引（c [53]）索引（c [13]）索引（c [3]）索引（c [0]））索引（索引（c61）索引（ c15）索引（c3）索引（c0））（索引（c64）索引（c15）索引（c3）索引（c0））

在上面可以排除常见的子表达式，从而提高评估效率。为了执行这样的集合表达式评估，我们开发了新的分布式查询处理器，我们将在下一部分中进行讨论。

我们引入了两个新的分布式查询处理器，即反向过滤器和反向连接器，它们适用于空间SELECT和JOIN查询。这些可以评估从要评估的表达式派生的通用集合表达式。这两个运算符都可以分布，以进行可伸缩的评估。这些集合表示为要从倒排索引扫描的单元格范围。这些处理程序会产生误报，因为覆盖物不能准确地代表原始形状。随后使用查找联接消除这些误报，该查找联接检索原始形状并对空间表达式进行精确评估。我们基于成本的查询优化器会自动计划使用这些新处理器以及随后的查找联接。

基于成本的优化器使用单元ID上的直方图来决定何时使用反向过滤器。目前计划使用启发式方法而不是基于成本的方法来进行反向连接。

使用空间索引可以加速此处列出的25种以上的空间功能和功能变体。包含空间和非空间函数的复杂表达式也可以使用空间索引来加速。

以下是我们先前查询的EXPLAIN输出，其中显示了反向连接和后续查找连接。

＆gt; EXPLAIN SELECT parks.name，citys.nameFROM城市JOIN parksON ST_Contains（cities.geom，parks.geom）;树|字段|描述--------------------- + ----------------------- + --- ----------------------- |分配|全查询联接| | │| |表格| parks @ primary│｜ |平等| （名称）=（名称）│｜ |平等是关键| │| | pred的| pred的| pred的st_contains（geom，geom）└──反向连接| | │｜ |表格| parks @ geom_index└──扫描| | |表格| city @ primary |跨越|全扫描

到目前为止，我们已经考虑了空间索引的算法方面。空间数据库处理的现实世界数据可能带来更多挑战。

良好的电池盖对于性能至关重要。我们在电池盖质量方面面临两个问题。

首先，线段接近共线的多边形可能会使覆盖范围生成器产生非常宽的覆盖范围，例如，城市邻域的多边形的整个地球覆盖范围。我们通过启发式方法解决了这一问题，该方法可以识别出这种不良的覆盖物，而后退到使用形状的边界框生成覆盖物。

其次，对于接近矩形的形状，单元格覆盖可能比使用边界框的“划分对象”索引差。我们在巴黎的较早示例就是此问题的一个极端极端的表示，其中4个单元的覆盖面积是原始形状面积的5倍以上。请注意，在许多形状中，单元格覆盖效果可能比边界框好。

通过开发一种使我们接近两种方法中最好方法的方案，我们已经解决了这一问题。在我们的方案中，倒排索引既存储单元格ID，又存储原始形状的边界框。在将单元格用作集合表达式计算的一部分之前，我们使用边界框快速检查原始形状是否可以满足表达式，如果不满足，则忽略与单元格ID一起存储的键。对于某些工作负载，我们发现该方案的误报率降低了3倍。

前面我们讨论了“划分空间”是如何要求有界空间预先指定的。对于用于GEOGRAPHY类型的球面/椭球形几何体来说，这不是问题。但是，这对于GEOMETRY类型可能是一个挑战。我们采用了两方面的方法来最大限度地提高用户的可用性和性能：

当要索引的GEOMETRY列具有对应于地球投影的已知SRID时，我们将自动推断出索引的有限空间。 CockroachDB可识别6000多个SRID，包括所有EPSG支持的SRID。

当SRID未知时，我们使用合理的默认值来减少形状不适合有限空间的可能性。最后，如果这还不够，那么用户可以在创建索引时指定范围。

在这种情况下，我们会适度降低索引性能。超过有限空间的形状将被剪切并索引，该ID对应于落入有限空间的部分的单元ID以及特殊的溢出单元ID。用于查询的特定几何图形也得到类似处理-如果该几何图形不超过有限空间，我们就不需要查询溢出单元ID。

我们计划根据用户的反馈意见继续改善空间索引编制。我们正在研究的领域包括：

地理分区的空间索引：CockroachDB的一项引人注目的功能是对地理分区的支持，这可以减少延迟并满足合规性要求。包括空间倒排索引在内的倒排索引当前无法进行地理分区。我们正在积极致力于地理分区的倒排索引。

左联接算法的改进：我们为涉及空间倒排索引的左外部/半/反联接生成的计划效率不如我们期望的那样高（与内部联接不同）。我们正在积极研究一种新的方案，以解决“非覆盖”索引的这一问题。即无法完全评估表达式的索引，要么是因为它们不包含表达式所需的所有列，要么是包含不精确的列，例如覆盖空间索引中的单元格。

对具有倒排索引的其他类型的查询改进：CockroachDB已经支持JSON和ARRAY类型的倒排索引。这些反向索引上的查询当前不使用上述新的分布式查询处理器。我们正在积极致力于将这些处理器用于JSON和ARRAY类型。

用于空间查询的Pebble优化：现在，我们拥有一个内部存储引擎Pebble，我们已经确定并进行了优化以更好地支持反向索引查询，这将在下一版本中提供。

如果您对空间数据想要获得的功能有任何反馈，请随时与我们联系。您可以将其发布在CockroachDB Community Slack的#spatial或＃product-feedback渠道中。