Query: Cursor-based pagination++

[benmccallum]

Problem
#17065 will add support for SkipWhile, making cursor-based pagination possible, and is a great step forward, but it doesn't unlock an elegant, single-query/round-trip solution to calculating totalCount, hasNextPage and hasPreviousPage, which are a core part of Relay cursor connections.

Potential solutions
Here's a SQL example that solves this (with one query / round-trip to the server) with use of a CTE, but I'm opening the floor to a way to make this nice and easy with EF Core, perhaps as another extension method?

Another option might be that if it's possible to extract out the WHERE and ORDER BY expressions, this could be done outside of EF Core, by constructing that kind of query I've shown, either just for getting the pagingInfo as another DB call, or, by (if possible) building a raw sql that can execute against EF Core but still map to the entities. This is essentially what I do with SqlKata right now to get this working in a pretty hacky way, based on Corstian's original technique. (see C# in the gist link above).

[sdanyliv]

@benmccallum, interesting SQL solution, but without performance tests I'm not sure that it is effective ;)

Anyway it was small challenge and I had a free hour and tried to implement this via linq2db because library supports mentioned SQL syntax natively. Time were not wasted: I found and fixed bug in our library ¯\_(ツ)_/¯.
Results are here. Also I've added my vision how this SQL should looks like to be more performant:
linq2db/linq2db#2245
Dynamic query creation in diff

In few days this sample will work via linq2db.EntityFrameworkCore

[benmccallum]

Thanks @sdanyliv ! Will take a look. One thing I haven't got in my gist is paging in reverse, though the technique is largely similar.

The inputs become before cursor and last for count.

I'll try update it when I have a moment so we can see if linq2db could also support that.

[rth001]

@benmccallum, interesting SQL solution, but without performance tests I'm not sure that it is effective ;)

Anyway it was small challenge and I had a free hour and tried to implement this via linq2db because library supports mentioned SQL syntax natively. Time were not wasted: I found and fixed bug in our library ¯\_(ツ)_/¯.
Results are here. Also I've added my vision how this SQL should looks like to be more performant:
linq2db/linq2db#2245
Dynamic query creation in diff

In few days this sample will work via linq2db.EntityFrameworkCore

@sdanyliv, Is this working in linq2db.EntityFrameworkCore?

Thanks!

[roji]

I've been doing quite a bit of research on pagination recently - here are some thoughts on this.

The proposed SQL seems to correspond to what this article calls "lower-bound filtering based on row numbering", which is a variant on offset-based techniques for pagination. In other words, it suffers from the same major problems as simple offset pagination: all rows prior to the offset must still be computed and worked through at the database even if they aren't sent to the client, and if rows are inserted concurrently during pagination, the same row will appear twice.

In other words, my current thinking is that good pagination is keyset pagination, at least as long as simple forwards/backwards pagination is involved (random access jumping around pages is different and probably does involve offseting).

As an aside, I believe that at the EF Core level we should concentrate on providing the basic building blocks which can be built upon by higher-level, possibly external layers (at least at first). So I do think we should add row value comparisons, for example (#26822), which are important for performant keyset pagination. And speaking of higher-level layers, https://github.com/mrahhal/MR.EntityFrameworkCore.KeysetPagination may be of interest.

PS Totally unrelated to this, I do believe we should provide common-table expression (CTEs) support in EF, this is tracked by #26486.

[benmccallum]

Thanks for the update @roji.

What do you think of that keyset pagination library @michaelstaib? That seems like essentially what I built on SqlKata (where
I modified the passed SqlKata.Query in-situ), as demo'd here; but on top of EF 🎉 (modifying the actual expression tree) and with a really nice API. Thanks @mrahhal !

I need to walk through it, see what it fires, but it's essentially solving all the same problems. I think mine is a little lighter on the number of queries (as I roll things like hasNext/hasPrev/totalCount into extra rows/cols) to avoid separate queries, but like @roji has mentioned, that's not gonna matter much if the query is slow

[mrahhal]

Thanks for the mention.

single-query/round-trip solution to calculating totalCount, hasNextPage and hasPreviousPage

I haven't looked at this much, but it does feel like doing it this way would involve the same problem that afflicts offset based pagination. So yeah probably isn't worth it, as long as there are good indexes for the keyset query the perf hit of the additional queries is negligible. And this is what I observed in my tests, as the separate HasPrev/HasNext queries added almost no additional time at all to the main query (again, as long as there are good indexes).

[benmccallum]

Also worth mentioning that when I'm using my current approach with SqlKata, I'm using that to get the ordered ids of the set of records I need, then firing an EF Core query with projections to actually get only what I need hah! And that's been fine for us.

I think we can close this now and I'll update as/if needed.

[roji]

Great, thanks @benmccallum and @mrahhal! Do post back here with any additional relevant thoughts, I'm interested in making sure pagination is supported in the best possible way when using EF Core etc.

Note that I also intend to add pagination guidelines to the EF perf docs, summarizing some of the above (this is tracked by dotnet/EntityFramework.Docs#3582).

[mrahhal]

I just remembered something. It looks like EF Core doesn't support specifying the sorting (ASC/DESC) of the column when creating a composite index? While this won't affect the row value usages in EF Core (because row value can't be used with mixed sorting anyway), this means (when using my higher level library) I can't create a good index for a keyset pagination query that acts on a mixed sorting of columns (without having to jump down to raw sql). i.e Score DESC + Id ASC. Any thoughts?

[ajcvickers]

@mrahhal "Add support for index ordering - ASC/DESC and collation" is tracked by #4150 and is currently in the plan for 7.0.