How to Optimize Order by Random()
tpetry.me
tpetry.me
Another approach would be to create a table with a small sample of the main one and refresh it periodically -- each query just needs to do a random reordering on the small sample, and the results will be truly random over time.
This where you can spend a surprising amount of time unpredictably.
Having a pre-shuffled array helps much more.
Edit: I doubt it’s uniform as well because rows at the edges are less likely to be selected.
if rows don't often get deleted, you can keep a row for the items ordered number, but on deletion you would have to relabel all rows (or put up with uneven page item counts)
If you computed the cell points anew for each sampling, it would indeed be random. But for repeated sampling, you've made up a very skewed distribution, where the successive samples are highly correlated.
It‘s 2d because databases do not have kNN with index support for a single float value. And without kNN you are building approach #2 with all of it‘s problems.
I've Googled around but didn't find anything about this trick:
You can calculate a score and do something like ORDER BY RAND() * score to bias towards certain rows. This could be useful, e.g. you want to randomly show your most profitable items. The kNN method seems harder to generalize.
Anyway, if you had this blue noise, whether 1d or 2d, would still not solve your problem; once you start deleting points, you lose your beautiful properties of uniform voronoi cell sizes and your back to square one.
While this approach does have this benefit, it's no longer "random" in the sense that all rows are equally likely to be selected. So, it depends on your purpose as to whether this is an acceptable solution. I don't see any reason to do it in 2D over 1D, except that some of the flaws in the approach are more obscured.
I'm unclear why you can't do traditional gold standard simple random sampling, where you repeatedly generate random numbers and look up the index of those numbers.
The k-NN algorithm should still be at least O(n) (I think?)
Simple random sampling is O(1), with respect to the total number of table rows.
Is the problem that you want exactly three rows, and some numbers will be rejected if you don't re-index? SQL can manage while loops:
if you have thousands of rows, it doesn't really matter if one is 3 times as likely to show up as another one, as long as the odds aren't stacked too heavily towards any one row (at least for what I assume to be the typical use case of showing users a random product/page/whatever)
I understand that SQL is considered simpler if you have code-golfed it into one line, but the procedure of simple random sampling is much simpler than generating a 2D map of points and finding the nearest one.
Points inside a cluster of other points will be less likely to be picked than points that are in a relatively empty region of space.
You can fix this by looping the space around once you reach the edge but good luck expressing that in SQL.
You could also fix it by putting them on a sphere I think, though picking a random point on a sphere is exactly the easiest thing to do.
I think using a range of rows is overkill, at least for row-stores. And also in the majority of cases random rows are preferred than a range.
In the case where the table has a simple Primary Key the query is easier. Select all the valid PKs (rows) ordered by random and then limit.
SQLite gives access to the rowid making this query even simpler and likely faster (no need for PK and the query works on tables without a PK).
SELECT * FROM test
WHERE rowid IN
(SELECT rowid FROM test
ORDER BY random() LIMIT 10);
SELECT * FROM test JOIN
(SELECT rowid as rid
FROM test ORDER BY random() LIMIT 10) AS srid
ON test.rowid = srid.rid;
If your table is truly big, say billions of rows, this could be improved by reducing the list of rowids with a WHERE clause.
But don't overdo it or you'll affect the truer randomness. For most cases just reduce to hundreds of thousands.
For whatever reason, using this filtered (WHERE), the JOIN query to generates a seemingly better SQLite plan.
SELECT * FROM test JOIN
(SELECT rowid as rid FROM test
WHERE random() % 10 = 0 -- Reduce rowids
ORDER BY random() LIMIT 10) AS srid
ON test.rowid = srid.rid;
2. To truly random sample k out of a set of n rows it's needed to know the set first.
3. Walking the rowid B-Tree should be relatively fast (and necessary because of 2.)
It may be the case a sub-range is good enough (e.g. the table is quite disordered relatively to the properties looked after). But this is very unusual and you should warn the users of this data because later on they might change
Imagine your sub-range picks rows created over the weekend or some other particular time-frame. Or an import from some other legacy system. This will not be representative of the full set in many ways.
If the system needs to do a lot of sampling queries, perhaps it would be better to make overnight an auxiliary table. You can make many sample tables and compare which ones deviate less from the actual table. This table will be small and could even have materialized views pre-computed with the most expensive computations.
import numpy as np
import matplotlib.pyplot as plt
n = 10_000_000
np.random.seed(0)
a = np.random.random([n])
a.sort()
b = np.append(a[1:] - a[:-1], 1 + a[0] - a[-1])
plt.hist(np.log10(b), bins=100)
plt.show()
Not that it would be too surprising, since the behavior is a general property of the (ermph… Laplace? Poisson? oh, whatever) distribution, right? Still, I made this histogram for the real probabilities of Wikipedia articles (for enwiki and my home cswiki) and it turned out to look the same (meaning the random number generator is not obviously superbad), see https://gist.github.com/mormegil-cz/84d0cc34eb5f1234be8966f7...