Fast Random Results - "ORDER BY RAND()" is bad

Sxooter · 2007-04-15T03:26:02+00:00

Quite often we need fast random results. A lot of new developers do it this way: select * from table order by random() limit 1; Seems simple enough. And...

Fast Random Results - "ORDER BY RAND()" is bad

Sxooter

Because there might be holes in the sequence.

OTOH, you can cache the start / stop numbers and use something like:

select * from table where id >= $id limit 1;

Sxooter

Just read what you wrote (second time) and you're absolutely right.
Will post an adendum

NogDog

Just a thought I had, no idea if it would perform any better:

Do a SELECT COUNT(*) to get the number of records
Do a <?php $offset = rand(0, $count - 1); ?> where $count comes from the above query.
Do a SELECT * FROM table LIMIT 1 OFFSET $offset

I have no empirical evidence how this would perform versus the ORDER BY RAND() method, but figured I'd throw it out there in case you want to try it.

Sxooter

Thanks to laserlight's point, I ran the same query to populate the summary table, but with the last month's data instead of the last 48 hours. It took quite a while to build the summary table, 450 seconds. And it inserted 6787330 rows. Select time still hovers around 50 milliseconds for the first time on a row, 1 millisecond the second time when it's block is in memory.

Sxooter

NogDog wrote:
Just a thought I had, no idea if it would perform any better:

Do a SELECT COUNT(*) to get the number of records

Do a <?php $offset = rand(0, $count - 1); ?> where $count comes from the above query.

Do a SELECT * FROM table LIMIT 1 OFFSET $offset

I have no empirical evidence how this would perform versus the ORDER BY RAND() method, but figured I'd throw it out there in case you want to try it.

Tried it before. It's halfway between order by rand() and my method in terms of performance. Problem is that the db still has to generate the whole data set before hitting the offset and stopping, so the higher the number, the longer it will take to return.

Note that select count(*) is NOT fast in most databases (Oracle, PostgreSQL, MySQL with innodb tables) when the tables are very large.

for instance, on the table listed above, hitting the last month's data, Here's what I go for varying offsets, in milliseconds

1: 1.3
100: 3.5
1000: 4.4
10,000: 23
100,000: 210
500,000: 1280
1,000,000: 3000

You can see where that's heading. At 40+ million rows, it's not gonna scale.

COUNT() pretty much has to traverse through the entire table, right?

laserlight, yes count() has to traverse the whole table in many databases, such as postgresql and oracle and mysql with innodb tables...

laserlight

Note that select count() is NOT fast in most databases (Oracle, PostgreSQL, MySQL with innodb tables) when the tables are very large.

COUNT() pretty much has to traverse through the entire table, right?

NogDog

I was remembering this regarding MySQL:

COUNT(*) is optimized to return very quickly if the SELECT retrieves from one table, no other columns are retrieved, and there is no WHERE clause.

However, it then notes that this is only applicable in MyISAM tables.

Roger_Ramjet

Instead of COUNT() you can use SHOW TABLE STATUS with myisam tables to get the number of rows. Unfortunately this does not work for other table types which only return an approximation of the row count.. Be interesting if someone could benchmark this against count(). My assumption is that show status will be independent of table size.

Sxooter

There's something similar in most databases for estimating rows cheaply. In PostgreSQL it's

select reltuples from pg_class where relname='tablename';

klunky but it works. It tells you how many tuples were in the table at the end of the last vacuum.

Roger_Ramjet

[edit]cleaned up for sticky[/edit]

When I take those 3 steps back and look at the problem, I see that the solution is the domain itself. What we have all forgot is that the web is a random environment. We see so many folk trying to use this RAND() thing for good reasons on their websites because they want to display random advertising banners, random users, random messages, etc. What we all forget is a) Random does not mean unique, but more importantly b) it is the users who are already random.

The solution to displaying random events to individual users is already taken care of by their random page hits. All you need to do is to cycle sequentially through your items and that is a simple algorithm with easy optimisation.

