Subconsulta NOT IN muy lenta

[planmental]

buenos días foreros.

Vengo con otro problema más, pues tengo un problema con una subconsulta NOT IN.

Y no es un problema de programación pues todo sale bien, mi problema es que es muy lento el proceso y es que necesito hacer varios querys con la misma subconsulta en la misma página php.

El código es el siguiente:

Código MySQL:

SELECT MAX(fecha) fecha,  id, remolque FROM vehiculos 
WHERE cliente ='".$f['cliente']."' AND remolque 
NOT IN (SELECT remolque FROM vehiculos WHERE cliente ='".$f['cliente']."' 
AND localidad = 'BASE') GROUP BY remolque
 

Tengo que sacar todos los remolques de la tabla vehiculos pero si el local dice 'BASE' que no me los muestre. Todo sale muy bien justo como lo necesito, pero mi problema radica en que es muy lenta la consulta por la razón de que son varios códigos como los que muestro arriba. Y lo que necesito es si existe otra opción a la subconsulta un poco más rápida.

PD: manejo solo una tabla.

Por su atención gracias.