Efcore: Outline guiding principles and decide on direction for queries in 3.0

[ajcvickers]

There are several query-related efforts being worked on or considered for the 3.0 release. This issue is a single place to track and discuss these efforts at a high level as we make progress and decide on direction.

Initial areas to consider:

• Increase test coverage
• Fix query bugs
• Decide on architecture changes, if any. For example internalize or remove Relinq.
• Consolidate and document guiding principles for different types of translations and evaluations. For example, #12668, #12672, #12736, #12737, #12667, #12728, #12736, #12756, #12764, #12775, #12776, #12794, #10434, #12284 (null safety), #13899, #14046, https://github.com/aspnet/EntityFrameworkCore/issues/12761#issuecomment-408555481 (top projection rewrite), #12195
• Decide on keeping full client-eval fallback, going to explicit client-eval only, or moving to a mixture. For example, see #12765, #12844, #12945, #13048, #10265

[divega]

Including here the seminal client-side evaluation proposal Colin Meek wrote:

Implicit boundaries in LINQ to Entities (client-side evaluation)

Overview

LINQ forces us to blur the boundary between the server and the client. For a provider like LINQ to Entities, this means that a query supplied to the stack is always partly evaluated in the client application and partly in the database server. For instance, the query

int productId = 1;
var q =
    from p in context.DbSet<Product>()
    where p.ProductID == productId
    where DetermineProductPriority(p) == "High"
    select new XElement(
        "Product",
        new XAttribute("Name", p.Name),
        new XAttribute("ID", p.ProductId));

includes a selection evaluated by the server (p.ProductId == @productId), but also client expressions, e.g. the binding of the free variable productId and materialization of XML nodes in the projection. It also includes a call to a client-side method on a predicate over a server correlated expression, something that is not supported by either LINQ to Entities or in most LINQ to * implementations.

While we have found it convenient to talk about LINQ to Entities as a strict implementation – all server or nothing – and other implementations such as LINQ to SQL as hybrid implementations – splitting the query into client and server expressions – these implementations really exist along a continuum, and it makes sense to examine this continuum in more detail to clarify the current behavior and how we could improve EF.

It is convenient to discuss this continuum with respect to the following expression scopes:

• _Independent sub-expressions_: in the above query, the access to the free variable productId is compiled into something like Expression.Field(Expression.Constant(CS$<>8__locals6), fieldof(<>c__DisplayClass5.productId)), which does not depend on the current scope of the query (i.e. it is not correlated to the contents of any table in the database). The process of identifying and evaluating these independent sub-expressions has become known as expression _funcletization_ at Microsoft.
• _Client sources_: LINQ queries are typically bootstrapped by IQueryable roots, e.g. dbContext.DbSet<Product>() in the above example.
• _Client projections_: while client sources introduce typed iterators as the root or roots for remote queries, client projections close the loop by shaping typed query results. In the above example, entity results are shaped into XML nodes, new XElement…
• _Dependent sub_-_expressions_: certain sub-expressions can only be evaluated by the client, e.g. DetermineProductPriority…, but depend on intermediate results from the server, e.g. DetermineProductPriority(<u>p</u>).

_Note that these categories are somewhat arbitrary. A client source is a kind of independent sub-expression and a dependent sub-expression is in some ways just a generalization of client projections. The categories are still intuitively useful however: independent sub-expressions often map to parameters while client sources mostly map to scans, and; client projections are frequently benign while dependent sub-expressions are often cause for concern (consider high selectivity filters)._

Implicit boundaries are dangerous but also an essential feature of LINQ. Finding the appropriate balance is important. From feedback we have received over the years, we know that users expect magic and may be disappointed if we either throw because we’re overly strict or we end up streaming 1,000,000 rows from the database into the client to find the 10 rows matching a client predicate because we were too loose.

Independent sub-expressions and client sources

Options:

