For a project I'm working on, I got confronted with a rather ugly and complex mysql-query:

SELECT *,ij_cursta.opmerking as ij_cursta_opm, ij_rad.afhklantnaam as ij_rad_afhklantnaam, ij_rad.levklantnaam as ij_rad_levklantnaam, ij_rad.afhpostcode as ij_rad_afhpostcode, ij_rad.afhgemeente as ij_rad_afhgemeente, ij_rad.levpostcode as ij_rad_levpostcode, ij_rad.levgemeente as ij_rad_levgemeente, ij_bons.uid as ij_bons_uid, ij_afhland.iso as ij_afhland_iso, ij_levland.iso as ij_levland_iso FROM (  SELECT tb_status.bonref, tb_status.datum, MAX(tijd) AS tijd FROM (
SELECT bonref, MAX(datum) AS datum FROM tb_status GROUP BY bonref ) D
JOIN tb_status USING(bonref,datum) GROUP BY tb_status.bonref ) T
JOIN tb_status AS ij_cursta USING(bonref,datum,tijd)  JOIN tb_ritten ON tb_ritten.bonnr = T.bonref
JOIN tb_ritadressen AS ij_rad ON tb_ritten.bonnr = ij_rad.bonnr
JOIN tb_statuses AS ij_stat ON ij_stat.id = ij_cursta.status
JOIN tb_landen AS ij_afhland ON ij_rad.afhland = ij_afhland.land_en
JOIN tb_landen AS ij_levland ON ij_rad.levland = ij_levland.land_en
JOIN tb_bons AS ij_bons ON tb_ritten.bonnr = ij_bons.bonnr
WHERE tb_ritten.klantid=1 OR tb_ritten.klantid=2 OR tb_ritten.klantid=3 OR tb_ritten.klantid=4 OR tb_ritten.klantid=5 OR tb_ritten.klantid=6 OR tb_ritten.klantid=9
GROUP BY tb_ritten.bonnr ORDER BY tb_ritten.encoddatum DESC, tb_ritten.encodtijd DESC

When the php page containing this query was called, it took about 2 minutes to load. Yesterday I was sick of it, and started troubleshooting.
Using EXPLAIN I found out it wasn't using any index, and using profiling, it was clear almost all of the 2 minutes was used to copy data to a temp table.

I decided to start adding some indexes, based on the joins. After that the results (using SQL_NO_CACHE to make sure it wasn't a cached query) were shown after 8 seconds. A vast improvement, but not good enough for me.
I added some more indexes, changed the database slightly (added an intermediate table), and (with help of some people on irc.arstechnica.com, changed the query to:

SELECT *,ij_cursta.opmerking as ij_cursta_opm, ij_rad.afhklantnaam as ij_rad_afhklantnaam, ij_rad.levklantnaam as ij_rad_levklantnaam, ij_rad.afhpostcode as ij_rad_afhpostcode, ij_rad.afhgemeente as ij_rad_afhgemeente, ij_rad.levpostcode as ij_rad_levpostcode, ij_rad.levgemeente as ij_rad_levgemeente, ij_bons.uid as ij_bons_uid, ij_afhland.iso as ij_afhland_iso, ij_levland.iso as ij_levland_iso FROM tb_status_latest as ij_cursta
JOIN tb_ritten ON tb_ritten.bonnr = ij_cursta.bonref
JOIN tb_ritadressen AS ij_rad ON tb_ritten.bonnr = ij_rad.bonnr
JOIN tb_statuses AS ij_stat ON ij_stat.id = ij_cursta.status
JOIN tb_landen AS ij_afhland ON ij_rad.afhland = ij_afhland.land_en
JOIN tb_landen AS ij_levland ON ij_rad.levland = ij_levland.land_en
JOIN tb_bons AS ij_bons ON tb_ritten.bonnr = ij_bons.bonnr
WHERE tb_ritten.klantid in (1, 2, 3, 4, 5, 6, 9)
GROUP BY tb_ritten.bonnr ORDER BY tb_ritten.encoddatum DESC, tb_ritten.encodtijd DES

After all these changes, of which the indexes brought the most impressive speed gain, the query now executes in 0.6 seconds. That is an unbelievable 2000 times faster than original!