Don't all databases support efficient TABLESAMPLE with a number of rows? Postgres probably does.
Tablesample is not accurate as far as I remember.
I googled around, it isn't it gets complete pages with multiple rows so it tends to clump.
How to Optimize Order by Random()
11–20 of 37 posts
Re: How to Optimize Order by Random()
#12Earlier quoted context omitted.
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 suc…
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.
Re: How to Optimize Order by Random()
#13Earlier quoted context omitted.
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 suc…
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.
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.
Re: How to Optimize Order by Random()
#14Wouldn'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.
Re: How to Optimize Order by Random()
#15What 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.
Re: How to Optimize Order by Random()
#16This not a random selection. It has the same issues as the 1-dimensional case, and will not sample uniformly.
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.
Re: How to Optimize Order by Random()
#17Edit: https://gist.github.com/alecco/9976dab8fda8256ed403054ed0a65...
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;
Re: How to Optimize Order by Random()
#18Wouldn'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?
Depends on how big a percentage of the set you're planning to pick but yeah that would work.
Re: How to Optimize Order by Random()
#19This not a random selection. It has the same issues as the 1-dimensional case, and will not sample uniformly. 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.
It's not about the randomness of the results, it's about optimizing the speed of the original query.
Re: How to Optimize Order by Random()
#20This not a random selection. It has the same issues as the 1-dimensional case, and will not sample uniformly. 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.
Not to mention that points near the edge are 50% less likely to be picked (or 75% less likely if they're near a corner).
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.