グループごとに最大のクエリを高速化するにはどうすればよいですか？

これを試してください：

SELECT    district, id, COUNT(b.district)
FROM      adverts a INNER JOIN adverts b
              ON a.district = b.district
WHERE     b.id > a.id
GROUP BY  district, id 
HAVING    COUNT(b.district) < 5
ORDER BY  district, id DESC 

定義上、Joins 速い subqueriesより 。