Simpelthen ved at anvende en GROUP BY klausul, og forudsat at du har et indeks, FOREIGN KEY , eller PRIMARY KEY på parentId , ydelsen burde være ganske god. (parentId ser ud til, at det sandsynligvis er en FORIEGN KEY , så sørg for at definere begrænsningen for at håndhæve indeksering).
SELECT `parentId`
FROM `foo`
GROUP BY `parentId`
ORDER BY COUNT(*) DESC