Theory of indexes for query with joins I found the following talk by Zardosht Kasheff enlightening:

http://www.infoq.com/presentations/Index-SQL

but it only covers the case of simple queries on a single table.

Is there something similar for queries involving multiple tables?  Possibly including GROUP BY?

I'm looking for some theory/guidelines which I can apply to MySQL with the InnoDB storage engine.
A common mistake is

SELECT ... SUM(a.foo) ...
    FROM a
    JOIN b ON ...
    WHERE ...
    GROUP BY a.id


When you JOIN two tables, you usually get an explosion of the number of rows.  The SUM is then done, probably summing up a.foo repeatedly, leading to the 'wrong' (too big) answer.

But that was not what you asked.

A JOIN is almost always executed this way:


Pick a table to start with.  Apply any filtering (WHERE).  So far, the single-table rules apply.
Move on to another table.  But this time, use "Nested Loop Join".  This means "foreach row from step 1, reach into table 2".


So, the new question you are asking is how to reach into table 2?  There is an ON clause (assuming it is not a "cross join").  That gives you one (or more) field that should be used in the 'best' index for table 2.  Then use that field, plus any other fields in WHERE, together with the single-table rules to construct the optimal index for that JOIN.

Since the optimizer might pick a different order of tables, or might like to have multiple choices, find the best indexes for each order.

Then simplify.


INDEX(x), INDEX(x,y) --> INDEX(x,y)
Don't have indexes with more than, say, 5 fields.
If you are joining to the PRIMARY KEY of table 2, you don't need a longer index.
Consider "covering" indexes.  (EXPLAIN will say "Using index", not to be confused with "Using index condition", which is ICP.)


Here are some tips on how the optimizer thinks when joining two tables:


A table with a WHERE filter will be chosen before one without.
Other things being 'equal', the smaller table will be chosen first.
Sometimes an ORDER BY will be preferred over a WHERE in ordering the tables.
LIMIT is rarely a factor, although it probably should be.


My cookbook also focuses on single-table; maybe this answer will help me write about JOINs.