SQL server Coordinate distance optimization

Question

I am working with SQL server 2008 on query that looks for users within certain distance from central point that is moving - which means I am constantly hitting database (new results need to be added to the existing set and ones out of distance to be removed) and every millisecond saved is of value.

ATM we are using following query (Id's are used cause they are indexed ATM and good when trying for speed):

declare @lat int = 500,
@lon int = 700

  SELECT @lat, @lon, id, journeyid,  ((ACOS(SIN(@lat * PI() / 180) * SIN([Id] * PI() / 180) + 
         COS(@lat * PI() / 180) * COS([Id] * PI() / 180) * COS((@lon - [JourneyId]) * 
         PI() / 180)) * 180 / PI()) * 60 * 1.1515) as dist
FROM [OnlineLegal_dev1].[dbo].[Customer] 
         group by [Id], [JourneyId], ((ACOS(SIN(@lat * PI() / 180) * SIN([Id] * PI() / 180) + 
         COS(@lat * PI() / 180) * COS([Id] * PI() / 180) * COS((@lon - [JourneyId]) * 
         PI() / 180)) * 180 / PI()) * 60 * 1.1515)
HAVING ((ACOS(SIN(@lat * PI() / 180) * SIN([Id] * PI() / 180) + 
         COS(@lat * PI() / 180) * COS([Id] * PI() / 180) * COS((@lon - [JourneyId]) * 
         PI() / 180)) * 180 / PI()) * 60 * 1.1515)<=10000

  ORDER BY ((ACOS(SIN(@lat * PI() / 180) * SIN([Id] * PI() / 180) + 
         COS(@lat * PI() / 180) * COS([Id] * PI() / 180) * COS((@lon - [JourneyId]) * 
         PI() / 180)) * 180 / PI()) * 60 * 1.1515) ASC

Current speed to select top 1k records is 00:00:00.097

How could I optimize this further for speed?

Can you explain your formula, please (some spherical geometry I guess)? Taking the sinus of an ID looks very strange. Why can't you simply calculate the distance with Pythagoras? — Olivier Jacot-Descombes, Jan 05 '16 at 12:53
@OlivierJacot-Descombes Ids are used since those columns are indexed, it would be latitude longitude in actual app. It curves to account for the roundness of earth for coordinates further from equator. If this cannot be optimized well enough another option we might use is square that is multiplied by constant for country since we are based in Europe and countries are small here. — Matas Vaitkevicius, Jan 05 '16 at 13:09
Any reason not to use the geography data type here and let the math be done in the CLR? — Ben Thul, Jan 05 '16 at 17:26
@BenThul TBH I never used it, still I find it hard to believe it could be faster than pure sql solution, am I missing something? — Matas Vaitkevicius, Jan 05 '16 at 17:52
Yes you are. CLR excels at (among other things) doing calculation heavy things like you're doing. Also, you get the advantage of the geography type not assuming that the Earth is a perfect sphere (like the Haversine forumula that you're using does) but rather an oblate spheroid. — Ben Thul, Jan 05 '16 at 19:05
@BenThul I did here are the results http://stackoverflow.com/questions/34763910/sql-geometry-vs-decimal8-6-lat-long-performance/34763914#34763914 — Matas Vaitkevicius, Jan 13 '16 at 10:18

score 1 · Accepted Answer · answered Jan 05 '16 at 12:57

1

DECLARE @lat INT = 500,
        @lon INT = 700

DECLARE @lat_s FLOAT = SIN(@lat * PI() / 180),
        @lat_c FLOAT = COS(@lat * PI() / 180)

SELECT DISTINCT @lat, @lon, *
FROM (
    SELECT
        id,
        journeyid,
        ((ACOS(@lat_s * SIN([id] * PI() / 180) + @lat_c * COS([id] * PI() / 180) * COS((@lon - [JourneyId]) * PI() / 180)) * 180 / PI()) * 60 * 1.1515) AS dist
    FROM dbo.Customer
) t
WHERE dist <= 10000
ORDER BY dist

answered Jan 05 '16 at 12:57

Devart

119,203
23
166
186

Very clever :) Oddly speed is the same, I will add more data for it to show. – Matas Vaitkevicius Jan 05 '16 at 13:02
After indexing and other jazz for 47k records to run 100 times selection of top 1000 where proximity is 10000 - mine is ~28s and yours ~16s. – Matas Vaitkevicius Jan 13 '16 at 09:23
A similar answer can be found https://stackoverflow.com/q/44293480/5058871 – Dov Benyomin Sohacheski Jun 14 '18 at 18:42

score 1 · Answer 2 · answered Jan 05 '16 at 13:12

You could store the pre-calculated values

SIN([Id] * PI() / 180)

and

COS([Id] * PI() / 180)

In the DB, for instance with an INSERT / UPDATE trigger each time an Id is inserted or updated.

CREATE TRIGGER dbo.tiuCustomer ON dbo.Customer
    FOR INSERT, UPDATE
AS BEGIN
   UPDATE dbo.Customer
   SET
       cos_id = COS(Inserted.Id * PI() / 180),
       sin_id = SIN(Inserted.Id * PI() / 180)
   FROM Inserted
   WHERE 
      dbo.Customer.CustomerID = Inserted.CustomerID -- Use the PK to link your table
                                                    -- with Inserted.
END

SQL server Coordinate distance optimization

2 Answers2