Looks like a "Optimizer injected sort" issue
Here is a representative query:
SELECT d.col1 FROM #Temp AS d INNER JOIN configtable AS c ON parameterName = 'Name' INNER JOIN AuditTable AS at ON at.databaseID = c.ParameterValue AND at.col1 = d.col1 LEFT OUTER JOIN multiValueTable as mvt on mvt.databaseID = c.parameterValue AND mvt.col1 = d.col1 INNER JOIN StatusTable AS st on st.databaseID = d.databaseID AND st.col1 = COALESCE(at.col2, mvt.col2) AND st.col2 = 'XXX' WHERE COALESCE(at.col3, mvt.col3) IS NOT NULL
This query can take up to 12 hours to run. Any hints?
It would be easier to answer more definitively if the actual plan un-anomilised was provided. As we've not got that I'll tell you what I'd begin looking for, this of course can change as you go on but it'll give you a start.
The merge join (right outer join) is getting data from the top clustered index scan on table 3 and from the path below. The sort operation at 41.3% is using two columns, one from table1 and one from table 5. These are already sorted by operations later down the path.
In order to affect the sort in question you'd need to get the data in the correct order by another method, which as you mention, can be by having it in the correct order already by using indexes. As the lower section of this is a little more complex that the upper I'd suggest beginning by seeing if you can add an index to Table3, this would remove the clustered index scan and replace it with an index operation, assuming you can alter the order this data is provided, to match that of the path below, you may be good to stop there. However, table 1 is having a table scan done so that would probably benefit from an index, sorting the data in the order to match that required for the joins.
Finally, looking at the query, I expect the WHERE clause may be better written something like this (not tested) – I think I may start with this to see what affect it has on the estimated plan.
WHERE at.col3 is not null
(at.col3 is null and mv.col3 is not null)
Remember altering the order of the data within indexes can have an affect on other queries so should be carefully tested.
All this is just theoretical and I may well be wrong about parts of it so please use it as a start and possibly to rule out methods of optimizing this one rather than the exact process that must be followed.