Optimizing Reads on Large MongoDB Collections

Introduction

When working with large MongoDB collections holding tens of millions of records, there was a need to build random samples of unique field values belonging to the documents in such a collection.

MongoDB ships with the $sample function for this operation; it can be used as part of an aggregation pipeline. There is also an option based on the $skip operator. In practice, though, sampling fields this way on a large collection takes a noticeable amount of time, with either approach.

To cut the time these samples take, a custom algorithm had to be developed — one that sped the work up by orders of magnitude. The approach and an implementation of that algorithm follow.

Source data

Take an email database that stores, among other fields, the email address and the subject of the message, with roughly 800,000 documents.

A typical document stored in MongoDB looks like this standard JSON:

{
  "_id": {
    "$oid": "6461f8cbd2b81e62fcfo54ca"
  },
  "mail": "[email protected]",
  "subject": "The road to book lovers",
}

The system field "_id" in this document is generated automatically when the document is added to the collection. Note that this field is always indexed by default, and its value is computed by strictly defined rules that make it unique within the database.

According to MongoDB's documentation, the "_id" value is a BSON ObjectID and consists of three parts:

• A 4-byte generation timestamp, expressed in Unix epoch seconds.
• A 5-byte random number, generated once for the worker process that adds the document to the collection.
• A 3-byte counter, initialized randomly.

Figure 1 shows sample values for a test collection.

The figure shows that a single process built the collection: documents were written in one stream (the timestamps are evenly spaced) and the counter increments by one for each document.

Experiments showed that when the process changes, both the process identifier and the counter's starting value change. So the only value that remains consistently sequential is the time field.

However, if documents are added to the collection irregularly, gaps appear in that field. For example, Figure 1 gives statistics for a database holding about 100,000,000 records (in Figure 2 the time field has been converted to UNIX time).

The figure shows that the table was populated in three phases at different times, leaving gaps in the pseudo-monotonic sequence of document timestamps.

Note that in large tables the "counter" field takes on every value from 000000 to ffffff (see Figure 2), which is entirely logical.

Given this, a random sample can be built from the segment of the _id field that corresponds to the time the document was added to the collection.

Because that segment sits in the high-order digits of the "_id" value, the index the DBMS creates by default for this field will handle selection of values for this segment correctly.

Algorithm for regularly populated collections

A simple algorithm for randomly selecting a few OIDs can look like this:

1. Find the minimum (min_oid) and maximum (max_oid) ObjectID values and generate a random value (rand_oid) between them.
2. Find the real ObjectID in the collection being processed that is closest to the generated value.
3. Check whether such a rand_oid has been found before; if it has, generate a new random value and repeat the OID selection step.
4. Repeat the procedure the required number of times.

The algorithm works correctly for collections where records are added regularly rather than in large batches separated by long gaps (as in the example in Figure 2), and in some cases this simple algorithm is enough. Still, if the pseudo-monotonic sequence of timestamps contains gaps, a random number drawn across the full range will often land in those gaps, so this property of the collection should be taken into account.

What can be done about this?

Algorithm accounting for time gaps

Roughly speaking (not to scale), a collection with gaps can be pictured like this (see Figure 3):

If the generated value lands in the "milk" (an empty gap), the closest real document identifiers will be the identifiers of documents at the edges of the ranges. The processes that placed those documents in the database will most likely be different. This difference is used as the signal for detecting a landing in "milk":

