Optimize nearest neighbor query on 70 million point cloud on SQL Server 2008

Question

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 about 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

Answer 1

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]

Answer 2

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.

Answer 3

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