[mewpmewp2]

If it's hitting an index properly it should perform binary search on it, and just be able to locate the row, correct?

They also say "We had a very large table (28 million) rows that we were getting timeouts querying on anything other than the primary key."

Which implies that indexing did work if that was primary key. How could other indexes fail? They should work with similar performance. Doesn't that imply they must've done something wrong or there was some sort of bug somewhere? Or were the column in some fashion I can't think of?