Hacker News Reader

Comment by timr | Hacker News Reader

Author here.

Yes, reservoir sampling is O(N), but my point there was that it doesn't require instantiating every record at once. Also, the cost of the random number generation isn't the big deal in an ORDER BY RANDOM() implementation -- it's that even the smart implementations end up doing multiple table scans. So even at O(n) this probably beats most implementations of that approach, in practice.

Reservoir sampling is appropriate with more than just a set of unknown size -- you very frequently know the size of a set, but it's still too big to sample directly. But yes, if your sets are small, you have a lot of options.

View on HN

While good in theory, it's often really slow in practice as even small sample sets can trash your cache and it still needs a random number for every element.

You can make a better approach using a much longer list, but then the math is far less elegant. EX: Add the first X * N elements to the list. Then remove 1/X of them. Then 1/X of the times add an element to the list until it’s full. Cull 1/X of them and then add new elements (1/X)^2 of the time. Repeat until you run out of elements at which point you cull the list back to X elements.

Downside is your generating ~N log N random numbers so scanning the list and then sorting a random set may be faster.

If you have an approximate number elements AND want a small percentage of them then randomly generate X * N element list which is then culled to an N element list.

Finally, if N happens to be close to the full number of elements you’re better off creating an exclusion list.

PS: Reservoir Sampling is only good if your memory constrained, need a constant time algorithm, and generating random numbers is expensive.

If you know the size of the set, then you can generate a random set of (non-duplicate) indices, and use those to fetch data.

Offhand I'm not sure how to do that in SQL, since data isn't usually fetched by index (unless the row has an explicit index key). Worst-case you could iterate over the rows just as you do with reservoir sampling, and it would still be faster (since you aren't generating tons of random numbers and doing a lot of array manipulation). Or you could do one query fetching just the primary key, record the keys of the indices you're interested in, and then do a second query to fetch that set. Or maybe SQL does have some way to fetch by index after all.

Yeah - unfortunately there isn't a great way to select n random rows in standard SQL.

If you have an integral primary key, you could select its max and generate random numbers up to that. Continuity isn't guaranteed so you would need to check for nonexistent primary keys in addition to checking for duplicates.

If there's no integral primary key, then there's no standard SQL solution faster than O(n).

If N is sufficiently larger than k, it might actually be faster to do something like

  let count = query("SELECT COUNT() FROM table")
  let indices = computeIndices(count, k)
  for index in indices {
    results.append(query("SELECT * FROM table LIMIT 1 OFFSET ?", index))
  }

Yeah, you're doing a bunch of queries, but you're removing all of copying all the data from all the rows.

OFFSET j is O(j) in most RDMSes. You made an o(N/2 * k) algorithm given j is a random number in [0,N).

Depending on the size of k compared to N, and how much data is in each row, it's still probably better than iterating over the entire contents of the table.

Also, do you have any citation for OFFSET j being O(j)? I can believe that's the case, but it also seems fairly obvious to optimize OFFSET for the case of a non-filtered unordered SELECT (or one ordered in a way that matches an index).

Assuming that the DB is backed by some kind of tree, it would need to maintain extra metadata in the branches in order to achieve even O(log n) offsetting. For this reason I could understand it being a linear operation.

My first solution would have been getting a count, maybe a cached count and just doing random between 0 and that count, fetching by index? Or if you want more than one, just get a slice? Probably not the best, but at the top of my head.

I might be misunderstanding something, but this seems much more complex than systematic sampling, which is well understood even in the case where the number of records (read: population size) is unknown (this situation occurs in quality control on an assembly line).

Can anyone comment on why this reservoir method would be a better choice than the old fashioned systematic sample? (which, BTW, only requires the generation of one random number to determine the starting record).

>>Reservoir sampling is appropriate with more than just a set of unknown size -- you very frequently know the size of a set, but it's still too big to sample directly.

I'm not sure that I buy this...Do you have an example? Still, it is a neat algorithm. And it is a true stream query algorithm, that is, if you have an open-ended stream, it maintains a random sample at all times.

Deleted comment

If you have N locations with known addresses and you can select a sample of k from those addresses randomly with uniform probability, then sure, do that.

But there are lots of situations where you don't have that: say, you're sampling from a database join, or you're just using a table that has non-contiguous id values (e.g. a table with deletions). Or, in the case of truly "Big Data", you have the data spread over multiple machines. In these cases, you need an approach suitable for when you don't know the size of the stream, you can't load it all into memory and/or you can't select randomly from an address pool.

Sorry, I deleted this comment immediately after posting but you managed to respond to it too quickly, it originally said:

>Having a large input set of known size (and your result set is not large) is not a time when you would want to use reservoir sampling. Such a problem can be solved in O(k) where k is the size of the result set, while reservoir sampling is O(n) where n is the size of the input set.

and I have responded here: https://news.ycombinator.com/item?id=9158903

doesn't your implementation require you to fetch all data into the client process for ruby to iterate over?

isn't the movement of such data -- when you have billions of rows simply impossible in reasonable time?

This implementation is useful at some scales, but not all: it uses find_each to iterate over the ActiveRecord scope, which is going to be slower than doing it all in the database (if that's possible), but still way better than instantiating every record in a large table.

(find_each instantiates a few records at a time, then throws them away)

it will, in general, instantiate N-n/N records (even distribution, right - N=total records, n=sample size) that is still too much data to fetch to the client for any large data set.

You don't have to instantiate the records; that's just the way I did it here. For example, you could do two passes: one to randomly select IDs, and one to fetch a small number of records for the sample set. That's O(2N), but still better than what most databases will do for an ORDER BY RANDOM() query.

There's also another, less-known variant of this algorithm that I'll go into in a future post that alleviates the concern.

Reply on news.ycombinator.com