da ich ja auf der "linken"-Tabelle selektiere müssen auch nur 4000 Joins durchgeführt werden.
Das ist ein Irrtum. Es werden sämtliche Sätze ver-joint, denn die WHERE-KLausel könnte sich ja auf eine (erst durch den JOIN erzeugte) Kombination beziehen.
Soweit ich das sehe, ist MySQL so clever das zu erkennen. Denn aus der WHERE-Bedingung geht ja hervor, dass nur aus der linken Seite selektiert wird. ich habe mal den Test gemacht und in die WHERE-Bedingung einen nicht existierenden Usernamen eingesetzt (bzw. einen der nur sehr selten vorkommt). Das hat den Query extrem beschleuningt. Es scheint also in der Tat so zu sein, das nur die nötigen Zeilen gejoined werden - sonst würde die Laufzeit ja nicht von der Größe des Ergebnisses abhängen.