Worse query performance even after improving the query by making it to run in parallel mode
One thing stands out clearly for me - this warning in the XML query plan:

&lt;Warnings&gt;
    &lt;PlanAffectingConvert ConvertIssue="Seek Plan" Expression="N'Public'=CONVERT_IMPLICIT(nvarchar(20),[r].[SecurityLevel],0)"/&gt;
&lt;/Warnings&gt;


A little known speed killer in SQL Server is passing an nvarchar() parameter to use in an indexed seek against a varchar() indexed value.  What SQL Server does in this case is to convert each value in the indexed field to an equivalent nvarchar() value, and compare them against the parameter.

Why doesn't it convert the nvarchar field to a varchar and use the index? Because all of varchar is a subset of nvarchar, but not all of nvarchar is a subset of varchar. Thus, to do the correct comparison, the varchar values must be converted to nvarchar values.

The effect of this is that the index is not used as an index (and may not be used at all, depending on the fields needed.)  Instead, the index is scanned from beginning to end to identify the matches, with each index entry having the value converted, one by one.  This is very slow.

There are two ways to handle this:


Change the field in the table and index to nvarchar
(Recommended) Change the parameter value to varchar before using it in the lookup.


The change can be handled in a number of ways. Either change the parameter type in the stored procedure being called, change the parameter type being passed by the application (There are articles on how to do this for Entity Framework calls to SQL), or add a CAST/CONVERT call in the code (which may be more trouble than it is worth.)