How to Optimize Order by Random()
tpetry.me
How to Optimize Order by Random()
1–10 of 37 posts
Re: How to Optimize Order by Random()
#2The best solution in this article seems quite convoluted and not very portable. Is there a better way?
Edit: I doubt it’s uniform as well because rows at the edges are less likely to be selected.
Re: How to Optimize Order by Random()
#3Don't all databases support efficient TABLESAMPLE with a number of rows? Postgres probably does.
Re: How to Optimize Order by Random()
#4The best solution in this article seems quite convoluted and not very portable. Is there a better way? Edit: I doubt it’s uniform as well because rows at the edges are less likely to be selected.
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)
Re: How to Optimize Order by Random()
#5Don't all databases support efficient TABLESAMPLE with a number of rows? Postgres probably does.
Tablesample is not accurate as far as I remember.
Re: How to Optimize Order by Random()
#6The best solution in this article seems quite convoluted and not very portable. Is there a better way? Edit: I doubt it’s uniform as well because rows at the edges are less likely to be selected.
Your randomness may also sometimes be at the edge. I am the author of the article, if you do know any failure in my approach i am happy to fix it.
Re: How to Optimize Order by Random()
#7The best solution in this article seems quite convoluted and not very portable. Is there a better way? Edit: I doubt it’s uniform as well because rows at the edges are less likely to be selected.
Your randomness may also sometimes be at the edge. I am the author of the article, if you do know any failure in my approach i am happy to fix it.
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.
Re: How to Optimize Order by Random()
#8Earlier quoted context omitted.
Your randomness may also sometimes be at the edge. I am the author of the article, if you do know any failure in my approach i am happy to fix it.
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.
Re: How to Optimize Order by Random()
#9Wouldn'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?
Re: How to Optimize Order by Random()
#10The best solution in this article seems quite convoluted and not very portable. Is there a better way? Edit: I doubt it’s uniform as well because rows at the edges are less likely to be selected.
Your randomness may also sometimes be at the edge. I am the author of the article, if you do know any failure in my approach i am happy to fix it.
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: