ICDE 2022 | RW-tree: 用于构建R-tree的负载感知学习框架

时空实验室 2023-05-22

R-tree是比较常用的支持多维数据查询的索引。它的性能主要取决于在插入新的数据时如何构建树的结构。然而，现有工作没有考虑工作负载信息，因此研究工作负载感知的R-tree对于查询性能的优化有着重要的意义。本次为大家带来数据库领域顶级会议ICDE的论文：《RW-Tree: A Learned Workload-aware Framework for R-tree Construction》

一．背景

R-tree是一种流行的用于空间数据的树形数据结构，可以用来索引多维数据，如地理坐标、矩形或多边形，它由分层的最小边界矩形（MBRs）表示。查询效率主要取决于R-tree的结构。因此，该领域的现有工作都致力于如何在插入新数据的同时保持R-tree的良好结构。

现有工作可大致分为两类。一类是批处理的方法，它是在收集好数据后自下而上地构建R-tree，这种方法的缺陷在于不支持实时数据的更新。另一类是在插入过程中不断修改R-tree的结构。然而，目前这方面的工作都采用一些启发式的方法（比如根据插入后MBR的面积扩大量），并没有考虑实际工作负载。由于现实世界中的工作负载总是遵循一定的分布规律，在知道工作负载的前提下，可以构建一个能有效执行与给定工作负载分布相同的查询的R-tree。因此，论文旨在通过考虑历史查询工作量信息来优化R-tree的构造。

该工作主要存在以下3个难点：1) 如何捕捉工作负载的特征并将其表示出来以实现高效的优化；2) 给定工作负载，如何评估某个选择（比如选择插入哪个子节点）给查询带来的好处；3) 除了范围查询，KNN查询也是空间查询的一个重要种类，应该如何同时考虑这两种查询的负载。

论文提出了RW-tree，一个学习型的工作负载感知框架。它首先从查询工作负载中提取几个重要的特征，并学习一个表示工作负载的分布，这样在构建R-tree时就可以很好地捕获工作负载的特征（针对挑战1）。然后，给定工作负载表示，论文提出了一个成本模型作为度量，它可以较为准确地估计实际查询执行时间（针对挑战2）。第三，当工作负载同时包含范围搜索查询和KNN查询时，论文将KNN查询转换为范围查询，并利用学习到的数据分布来回答这些查询（针对挑战3）。

二．前言

2.1 问题定义

正如我们所知，R-tree是一个数据结构，它将邻近的数据实例进行分组，将它们表示为一个MBR，并将这些MBR组织为一个平衡的搜索树。给定一个R-tree，查询时，利用MBR来决定是否在子树中进行搜索。因此，树的结构对搜索性能有很大的影响，这是由数据插入操作决定的。若要插入一条数据，需要从根节点递归地遍历，其中有两个关键步骤：1) 选择插入的子树：在迭代的过程中，每一层都需要选择一个子树进行插入；2) 拆分溢出节点：当一个节点的数据量到达存储上限时，需要将其拆分成两部分或者重新插入一些数据。

2.2 传统启发式方法的缺陷

为了解决上述两个问题，传统的方法往往从MBR的面积进行考虑。以最经典的R-tree为例，它会选择让面积扩大最小的节点进行插入。处理溢出时，它选择分裂后总面积最小的方案。如图 1所示，虚线矩形代表查询，实心矩形代表R-tree节点，假设R15即将被插入R-tree，首先需要从R21和R22中选择一个节点进行插入，如果采用传统的R-tree，如(b)所示，它会扩大R21以覆盖R15，因为R21需要扩大的面积小于R22所需要的。然而，右上角的三个查询q1，q2和q3会导致额外的IO，因为R21在扩大后与它们相交了，需要进行一次额外的扫描。然而如果我们如(c)所示扩大R22，那么只有q4会受影响。

图 1 插入策略示例

2.3 工作负载感知数据插入

根据这个例子，我们可以看到，考虑到查询工作负载，简单地依赖区域扩大的面积来选择要插入的子树可能不是一个好的选择。理想情况下，给定一个查询工作负载，一个数据实例，和几个候选插入的MBR，如果能准确地获得数据在插入某个MBR后查询性能的变化的话，就可以选择最佳的MBR。但是，获得性能变化相当困难，因为1) 查询工作负载（包括未来）的整个分布很难预测，并且2) 性能的变化只有查询后才知道。对于前者，论文假设工作负载会长时间保持稳定，因此基于历史工作负载构建R-tree是可行的。对于后者，论文建议使用一种基于学习的方法来估计数据插入带来的性能变化。

2.4 Cost：已扫描节点的数量

对于广泛使用的范围查询，搜索算法是递归扫描与查询范围重叠的节点。由于R-tree是平衡的，因此每个节点上的扫描时间相似，扫描节点的数量与查询执行时间成正比。由于工作负载中查询的实际执行时间很难获得，论文建议使用扫描节点的总数（扫描数命名为成本，用C表示）作为性能的度量。

