The Optimizer model makes several assumptions when making plan choice decisions. These decisions can be false for particular queries and data sets, and sometimes this can cause plan issues. One such problem is called “The Sorted Seek Problem” by the Optimizer Team, and it affects plan selection, usually between clustered index or heap scan plans and bookmark lookup plans.
When costing a series of bookmark lookup operations (for a heap) or index seek operations (for an index), the costing code will effectively treat these as a series of random I/Os. These are much more expensive than sequential I/Os because the disk arm needs to be moved and the disk needs to spin around to find the right sector(s). When the correct page is found, it is loaded into the buffer pool and the engine will cache it for future references. The costing code also understands, on average, how often a page is likely to be found on subsequent operations in the cache, and it costs these accesses much more cheaply than the original access.