• _Necessary_: free variables and constants are unavoidable. We need to allow expressions that represent access to field, property and constant in order to implement a viable LINQ provider.
• _Literals_: the LINQ equivalent of value literals. Allow constants (1), primitive type constructors (new DateTime(2008, 5, 28)) and even array initialization patterns (new int[] {…}).
• _Root construction_: currently LINQ to Entities only supports some forms of roots inside the query, e.g. context.Products is recognized, but unfortunately inline construction of query roots is not, e.g. dbContext.DbSet<T>() and context.CreateQuery<T>(string) are not recognized.
• _Server-unsupported expressions that can be converted to server parameters_: currently LINQ to Entities will throw if it finds any expression that it cannot evaluate on the server in a query. If we could turn an independent expression into a query parameter and we know that no part of the expression could ever be evaluated by the server, at least with the same semantics, we could funcletize it. There is an interesting challenge on deciding how much of a sub-expression we can funcletize. For instance, consider the expression stringBuilder.ToString().Length. While the stringBuilder.ToString() part can only be evaluated on the client, .Length could either be evaluated on the client alongside the rest of the expression or translated to LEN(@param) in the store. LEN() in SQL Server has subtly different semantics form string.Lenght in the CLR in that it ignores trailing blanks. We have three options on what we can funcletize:
  a. The minimal sub-expression that cannot be evaluated on the server
  b. The minimal sub-expression that cannot be evaluated on the client plus any expression that can be evaluated on either the client or the server with identical semantics
  c. The maximal sub-expression that can be evaluated on the client
• Options (a) and (b) guarantee that at least for a particular server, all occurrences of such expressions would have consistent semantics, regardless of where they appear in the query. The alternative to this is to evaluate. Option (c) would imply that any sub-expression that can be turned into a parameter would be evaluated on the client. This is the most flexible approach but means we apply inconsistent semantics to some operators depending on which side of the boundary they find themselves on.
• _Server-unsupported expressions that cannot be turned into server parameters:_ We should also explore these. There are interesting solutions where you pipe values through the query to the result, which works when the value is never cracked or cracked at need on the client. This greatly increases the cost of the feature for LINQ to Entities which would need to introduce its own intermediate metadata representation for such values.

Client projection

Options:

• _Composable_: projections that can be composed within a query are supported as client projections. For instance, entities, complex types and “rows” can be projected but arbitrary method calls or constructors cannot.
• _Non_-_composable_: top-level projections could include arbitrary method calls and constructors. For efficiency, reverse funcletization occurs for the client projection, e.g. select ClientMethod1(ClientMethod2(e.X, e.Y), e.Z) becomes select new { e.X, e.Y, e.Z } into f select ClientMethod1(ClientMethod2(f.X, f.Y), f.Z).

Note that method calls may introduce additional round-trips to the server. Before people start shouting about “nanny state APIs”, consider that users are not complaining that they wanted the round-trips but that we failed to crack the methods to figure out how to avoid them…

Dependent sub-expressions

What happens when a sub-expression cannot be evaluated by the server but depends on intermediate results?

• Whenever an unsupported expression is encountered, we could simply split the query at that point (modulo the kinds of local optimizations described for client optimization).
• We should attempt to push as much server logic “down” the tree as possible to minimize the amount of work in the client. This is critical where joins, selections and even some projections are involved.

Interface considerations

If we implement support for these patterns, we should also consider allowing the user to disable them. The user can exercise whatever level of control they want over the client-server partitioning of the query. In addition, we should make the partitioned plan visible to the user, either by using documented boundary expressions or through a debugger visualizer.

Implementation considerations

We can include a separate pass to identify supported and unsupported expressions in the query tree, similar to other LINQ implementations.

[tuespetre]

I love the example with new XElement(...) and immediately see the potential translation into FOR XML PATH. 😉

As for architectural changes and managing query bugs, I feel like there is a lot I could say but I don't know how effective I would be at communicating it.

[ajcvickers]

@tuespetre I'm pretty sure we will want to talk to you about some of this stuff, so stay tuned. :-)

[pmiddleton]

@ajcvickers - In regards to looking at ReLinq. Is #12048 the driving issue behind that, or are there other things driving it as well?

