MySQL Index Usage – Why MySQL Fails to Use Index Effectively with Large LIMIT Offset

indexmyisammysql-5select

I do not understand when querying 5 rows from a table of 500,000 rows, the following query takes 0.00sec:

SELECT id, username FROM Users FORCE INDEX (PRIMARY) ORDER BY id LIMIT 20,5;

But querying the exact same rows in the reverse takes 2.50sec:

SELECT id, username FROM Users FORCE INDEX (PRIMARY) ORDER BY id DESC LIMIT 499975,5;

Furthermore, if I don't force index for the second query, MySQL will choose not to use it.

I note that there is a plan to introduce sort order for index, but that does not explain why MySQL cannot use the same index effectively when LIMIT offset is large since it knows the total row count.

Best Answer

Yes, the large offset is a problem. MySQL does early row lookups, which do not allow throwing data away as easy as one imagines. MySQL retrieves the whole records as it processes the database and each record may be of variable length. Throwing rows away afterwards becomes as cumbersome as throwing each single row away. It's not like "throw away x*y bytes".

There are tricks to force MySQL into late row lookup, which means process the index and do all operations concerning that, than retrieve the row. This offers the possibility to throw rows away much faster.

See

Notice another contrast

The table count is 4636881
The EXPLAIN plan for the first query traversed 4000010 indexed_column keys. No need to read the last 636871 keys.
The EXPLAIN plan for the second query traversed 4636881 rows ordered by indexed_column. For every row picking up the non-indexed column out of the table, the indexed column (already sorted by the index) is looked up and comes along for the ride. The tmp table gets ordered by the indexed column, and mysqld then dismisses the first 4000000 rows, leaving 10 rows. All that interaction between table and index just for 10 rows is the bottleneck.

COMMON THINGS

In both instances, the query specfies the number of rows to traverse. Since the number of rows in the table is 4636881, we should readily expect a full scan. The contrast becomes apparent when the MySQL Query Optimizer decides where to perform the full scan.

The first query is referencing an indexed column only in the SELECT list and the WHERE clause. The MySQL Query Optimizer chooses to perform a full index scan with no need to contact the table since everything needed is in the index.
The second query is referencing an indexed column in the WHERE clause. However, it must reach out the table to retrieve the corresponding non-indexed column. The MySQL Query Optmizer was tipped off by the query that it must not use the index becasue of the number of rows it was expected to read. As a rule of thumb for any RDBMS, if more than 5% of a table has to be read to fulfill a query, the MySQL Query Optimizer will just throw the index 'under the bus' and do a full table scan.

Doing the math, here is what MySQL Query optimizer computes:

5% of 4636881 is 231844
The second query is commanded to read 4000000 rows, which is way higher than 231844
MySQL Query Optimizer realizes there would be too much interaction between table (because of the non-indexed column) and index (because of the indexed column) to get the needed data. It decides to read the table only (because both the indexed and non-indexed columns are residing together in the table) rather than bounce back and forth between them.

In my honest opinion, with the row count of the table, the present indexes the table has, and the number of rows prescribed by the query, the MySQL Query Optimizer made the correct decision.

RECOMMENDATION

Create this index

ALTER TABLE `table` ADD INDEX mynewndx (indexed_column,some_other_column);

and your second query will never touch the table again going forward. The MySQL Query Optimizer will behave quite differently when it sees this new index.

MySQL – Using Primary Index Without Hinting or Forcing

Here is a suggestion for a rewrite. Perhaps your ORM can be convinced to produce this query. It's only slightly different from the original. The only change is a derived table instead of the base table star. As the tables have foreign keys defined and the query starting from star, follows the foreign keys, the result will be the same:

SELECT *
  FROM 
      ( SELECT * FROM star ORDER BY id DESC LIMIT 10 )                -- the only change
      AS star  
  INNER JOIN `question` ON (`star`.`question_id` = `question`.`id`)
  INNER JOIN `level` ON (`question`.`level_id` = `level`.`id`)
  INNER JOIN `video` ON (`question`.`video_id` = `video`.`id`)
  INNER JOIN `user` ON (`star`.`user_id` = `user`.`id`)
  ORDER BY  `star`.`id` DESC 
LIMIT 10 ;

Another idea would be to keep your query but change all the INNER joins to LEFT joins. This might produce a different plan that utilizes the primary key of star. And because of the foreign keys, we are again sure that the query is equivalent and will produce the same results.

Not entirely relevant to efficiency:

SELECT * should not be used. Add only the list of the columns you need, not all the columns of all the tables involved. How are you going to identify anyway in the results whether the id column comes from star.id or from question.id or from ...?

Best Answer

Related Solutions

Mysql – Why does MySQL choose this execution plan

Notice another contrast

COMMON THINGS

RECOMMENDATION

MySQL – Using Primary Index Without Hinting or Forcing

Related Question