Custom Indexing for Latitude-Longitude Data

In the June 2012 issue of MSDN Magazine, I wrote an article that describes how to create custom indexes for SQL data which represents geo-spatial information, that is, latitude and longitude data. The essential problem that custom geo-spatial indexes solve is quickly finding neighbors to a given data point. For example, suppose you have a huge database of mobile device user information and one user is located at latitude 47.00 and longitude -122.00 (this is in Redmond, WA). You want to find all users that are within 1 degree latitude and longitude of the user. A simple statement like (note: avoiding >= and <= symbols)

SELECT userID FROM tblData
WHERE lat greater-or-equal 46.50 AND lat less-or-equal 47.50
AND lon greater-or-equal -122.50 AND lon less-or-equal -121.50

could take a very long time to execute. So the idea of custom indexing is to assign a geographical sector ID to every user. For example, suppose that the 1 degree by 1 degree rectangle above had sector ID 1234. Then the select statement to find all nearby users would be

SELECT userID FROM tblData
WHERE sectorID = 1234

Assuming sectorID is indexed, this would be very fast. Of course the devil is in the details. You can read the article online at

This entry was posted in Software Test Automation. Bookmark the permalink.