This query was working fine when the database was small, but now that there are millions of rows in the database, I am realizing I should have looked at optimizing this earlier. It is looking at over 600,000 rows and is Using where; Using temporary; Using filesort (which leads to an execution time of 5-10 seconds). It is using an index on the field 'battle_type.'

SELECT username, SUM( outcome ) AS wins, COUNT( * ) - SUM( outcome ) AS losses
FROM tblBattleHistory
WHERE battle_type =  '0' && outcome <  '2'
GROUP BY username
ORDER BY wins DESC , losses ASC , username ASC 
LIMIT 0 , 50