Speedy: ORDER BY RAND() operation

[bimalpoudel]

What can be done to make the following query run faster?
file_id is the primary key on the table (index)

# Random playlist
SELECT
	file_name `title`,
	REPLACE(file_path, 'P:/', '') `location`
FROM physical_files
ORDER BY
	RAND()
LIMIT 30;

I have several records in the database. And, this query is just not efficient. I want to draw random files, but ORDER BY is not good here.

There is an interesting post on similar topic on Anton Titov. Stil my problem cannot be solved. I cannot generate the list of random file_ids randomly in PHP, because, they may not exist or, filtered within WHERE condition.

Thank you in advance for a good suggestion.

[r937]

i thought it was an excellent article

why can't you generate the file_ids? what do they look like?

[felgall]

I cannot generate the list of random file_ids randomly in PHP, because, they may not exist or, filtered within WHERE condition.

There are a number of options on how to select random entries depending on how many you want.

In the variant where you get the ids and then select one at random you use a database query to extract the list of all the key values that exist in the table and then select randomly from that list. That way they always would exist and satisfy the where condition because you'd specify that in the query retrieving them.

If there are going to be too many ids to extract them all then one alternative is to first do a query to determine how many rows of the table satisfy your query to be included in the random selection. Then generate the required number of random numbers less than that number and then do a second query of the database to return the data in the entries corresponding to those random position in the results (using LIMIT 1 OFFSET randomnumber). To retrieve 30 randomly selected results would require 31 database calls to first retrieve the number of records to select from and then the specific 30 records randomly selected but it would still be lots faster than using ORDER BY rand().

ps. Also agree that is an excellent article. It doesn't cover quite as many alternative options as the book "SQL Antipatterns" does in chapter 16 which provides a half dozen alternative solutions for this problem but the article does provide a far more detailed explanation of the alternatives it does cover.

[bimalpoudel]

@r937
The reason why I cannot rely on self generated random numbers between 1 and max(file_id) is:
* The file_ids may not be continuous.
* Some rows will be filtered in WHERE condition; like: allow_play='Y', and if its (row whose allow_play is 'N') file_id was generated, there will be no data.

@felgall
What about generating a pool of valid file_ids in a different table.
And then again randomly selecting file_ids still by ORDER BY RAND() LIMIT 30.
Building a comma separated list of those file_ids, and querying with the WHERE part:

WHERE file_id IN(r,a,n,d,o,m,l,y,...,f,i,l,e,_,i,d,s)

I think it's ORDER BY RAND() will run much faster than on the table physical_files.
This pool has only one column in the table: file_id, and can be indexed.
Or, even made the primary key, as like in physical_files.

[felgall]

I think it's ORDER BY RAND() will run much faster than on the table physical_files.

Since ORDER BY RAND has to load all the keys into memory and then spend a huge amount of time switching them around getting rid of the first step will not save any significant amount of time (like standing on a ladder would make no significant difference in getting you to the moon).

Based on the information you have provided I would suggest that you do one call to count the number of entries that match the criteria you are after. Then generate your 30 random numbers between 0 and one less than the number of entries. Finally do thirty separate calls to the database each to return one of the random results you are after - specify LIMIT 1 and OFFSET randomNumber to get the specific entry corresponding to the random number you generated.

The 31 separate calls to the database will between them be way more efficient than the one call using ORDER BY RAND. Just how much time it will save depends on how many records you are extracting the 30 from but even if you only have a few hundred records it should result in saving you at least 90% of the time the order by rand would take (and probably a lot more).

[r937]

The 31 separate calls to the database will between them be way more efficient than the one call using ORDER BY RAND.

i strenuously dispute this blanket statement, and ask you to present proof

[felgall]

i strenuously dispute this blanket statement, and ask you to present proof

Why don't you provide an example where the one call using ORDER BY RAND would be more efficient at retrieving 30 records at random than the way I suggested. The inefficiency of ORDER BY RAND is a well documented fact so I believe that the burden of proof that there are circumstances where it isn't lies on the person who disputes that inefficiency.

Anyway the simplest most efficient situation using ORDER BY RAND in this case would be with only 30 records to sort randomly (you can't have fewer than that and be able to retrieve 30 records). Assuming the minimum possible number of comparisons in sorting the database you'd have 29 comparisons with the final random order being identical to the original order. The time taken to do those 29 comparisons compared to the time taken to retrieve the number of records in the table is the difference between the shortest possible time that the order by rand can take and the time that the alternative will always take. This might be slightly faster than doing the extra read but will occur only once in 2.6525285981219105863630848e+32 runs of the code. In all of the other 2.6525285981219105863630848e+32 possible orders in which the 30 records can be returned there will be more than 29 comparisons that need to be done. The average number of compares required will take much longer to carry out than retrieving the number of records in the table. That's with just 30 records in the table. The number of comparisons to be done will grow rapidly as additional records are added to the table and so the average time taken to do the compares will be significantly larger if there are even a few more records in the table. The time taken using the alternative changes far less since all we need to do is count the records and not sort them. So except in a very few instances where the "random order" ends up the same as the order in the database the time taken to do the compares will be significantly longer than the time taken to count the records.

[r937]

come on, stephen, please stop making stuff up, i've called you on that before and yet you keep making these statements

i'm not disputing that ORDER BY RAND is slow, i'm disputing your claim that 31 calls are "way more efficient" and "saving you at least 90% of the time"

you're the one who pulled the 90% number out of the air, and i'm just asking you to cite your sources

otherwise, it's just more bafflegab on your part, like that monolithic huge paragraph of rationalization that you just posted

[bimalpoudel]

Or, what about we suggest Sun/MySQL have a different way ;-)

