How to optimize spatial join?

Question

The SQL Server is pretty fast finding neighbors of a geography in a spatial index. Either it is finding nearest neighbors or all neighbors in specific area, the query result is instant.

I am not able to get the result so fast, if I need to find neighbors for multiple points.

I guess the business case is widely recognized. Let's say we have one table with coordinates of locations (it can be stores, restaurants, offices, etc.) and one table with coordinates of the users and their travel distance.

In the context of the user, if I am in the center of the city and want to travel 5 miles - getting all locations in my range is fast. But in the context of a business, if I want to send email to all users who are in range of my stores, the query is pretty slow.

Here is some sample date with several queries trying to find all users - locations pairs.

DROP TABLE IF EXISTS #Users;
DROP TABLE IF EXISTS #Locations;

CREATE TABLE #Users
(
    [UserID] BIGINT pRIMARY KEY
   ,[Latitude] DECIMAL(9, 6)
   ,[Longitude] DECIMAL(9, 6)
    -- this is our user point and user's travel distances in meters
   ,[CenterGeography] GEOGRAPHY
   ,[TravelDistance] INT
    -- this is the [CenterGeography] * [TravelDistance]
   ,[AreaGeography] GEOGRAPHY
);

CREATE SPATIAL INDEX [IX_#Users_CenterGeography] ON #Users
(
    [CenterGeography]
);

CREATE SPATIAL INDEX [IX_#Users_AreaGeography] ON #Users
(
    [AreaGeography]
);

CREATE TABLE #Locations
(
     [LocationID] BIGINT pRIMARY KEY
    ,[CenterGeography] GEOGRAPHY
);

CREATE SPATIAL INDEX [IX_#Locations_AreaGeography] ON #Locations
(
    [CenterGeography]
);

INSERT INTO #Users ([UserID], [Latitude], [Longitude], [TravelDistance])
SELECT CenterLocations.[CenterID] * 10000 + U.[value]
      ,CenterLocations.[Lat] + ABS(CHECKSUM(NEWID())) % 1000 * 0.0001
      ,CenterLocations.[Long] + ABS(CHECKSUM(NEWID())) % 1000 * 0.0001
      ,1 + ABS(CHECKSUM(NEWID())) % 5 * 1609
FROM GENERATE_SERIES(1, 1000) U
CROSS APPLY
(
    VALUES (1, 13.404954, 52.520008)
          ,(2, 13.737262, 51.050407)
          ,(3, 6.783333, 51.233334)
          ,(4, 9.183333, 48.783333)
          ,(5, 6.953101, 50.935173)
) CenterLocations ([CenterID], [Lat], [Long]);

UPDATE #Users
SET [CenterGeography] = GEOGRAPHY::Point([Latitude], [Longitude], 4326) 
   ,[AreaGeography] = GEOGRAPHY::Point([Latitude], [Longitude], 4326).STBuffer([TravelDistance]);

INSERT INTO #Locations ([LocationID], [CenterGeography])
SELECT CenterLocations.[CenterID] * 10000 + L.[value]
      ,GEOGRAPHY::Point(CenterLocations.[Lat] + ABS(CHECKSUM(NEWID())) % 1000 * 0.0001, CenterLocations.[Long] + ABS(CHECKSUM(NEWID())) % 1000 * 0.0001, 4326)
FROM GENERATE_SERIES(1, 100) L
CROSS APPLY
(
    VALUES (1, 13.404954, 52.520008)
          ,(2, 13.737262, 51.050407)
          ,(3, 6.783333, 51.233334)
          ,(4, 9.183333, 48.783333)
          ,(5, 6.953101, 50.935173)
) CenterLocations ([CenterID], [Lat], [Long]);

RETURN;

-- varint 00 - get locations for one user (the spatial index is used without the hint)

    SELECT U.[UserID]
          ,L.[LocationID]
    FROM #Users U 
    INNER JOIN #Locations L WITH (INDEX = [IX_#Locations_AreaGeography])
        ON U.[CenterGeography].STDistance(L.[CenterGeography] ) <= U.[TravelDistance]
    WHERE U.[UserID] = 10001;

-- variant 01 - intersect -- spatial index not used -- 83 seconds

    DROP TABLE IF EXISTS #TEST;

    SELECT U.[UserID]
          ,L.[LocationID]
    INTO #TEST
    FROM #Users U
    INNER JOIN #Locations L
        ON U.[AreaGeography].STIntersects(L.[CenterGeography]) = 1;

-- variant 02 - STDistance -- spatila index is used -- 62 seconds

    DROP TABLE IF EXISTS #TEST;

    SELECT U.[UserID]
          ,L.[LocationID]
    INTO #TEST
    FROM #Users U
    INNER JOIN #Locations L WITH (INDEX = [IX_#Locations_AreaGeography])
        ON U.[CenterGeography].STDistance(L.[CenterGeography] ) <= U.[TravelDistance];

-- variant 03 - STDistance -- only works if the <= argument is static but it is executed for 13 seconds

    DROP TABLE IF EXISTS #TEST;

    SELECT U.[UserID]
          ,L.[LocationID]
    INTO #TEST
    FROM #Users U WITH (INDEX = [IX_#Users_CenterGeography])
    INNER JOIN #Locations L 
        ON U.[CenterGeography].STDistance(L.[CenterGeography] ) <= 6437 --U.[TravelDistance]
    OPTION (RECOMPILE);

The example uses GENERATE_SERIES, so it requires SQL Server 2022. I can create any type of index or materialized any kind of geography object, so one can change the tables definitions if you want. For now, it seems the fastest technique is variant 03 but it requires hard coded travel distance to work, which basically means I am not returning the correct data.

I want to know is there a way to optimize such queries using spatial data in SQL Server or I need to find alternative to get better performance (for example to pre-calalculate with triggers the locations in range per each user).

Answer 1

Based on the sample data, it seems that variant 02 is the fastest - 62 seconds on my environment.

Alternative solution is to implement bounding box alone. In order to to that we need to calculate the coordinates of the its min and max points based on user's travel distance.

This box will be not accurate - it will include more points (locations) which will be filtered using more precise method - in our case STDistance.

The issue is to ensure all points are included in the initial bounding box. I have tested different formulas to solve this and this is the best one I have found:

DECLARE @BufferPercentage DECIMAL(5, 2) = 1.10;

UPDATE #Users
SET [MinLatitude] = Latitude - (([TravelDistance] * @BufferPercentage) / 111111.0)
   ,[MaxLatitude] = Latitude + (([TravelDistance] * @BufferPercentage) / 111111.0)
   ,[MinLongitude] = Longitude - (([TravelDistance]  * @BufferPercentage ) / (COS(RADIANS(Latitude)) * 6371000 * PI() / 180))
   ,[MaxLongitude] = Longitude + (([TravelDistance]  * @BufferPercentage ) / (COS(RADIANS(Latitude)) * 6371000 * PI() / 180))

We are 10% of each travel distance value. The longitude formula is based on this:

Longitude Modification Factor: The Earth's circumference is not the same at all latitudes. Near the equator, the circumference is greater, and it reduces as you move toward the poles. This means a degree of longitude represents a greater distance at the equator than it does at higher latitudes. To account for this, the formula uses COS(RADIANS(Latitude)). The cosine of the latitude gives us a scaling factor that decreases from 1 at the equator (0 degrees latitude, where the cosine is 1) to 0 at the poles (90 degrees latitude, where the cosine is 0).

Earth’s Mean Radius (in meters): 6371000 represents the mean radius of the Earth in meters. It's an average value that balances out the equatorial and polar radii, providing a standard value to use in spherical Earth calculations.

Radians to Degrees Conversion: Since a degree is a measure of angular distance and the Earth is approximately spherical, we need to convert the travel distance from meters to degrees of longitude. To do this, we divide the distance by the Earth's circumference at the given latitude and convert radians to degrees using PI() / 180, because there are 2 * PI radians in a full circle and thus PI() / 180 radians in one degree.

The new code completes for 3 seconds on my machine, but please not if you are using this, that the results might be not correct as we are using some % add to travel distance as the Earth surface is not perfect sphere.

If someone can share more precise formula it will be nice.

Here is the whole code:

DROP TABLE IF EXISTS #Users;
DROP TABLE IF EXISTS #Locations;

CREATE TABLE #Users
(
    [UserID] BIGINT pRIMARY KEY
   ,[Latitude] DECIMAL(9, 6)
   ,[Longitude] DECIMAL(9, 6)
    -- this is our user point and user's travel distances in meters
   ,[CenterGeography] GEOGRAPHY
   ,[TravelDistance] INT
    -- this is the [CenterGeography] * [TravelDistance]
   ,[AreaGeography] GEOGRAPHY
   --
   ,[MinLatitude] DECIMAL(9, 6)
   ,[MaxLatitude] DECIMAL(9, 6)
   ,[MinLongitude] DECIMAL(9, 6)
   ,[MaxLongitude] DECIMAL(9, 6)
);

CREATE SPATIAL INDEX [IX_#Users_CenterGeography] ON #Users
(
    [CenterGeography]
);

CREATE SPATIAL INDEX [IX_#Users_AreaGeography] ON #Users
(
    [AreaGeography]
);

CREATE TABLE #Locations
(
     [LocationID] BIGINT pRIMARY KEY
    ,[CenterGeography] GEOGRAPHY
);

CREATE SPATIAL INDEX [IX_#Locations_AreaGeography] ON #Locations
(
    [CenterGeography]
);

INSERT INTO #Users ([UserID], [Latitude], [Longitude], [TravelDistance])
SELECT CenterLocations.[CenterID] * 10000 + U.[value]
      ,CenterLocations.[Lat] + ABS(CHECKSUM(NEWID())) % 1000 * 0.0001
      ,CenterLocations.[Long] + ABS(CHECKSUM(NEWID())) % 1000 * 0.0001
      ,1 + ABS(CHECKSUM(NEWID())) % 5 * 1609
FROM GENERATE_SERIES(1, 1000) U
CROSS APPLY
(
    VALUES (1, 13.404954, 52.520008)
          ,(2, 13.737262, 51.050407)
          ,(3, 6.783333, 51.233334)
          ,(4, 9.183333, 48.783333)
          ,(5, 6.953101, 50.935173)
) CenterLocations ([CenterID], [Lat], [Long]);

UPDATE #Users
SET [CenterGeography] = GEOGRAPHY::Point([Latitude], [Longitude], 4326) 
   ,[AreaGeography] = GEOGRAPHY::Point([Latitude], [Longitude], 4326).STBuffer([TravelDistance]);

INSERT INTO #Locations ([LocationID], [CenterGeography])
SELECT CenterLocations.[CenterID] * 10000 + L.[value]
      ,GEOGRAPHY::Point(CenterLocations.[Lat] + ABS(CHECKSUM(NEWID())) % 1000 * 0.0001, CenterLocations.[Long] + ABS(CHECKSUM(NEWID())) % 1000 * 0.0001, 4326)
FROM GENERATE_SERIES(1, 100) L
CROSS APPLY
(
    VALUES (1, 13.404954, 52.520008)
          ,(2, 13.737262, 51.050407)
          ,(3, 6.783333, 51.233334)
          ,(4, 9.183333, 48.783333)
          ,(5, 6.953101, 50.935173)
) CenterLocations ([CenterID], [Lat], [Long]);

RETURN;

    
    DECLARE @BufferPercentage DECIMAL(5, 2) = 1.10;

    UPDATE #Users
    SET [MinLatitude] = Latitude - (([TravelDistance] * @BufferPercentage) / 111111.0)
       ,[MaxLatitude] = Latitude + (([TravelDistance] * @BufferPercentage) / 111111.0)
       ,[MinLongitude] = Longitude - (([TravelDistance]  * @BufferPercentage ) / (COS(RADIANS(Latitude)) * 6371000 * PI() / 180))
       ,[MaxLongitude] = Longitude + (([TravelDistance]  * @BufferPercentage ) / (COS(RADIANS(Latitude)) * 6371000 * PI() / 180))

    DROP TABLE IF EXISTS #TEST;
    DROP TABLE IF EXISTS #TEST3;

    SELECT U.[UserID], L.[LocationID]
    INTO #TEST
    FROM #Users U
    INNER JOIN #Locations L 
        ON L.[CenterGeography].Long >= U.MinLongitude
        AND L.[CenterGeography].Long <= U.MaxLongitude
        AND L.[CenterGeography].Lat >= U.MinLatitude
        AND L.[CenterGeography].Lat <= U.MaxLatitude

    SELECT  U.[UserID], L.[LocationID]
    INTO #TEST3
    FROM #TEST A
    INNER JOIN #Users U
        ON A.[UserID] = U.[UserID]
    INNER JOIN #Locations L
        ON A.LocationID = L.LocationID
    WHERE U.[CenterGeography].STDistance(L.[CenterGeography]) <= U.[TravelDistance]