Sql-server – Reducing sort time for querying aspnet_users table in Sql Server

I've recently taken over software development for a small company. My mandate includes managing our SQL stuff, which is something I don't really know much about, and I don't think the guy before me knew much about it either – the whole setup seems to be a bit of a mess.

I'm trying to improve the speed of a complex search of user accounts, which is taking 5-10 seconds, which seems a lot for 750,000 records (apparently, this not considered a big table.)

For some reason, there are two tables which contain user details:

Aspnet_Users
    UserId uniqueidentifier (Primary Key)
    Username nvarchar(256)
    .... (other stuff)

Users
    UserId uniqueidentifier (Primary Key)
    FirstName nvarchar(50)
    Surname nvarchar(50)
    Email nvarchar(256)
    ... (other columns related to our business)

Note that Users.UserId has no relationship to Aspnet_Users.UserId, even though users.userid should probably be a foreign key of aspnet_users.userid. I don't know if this matters.

There are more tables referenced in the search query, but the bulk of the query time seems to be spent on merging the two tables above: 90%.

The generated execution plan looks like this:

Clustered Index Scan [aspnet_Users].[aspnet_users_index] Cost: 13%
|
|
|
V
Sort Cost: 50%
|
|                Clustered Index Scan (Clustered) [Users].[PK_user_details] Cost:23%
|                |
V                V
Merge Join (Inner Join) 4%
|
|
|
V
(Lots more stuff, none of which is very expensive)

As you can see, most of the time is taken up by that sort.

I don't know that much about SQL, so I don't really know how to make go faster. I tried making a View that included most of the tables used in this query, but it didn't seem to help.

For information, here is the full search query. I think that the problems I am having aren't really related to the complexity of this particular query, though.

ALTER PROCEDURE [dbo].[sp_FTSearchLocation] 
     @SearchFor nvarchar(200)
     ,@SearchInLat Decimal(18,15)
     ,@SearchInLng Decimal(18,15)
     ,@SearchActivity int
     ,@StartRow int
     ,@EndRow int
AS
BEGIN
    SET NOCOUNT ON;

    SELECT * FROM (
    SELECT TOP (@EndRow)
        FT_TBL.CompanyName, FT_TBL.Email, FT_TBL.UserId, aspnet_Users.UserName as Handle,
        FT_TBL.ServicePoint1, FT_TBL.ServicePoint2, FT_TBL.ServicePoint3,
        FT_TBL.ServicePoint4, FT_TBL.ServicePoint5, FT_TBL.ServicePoint6,
        Addresses.Building, Addresses.Street, Addresses.City, Addresses.Region,
        Addresses.Postcode, Addresses.Latitude, Addresses.Longitude, Activities.Activity,
        vw_Ratings.Rating, FT_TBL.IsFromPaidBusinessDB,FT_TBL.ActivityID,
        ROW_NUMBER() OVER (ORDER BY vw_Ratings.Rating DESC,
        FT_TBL.CompanyName  ) AS num

    FROM
        Users as FT_TBL INNER JOIN
        aspnet_Users ON FT_TBL.UserId = aspnet_Users.UserId INNER JOIN
        Addresses ON FT_TBL.UserId = Addresses.UserId INNER JOIN
        Activities ON FT_TBL.ActivityID = Activities.ActivityID INNER JOIN
        Country ON Addresses.CountryISO = Country.Iso LEFT OUTER JOIN
        vw_Ratings ON FT_TBL.UserId = vw_Ratings.UserId

    WHERE
        ( -- filter for all queries --
                (FT_TBL.IsActive = 1)
            AND (FT_TBL.IsPro = 1)
        )       
        AND ( -- filter for 'searchfor' --
               (@SearchFor IS NULL)
            OR (FT_TBL.CompanyName like '%' + @SearchFor + '%') 
            OR (aspnet_Users.UserName like '%' + @SearchFor + '%')
            OR (Activities.Activity like '%' + @SearchFor + '%')
        )
        AND ( -- filter for 'searchIn'
                (
                    (@SearchInLat is null)
                    OR (@SearchInLng is null)
                )
                OR (    
                    (Addresses.Latitude IS NOT NULL)
                    AND (Addresses.Longitude IS NOT NULL)
                    AND ( (Addresses.Latitude - @SearchInLat)  BETWEEN -0.5 AND 0.5)
                    AND ( (Addresses.Longitude - @SearchInLng) BETWEEN -0.5 AND 0.5)
                )
            )                       
        AND ( -- filter by activity --
               (@SearchActivity IS NULL)
            OR (@SearchActivity = Activities.ActivityID)
        )

    ORDER BY 
        vw_Ratings.Rating DESC,
        FT_TBL.CompanyName  
    ) As a
    WHERE num > @StartRow

    OPTION (RECOMPILE)

END

Can anyone suggest a way to make this faster?

EDIT: Pastebin of xml wexecution plan