Optimizing MySQL - Database Design Manual: Using MySQL for Windows - page 152

Figure 13.6 EXPLAIN on a restricted cross join.

If you run the above script, you will get approximately 800 rows back. You would there-
fore assume that adding the WHERE clause made the query more efficient. However, run-
ning EXPLAIN on the query gives the results shown in Figure 13.6.
You will notice that although the actual query only returned around 800 rows, running
the EXPLAIN shows that 1764 rows need to be examined in order to execute the query, so it
is just as inefficient as the cross join before the WHERE restriction.
Section 3.2.1 of the online MySQL manual that comes with the product gives a thorough
walk-through of using EXPLAIN to optimize a complex query.

Indexing

When we looked at the possible_keys column of the EXPLAIN output, I said that if we had
a NULL in this column the query could be made more efficient by using an index. An index
is a data structure that will speed up the retrieval of rows when applied to a certain search
criterion. In other words, if you are searching for something in a table, the search will gen-
erally be quicker if an index exists for the column that the data is contained in.
For instance, say you have a log database full of tens of thousands of records which con-
tains data for a whole year of web accesses. The data is stored in a sorted form, as data is
inserted into the table in chronological order; so all of the dates are ascending. If you need
to search for all of the page hits in June, the server has to sequentially examine all of the
rows for the proceeding months until it finds the entries for June. It probably needs to check
all of the rows created in the months after June as well if it does not realize that the data is
stored in date order.
If we were to add an index to the date column in this table, when searching for June, the
MySQL server would examine the index and find that the table is sorted and realize that it
can start the retrieval approximately 60 000 records into the table. This might actually be
half-way through May, but this means that much fewer rows need to be examined before
finding the June entries. Then, as soon as the server comes across a July entry the search can
stop, because if the dates are sorted, no more June entries can occur once the July ones
begin. If the table contains approximately 10 000 rows per month, the index will have saved
the server from looking at over 100 000 rows, that is, the January to May rows and the July
to December ones.