sql-server optimize query with lots of null checks
NULL bitmap is indeed used for query optimization that involve columns with NULL values, but there are a few considerations here:


NULL bitmap is not present on nonclustered indexes (you'll see why), on the other hand it is always present on the leaves of clustered indexes, and heap tables.
NULL bitmap cannot be built for index records, but exclusively for data records (this is why you cannot have it for nonclustered indexes). That means you can have a NULL bitmap either on the table (organized as heap) or on a clustered index (leaves).
NULL bitmap is not present for tables with only SPARSE columns.


You should check if you have a NULL bitmap indeed. My guess is that yours is missing. You could use DBCC to check the record attributes:

Open a query window and issue:

DBCC IND (DATABASE_NAME, 'TABLE_NAME', -1)
DBCC TRACEON (3604)
DBCC PAGE (DATABASE_NAME, PageFID, PagePID, 3)
DBCC TRACEOFF (3604)


where PageFID and PagePID are displayed by the first command DBCC IND then check for the Record Attributes and check if NULL_BITMAP is present.

If there isn't any, then create a clustered index on the table, and check again.
You could also give us the execution plan, and the actual definition of the table (with dummy column names if confidential).