Take the 2-minute tour ×
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.

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.