Bitmap indexes in Go: searching at wild speed

Opening Remarks

I presented this talk in English at GopherCon Russia 2019 in Moscow and in Russian at a meetup in Nizhny Novgorod. It discusses the bitmap index, which is less common than the B-tree but equally interesting. I share the recording of my conference presentation in English and the text transcription in Russian.

We will explore how the bitmap index works, when it is better, when it is worse than other indexes, and in which cases it can be significantly faster; we'll see in which popular DBMSs bitmap indexes already exist; and we will attempt to write our own in Go. As a 'dessert', we will use existing libraries to create our own super-fast specialized database.

I really hope my efforts will be useful and interesting to you. Let's get started!

Introduction

Hello everyone! It's six in the evening, and we are all super tired. What a wonderful time to talk about the boring theory of database indexes, right? Don’t worry, I’ll have a couple of lines of source code here and there. 🙂

Joking aside, the talk is packed with information, and we don’t have much time. So let’s get started.

Today I will talk about the following:

• what indexes are;
• what a bitmap index is;
• where it is used and where it is NOT used and why;
• a simple implementation in Go and a bit of dealing with the compiler;
• a slightly less simple but much more performant implementation in Go assembly;
• the 'problems' of bitmap indexes;
• existing implementations.

So what are indexes?

An index is a separate data structure that we maintain and update in addition to the primary data. It is used to speed up searches. Without indexes, searching would require a full scan of the data (a process called full scan), and this process has linear algorithmic complexity. However, databases typically contain vast amounts of data, and linear complexity is too slow. Ideally, we would like to achieve logarithmic or constant time complexity.

This is a vast and complex topic filled with nuances and trade-offs, but after looking at decades of development and research in various databases, I am ready to assert that there are only a few widely used approaches to creating DB indexes.

The first approach involves hierarchically reducing the search space by dividing it into smaller sections.

We usually achieve this by using various types of trees. An example could be a large box with materials in your cabinet, containing smaller boxes that are categorized by different topics. If you need materials, you would likely look in the box labeled 'Materials' rather than the one labeled 'Cookies,' right?

The second approach is to directly identify the required element or group of elements. We do this using hash maps or inverted indexes. Using hash maps is very similar to the previous example, except instead of a box of boxes, you have a bunch of little boxes with final items in your cabinet.

The third approach is to eliminate the need for a search entirely. We achieve this with Bloom filters or cuckoo filters. The former provides an instant response, freeing you from the need to perform a search.

The last approach is to fully utilize the capabilities that modern hardware provides us. This is precisely what we do in bitmap indexes. Yes, using them sometimes requires us to go through the whole index, but we do this super efficiently.

As I mentioned, the topic of database indexes is vast and filled with trade-offs. This means that sometimes we can use multiple approaches simultaneously: if we need to speed up searches even further or if we need to cover all possible types of searches.

Today I will talk about the least known approach from those mentioned—the bitmap indexes.

Who am I to speak on this topic?

I work as a team lead at Badoo (you might be more familiar with our other product—Bumble). We already have over 400 million users worldwide and many features designed to find the best match for them. We achieve this through custom services that utilize bitmap indexes, among other things.

So what exactly is a bitmap index?

Bitmap indexes, as the name suggests, use bitmaps or bit sets to implement a search index. From a bird's eye view, this index consists of one or more bitmaps representing certain entities (like people) and their properties or parameters (age, eye color, etc.), along with an algorithm that utilizes bitwise operations (AND, OR, NOT) to respond to search queries.

It is said that bitmap indexes are best suited and extremely efficient for cases where searches involve queries across many columns with low cardinality (think 'eye color' or 'marital status' compared to something like 'distance from the city center'). However, I will later show that they work perfectly well for columns with high cardinality as well.

Let’s consider a simple example of a bitmap index.

Imagine we have a list of Moscow restaurants with binary properties like these:

• near metro;
• has private parking;
• has terrace;
• accepts reservations;
• vegan friendly;
• expensive.

Let’s assign a sequential number to each restaurant starting from 0 and allocate memory for 6 bitmaps (one for each characteristic). Then we will fill these bitmaps depending on whether the restaurant has the specific property or not. If restaurant 4 has a terrace, then bit number 4 in the 'has terrace' bitmap will be set to 1 (if there is no terrace, it will be 0).

Now we have the simplest possible bitmap index, and we can use it to respond to queries like:

• 'Show me restaurants that are vegan friendly';
• 'Show me inexpensive restaurants with a terrace where reservations can be made.'

How? Let’s take a look. The first query is very simple. All we need to do is take the bitmap 'vegan friendly' and convert it into a list of restaurants whose bits are set.


