How do I load a random document from CouchDB (efficiently and fairly)?

After giving this some more thought, I came up with a solution. For completeness sake, I will first show two simple approaches and explain why they are flawed. The third solution is the one I'm going with.

Approach 1: Skip

This is the trivial solution: You have a simple view (let's call it random) with a map function that emits all documents you want to choose from and the built-in _count reduce function. To pick a random document, follow these steps:

  • Find the total number of documents N in the view by calling:
    http://localhost:5984/db/_design/d/_view/random
  • Pick random number 0 <= i < N
  • Load the i'th document:
    http://localhost:5984/db/_design/d/_view/random?reduce=false&skip=i&limit=1

This approach is bad because it doesn't scale well for large numbers of documents. According to this section of "CouchDB - The Definitive Guide" the skip argument should only be used with single-digit values.

The solution above would have to loop through i documents before returning the chosen one. In SQL terms it's the equivalent of a full table scan as opposed to an index lookup.

Approach 2: Random Number in Document

With this approach, a random number is generated for each document at creation time and stored in the document. An example document:

{
  _id: "4f12782c39474fd0a498126c0400708c",
  rand: 0.4591819887660398,
  // actual data...
}

The random view then has the following map function:

function(doc) {
  if (doc.rand) {
    emit(doc.rand, doc);
  }
}

These are the steps to pick a random document:

  • Pick a random number 0 <= r < 1
  • Load the document:
    http://localhost:5984/db/_design/d/_view/random?startkey=r&limit=1
  • If no document is returned (because r is larger than the largest random number stored in the database), wrap around and load the first document.

This is very fast and looks great at first sight. However, there's a serious flaw: not all documents have the same chance of being picked.

In the most simple example, there are two documents in the database. When I choose a random document a very large number of times, I want each document to come up half of the time. Let's say the documents were assigned the random numbers 0.2 and 0.9 at creation time. So document A is picked when (r <= 0.2) or (r > 0.9) and document B is chosen when 0.2 < r <= 0.9. The chance of being picked is not 50% for each document, but 30% for A and 70% for B.

You might think the situation improves when there are more documents in the database, but it really doesn't. The intervals between documents get smaller, but the variation in interval size get's even worse: Imagine three documents A, B and C with the random numbers 0.30001057, 0.30002057 and 0.30002058 (no other documents are in between). The chances of B being chosen are 1000 times greater than C being chosen. In the worst case, two documents are assigned the same random number. Then only one of them can be found (the one with the lower document id), the other is essentially invisible.

Approach 3: A combination of 1 and 2

The solution I came up with combines the speed of approach 2 with the fairness of approach 1. Here it is:

As in approach 2, each document is assigned a random number at creation time, the same map function is used for the view. As in approach 1, I also have a _count reduce function.

These are the steps for loading a random document:

  • Find the total number of documents N in the view by calling:
    http://localhost:5984/db/_design/d/_view/random
  • Pick random number 0 <= r < 1
  • Calculate random index: i = floor(r*N)
    My goal is to load the i'th document (as in approach 1). Assuming the distribution of random numbers is more or less uniform, I'm guessing the i'th document has a random value of approximately r.
  • Find the number of documents L with a random value lower than r: http://localhost:5984/db/_design/d/_view/random?endkey=r
  • See how far off our guess is: s = i - L
  • if (s>=0)
    http://localhost:5984/db/_design/d/_view/random?startkey=r&skip=s&limit=1&reduce=false
  • if (s<0)
    http://localhost:5984/db/_design/d/_view/random?startkey=r&skip=-(s+1)&limit=1&descending=true&reduce=false

So, the trick is to guess the random number assigned to the i'th document, look that up, see how far we're off and then skip the number of documents by which we missed.

The number of documents skipped should remain small even for large databases, since the accuracy of the guess will increase with the number of documents. My guess is that s remains constant when the database grows, but I haven't tried and I don't feel qualified to prove it theoretically.

If you have a better solution, I'd be very interested!


How about "abusing" a view's reduce function?

function (keys, values, reduce) {
    if (reduce)
      return values[Math.floor(Math.random()*values.length)];
    else
      return values;
}

If insert performance is not an issue you could try to make number non random e.g. make it doc_count + 1 at the time of creation. Then you could look it up with a random number 0 <= r < doc_count. But that would either require to synchronize the creation of documents or have sequence external to couchdb, e.g. an SQL database.

Best regards

Felix

Tags:

Random

Couchdb

Recent Posts