SELECT RAND() AS 'my_rand', t.*
FROM table t
GROUP_BY domain
ORDER BY my_rand LIMIT 1000
Я не уверен, насколько это действительно случайно, но в моей тестовой базе данных он выдает, казалось бы, случайные результаты.
Я не уверен, что вы можете сделать это простым запросом, не сканируя всерядов.