last time i looked into this exact problem for mysql this is the best approach i found, and ended up going with. unfortunately the intuitive solutions are not always as good with sql as more convoluted ones. Another common one is e.g. limit pagination vs range offsets, where the former must unfortunately load all rows preceding the page you want, and the latter can just do an index-based lookup.
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)
It doesn't make any sense at all. Draw the Voronoi diagram; the cells will be of non-uniform size, so some points are much more likely to be picked than others. And why is this 2D? 2D doesn't give you any more randomness than 1D, it's just obfucscation.
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 the best randomness that is achievable i am aware of. Do you have ideas for improvements?
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.
If you want quality randomness you can always do some equivalent of ORDER BY RAND() as long as you get a new RAND() for each row.
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.
This already has the same problems as #2, but worse;this already has uneven distribution from the beginning, even without deletions.
Perhaps it may be worth pointing this out: you mention that this creates a "perfect random distribution" but that "with only a few records the distribution is not as perfect". This is a misconception; this perceived imperfection, the clumps etc, that's what random points always look like. The size of the voronoi cells, which determine the probability of a point to be sampled, are of very different sizes here.
What you are thinking of is a random distribution of points where the points will have somewhat uniform distance to their neighbors. This is called blue noise. Creating scattered points with blue noise properties in 2d is not very complicated, but it is a bit more complicated than just combining two uniform random values. FWIW, uniform randomness does not even have blue noise properties in 1d, perhaps much more obviously.
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.
The benefit of this solution is that we don't want to depend on SQL to generate unlimited random numbers: one for each row of the table is a lot of work.
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:
i think mostly because this is even more complicated than the approach taken, and the proposed solution is good enough. If you do have large gaps in your dataset you can also account for them by just blocking a range of numbers ahead of time, optionally with a monthly cron job to identify new gaps larger than X rows, depending on how often new such gaps form.
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 think mostly because this is even more complicated than the approach taken
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.
I guess you have a point there. My gut instinct was that it'd be more complicated to understand/modify but thinking about it a bit more I don't think that's really necessarily the case. And even with much more rows being filtered out than being included in the predicate, it would take looking at the same amount of rows on average (I think) to find the desired amount of results. It might be worse if there's significantly more deleted rows than existing ones, though.
Unfortunately, it's impossible to do true uniform random over set of rows without doing something like count() over the things you are sampling over. You are looking to select something with probability 1/n, where n is the number of rows, so you must somehow, possibly implicitly, compute n, which is the count. So you'll always end up with at least O(n) assuming you have no pregenerated structure before running the query.
Wouldn't you typically solve this kind of problem with rejection sampling? Pick a random ID - if it's already in the result set or deleted, try again. I suppose this cannot be neatly expressed in SQL though?
I think this is a good approach and I see a few ways to make it even better. First you could overfetch to reduce risk of needing another query. Secondly you could rewrite ids occasionally to reduce gaps.
Generate a temp table with a sufficient number of random values and join. Add an ORDER BY RANDOM() to those results to subsample.
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.
What you could do if you have lots of queries and few updates is maintain a table mapping 1-n to your rows. If you delete row k with 1<=k<n you would need repoint k to whatever n pointed to, and delete n. So it needs some transactions to make it work.
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);
or with a more verbose JOIN:
SELECT * FROM test JOIN
(SELECT rowid as rid
FROM test ORDER BY random() LIMIT 10) AS srid
ON test.rowid = srid.rid;
The database engine tracks existing rows by some sort of id with its own internal rowid/PK index structure. Materializing these IDs should not be that expensive and as it's sequential access it should be pretty fast. The expensive part is the ORDER BY random().
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;
The manual '% 10' filter could be improved with some calculation of the table's row count, minding small tables. Left as exercise.
For every pf your examples the database will do a full table scan. If i am wrong feel free to correct me. But i tried multiple approaches more than the ones discussed and as soon as you start using random() the database will scan every record.
1. Picking a random sub-range is not the same thing as random sampling. See other comments here and all over the Internet.
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.
It's not neglible at all. I generated 10 million uniform numbers and made a histogram of the log10(probability) - there are dramatic differences in probability for different pages. Now, since the random page is just for fun, that may be considered acceptable.
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()
Some highlights: The lowest probability page had a mere 1e-14 chance, while the highest had a 1e-6. The 90th percintile was 20 times more likely than the 10th.
Yeah, right, that’s what I considered “acceptable” for such a fun-only functionality, I guess.
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...
36 comments
[ 4.0 ms ] story [ 156 ms ] threadEdit: 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:
https://dev.mysql.com/doc/refman/8.0/en/while.html
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.
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.
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.
https://news.ycombinator.com/item?id=27088101
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).
or with a more verbose JOIN: The database engine tracks existing rows by some sort of id with its own internal rowid/PK index structure. Materializing these IDs should not be that expensive and as it's sequential access it should be pretty fast. The expensive part is the ORDER BY random().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.
The manual '% 10' filter could be improved with some calculation of the table's row count, minding small tables. Left as exercise.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.
https://imgur.com/a/WBLh3kQ
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...