シンプルなソート

ソートするカラムにインデックスをはりまます。
インデックスは既にソートされているので、単純に取り出すだけなら高速にとれます。

// index追加
ALTER TABLE sampleTable ADD INDEX (sampleColumn);

// indexソート済みのカラムでソート
SELECT * FROM sampleTable ORDER BY sampleColumn LIMIT 10;

WHERE句とORDER BY句で別カラムに条件を当てたソート

WHERE句とORDER BY句で別々のインデックスを指定する場合は複合インデックスを使いましょう。

// index追加
ALTER TABLE sampleTable ADD INDEX (sampleColumn1, sampleColumn2);

// indexソート済みのカラムでソート
SELECT * FROM sampleTable where sampleColumn1 = 1234 ORDER BY sampleColumn2 LIMIT 10;

ORDER BY句で複数カラムに条件を当てたソート

SELECT * FROM t1 ORDER BY col2,col1;

しかしこの時、クエリでのカラムの指定順と複合インデックスの指定順は合わせる必要があります。
Mysqlではバージョンによりますが、ASCとDESCが混合している状態ではインデックスが使用されないです。

デフォルトではASCが使われるので、DESCを指定する際は全てのカラムにDESCを明記する。

SELECT * FROM t1 ORDER BY col2 DESC, col1 DESC;

インデックスを極力増やしたくない場合

USE INDEXを使うことでオプティマイザにインデックスを使わせることが出来る。

ALTER TABLE t1 ADD INDEX (col2);
SELECT * FROM t1 USE INDEX (col2) WHERE col1 = 123 ORDER BY col2 LIMIT 10;

参考:https://use-the-index-luke.com/ja/sql/sorting-grouping/order-by-asc-desc-nulls-last
参考:http://download.nust.na/pub6/mysql/doc/refman/5.1-olh/ja/index-hints.html