mysql 5.5 bad query plan

[TABLE]
[TR]
[TD=“class: votecell”] [CENTER]0down votefavorite [/CENTER]
[/TD]
[TD=“class: postcell”]I am using mysql 5.5 with innodb. I ran into an issue where one particular query suddenly started using sub optimal query plan. Prior to this, the query was working fine with a response time of 1 second or so. But suddenly mysql started using a different query plan with a different index which was least selective resulting in a response time of 200+ secs. Can somebody explain why this would happen? When I ran the same query with an index hint of the correct index, all the subsequent runs of the query started using the new query plan.
Can somebody please provide some explanation to the root cause of this issue? One possible thing I can think of is the table statistics would be out of date but I don’t think the underlying table data changed so drastically that it would completely change the query plan and use a new index
[/TD]
[/TR]
[/TABLE]