Etapa 1. Você tem o OR de 4 condições. Transforme a consulta em UNION de 4 SELECTs , cada um com um dos OR condições.

Etapa 2. Remova as tabelas não utilizadas em cada SELECT (para se livrar dos produtos cartesianos).

Etapa 3. Adicione INDEX(uid, rid) (em qualquer ordem) para a .