Translate queries where a row includes a collection to use arrays instead of being implemented through joins

[Emill]

Following discussion in #712.

Consider queries like

var blogs = context.Blogs
    .Include(blog => blog.Posts)
    .ToList();

or something like

var blogs = context.Blogs
    .Where(...)
    .Select(b => new
    {
        BlogTitle = b.Title,
        LargeColumn = b.LargeColumn,
        LastPosts = b.Posts.OrderByDescending(p => p.Id).Take(4).Select(p => p.Message).ToList()
    })
    .ToList();

This might either lead to "cartesian explosion" if implemented through joins, or result in multiple duplicated work at the server if split-query strategy is used (https://docs.microsoft.com/en-us/ef/core/querying/single-split-queries).

PostgreSQL is capable of returning a record[] in a column, which can contain a result set of a subquery. It seems like other query engines can take advantage of this, for example in GraphQL https://www.shanestillwell.com/2017/09/15/postgresql-json-and-graphql/, although json is used instead of record[] to encode the data instead.

I've done some initial performance testing regarding PostgreSQL's query plans.

There are basically two strategies, executing a subquery and join + group by + aggregate.

Subquery:

select *, array(select row(tbl2.*) from tbl2 where tbl1.id = tbl2.tbl1id) from tbl1

Join + group by + aggregate:

select tbl1.*, array_agg(tbl2) from tbl1 left join tbl2 on tbl1.id = tbl2.tbl1id group by tbl1.id

The first strategy includes a subquery which will be executed once per row. This means O(n*m) if there is no foreign key index, due to it will perform a full sequential scan on tbl2 for each row in tbl1, which is pretty bad. However, when there is an index for the foreign key, it can be used and hence result in optimal time complexity. An extra inner join inside the subquery in the case of a many-to-many relationship also just uses the primary key index on the third table to follow the extra redirection, which is good.

The second strategy results in a similar query plan compared to using just a traditional left join, plus a sort (if indexes are not available for the foreign key) plus an aggregation. So this basically changes overhead in network traffic (or cartesian explosion in case of 2 or more joins) to some simple aggregation work on the server side.

If there are nested includes (i.e. tbl1 [has-many] tbl2 [has-many] tbl3), then the first strategy will result in a simple and efficient query plan (assuming indexes exist!), while the second one becomes more complex assuming aggregation is performed after every join.

Depending on the specific data and query, a normal join could of course sometimes be more performant, especially if the data that is being duplicated is small.

To me this still looks very promising and I guess it could improve performance over split-query, to avoid the backend to perform duplicate work. It could really be a killer-feature in my opinion when the user wants to perform a complex query including many navigations, or when the returned data is more like a complex json structure than a 2D table. Probably a lot of work must be put into the efcore repo.

[roji]

Thanks for putting this together @Emill, I agree it's a very promising direction for the PG provider.

This means O(n*m) if there is no foreign key index, due to it will perform a full sequential scan on tbl2 for each row in tbl1, which is pretty bad. However, when there is an index for the foreign key, it can be used and hence result in optimal time complexity.

EF Core automatically creates indexes for foreign keys, so I don't think this should be too much of a concern. Also, if there's no index, won't regular JOINs be equally bad?

Depending on the specific data and query, a normal join could of course sometimes be more performant, especially if the data that is being duplicated is small.

Sure. In any case, this will very likely be an opt-in strategy - just like split query is an opt-in in EF Core - so users will be able to experiment and select the right strategy.

In general, this is likely to be quite a huge task, involving lots of internal knowledge of EF Core, and would likely require some changes on the EF Core side as well (one advantage of the subquery strategy is that it doesn't rely on custom aggregate methods - dotnet/efcore#22957). If you're interested in giving this a try, I'll be happy to help in whatever way I can.

/cc @smitpatel @ajcvickers

[Emill]

EF Core automatically creates indexes for foreign keys, so I don't think this should be too much of a concern. Also, if there's no index, won't regular JOINs be equally bad?

Not necessarily. It can use a sequential scan on both tables (once) and then use a hash join to combine them. A subquery executing a full sequential scan with a filter is basically the same as a nested loop join strategy.

In general, this is likely to be quite a huge task, involving lots of internal knowledge of EF Core, and would likely require some changes on the EF Core side as well (one advantage of the subquery strategy is that it doesn't rely on custom aggregate methods - dotnet/efcore#22957). If you're interested in giving this a try, I'll be happy to help in whatever way I can.

I'm currently reading through EFCore.Relational.Query to get a grasp of how EF Core actually works internally, and how much big of a work this would be.

[Emill]

This seems also a perfect fit for implementing the currently non-supported GroupJoin LINQ method.

[roji]

That's possible, but note that in many cases GroupJoin is rewritable to other LINQ constructs, see dotnet/efcore#19930.

[Emill]

Ok so I've now implemented a proof-of-concept for this for the case of collections and include collections.
Right now it doesn't require any changes in Npgsql, and therefore uses reader.GetFieldValue<object[][]>(index) ro retrieve a record[], which works fine in most cases, but not when fetching customized data types or literal strings (unknown type).

My work starts in the query pipeline at CollectionJoinApplyingExpressionVisitor, which is now replaced by a CollectionArrayApplyingExpressionVisitor. This now adds an ARRAY(SELECT ROW(...) ...) subquery to the current SelectExpression instead of adding a join.

Most work is however done in the materializer (RelationalShapedQueryCompilingExpressionVisitor.ShaperProcessingExpressionVisitor). An inner shaper is created for every level, and the new function PopulateCollectionArray is called for every record[][] which then calls the inner shaper. To read inner fields, the dbDataReader calls are replaced by indexing into the object[] representing the current record.

This new approach naturally makes some previously unsupported queries now work. See https://docs.microsoft.com/en-us/ef/core/what-is-new/ef-core-5.0/breaking-changes#collection-distinct-groupby and dotnet/efcore#15873. Since the identity key is no longer needed to correlate the results, these kinds of queries no longer throw InvalidOperationException.

I've ran the tests and so far I've only noticed three kinds of reasons why tests fail:

1. The correct types are not read, as stated above, which causes things like byte columns (which are represented as int2 in PostgreSQL) to fail, due to unsupported implicit conversion between short and byte. Also string literals in collections don't work (due to unknown type).
2. Tests where InvalidOperationException are expected, but now succeed, or throw other errors while verifying the result due to bugs in the tests.
3. Tests where the result is not unambiguously ordered (.OrderBy), but the verifying code nevertheless expects a certain order.

Since arrays and records are PostgreSQL only (I think?), I'm not sure if this should be put into the efcore repo or efcore.pg repo. I find it a bit hard to put in efcore.pg due to the many internal changes in the inner core. On the other hand - there are a bunch of features in the core repo which only a few databases support. Anyway, potentially it would be possible to detect if only simple types are used (string, int, null etc.) and in that case return a json tree from the server, which should be supported by for example MySQL (https://stackoverflow.com/a/41760134/556495). The exact same strategy could be used for that approach as the array-of-rows one.

The next feature that can make use of this array approach is the kind of group by queries, where we extract a whole collection as an array with ARRAY_AGG, grouped by some key.

[Emill]

Link: Emill/efcore@c283075.

[roji]

/cc @smitpatel you may want to have a look at this

[roji]

@Emill thanks again for looking at this complicated and very promising direction. It's really, really nice to see this loading strategy starting to work with EF Core.

I am not an expert in some of the areas you touched, and @smitpatel will likely have to help us out here quite a bit - I've already had a first brief discussion with him. However, since arrays are a PostgreSQL-specific functionality, the first thing to do here is to plan how we can move most of this functionality into EFCore.PG, and to identify where we need (hopefully minimal) modifications from the EF Core side. For example, things like RowExpression and ArraySubqueryExpression definitely don't make sense outside of EFCore.PG and should not be in EF Core (e.g. the SQL Server provider shouldn't need to worry about these). I think @smitpatel may have a slightly different factoring in mind which would reduce the need to change EF Core much.

[smitpatel]

Overall when utilizing arrays, what we need is to bypass whole pending collections thing since there is no collection in SQL anymore from join form. So when translating a collection for a projection perspective the translation itself can be made array. This would make array type SQL expression and related binding automatically go into projection. The shaper for this array would be specialized, which utilizes the info that we will get array from database which we will need to enumerate and apply a shaper on top of it.
An example of that is in InMemory here
https://github.com/dotnet/efcore/blob/d40410d0718206c6d827c06afe650faa15ffc5b6/src/EFCore.InMemory/Query/Internal/InMemoryProjectionBindingExpressionVisitor.cs#L501-L514
Note: the in-memory implementation just uses everything internal since it is all provider code. It may not be possible to exactly same thing for postgre since not all class is made publicly extensible in postgre. Let's try approach this way and we can figure out what we need to do in EF Core to allow provider to extend if further.

[Emill]

My proof-of-concept implementation is very similar to the InMemory variant. I admit the pending collections thing could be bypassed - I just did it this way to minimize code change compared to the join strategy. But now when I see the InMemory implementation I guess the code change would possibly be similar if it was simply bypassed. The rest of the code is conceptually very similar to the InMemory provider.

So most of the changes to support this are actually in the materializer/shaper code. Conceptually implementing collections using arrays instead of joins is in fact much simpler. One big difference is that the "value buffer" to read data from, compared to InMemory or Cosmos is that depending on what level we are at, the value buffer works differently. At the outermost level, we use a SELECT expression together with one or more projections SELECT a, b, c FROM ..., and then use a DbDataReader to fetch individual columns. At any other level, we must use the form SELECT ROW(a, b, c) FROM ... instead, wrapped in an ARRAY(...) expression and then read individual columns using an object[], where the array is represented as an object[][]. Right now the projection indexes used for bindings for a, b, c are 0, 1, 2 but point to the contents inside the ROW value, while we also have a RowExpression as the only projection in the inner SelectExpression. These differences make it slightly more complex than the InMemory and Cosmos providers.

Maybe we should use @roji's strategy of returning an inner data reader in Npgsql as explained in npgsql/npgsql#3558 after all (outerDataReader.GetFieldValue<DbDataReader>(index)), to make the implementation deal with only one type of data reader. We will need some kind of mechanism to choose the data type an inner column should be read as anyway to support this array feature properly.

[roji]

@emil it all sounds good/right to me. I'd again be happiest if we could move forward on the EF side and leave the Npgsql interface for a bit later and resolve as much as possible on the EF Core side. But if this is starting to interfere, i.e. if the work to implement things today with object[][] is too difficult (and would possibly be thrown away), we can pause and discuss that other side too.

BTW FWIW it could be a nice feature for Npgsql to be able to return record as ValueType, even if we end up not using that for EF array materialization; as a user, I think that's how I would typically want to read these results in .NET. On the other hand, users generating and reading records seems like a very rare scenario.

[Emill]

Yep, I feel I'd like to avoid working with object[][]. I guess it's up to you in the EF Core team to decide how to open up and make it possible to put the relevant code inside efcore.pg instead of efcore. If you want, I can try to evaluate different strategies and come up with some options.

[smitpatel]

The only place where interaction would become complicated when "GetValue" doesn't have T as a mapped database type. i.e. DbDataReader. At that point, not only the GetValue injection part which is reading value from server needs to change, you would also need to add another level of processing to materialize from that DbDataReader. Is there any specific value in getting DbDataReader back from server for a collection compared to object[][] (or other suitable type like record[] or compositetype[])? Having it as a mapped type which is collection of other mapped type makes processing a lot easier. Also the real materialization, should require very little work with approach I mentioned by converting the special shaper expression into client method before EF Core processes it. Once we are in shaper, client methods are processed like base visitor.

Regarding ValueBuffer vs DbDataReader, currently from conceptual perspective, we don't have DbDataReader. We have an abstract object, which will provide us database mapped type value in our client code. That value can be accessed via

• int index in a ValueBuffer object (which is equivalent of an object[])
• int ordinal in DbDataReader
• string based name in DbDataReader
• string based key in a JSON

InMemory puts an array of ValueBuffer inside one of the slot of ValueBuffer. Putting a composite type[] inside one of the column in DbDataReader is equivalent.

[roji]

@smitpatel I think the main reason for wanting to avoid object[][] is because that would box for all value type column values.

[Emill]

If we just ask Npgsql for an object[][] for a specific column (reader.GetFieldValue<object[][]>(index)), Npgsql won't know what data types we want in the inner values. It currently uses the default type mapper for whatever data type being returned from the server, and casts it to an object. If Npgsql returns a DbDataReader for a column, we can (recursively) use the GetFieldValue API to read a column using a specific CLR type, which is needed to be supported for EF Core. Currently such tests fail with my current implementation.

As @roji mensions, object[][] also might create a boxing overhead (don't known how significant that is though in this case).

We could add ValueTuple<T, ...> or Tuple<T, ...> support for Npgsql's data reader, to be able to ask for e.g. reader.GetFieldValue<Tuple<int, string, Tuple<int, DateTime>[]>[]>(index). That's another way of solving the problem, but of course might create unnecessary objects that we're going to throw away soon after materializing into the final entities.

I just realized that later method naturally works good when we must use the BufferedDataReader. If we use a DbDataReader for every record[] column, we must make sure those objects work even when the reading is complete in the outer reader.

Do you think it would be an issue of creating a bunch of types at runtime such as Tuple<int, string, Tuple<int, DateTime>[]>[]? From what I understand, types defined at runtime cannot be garbage collected, so that might lead to some memory leak if you generate LINQ queries dynamically.

[roji]

Apologies in advance for the long comment.

If we just ask Npgsql for an object[][] for a specific column (reader.GetFieldValue<object[][]>(index)), Npgsql won't know what data types we want in the inner values. It currently uses the default type mapper for whatever data type being returned from the server, and casts it to an object. If Npgsql returns a DbDataReader for a column, we can (recursively) use the GetFieldValue API to read a column using a specific CLR type, which is needed to be supported for EF Core. Currently such tests fail with my current implementation.

Right, that part is even more important than the boxing allocations with object[][]. It's similar to the difference between calling generic DbDataReader.GetFieldValue<T>() and non-generic DbDataReader.GetValue(): the latter is problematic when the database type doesn't by default map back to the expected EF Core (supplied as T in the former).

I just realized that later method naturally works good when we must use the BufferedDataReader. If we use a DbDataReader for every record[] column, we must make sure those objects work even when the reading is complete in the outer reader.

That's one of the reasons I'm a bit apprehensive of the nested DbDataReader approach, or indeed any approach where DbDataReader exposes a field access API with lifecycle management issues. To solve this, we could return a disposable RecordReader object (similar to DbDataReader but disposable), and if NpgsqlDataReader.Read is called before the RecordReader is disposed, we create a copy of the row's memory that's owned by that reader (this assumes we don't support CommandBehavior.SequentialAccess. If we do, the record's memory also needs to be cloned out when reading the next field). This way, without BufferedDataReader, each record is consumed before the next one is requested, and everything is efficient (no copying). With BufferedDataReader, raw binary data is copied out record-by-record, with each row's memory owned by its RecordReader.

Do you think it would be an issue of creating a bunch of types at runtime such as Tuple<int, string, Tuple<int, DateTime>[]>[]? From what I understand, types defined at runtime cannot be garbage collected, so that might lead to some memory leak if you generate LINQ queries dynamically.

This indeed worries me more than the throwaway array allocations associated with this approach (I've recently seen even more evidence that short-lived (gen0) allocations have very little actual perf impact in meaningful metrics (e.g. RPS in TechEmpower Fortunes)). Indeed, if there's an explosion of query projection shapes because (mainly due to dynamic query construction), we'd have an explosion of generic types, which may be problematic. I'm not sure how problematic this is.

It feels like at this point a summary of our options could be useful:

• Option 1: Read object[][].
  • PRO: Extremely simple (already implemented in Npgsql today).
  • PRO: No lifecycle issues since fields are decoded and copied out immediately, so compatible with BufferedDataReader and similar.
  • CON: The API consumer doesn't the expected field types, so this will fail when the database type doesn't by default map back to the expected EF Core. This is probably a show-stopper.
  • CON: Many throwaway allocations are generated - both the value type fields which are boxed and the arrays containing the object representations.
    reading strategies.
• Option 2: Read ValueTuple<...>[]
  • PRO: The API consumer does specify the expected field types, so no mapping issues as in option 1.
  • PRO: As in option 1, no lifecycle issues since fields are decoded and copied out immediately, so compatible with BufferedDataReader and similar.
  • PRO: Less allocations than option 1, since fields aren't boxed. The arrays are still allocated though.
  • CON: Possible generic type explosion in some dynamic query scenarios.
• Option 3: Read RecordReader[] (disposable NpgsqlDataReader-like API)
  • PRO: No additional CLR types are used as in option 2, so no potential for type explosion.
  • PRO: Like option 2, less allocations than option 1, since fields aren't boxed. The arrays are still allocated though.
  • CON: Lifecycle issues since fields are decoded late, so memory may need to be copied out etc. Non-trivial complexity and potential for subtle bugs.

Orthogonal to the choice made above, we could also introduce something to avoid the array allocation, but we'd probably need to solve This would have the same lifecycle issues with BufferedDataReader. Since this only avoids an array allocation per object, I'm not sure it's worth the complexity (at least not in an initial implementation).

I think option 1 above is excluded because of the type mapping issue - but I'm hesitating between option 2 and 3. The only disadvantage of 2 seems to be the potential type explosion, which wouldn't be a concern in most applications; heavily dynamic applications could simply not opt into this loading strategy (using classical EF's single/split query strategies instead), but discoverability is very problematic here (how would even know they have this problem etc.). 3 is the most complete option, but adds some considerable complexity. Since that's its only drawback, I'm slightly leaning towards 3.

Thoughts? Have I missed other options or tricks?

[Emill]

With option 3, speaking for the Npgsql provider now, can't the RecordReaders just store a reference to the backing array that the original NpgsqlDataReader, including the range for this sub-part? That way we avoid copying for every level. When Read() is then called on the outer reader, NpgsqlDataReader remembers that a RecordReader is having a reference to the array, so instead of recycling the array, it creates a new one for the next row. This can actually be used to build an Npgsql-specific BufferedDataReader if you think of it that way...

[roji]

@Emill that's pretty much what I was proposing above - RecordReader would be a thin view over a portion of the internal NpgsqlReadBuffer (conceptually similar to a Memory<byte>). Either NpgsqlDataReader causes a new array to be created on Read (when undisposed RecordReaders still exist), or the RecordReaders are informed and copy their relevant portions out; the latter may be more efficient since Npgsql's internal buffer is big (8K by default), and we'd need to allocate a new one for each row. But I guess that's going a bit too deep into implementation details (in any case I'm sure @smitpatel doesn't care much 🤣).

[Emill]

Maybe an implementation detail, but I was thinking that when Read() is called on the outer reader, if there are still undisposed RecordReaders, we can assume the user will create a RecordReader somewhere for this next row too, so just create a new array of the exact size, as returned by postgresql in the row header for the next row.

[roji]

That's a good optimization, i.e. detect the "buffering" usage pattern early and switch to a different mode. However, I'm a bit scared of the complexity all this stuff is going to add to NpgsqlDataReader (which after all would only be useful to support this). But we can give it a try and see where it leads.

BTW rather than RecordReader it should probably be called RowReader, as it would also be usable with composite types (mapped or not).

[Emill]

I'm leaning towards making the NpgsqlRecordDbDataReader only valid as long as the current outermost row is valid, i.e. until Read() is called. Then it can just refer to a span of the current read buffer (in case of non-sequential mode). The NpgsqlReadBuffer is not at all designed to use a plain array as backing buffer without socket or connector, which is kind of needed if it should still be valid when the outermost reader advances to the next row. Instead EF Core could create inner BufferedDataReaders, object[] or something if it wants to buffer the whole result. The ReaderColumn dynamic functions can be used to create such an inner structure, which will be called at the initial pass when the original reader is executed.

[roji]

I'm leaning towards making the NpgsqlRecordDbDataReader only valid as long as the current outermost row is valid, i.e. until Read() is called.

That would involve some additional customization on the EF provider side, which it may be better to avoid. It's true that currently NpgsqlReadBuffer expects to have a socket and a connector, but I'm not sure how much work it would be to make it behave correctly as a pure memory buffer wrapper. But it's really up to you.

We can also defer the question and ignore BufferedDataReader for now - arriving at a point where everything works like we want without buffering would already be a really nice achievement. We can then revisit this question.