Generate table joins instead of subquery joins

[roji]

For queries with includes, we currently generate joins with a subquery:

SELECT [b].[Id], [b].[Name], [b].[UserId], [t].[Id], [t].[BlogId], [t].[Description], [t].[UserId], [t].[Id0], [t].[Created], [t].[Hash], [t].[IsDeleted], [t].[Modified], [t].[PostId]
FROM [Blog] AS [b]
LEFT JOIN (
    SELECT [p].[Id], [p].[BlogId], [p].[Description], [p].[UserId], [p0].[Id] AS [Id0], [p0].[Created], [p0].[Hash], [p0].[IsDeleted], [p0].[Modified], [p0].[PostId]
    FROM [Post] AS [p]
    LEFT JOIN [PostInstance] AS [p0] ON [p].[Id] = [p0].[PostId]
) AS [t] ON [b].[Id] = [t].[BlogId]
ORDER BY [b].[Id], [t].[Id], [t].[Id0]

We could simplify this to:

SELECT [b].[Id], [b].[Name], [b].[UserId], [t].[Id], [t].[BlogId], [t].[Description], [t].[UserId], [t].[Id0], [t].[Created], [t].[Hash], [t].[IsDeleted], [t].[Modified], [t].[PostId]
FROM [Blog] AS [b]
LEFT JOIN [Post] AS [p] ON [b].[Id] = [p].[BlogId]
LEFT JOIN [PostInstance] AS [p0] ON [p].[Id] = [p0].[PostId]
ORDER BY [b].[Id], [p].[Id], [t].[Id0]

We should measure the execution perf difference between the above two. Even if there is no (significant) difference, we could still decide to do this for SQL simplicity.

Originally raised in #17455.

[Gwindalmir]

Is there any way for a provider writer to override this?

I'm developing an EF 2.2 provider for an older database, and it doesn't support subqueries in a join clause at all. So currently the generated SQL is invalid.

In my case, I'm just executing the git BuiltInDataTypesBase test:

                var entity = context
                    .Set<StringKeyDataType>()
                    .Include(e => e.Dependents)
                    .Where(e => e.Id == "Gumball!")
                    .ToList().Single();

That generates this SQL statement:

SELECT "e.Dependents"."Id", "e.Dependents"."StringKeyDataTypeId"
FROM "StringForeignKeyDataType" "e.Dependents"
INNER JOIN(
    SELECT "e0"."Id" 
    FROM "StringKeyDataType" "e0"
    WHERE "e0"."Id"=N'Gumball!'
) AS "t" ON "e.Dependents"."StringKeyDataTypeId"="t"."Id"
ORDER BY "t"."Id"

However it is invalid for the particular DB vendor, and it must instead be:

SELECT "e.Dependents"."Id", "e.Dependents"."StringKeyDataTypeId"
FROM "StringForeignKeyDataType" "e.Dependents"
INNER JOIN ("StringKeyDataType" "t")
ON "e.Dependents"."StringKeyDataTypeId"= "t"."Id"
WHERE "t"."Id"=N'Gumball!'
ORDER BY  "t"."Id"

I've been digging into the code, and it's hard to find much information on how to change the query generation engine at that level.

Should I open a separate question for this?

[roji]

@Gwindalmir your LINQ query doesn't produce a subquery for me, either on 2.2 and on 3.1:

Repro for 2.2

class Program
{
    static void Main(string[] args)
    {
        using var ctx = new BlogContext();
        ctx.Database.EnsureDeleted();
        ctx.Database.EnsureCreated();
        
        var results = ctx
            .Set<StringKeyDataType>()
            .Include(e => e.Dependents)
            .Where(e => e.Id == "Gumball!")
            .ToList();
    }
}

public class BlogContext : DbContext
{
    public DbSet<StringKeyDataType> StringKeyDataTypes { get; set; }

#pragma warning disable 618
    public static readonly LoggerFactory ContextLoggerFactory
        = new LoggerFactory(new[] { new ConsoleLoggerProvider((_, __) => true, true) });
#pragma warning restore 618
    
    protected override void OnConfiguring(DbContextOptionsBuilder optionsBuilder)
        => optionsBuilder
            .UseSqlServer(@"Server=localhost;Database=test;User=SA;Password=Abcd5678;Connect Timeout=60;ConnectRetryCount=0")
            .EnableSensitiveDataLogging()
            .UseLoggerFactory(ContextLoggerFactory);
}

public class StringKeyDataType
{
    public string Id { get; set; }
    public List<Dependent> Dependents { get; set; }
}

public class Dependent
{
    public string Id { get; set; }
}

