+972 52-548-6969
Deep in the heart of Corax (RavenDB’s querying engine), everything deals with something called a Posting List. Posting Lists are a way for the engine to say “all of those documents have the term Fast for the field Speed”. Conceptually, a Posting List is an ordered set of document ids. In this case (and this is important, the ids in question are numeric, not RavenDB’s document id, which is a string).
An interesting problem with Posting Lists is that a term can be unique (such as a GUID) - only a single document will ever have this value. They can have a small set of values (for example, CreationDate, where only the items created on that day will share the same value). Or they can have many values (for example, Status = ‘Shipped’ for Orders).
The reason those details matter is that we can deal with the three (very) different modes in a distinct manner to reduce the cost of storage that Corax uses for Posting Lists. Internally, Corax has the notion of a PostingListId, which is just a 64-bit number. We use the least significant 2 bits to tell us what kind of Posting List this is.
Typical code to consume this looks like this:
while ((read = provider.FillPostingListIds(plIds)) > 0)
{
for (int i = 0; i < read; i++)
{
var postingListId = plIds[i];
var termType = (TermIdMask)postingListId & TermIdMask.EnsureIsSingleMask;
switch (termType)
{
case TermIdMask.Single:
{
// Accumulate the single decoded entry ID into the entryBuffer
// Flush to bitmap if the buffer is full
break;
}
case TermIdMask.SmallPostingList:
{
// Decode inline via FastPForBufferedReader into the entryBuffer
// Flush to bitmap if the buffer is full
break;
}
case TermIdMask.PostingList:
{
// Flush any accumulated entries from the buffer first
// Iterate through the full large posting list via FillFromPostings
break;
}
default:
throw new InvalidOperationException($"Unknown TermIdMask type: {termType}");
}
}
}The code here iterates through a list of Posting List ids, handling each one of the options. This is part of handling queries such as: where CreatedAt > $lastQuarter. We have to get all the distinct dates in the range, and for each date, we need to get all the matching documents for it.
The code here is pretty simple, right? It is fairly obvious what it does, but it has a pretty big problem. It processes each one of the Posting Lists manually & separately. There are two problems with this approach:
- We end up doing a lot of branching, based on which Posting List type we are processing.
- We lose the ability to handle the Posting Lists in bulk.
Because we use the lowest two bits to store the type of the Posting List, we can do better. The insight behind the new approach is that (id & EnsureIsSingleMask) naturally yields 0, 1, or 2 — a perfect index into an array of buckets. Instead of a switch statement, we partition the batch in one pass with no per-item branches:
var buckets = new List<long>[3];
while ((read = provider.FillPostingListIds(plIds)) > 0)
{
for (int i = 0; i < read; i++)
{
buckets[(int)(plIds[i] & 0b11)].AddUnsafe(pid);
}
}Of course, you’ll note that we aren’t actually processing those, just putting them in buckets. The fact that we are able to split them into groups in a branchless manner is a fun optimization task, but it doesn’t matter as much as the next stage… we can now deal with a list of Posting Lists that are already divided by type.
For example, for the list holding only a single unique value, I can run the following:
var singlesSpan = CollectionMarshal.AsSpan(buckets[0]);
EntryIdEncodings.DecodeAndDiscardFrequency(singlesSpan, singlesSpan.Length);
var singlesLen = Sorting.SortAndRemoveDuplicates(singlesSpan);
bitmap.AddRange(singlesSpan[..singlesLen]);This is great, because now I can process the entire list using SIMD in a highly efficient manner. But things get better when we look at the other lists. In the case of the small Posting Lists, for example, the ids that I’m reading are not the actual values, but point to where the values actually reside.
This gives me the chance to actually load them from disk in an optimal, batched manner, like so:
var smallsSpan = buckets[1].ToSpan();
EntryIdEncodings.DecodeAndDiscardFrequency(smallsSpan, smallsSpan.Length);
var smallLen = Sorting.SortAndRemoveDuplicates(smallsSpan);
Container.GetAll(llt, smallsSpan[..smallLen], containerItems.ToSpan(), long.MinValue, pageLocator);
for (int i = 0; i < smallLen; i++)
{
var item = containerItems[i];
// read the small posting list and deal with it
}The key here is the Container.GetAll() call, which takes the list of unique Postings List locations and loads them in an optimized manner. In the previous code style, that was actually pretty hard to do. In this manner, it falls naturally from the way we write the code.
There are also advantages to the fact that we run tight loops with the same code, instead of branching for each type. We also ended up with less code overall, which is also nice.