It seems like a major undertaking to remove/replace it given how the tightly the query system is architected around it with a lot of risks for breaking things.

[ajcvickers]

@pmiddleton Other things too, And yes, I agree that it is risky; that is one of the considerations. Sorry for being a bit ambiguous here. Like I said, stay tuned. Don't be impatient. 😉

[pmiddleton]

@ajcvickers - I have the open PR for TVF and am currently working on a pivot feature. Both have tie-ins to ReLinq so the possible change peaked my interest as there might be some rework required on my part. :)

[ajcvickers]

@pmiddleton Agreed.

[tuespetre]

@ajcvickers Heyyy, I’m onto you 👀

[smitpatel]

(not linking individual issues here).
Currently, there are few blockers in current query pipeline due to various reasons which requires some architecture level changes. e.g tracking entity types in all cases properly, Include/correlated subquery with client eval, Type inference in Sql Translation, Include path specification. let queries, client evals and side effects.
Some of them are also linked to things coming from relinq like let queries which generates same reference to subquery model which can be mutated. EF property over collection type props, tracking which we try to identify by tracing querysources.

12048 Brought us need to do something about external dependencies. As "grass is always greener" on other side, we debated & researched on the line, how about removing relinq as query parser and work with expression trees directly. Certainly it doesn't solve all issues with query but it still allows us to get away from limitations we are facing from Relinq right now. As our friend @tuespetre have already written implementation of EF Core query compiler without relinq, we got inspiration that it may be possible to have a query compiler just with expression tree world. So that is what we are going to attempt for 3.0. Even though 3.0 is little bit further out, replacing whole query compiler is a huge task. The big chunk of work will come into SQL translation which is currently done from relinq query model. Trying to change the whole pipeline and also fixing issues (or make it extensible to fix in future), is optimistic goal. We are going to try for it though we may keep older pipeline for a while till we reach good progress with new compiler. This will also require changes in provider codebase.

In the same timeframe we are also going to internalize/remove IX-async and also replace IAsyncEnumerable coming from C# 8.0.

Along the way we are also going to make design decision for some of the issue linked here on the basis of value/usefulness vs complexity. Individual issues would be updated as we make decision.

Hope this clarifies people looking for update. If any confusion, feel free to ask questions.

[pmiddleton]

Is the idea still do a two pass parse and convert the IQueryable expression tree to an AST and then to SelectExpression, or does the team feel that using an intermediary AST is itself one of the problems?

[smitpatel]

@pmiddleton - We want to avoid any intermediary AST. Currently, translation pipelines looks at QueryModel and builds QueryModelVisitor.Expression. We are looking to make it in place translation rather than disconnected.

[pmiddleton]

I have have run into two areas where Relinq has given me a bunch of grief which you might want to think about as you do the rework.

1) Trying to use functions as data sources. When implementing both bootstrapped functions and table valued functions I needed a function to act as the source of the query. Relinq is geared around having a class act as the query source, while a function which returns IQuerable is perfectly acceptable to Linq.

2) Trying to add support for a custom Linq method. The work I am doing for the pivot feature required a new Linq method. There was a lot of formality to get Relinq to understand that new method and parse it correctly. Even once I had the parsing working Relinq still didn't treat the method the way I would have liked. The extension point required pivot to be treated as a result operator when it is really acting as a new query source which change the shape of the query.

Removing the AST should help with both of these issues.

[pmiddleton]

@smitpatel - Is there going to be a public working branch at some point so that we can check things out as they are built?

[smitpatel]

@pmiddleton - Yes. It will take some time to initially bootstrap the compiler.

[ajcvickers]

Update on the plan for query in 3.0

We have been having some deep discussions over what we should do with query in 3.0. These discussions fall into two areas:

• Query behavior and whether we can make query more robust, conceptually easier to understand, and with less chance of regressing by making some high-level changes to the way it works. Most of the issues linked from here relate to this.
• Query architecture. Specifically, should remove Relinq, and, if so, what are the mechanics and architecture changes around this?

