在SQL Server 2008上优化7000万个极高密度空间点云的最近邻查询

我在SQL Server 2008 R2 Express数据库中有大约7500万条记录。每个都是对应于某个值的lat long。这个表有地理列。我试图为给定的经纬度(点)找到一个最近的邻居。我已经有一个查询与空间索引到位。但是，根据记录在数据库中的位置，比如第一季度或上一季度，查询可能需要大约3到30秒才能找到最近的邻居。我觉得这可以通过优化查询或空间索引来优化，从而获得更快的结果。现在应用一些默认设置的空间索引。下面是我的表和查询的样子。

CREATE TABLE lidar(
    [id] [bigint] IDENTITY(1,1) NOT NULL,
    [POINTID] [int] NOT NULL,
    [GRID_CODE] [numeric](17, 8) NULL,
    [geom] [geography] NULL,
 CONSTRAINT [PK_lidar_1] PRIMARY KEY CLUSTERED ([id] ASC)
 WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, IGNORE_DUP_KEY = OFF, 
 ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
) ON [PRIMARY]

我使用的空间索引:

CREATE SPATIAL INDEX [SPATIAL_lidar] ON [dbo].[lidar] ([geom]) USING  GEOGRAPHY_GRID 
WITH (
GRIDS =(LEVEL_1 = MEDIUM,LEVEL_2 = MEDIUM,LEVEL_3 = MEDIUM,LEVEL_4 = MEDIUM), 
CELLS_PER_OBJECT = 16, PAD_INDEX  = OFF, SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF,  
ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]

下面是我使用的查询:

declare @ms_at geography = 'POINT (-95.66 30.04)';
select TOP(1) nearPoints.geom.STAsText()as latlon 
from
(
select r.geom
from lidar r With(Index(SPATIAL_lidar))
where r.geom.STIntersects(@ms_at.STBuffer(1000)) = 1
) nearPoints

下面是我的数据库中的一个示例。给大家一个精确和密度的概念。所有7000万条记录都是针对一个城市的(激光雷达数据)

POINT (-95.669434934023087 30.049513838913736)

现在这个查询给了我如上所述的结果，但是我想尽可能地提高性能。我的猜测是，通过调整空间索引的默认值，我可能能够提高性能。有什么线索吗?

我尝试将缓冲区从10更改为1000，但结果几乎相同。

也欢迎任何其他改善性能的建议。

这是我现在使用的系统:

Windows 7 64bit Professional
Intel(R) Core(TM)2 Quad CPU    Q9650  @ 3.00GHz (4 CPUs), ~3.0GHz
Ram: 8 GB
NVIDIA GeForce 9500 GT

对不起，但这不是SQL答案，而是一种获得可预测性能的方法，假设您的数据受到某些约束。

数据变化的频率是多少?如果可能的话，你是否可以预先计算出每个最近邻居实体的图，并使用它来加快你的选择?

如果这个数据大部分是只读的，那么…

这些点的分布有多均匀?如果分布相当均匀，那么你可以通过在哈希表中存储每个坐标和索引来滚动你自己的空间映射。

如果您不需要在数据库中保存数据，请将其移到内存映射文件中以进行快速散列查找。(70m的记录应该可以很容易地存储在内存中)。

我使用这个架构来生成亚毫秒级的搜索，用于显示广告和搜索引擎相关性。

= =精化= =

你只需创建一个固定大小的正方形网格(如棋盘)，并将每个点映射到网格中，然后创建一个属于每个网格盒子的对象列表——如果你正确调整每个盒子的大小，你应该在每个正方形中平均有5-50个点——这在原则上是一个四叉树，但为了简单起见没有树。

将所有数据分散到桶中后，对于每个空桶，添加最近的包含数据的桶的信息。

你现在可以给每个桶从左到右- y-line编号，这样每个桶都有一个唯一的数字，可以从坐标计算——你把每个桶插入一个哈希表，或者如果空间允许，就像一个直接查找表。

现在，当你有了你的查询，你只需计算将映射到哪个桶，你将得到一个桶中的对象列表，或者你将得到一个"空"桶，其中包含指针最近的桶有内容。

这将给你你正在寻找的对象的第一个候选列表，现在你只需要运行，看看哪一个是最近的。

在99%的情况下就是这样——但是如果你担心(a)在下一个桶中有一些候选者实际上更近，那么只需检查周围的8个桶，看看你是否能找到更近的。

如果你现在还想获得所有最近对象的列表，那么也为每个对象计算一个由5个最近邻组成的简单网络，这样你就会得到这样的数据结构:a ->{B,C,D, D,E,F}， B->{a,D,G,H,I}， C->{a,J,K,G,M}....

这将形成一个简单的网络，你现在可以用Dijkstra的变化遍历它来得到所有与你最近的点相邻的点

构建数据结构需要时间，但是一旦完成，正确的查找和返回数据集可以在几毫秒内完成(不包括任何http或off-box通信)

对于SQL Server 2008上的常规最近邻查询，可以尝试Isaac在他的博客中记录的方法，该方法使用数字表增加查找的边界，直到找到足够的候选者。另一个建议是尝试改变你的网格密度- HHHH或HHMM可能会更好地用于密集点。

在Sql Server Denali中，优化最近邻查询的功能也将通过常规的SELECT TOP来本地支持。ORDER BY语法

作为旁注，在您的示例中，看起来您在查询中缺少ORDER BY距离子句以配合顶部?您当前的查询将返回距离目标1000米以内的点，但不一定是最近的点。

您尝试过索引设置吗?我通常在每个单元格中使用更高的对象，并在所有网格级别中使用"高"。见下文:

CREATE SPATIAL INDEX [SPATIAL_lidar] ON [dbo].[lidar] ([geom]) USING  GEOGRAPHY_GRID  WITH ( GRIDS =(LEVEL_1 =   HIGH,LEVEL_2 = HIGH,LEVEL_3 = HIGH,LEVEL_4 = HIGH),  CELLS_PER_OBJECT = 64, PAD_INDEX  = OFF, SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF,   ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]

阅读这篇关于空间索引的文章。

我猜你的主过滤器效率很低。你可能需要你的网格密度高，因为你的点是非常密集的。我一直在努力解决的一个问题是如何使LEVEL1的密度大于256 (HIGH)。我很惊讶微软强迫我们只有3个网格密度选项

相关内容

最新更新

热门标签：