Ok cool, I'm not familiar with explain, so I'll educate myself on that, looks like it could be quite useful :-)

That aside, would that explain why the performance in MySQL Query Analizer is fine, yet when the query is executed via a php page it is incredibly slow?