Oh so that's what a Bitmap DB is

Have you ever started a job with absolutely no idea what the company's software does?

I'm celebrating my 2 month anniversary at FeatureBase, and I just figured it out this morning.

More accurately we're talking about bitmap indexes.
It's a different approach to finding data based on its attributes.

As a game designer, my examples will be pulled from the Pokemon Pokédex.
Convenient indexing, set number of types, lists of weaknesses and abilities. Perfect all around example.

Bitmaps for the Pokédex

There are currently... 905! Pokemon. Seems reasonable, glad I picked this.

Let's consider analyzing Pokemon by their types and weaknesses.

Finding Pokemon by Type

There are 18 types.
For each type, we have a list of bits.
905 bits to be exact. Each bit represents a Pokemon, with the position of the bit being the same as the Pokemon's index.

To find the Pokemon of a given type, you scan the bit array for each position with a 1.
Each Pokemon has a bit in the list, and its position is mapped to their index in the main table.

Then it's a matter of scanning that list and pulling each of the records.
Sounds inefficient, until you realize how little data needs to be actually reviewed.

Exactly 905 bits. (theoretically)

No need to load any of the records to perform the search.
No need to do any string comparisons, or hashing, etc. etc.

Finding Pokemon by Multiple Types

Some Pokemon have multiple types.
Many have multiple weaknesses.

This is where I found these indexes to be fun.

To find all the Pokemon, for example, that are both Fairy and Poison type, we get the list of bits from each.
Then we do a bitwise AND on them.

The resulting list of bits will have a 1 in any position where that number Pokemon is both a Fairy and Poison type.

Of which there are 0. (153 possible combinations, it took me about 23 tries to find one with no Pokemon.)

Now let's find all the Pokemon who are weak to our new #906 Fairy/Poison Pokemon.
Same steps, but we change to a bitwise OR.
Any Pokemon weak to Fairy or Poison type.

Takeaway

Bitmaps:

Take each possibility and create a list of yes or no for each record.
Sounds crazy, but is really small and really fast.
Doesn't work for everything (can't tell you which Pokemon has the most tragic backstory, it's Cubone)

If this still sounds complex, or if you want to see what happens when some smart people make it even faster, then give it a try with FeatureBase.

Yes I work for them, and my job is to help you understand and work with it.
Let me know if I did a good job on our Discord Server, or if you'd like to hear a completely different example.