Repro for 3.1

class Program
{
    static void Main(string[] args)
    {
        using var ctx = new BlogContext();
        ctx.Database.EnsureDeleted();
        ctx.Database.EnsureCreated();
        
        var results = ctx
            .Set<StringKeyDataType>()
            .Include(e => e.Dependents)
            .Where(e => e.Id == "Gumball!")
            .ToList();
    }
}

public class BlogContext : DbContext
{
    public DbSet<StringKeyDataType> StringKeyDataTypes { get; set; }

    static ILoggerFactory ContextLoggerFactory
        => LoggerFactory.Create(b => b.AddConsole().AddFilter("", LogLevel.Information));

    protected override void OnConfiguring(DbContextOptionsBuilder optionsBuilder)
        => optionsBuilder
            .UseSqlServer(@"Server=localhost;Database=test;User=SA;Password=Abcd5678;Connect Timeout=60;ConnectRetryCount=0")
            .EnableSensitiveDataLogging()
            .UseLoggerFactory(ContextLoggerFactory);
}

public class StringKeyDataType
{
    public string Id { get; set; }
    public List<Dependent> Dependents { get; set; }
}

public class Dependent
{
    public string Id { get; set; }
}

Out of curiosity, which database are you trying to develop for? This issue is about removing a subquery join in a very particular case, but there are quite a few others where doing so isn't possible. Subquery joins are a standard SQL feature, and a database which doesn't support them is likely to have many issues as an EF Core relational provider...

Finally, note that EF Core 2.2 is no longer supported - 2.1 and 3.1 are the current long-term support versions. Any new development should probably happen against 3.1.

[smitpatel]

Just to answer how to do it, add a custom implementation IQueryTranslationPostprocessor deriving from RelationalQueryTranslationPostprocessor and replace ShapedQueryExpression.QueryExpression which would be a SelectExpression with a different SelectExpression to generate same result without subquery joins. If you find any lacking APIs to make required change, then another option is to provider custom IQuerySqlGenerator which will just simplify subquery join to table join when printing it out to DbCommand text.

[Gwindalmir]

Thanks, at the time I started, 3.1 wasn't released, and supporting .NET Framework is a requirement, so I went with 2.2.

I'm not sure why you don't see it, as the SQLite driver included in this source constructs the same query.
I downloaded the release/2.2 tag as my reference point.

As for the DB in question, I'm not sure I should reference it, as I work for the company that makes it. I will say it supports primarily SQL-92 standard, with a few SQL-99 additions.

[roji]

@Gwindalmir the best way would be to open a new issue and include a short, runnable code sample with SQLite that shows it happening.

If you're still in development, I'd strongly recommend considering switching to 3.1 - it's the LTS version for years to come, whereas 2.2 is already out of support.

[Webreaper]

@Gwindalmir I don't see the subquery with a single include or ThenInclude, using SQLite. It took two ThenIncludes for me to generate the subquery (see the example in issue #19418 linked above). That was with .Net Core 3.1.

[Gwindalmir]

@Gwindalmir I don't see the subquery with a single include or ThenInclude, using SQLite. It took two ThenIncludes for me to generate the subquery (see the example in issue #19418 linked above). That was with .Net Core 3.1.

I'm going to migrate to 3.1, and test again. If the issue is resolved there, then that's great. If not, I'll open a new issue here.
Thanks for the help everyone!

[Gwindalmir]

Just as a follow-up, in case anyone else has the same problem:
Upgrading to EF 3.1 solved the issue!

[roji]

Good to hear, thanks @Gwindalmir.

[Webreaper]

Any updates on an ETA for the original issue in this thread to be resolved? :)

[roji]

@Webreaper no update at the moment - this issue is "consider-for-next-release", which means it's a stretch goal for 5.0. While it's considered important, we don't think it's as important as the other issues have have triage into the 5.0 milestone (but it may still get done).

[Webreaper]

Totally understand. Thanks for the update! Looking forward to .Net 5!

[Webreaper]

Errm, looking forward to this in .Net 6? ;)

[Webreaper]

This is a 6-monthly reminder - my queries are taking 950ms when they could be taking under 200ms due to having to workaround this bug. Any chance of a fix in .Net 6 previews 6-10?

[roji]

@Webreaper this is still in the plan for EF Core 6.0, I do hope we'll manage to get it in.

[Webreaper]

Great! Thanks!

[ajcvickers]

Note from triage: putting this in 7.0 to consider doing it in some cases. It is unlikely we will implement this in all cases due to complexity.

[smitpatel]