Those cases where RAND() is a necessary and applicable solution are complex apps like MRP/JIT, BI, Risk Analysis/Financial Modelling, Market Research, Scientific Analysis, etc: domains where complex and powerful analysis is involved and performance is secondary to results. When I worked in market research we did not mind if a report took 20 mins to process - just go to lunch, or run it overnight.

Sxooter

Because with all their wealth of experience and knowledge, this RAND() problem is not one that they have had to solve before. If it were then the solution would have been presented already.

I have run into it quite a bit before, and I believe I have presented the best solution for randomly selecting one row from a large data set. 😃

If you've got a better solution, I'd love to see it.

About the 20 minute reports. I've got some reports that take the better part of a day to run, and that's after massive optimization. When you're aggregating 40 million rows of data, it can only be done so fast. If that same report had an order by random() clause in it, it would, literally, eat every byte of RAM, gigs of storage, and probably not return for weeks, maybe even months.

Roger_Ramjet

Hey, cool down Sxooter, I was not knocking you. On the contrary, I was trying to say that generally you would not even think of doing this. Those cases where you would have done it would be apps where rand() was essential and the only way to do the job; and you would accept the performance hit just because it was the ONLY way to do the job.

If I've upset you, sorry. All I can say is that sitting drinking beer in the sunshine has got the better of me.

I do have a modification to your method that will not get the performance hit with using LIMIT base,offset on large data sets.

// get the highest 2 ids
$res1 = mysql_query("SELECT id FROM table ORDER BY id DESC LIMIT 2");
// generate random no between 0 and second highest id
$top = mysql_result($res1,1);
$rand = rand(0,$top);
// now query for id greater then random no
$sql = "SELECT * FROM table WHERE id>$rand ORDER BY id DESC LIMIT 1"

Size of dataset should not matter, but I stand to be corrected if you care to benchmark it.

Sxooter

I'm not upset in the least, honestly. I sorta kinda figured that was where you were heading.

I've posted something similar to your solution and that one also runs very quickly.

I think I might be due for a pub run myself! 🙂

Roger_Ramjet

Cool, Sxooter, go for it. I'm back down there myself in a mo to watch Chelsea v Blackburn in the FA cup semis. 😉

bradgrafelman

Thread stickied; if any cleaning up needs to be done, Sxooter, let me know.

sarakigroup1

Bozebo

Wow that's a sweet tip... I used to do it that way about 3 years ago when I was starting out and had no idea there was an ORDER BY rand() possibility.

djalecc

Roger Ramjet wrote:
We see so many folk trying to use this RAND() thing for good reasons on their websites because they want to display random advertising banners

I'm stuck on this one now, was going to use RAND() to pick 1 of 3 adverts, but decided to rotate them...

Roger Ramjet wrote:
The solution to displaying random events to individual users is already taken care of by their random page hits. All you need to do is to cycle sequentially through your items and that is a simple algorithm with easy optimisation.

Can you share this solution/algorithm with us? Please 😃

laserlight

I'm stuck on this one now, was going to use RAND() to pick 1 of 3 adverts, but decided to rotate them...

Rotation should work just as well.

Can you share this solution/algorithm with us?

Basically, keep some kind of pointer to the current item. Increment (and loop around) the pointer whenever the current item is displayed. In other words, Roger Ramjet suggested your rotation solution.

djalecc

laserlight wrote:
Basically, keep some kind of pointer to the current item. Increment (and loop around) the pointer whenever the current item is displayed. In other words, Roger Ramjet suggested your rotation solution.

In the deep dark night I managed it, of course it was very simple, but me being a man with Man Flu at the time I just could not get my head around it :rolleyes:

The answer in case anyone is looking for it is simply have a counter, when the ad is shown add 1 to that counter, the query is simply

SELECT * FROM adverts ORDER BY counter_total LIMIT 1

It only kicks in and works of course [ and this is where I blame the man flu ] if the counter_total filed is set to int() :o