SELECT ... FROM ...
ORDER BY
  RAND_IMPROVED(file_id)
LIMIT 30;

All with the above logics that we discussed? Again ;-)

[SpacePhoenix]

Scallio, do you mind testing this way of doing it (with the same initial dataset as the first two ways)?

    // 3rd Method
    
    $sw->start();

    for ($n=0;$n<10;$n++) {


        $query='SELECT itemId FROM items WHERE feedId>34 LIMIT '.$numItems;

        $res=mysql_query($query);
        
        $item_ids=array();
        while ($row = mysql_fetch_array($result, MYSQL_BOTH)) {
            $item_ids[]=$row;
        }
        
        $random_item_ids=array_rand($item_ids,10);
        
        // Optional shuffling of the order
        shuffle($random_item_ids);
    }
    
    $orderRandTime=$sw->stop() / 10; 

[ScallioXTX]

I wouldn't mind but I don't see what you're trying to do. You get $numItems from the database, pick $numItems of those at random (so you'll just get all items in the array) and then shuffle them.

So you just get the $numItems first rows from the database in a random order. Or am I missing something?

[SpacePhoenix]

Remove the LIMIT from the query

[ScallioXTX]

Remove the LIMIT from the query

Ah, now it makes sense!

Well, that also has a relatively constant time, and I have to say I'm totally surprised. I would have expected it to be the slowest of all options (due to the massive amount of data transfer needed), but with only ~0,21 seconds for $numItems=10 to ~0,22 seconds for $numItems=300 (on the larger table) it's actually quite a lot (~67%) faster than ORDER BY RAND !

Nice one SpacePhoenix!!

PS. If PHP and MySQL run on different servers this probably isn't the best option, especially not if you have to pay for data transfer between those servers. But still, very nice!
PPS. This is the code I used:

$sw->start();
for ($n=0;$n<10;$n++) {
    $query='SELECT itemId FROM items WHERE feedId>34';

    $res=mysql_query($query);

    $item_ids=array();
    while ($row = mysql_fetch_assoc($res)) {
        $item_ids[]=$row['itemId'];
    }

    $random_item_ids=array_rand($item_ids,$numItems);

    // Optional shuffling of the order
    // shuffle($random_item_ids);
}
$time=$sw->stop() / 10; 

I didn't apply shuffle because array_rand also get's random items, thus shuffle would only give it slightly more entropy

[SpacePhoenix]

Scallio it would make for an intersting test to repeat the three tests but with PHP and MySQL on physically separate server boxes and to compare the speed of each option both against each other and when each option is done where they're on the same server box.

[ScallioXTX]

Scallio it would make for an intersting test to repeat the three tests but with PHP and MySQL on physically separate server boxes and to compare the speed of each option both against each other and when each option is done where they're on the same server box.

If I had access to two different server boxes I'd surely like to try that. Sadly I don't ...

[r937]

here's another method ...
http://www.rndblog.com/how-to-select...rows-in-mysql/

[ScallioXTX]

here's another method ...
http://www.rndblog.com/how-to-select...rows-in-mysql/

Sorry, but I'm going to write that one off as a Bad Idea (tm).

It's based on the assumption that if you want you to get x percent of the rows in the database you should use WHERE RAND() < x/100
That in turn is based on the assumption that RAND() in MySQL has a perfectly uniform distribution.
Quite an assumption to make, and it doesn't hold.

Back to my table with 141687 rows. Say I want 100 rows from that. From the info you linked to I should use 100/141687 ~= 0.000706. So the query is:

SELECT itemId FROM items WHERE RAND()<=0.000706;

(leaving out the WHERE feedId>34 for simplicity)

If I run that 1000 times, these are the numbers of rows I get back (n: m meaning n rows returned m times out of 1000):

73: 2
75: 1
77: 4
78: 5
79: 3
81: 6
82: 10
83: 8
84: 9
85: 12
86: 17
87: 13
88: 20
89: 20
90: 24
91: 28
92: 23
93: 40
94: 30
95: 40
96: 45
97: 40
98: 40
99: 32
100: 47
101: 39
102: 35
103: 37
104: 39
105: 30
106: 26
107: 29
108: 32
109: 29
110: 24
111: 20
112: 16
113: 11
114: 9
115: 20
116: 13
117: 13
118: 9
119: 5
120: 7
121: 7
122: 9
123: 2
124: 4
125: 5
126: 3
127: 1
128: 1
129: 1
130: 1
131: 1
132: 1
135: 1
139: 1

Which looks like the starting of a bell curve with mju=100, which is no surprise at all.

My point being that you don't necessarily get 100 rows back with this 0.000706. The author of the method also found that and said "we can increase the fragment number a bit and limit the query", but that's just changing the facts because the theory doesn't fit, and still doesn't guarantee 100 rows. Just because the chance of less than 100 rows decreases doesn't mean it won't happen.

All that, plus I need to know many rows are in the database before I can even start this procedure, which is an extra query (SELECT COUNT(*) FROM daTable).

[bimalpoudel]

WHERE RAND()<=0.000706;

This either repeats data, or misses records. Every time I tried this without LIMIT, it returns different number of results.

Further, really needs to calculate the value upto which we can compare.

[ScallioXTX]

WHERE RAND()<=0.000706;

That one was specific for the number of results I wanted from my database. It's not some generic number you can just plug in anywhere.

This either repeats data,

No it doesn't

or misses records.

That's the whole point of ORDER BY RAND() isn't it?

Every time I tried this without LIMIT, it returns different number of results. Further, really needs to calculate the value upto which we can compare.

Yes, that's the whole point of my previous post. Did you read that post or just scan it?