Contains to OPENJSON translation regresses performance

[Suchiman]

After upgrading to EFC8, we've run into several severe performance regressions where millisecond queries started timeouting.
This is due to EFC8 now generating

DECLARE @__p_1 int = 0
DECLARE @__p_2 int = 25
DECLARE @__profileIds_0 nvarchar(4000) = N'[923]'
SELECT [a].[AmsPk] AS [Id], [a].[Bearbeitet], [a].[Amsidnr]
FROM [AmsKunden] AS [a]
INNER JOIN [StorageProfiles] AS [s] ON [a].[Profile_Id] = [s].[Id]
WHERE [s].[Id] IN (
    SELECT [p].[value]
    FROM OPENJSON(@__profileIds_0) WITH ([value] int '$') AS [p]
)
ORDER BY [a].[Bearbeitet] DESC
OFFSET @__p_1 ROWS FETCH NEXT @__p_2 ROWS ONLY

where it used to generate

DECLARE @__p_1 int = 0
DECLARE @__p_2 int = 25
SELECT [a].[AmsPk] AS [Id], [a].[Bearbeitet], [a].[Amsidnr]
FROM [AmsKunden] AS [a]
INNER JOIN [StorageProfiles] AS [s] ON [a].[Profile_Id] = [s].[Id]
WHERE [s].[Id] IN (923)
ORDER BY [a].[Bearbeitet] DESC
OFFSET @__p_1 ROWS FETCH NEXT @__p_2 ROWS ONLY

from my analysis, the problem here is that the cardinality estimator flat assumes that OPENJSON will return 50 rows. If the column that you're filtering on is not very selective, that is enough to dissuade SQL Server from seeking that index. In addition, it also dissuades it from using filtered indexes which requires constants but that's orthogonal. I have a lot of queries where i do .Where(x => col.Contains(x.SomeId)) where col contains in 99% of the time just one element, with the very rare 0 or occasional 2 elements (although more are possible in theory).

Since that is absolutely blocking, i had to apply the CompatLevel 120 hack but i consider that quite the nuclear option, especially since we would like to use more of the ToJson features. The only other option i could see to get around that was to apply a FORCESEEK hint but this isn't (well) supported in EFC either.

CompatLevel 120 works for now but i don't think that's a permanent solution. Query Cache poisoning and frequent recompilations are not remotely as expensive as queries that regress from milliseconds to "can't finish in 120s", so this feature comes at a trade off that is not worth it for us. The naive better solution to workaround this would be similiar to the SplitQuery feature (that has both a global and query level switch).

Include provider and version information

EF Core version: 8.0
Database provider: Microsoft.EntityFrameworkCore.SqlServer
Target framework: .NET 8.0
Operating system: Windows 10
IDE: Visual Studio 2022 17.9P1

[roji]

@Suchiman is it possible for you to provide a repro for this performance regression, i.e. data and a query which show the new OPENJSON-based approach performing significantly worse? That would help deciding what to do here.

[stevendarby]

@Suchiman are the FORCESEEKs in your queries above generated by EF?

@roji sorry if this clouds matters but a problem stemming from cardinality estimates was raised in the original issue and I don't think it was tracked in a separate issue as you requested #13617 (comment). Just a little reminder now in case it's useful to consider alongside this issue.

[Suchiman]

are the FORCESEEKs in your queries above generated by EF?

sorry, no, copied the wrong thing where i was tinkering if query hints would help.

data and a query which show the new OPENJSON-based approach performing significantly worse?

I'll try, the databases i'm working with are anywhere between 400GB and 3TB right now so this might need a whole lot of data to start being reproducible.

[ErikEJ]

@Suchiman How could EF Core determine that not using openjson is better in this case?

[Suchiman]

@Suchiman How could EF Core determine that not using openjson is better in this case?

Not using OPENJSON is likely always better for query runtime as SQL Server can optimize constants a lot better than an opaque input, there are tradeoffs however on query compilation times, tradeoffs that EFC cannot reasonably make assuming it will always improve things. Thus why i suggested of making it a query level option, akin to AsSplitQuery.

[roji]

@Suchiman @stevendarby thanks for your comments; I'm currently away but will be back next and will fully look into this in more detail.

