Efcore: Query: ParameterExtraction creates a parameter for every instance even though same variable is referenced

[smitpatel]

From https://github.com/aspnet/EntityFramework6/issues/211#issue-212215385
Query:
```c#

var parameter = 0;
var q = from p in db.Posts
where p.BlogId == parameter || p.PostId == parameter
select p;

var q2 =
from a in q
from b in q
where b.PostId > parameter
select new {a, b};

q2.ToList();

Generates following SQL
```SQL
Executed DbCommand (2ms) [Parameters=[@__parameter_0='0', @__parameter_1='0', @__parameter_2='0', @__parameter_3='0', @__parameter_4='0'], CommandType='Text', CommandTimeout='30']
      SELECT [p].[PostId], [p].[BlogId], [p0].[PostId], [p0].[BlogId]
      FROM [Posts] AS [p]
      CROSS JOIN [Posts] AS [p0]
      WHERE ((([p].[BlogId] = @__parameter_0) OR ([p].[PostId] = @__parameter_1)) AND (([p0].[BlogId] = @__parameter_2) OR ([p0].[PostId] = @__parameter_3))) AND ([p0].[PostId] > @__parameter_4)

[ilmax]

@smitpatel I would like to give a try to this one

[ilmax]

@smitpatel Hacking a bit the ParameterExtractingExpressionVisitor I was able to obtain the following sql for (almost) the same query as the one you posted here

@__parameter_0='0'

SELECT [p].[Id], [p].[BlogId], [p].[Content], [p].[Title], [p0].[Id], [p0].[BlogId], [p0].[Content], [p0].[Title]
FROM [Posts] AS [p]
CROSS JOIN [Posts] AS [p0]
WHERE ((([p].[BlogId] = @__parameter_0) OR ([p].[Id] = @__parameter_0)) AND (([p0].[BlogId] = @__parameter_0) OR ([p0].[Id] = @__parameter_0))) AND ([p0].[Id] > @__parameter_0)

Still some work left, but the main idea is to keep track of the created parameter and every time TryExtractParameter is called, it checks if it has already created a parameter for the given expression, so at the end of the day I'm just comparing expression equality, for now only MemberExpression are supported and the nice thing is that even having two instances of a MemberExpression referring to the same variable instance, we can use reference equality on the Member property because the same instance is reused across different MemberExpression.

So now I'm asking your feedback on this approach, do you think it's reasonable?

[smitpatel]

@ilmax - We would like to know how are you de-duping in ParameterExtractor. That visitor is first step in query execution and it runs for every expression tree passed into EF. Even if we have previously compiled same query. We don't want to put expensive work inside it because it would increase query runtime. (It is hot path :fire:)
If it is cheap operation, it should be ok to be there.
If it's not then perhaps can be do some de-duping in compilation phase? We could store some extra metadata about parameter during extraction and then during compilation phase, de-dupe them to arrive at smaller set which will be used in query.
You can always create PR or link commit here to get feedback on current implementation.

[anpete]

To echo @smitpatel, we want to try and avoid adding anything to parameter extraction and try and do this in the compiler somehow..

[ilmax]

@smitpatel, @anpete thank you for the explanation, this is what I was looking for.
You can find the actual changes here.
There's still a bunch of work to do e.g. run all tests and ensure no regression are added, so I'm not sure open a PR now is a good idea, I would like to know what you guys think about the changes here, and if you think it's better to avoid this one on the hot path, I will try to push the work down in the compilation phase.

Thanks

[ilmax]

@smitpatel, @anpete I hacked a way to run benchmarkdotnet on the ParameterExtractingExpressionVisitor to verify the performance characteristics of the implementation (using the ExpressionEqualityComparer as suggested in the comments).
This is the result:

