Re: ORDER BY RAND() Too Slow! Alternatives?

[Jeffrey D. Wheelhouse]

At 11:39 PM 2/10/2001 -0800, Stephen Waits wrote:
Never mind on the "it doesn't work on my system" more like it didn't
work on my brain :)  Works fine.

Oh, phew.

Theoretically it could be as fast as Carsten's method couldn't it?  If
it hit a record on the first shot?  Otherwise it's pounding through an
index O(random-nearest_id) where his does it O(1).  And could it
potentially loop infinitely?

Based on my admittedly pathetic understanding of B-trees and database 
indexes, I *think* Carsten's approach is O(lg n) on the number of rows.  My 
approach is O(M*n) on the number of rows, where M is a pretty lightweight 
access to nab the key.  The "LIMIT $rand, 1" approach is O(D*n/2) on the 
number of rows over time, but D is a nasty I/O hit to slurp the whole row 
into the resultset.

The only case where Carsten's approach and mine would converge would be if 
you were using a query where no index could be applied.  Then they'd both 
be stuck at O(N) on the number of rows.

I am curious whether "(@rand:=@rand-1)+id=id" can be optimized to remove 
the table reference (id) without having the query optimizer decide it only 
needs to run once.  That might shave a good bit off of M.

In a case like this, it would be handy to have a ROW() function that tracks 
the running counter being used to generate the "X rows in set." 
statistic.  But such a thing would probably be of limited utility.

At 11:28PM 2/10/2001 -0800, Stephen Waits wrote:
Carsten's approach is one of those "duh" things I don't understand why I
hadn't thought of it.?

Likewise.  It's a good reminder that clever solutions don't always come 
from linear thinking.  Thanks Carsten!

Jeff


-
Before posting, please check:
   http://www.mysql.com/manual.php   (the manual)
   http://lists.mysql.com/   (the list archive)

To request this thread, e-mail [EMAIL PROTECTED]
To unsubscribe, e-mail [EMAIL PROTECTED]
Trouble unsubscribing? Try: http://lists.mysql.com/php/unsubscribe.php

Re: ORDER BY RAND() Too Slow! Alternatives?

[Jeffrey D. Wheelhouse]

Could you do something like:

CREATE TEMPORARY TABLE temptable (
   pk INTEGER,
   rand INTEGER
);
INSERT INTO temptable SELECT yourpk,Rand() FROM yourtable;
SELECT yourtable.* FROM yourtable,temptable WHERE pk=yourpk ORDER BY rand;
DROP TABLE temptable;

That might be quicker than your current approach.

Jeff

At 12:12 PM 2/10/2001 -0800, Stephen Waits wrote:

Hi there,

In the quest to get a random row from a table, "order by rand()" has
proven too inefficient and slow.  It's slow because MySQL apparently
selects ALL rows into memory, then randomly shuffles ALL of them, then
gives you the first one - very inefficient.  There are a few other ways
I've thrown around but none are "elegant".

One is, if a table has an id # column, like "id int unsigned not null
auto_increment", I could do this:

select max(id) from table;
$random_number = ...
select * from table where id=$random_number;

This is very fast (assuming the id field is a unique index).  But it has
the problem that if records have been deleted I might get a 0-row
response.  It also does not work if I want to limit to a particular
category, for instance "where category='women'" or something.

I could do this too:

select count(*) from table;
$random_number = ...
select * from table limit $random_number,1;

This has the benefit of always working but the speed, though faster than
the "order by rand()" method, remains unacceptable.  The speed seems
linear with regard to the size of $random_number; which is probably
obvious to you.

So I've experimented with several other things:

select * from table where limit rand(),1;
select * from table where id=(mod(floor(rand()*4294967296),count(*))+1);
.. and it only gets uglier from -- these are all not accepted by MySQL.

MySQL does not allow for subqueries which is another way it could possibly
be accomplished.  In the end, I'll just use what works, no matter the
speed.

BUT, I'd love to hear what other people have done to solve this problem!

Thanks,
Steve


-
Before posting, please check:
http://www.mysql.com/manual.php   (the manual)
http://lists.mysql.com/   (the list archive)

To request this thread, e-mail [EMAIL PROTECTED]
To unsubscribe, e-mail [EMAIL PROTECTED]
Trouble unsubscribing? Try: http://lists.mysql.com/php/unsubscribe.php


-
Before posting, please check:
   http://www.mysql.com/manual.php   (the manual)
   http://lists.mysql.com/   (the list archive)

To request this thread, e-mail [EMAIL PROTECTED]
To unsubscribe, e-mail [EMAIL PROTECTED]
Trouble unsubscribing? Try: http://lists.mysql.com/php/unsubscribe.php