2.5 通过cost优化插入操作

给定R-tree T以及查询负载W，记C(T,W)为T在W下的表现。在数据R插入时，树的结构可能会发生改变，产生新的R-tree T’，此时的成本记为C(T’,W)。此时，优化问题就相当于找到T’，使C(T’,W)最小。

三．方法

3.1 RW-tree框架

RW-tree的总体框架如图 2所示。首先，给定T，W以及R，会产生许多可能的子树T‘。RW-tree使用最佳优先的方式来找到最优的T’。具体来说，在从上到下遍历T时维护一个优先级队列，并首先探索可能导致低成本树状结构的子树，从而减少搜索空间。

在遍历T的时候，RW-tree使用一个学习模型来估计候选子树的成本C(T'，W)。

对于KNN查询，论文将其转化成范围查询后再采用上述的方法建立R-tree。

图 2 RW-tree框架

3.2 成本模型

为了实现工作负载感知的空间数据插入，需要首先知道查询分布，这对于估计成本非常重要。因此，在这一部分中，RW-tree以工作负载W作为输入，并学习其分布。因为工作负载中的每个查询q对应一个MBR，用B (q)表示，可以用中心的坐标（x_q，y_q）、搜索边界MBR的宽度（w_q）和高度（h_q）来表示。因此，查询分布可以用4维概率密度P（x_q, y_q, w_q、h_q）的形式表示，这之后可以通过四维积分来计算得C(n, W)(n为树的一个节点)，C(T’W)可以通过所有节点求和得到。然而，计算四维积分是十分耗时的，论文通过如下的方法来计算：

在实际工作负载中，整个空间的查询分布可能很复杂，但一个合理的假设是，一个局部区域的分布可以近似为均匀分布。在此基础上，利用这些均匀分布可以大大加速积分计算。这个过程可分为以下3步：1) 将整个空间划分为几个分区，每个分区都可以用均匀分布来近似描述；2）计算每个分区的每个均匀分布上的积分；3) 通过将每个分区的结果相加，计算C(n, W）。（划分后的每个分区可通过二维均匀分布积分计算，具体过程可参考原论文）

假设空间被分为了N个分区，记为{P₁,P₂…P_N}。显然，在计算C(n, W)时，并不需要考虑所有分区，因为有的分区中的查询不会与n相交。为了方便计算，论文使用分区内查询宽度的平均值w(—)和高度平均值h(—)来表示同一分区内的所有查询。可以用如下的公式来判断某个分区内的查询是否对节点n有影响：

然后，对于每个可能影响节点n的分区，通过计算其可能影响节点n的面积（这个面积可通过扩展n的MBR得到），然后求和即可得到n的成本。记S（n，p_i）表示为节点n的扩展MBR与p_i的相交面积，ρ_i表示为p_i中的查询密度。最终的成本计算公式如下：

如图 3，对于节点n，假设分区p₁的查询平均宽度为w(—)，高度为h(—)，那么所有可能与n相交的查询矩形的中心点一定位于棕色虚线所形成的矩形之中，此时棕色矩形与p₁的相交面积即是我们需要的面积。

图 3 成本计算

在得知分区后成本计算方法后，一个很重要的问题就是如何得到这样的分区，其中查询的分布遵循均匀分布。这个过程可分为3步，首先，将整个空间划分为网格，将查询映射到相应的网格中，来进行工作量的预处理，然后计算这些查询的统计信息。然后，通过空间填充曲线将这些网格进行聚类，其中同一簇中的查询具有类似的统计信息。最后，基于这些簇计算空间分区。

第一步将整个空间划分成多个均匀的小网格，并统计每个网格的查询密度、平均高度和宽度。

第二步是对网格进行聚类，由于我们的目标是希望每个分区中查询呈均匀分布，因此分区中的网格应该是空间连续的，并且具有相似的特征。首先，为了实现空间连续性，论文使用空间填充曲线对所有网格进行排序。此时，给定曲线上的任意连续区间，与该区间对应的网格将构成连续的空间。因此，如果我们把已排序的网格序列划分为几个片段，每个片段将对应于一个空间连续的分区。接下来，我们将介绍如何划分序列，以确保每个片段内部都有具有相似特征的网格。以密度特征ρ为例，如图 4所示，在使用空间填充曲线编号后，就可以得到ρ对应的累计分布函数（b），其中

。接着，论文计算了一个分段线性函数CF^∗_ρ来近似累积函数，它可以很好地表示ρ的分布。如果我们想得到一个这样的分区，在该分区内，每个网格的特征相似，那么，这些网格对应的累计分布函数的梯度应该是相似的。在(c)中我们可以观察到，1-3网格对应的累计分布函数的梯度是固定的，因此1-3网格将被聚到一个簇。

图 4 学习集群网格

除了ρ外，还需要根据平均高度和宽度来进行聚类。图 5的(a)，(b)，(c)对应了三种簇。接着，对于每个特征中的每个簇，分配一个独特的ID。比如(a)中的第一个分区的ID就是1。然后每个网格的特征可用一个三元组表示，如果两个网格的空间填充曲线ID邻近并且特征的三元组相同，它们将会被聚到新的一个簇。比如(d)中右下角四个矩形就被聚到一个簇。最后一步是将簇转换成矩形区域，因为聚好的簇可能形状不规整。论文采用贪心算法来解决这个问题，当一个簇不是规整的矩形时，会将其切成多个矩形，这个过程是不断从中切取最大矩形。

图 5 将簇调整成空间分区

3.3 KNN查询

对于任何给定的查询点o =（x_o，y_o），记KNN (o)为o的k个最近邻的集合。假设o的第k个最接近的数据为o'，o'与o之间的距离用d (o)表示。由于KNN查询是用最佳优先搜索算法实现的，因此KNN (o)的扫描节点与以o为中心，d (o)为半径的范围查询相同[1]。因此，我们可以将KNN查询转换为范围搜索查询，并使用上述框架来解决这个问题，其核心问题是如何计算d (o)。

为了预测d (o)，首先，需要学习数据的分布，用Q（x，y）表示。然后，使用

来表示搜索框内的期望数据量，即以o为圆心，d (o)为半径的圆的查询范围内的数据的期望数量。之后，通过求解函数E(o, d(o))=k，我们可以推导出相应的d (o) 。具体求解过程可参考原论文。

四．实验

论文使用了两个合成数据集以及两个真实数据集来评估RW-tree的性能，数据集的相关信息如表 1所示，其中，Syn-Uni和Syn-Skew为合成数据集。Syn-Uni数据集中，矩形的中心点的分布呈均匀分布。而Syn-Skew呈二维正态分布。

表 1

由于RW-tree旨在基于历史工作负载优化数据插入操作，因此工作负载的一些特征可能会影响RW-tree的性能。除了工作负载的一些常规统计数据（例如查询的长宽度）外，论文还考虑了工作负载的倾斜度和选择性：

倾斜度：查询的宽度和高度之比的较大值，即
选择性：查询的区域面积与整个数据集所占空间面积的比值

论文选用了经典的R-tree变体R*-tree作为对比方法。

4.1 不同倾斜度下性能对比

图 6展示了在不同的倾斜度下RW-tree与R*-tree的性能表现，可以看到，随着倾斜度的增大，RW-tree和R*-tree之间的差距逐渐变大，这说明通过学习历史查询R-tree可以保持一个更优的结构。

图 6 不同倾斜度下方法对比

4.2 KNN查询性能评估

论文根据之前使用的范围查询的负载生成KNN查询。以范围查询的中心点作为KNN查询的搜索点，并在相应的数据集上执行KNN查询。图 7显示了不同数据集的KNN工作负载的总执行时间。总体而言，RW-tree在所有测试用例中都优于R*-tree。此外，可以观察到OSM-CA数据集的性能改进优于Syn-Uni数据集。原因是RW-tree首先将KNN查询转换为范围查询，以训练RW-tree的代价模型。由于Syn-Uni数据集遵循均匀分布，RW-tree的性能提升受限于其低倾斜度。

图 7 KNN查询性能评估

4.3 成本学习模型效果评估

由于成本模型对RW-tree的整体性能有很大的贡献，论文通过将成本模型与执行工作负载的真实成本进行比较来评估学习成本模型的效果。

结果如图 8所示，可以看到，通过模型学到的成本与真实成本遵循类似的分布，这表明学习到的成本模型工作得很好。

图 8 成本模型的效果i

五．总结

本文介绍了RW-tree，一个通过学习历史查询来优化R-tree的插入过程的框架。论文首先提出了一种基于学习的方法来学习工作负载的分布。然后，提出了一个成本模型来衡量数据插入策略的性能，并选择最佳的数据插入策略。此外，RW-tree同时支持范围搜索和KNN查询的优化。实验结果表明，该方法在查询效率方面优于基线方法。

参考文献

[1]N. Roussopoulos, S. Kelley, and F. Vincent. Nearest neighbor queries. In SIGMOD Conference 1995, pages 71–79, 1995.

-End-

本文作者

何翔

重庆大学计算机科学与技术专业在读硕士一年级学生，重庆大学START团队成员，主要研究方向：时空数据管理

时空艺术团队（START，Spatio-Temporal Art）来自重庆大学时空实验室，旨在发挥企业和高校的优势，深入探索时空数据收集、存储、管理、挖掘、可视化相关技术，并积极推进学术成果在产业界的落地！年度有2~3名研究生名额，欢迎计算机、GIS等相关专业的学生报考！

r-tree 空间数据特征选择 knn

文章转载自时空实验室，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

ICDE 2022 | RW-tree: 用于构建R-tree的负载感知学习框架

评论

相关阅读