SQL Server Geography query is too slow

We have 2 tables, one table is Customers, with each one's location as a Geography column, and one table is Branch Offices also with each one's location as a Geography column (we populate the Geography columns from latitude and longitude columns)

The tables are simple: Cust_Locations has CustNum (integer, PK) and CustLoc (geography, with spatial index), Branch_Locations has BranchNum (integer, PK) and BranchLoc (geography with spatial index).

We need to run a query (view) that's intended to show the closest branch office to each customer, based on Geography columns, and it runs fine with a couple of thousand customers. We just received a big job that needs to run with 700,000 customers and it takes hours to run. Can anyone suggest any ways to speed up this SQL?

WITH CLOSEST AS (
    SELECT *, ROW_NUMBER() 
    OVER (
        PARTITION BY CustNum
        ORDER BY Miles
    ) AS RowNo 
    FROM 
(
SELECT 
CustNum,
BranchNum, 
CONVERT(DECIMAL(10, 6), (BranchLoc.STDistance(CustLoc)) / 1609.344) AS Miles
FROM 
Branch_Locations
CROSS JOIN
Cust_Locations
) AS T
)
SELECT TOP 100 PERCENT CustNum, BranchNum, Miles, RowNo FROM CLOSEST WHERE RowNo = 1 ORDER BY CustNum, MILES

Select allOpen in new window

I have no ida what to try. One thought was could there be a way to put the distance comparison into the JOIN? Nothing else comes to mind so far...

Thanks for any suggestions!