StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p><a href="http://jan.kneschke.de/projects/mysql/order-by-rand/" rel="nofollow noreferrer">This page</a> has a pretty detailed writeup on how to optimize an <code>ORDER BY RAND()</code>-type query. It's actually too involved for me to explain adequately on SO (also, I don't fully understand some of the SQL commands used, though the general concept makes sense), but the final optimized query makes use of several optimizations:</p> <ol> <li>First, <Code>ORDER BY RAND()</code>, which uses a <code>filesort</code> algorithm on the entire table, is dropped. Instead, a query is constructed to simply generate a single random id.</li> <li>At this stage, an <code>index scan</code> is being used, which is even less efficient than a <code>filesort</code> in many cases, so this is optimized away with a subquery.</li> <li>The <code>WHERE</code> clause is replaced with a <code>JOIN</code> to reduce the number of rows fetched by the outer <code>SELECT</code>, and the number of times the subquery is executed, to just 1.</li> <li>In order to account for holes in the ids (from deletions) and to ensure an equal distribution, a mapping table is created to map row numbers to ids.</li> <li>Triggers are used to automatically update & maintain the mapping table.</li> <li>Lastly, stored procedures are created to allow multiple rows to be selected at once. (Here, <code>ORDER BY</code> is reintroduced, but used only on the result rows.)</li> </ol> <p>Here are the performance figures:</p> <ul> <li>Q1. ORDER BY RAND()</li> <li>Q2. RAND() * MAX(ID)</li> <li>Q3. RAND() * MAX(ID) + ORDER BY ID</li> </ul> <pre> 100 1.000 10.000 100.000 1.000.000 Q1 0:00.718s 0:02.092s 0:18.684s 2:59.081s 58:20.000s Q2 0:00.519s 0:00.607s 0:00.614s 0:00.628s 0:00.637s Q3 0:00.570s 0:00.607s 0:00.614s 0:00.628s 0:00.637s </pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload