For the web site WordMine.info, that is a search engine searching for words in almost any way possible, some optimizations are needed for the searches. Several word lists on the site have almost one million words and only doing a scan of all words and do a Regex or wild card-match one million times is too slow for a reasonable response time.

The most common database index is R-tree. The R-tree index is very good for what it is designed for, but you need to know what columns that is going to be queried to create a good index. Since the searches on WordMine.info is very flexible, there is no way to create an index (or a reasonable amount of indexes) that would work for each every possible search type.

Bitmap Indexes are very specialized indexes and can give a true of false for each record. A R-tree index can index all cities where customers are located and easily find which customers that are located in Gothenburg or customers that are in Copenhagen or all customers that are in either Berlin or London. The bitmap index can only answer one of these questions; “Is a customer in Gothenburg or not?”. To find the customers that are in Copenhagen you need a new index for that. But on the other hand they are somewhat compact (but since you need several indexes for each column, the total is not so compact) and also incredible good at combining several indexes to find the records that are interesting. So finding the customers that are in either Berlin or London, you need two indexes; one for customers in Berlin and one for customers in London. But since bitmap indexes are fast to combine you can easily use the two indexes combined to find all the customers in either Berlin or London.

To combine two indexes is very fast, to combine two indexes the processor instruction bitwise OR or bitwise AND is used, and also the bitwise instruction is normally done on 64 records at the same time.

Bitmap Index implementations in C#

In 2014 i wrote my own implementation of a bitmap index and found that it was extremely fast, it was somewhat specialized to my needs at WordMine.info, but after the initial testing of the first implementation it got abandoned for some reason.

Now, 10 years later, I thought that there is probably several implementations and NuGet packages that can easily beat the performance of my implementation. But there was not so many easy to find implementations as I expected. Actually, Microsoft Copilot found two of the implementations for me, the only time I Copilot has done anything useful so far.

Benchmarked bitmap indexes

csharpewah

https://github.com/lemire/csharpewah
License: Apache License, Version 2.0 (ASL2.0)
Last update: Nov 13, 2021

This is a compressed bitmap index. It’s usage is pretty straight forward, you create a EwahCompressedBitArray (with an initial size, if you like) and you Set(index) all the index positions that are true. There don’t seem to be a way to change a bit after it is set and all the added bits has to be added in order.

After the initialization you can And(), Or() or AndNot() two indexes together. To get the result you use GetPositions() to get a list (List<int>) with all the positive positions, or the enumerator to loop the positions. There is also an optimized Intersects() that returns true if both indexes has at least one true bit in the same position. A special case that I cannot find any use of myself.

CSharp.BitmapIndex

https://github.com/reinaldoarrosi/CSharp-BitmapIndex
License: Unknown
Last update: Aug 5, 2013

After I begun testing this implementation I realized that it was a wrapper for the csharpewah. CSharp.BitmapIndex adds handling of multiple bitmap indexes internally and has its own query language to handle the combining of the different indexes needed to get the result you are querying.

It look like the index initialization tries to help with the mapping of database values to bitmap index. So instead of creating an index for all customers in Gothenburg, you set the position of a key that is group/value (you can even have keys with group/subgroup/value).
bitmapIndex.Set(new BiKey(“City”, “Gothenburg”), position);
I can see the reason why the implementation is made like this, but all the new BiKey() (that is also needed in the querying) makes it a bit annoying to use. The querying is even more “chatty” than the index generation, but the intention is good to encapsulate all the indexes in the implementation.

CRoaring.Net

https://github.com/andersstorhaug/CRoaring.Net
License: MIT
Last update: Feb 21, 2018

CRoaring.Net is a .NET wrapper of the C implementation CRoaring (https://github.com/RoaringBitmap/CRoaring, License: Apache-2.0 and MIT), which is a port of the Java implementation (https://github.com/RoaringBitmap/RoaringBitmap, License: Apache-2.0). There are several other wrappers of the C version and ports of the Java implementation, but I selected this version because it was the repository with most recent (7 years) updates. Because the Java and C versions still gets frequent updates and this wrapper was 7 years old when tested, there might be improvements during these years that are not included in this implementation.

The usage of is pretty straight forward, you combine an index with another with the included methods. There are methods for combining two indexes, And, Or, AndNot, OrNot, Xor and more. Most (or all) has two different version where one of them creates a new index and another version updates the existing index with the combined result. The latter it much more effective when combining several indexes. There is also some static methods that combines a list of indexes, but for some reason combining these indexes with And is not included, but that seems to be a design decision in the CRoaring version.

Since CRoaring.Net is a direct wrap of CRoaring, it is using uint everywhere instead of int. The only time that that would be useful is when the indexed data has more than two billion records, which probably is pretty rare. This results in some of the API needs annoying casts.

Crude.BitmapIndex

https://github.com/aberkromb/Crude.BitmapIndex
License: MIT
Last update: Oct 6, 2019

This bitmap index implementation has the API that I like the most. It uses a Predicate (a Func that returns a bool) to generate the index, you create a builder and run builder.IndexFor(“in-gothenburg”, customer => customer.City == “Gothenburg”). It also includes two query engines, one default and one that uses the hardware acceleration Avx2.

But a great API does not help when the implementation has too many bugs. The first issue was that I tried with 1 million records, which quickly gave an index out of range exception, after some testing it turned out that the index data length cannot be a multiple of 64 without crashing. The hardware accelerated engine worked fine when running the included tests that uses 100,000 records, but with several more records the optimized version just hangs.

Equativ.RoaringBitmaps

https://github.com/equativ/Equativ.RoaringBitmaps
License: Apache-2.0
Last update: Nov 27, 2024

The Equativ.RoaringBitmaps is a pure C# port of the Java implementation RoaringBitmap (http://roaringbitmap.org/).

Creating indexes with Equativ.RoaringBitmaps is done by giving a list with all the set bits to the Create() method. After the index is created it cannot be changed, but it can be Optimized(). This is the only implementation that overloads the bitwise operators to combine the indexes.

ManualBitmapIndex

This is my first test with bitmap indexes from 2014, it is just a List<uint> for all the bits. And to combine two indexes it just loops all the uints in the list and bitwise and them together.

The only performance improvement in is code is that when retrieving the matches it first checks if there is any bit set at all before looking for which bits are set.

BitArrayIndex

This is almost a copy of the ManualBitmapIndex, but instead of storing the bits in a List<uint>, they are stored in a BitArray (https://learn.microsoft.com/en-us/dotnet/api/system.collections.bitarray).

When looking at the code for the BitArray class it is very optimized and hopefully some of the brightest minds at the dotnet team has worked on this code. The methods And(), Or(), Xor() and Not() uses hardware accelerated Vectors to execute the bitwise operations. The computer running the benchmarks supported hardware acceleration of Vector256.

Benchmarking speed of index search

This benchmarking is done on real data where I might have use for a bitmap index.

Total number of records: 1,335,000
Bits set is each index:
Index #1: 805,000 (60%)
Index #2: 226,000 (17%)
Index #3: 453,000 (34%)
Index #4: 384,000 (29%)
Index #5: 926,000 (69%)

About the index search benchmarking

The benchmarking merges two to five indexes with And to get the combined result. After the indexes are combined, the first matching 100 items from a List<> is retrieved. The reason to only get the first 100 items is to not include the retrieval of data in the index search benchmark and also simulate pagination of the result.

About the result of the speed benchmark

• I was surprised that the ManualBitmapIndex would be faster than most of the other implementations. But maybe this raw implementation lacks some of the overhead that the other implementations have.
• Also, I expected the hardware accelerated BitArray to be much faster than the ManualBitmapIndex because of the hardware acceleration. But the benchmark shows that in all the benchmarks the BitArray is slower or about the same speed.
• CrudeBitmapDefault is the worst in all the tests because there is no way to limit the number of data to return. So it will always generate an array with all the objects that matches the combined indexes. All the other benchmarks only returns the first 100.
• The optimized indexes in CRoaring.Net and Equativ.RoaringBitmaps does not look optimized when it comes to index speed. But that was expected, since I’m pretty sure the optimization refer to memory usage of the index. Also when the indexes has few
• On their GitHub page, Equativ.RoaringBitmaps show benchmarking that beats CRoaring.Net in on every operation. But the reason for this benchmarking result, is because Equativ.RoaringBitmaps uses optimized indexes in for their own indexes, but unoptimized CRoaring.Net indexes. Changing the benchmark so both uses optimized indexes, makes Equativ.RoaringBitmaps 1.5 to 2.5 times slower.

Benchmarking memory of index search

Benchmarking speed of index generation

About the result of the index generation

• What stands out here is the CSharp.BitmapIndex, while all other indexes takes a fraction of a second to create the indexes, CSharp.BitmapIndex takes almost a minute for each index. This is because this implementation does not give any way to preallocate the size of the index. This means that in this benchmark the underlying EwahCompressedBitArray (which, by the way, supports preallocation of memory) is probably reallocating the index about 20,000 times.
  But wait, there is more, CSharp.BitmapIndex is reallocating, not one, but two different indexes about 20,000 times, which one of them is negated, with Not(), twice for each set bit.

Benchmarking memory of index generation

Foot notes

• This post uses indexes as plural of index and not the .NET indices. According to Oxford Learners Dictionary (link), both versions are valid.