Can Microsoft store three-valued fields in a single bit?

Question

I'm completely ignorant of SQL/databases, but I was chatting with a friend who does a lot of database work about how some databases use a "boolean" field that can take a value of NULL in addition to true and false.

Regarding this, he made a comment along these lines: "To Microsoft's credit, they have never referred to that kind of field as a boolean, they just call it a bit. And it's a true bit - if you have eight or fewer bit fields in a record, it only requires one byte to store them all."

Naturally that seems impossible to me - if the field can hold three values you're not going to fit eight of them into a byte. My friend agreed that it seemed odd, but begged ignorance of the low-level internals and said that so far as he knew, such fields can hold three values when viewed from the SQL side, and it does work out to require a byte of storage. I imagine one of us has a wire crossed. Can anyone explain what's really going on here?

Answer 1

I recommend reading this for a good explanation of null storage: How does SQL Server really store NULL-s. In short, the null/not null bit is stored in a different place, the null bitmap for the row.

From the article:

Each row has a null bitmap for columns that allow nulls. If the row in that column is null then a bit in the bitmap is 1 else it's 0.

So while the actual values for 8 bit columns are stored in 1 byte, there are extra bits in the row's null bitmap that indicate if that column is NULL or not...so depends on how you're counting. To be completely accurate, 8 bit columns use 2 bytes, just split up in 2 different locations.

Answer 2

The null indicator is stored separately, so a nullable bit actually requires two bits. And strictly speaking, "null" isn't a third value; it's sort of a placeholder that says, "There could be a value here, but we don't know what it is." So if a bit is null, you can compare it to true and the comparison will fail, but you can also compare it to false and the comparison will fail.

Answer 3

You are correct. You can pack the eight true/false values into a single byte, but you still need additional storage to indicate whether it is NULL or not. Representing 3⁸ different states with only 2⁸ is impossible.