1. Take a random rand_id and find the real document ObjectID to its left (MongoDB's $lt operator) and to its right ($gt).
2. Check whether the process identifiers of the found documents match. If they do not, these are the boundary documents of the ranges. In that case, generate a new random rand_id in the range that lies between the edge (start or end) of the overall range and the found boundary document.
3. Repeat the check and narrow the range for generating rand_id until the value lands in the "green" (a filled segment of the collection), which is indicated by matching process identifiers on the real ObjectIDs to the left and right of rand_id.
4. Add the found real ObjectID (either the "left" one, the "right" one, or both) to the resulting set.

Implementation and testing

First, run an experiment that builds samples of email addresses and measure how long it takes.

Of the specific modules needed for testing, only the standard pymongo module is required; it can be downloaded from a public repository.

To measure execution time, it is convenient to use a decorator that supplements the result of any Python function with its runtime.

def timer(func):
    def _wrapper(*args, **kwargs):
        start = time.perf_counter()
        result = func(*args, **kwargs)
        runtime = time.perf_counter() - start
        print(f"{func.__name__} took {runtime:.4f} secs")
        return result
    return _wrapper

First, write a function that finds a random ObjectID:

def get_random_objid(min_oid, max_oid):
    """
    The function generates a random ObjectID within the range
    """
    f = str(min_oid)[:8] # take the first 8 characters, which correspond to the record timestamp
    l = str(max_oid)[:8]
    fn = int(f, 16)
    ln = int(l, 16)
    random.seed()
    r = random.randrange(fn, ln)
    rand_oid = ObjectId("".join([hex(r)[2:],"0000000000000000"]))
    return rand_oid

One note: for generation it makes sense to set only the ObjectID digits that correspond to the timestamp, that is, the first 4 bytes of the identifier.

To use the function, the minimum and maximum identifiers marking the time boundaries of the collection being processed are needed; they can be computed as follows:

# MongoClient(used_connection)["tmp"]
min_oid = list(coll.find().sort("_id", 1).limit(1))[0]["_id"]
max_oid = list(coll.find().sort("_id", -1).limit(1))[0]["_id"]

Sorting with the "-1" parameter orders the collection from the larger identifier value to the smaller one.

Below is a function that finds the identifiers of real documents in the collection located to the left and right of a randomly found identifier, plus a function that splits an identifier into its logical parts — "Time", "Process", "Counter".

def trim_objid(obj_id):
    s = str(obj_id)
    return {"id":obj_id, "time":s[:8],"proc":s[8:18], "counter":s[18:]}

def get_near_oid(coll, reference_oid):
    left = list(coll.aggregate([{"$sort": {"_id": -1}},
                                {"$match": {"_id": {"$lte": reference_oid}}},
                                {"$limit":1}]))
    if not left:
        left = [coll.find_one()]
    right = list(coll.aggregate([{"$match": {"_id": {"$gte": reference_oid}}},
                                 {"$limit":1}]))
    if not right:
        right = list(coll.aggregate([{"$sort": {"_id": -1}}, {"$limit":1}]))

    return {"left":trim_objid(left[0]["_id"]), "right":trim_objid(right[0]["_id"])}

When it runs, the nearest-identifier lookup function get_near_oid returns roughly this result:

{'left': {'id': ObjectId('6461f8cdd2b81e62fcf16ffd'),
          'time': '6461f8cd',
          'proc': 'd2b81e62fc',
          'counter': 'f16ffd'},
 'right': {'id': ObjectId('6461f8ced2b81e62fcf16ffe'),
           'time': '6461f8ce',
           'proc': 'd2b81e62fc',
           'counter': 'f16ffe'}}

In this example, the process identifiers ("proc") of the "right" and "left" IDs match, meaning the generated value landed in the "green" — a real segment of the collection — rather than "milk", a gap, and the resulting identifier can safely be taken for inclusion in the set.

The function that returns "valid" identifiers from the real blocks of the collection looks like this:

def get_inline_oids(coll):
    min_oid = list(coll.find().sort("_id", 1).limit(1))[0]["_id"]
    max_oid = list(coll.find().sort("_id", -1).limit(1))[0]["_id"]
    rand_oid = get_random_objid(min_oid, max_oid)

    # find the identifiers of the documents located to the left and right of the reference one
    gap = get_near_oid(coll, rand_oid)

    while gap["left"]["proc"] != gap["right"]["proc"]:
        rand_oid = get_random_objid(min_oid, gap["left"]["id"])
        gap = get_near_oid(coll, rand_oid)
        if gap["left"]["proc"] != gap["right"]["proc"]:
            rand_oid = get_random_objid(gap["right"]["id"], max_oid)
            gap = get_near_oid(coll, rand_oid)
    print(gap)
    return {gap["left"]["id"], gap["left"]["id"]}

Finally, put together the last function, which returns the required number of random identifier values, and decorate it with the execution-time handler.

Here is also the standard function for sampling random values, for a later performance comparison.

Then run a test on samples of different lengths: 5, 10, 50.

@timer
def get_sample_oids(coll, count=1):
    oids = set()
    while len(oids) < count:
        oids = oids.union(get_inline_oids(coll))
    if len(oids) != count:
        oids.pop()
    return oids

@timer
def get_samples_standard(coll, count=1):
    res = list(coll.aggregate([{"$sample": {"size": count}},{"$project":{"_id":1}}]))

    return {value["_id"] for value in res}

for i in [5,10,50]:
    print("Collection size: {}, sample size: {}".format(coll.estimated_document_count(), i))
    get_sample_oids(coll,i)
    get_samples_standard(coll,i)

The run produces the following results:

Collection size: 102316457, sample size: 5 get_sample_oids took 0.0247 secs get_samples_standard took 2.9753 secs Collection size: 102316457, sample size: 10 get_sample_oids took 0.0495 secs get_samples_standard took 3.2230 secs Collection size: 102316457, sample size: 50 get_sample_oids took 1.5310 secs get_samples_standard took 3.2344 secs

For small samples, the speed differs by two orders of magnitude — that is very good indeed.

This code is of course not perfectly optimized, which shows on larger samples. Time is spent avoiding gaps, and landing in a gap means searching for a new identifier all over again.

If the algorithm is improved so that gaps found once are remembered and excluded from further random identifier selection, the speed will hold up on large samples too.

Also, this whole hassle with random samples can stop being a problem altogether if, from the start, documents added to a MongoDB collection are given a custom unique incremental identifier instead of the default one.

But... life happens, and every approach has a right to exist. That goes for this algorithm too.

:)