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.
Da solltest dich über Subselects schlau machen oder zwei SQLs nehmen.