I've made large joins faster in MySQL by adding gratuitous order by to derived table queries, which lead to probing the index in the join in index order instead of a different, more random, order. The cost of the extra redundant sort was less than the cost of the random btree traversals.