2 similar queries in large sql server table - 1 takes too long I have a huge table in my database that contains distances between cities.  This enables my application to find nearby cities around the world when a starting city is selected.  It contains 4 columns - ID, StartCityID, EndCityID and Distance and contains about 120 million rows.  I've got indexes set up on the startcityID, endcityID, another one for both, and another one each for startcity + distance, and endcity + distance.  (This is my first real dealings with indexes so not 100% sure if I'm doing it correctly).

Anyway - I do the following 2 queries:

Select distinct StartCityID
From Distances where EndCityID = 23485


and 

Select distinct EndCityID 
From Distances where StartCityID = 20045


They both return the same number of cityIDs, but the top one takes 35 seconds to do, and the bottom one returns results immediately.  When I look at the indexes, they seem to be set up to serve startCity and endCity in the same way.  Anyone know why they might be acting differently? I'm at a loss...

NB - this may offer more insight, but the one that takes 35 seconds - if I press execute again straight away with the same ID, it returns results immediately as well that time.  Unfortunately that isn't good enough for my website but it may be useful information.

Thanks
The explain plan (or execution plan) should tell you exactly where the difference lies, and which indexes are being used.

See here for more info on how to get an explain plan.