Hmm.. looking closer at the slow-queries.log -- I believe this may be a problem with the join syntax, not the indexes.
Here's what the log shows:
# Time: 110224 22:32:56
# User@Host: me[me] @ localhost [127.0.0.1]
# Query_time: 168 Lock_time: 0 Rows_sent: 1036 Rows_examined: 72105167
SELECT * FROM territory_borders_finished, territories_finished where tb_game_number=378664 and te_game_number=378664 and tb_border = te_code ORDER BY tb_territory;
Now .. notice the query time is 168 seconds, and notice the Rows_examined is 72 million.
Running that same query in the console indeed does take over a minute to complete.
However, if I run the subqueries on each of the tables:
SELECT * FROM territory_borders_finished WHERE tb_game_number = 378664
and
SELECT * FROM territories_finished WHERE te_game_number = 378664
Each of those queries complete in less than 1 second.
So .. what gives? At this point, MySQL just needs to join that data up with each other, sort it, then spit it out .. this should be taking less than 2 seconds.
I can just do two queries, then join it up and sort it in Java at this pace.
Obviously I'm not crafting this join correctly :(