Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm displaying about 1,000,000 records separated by 10 records per page.

select * from table order by id DESC limit a, b; 

In this query id is indexed, and b is 10.

The querying time is fast when a is small, but the time dramatic increased to about 100s when a is near the end of the table. I wonder what's the time complexity of this query? Is it bounded by O(b) or O(a)?

(I use the Innodb engine)

When a = 200000, The Explain said:

+----+-------------+--------+-------+---------------+---------+---------+------+--------+----------+-------+
| id | select_type | table  | type  | possible_keys | key     | key_len | ref  | rows   | filtered | Extra |
+----+-------------+--------+-------+---------------+---------+---------+------+--------+----------+-------+
|  1 | SIMPLE      | status | index | NULL          | PRIMARY | 4       | NULL | 200001 |   653.99 |       |
+----+-------------+--------+-------+---------------+---------+---------+------+--------+----------+-------+
share|improve this question

migrated from stackoverflow.com Dec 22 '12 at 15:25

This question came from our site for professional and enthusiast programmers.

2  
Look at your EXPLAIN – Kermit Dec 22 '12 at 14:50
    
Thanks, I'll try it. – chyx Dec 22 '12 at 15:08
    
Look at your EXPLAIN, under the rows title. – ypercubeᵀᴹ Dec 22 '12 at 15:30
    
So it means the complexity is O(a), right? – chyx Dec 22 '12 at 15:55
    
LIMIT a, b is the same as LIMIT b OFFSET a, so first the index has to be read sequentially and a values skipped (assuming that id is unique), then b values read from the index and then b rows retrieved from the table. Since this is InnoDB (and again assuming that the clustered index is on id), the 2nd operation is skipped and the 3rd is done together on the clustered index (e.g. the table). – ypercubeᵀᴹ Dec 22 '12 at 16:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.