Hash Match in Query has high cost and high number of excecutions I have the following query:

      declare @jobID NVARCHAR(20)
    declare @dataGroup BIGINT
    declare @lastSyncVer BIGINT

       set @jobid='P-0001'
       set @dataGroup= 5637144576
       set @lastSyncVer = 316244734

SELECT us.[DATASTOREID], us.[UPLOADSESSIONID], us.[UPLOADPATH], us.[STATUS], us.[DATEUPLOADED], us.[DATECREATED], us.[CHECKSUM], us.[FILESIZE], us.[ID], us.[RERUNFOR]
        FROM [dbo].[UPLOADSESSION] us
            INNER JOIN CHANGETABLE(CHANGES [dbo].[UPLOADSESSION], @lastSyncVer) AS CT ON us.[ID] = CT.[ID]
            INNER JOIN [dbo].[DATASTORE] ds ON us.[DATASTOREID] = ds.[ID]
            INNER JOIN [dbo].[DATAGROUP] dg ON ds.[DATAGROUPID] = dg.[ID]
        WHERE dg.[ID] = @dataGroup
          AND us.[JOBID] = @jobID
                AND us.[RERUN] = 0
        ORDER BY us.[ID]


When I run a query cost analyze of the query I see that the Hash Match takes up 83% of the cost. I also see that the hash match has a really high number of executions(over 800k). The main problem with the query is that it is very slow. I have let it run for over 40 minutes, and it still didn't finish. The query is written by Microsoft, and is part of their functionally in their ERP system Microsoft Dynamics AX. Can anyone come up with some ideas how we can speed things up? This query used to take under 30 seconds. 

Perhaps the problem isn't in the query itself, but in other problems with the DB? I have tried updating stats.
If it used to run in 30 seconds, that means that something changed: you have to identify what that something is and fix it.

That something is most probably the query execution plan. There must be a better execution plan than the one that you're getting now, but the optimizer doesn't feel like giving you that plan any more. The reason can be only one: outdated statistics. 

Statistics become stale when you modify data in your tables and from time to time you need to update them. SQL Server will try to update statistics automatically when the number of changed rows exceeds a threshold that can be either static (20%) or adaptive (needs TF 2371 turned on). Either way, it's impossible to control the number of rows that SQL Server will scan to compile the statistics. This is particularly problematic when the distribution of the data is not uniform and you have skewed data. In that case, you'd better disable auto update statistics for the particular table/index and make sure that you update your statistics manually with FULLSCAN.

Another possible reason for getting an inefficient plan is parameter sniffing, but the reasoning behind is the same: your plan gets compiled for a non representative set of parameters, that determine  a performance nightmare when the plan is compiled for a more representative set of parameters. In this case, OPTIMIZE FOR hints might help, but usually fixing the stats is a better idea.

That said, if it used to run in 30 seconds you might still have the efficient plan lying around somewhere in the cache: try to find it in sys.dm_exec_cached_plans and compare it with the plan that you are getting now.