I wasn't game to restore a 110 GB database for just one table so I created my own data. The age distributions should match what's on Stack Overflow but obviously the table itself won't match. I don't think that it's too much of an issue because the queries are going to hit indexes anyway. I'm testing on a 4 CPU computer with SQL Server 2016 SP1. One thing to note is that for queries that finish this quickly it's important not to include the actual execution plan. That can slow things down quite a bit.

I started by going through some of the solutions in Erik's excellent answer. For this one:

SELECT SUM(Records)
FROM 
(
    SELECT COUNT(Id)
    FROM dbo.Users AS u
    WHERE u.Age < 18

    UNION ALL

    SELECT COUNT(Id)
    FROM dbo.Users AS u
    WHERE u.Age IS NULL
) x (Records);

I got the following results from sys.dm_exec_sessions over 10 trials (the query naturally went parallel for me):

╔══════════╦════════════════════╦═══════════════╗
║ cpu_time ║ total_elapsed_time ║ logical_reads ║
╠══════════╬════════════════════╬═══════════════╣
║     3532 ║                975 ║         60830 ║
╚══════════╩════════════════════╩═══════════════╝

The query that worked better for Erik actually actually performed worse on my machine:

SELECT SUM(Records)
FROM 
(
    SELECT 1
    FROM dbo.Users AS u
    WHERE u.Age < 18

    UNION ALL

    SELECT 1
    FROM dbo.Users AS u
    WHERE u.Age IS NULL
) x (Records)   
OPTION(QUERYTRACEON 8649);

Results from 10 trials:

╔══════════╦════════════════════╦═══════════════╗
║ cpu_time ║ total_elapsed_time ║ logical_reads ║
╠══════════╬════════════════════╬═══════════════╣
║     5704 ║               1636 ║         60850 ║
╚══════════╩════════════════════╩═══════════════╝

I'm not immediately able to explain why it's that bad, but it's not clear why we want to force nearly every operator in the query plan to go parallel. In the original plan we have a serial zone that finds all rows with AGE < 18. There are only a few thousand rows. On my machine I get 9 logical reads for that part of the query and 9 ms of reported CPU time and elapsed time. There's also a serial zone for the global aggregate for the rows with AGE IS NULL but that only processes one row per DOP. On my machine this is just four rows.

My takeaway is that it's most important to optimize the part of the query that finds rows with a NULL for Age because there are millions of those rows. I wasn't able to create an index with less pages that covered the data than a simple page-compressed one on the column. I assume that there's a minimum index size per row or that a lot of the index space cannot be avoided with the tricks that I tried. So if we're stuck with about the same number of logical reads to get the data then the only way to make it faster is to make the query more parallel, but this needs to be done in a different way than Erik's query that used TF 8649. In the query above we have a ratio of 3.62 for CPU time to elapsed time which is pretty good. The ideal would be a ratio of 4.0 on my machine.

One possible area of improvement is to divide the work more evenly among threads. In the screenshot below we can see that one of my CPUs decided to take a little break:

Index scan is one of the few operators that can be implemented in parallel and we can't do anything about how the rows are distributed to threads. There's an element of chance to it as well but pretty consistently I saw one underworked thread. One way to work around this is to do parallelism the hard way: on the inner part of a nested loop join. Anything on the inner part of a nested loop will be implemented in a serial way but many serial threads can run concurrently. As long as we get a favorable parallel distribution method (such as round robin), we can control exactly how many rows are sent to each thread.

I'm running queries with DOP 4 so I need to evenly divide the NULL rows in the table into four buckets. One way to do this is to create a bunch of indexes on computed columns:

ALTER TABLE dbo.Users
ADD Compute_bucket_0 AS (CASE WHEN Age IS NULL AND Id % 4 = 0 THEN 1 ELSE NULL END),
Compute_bucket_1 AS (CASE WHEN Age IS NULL AND Id % 4 = 1 THEN 1 ELSE NULL END),
Compute_bucket_2 AS (CASE WHEN Age IS NULL AND Id % 4 = 2 THEN 1 ELSE NULL END),
Compute_bucket_3 AS (CASE WHEN Age IS NULL AND Id % 4 = 3 THEN 1 ELSE NULL END);

CREATE INDEX IX_Compute_bucket_0 ON dbo.Users (Compute_bucket_0) WITH (DATA_COMPRESSION = PAGE);
CREATE INDEX IX_Compute_bucket_1 ON dbo.Users (Compute_bucket_1) WITH (DATA_COMPRESSION = PAGE);
CREATE INDEX IX_Compute_bucket_2 ON dbo.Users (Compute_bucket_2) WITH (DATA_COMPRESSION = PAGE);
CREATE INDEX IX_Compute_bucket_3 ON dbo.Users (Compute_bucket_3) WITH (DATA_COMPRESSION = PAGE);

I'm not quite sure why four separate indexes is a little faster than one index but that's one what I found in my testing.

To get a parallel nested loop plan I'm going to use the undocumented trace flag 8649. I'm also going to write the code a little strangely to encourage the optimizer not to process more rows than necessary. Below is one implementation which appears to work well:

SELECT SUM(t.cnt) + (SELECT COUNT(*) FROM dbo.Users AS u WHERE u.Age < 18)
FROM 
(VALUES (0), (1), (2), (3)) v(x)
CROSS APPLY 
(
    SELECT COUNT(*) cnt 
    FROM dbo.Users 
    WHERE Compute_bucket_0 = CASE WHEN v.x = 0 THEN 1 ELSE NULL END

    UNION ALL

    SELECT COUNT(*) cnt 
    FROM dbo.Users 
    WHERE Compute_bucket_1 = CASE WHEN v.x = 1 THEN 1 ELSE NULL END
        
    UNION ALL

    SELECT COUNT(*) cnt 
    FROM dbo.Users 
    WHERE Compute_bucket_2 = CASE WHEN v.x = 2 THEN 1 ELSE NULL END

    UNION ALL

    SELECT COUNT(*) cnt 
    FROM dbo.Users 
    WHERE Compute_bucket_3 = CASE WHEN v.x = 3 THEN 1 ELSE NULL END
) t
OPTION (QUERYTRACEON 8649);

The results from ten trials:

╔══════════╦════════════════════╦═══════════════╗
║ cpu_time ║ total_elapsed_time ║ logical_reads ║
╠══════════╬════════════════════╬═══════════════╣
║     3093 ║                803 ║         62008 ║
╚══════════╩════════════════════╩═══════════════╝

With that query we have a CPU to elapsed time ratio of 3.85! We shaved off 17 ms from the runtime and it only took 4 computed columns and indexes to do it! Each thread processes very close to the same number of rows overall because each index has very close to the same number of rows and each thread only scans one index:

On a final note we can also hit the easy button and add a nonclustered CCI to the Age column:

CREATE NONCLUSTERED COLUMNSTORE INDEX X_NCCI ON dbo.Users (Age);

The following query finishes in 3 ms on my machine:

SELECT COUNT(*)
FROM dbo.Users AS u
WHERE u.Age < 18 OR u.Age IS NULL;

That's going to be tough to beat.