I am running two very similar update queries but for a reason unknown to me they are using completely different execution plans. Normally this wouldn't be a problem but they are both updating exactly the same amount of rows but one is using an execution plan that is far inferior to the other, 4 secs vs 2 mins, when scaled up this is causing me a massive problem.

The only difference between the two queries is one is using the column CLI and the other DLI. These columns are exactly the same datatype, and are both indexed exactly the same, but for the DLI query execution plan, the index is not used.

Any help as to why this is happening is much appreciated.

-- Query 1
UPDATE a
 SET DestKey = ( 
 SELECT TOP 1 b.PrefixKey 
 FROM refPrefixDetail AS b 
 WHERE a.DLI LIKE b.Prefix + '%' 
 ORDER BY len(b.Prefix) DESC )
FROM CallData AS a

-- Query 2
UPDATE a
 SET DestKey = ( 
 SELECT TOP 1 b.PrefixKey 
 FROM refPrefixDetail b 
 WHERE a.CLI LIKE b.Prefix + '%' 
 ORDER BY len(b.Prefix) DESC )
FROM CallData AS a