Working on customer case today I ran into interesting problem – query joining about 20 tables (thank you ORM by joining all tables connected with foreign keys just in case) which would take 5 seconds even though in the read less than 1000 rows and doing it completely in memory. The plan optimizer picked was very good one, yet you could notice EXPLAIN itself was taking same 5 seconds, which points to problem with optimizer performance. Note though if you have subqueries these might need to be executed during EXPLAIN phase yet making it unusable to check the optimizer performance.

Solution for this problem was to use set optimizer_search_depth=0, rarely used option which as per manual will chose best value automatically. Making this change I could bring optimization, and full query execution time to less than 50ms. Low values, such as 3,4 provided a bit better performance but I decided against using this as I did not want to risk likehood of execution plans changing for some over queries joining less number of tables.

I was wondering if 0 is automatic selection why do we have value of 62 being default in MySQL 5.5 which can produce very expensive plan selections ? Investigating this further I found the following explanation from Timour Katchaounov in MySQL mailing list archives

I have some recollection that there were few main reasons for the
decision to keep exhaustive search as the default:
- backwards compatibility,
- the hypothesis that most users have joins with few tables,
- it is not clear how far from optimal plans do we get by using a greedy
search.

From the same discussion we can learn how automatic selection works – it picks value of min(number of tables, 7) essentially limiting search depth to no more than 7 at which complexity is reasonable. This makes Timour explanation somewhat conflicting though as if we assume MySQL users do not join lots of tables (less than 7) when using 0 as default value would not impact them.
For people who have more than 7 tables in join I think faster execution plan computation would be more important than backward compatibility.

In MySQL 5.6 things are likely to get even better handling joins of many tables as optimizer heuristics are improved so much higher search depths are feasible now.