On one of my projects, I cam across a certain performance edge case on a site with a large volume of data. For whatever reason, the MySQL optimizer refused to use the fastest index in a handful of views queries, causing these queries to be painfully slow.
Here is a simplified example of a query generated by views:
SELECT nid, title FROM node WHERE status <> 0 AND type IN ("story") ORDER BY created DESC;
When viewing the explain plan for this query, it shows my that MySQL is choosing to use the node_type index instead of node_created.