In today's weblog post I want to talk about the NULL bitmap mask and some mysteries

that you can encounter with it. The NULL bitmap mask encodes at the Storage Engine

level which column stores a NULL value and which not. It's a simple bitmap mask, where

a set bit (1) means that the column has a NULL value, and a not set bit (0) means

that the column has an actual value (not a NULL value).

At the first look this sounds very straightforward, but when you look into the details,

there are some implications with this approach. Let's have in the first step a look

into the concrete structure of a data row that is used by the Storage Engine to store

physically a record on a disk. The following picture shows that structure:

This format is called the FixedVar format, because SQL Server always stores fixed

length columns (like INT, CHAR) before variable length columns (like VARCHAR) are

stored. As you can see SQL Server stores at the beginning 2 bytes with some status

bits, and then in 2 bytes the offset to which the fixed portion of the record is stored.

Afterwards you find 2 bytes that stores the column count, which is followed by the

actual NULL bitmap mask.

When you look at this in the first step, everything makes sense to you, but after

a second look, you start thinking and you may ask, WHY SQL Server stores the actual

column count in EVERY data row??? The column count MUST be identical for every data

row! Why SQL Server actually stores redundant data?

The first (short) answer is very easy and logical: SQL Server needs the column count

to calculate how many bytes are used for the actual NULL bitmap mask. Up to 8 columns

in a table needs 1 byte, 9 – 16 columns need 2 bytes, 17 – 24 columns need 3 bytes,

and so on. Makes sense, but again: the column count for each record in a table MUST

BE THE SAME!

Let's have now a more detailed look into the technical correct answer, along with

some examples. First of all, you need to know that the NULL bitmap mask stores the

number of columns that are CURRENTLY stored in the record at the Storage Engine level.

This means that SQL Server can store a different amount of columns in a physical data

row – ok, now it gets really confusing… So the column count in the physical data row

does not have to match with the column count in the table metadata layer (sys.columns).

Those are also really different layers inside the architecture of SQL Server.

So under which circumstances those layers are not matching to each other? It's very

simple: when you are adding columns to an existing table! SQL Server makes a big difference

if you add a NULL or NOT NULL column to a table. When you just add a new NULL column

to a table, SQL Server only updates the table metadata layer, WITHOUT touching the

Storage Engine layer. This means that none of your records gets physically changed,

when you add a NULL column. On the other hand, when you add a NOT NULL column, SQL

Server updates the table metadata layer, and ALSO the Storage Engine layer, which

means that SQL Server has to touch and rewrite EACH of the records in the table, where

you have added the NOT NULL column. This makes a huge performance different! For that

reason SQL Server has to store the actual column count in each data record, because

the column count must not be in synch with the table metadata layer.

Let's have now a more detailed look into a concrete example. For this example I have

created a simple table with 8 columns, which means that SQL Server uses 1 byte for

the NULL bitmap mask:

CREATE TABLE TestTable

(

Column1 INT IDENTITY(1, 1) NOT NULL,

Column2 CHAR(600) NOT NULL,

Column3 CHAR(600) NOT NULL,

Column4 CHAR(600) NOT NULL,

Column5 CHAR(600) NOT NULL,

Column6 VARCHAR(600) NOT NULL,

Column7 VARCHAR(600) NOT NULL,

Column8 VARCHAR(600) NOT NULL,

)

GO

Afterwards I have inserted 2 records into the previous created table:

INSERT INTO TestTable VALUES

(

REPLICATE('2', 600),

REPLICATE('3', 600),

REPLICATE('4', 600),

REPLICATE('5', 600),

REPLICATE('6', 600),

REPLICATE('7', 600),

REPLICATE('8', 600)

),

(

REPLICATE('2', 600),

REPLICATE('3', 600),

REPLICATE('4', 600),

REPLICATE('5', 600),

REPLICATE('6', 600),

REPLICATE('7', 600),

REPLICATE('8', 600)

)

GO

When you dump out both data pages through the DBCC PAGE command, you can see that

each record has a length of 4219 bytes (4204 bytes data + 7 bytes row overhead + 2

bytes variable length column count + 3 x 2 bytes variable column offset array entry).

DBCC TRACEON(3604)

GO

DBCC IND(InternalStorageFormat, TestTable, -1)

GO

DBCC PAGE (InternalStorageFormat, 1, 79, 1)

GO

DBCC PAGE (InternalStorageFormat, 1, 89, 1)

GO

Now just add a new NULL column to the existing table:

ALTER TABLE TestTable ADD Column9 CHAR(600) NULL

GO

This is the 9th column in the table, which means SQL Server needs now 2 bytes for

the column count. But SQL Server DOES NOT changes the physical data row at the Storage

Engine level, because you are just adding a NULL column. SQL Server doesn't have to

do anything on the Storage Engine level. You can prove that just by dumping out the

2 data pages again:

DBCC PAGE (InternalStorageFormat, 1, 79, 1)

GO

DBCC PAGE (InternalStorageFormat, 1, 89, 1)

GO

The records have the same length of 4219 bytes, but you have added a column (logically)

to the table. Let's try now to update one record of the table, so that the previous

added column gets an actual value:

UPDATE TestTable SET Column9 = REPLICATE('9', 600)

WHERE Column1 = 1

GO

When you now dump out the page where the first record of the table is located, you

can see that the record size is now 4820 bytes. SQL Server has now expanded the NULL

bitmap mask to 2 bytes (1 additional byte overhead) and has written out the actual

value of the column (600 additional bytes). SQL Server increased the record size from

4219 bytes to 4820 (4219 + 1 + 600 = 4820).

When you dump out the data page where the 2nd record of the table is stored, the record

size is the old one of 4219! You have now created a scenario where SQL Server stores

a different length of the NULL bitmap mask inside the data row. This also means that

you can have scenarios where a table with only fixed length columns has different

row sizes on the Storage Engine level – sounds interesting, isn't it? J

Let's now drop the table, recreate it, and insert the 2 records into it. Now we are

adding a NOT NULL column to the table:

ALTER TABLE TestTable ADD Column9 CHAR(600) NOT NULL DEFAULT REPLICATE('9', 600)

GO

Now, SQL Server has to change EVERY record on the Storage Engine Level, because the

default value of the new column must be added (you must define a default value for

the new column when you already store records in a table), and SQL Server also has

to expand the NULL bitmap mask.

This phenomenon can lead to serious performance problems when you are dealing with

large tables, and you want to add a NOT NULL column. To give you an idea about the

performance degradation I have inserted 1 million records into that table. When I

have added a NULL column, SQL Server needed a few milliseconds, because it was just

a metadata operation. But when I have added to that table a NOT NULL column, it took

around 40 seconds (!) until the ALTER TABLE was completed. So as you can see this

is a serious performance degradation when dealing with adding NOT NULL columns to

big tables!

I hope that you now understand why SQL Server has to store the actual column count

in each record on the Storage Engine level, and that you can have serious performance

problems when you are adding NOT NULL columns to large tables in SQL Server.

Thanks for reading!

-Klaus