The basic case when the subquery doesn't have any additional operations (including joins), are converted to table joins in 7.0. This is the case where it is mathematically correct to transform. Leaving up to @roji to determine if there are additional cases which are equivalent in all cases.

[roji]

For reference, @smitpatel's PR for the above is #26476. At some point I'll take a look and think if I can think of other cases.

[yuriy-syrota]

Just to answer how to do it, add a custom implementation IQueryTranslationPostprocessor deriving from RelationalQueryTranslationPostprocessor and replace ShapedQueryExpression.QueryExpression which would be a SelectExpression with a different SelectExpression to generate same result without subquery joins. If you find any lacking APIs to make required change, then another option is to provider custom IQuerySqlGenerator which will just simplify subquery join to table join when printing it out to DbCommand text.

Could you please provide more details on how to do this? I'm working on a project with a complex DB structure. There are queries that are joining two dozen tables using Include().ThenIncude(). It also uses global query filters. So one of these things is causing each table in a join to be replaced with a subquery that does a "select *". Even though this is a small DB (none of the tables have more than 1000 records, each query is taking extremely long.
I experimented with one query. It's translated into a 2 page long SQL and takes 900ms to execute. When I added IgnoreQueryFilters() to it, the SQL produced was 4 lines long and took 2ms to execute.

Please help.

[roji]

Could you please provide more details on how to do this?

