To INCLUDE or Not INCLUDE in an Index

Question

Current Situation

I am observing a simple statement that is querying one table and accessing multiple indexes to retrieve the data:

SELECT DISTINCT 
feld16,
zahl4,
feld12,
feld19 FROM 
object1 WHERE 
(deleted = 0 or deleted IS NULL)

The query execution plan can be found on Brent Ozar's Paste The Plan website and a graphical representation follows:

The table is made up of 82 columns containing various data. The distribution of the data in the deleted column is:

 deleted | Number of records
---------+-------------------
       0 |        71'620'068
    NULL |                10
 a value |            59'673

The result set contains approx. 64 million rows of the approx. 71 million rows that match the search predicate WHERE (deleted = 0 or deleted IS NULL). This is because the DISTINCT omits 7 million records.

Going Forward

In order to speed things up a bit, I am considering adding a new index. Initially I thought I was knowledgeable enough to add an adequate index, but I am starting to second-guess myself.

Question

Which of the following index definitions would (possibly) be an adequate solution?

1. Index without INCLUDE

CREATE NONCLUSTERED INDEX [IDXNew] ON [schema_owner].[object1]
(
    [deleted] ASC,
    [feld16] ASC,
    [zahl4] ASC,
    [feld12] ASC,
    [feld19] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, ONLINE = ON, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON)

2. Index with INCLUDE

CREATE NONCLUSTERED INDEX [IDXNew] ON [schema_owner].[object1]
(
    [feld16] ASC,
    [zahl4] ASC,
    [feld12] ASC,
    [feld19] ASC
)
INCLUDE 
(
    [deleted] ASC
)
WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, ONLINE = ON, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON)

3. Index with INCLUDE, but the other way round

CREATE NONCLUSTERED INDEX [IDXNew] ON [schema_owner].[object1]
(
    [deleted] ASC
)
INCLUDE(
    [feld12],
    [zahl4],
    [feld16],
    [feld19]
) 
WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON)

My Initial Thoughts

.. were to go with the first index definition and include all the columns. On reading up on the INCLUDE part of the index creation I thought of creating the second index. I then thought: Why not add a filter to the index like deleted = 0 or deleted IS NULL and then started second guessing my knowledge about indexes.

Additional Information

There are some trace flags running on the SQL Server 2016 instance. Some were recommended to us by Microsoft PFE during a PTOC.

<TraceFlag Value="2335" Scope="Global" /> -- Assume fixed amount of memory
<TraceFlag Value="2371" Scope="Global" /> -- Updates statistics in linear mode
<TraceFlag Value="4199" Scope="Global" /> -- Enable QO fixes

And the CE is currently set to run in backwards compatibility mode:

CardinalityEstimationModelVersion="70"

Answer 1

If you specifically want to optimise for getting these results quickly then one method would be an indexed view.

With a view definition of

SELECT feld16,
       zahl4,
       feld12,
       feld19,
       COUNT_big(*) AS [count]
FROM   object1
WHERE  ( deleted = 0
          OR deleted IS NULL )
GROUP  BY feld16,
          zahl4,
          feld12,
          feld19 

And a unique clustered index created on feld16, zahl4, feld12, feld19 then a SELECT against that view (potentially with NOEXPAND hint dependent on SQL Server edition) would likely be the fastest way of getting this data as it will all be pre-calculated in advance.

I'd be reluctant to use an indexed view for this case though as it still has nearly as many rows as the original table.

I would go for your index 1 and hope to see two seeks (for deleted = 0 and deleted is null) merge unioned together on the other four columns and then fed into a stream aggregate to remove the duplicates without any sorting or hashing (or ideally with the duplicate removal before the merge).

The reason why the merge union and stream aggregate(s) would be possible is that both the seeks will return rows in [feld16] ASC, [zahl4] ASC, [feld12] ASC, [feld19] ASC order.

If you don't get the desired execution plan it may need a query rewrite to

SELECT feld16,
       zahl4,
       feld12,
       feld19
FROM   object1
WHERE  ( deleted = 0 )
UNION
SELECT feld16,
       zahl4,
       feld12,
       feld19
FROM   object1
WHERE  ( deleted IS NULL ) 

Answer 2

A filtered index with the 4 column needed, should avoid the "concatenation", the "key Lookup" and the "sort" steps shown in the Plan, improving query performance.

CREATE NONCLUSTERE INDEX CoverTest1 ON [Schema_owner].[object1]
( feld12, zahl4, feld16, feld19 )
WHERE ISNULL(deleted, 0) = 0

I tested something similar (just 10Mln rows, different statistics, ...) comparing multiple indexes and the one above made the best change in terms of time and resources.