BenchmarkDotNet=v0.10.9, OS=Windows 10.0.16299
Processor=Intel Core i7-8550U CPU 1.80GHz, ProcessorCount=8
Frequency=1945313 Hz, Resolution=514.0561 ns, Timer=TSC
.NET Core SDK=2.1.300-preview2-008367
  [Host] : .NET Core 2.0.6 (Framework 4.6.26212.01), 64bit RyuJIT
  Clr    : .NET Framework 4.7 (CLR 4.0.30319.42000), 64bit RyuJIT-v4.7.2633.0
  Core   : .NET Core 2.0.6 (Framework 4.6.26212.01), 64bit RyuJIT


                          Method |  Job | Runtime |      Mean |     Error |    StdDev |    Median | Scaled | ScaledSD |
-------------------------------- |----- |-------- |----------:|----------:|----------:|----------:|-------:|---------:|
          Original_No_parameters |  Clr |     Clr |  2.346 us | 0.0469 us | 0.0882 us |  2.364 us |   1.00 |     0.00 |
   DeDupParameters_No_parameters |  Clr |     Clr |  2.401 us | 0.0474 us | 0.0936 us |  2.408 us |   1.02 |     0.06 |
         Original_Two_parameters |  Clr |     Clr |  8.014 us | 0.1390 us | 0.1807 us |  8.089 us |   3.42 |     0.15 |
  DeDupParameters_Two_parameters |  Clr |     Clr |  8.166 us | 0.1574 us | 0.2206 us |  8.232 us |   3.49 |     0.16 |
        Original_Five_parameters |  Clr |     Clr | 12.293 us | 0.2448 us | 0.4476 us | 12.373 us |   5.25 |     0.27 |
 DeDupParameters_Five_parameters |  Clr |     Clr | 11.662 us | 0.2326 us | 0.6786 us | 11.270 us |   4.98 |     0.34 |
         Original_Ten_parameters |  Clr |     Clr | 19.191 us | 0.2887 us | 0.2410 us | 19.265 us |   8.19 |     0.32 |
  DeDupParameters_Ten_parameters |  Clr |     Clr | 19.117 us | 0.4678 us | 1.3793 us | 19.198 us |   8.16 |     0.66 |
          Original_No_parameters | Core |    Core |  2.069 us | 0.0408 us | 0.0725 us |  2.085 us |   1.00 |     0.00 |
   DeDupParameters_No_parameters | Core |    Core |  1.993 us | 0.0398 us | 0.0882 us |  1.999 us |   0.96 |     0.05 |
         Original_Two_parameters | Core |    Core | 19.673 us | 0.2357 us | 0.2981 us | 19.633 us |   9.52 |     0.37 |
  DeDupParameters_Two_parameters | Core |    Core | 17.754 us | 0.3084 us | 0.2575 us | 17.761 us |   8.59 |     0.33 |
        Original_Five_parameters | Core |    Core | 30.861 us | 0.6451 us | 1.0598 us | 30.488 us |  14.94 |     0.74 |
 DeDupParameters_Five_parameters | Core |    Core | 29.708 us | 0.6505 us | 1.9180 us | 28.856 us |  14.38 |     1.06 |
         Original_Ten_parameters | Core |    Core | 52.280 us | 1.0400 us | 2.6846 us | 51.022 us |  25.30 |     1.58 |
  DeDupParameters_Ten_parameters | Core |    Core | 50.769 us | 0.3828 us | 0.3196 us | 50.798 us |  24.57 |     0.89 |

Original means the ParameterExtractingExpressionVisitor is not trying to de-dup expression parameters (the actual master implementation)
Please note that all expression used in the benchmarks use always the same parameter, so the dictionary lookup return always true, I will add some negative cases in the coming days as well.
Here you can find the benchmark code.

To me looks like there is a small perf regression related to the added code, but a noticeable slowdown as the expression gets more complicated, the worse case is from 8x in .NET Framework to up to ~25x in .NET Core slower than the baseline.
Please let me know if you need me to add some more benchmark and what are your thoughts.

Thanks

[anpete]

@ilmax Looks good to us. I think we would be good with this approach 🎉