Just to make it clear, the instructions you quoted above are about modifying EF itself to implement this, not something to be done in your own application. Unless you intend to contribute this to EF (and it isn't a trivial change to make), this would be relevant for you.

Regardless, can you please put together a minimal database and code sample which shows the significant perf difference with and without query filters? This issue is still lacking a minimal repro which clearly shows the subquery join as being a significant perf issue. Also, in many cases where users encounter such a perf difference, the actual cause lies elsewhere; so it would be good to be sure what's going on.

[yuriy-syrota]

Oh, I thought it was something I could do in my project.
I'll try to put together a minimal project to share with you.

[jzabroski]

Hi @roji - this is some initial thoughts on this issue. Hope to follow up later with some more thorough analysis. Was brought here by a coworker who was stumped by slow queries in both EFCore and EF6, and blamed this issue.

For queries with includes, we currently generate joins with a subquery:
-- @roji , original post in thread

and

Stepping back, his issue was #17622 (comment) opened purely to eliminate subqueries which are unnecessary, replacing them with mathematically equivalent SQL that performs JOINs directly without the subquery:
[...example removed from quote...]
The various subsequent discussions seem to widen this scope and bring in various other questions (at least in some cases) - single query vs. split query performance, or changes to the SQL (INNER instead of LEFT join) which would cause different data to be returned, and therefore would be incorrect.
-- @roji

and

#17622 (comment)
-- @smitpatel

@roji If this issue is for cases where there are equivalent mathematical transforms, then I think I have a regression test to add to the test suite that I discovered today:

For example, if I have a schema like:

1 Transaction ... Has Many Account Allocations
1 Transaction ... Has 1 Transaction Type
1 Transaction ... Has 1 Warehouse
1 Transaction ... Has 1 Currency
1 Account Allocation ... Has 1 Account
1 Account ... Has 1 Group

return Set<AccountAllocation>()
                .Where(a => !a.Deleted)
                .Where(a => a.TransactionType.AffectsPosition)
                .Where(a => a.Account.IsActive)
                .Where(a => a.Account.Group.Id == accountGroupId)
                .Where(a => a.Transaction.TransactDate > cutoffDate)
                .Where(a => a.Transaction.Currency.Id == currencyCode)
                .Where(a => !a.Transaction.Warehouse.IsTransferHub)
                .Take(1) // new command inbetween - this forces a TOP (1) which alleviates some table scan pressure on the query
                .Any();

CLICK ME FOR SQL

exec sp_executesql N'SELECT
	CASE
	WHEN (
		EXISTS (
			SELECT         1 AS [C1]
			FROM
				(
					SELECT TOP (1) [Extent3].[AccountGroupId] AS [AccountGroupId], [Extent4].[TransactDate] AS [TransactDate], [Extent4].[WarehouseId] AS [WarehouseId], [Extent4].[CurrencyId] AS [CurrencyId]
					FROM    [dbo].[AccountAllocations] AS [Extent1]
					INNER JOIN [dbo].[TransactionTypes] AS [Extent2] ON [Extent1].[TransactionTypeId] = [Extent2].[TransactionTypeId]
					INNER JOIN [dbo].[Accounts] AS [Extent3] ON [Extent1].[AccountId] = [Extent3].[AccountId]
					INNER JOIN [dbo].[Transactions] AS [Extent4] ON [Extent1].[TransactionID] = [Extent4].[TransactionID]
					WHERE ([Extent1].[Deleted] <> 1) AND ([Extent2].[AffectsPosition] = 1) AND ([Extent3].[IsActive] = 1)
				) AS [Filter1]
				LEFT OUTER JOIN [dbo].[Warehouses] AS [Extent5] ON [Filter1].[WarehouseId] = [Extent5].[WarehouseId]
			WHERE ([Filter1].[AccountGroupId] = @p__linq__0) AND ([Filter1].[TransactDate] > @p__linq__1) AND (([Filter1].[CurrencyId] = @p__linq__2) OR (1 = 0)) AND ([Extent5].[IsTransferHub] <> 1)
		)
	)
	THEN cast(1 as bit) ELSE cast(0 as bit) END AS [C1]
FROM  ( SELECT 1 AS X ) AS [SingleRowTable1]',N'@p__linq__0 int,@p__linq__1 datetime2(7),@p__linq__2 nvarchar(4000)',@p__linq__0=88,@p__linq__1='2021-11-03 00:00:00',@p__linq__2=N'USD'
GO

then, in EF6, I get a query where the .Where statements without free variables are generated as table joins, but the .Where statements with free variables (accountGroupId, cutoffDate and currencyCode) are left outer joined to all those table joins. This results in a really large number of read operations, because the EXISTS check is after the left outer join. Thus, I have to cheat and add Take(1) to simulate a TOP 1 to get this query to not be terrible on SQL Server. Without Take(1), on a table with > 1.5 million transaction entities in the cut off period, it will scan every one of the pages containing those transaction entities, and takes about 6 seconds to run. With Take(1), it has an initial SQL Server query plan compilation overhead for the first run (on the db server side), and after that, runs in 1 ms flat.

If you see my point, there seems to be broader pattern of how transitive navigation paths are handled. It looks like the previous merges by Smit linked to this issue deal with other scenarios, like OrderBy (query) and HasQueryFilter (model builder configuration) and Includes.

If the broader pattern is transitive navigation paths handling, then I see why @msmolka added a comment here as well. It's also not particularly clear to me why placement of free variables should alter the query, but it seems like it may. There's probably a good reason I do not see why this is happening.

[smitpatel]

@jzabroski - You are posting a SQL generated by EF6. We have no plans to make any changes to that.
Which brings us to question - What is the generated query in EF Core. In the absence of any of those navigation being an owned navigation, all of them would expand on same level without causing subquery as EF6 did. So please run your query in EF Core and if that is not satisfactory to you, file new issue with detailed repro steps.

[CharlieDigital]

@smitpatel Should this be fixed in EFCore 7?

I'm using EFCore7 with Npgsql 7.0.3

I have a reproduction repo here: https://github.com/CharlieDigital/efcore-m2m

docker compose up -d
dotnet run

# Omit the | jq. if you don't want pretty print.
curl http://localhost:5256/init & curl http://localhost:5256/products | jq .

The generated query is as follows:

SELECT p.id, p.created_utc, p.name, t.product_id, t.media_id, t.id, t.created_utc, t.name
FROM products AS p
LEFT JOIN (
    SELECT p0.product_id, p0.media_id, m.id, m.created_utc, m.name
    FROM product_media AS p0
    INNER JOIN media AS m ON p0.media_id = m.id
) AS t ON p.id = t.product_id
ORDER BY p.id, t.product_id, t.media_id

There's a branch with no explicit ProductMedia relationship table: https://github.com/CharlieDigital/efcore-m2m/tree/variant/no-explicit-join

Result is the same.

[roji]

This issue is in the Backlog milestone. This means that it is not planned for the next release (EF Core 8.0). We will re-assess the backlog following the this release and consider this item at that time. However, keep in mind that there are many other high priority features with which it will be competing for resources. Make sure to vote (👍) for this issue if it is important to you.

[CharlieDigital]

@roji That's a shame; this issue has serious performance implications beyond toy datasets and it may not be obvious to users unless they are dumping their SQL that this is the cause of the performance issues.

[roji]

@CharlieDigital can you provide a clear, simple comparison and query plan showing the performance issue? That would help bump the priority of this. Note that I'm not saying we shouldn't do this - it would just help to have a clear, side-by-side comparison showing an exact difference.

[inf9144]

Would also like to see this fixed. Besides the performance - it makes reading the generated sqls really hard. :-/

[CharlieDigital]

@roji on simple queries, the performance is as expected. We've observed the issue when performing deep ThenInclude and ordered sub-queries. For example, an Order that has multiple LineItems which reference a Product which has a set of Media that are ordered.

The workaround that we ended up using is to carry a discriminator field down as deep as practical and then performing a filter on the ThenInclude using the discriminator. For example, consider a case where we have many Stores in the DB.

We would add a StoreId field to Media so that we can filter the Media so we can filter the Media by the StoreId in the ThenInclude.

I've moved off of the project so I'll see if I can find some time to produce a sample project that demonstrates this issue, but we saw queries go from 16s down to sub-20ms on our dataset.

[roji]

We've observed the issue when performing deep ThenInclude and ordered sub-queries. For example, an Order that has multiple LineItems which reference a Product which has a set of Media that are ordered.

That sounds like it could intersect with #29171, which is about removing the orderings from the SQL altogether.

I definitely think there's a potential perf issue here (simple joins instead of subquery joins), but one of the problems is that we haven't yet seen a clear, minimal sample backed by server plans and/or benchmarked query runtime that prove the difference. I definitely intend to investigate this at some point, but such a clear repro would certainly help prioritize this.

[RelativelyRandom]

If you need a demonstration, I just ran an SQLite test, if anyone is interested. I simplified a structure we commonly use in production so it's not an adversarial example or anything like that, just fake data. I can simplify even more, formalize the test and pack it up if someone can provide me with requirements.

We very often have a three-level hierarchy of one-to-many mappings: each Lot has many Parts, and each of those Parts has a few Inspections. If you want to fetch a lot, you could just naively use context.Lots.Include(l=>l.Parts).ThenInclude(r=>r.Inspections).Where(l=>l.Id = 15). Unfortunately, this will generate a query which reads through the entire Parts and Inspections tables.

I populated my test DB with 100 lots totaling about 500 MB and that took over 3 seconds on my laptop. When I refactor the SQL to flat joins, it's done in less than 100 ms. The outputs are identical.

On SSDs this is a nuisance, but on HDDs it's completely unusable. In the past, to work around this, we resorted to hacks like manually querying just the lot, then the min and max IDs of parts inside the lot, then fetching all the parts between this ID range which belong to the lot.

Original SQL with SQLite's query plan:

SELECT "t"."Id", "t"."Barcode", "t0"."Id", "t0"."EndTime", "t0"."LotId", "t0"."StartTime", "t0"."Id0", "t0"."CaptureTime", "t0"."Message", "t0"."PartId", "t0"."Passed"
FROM (
      SELECT "l"."Id", "l"."Barcode"
      FROM "Lots" AS "l"
      WHERE "l"."Id" = 33
      LIMIT 1
) AS "t"
LEFT JOIN (
      SELECT "p"."Id", "p"."EndTime", "p"."LotId", "p"."StartTime", "i"."Id" AS "Id0", "i"."CaptureTime", "i"."Message", "i"."PartId", "i"."Passed"
      FROM "Parts" AS "p"
      LEFT JOIN "Inspections" AS "i" ON "p"."Id" = "i"."PartId"
) AS "t0" ON "t"."Id" = "t0"."LotId"
ORDER BY "t"."Id", "t0"."Id"

QUERY PLAN
|--CO-ROUTINE t
|  `--SEARCH l USING INTEGER PRIMARY KEY (rowid=?)
|--MATERIALIZE t0
|  |--SCAN p
|  `--SEARCH i USING INDEX IX_Inspections_PartId (PartId=?) LEFT-JOIN
|--SCAN t
|--SCAN t0 LEFT-JOIN
`--USE TEMP B-TREE FOR ORDER BY

Refactored SQL with SQLite's query plan:

SELECT "t"."Id", "t"."Barcode", "p"."Id", "p"."EndTime", "p"."LotId", "p"."StartTime", "i"."Id", "i"."CaptureTime", "i"."Message", "i"."PartId", "i"."Passed"
FROM (
    SELECT "l"."Id", "l"."Barcode"
    FROM "Lots" AS "l"
    WHERE "l"."Id" = 33
    LIMIT 1
) AS "t"
LEFT JOIN "Parts" AS "p" ON "t"."Id" = "p"."LotId"
LEFT JOIN "Inspections" AS "i" on "p"."Id" = "i"."PartId"
ORDER BY "t"."Id", "p"."Id"

QUERY PLAN
|--CO-ROUTINE t
|  `--SEARCH l USING INTEGER PRIMARY KEY (rowid=?)
|--SCAN t
|--SEARCH p USING INDEX IX_Parts_LotId (LotId=?) LEFT-JOIN
|--SEARCH i USING INDEX IX_Inspections_PartId (PartId=?) LEFT-JOIN
`--USE TEMP B-TREE FOR ORDER BY