Simple query optimization (WHERE + ORDER + LIMIT)

Question

I have this query that runs unbelievably slow (4 minutes):

SELECT * FROM `ad` WHERE `ad`.`user_id` = USER_ID ORDER BY `ad`.`id` desc LIMIT 20;

Ad table has approximately 10 million rows.

SELECT COUNT(*) FROM `ad` WHERE `ad`.`user_id` = USER_ID;

Returns 10k rows.

Table has following indexes:

  PRIMARY KEY (`id`),
  KEY `idx_user_id` (`user_id`,`status`,`sorttime`),

EXPLAIN gives this:

           id: 1
  select_type: SIMPLE
        table: ad
         type: index
possible_keys: idx_user_id
          key: PRIMARY
      key_len: 4
          ref: NULL
         rows: 4249
        Extra: Using where

I am failing to understand why does it take so long? Also this query is generated by ORM (pagination) so it would be nice to optimize it from outside (maybe add some extra index).

BTW this query works fast:

select aa.*
from (select id from ad where user_id=USER_ID order by id desc limit 20) as a
join ad as aa on a.id = aa.id ;

Edit: I tried another user with much less rows (dozens) than original one. I am wondering why doesn't original query use idx_user_id:

EXPLAIN SELECT * FROM `ad` WHERE `ad`.`user_id` = ANOTHER_ID ORDER BY `ad`.`id` desc LIMIT 20;

           id: 1
  select_type: SIMPLE
        table: ad
         type: ref
possible_keys: idx_user_id
          **key: idx_user_id**
      key_len: 3
          ref: const
         rows: 84
        Extra: Using where; Using filesort

Edit2: with help of Alexander I decided to try force MySQL to use the index I want, and following query is much faster (1 sec instead of 4 mins):

SELECT * 
FROM `ad` USE INDEX (idx_user_id)
WHERE `ad`.`user_id` = 1884774
ORDER BY `ad`.`id` desc LIMIT 20; 

Answer 1

In the EXPLAIN output you can see that the key value is PRIMARY. This means that MySQL optimizer decided that it is faster to scan all table records (which are already sorted by id) and search first 20 records with the specific user_id value than to use idx_user_id key, which was considered by optimizer as a possible key and then rejected.

In your second query the optimizer sees that only id values are necessary in the subquery, and decided to use idx_user_id index instead, as that index allows to calculate the list of necessary ids without touching the table itself. Then only 20 records are retrieved by direct search by primary key value, which is very fast operation for that small number of records.

As you query with ANOTHER_ID shows, the MySQL wrong decision was based on the number of rows for the previous USER_ID value. This number was so big that the optimizer guessed that it will find the first 20 records with this specific user_id faster just by looking at the table records itself and skipping records with wrong user_id values.

If table rows are accessed by index, it requires random access operations. For typical HDD random access operations are about 100 time slower then sequential scan. So in order for index to be useful it must reduce the count of rows to less then 1% of the total rows count. If the rows for the specific USER_ID value accounts for more than 1% of the total number of rows, it may be more efficient to do full table scan instead of using of index, if we want to retrieve all these rows. But MySQL optimizer doesn't takes into account the fact that only 20 of this rows will be retrieved. So it mistakenly decided not to use index and do full table scan instead.

In order to make your query fast for any user_id value you can add one more index which will allow the query execution in the fastest way possible:

create index idx_user_id_2 on ad(user_id, id);

This index allows MySQL to do both filtering and sorting. To do that the columns used for filtering should be placed first, and the columns used for ordering should be placed second. MySQL should be smart enough to use that index, because this index allows to search all necessary records without skipping any records.