Lấy nhanh random rows trong mysql table

Em có db mysql tầm chục M rows. Giờ em muốn select ngẫu nhiêu 1M rows, nhưng xài order by rand() thì quá chậm. Thêm nữa là e ko đánh số thứ tự cho rows nên select theo kiểu random ID ko được. Có cách nào giải quyết ko mấy thánh?