Eliminate key lookup in execution plan
My question is, why it's still doing key lookup instead of index scan/seek ?


The query specifies that results should be ordered by DateCreated.  Since you already had a nonclustered index on DateCreated, the optimizer decided that the cost of doing key lookups was lower than sorting all of the data by DateCreated.


  Does this mean key lookup was done due to ORDER BY on non-clustered index ?


Essentially, yes.  It was estimated to be cheaper* to read the data in the required order, and get any additional fields through a key lookup, rather than reading all of the fields from a single index and then sorting it by DateCreated.

You could confirm this by comparing the estimated costs between 


the original query (with the original indexes), and 
the original query with an index hint


The index hint would be like this on the FROM line:

FROM [dbo].[Watchdog] WITH (INDEX (LocationId_FirstTrigger))


This should produce a plan with no key lookups (since LocationId_FirstTrigger is covering for that query), and a Sort operator.  I'd expect the "Estimated Cost" to be higher, thus the other plan was chosen.



* To explain the optimizer's choice here:

The TOP (1) in your query means the optimizer sets a row goal, meaning the plan is geared toward producing one row quickly. The optimizer expects to find one row from the Index Scan matching your LocationId predicate very quickly, since it assumes values are distributed uniformly. This may or may not be true in reality. The cost of one Key Lookup following the Index Scan is pretty small.

The scan + lookup option therefore looks cheaper to the optimizer than finding matches using LocationId_FirstTrigger and sorting. You can turn the row goal logic off for the query as a test by adding an OPTION (QUERYTRACEON 4138) hint. You will likely find the optimizer then chooses the LocationId_FirstTrigger index without an index hint.

Still, the best alternative is to modify your index as Mikael Eriksson suggests.