Focusing on the second question, at a high-level Relinq provides value in that it normalizes and “simplifies” the expression trees into a model that is conceptually easier to handle. However, as is usually the case with normalization and simplification, the end result can be less flexible to work with and can result in added complexity when the simplified model hides things in the underlying system that are needed. We have found this to be increasingly the case with EF Core, especially when considering non-relational databases. Also, any time a new abstraction is introduced it requires that people understand that abstraction. In this case, this means that people with a good understanding of LINQ expression trees also need to understand Relinq when contributing to EF Core, which can be a blocker for collaboration.

Before going any further, the EF Core team at Microsoft want to make it 100% clear that we have been extremely happy with the quality of Relinq, and working with the Relinq team has been a complete pleasure. Relinq is a great product and does a great job of doing what it does. That being said, after carefully considering our options, we believe that now is the right time to experiment with moving away from Relinq. As we learn from this experiment we may change our mind and keep Relinq, but we expect that the flexibility and experience of working directly with expression trees will turn out to be a better way forward for EF Core.

We will follow up on this post next week with some more details on how we are approaching this from the technical side.

What this means for applications

The removal of Relinq should not impact most application code, since application code does not typically interact directly with the query model.

What this means for database providers

Assuming we achieve the desired results and we end up using expression trees directly instead of Relinq in 3.0, database providers will have to change accordingly. We will update the database providers that we ship (SQL Server, In-memory, Cosmos DB, Oracle sample provider, SQLite) to ensure that they are ready for the 3.0 release. We will also work closely with the owners of other popular database providers like Pomelo MySQL, Npgsql, and SQL Compact, to ensure that they are updated to support this change in 3.0.

[pmiddleton]

@ajcvickers - Is SelectExpression et al going to stay the same, or do you plan to generate the final sql via a walk of the expression tree?

[smitpatel]

@pmiddleton - There will be SelectExpression but it would change some of the features. Perhaps the biggest change in SelectExpression would be around its projection handling. Currently, we add SQL fragment to projection and bind using the index in projection. Which causes quite a few issues in terms of changing projection ordering since there is already ValueBuffer binding somewhere else. (this is the reason we needed RequiresMaterializationExpressionVisitor). The plan is to deviate away from binding straight away. Also we were looking to make it Immutable. I am not certain if that is going to achieve best result but we'll see.

[ajcvickers]

@tuespetre Sent you an email last week--did you get it? If not, what is a good email address to use?

[tuespetre]

@ajcvickers sorry, I did get that but was kind of busy. I replied the other day 👍

Regarding what @smitpatel said, I think he covered what I would have suggested as the two 'first motions':

• moving towards a more 'natural' projection model instead of a 'list' projection model. I accomplished this by heavy use of ValueTuple to tack on and retrieve extra properties, and extension Expressions where appropriate for carrying things 'up the tree' (like Include information.) This goes hand-in-hand with the ValueBuffer thing -- by having placeholder 'column reference' expressions in the projection instead of binding early to a data source, you get multiple benefits:
  
  
  
  • every kind of binding can be handled using Expression constructs, like, "does this member access expression make sense?" No more of the "ok, is what we want in this list of expressions, no, ok, is it in this value buffer, maybe..."
  
  
  • you can optimize away duplicate reader accesses at the latest possible stage
  
  
• making SelectExpression immutable (and everything else Expression/ExpressionVisitor based, for that matter) will make transformations easier to reason about, although it does involve stepping back at times to visualize some higher-order transformations. It makes 'copying and pasting' whole subtrees during transformations fairly easy and worry-free!

[wizofaus]

Would https://github.com/aspnet/EntityFrameworkCore/issues/6482 be relevant in this context? For instance there are entire 3rd party libraries that re-implement much of the Linq->SQL builder because they want it for things like bulk insert/update etc. that EF Core doesn't natively support.

[smitpatel]

@ajcvickers & @divega can answer that.

The current pipeline of EF, especially multiple SQL for collection include etc. makes it impossible to provide SQL easy way.

