MySQL paging analysis principle and efficiency improvement

MySQL paging analysis principle and efficiency improvement

At PERCONA PERFORMANCE CONFERENCE 2009, several engineers from Yahoo gave a report titled "Efficient Pagination Using MySQL" which had many highlights. This article is a further extension of the original report.

First, let's look at the basic principles of paging:

MySQL> explain SELECT * FROM message ORDER BY id DESC LIMIT 10000, 20\G
***************** 1. row **************
id: 1
select_type: SIMPLE
table: message
type: index
possible_keys: NULL
key: PRIMARY
key_len: 4
ref: NULL
rows: 10020
Extra:
1 row in set (0.00 sec)

limit 10000,20 means to scan 10020 rows that meet the conditions, discard the first 10000 rows, and return the last 20 rows. The problem lies here. If limit 100000,100 is used, 100100 rows need to be scanned. In a highly concurrent application, each query needs to scan more than 100,000 rows, and the performance will definitely be greatly reduced. The article also mentions that limit n performance is not a problem because only n rows are scanned.

The article mentions a "clue" approach to provide some "clues" for page turning. For example, SELECT * FROM message ORDER BY id DESC, pagination in descending order by id, 20 items per page, the current page is the 10th page, the largest id of the current page entry is 9527, and the smallest is 9500. If we only provide jumps such as "previous page" and "next page" (no jump to page N), then when processing the "previous page" SQL statement can be:

SELECT * FROM message WHERE id > 9527 ORDER BY id ASC LIMIT 20;

When processing the "next page", the SQL statement can be:

SELECT * FROM message WHERE id < 9500 ORDER BY id DESC LIMIT 20;

No matter how many pages are turned, only 20 rows are scanned for each query.

The disadvantage is that it can only provide links in the form of "Previous Page" and "Next Page", but our product manager likes links like "<Previous Page 1 2 3 4 5 6 7 8 9 Next Page>" very much. What should we do?

If LIMIT m,n is unavoidable, the only way to optimize efficiency is to make m as small as possible. We extend the previous "clue" approach and still use SELECT * FROM message ORDER BY id DESC, paginating in descending order by id, with 20 items per page. The current page is the 10th page, and the largest id of the current page entry is 9527, and the smallest is 9500. For example, if you want to jump to page 8, the SQL statement I have seen can be written as follows:

SELECT * FROM message WHERE id > 9527 ORDER BY id ASC LIMIT 20,20;

Jump to page 13:

SELECT * FROM message WHERE id < 9500 ORDER BY id DESC LIMIT 40,20;

The principle is still the same. Record the maximum and minimum values ​​of the current page id, and calculate the relative offset between the jump page and the current page. Since the pages are close, the offset will not be large, so the m value is relatively small, which greatly reduces the number of rows scanned. In fact, the traditional limit m,n, the relative offset is always the first page. In this case, the efficiency decreases as you turn to the back. The method given above does not have such a problem.

Pay attention to ASC and DESC in the SQL statement. If the result is retrieved by ASC, remember to invert it when displaying it.

It has been tested in a table with a total of 600,000 data points, and the effect is very obvious.

Thank you for reading, I hope it can help you, thank you for your support of this site!