Gorilla3D Primative Teachings

Blog   Gorilla_Labs   Tutorials   Portfolio   Contact  
Joseph Says: STOP SPAMMING MY %$#@ING SITE $%#@!!!!!
Search

Faster & Smarter MySQL Random Row Selection

Wednesday, December 19, 2007

In this entry will be dealing the following dataset:
geoip.sql ~ 94k rows | 7.8 MB

Figure 1. Shows the typical random MySQL random row Selection. On my server I ran 1000 iterations coming to about 0.6 seconds average in response time. The script took over 10 mins to execute 1000 random rows. Thats is awful performance and mean that if your site has more then 1 queries per second your database would crawl to a halt.

Figure 1. ~ 0.6 seconds

  1. <?php
  2. //-- Mysql Database Config
  3. $db_host = 'localhost';
  4. $db_db   = 'mysite';
  5. $db_user = 'root';
  6. $db_pass = '';
  7.  
  8. //-- Mysql Connection
  9. $db_link = mysql_connect($db_host, $db_user, $db_pass)
  10. 	or die('MySQL Connection Error:'.mysql_error());
  12. 	or die('MySQL Error: Cannot select table');
  13. //-- Fetch a random row
  14. $sql = "SELECT * FROM `csv` ORDER BY RAND() LIMIT 1";
  15. $result = mysql_query($sql) or die(mysql_error());
  16. $row = mysql_fetch_assoc($result);
  17. ?>


Figure 2. Shows an alternative method yields 1000 iterations coming to about 0.001 seconds average in response time. Meaning your database can now withstand 1000 queries per second.

Figure 2. ~ 0.001 seconds
  1. <?php
  2. //-- Mysql Database Config
  3. $db_host = 'localhost';
  4. $db_db   = 'mysite';
  5. $db_user = 'root';
  6. $db_pass = '';
  7.  
  8. //-- Mysql Connection
  9. $db_link = mysql_connect($db_host, $db_user, $db_pass)
  10. 	or die('MySQL Connection Error:'.mysql_error());
  12. 	or die('MySQL Error: Cannot select table');
  13.  
  14. //-- Find the largest ID
  15. $sql = "SELECT * FROM `csv` ORDER BY `id` DESC LIMIT 1";
  16. $result = mysql_query($sql) or die(mysql_error());
  17. $row = mysql_fetch_assoc($result);
  18. //-- Fetch a random row
  19. $max = intval($row['id']);
  20. $sql = "SELECT * FROM `csv` WHERE `id` = ". rand(1, $max) ." LIMIT 1";
  21. $result = mysql_query($sql);
  22. $row = mysql_fetch_assoc($result);
  23. ?>


Now what if your database has large section of missing ids (They skip in range, i.e 1, 3, 7)? Well look at Figure 3. This is an example of just looping the random selection based on the same code as Figure 2. The performance on this will very as it could be the 1st result that yields a row or the 100th, none of the less it still a far better alternative result then using MySQL's built in RAND() function to fetch random rows.

Figure 3. ~ N/A
  1. <?php
  2. // Mysql Database Config
  3. $db_host = 'localhost';
  4. $db_db   = 'mysite';
  5. $db_user = 'root';
  6. $db_pass = '';
  7.  
  8. // Mysql Connection
  9. $db_link = mysql_connect($db_host, $db_user, $db_pass)
  10. 	or die('MySQL Connection Error:'.mysql_error());
  12. 	or die('MySQL Error: Cannot select table');
  13.  
  14. //-- Find the largest ID
  15. $sql = "SELECT * FROM `csv` ORDER BY `id` DESC LIMIT 1";
  16. $result = mysql_query($sql) or die(mysql_error());
  17. $row = mysql_fetch_assoc($result);
  18. $max = intval($row['id']);
  19. $result = false;
  20. //-- Query a random row until we get a result
  21. while(!$result) {
  22.   $sql = "SELECT * FROM `csv` WHERE `id` = ". rand(1, $max) ." LIMIT 1";
  23.   $result = mysql_query($sql) or die(mysql_error());
  24. }
  25. $row = mysql_fetch_assoc($result);
  26. ?>


Now if your looking for a pure Mysql method use a subquery, this will allow you to use Mysql to still generate random ids. If you look at Figure 4. the subquery is which just totals the number of rows within our database. Then the table's id is matched against php's random function lcg_value() which only generates 0 - 1 numbers, to fix that we just multiply that against our subquery's 'total'. So in the end what did 1000 iterations prove? Well I got 0.0005 seconds average per query, as you can see even faster then in Figure 2.

Firgure 4. ~ 0.0005 seconds by Joe
  1. <?php
  2. // Mysql Database Config
  3. $db_host = 'localhost';
  4. $db_db   = 'mysite';
  5. $db_user = 'root';
  6. $db_pass = '';
  7.  
  8. // Mysql Connection
  9. $db_link = mysql_connect($db_host, $db_user, $db_pass)
  10. 	or die('MySQL Connection Error:'.mysql_error());
  12. 	or die('MySQL Error: Cannot select table');
  13. $sql = "SELECT * FROM csv WHERE id = ROUND(".lcg_value()." * (SELECT COUNT(*) FROM csv)) LIMIT 1";
  14. $result = mysql_query($sql) or die(mysql_error());
  15. $row = mysql_fetch_assoc($result);
  16. ?>


