The best way to explain this is with an example.
If you were to build an access control system, you would probably create two tables Users and Permissions, lets say something like:
| users |
|---|
id: int |
name: varchar(50) |
| permissions |
|---|
id: int |
name: varchar(50) |
Since most users are likely to have more than one permission, we also get
| users_permissions |
|---|
user_id: int |
permission_id: int |
here’s the problem. In any given usage of this, I’m likely to want to find the the users that have an arbitrary number of permissions. No matter how you build it, you’re going to have a number of complicated joins.
There is a simpler solution that can be employed. Instead of using sequential integers for ID, use the ID as a bitmap. That is to say you have the following Permissions:
| id | name |
|---|---|
| 1 | Permission One |
| 2 | Permission Two |
| 4 | Permission Three |
| 8 | Permission Four |
This means that instead of having our join table we can add permission_id to our user table and use bitwise operators in our selects.
Obviously we’re mostly limited to 32 or 64 permissions unless we also change the keywords of the IDs
id1:int → permission_id1
id2:int → permission_id2
Becuase we’re using these ints as a bitmaps, we can use them in concert by defaulting each to field to 0 and continuing to do our bitwise operations, doing a boolean AND. Having doubled our available number of permissions we can keep adding id fields until we get the number of items we want.
This technique is good for specific types of problems:
- The items are the basis for making selection
- You typically select based on the existance of multiple items
- The number of items is relatively stable
To do this well, you’d want to do a few things:
- Handle creation to make it easy to ensure that the next next bit is set.
- Provide some mechanism for finding objects based on the associated items.