Mysql – Query Performance Regression Between Different Versions

I have two MySQL databases, A and B. They have identical hardware and schema. They have different data and database A has more data then B. Database A is also running version 5.1, while B is on 5.5. The tables involved are fairly large.

I am running a query on both:

SELECT atr.id as id, count(*) as ticket_count 
FROM cba_ticket t
JOIN cba_ticket_custsvc tcs ON t.id = tcs.ticket_id 
JOIN cba_delivered_address da ON tcs.route_address_id = da.route_address_id 
JOIN cba_assignment_truck_run atr ON da.assignment_truck_run_id = atr.id 
JOIN cba_assignment a ON a.id = atr.assignment_id                   
WHERE atr.id IN (...) 
AND t.created_at BETWEEN DATE_SUB(a.start_date, INTERVAL 28 DAY) AND DATE_ADD(a.start_date, INTERVAL 7 DAY) 
AND atr.truck_run_type = 0 
AND tcs.is_invalid = false 
AND t.ticket_type = 1
GROUP BY atr.id;

Where … is a comma delimited list of numbers.

In database A, the query comes back in ~1.5 seconds. Database B takes at least 5 minutes. I haven't let it finish yet.

When I run EXPLAIN for the query in database A:

+----+-------------+-------+--------+----------------------------------------------+-------------------------+---------+-------------------------+------+----------+-------------+
| id | select_type | table | type   | possible_keys                                | key                     | key_len | ref                     | rows | filtered | Extra       |
+----+-------------+-------+--------+----------------------------------------------+-------------------------+---------+-------------------------+------+----------+-------------+
|  1 | SIMPLE      | atr   | range  | PRIMARY,assignment_id_idx,truck_run_type     | PRIMARY                 | 8       | NULL                    |  750 |    75.07 | Using where |
|  1 | SIMPLE      | a     | eq_ref | PRIMARY                                      | PRIMARY                 | 8       | cba.atr.assignment_id   |    1 |   100.00 |             |
|  1 | SIMPLE      | da    | ref    | route_address_id_idx,assignment_truck_run_id | assignment_truck_run_id | 8       | cba.atr.id              |  400 |   100.00 |             |
|  1 | SIMPLE      | tcs   | ref    | ticket_id,route_address_id                   | route_address_id        | 5       | cba.da.route_address_id |    1 |   100.00 | Using where |
|  1 | SIMPLE      | t     | eq_ref | PRIMARY,created_at                           | PRIMARY                 | 4       | cba.tcs.ticket_id       |    1 |   100.00 | Using where |
+----+-------------+-------+--------+----------------------------------------------+-------------------------+---------+-------------------------+------+----------+-------------+

Database B:

+----+-------------+-------+--------+----------------------------------------------+----------------------+---------+--------------------------------+------+----------+----------------------------------------------+
| id | select_type | table | type   | possible_keys                                | key                  | key_len | ref                            | rows | filtered | Extra                                        |
+----+-------------+-------+--------+----------------------------------------------+----------------------+---------+--------------------------------+------+----------+----------------------------------------------+
|  1 | SIMPLE      | tcs   | ALL    | ticket_id,route_address_id                   | NULL                 | NULL    | NULL                           | 9358 |   100.00 | Using where; Using temporary; Using filesort |
|  1 | SIMPLE      | t     | eq_ref | PRIMARY,created_at                           | PRIMARY              | 4       | cba.tcs.ticket_id              |    1 |   100.00 | Using where                                  |
|  1 | SIMPLE      | da    | ref    | route_address_id_idx,assignment_truck_run_id | route_address_id_idx | 9       | cba.tcs.route_address_id       |   54 |   100.00 | Using where                                  |
|  1 | SIMPLE      | atr   | eq_ref | PRIMARY,assignment_id_idx,truck_run_type     | PRIMARY              | 8       | cba.da.assignment_truck_run_id |    1 |   100.00 | Using where                                  |
|  1 | SIMPLE      | a     | eq_ref | PRIMARY                                      | PRIMARY              | 8       | cba.atr.assignment_id          |    1 |   100.00 | Using where                                  |
+----+-------------+-------+--------+----------------------------------------------+----------------------+---------+--------------------------------+------+----------+----------------------------------------------+

Why would the explains be so different? Is it the MySQL version differences(even though the newer one performs worse)? How would I get database B up to speed?