# optimize nearest neighbor query on 70 million extremely high density spatial point cloud on SQL Server 2008

I have about 75 million records in a SQL Server 2008 R2 Express database. Each is a lat long corresponding to some value. The table has geography column. I am trying to find one nearest neighbor for a given latitude longitude (point). I already have a query with spatial index in place. But depending on where the record is in the database, say first quarter or last quarter, the query can take about from 3 to 30 seconds to find the nearest neighbor. I feel this can be optimized to give lot faster result by optimizing the query or spatial index. Right now applied some the spatial index with default settings. Here is what my table and query looks like.

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]


The spatial Index i am using:

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]


Here is the Query I am using:

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


Here is a sample of lat longs in my database . to give an idea of accuracy and density. All the 70 million records are for one city (Lidar Data)

POINT (-95.669434934023087 30.049513838913736)


Now this query gives me results as i described above, but i want to improve the performance as much as possible. My guess is by tweaking the default values of the spatial index i may be above to better optimize the performance. Any clues this?

I tried varying the buffer from 10 to 1000 but with almost same results.

Also any other suggestions to improve the performance are welcome.

Here is the system i am using right now:

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

-
Is this lidar data? If so consider adding a lidar tag. –  Kirk Kuykendall Jul 11 '11 at 19:16
yes this is lidar data. will add the tag thanks. –  Shaunak Jul 11 '11 at 20:26
I don't speak SQL Server, but it looks to my untutored eye that your query has to find all points lying within a 1000 meter buffer of the target point. These point-in-polygon tests are going to be way slower than proximity tests, which are the basis for solutions offered in your previous question. –  whuber Jul 11 '11 at 20:30
@whuber: I have tried distance based queries and the time in minutes. way to high. May be i am going wrong some where. As of these point in polygon, it takes time in seconds. Even varying the buffer from 10 to 10000 has little imact on time. –  Shaunak Jul 11 '11 at 20:39
@Shaunak Then there's something the matter with the distance-based queries, because theoretically they can be done on average in microseconds (or better) and in milliseconds (worst case) using appropriate indexes such as K-D trees. You might want to think about improving them rather than looking for ways to optimize the point-in-buffer search. –  whuber Jul 11 '11 at 20:48

Try running the sp_help_spatial_geography_index stored procedure to get details on how your spatial index is being used. You should be able to use something like:

declare @ms_at geography = 'POINT (-95.66 30.04)'
set @ms_at = @ms_at.STBuffer(1000).STAsText()
exec sp_help_spatial_geography_index 'lidar', 'SPATIAL_lidar', 0, @ms_at;


Post the results in your question to see if anything stands out. The meaning for each of the items can be found here.

If your coordinates were projected then you could also do a simple non-spatial query on calculated X,Y fields, and checking X < MinX and X > MaxX etc.

Projecting your coordinates (in a GEOMETRY type field) also allows you to limit your spatial index to the extent of the data which can speed up performance considerably. Replace the world extents with the extents of your data:

CREATE SPATIAL INDEX [SPATIAL_lidar] ON [dbo].[lidar] ([geom]) USING  GEOMETRY_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,
BOUNDING_BOX =(-90, -180, 90, 180),) ON [PRIMARY]

-
According to technet.microsoft.com/en-us/library/bb934196.aspx the BOUNDING_BOX can only be used for GEOMETRY_GRID, not GEOGRAPHY_GRID –  Kelso Jul 11 '11 at 23:33
Updated answer. The GEOMETRY type should be far faster as the BOUNDING_BOX can be set. –  geographika Jul 12 '11 at 7:38
thanks. Let me try that and get back! –  Shaunak Jul 12 '11 at 13:44

Consider simplifying the buffer with BufferwithTolerance. If points are tightly packed the system has to identify if a point is either side of the boundary. The simpler that line is, the less work the machine has to do.

-

Check out this resource by Isaac Kunen about using a numbers table to optimize nearest neighbor using a spatial index

http://blogs.msdn.com/b/isaac/archive/2008/10/23/nearest-neighbors.aspx

-