problema con tablas, demasiados registros

[glome]

Hola

Estoy volviendome loca, y lo peor es que no se si tendrá solución.
Les cuento, tengo varias tablas, cada una de ellas de entre 300.000 y 600.000 registros.

Digamos que tengo una consulta fácil (tabla marcas, 60 o 70 registros) y por cada marca tengo que buscar la cantidad de resultados de las dos tablas grandes relacionadas entre si.
La funcion de php me deja colgado el pc entero. Desde phpmyadmin, 1 o 2 consultas me las busca, aunque un poco lento, pero si pongo el sql completo tambien se queda atascado. Por lo que creo que no son las consultas en sí.

Estoy buscando formas de optimizar la base de datos, las consultas y el php, pero no estoy consiguiendo nada.

Mi pregunta es: ¿Es posible gestionar desde php esa cantidad de registros?
Si creeis que es error de mis consultas, os mando el codigo que pidais.

Mil gracias