Must an index cover all selected columns for it to be used for ORDER BY?

Question

Over at SO, someone recently asked Why isn't ORDER BY using the index?

The situation involved a simple InnoDB table in MySQL comprising three columns and 10k rows. One of the columns, an integer, was indexed—and the OP sought to retrieve his entire table sorted on that column:

SELECT * FROM person ORDER BY age

He attached EXPLAIN output showing that this query was resolved with a filesort (rather than the index) and asked why that would be.

Despite the hint FORCE INDEX FOR ORDER BY (age) causing the index to be used, someone answered (with supporting comments/upvotes from others) that an index is only used for sorting when the selected columns are all read from the index (i.e. as would normally be indicated by Using index in the Extra column of EXPLAIN output). An explanation was later given that traversing the index and then fetching columns from the table results in random I/O, which MySQL views as more expensive than a filesort.

This appears to fly in the face of the manual chapter on ORDER BY Optimization, which not only conveys the strong impression that satisfying ORDER BY from an index is preferable to performing additional sorting (indeed, filesort is a combination of quicksort and mergesort and therefore must have a lower bound of Ω(nlog n); whilst walking through the index in order and seeking into the table ought to be O(n)—so this makes perfect sense), but it also neglects to mention this alleged "optimisation" whilst also stating:

The following queries use the index to resolve the ORDER BY part:

SELECT * FROM t1
  ORDER BY key_part1,key_part2,... ;

To my reading, that is precisely the case in this situation (yet the index was not being used without an explicit hint).

My questions are:

• Is it indeed necessary for all selected columns to be indexed in order for MySQL to choose to use the index?

  • If so, where is this documented (if at all)?

  • If not, what was going on here?