The second query is a bit more complex. We need to use the NOT bitwise operation on the bitmap "expensive" to obtain a list of inexpensive restaurants, then AND it with the bitmap "can book a table" and AND the result with the bitmap "has a terrace." The resulting bitmap will contain a list of establishments that meet all our criteria. In this example, it’s only the restaurant "Youth."


There’s a lot of theory here, but don’t worry, we’ll see the code very soon.

Where are bitmap indexes used?

If you "Google" bitmap indexes, 90% of the answers will be somehow related to Oracle DB. But other DBMSs surely support such a cool feature, right? Not quite.

Let’s go through the list of main suspects.

MySQL does not yet support bitmap indexes, but there is a proposal to add this option (https://dev.mysql.com/worklog/task/?id=1524).

PostgreSQL does not support bitmap indexes but uses simple bitmaps and bitwise operations to combine search results across several other indexes.

Tarantool has bitset indexes, supporting simple searches on them.

Redis has simple bit fields (https://redis.io/commands/bitfield) without the ability to search on them.

MongoDB still does not support bitmap indexes, but there is also a proposal to add this option. https://jira.mongodb.org/browse/SERVER-1723

Elasticsearch uses bitmaps internally (https://www.elastic.co/blog/frame-of-reference-and-roaring-bitmaps).

• But a new neighbor has appeared in our house: Pilosa. This is a new non-relational database written in Go. It contains only bitmap indexes and builds everything on them. We’ll talk about it a bit later.

Implementation in Go

But why are bitmap indexes used so rarely? Before answering this question, I would like to demonstrate to you an implementation of a very simple bitmap index in Go.

Bitmaps are essentially represented as just pieces of data. In Go, let’s use byte slices for this.

We have one bitmap for one restaurant characteristic, and each bit in the bitmap indicates whether a specific restaurant has that property or not.

We will need two helper functions. One will be used to fill our bitmaps with random data. Random, but with a certain probability that a restaurant possesses each attribute. For example, I believe that there are very few restaurants in Moscow where you cannot reserve a table, and I think that about 20% of establishments are suitable for vegetarians.

The second function will convert the bitmap into a list of restaurants.


To respond to the query 'Show me inexpensive restaurants that have a terrace and where it is possible to reserve a table', we will need two bitwise operations: NOT and AND.

We can simplify our code a bit by using the more complex operation AND NOT.

We have functions for each of these operations. Both of them loop through the slices, take the corresponding elements from each, combine them with a bitwise operation, and place the result in the resulting slice.

And now we can use our bitmaps and functions to respond to the search query.

Performance is not that high, even though the functions are very simple and we saved quite a bit by not returning a new resulting slice with each function call.

After profiling a bit with pprof, I noticed that the Go compiler missed one very simple but crucial optimization: function inlining.

The thing is that the Go compiler is terribly afraid of loops that go through slices and categorically refuses to inline functions that contain such loops.

But I'm not afraid and can trick the compiler by using goto instead of a loop, just like in the old days.

And, as you can see, now the compiler gladly inlines our function! As a result, we manage to save about 2 microseconds. Not bad!

The second bottleneck is not hard to spot if you take a careful look at the assembly output. The compiler added boundary checks for the slice right inside our hottest loop. The fact is that Go is a safe language, and the compiler is concerned that my three arguments (three slices) may have different sizes. There is, after all, a theoretical possibility of a buffer overflow.

Let's calm the compiler by showing it that all slices have the same size. We can do this by adding a simple check at the beginning of our function.

Seeing this, the compiler happily skips the check, and in the end, we save another 500 nanoseconds.

Large batches

Okay, we've managed to squeeze some performance out of our simple implementation, but this result is actually much worse than what is possible with the current hardware.

All we're doing are basic bitwise operations, and our processors perform them very efficiently. Unfortunately, we are 'feeding' our processor very small chunks of work. Our functions perform operations byte by byte. We can easily tune our code to work with 8-byte chunks by using slices of UInt64.

As you can see, this small change accelerated our program eightfold by increasing the batch size eight times. The gain can be said to be linear.

Assembly implementation

But this is not the end. Our processors can work with chunks of 16, 32, and even 64 bytes. Such 'wide' operations are called single instruction multiple data (SIMD), and the process of transforming code so that it uses these operations is called vectorization.

Unfortunately, the Go compiler is far from an expert in vectorization. Currently, the only way to vectorize code in Go is to take and manually lay out the data operations using Go assembly.

Go assembly is a strange beast. You probably know that assembly is something that is very architecture-specific for the computer you're writing for, but in Go, that's not the case. Go assembly is more like an intermediate representation language (IRL): it is almost platform-independent. Rob Pike gave a great presentation talk on this topic a few years ago at GopherCon in Denver.

In addition to this, Go uses an unusual Plan 9 format that differs from the widely recognized AT&T and Intel formats.

It is safe to say that writing Go assembly manually is not the most enjoyable task.

But fortunately, there are already two high-level tools that assist us in writing Go assembly: PeachPy and avo. Both utilities generate Go assembly from higher-level code written in Python and Go, respectively.

These utilities simplify tasks like register allocation, writing loops, and generally ease the process of entering the world of assembly programming in Go.

We will use avo, so our programs will be almost ordinary Go programs.

Here is what the simplest example of an avo program looks like. We have the main() function, which defines the Add() function within itself, whose purpose is to add two numbers. There are helper functions for obtaining parameters by name and for retrieving one of the free and suitable processor registers. Each processor operation has a corresponding function in avo, as seen with ADDQ. Finally, we see a helper function for storing the resulting value.

By calling go generate, we will run the avo program and end up with two generated files:

• add.s containing the resulting code in Go assembly;
• stub.go with function headers to bridge the two worlds: Go and assembly.

Now that we have seen what avo does and how it works, let’s look at our functions. I have implemented both scalar and vector (SIMD) versions of the functions.

First, let's look at the scalar versions.

As in the previous example, we ask for a free and proper general-purpose register, we don’t need to calculate offsets and sizes for the arguments. avo does all of this for us.

Previously, we used labels and goto (or jumps) for performance enhancement and to trick the Go compiler, but now we are doing this from the beginning. The thing is, loops are a higher-level concept. In assembly, we only have labels and jumps.

The remaining code should already be familiar and clear. We emulate loops with labels and jumps, take a small part of data from our two slices, combine them with a bitwise operation (AND NOT in this case), and then store the result in the resulting slice. That's all.

Here is what the final assembly code looks like. We did not need to calculate offsets and sizes (highlighted in green) or keep track of the registers being used (highlighted in red).

If we compare the performance of the assembly implementation with the performance of the best implementation in Go, we will see that they are the same. And this is to be expected. After all, we didn't do anything special—we simply reproduced what the Go compiler would do.

Unfortunately, we cannot force the compiler to inline our functions written in assembly. The Go compiler does not currently have this capability, although there has been a request to add it for quite some time.

That is why it is impossible to gain any advantages from small functions in assembly. We either have to write large functions, use the new math/bits package, or avoid assembly altogether.

Now let’s take a look at the vectorized versions of our functions.

For this example, I decided to use AVX2, so we will work with operations that deal with 32-byte chunks. The structure of the code is very similar to the scalar version: loading parameters, asking for a free general-purpose register, and so on.

One of the innovations is that wider vector operations use special wide registers. In the case of 32-byte chunks, these are registers prefixed with Y. That’s why you see the YMM() function in the code. If I had used AVX-512 with 64-bit chunks, the prefix would have been Z.

The second innovation is that I decided to use an optimization called loop unrolling, which means performing eight loop iterations manually before jumping back to the start of the loop. This optimization reduces the number of branches in the code, and it is limited by the number of free registers available.

But what about performance? It is excellent! We achieved a speedup of about seven times compared to the best solution in Go. Impressive, right?

However, even this implementation could potentially be further accelerated using AVX-512, prefetching, or a JIT (just-in-time compiler) for the query planner. But that is definitely a topic for another talk.

Issues with bitmap indexes

Now that we have examined the simple implementation of a bitmap index in Go and a much more performant one in assembly, let’s finally discuss why bitmap indexes are so rarely used.

Older academic papers mention three problems with bitmap indexes, but more recent studies and I argue that they are no longer relevant. We won't delve deeply into each of these issues, but we'll take a superficial look at them.

The High Cardinality Problem

So, we are told that bitmap indexes are suitable only for fields with low cardinality, meaning those with few values (such as gender or eye color). The reason is that the usual representation of such fields (one bit per value) will take up too much space in cases of high cardinality, and moreover, these bitmap indexes will be sparsely (rarely) populated.


Sometimes we can use a different representation, for example, the standard one we use for numerical representation. But it was the emergence of compression algorithms that changed everything. Over the last few decades, scientists and researchers have devised numerous compression algorithms for bitmaps. Their main advantage is that we do not need to decompress bitmaps to perform bitwise operations — we can conduct bitwise operations directly on compressed bitmaps.

Recently, hybrid approaches have emerged, such as roaring bitmaps. They use three different representations for bitmaps simultaneously — traditional bitmaps, arrays, and so-called bit runs — and balance between them to maximize performance and minimize memory consumption.

You can find roaring bitmaps in some of the most popular applications. There are already a huge number of implementations for a variety of programming languages, including more than three implementations for Go.

Another approach that can help us deal with high cardinality is called binning. Imagine you have a field representing a person's height. Height is a floating-point number, but we, humans, don’t think of it in those terms. For us, there is no difference between a height of 185.2 cm and 185.3 cm.

Thus, we can group similar values into bins within 1 cm.

And if we also know that very few people have a height less than 50 cm and greater than 250 cm, we can essentially turn a field with infinite cardinality into a field with cardinality of about 200 values.

Of course, if needed, we can perform additional filtering later.

The issue of high bandwidth

The next issue with bitmap indexes is that updating them can be very costly.

Databases must allow for updating data at the moment when potentially hundreds of other queries are searching through that data. We need locks to avoid problems with concurrent data access or other concurrency issues. And where there is one big lock, there is a problem — lock contention, when that lock becomes a bottleneck.

This issue can be solved or circumvented using sharding or versioned indexes.

Sharding is simple and well-known. You can shard a bitmap index just as you would shard any other data. Instead of one large lock, you obtain many smaller locks and thus eliminate lock contention.

The second way to solve the problem is by using versioned indexes. You may have one copy of the index that you use for searching or reading, and another for writing or updating. And every so often (e.g., every 100 ms or 500 ms), you duplicate them and switch them. Of course, this approach is applicable only when your application can work with a slightly outdated search index.

These two approaches can be used simultaneously: you may have a sharded versioned index.

More complex queries

The last problem with bitmap indexes is that, as we are told, they are poorly suited for more complex types of queries, such as range queries.

Indeed, if you think about it, bitwise operations like AND, OR, etc., are not very suitable for queries like "Show me hotels with room rates from $200 to $300 per night."

A naive and very unreasonable solution would be to take the results for each dollar value and combine them using a bitwise OR operation.

A somewhat more appropriate solution would be to use grouping. For example, in groups of $50. This would speed up our process by 50 times.

But the problem is easily solved by using a representation specifically created for this type of query. In academic papers, it is called range-encoded bitmaps.

In such a representation, we don't just set one bit for a given value (for example, 200), but we set this value and everything above it. 200 and above. The same goes for 300: 300 and above. And so on.

Using this representation, we can respond to this type of search query by scanning the index only twice. First, we get a list of hotels where the room cost is less than 300 dollars, and then we filter out those where the cost is below 199 dollars. Done.

You will be surprised, but even geocoding queries are possible using bitmap indexes. The trick is to use a georepresentation that surrounds your coordinate with a geometric shape. For example, S2 from Google. The shape should be representable in the form of three or more intersecting lines that can be numbered. This way we can transform our geocoding query into several 'range' queries (along these numbered lines).

Ready-made solutions

I hope I have piqued your interest a bit and you now have another useful tool in your arsenal. If you ever need to do something similar, you'll know where to look.

However, not everyone has the time, patience, and resources to create bitmap indexes from scratch. Especially more advanced ones, using SIMD, for example.

Fortunately, there are several ready-made solutions that can help you.

Roaring bitmaps

First, there’s the roaring bitmaps library that I mentioned earlier. It contains all the necessary containers and bitwise operations you will need to create a full-fledged bitmap index.

Unfortunately, at the moment, none of the Go implementations use SIMD, which means that Go implementations are less performant than implementations in C, for example.

Pilosa

Another product that can help you is the Pilosa DB, which essentially only has bitmap indexes. It is a relatively new solution but is quickly winning hearts.

Pilosa uses roaring bitmaps internally and gives you the ability to utilize them, simplifying and explaining all the aspects I mentioned earlier: grouping, range-encoded bitmaps, the concept of fields, etc.

Let’s quickly take a look at an example of using Pilosa to answer a question you're already familiar with.

The example is very similar to what you've seen before. We create a client to the Pilosa server, establish an index and the necessary fields, then fill our fields with random data based on probabilities, and finally execute a familiar query.

After that, we use NOT on the field 'expensive', then intersect the result (or AND it) with the field 'terrace' and the field 'reservations'. And finally, we get the final result.

I sincerely hope that in the near future, databases like MySQL and PostgreSQL will also feature this new type of index — bitmap indexes.

Conclusion

If you haven't fallen asleep yet, thank you. I had to briefly touch on many topics because of limited time, but I hope the presentation was useful and perhaps even motivating.

It's good to know about bitmap indexes, even if you don't need them right now. Let them be one more tool in your toolbox.

We reviewed various tricks to enhance performance for Go and the issues that the Go compiler is still not handling very well. This is certainly useful knowledge for every Go programmer.

That's all I wanted to share. Thank you!

Source: habr.com