I have a complex database schema. I built a big query in MySQL 5.6 which joins 20 tables. When I run the query on a local copy of MySQL 5.6 on my Mac I am getting 1-2 millisecond response times. When I run the same query (with the same data via a mysql dump) on MySQL 5.5 on Ubuntu I am getting 60 second response times. I ran profiling on the slow query and discovered that almost the full 60 seconds is being spent in the 'statistics' stage. The 'statistics' stage is apparently where MySQL is determining how best to perform all the joins.
How can MySQL 5.6 perform this in milliseconds and in 5.5 it is taking a full minute?
Any ideas as to what to address first?