Парампампам. КостылиКостылиКостылиКостылиКостылиКостыли
Генерируйте ваш мильён записей
tbl (тип — MEMORY!!!!!)
id|crc
Считаете любой хеш (напр.CRC32) записи, берёте 5-8 символов с любой стороны и пишите в поле (один долгий запрос вида, update tbl set crc = substr (5,7,CRC(concat(id,'somerandsmthng'))) ага) обязательно ставите индекс по этому остатку CRC.
insert into newtbl select id as tktid, 0 as uid from tbl order by crc;
В итоге мильён довольно перемешанных записей.
Как-то так.