16

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
5
  • 1
    Is this lidar data? If so consider adding a lidar tag. Jul 11, 2011 at 19:16
  • 2
    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, 2011 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, 2011 at 20:39
  • 1
    @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, 2011 at 20:48
  • Is this grid data? Why not use a raster? Jul 12, 2011 at 21:21

3 Answers 3

9

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]
2
1

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.

1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.