The mystery of the NULL bitmap mask
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 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!