Let's reframe a problem we had from earlier. We have a very large set which we computed to match a query. The set contains possibly millions of documents. We want to return the elements of the set in an order that corresponds to a field of each document, an order that does not necessary match the order of its document IDs.

One way we could do this would be to simply load the field for each document and then perform a conventional sort, like Heapsort. Heapsort would even be particularly efficient on very large sets for producing a small number of top documents, since it could be stopped after a few iterations

But loading the field values for all of the documents could be a rather expensive and memory-intensive operation. For a set with 12 million documents, if the field value is a 32-bit integer, then each query would require processing around 48MB of data. That isn't at all free to look up.

The algorithm

We can use our ability to perform range queries using the bitmap trees discussed in the previous article to flip this sorting problem on its head. Given a query result set with 12 million documents, if we pick a random set bit, and find its field value, we can use the bitmap tree to collect the set of all documents greater than the pivot.

Let's build a tree datastructure we can use for this purpose. We'll be using Roaring Bitmaps for their optimized implementation, and start by defining all of the structures we will need.

struct bitmap_tree_node {
    uint64_t min_value;
    union {
        roaring_bitmap_t *bitmap_union;
        uint32_t single_document_id;
    };
    bool is_leaf;
};

struct bitmap_tree_level {
    uint32_t num_nodes;
    struct bitmap_tree_node *nodes;
};

struct bitmap_tree {
    uint32_t num_nodes;
    uint32_t num_levels;
    uint32_t branch_factor;
    struct bitmap_tree_level *levels;
};

Now, let's implement an algorithm to select all documents greater than a given value. We will walk backwards through the nodes of the tree and insert all documents from their bitmap unions, until we find a node that is no longer greater than value. We then stop, and recurse into the next level of the tree, where we repeat until we get to the bottom or run out of nodes.

roaring_bitmap_t *select_gte(struct bitmap_tree *tree, uint64_t value)
{
    roaring_bitmap_t *bitmap = roaring_bitmap_create_with_capacity(0);
    int32_t start_pos = 0;

    for (int32_t i = tree->num_levels - 1; i >= 0; i--) {
        struct bitmap_tree_level *level = &tree->levels[i];
        int32_t level_length = level->num_nodes;
        int32_t end_pos = min(start_pos + tree->branch_factor, level_length);
        int32_t j = end_pos - 1;

        for (; j >= start_pos; j--) {
            if (level->nodes[j].min_val < value) {
                // At this point we are no longer considering nodes in the tree
                // less than the comparison value, so stop advancing at this level.
                break;
            }

            if (level->nodes[j].is_leaf) {
                // Leaf nodes directly contain document ids.
                roaring_bitmap_add(bitmap, level->nodes[j].single_document_id);
            } else {
                // Non-leaf nodes contain a bitmap union.
                // We will use to to gather all documents under this node.
                roaring_bitmap_or_inplace(bitmap, level->nodes[j].bitmap_union, 0);
            }
        }

        if (j < start_pos) {
            // We are walking backwards.
            // At this point we already consumed the entire tree, so stop.
            break;
        }

        start_pos = j * tree->branch_factor;
    }

    return bitmap;
}

Given the set of all documents greater than the pivot, we can then intersect with our query result set to produce all documents matching the query AND greater than the pivot. On average, we expect this to cut the number of documents to consider in half. This allows us to implement Quickselect using only bitmap operations.

The benchmarks

In this benchmark, I compare the performance of the professional search engine Elasticsearch to a very naive implementation of the sorting algorithm described in the past few blog posts.

1.2 million documents as images tagged safe from Derpibooru are loaded, and then sorted by their creation date. This is executed on an Intel i7-4790K, and represents the best of 50 runs for each.

The results speak for themselves. Execution of the search and sort is so much faster—more than a full order of magnitude—it makes Elasticsearch look quite slow in comparison. To be fair, Elasticsearch is designed for text search, where none of these techniques apply, but there is no other suitable database which can efficiently execute tagged queries.