Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How to Optimize Order by Random()

tpetry.me

Post reply on HN
Print view View original

31–37 of 37 posts

Re: How to Optimize Order by Random()

#31

Post by alecco »

tpetry wrote: post #25
alecco wrote: post #17

Edit: 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…

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.

Re: How to Optimize Order by Random()

#32

Post by im3w1l »

mormegil wrote: post #27

In MediaWiki, the "Random page" function works using an indexed page_random column, see https://m.mediawiki.org/wiki/Manual:Page_table#page_random For a large enough wiki, the potential non-uniformness is negligible, I guess. (Unless your RNG is wrong, see https://phabricator.wikimedia.org/T208909 )

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.

https://imgur.com/a/WBLh3kQ

Re: How to Optimize Order by Random()

#33

Post by nine_k »

MauranKilom wrote: post #9

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?

> try again

This where you can spend a surprising amount of time unpredictably.

Having a pre-shuffled array helps much more.

Re: How to Optimize Order by Random()

#35

Post by asddubs »

teachingassist wrote: post #28
asddubs wrote: post #24

Earlier quoted context omitted.

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…

> 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.

Re: How to Optimize Order by Random()

#36

Post by alecco »

credulousperson wrote: post #30
Bootvis wrote: post #2

The 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.

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 qu…

Exactly. And in case of SQL, it's worse because some rows may have been deleted so you can't even count of id (or rowid) to be contiguous.

Re: How to Optimize Order by Random()

#37

Post by mormegil »

im3w1l wrote: post #32
mormegil wrote: post #27

In MediaWiki, the "Random page" function works using an indexed page_random column, see https://m.mediawiki.org/wiki/Manual:Page_table#page_random For a large enough wiki, the potential non-uniformness is negligible, I guess. (Unless your RNG is wrong, see https://phabricator.wikimedia.org/T208909 )

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] -…

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...

Post reply on HN