Fixing parameter-sniffing of an embedded query via Recompile
If @UID is NULL then the query cannot be executed with a seek. That means in order to get a seek you need the value of the variable to not be NULL and you need the parameter embedding optimization to be applied to the query. In other words, the optimizer needs to see the value of the variable before creating the plan. Usually this can be accomplished with a RECOMPILE hint but not always. The final example of the linked blog shows how the parameter embedding optimization cannot be applied when assigning a value to a variable.

We can also see hints of that behavior by running your example queries. For query A I get the following as a seek predicate:

Seek Keys[1]: Prefix: [SE_DB].[dbo].[Entries].UID = Scalar Operator((100))


However, for query B I get the following predicate:

[@UID] IS NULL OR [SE_DB].[dbo].[Entries].[UID]=[@UID]


The @UID reference was not replaced with 100 for query B so we must get a scan.

We can also see the difference in the query trees created for optimization with undocumented trace flag 8606:



Query A is on the left and query B is on the right. For query A, the query optimizer builds the query plan using the literal value of the variable. For query B, the query optimizer builds the plan only knowing that a variable was used.

There are plenty of workarounds available that don't require dynamic SQL or branching code. You can add up the results of two subqueries:

SELECT @cnt =
(
    select count(1) cnt
    from Entries 
    where @UID is null
) +
(
    select count(1) cnt
    from Entries 
    where @UID is not null and UID = @UID
);


You can use UNION ALL:

SELECT @cnt = SUM(cnt)
FROM
(
    select count(1) cnt
    from Entries 
    where @UID is null

    UNION ALL

    select count(1) cnt
    from Entries 
    where @UID is not null and UID = @UID
) t
option(recompile);


You can also insert into a temp table and grab the value from the temp table:

select count(1) cnt INTO #t
from Entries
where (@UID is null or UID = @UID)
option(recompile);

SELECT @cnt = MAX(cnt) FROM #t;

DROP TABLE #t;