Non obvious optimization with divide and conquer

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…