How to optimize STDistance execution?
Regardless of any other improvements you make, be sure to test the impact on spatial execution times of enabling trace flags 6532, 6533, and 6534 (start-up only). These turn on native code spatial implementations. SQL Server 2012 Service Pack 3 or SQL Server 2014 Service Pack 2 required (Microsoft Support article). Native compilation is on by default from SQL Server 2016.

For STDistance the important trace flag is 6533. In a simple test, this improved execution time from 2100ms to 150ms without using a spatial index on my laptop's SQL Server 2012 instance.

Example adapted from SQL 2016 – It Just Runs Faster: Native Spatial Implementation(s) by Bob Ward):

Test Data

CREATE TABLE dbo.SpatialTest
(
    ID      integer NOT NULL IDENTITY(1,1) PRIMARY KEY CLUSTERED,
    Points  geography NOT NULL
);
GO
-- Insert random sample points
SET NOCOUNT ON;
GO
DECLARE @Point float = 1.1;

INSERT dbo.SpatialTest (Points) 
VALUES ('POINT(' + CAST(@Point AS varchar(20)) + ' ' + CAST(@Point AS varchar(20)) + ')' );

WHILE(SCOPE_IDENTITY() &lt; 100000)
BEGIN
    SET @Point = @Point + RAND(SCOPE_IDENTITY());
    IF (@Point &gt; 90.0)
    BEGIN
        SET @Point = -89.0 + RAND(SCOPE_IDENTITY());
    END;

    INSERT dbo.SpatialTest (Points) 
    VALUES ( 'POINT(' + CAST(@Point AS varchar(20)) + ' ' + CAST(@Point AS varchar(20)) + ')' );
END;


Test Query

DBCC TRACEON (6533);
DBCC TRACESTATUS;
GO
DECLARE 
    @s datetime2 = SYSUTCDATETIME(),
    @g geography = 'POINT(1.0 80.5)';

SELECT [Matches] = COUNT_BIG(*) 
FROM dbo.SpatialTest AS ST
WHERE ST.Points.STDistance(@g) &gt; 10000000.5
OPTION (MAXDOP 1, RECOMPILE);

SELECT [Elapsed STDistance Query (ms)] = DATEDIFF(MILLISECOND, @s, SYSUTCDATETIME());


Average execution times: 2100ms (trace flag off); 150ms (trace flag on).