random video fuction made me crazy

[clonevideos]

Dear friends
i got a message from my hosting regarding random things and i don't know what is that mean? Please help me out or else my hosting is making me problem due to cpu usages issues.
here is the message they send me first:
1) Hello,
I'm writing you about your database clovidz. Please do not use "order by
rand()" on shared mysql, it is inefficient and must randomize the entire
table to return the 20 records you want. Further use of this, or of the
order by rand() causing problems, may result in your database being
disabled or the videos table disabled. You can write me about this issue
at
# Query_time: 3003.739149 Lock_time: 0.099743 Rows_sent: 0
Rows_examined: 49478
use clovidz;
SET timestamp=1292517650;
SELECT * FROM `videos` WHERE
`video_type`='public' AND
`video_active`='1' AND
`video_approve`='1'
ORDER BY rand()
LIMIT 14140, 20;
I asked them how to fix and they replied the second message like this:
2)Thanks for writing me back, and sorry for the delay. The issue is due to
the website code using "order by rand()", which is used to randomize the
records returned. It also must randomize the entire table when it runs,
even if you only ask for a few records. If you are not the person who
developed the software using this database, this will be more difficult.
If that is the case, you can check if there is a way to turn off the
"show random 20 videos" feature, that would likely stop this problem
query. If that is not possible, then besides having a person change the
website code to not run this, or make it more efficient, this will
eventually outgrow shared mysql hosting and will need a MySQL VPS or more
powerful mysql hosting at another host. As more video data is added to
that table, it will get less and less efficient and cause more impact on
mysql. Please let me know what can be done to fix the query.
Thanks!
Any fixes? please help me.