- Filter 1M rows to find 100K rows -- a full table scan of 1M rows
- Pick, say, 10 random rows from the 100K -- a scan of 100K rows, unless you use some technique from http://mysql.rjweb.org/doc.php/random .
- Leave behind something that lets you "paginate". Do you care if it accidentally repeats rows? Is this web-based, meaning that "leaving something behind" can be messy -- such as listing all the items already seen when in the url of the [Next] button.
- Pagination via LIMIT and OFFSET is Order(N*N) to walk through all N pages. 100K rows, 10 rows at a time, would be something like 500M. Even worse than the original 1M.
Now, let me invent a solution that solves the cost of both "random" and "pagination". See http://mysql.rjweb.org/doc.php/random#case_extra_float_column_for_randomizing
- Prep: Add an extra column with some random number in it. Index it. This will become both the randomizer and the "where you left off" to avoid using the costly
OFFSET
.
- See the link for one approach to getting the first 10 random rows.
- See http://mysql.rjweb.org/doc.php/pagination for more on "remembering where you left off".
Do all those, and the cost becomes mostly the original Step 1, namely whatever it takes to filter the 1M rows. Hopefully, it won't even be that costly -- this depends on whether a suitable index can be had that gets all the way to the LIMIT 10
. (My gut says that won't be practical.)
Summing up:
SELECT ...
FROM ...
WHERE filters...
AND rnd > $left_off
ORDER BY rnd
LIMIT 10;
If you start $left_off
at 0, you get a repeatable, but seemingly random, sequence. And the [Next] button only needs to pass the last value of rnd
that was fetched from the current page.
Now to make it not repeatable? Re-populate rnd
every night. (That would mess with anyone in the process of paginating.)
LIMIT
andOFFSET
?ORDER BY RAND()
, and out of that useLIMIT
andOFFSET