In general, when you want to make a slow SELECT ...
        WHERE query faster, the first thing to check is
        whether you can add an index. All references between different
        tables should usually be done with indexes. You can use the
        EXPLAIN statement to determine
        which indexes are used for a
        SELECT. See
        Section 7.2.1, “Optimizing Queries with EXPLAIN”, and
        Section 7.4.4, “How MySQL Uses Indexes”.
      
        Some general tips for speeding up queries on
        MyISAM tables:
      
            To help MySQL better optimize queries, use
            ANALYZE TABLE or run
            myisamchk --analyze on a table after it
            has been loaded with data. This updates a value for each
            index part that indicates the average number of rows that
            have the same value. (For unique indexes, this is always 1.)
            MySQL uses this to decide which index to choose when you
            join two tables based on a nonconstant expression. You can
            check the result from the table analysis by using
            SHOW INDEX FROM
             and examining
            the tbl_nameCardinality value. myisamchk
            --description --verbose shows index distribution
            information.
          
To sort an index and data according to an index, use myisamchk --sort-index --sort-records=1 (assuming that you want to sort on index 1). This is a good way to make queries faster if you have a unique index from which you want to read all rows in order according to the index. The first time you sort a large table this way, it may take a long time.

User Comments
If you need to fetch a small number of rows from a table with 10s of millions of rows, LIMIT offset, n_rows will become increasingly slow as offset increases.
A way around this is to have a unique index that numbers the rows, and base your offset on that index. Example:
SELECT * FROM very_long_table WHERE id > 20000000 LIMIT 20;
is MUCH faster than
SELECT * FROM very_long_table LIMIT 20000000, 20;
SELECT * FROM very_long_table WHERE id > 20000000 LIMIT 20;
is MUCH faster than
SELECT * FROM very_long_table LIMIT 20000000, 20;
But it`s not the same thing ...
Add your own comment.