Why am I getting filesort on this really simple MySQL query?

Question

Table has two columns:

CREATE TABLE items ( 
    k INT auto_increment PRIMARY KEY, 
    val INT UNSIGNED
) ENGINE=MyISAM;

I put four items in the table:

INSERT INTO items (val) VALUES (12),(23),(45),(56);

Now if I do:

EXPLAIN SELECT * FROM items ORDER BY k;

I get the dreaded "using filesort". What's going on? According to this page, it should be using the index for the ordering. Am I doing something wrong?

Tested on MySQL 5.0.41 on XP and 5.0.67 on ubuntu.

UPDATE: I added 1,110,000 rows to the table, I added a VARCHAR column and filled it with text. The table size is now 135MB, and I'm still getting "using filesort".

1. Anyone has any tips as to how to add lots of rows quickly?
2. At what point should I consider a table "large enough" for query optimization testing?

Answer 1

Well maybe, just maybe, it's smart enough to figure out that the entire table can fit in one block and it doesn't bother to read the index. It's probably faster to read the whole table into memory and sort it (if that's even necessary - there's a good chance it's already sorted by key within the block).

Try it with a bigger table.

Answer 2

You can force it using:

EXPLAIN SELECT k, val FROM items FORCE INDEX(PRIMARY) ORDER BY k

I think it may be a MyISAM issue relating to index sizes etc.

If you create the same table as InnoDB and run the original order it works fine using the PRIMARY index.