ORDER BY optimization issue I have a query:

SELECT  
  user_details.id , user_details.first_name , user_details.last_name,
  user_accounts.name account_name, jtl0.account_id account_id, 
  user_details.title , user_details.job_function , 
  user_details.contact_data_status , user_details.assigned_user_id   
FROM user_details   
LEFT JOIN  user_accounts_user_details jtl0 
  ON user_details.id=jtl0.contact_id AND jtl0.deleted=0 
LEFT JOIN  user_accounts user_accounts 
  ON user_accounts.id=jtl0.account_id AND user_accounts.deleted=0 
where user_details.deleted=0 
ORDER BY account_name ASC LIMIT 0,21;


Without the ORDER BY / LIMIT, the query returns immediately, but when I add ORDER BY account_name ASC to this takes 5 minutes. I have tried several combinations of indexes on user_accounts but have no success.

Here is the EXPLAIN result of the query:

+----+-------------+----------+--------+--------------------------------------------------------------+-----------------------+---------+-------------------------------+---------+----------------------------------------------+
| id | select_type | table    | type   | possible_keys                                                | key                   | key_len | ref                           | rows    | Extra                                        |
+----+-------------+----------+--------+--------------------------------------------------------------+-----------------------+---------+-------------------------------+---------+----------------------------------------------+
|  1 | SIMPLE      | user_details | ref    | idx_contacts_del_last,idx_cont_del_reports,idx_del_id_user   | idx_contacts_del_last | 2       | const                         | 1554822 | Using where; Using temporary; Using filesort |
|  1 | SIMPLE      | jtl0     | ref    | idx_contid_del_accid                                         | idx_contid_del_accid  | 113     | salesify_db.contacts.id,const |       1 | Using index                                  |
|  1 | SIMPLE      | user_accounts | eq_ref | PRIMARY,idx_accnt_id_del,idx_accnt_assigned_del,idx_oss_name | PRIMARY               | 108     | salesify_db.jtl0.account_id   |       1 |                                              |
+----+-------------+----------+--------+--------------------------------------------------------------+-----------------------+---------+-------------------------------+---------+----------------------------------------------+


No of records in user_accounts : around 3000000
No of records in user_details : around 3400000
No of records in user_accounts_user_details : around 2500000


Index in user_accounts 

PRIMARY KEY (`id`),
  KEY `idx_accnt_id_del` (`id`,`deleted`),
  KEY `idx_accnt_name_del` (`name`,`deleted`),
  KEY `idx_accnt_assigned_del` (`deleted`,`assigned_user_id`),
  KEY `idx_accnt_parent_id` (`parent_id`),
  KEY `idx_oss_name` (`id`,`name`(15))
) ENGINE=InnoDB DEFAULT CHARSET=utf8


Index in user_details 

PRIMARY KEY (`id`),
  KEY `idx_cont_last_first` (`last_name`,`first_name`,`deleted`),
  KEY `idx_contacts_del_last` (`deleted`,`last_name`),
  KEY `idx_cont_del_reports` (`deleted`,`reports_to_id`,`last_name`),
  KEY `idx_reports_to_id` (`reports_to_id`),
  KEY `idx_del_id_user` (`deleted`,`id`,`assigned_user_id`),
  KEY `idx_cont_assigned` (`assigned_user_id`),
  KEY `primary_address_idx` (`primary_address_country`),
  KEY `idx_oss_dt` (`date_entered`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8


Index in user_accounts_user_details 

  PRIMARY KEY (`id`),
  KEY `idx_account_contact` (`account_id`,`contact_id`),
  KEY `idx_contid_del_accid` (`contact_id`,`deleted`,`account_id`)
Normally you want to throw away as many rows as you can, as quickly as you can.  That doesn't seem likely here, unfortunately.

All you have is 'deleted = 0' for each table, so MySQL will pick a table to start with.  In your explain, it picked user_details, resulting in 1.5M rows being used.

Do the other tables have fewer active rows?  If so, you'd want to start with that table instead.

Once it picks a table, it will join across.  If we're starting with user_details, you're off to user_accounts_user_details, so you'll want an index on user_details(deleted, id) so the ids can be found via the index.

Since you're coming into user_accounts_user_details with the contact_id, you'll want to start your index with that.  We know that deleted=0 there, too, so add that.  And, once again, you'll want the id for the next table in your index.  I think that means user_account_user_details(contact_id, deleted, account_id).

We'll take that account_id over to user_accounts, so we'll need an index there.  We still have deleted=0, and we're not continuing on to other tables, so try user_accounts(id, deleted).

Depending on the quantity and size of the columns you're SELECTing from each table, you can add them at the end of the indexes, which can keep MySQL from having to read the underlying row from disk.  In your case, it looks like you're SELECTing a good number of long columns, which I wouldn't add to the composite indexes described above.  I might be tempted to include user_accounts.name, since you use that in the ORDER BY clause.

I hope that helps.

If possible find some other way to reduce the number of rows more quickly.  Can you limit by date, or something else?  Starting with 10 records in the first table would be so much better than starting with 1M.

Good luck.