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 | |
+----+-------------+--------+-------+---------------+---------+---------+------+--------+----------+-------+
EXPLAIN– FreshPrinceOfSO Dec 22 '12 at 14:50EXPLAIN, under therowstitle. – ypercube Dec 22 '12 at 15:30O(a), right? – chyx Dec 22 '12 at 15:55LIMIT a, bis the same asLIMIT b OFFSET a, so first the index has to be read sequentially andavalues skipped (assuming thatidis unique), thenbvalues read from the index and thenbrows retrieved from the table. Since this is InnoDB (and again assuming that the clustered index is onid), 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