5 sec for 10000 records is REALLY slow... add some indexes to it.
BUT, a way faster solution would be this (assuming your not deleting to many records):
- have your table primary key be numeric, auto increment.
- with PHP, generate ~100 random numbers, from 0 to your max(id)
- SELECT * FROM table WHERE id IN ('.join(',',$ids).') LIMIT 50;
- Repeat the select until you get 50 records returned.
This can make your 5 sec select to 0.0005 sec, as long as you select from the entire table (works in most situations).