4 ms·

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

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: https://dev.mysql.com/doc/refman/8.0/en/while.html https://dev.mysql.com/doc/refman/8.0/en/while.html

asddubs 5y ago
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)
- teachingassist 5y ago
  > 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.
  - asddubs 5y ago
    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.

asddubs 5y ago

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)

teachingassist 5y ago
> 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.
- asddubs 5y ago
  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.