I agree that there needs to be a way to make EF generate constants for Contains, ideally on a per-query basis. I don't think a new operator is needed - such as AsSplitQuery; what's needed is a way to force the array parameter to be interpreted by EF as a constant instead of as a parameter - that's a more general need that we know we have (there are other places where this is a problem). In other words, I think that to force constantization you'd write something like the following (see #31552):

var ids = new[] { 1, 2 };
_ = await ctx.Blogs.Where(b => EF.Constant(ids).Contains(b.Id)).ToListAsync();

In the meantime, as a pretty verbose workaround, you can use the Expression APIs to produce that exact expression tree:

var ids = new[] { 1, 2 };
ContainsMethodInfo ??= typeof(Enumerable).GetMethods()
    .Single(m => m.Name == nameof(Enumerable.Contains) && m.GetParameters().Length == 2);

var parameter = Expression.Parameter(typeof(Blog), "b");
var predicate = Expression.Lambda<Func<Blog, bool>>(
    Expression.Call(
        ContainsMethodInfo.MakeGenericMethod(typeof(int)),
        Expression.Constant(ids),
        Expression.Property(parameter, nameof(Blog.Id))),
    parameter);

var results = await ctx.Blogs.Where(predicate).ToListAsync();

This produces the same query tree as when the array is written inline in the query:

var results = await ctx.Blogs.Where(b => new[] { 1, 2 }.Contains(b.Id)).ToListAsync();

... and generates the desired SQL:

SELECT [b].[Id], [b].[Name]
FROM [Blogs] AS [b]
WHERE [b].[Id] IN (1, 2)

This is by no means a satisfactory workaround - I know - but I'm posting it here in case you want to keep the SQL Server compatibility level (for other queries) and override the behavior on a per-query basis, today with 8.0.0.

One note: if you know you have a certain number of elements in the parameterized array, you can use an inline array as follows:

var result = await ctx.Blogs.Where(b => new[] { ids[0], ids[1] }.Contains(b.Id)).ToListAsync();

This is recommended for when you know the number of elements, producing the following SQL:

SELECT [b].[Id], [b].[Name]
FROM [Blogs] AS [b]
WHERE [b].[Id] IN (@__p_0, @__p_1)

In any case, I'll take a look at how EF.Constant support would look like and whether it's even possible to consider it for an 8.0 patch.

[ErikEJ]

@Suchiman You might find this extension method useful, uses parameters and simple ORs https://gist.github.com/ErikEJ/6ab62e8b9c226ecacf02a5e5713ff7bd

[stevendarby]

@Suchiman I would just like to understand what's happening on the SQL Server side a bit more, if that's ok! Regarding this:

the problem here is that the cardinality estimator flat assumes that OPENJSON will return 50 rows. If the column that you're filtering on is not very selective, that is enough to dissuade SQL Server from seeking that index.

Is the implication here that SQL Server would also avoid seeking the index with an IN containing 50 hardcoded values (because it would know there are 50 and not just estimate that)? If so, and turns out it's really slow doing that - doesn't that seem like an odd decision for SQL Server to make? Are your statistics up to date - could that influence its decision?

Out of interest, does adding TOP 1 in the OPENJSON subquery correct its estimate and get it to use the index? I was half wondering if bucketizing a hint like that, so that the estimate is at least within the right order of magnitude, could be a solution: TOP 1, TOP 10, TOP 100 etc. Or maybe there is some other kind of hint that could be used. It would lead to multiple query plans for different sizes, but each might be better performing and the number of them still much lower than pre-EF 8. I've not investigated this though and it might be a complete non-starter.

Anyway, @roji's suggestion seems like a good way forward.

[roji]

I also had @stevendarby's good questions in mind, and definitely still would like to see some sort of repro for this so that we can dig deeper into exactly what's going on... That could help us decide to what extent a patch here is needed for 8.0.0.

[Suchiman]

Is the implication here that SQL Server would also avoid seeking the index with an IN containing 50 hardcoded values (because it would know there are 50 and not just estimate that)?

Well SQL Server is really an oddball here. If i use WHERE [s].[Id] IN (@p1,@p2) then having 2 params is already enough to make it choose badly (estimated plan but it's the same bad shape):

If using hardcoded constants like WHERE [s].[Id] IN (1,2,3,4,5,6...), then it takes 61 constants before it tips over (estimated plan but it's the same bad shape)

If so, and turns out it's really slow doing that - doesn't that seem like an odd decision for SQL Server to make? Are your statistics up to date - could that influence its decision?

Doing a statistics update with fullscan is always the first thing i try, i wish that would help all the time 😆

Out of interest, does adding TOP 1 in the OPENJSON subquery correct its estimate and get it to use the index?

That does indeed work, and it seems like for SQL Server, the tipping point is exactly 50 in my case, with TOP (49) i still get the fast plan, with TOP (50) its the slow plan. One could think to make EFC generate TOP(@p_n), that allows both query plan caching and through the magic of parameter sniffing, to get a better plan, including all the gotchas of parameter sniffing such as getting a bad reused plan as well.

[roji]

Thanks for all the extra info and experimentation @Suchiman, that's definitely useful. I know it isn't easy, but some sort of repro for this would allow further investigation and possibly taking this to the SQL Server people to maybe get more insights.

Otherwise, I'm generally averse to EF generating something that's super-tailored to an internal SQL Server quirk (i.e. the TOP - with what exact threshold etc.)... If we see that this is indeed some sort of general thing for all queries using IN, that might make sense, but otherwise I'm not sure what we can do here. You should at least be able to get EF to generate the TOP yourself, i.e. by composing a Take on the parameterized array.