Simplemente aplicando un GROUP BY y suponiendo que tiene un índice, FOREIGN KEY , o PRIMARY KEY en parentId , el rendimiento debe ser bastante bueno. (parentId parece que es probable que sea una FORIEGN KEY , así que asegúrese de definir la restricción para hacer cumplir la indexación).
SELECT `parentId`
FROM `foo`
GROUP BY `parentId`
ORDER BY COUNT(*) DESC
