Bitwise in database

bitwise_database.md

For a one-to-many relationship, where the “many” has a small number of known values, relationships can be stored as bitmasks in the parent table as an integer, replacing the need for an additional table.

Say we have a table Person and we’d like to know how many Continents a person has visited. We’d start by assigning each Continent an “orthogonal” bit value. In C#, an enum is a good choice for this:

[Flags]
public enum JobAdvertisingRegion
{
    NorthAmerica = 1,              // or 1 << 0
    SouthAmerica = 2,              // 1 << 1
    Europe = 4,                    // 1 << 2
    Asia = 8,                      // 1 << 3
    Africa = = 16,                 // 1 << 4
    Australia = 32,                // 1 << 5
    Anarctica = 64                 // 1 << 6
}

The Persons table could then simply have a int column called Contintents. To indicate that a Person has visited Europe and Asia:

    UPDATE Persons SET Continents = (4 + 8) WHERE Id = whatever

To search for Persons who have visited Antarctica, we use bitwise math:

    SELECT * FROM Persons WHERE Continents & 64 = 64

To search for Persons who have visited both Africa and Asia:

    SELECT * FROM Persons WHERE Continents & (16 + 8) = (16 + 8)

To search for Persons who have visited either Australia or South America:

    SELECT * FROM Persons WHERE Continents & (32 + 2) != 0

One downside is that, while integer columns are indexable in SQL, their bit components are not. Some optimizations to get around this, for the above queries:

    SELECT * FROM Persons WHERE Continents & 64 = 64 AND Continents >= 64

    SELECT * FROM Persons WHERE Continents & (16 + 8) = (16 + 8) AND Continents >= (16 + 8)

    SELECT * FROM Persons WHERE Continents & (32 + 2) != 0 AND Continents >= 2