[divega]

@wizofaus I don't think the decisions we make about this issue will change much about #6482. The main challenge is still that there are are places in which we generate mutliple SQL statements for a single LINQ query, and that is not likely going away in 3.0.

It actually all changed :smile:

[wizofaus]

Pity, that always seemed to me one of the biggest weaknesses of LINQ-to-SQL - that you couldn't really use it at all to construct valid SQL just for condition clauses (in at least one application I worked on, we were able to use an earlier version of EF to generate parameterised SQL then chop off everything before "WHERE" to get the part we needed, but even that doesn't seem to be possible with EF Core).

[GSPP]

These questions are very important to solve in order to enable customers to migrate from LINQ to SQL. We are currently stuck on L2S in a large code base because we depend on client side evaluation.

Client side evaluation was very convenient and useful in L2S. We routinely check the SQL generated by L2S using SQL Profiler and we are very performance conscious. From years of practical experience I can say that L2S got the design right. It just worked.

We absolutely need the final Select to just do the right thing: Pull the required data from the server and evaluate the "tail" on the client. We do not need anything inside the query to be arbitrary code (e.g. a Where). This just has not been useful to us. Maybe there are 1 or 2 places we accidentally do this but it's not important.

We do depend on local evaluation of query parameters, though. This was your stringBuilder.ToString().Length example. A more practical example: where entity.SomeCol == GetFilterValue(httpContext). It is very useful to be able to do this.

We are often hitting the "root construction" issue. For example, we have code patterns like:

var results = (from t1 in db.Table1
                      join t2 in GetFilteredTable2() on ...
                      select new { t1, t2 });

Sub-queries enter the main query in the form of an IQueryable value that is externally generated and passed around. L2S seems to inline these values into the main query and execute this as normal. This is what we want. We also want compiled query caching for this. L2S does not have that but we built a sophisticated intermediate LINQ provider to build caching on top of L2S. This drastically optimized client side CPU cost for us. If EF were to handle that that would be awesome. We could delete a large amount of brittle code.

---

In general, CPU usage is important to us. We found that simple SQL queries take 0.25ms to execute on SQL Server. L2S could easily add 1ms of CPU overhead to this. This is a problem for resource usage as well as for latency if many queries are executed in a row.

As explained we solved this by compiling queries using a proxy LINQ provider.

EF should be conscious of CPU usage: Compiled query caching is important. Evaluation of client expressions should use runtime compiled functions (not interpretation or reflection).

In order to efficiently support caching of "holes" (the GetFilteredTable2() example) we found it necessary to perform two levels of caching. We first match the outer query structure to a cache item. Then, we evaluate the holes. The shape of the hole expressions is of course dynamic. Therefore, when creating the final query tree in order to compile it we need to plug in the holes and perform another round of caching. I assume arbitrary amounts of such nesting are theoretically possible. We found a fixed two levels sufficient for our needs.

---

From feedback we have received over the years, we know that users expect magic

Yes, that is a good characterization of our situation. We require magic to finally be able to migrate. Also, we found this kind of magic to be extremely useful.

[divega]

@GSPP thanks! This is great feedback! I will let @smitpatel provide details about any deltas, but I think what we are set to deliver in EF Core 3.0 matches the design you describe very closely.

[GSPP]

That would be awesome. We are eager to be able to consume all the innovation that is happening with EF.

[divega]

@smitpatel, @ajcvickers any need to keep this open now?

[smitpatel]

I will write certain notes overall about things and close it. Or I can add it to the docs and close the issue with reference to it.

[divega]

Adding a version of this with your notes to a “query architecture” section in the docs sounds great. I guess we can create a docs issue for that and close this anyway.

[jjxtra]

Even simple group by is broken in ef 3, why is this? Seems like a group by should translate to sql statement just fine...

[linkerro]

I second that question and also wonder how this situation makes any sort of sense.
This makes me feel miffed, very miffed.

[smitpatel]

@jjxtra @linkerro - Did you guys look at #17068?