MySQL, order by multiple columns from multiple tables

Question

I have two tables:

Table of Artists (tbl_artist):

artist_id - primary key
artist_name - has index   


Table of Albums (tbl_album):

album_id - primary key
album_artist_id - foreign key, has index
album_name - has index too

Tables have a lot of records on production server (artists - 60k, albums - 250k).

And on index page there is a list of albums, with pagination step = 50. Albums are sorted by artist_name ASC, album_name ASC. So the simplified query is following:

SELECT *
FROM tbl_artist, tbl_album
WHERE album_artist_id = artist_id
ORDER BY artist_name, album_name
LIMIT 0, 50

Query is executing very long. Probably it's because of ordering by columns from different tables. When I leave only 1 ordering - query is executing immediately.

What is possible to do in such situation? Many thanks.

Edit: explain:

+----+-------------+---------------+--------+------------------+---------+---------+-----------------------------------+--------+---------------------------------+
| id | select_type | table         | type   | possible_keys    | key     | key_len | ref                               | rows   | Extra                           |
+----+-------------+---------------+--------+------------------+---------+---------+-----------------------------------+--------+---------------------------------+
|  1 | SIMPLE      | tbl_album     | ALL    | album_artist_id  | NULL    | NULL    | NULL                              | 254613 | Using temporary; Using filesort |
|  1 | SIMPLE      | tbl_artist    | eq_ref | PRIMARY          | PRIMARY | 4       | db.tbl_album.album_artist_id      |      1 |                                 |
+----+-------------+---------------+--------+------------------+---------+---------+-----------------------------------+--------+---------------------------------+

explain with STRAIGHT_JOIN

+----+-------------+---------------+------+-----------------+-----------------+---------+------------------------------------+-------+---------------------------------+
| id | select_type | table         | type | possible_keys   | key             | key_len | ref                                | rows  | Extra                           |
+----+-------------+---------------+------+-----------------+-----------------+---------+------------------------------------+-------+---------------------------------+
|  1 | SIMPLE      | tbl_artist    | ALL  | PRIMARY         | NULL            | NULL    | NULL                               | 57553 | Using temporary; Using filesort |
|  1 | SIMPLE      | tbl_album     | ref  | album_artist_id | album_artist_id | 4       | db.tbl_artist.artist_id            |     5 |                                 |
+----+-------------+---------------+------+-----------------+-----------------+---------+------------------------------------+-------+---------------------------------+

Answer 1

You need an index of (artist_name, artist_id) and then (album_artist_id, album_name). The reason is because your join is between artist_id and album_artist_id, so it has to perform the same join with the indexes to produce a final need index of (artist_name, album_name) for the sort.

You then need to change your order by to be: ORDER BY artist_name, artist_id, album_name. This is because there could be two artist_name's that are the same, and this will cause it to order not as you are expecting. Also it will prevent it from using an index.

Using just indexes on artist_name, and album_name doesn't provide enough information to produce that sort, all you have is an ordered list of names with nothing to indicate how they connect to the other table.

Answer 2

Try changing the index on (album_artist_id) to an index on (album_artist_id, album_name).