True, there are a lot of subtleties in picking the best indexes. I have given some tips here:
http://forums.mysql.com/read.php?24,401240 (11 millions records : more than 30 seconds to retrieve simple request)
http://forums.mysql.com/read.php?24,399387 (Slow query with order by and limit)
http://forums.mysql.com/read.php?10,393815 (Index recomendations)
http://forums.mysql.com/read.php?10,389424 (Need Database Structure Help)
http://forums.mysql.com/read.php?10,390235 (Size of INDEX_LENGTH is higher than DATA_LENGTH !)
http://forums.mysql.com/read.php?10,388263 (CREATE TABLE ignores DATA DIRECTORY option)
http://forums.mysql.com/read.php?22,387385 (Huge row size compared to MyIsam)
http://forums.mysql.com/read.php?21,387250 (Significance of Primary Keys)
http://forums.mysql.com/read.php?10,379454 (Join Statement with math operation)
http://forums.mysql.com/read.php?10,381359 (checking status of CREATE INDEX)
http://forums.mysql.com/read.php?10,377625 (Estimating Index Size on Innodb Tables)
http://forums.mysql.com/read.php?24,376078 (COUNT(*) very slowly in large InnoDB table)
http://forums.mysql.com/read.php?10,376176 (performance issue on order by index)
http://forums.mysql.com/read.php?115,374753 (multicolumn index & forcing index to avoid filesort)
http://forums.mysql.com/read.php?20,371736 (tables with 3,500,000 rows, indexed but still v slow)
http://forums.mysql.com/read.php?20,371402 (Query with > 500000 entities in in where clause crashes server)
http://forums.mysql.com/read.php?22,370578 (Lock wait timeout exceeded; try restarting transaction)
http://forums.mysql.com/read.php?21,371066 (InnoDB to MyISAM)
http://forums.mysql.com/read.php?10,366506 (Indexes: how many, how much?)
http://forums.mysql.com/read.php?24,365913 (Improving Slow Query)
I am careful to state when a rule applies differently to MyISAM versus InnoDB. If I don't specify, then it applies equally well to both. However, if the thread is clearly dealing with one particular engine (as you are using MyISAM), I may leave out issues (better or worse) that would arise with the other Engine.
Back to your specifics...
"Using index" is usually on the first line of the EXPLAIN, regardless of where it was used. (Yes, this is confusing.) It means that when it hit some table, all the fields it needed were in a single index. This may double the speed over having to reach into the data from the index.
Here's how I analyzed
SELECT *
FROM territory_borders_finished tb, territories_finished te
WHERE tb.tb_game_number = 379085
AND te.te_game_number = tb.tb_game_number
AND tb.tb_border = te.te_code;
1. Since it is a JOIN, decide which table it will start with. This is likely to be the table for which there is some filtering (game_number = ...). So apply the rules below for that table (tb).
2. Now it needs to reach into the next table (te); what fields are being used? (game_number and tb_border). So build a compound index, in any order, with those fields.
Rules for a single table...
1. collect all fields in the WHERE clause that are "= constant" or "IN (single-constant)". Put those fields, in any order in a compound index. (only game_number in your case)
2. Now you get one chance at a range (BETWEEN, <, ...) or IN or GROUP BY or ORDER BY. Put one of those fields into the index. (no such case for your query)
It sounds like you could benefit from multiple indexes, each beginning with game_number, at least with 2 fields. 3 fields may be overkill.
Note: MySQL will almost never use 2 indexes. A "compound" index often works instead. (And is often much better than if it tried to do an "index merge" with two indexes.)