Query producing wrong estimates (part 1)

 I thought I'll start documenting instances of wrong estimations done by SQL Server. I already have one post on this topic, but recently I found another such case. Not sure it will help anyone, yet I'll document my findings.

This case is reproducible on compatibility levels 130 and 150, with QUERY_OPTIMIZER_HOTFIXES enabled and disabled

As usual let's first prepare table and fill it up with data:

CREATE TABLE T
(
PK UNIQUEIDENTIFIER NOT NULL DEFAULT NEWSEQUENTIALID(),
ID UNIQUEIDENTIFIER NULL,
B1 BIT NOT NULL
)

CREATE INDEX IX ON T
(ID, B1)

;WITH cte AS (
SELECT a FROM (VALUES(0),(0),(0),(0),(0),(0),(0),(0),(0),(0)) x(a))
INSERT INTO T(ID, B1)
SELECT NULL, 0
FROM cte
CROSS JOIN cte cte2
CROSS JOIN cte cte3
CROSS JOIN cte cte4
CROSS JOIN cte cte5
CROSS JOIN cte cte6

Now create following procedure and run it:

CREATE OR ALTER PROC #p (@p0 UNIQUEIDENTIFIER, @p1 BIT)
AS
BEGIN

    SELECT * FROM T
    WHERE ID = @p0
    AND B1 = @p1 

END

GO

EXEC dbo.#p @p0 = '00000000-0000-0000-0000-000000000000', 
            @p1 = 0

ID column has only null values and we're seeking for non null value, so we would expect an index seek with a lookup. What we get is table scan and totaly wrong estimates.

What are the ways to fix it? We could:

• remove the B1 = @p1 part. But this changes the query logic
• run query with literals. Suprisingly adding OPTION(RECOMPILE) doesn't fix the query
• add OPTION(OPTIMIZE FOR UNKNOWN). RECOMPILE doesn't work. But this one does. Go figure
• Remove the B1 column from the index. I find it fascinating that to fix a query performance you sometimes need to substitute good index with a worse one.

I'll let you dear reader to try out these fixes for my demo. I must say this looks like a bug to me. Since in  the real case I went for the index fix, I reviewed histogram for index with and without B1 column. They seemed basically identical, yet yielded totally different execution plans. I opened a ticket in UserVoice, but obviously don't hold my breath someone will even look in its remote direction.