How to decrease pagination query time when dealing with 2 million + records

[Niheel]

We have a table with 2 million plus records and we need to paginate through it at 100 records at a time.

What is the best way to approach this while keeping server load and overhead cost down?

Looking for any solution:
different query types
caching
mysql settings
hardware recommendations
indexing

[mwasif]

1. Are you using this type of query to count total number of records?
[CODE=php]$query = "SELECT * FROM table WHERE col1='something '";
..
..
echo mysql_num_rows( $rs);[/CODE]
If so, then please don't use mysql_num_rows( ).

2. Are the columns properly indexes that you are using in COUNT query?

3. Use caching for COUNT query. memcache can play and vital role.

Can you share the query that you are using to count no of records?