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