So when do you use RAND()?


For a single selection RAND() is just slow but when you need to use WHERE to filter your random selections as well as selection MANY random rows, RAND is your best best. Figure 5. & Figure 6. prove that point RAND() is just what to use when you need to filter your results. Now if you have a table that does not change very often and you are using the same filter over and over, Figure 6. would be your best best, this allows you to reuse the temp table to query rand rows much faster.

Figure 5. - Rand() ~ 0.65 seconds
  1. //-- Mysql Database Config
  2. $db_host = 'localhost';
  3. $db_db   = 'mysite';
  4. $db_user = 'root';
  5. $db_pass = '';
  6. //-- Mysql Connection
  7. $db_link = mysql_connect($db_host, $db_user, $db_pass)
  8. 	or die('MySQL Connection Error:'.mysql_error());
  10. 	or die('MySQL Error: Cannot select table');
  11. //-- FINALLY query for our random rows w00t
  12. $sql = "SELECT * FROM csv WHERE cn = 'Germany' ORDER BY RAND() LIMIT 50";
  13. $result = mysql_query($sql) or die(mysql_error().'<br>'.$sql);
  14. while($row = mysql_fetch_assoc($result)) {
  15.   $row;
  16. }


Figure 6. - Temp Table ~ 1.1 seconds / ~ 0.01 seconds
  1. //-- Mysql Database Config
  2. $db_host = 'localhost';
  3. $db_db   = 'mysite';
  4. $db_user = 'root';
  5. $db_pass = '';
  6. //-- Mysql Connection
  7. $db_link = mysql_connect($db_host, $db_user, $db_pass)
  8. 	or die('MySQL Connection Error:'.mysql_error());
  10. 	or die('MySQL Error: Cannot select table');
  11.  
  12. //-- Create a temp table, with our WHERE filters
  13. $sql = "CREATE TEMPORARY TABLE IF NOT EXISTS csvTemp (
  14.     temp_id INT(10) unsigned NOT NULL auto_increment,
  15.     PRIMARY KEY (temp_id)
  16.     )
  17.   SELECT * FROM csv 
  18.   WHERE cn = 'Germany'";
  19. mysql_query($sql) or die(mysql_error().'<br>'.$sql);
  20.  
  21. //-- Fetch the total row count (we cant join/subquery the same temp table)
  22. $sql = "SELECT COUNT(*) AS total FROM csvTemp";
  23. $result = mysql_query($sql) or die(mysql_error().'<br>'.$sql);
  24. $row = mysql_fetch_assoc($result);
  25. $total = intval($row['total']);
  26.  
  27. //-- Generate our random temp_ids
  28. $rands = array();
  29. foreach(range(1, 50) as $n) { // Select 50 random ids
  30.   $rands[] = intval(lcg_value() * $total);
  31. }
  32.  
  33. //-- FINALLY query for our random rows w00t
  34. $sql = "SELECT * FROM csvTemp WHERE temp_id IN (".implode(', ', $rands).")";
  35. $result = mysql_query($sql) or die(mysql_error().'<br>'.$sql);
  36. while($row = mysql_fetch_assoc($result)) {
  37.   $row;
  38. }




If you know better methods, please by all means leave a comment and share your code. You can use syntax highlighting as above by encasing your code in BBcode style tags. i.e

Comments

Volomike posted 93 days ago

My problem is seen with a paid sponsored classified listings site. I need 5 random sponsored listings that match a given keyword, followed by the rest of the non-sponsored listings. I need to make good use of randomness because I don't need some sponsored listings to have precedence too much over others. You can see how slow things are by checking out http://118fm.co.uk/. I have a real conundrum because keyword search queries are taking like 8 seconds to run, even with indexes added in. It used to take like 2 seconds when I first built the database.


Emmy posted 114 days ago

hello babe! remember me? :)


Joseph Montanez posted 296 days ago

Rob,
You are right when it comes to RAND() and you need to select many random rows as well as set up WHERE filters, RAND() is just what you need.


Rob Marsh posted 296 days ago

What about the case where a) you want more than a single row and b) there is a WHERE clause filtering the rows so that they may be be sparse? Nothing I've tried is faster than RAND().


Joseph Montanez posted 296 days ago

Given the query below it results in 0.0005 vs 0.001 in Figure 1. I acturally did not know how much RAND() degrades in performance, I also replaced RAND in Figure 4. to get 0.0006 results, yours is clearly better.

  1. $sql = "SELECT * FROM csv WHERE id = ROUND(".lcg_value()." * (SELECT COUNT(*) FROM csv)) LIMIT 1";


Add Comment