Allow users to express SQL row value comparison syntax

[mrahhal]

Row value is part of the SQL standard -though not supported by every database in all places- and it allows using the following syntax (for example in a where clause):

WHERE (timestamp, id) > ('2019-03-10 00:00:00+00:00', 1032749689)

This is in particular a highly valuable syntax when doing keyset/seek/cursor pagination, and being able to use it with databases that support it will be a big win for seek pagination in particular, but also composite conditions that can gain from this syntax in general.

The row value syntax above is equivalent, in theory, to something like this:

WHERE
    (timestamp > '2019-03-10 00:00:00+00:00') OR
    (timestamp = '2019-03-10 00:00:00+00:00' AND id > 1032749689)

But, for one, this logic condition becomes more complex the more columns you have. In addition, the db implementation of row value will usually be much more efficient than this (there are a few things you can do that can help the db engine in the above condition, but it doesn't look nice or readable).

More info about row value here: https://use-the-index-luke.com/sql/partial-results/fetch-next-page#sb-row-values

My use case is a package I worked on that fully implements keyset pagination with EF Core, but does so by building the expressions so that it translates to the logical condition syntax above. I could use a row value translator.

For a related issue to keyset pagination see this: #9115

Proposed solution

What I would love to see is a db function that EF Core understands and translates into the row value syntax for db providers that support it. Something like this:

var timestamp = ...;
var id = 1032749689;

// One option:
.Where(b => EF.Functions.GreaterThan(new[] { b.Column1, b.Column2 }, new[] { 1, 2 }))
// Another option with a tuple override:
.Where(b => EF.Functions.GreaterThan((b.Column1, b.Column2), new[] { 1, 2 }))

// Translates to sql:
// WHERE (timestamp, id) > ('2019-03-10 00:00:00+00:00', 1032749689)

One thing I'm not sure of is if there's a system in place that would allow a consumer to know if the current database provider supports this syntax or not. Because I want to be able to fallback to my implementation in such a case.

If this seems like an interesting and feasible addition, I'm willing to work on it.

[roji]

This is supported by PostgreSQL, SQLite, and MySQL (though your linked article claims that it isn't index compatible - that may have changed); it's not supported by SQL Server. I've just been looking into this recently, with regards to keyset pagination (see this deck, slides 22-23).

First, since row value comparison ((x, y) > (1, 2)) is logically the same as the decomposed version (x > 1 OR x = 1 AND y > 2), there may not be any actual value in specifying the former rather than the latter. The SQL is indeed terser/nicer, but the C# to express something like this wouldn't be (since C# doesn't support comparison over tuples). So if this has no actual perf benefits, I'd say it's better for users to simply write out their keyset pagination clause in C# as above. Are you aware of any such perf benefit?

Note that in the PostgreSQL, I recently implemented pattern matching over the decomposed version, identifying it and generating row value comparison in SQL instead (see npgsql/efcore.pg#2111, this was mostly a fun little project without any specific benefits in mind). This means that the C# side stays ugly, but the SQL becomes terser/nicer. We could promote this to relational, but I do think that should be done if there's a tangible benefit to doing so (beyond terser SQL).

[mrahhal]

Are you aware of any such perf benefit?

I've investigated this, and yes I'm sure of at least one perf benefit. In PostgreSQL, I created a table with a million records, and I have an index on created + id. I'm doing a simple seek + limit on the 2 columns. Here's the execution plan for a logical condition (x > a OR x = a AND y > b):

There's an Index Scan with a filter operation.

In contrast, here's the execution plan when using row value instead:

There's an Index Condition instead, which at least utilizes an access predicate on created, and maybe other columns if there's a valid index to use.

The difference stems from the fact that no db will be able to realize that it can use an access predicate on the 1st column when using the logical condition, but it understands exactly what access predicates to use when using row value. One way to force all dbs to recognize this without using row value is to add a redundant clause as following:

(x >= 1) AND
(x > 1 OR (x = 1 AND y > 2))

The first line above results in the db using an access predicate before filtering:

This optimization is something I also implemented here.

I'm not sure if this exactly matches in perf a db implemented row value for 2 columns, but it definitely won't match it for more than 2 columns (it'll be harder to keep generating these access predicate hints in the logic conditions properly then).

(There's one alternative form to do this without using a redundant clause, but it's much much harder for a human to understand.)

My test table is extremely simple (which is also why the filter had nothing to do after the access predicate), I'm sure the perf benefit will be more apparent in the real world.

---

I want to emphasize again how much easier it is to form the row value syntax than a generalized logical condition when we're dealing with more than a few columns. Granted, it's rare to have a query doing this over more than 2-3 columns, but anyway, the generalized condition expression for this is:

(x > a) OR
(x = a AND y > b) OR
(x = a AND y = b AND z > c) OR...

It's very easy to get wrong (and a horror to maintain).

---

npgsql/efcore.pg#2111

This is great. Trying to translate into row value from a db function instead of pattern matching will obviously be much easier too.

Also, when using efcore.pg, I'm wondering (haven't checked much of the code) if this will pick up the generated condition expressions I dynamically form in my package, since there's the additional optimization I have with the access predicate clause which might throw your pattern matcher off. (But with a quick look, it seems that it needs a very specific form when there's 3 columns, which wouldn't work with the generalized logical condition, and no support for more than that?).

---

In conclusion, I do think it has performance benefits as the db can optimize the execution because the intent is clear, and it would still be much easier to write in C# (even if uglier than others) than forming the error-prone logical condition ourselves.

I think there's also a lot to gain if the EFCore db provider that's being used automatically either choses to translate it to row value when supported and applicable, or form the logical condition otherwise (for reference, I do this here).

[roji]

@mrahhal thank you for the details and for the perf investigation! I got slightly different-looking query plans in my test (see full details below), but the end result is the same; row values do indeed improve performance in PostgreSQL. This shows once again that it's always worth investigating generating simpler SQL.

Perf investigation

Database setup

CREATE TABLE products
(
    id INT PRIMARY KEY GENERATED BY DEFAULT AS IDENTITY,
    sort1 INT,
    sort2 INT,
    name TEXT
);
CREATE INDEX IX_name ON products(sort1, sort2);

DO $$BEGIN
FOR i IN 1..5000000 LOOP
    INSERT INTO products (sort1, sort2, name) VALUES (i % 10, i % 5, 'Product' || i);
END LOOP;
END$$;

With row value comparison

EXPLAIN SELECT id, name FROM products WHERE (sort1, sort2) > (5, 2);

Resulting plan:

Bitmap Heap Scan on products  (cost=15989.82..73511.39 rows=1384438 width=36)
  Recheck Cond: (ROW(sort1, sort2) > ROW(5, 2))
  ->  Bitmap Index Scan on ix_name  (cost=0.00..15643.72 rows=1384438 width=0)
        Index Cond: (ROW(sort1, sort2) > ROW(5, 2))

Without row value comparison

EXPLAIN SELECT id, name FROM products WHERE sort1 > 5 OR sort1 = 5 AND sort2 > 2;

Resulting plan:

Bitmap Heap Scan on products  (cost=24815.80..99807.51 rows=2108806 width=18)
  Recheck Cond: ((sort1 > 5) OR ((sort1 = 5) AND (sort2 > 2)))
  ->  BitmapOr  (cost=24815.80..24815.80 rows=2184955 width=0)
        ->  Bitmap Index Scan on ix_name  (cost=0.00..21247.50 rows=1994009 width=0)
              Index Cond: (sort1 > 5)
        ->  Bitmap Index Scan on ix_name  (cost=0.00..2513.89 rows=190946 width=0)
              Index Cond: ((sort1 = 5) AND (sort2 > 2))

On the question of how users can express this in C#...

• One way is to use the approach from npgsql/efcore.pg#2111, i.e. require users to write the decomposed, complicated version and pattern-match it into row value comparisons in EF Core.
  • I agree this gets complicated as more keys are added
  • The pattern matching approach indeed requires a specific tree structure. My work in npgsql/efcore.pg#2111 should pick up an arbitrary number of keys and combine them into a single row value comparison, but there may be query shape variations which wouldn't be picked up - I haven't done a full analysis there. Though we'd document the recommend query shape properly, so this may not be a concern.
• The other way is to add a special EF Core API
  • The natural way to represent a row value in C# is value tuples, but unfortunately those have no comparison operators.
  • We can allow users to use arrays to express row values, e.g. ctx.Blogs.Where(b => EF.Functions.GreaterThan(new[] { b.Column1, b.Column2 }, new[] { 1, 2 }). This seems like an easier way to express things than the proposal above which chains Add. If the values are heterogeneous, users would need to specify new object[].
  • We could optionally also provide specialized overloads for some small value tuple sizes, which would be slightly more natural, and also avoid the problem of heterogeneity (e.g. ctx.Blogs.Where(b => EF.Functions.GreaterThan((b.Column1, b.Column2), (1, 2))). Though this may not be worth the effort.
• Since row values are standard across almost all database types (except SQL Server), it makes sense to introduce something into relational; but SQL Server would need a way to opt out of this: EF.Functions.GreaterThan should need to throw an informative message pointing users to the decomposed form instead. We can translate to the more complex expanded form which doesn't use row values.

In any case, I've opened dotnet/EntityFramework.Docs#3582 to track adding docs on good pagination practices.

Thanks again for opening this issue!

[mrahhal]

Here's my own code for the table I created in my perf investigation for completeness.

CREATE TABLE t1 (
  id SERIAL PRIMARY KEY,
  created timestamp with time zone
);

CREATE INDEX IX_created ON t1 (
  created
);

CREATE INDEX IX_created_id ON t1 (
  created,
  id
);

-- Generates about 1.5 million records
INSERT INTO t1 (created)
SELECT g.created FROM generate_series(
  timestamp with time zone '2019-01-01',
  timestamp with time zone '2021-11-17',
  '1 minute'
) AS g (created);

And the particular queries (originally from the ef log when I was testing inside a sample app so forgive the verboseness):

-- Logical condition
SELECT "u"."id", "u"."created"
FROM t1 AS "u"
WHERE ("u"."created" < '2020-11-24 18:51:23.831772') OR (("u"."created" = '2020-11-24 18:51:23.831772') AND ("u"."id" < 21))
ORDER BY "u"."created" DESC, "u"."id" DESC
LIMIT 20

-- Logical condition with an added clause to hint for access predicate
SELECT "u"."id", "u"."created"
FROM t1 AS "u"
WHERE ("u"."created" <= '2020-11-24 18:51:23.831772') AND (("u"."created" < '2020-11-24 18:51:23.831772') OR (("u"."created" = '2020-11-24 18:51:23.831772') AND ("u"."id" < 21)))
ORDER BY "u"."created" DESC, "u"."id" DESC
LIMIT 20

-- Row value
SELECT "u"."id", "u"."created"
FROM t1 AS "u"
WHERE ("u"."created", "u"."id") < ('2020-11-24 18:51:23.831772', 21)
ORDER BY "u"."created" DESC, "u"."id" DESC
LIMIT 20

The other way is to add a special EF Core API

The natural way to represent a row value in C# is value tuples, but unfortunately those have no comparison operators.

Now that you mention this, it would be great having this in C# itself with tuples...

But otherwise, I really like this one you mentioned:

ctx.Blogs.Where(b => EF.Functions.GreaterThan(new[] { b.Column1, b.Column2 }, new[] { 1, 2 })

Better than what I proposed, looks great and very readable. The tuple overload is a good idea too, otherwise maybe always having it new object[] { ... } is better for maintainability (it's an expression so no boxing to worry about).

Since row values are standard across almost all database types (except SQL Server), it makes sense to introduce something into relational; but SQL Server would need a way to opt out of this: EF.Functions.GreaterThan should need to throw an informative message pointing users to the decomposed form instead.

What do you think about EFCore translating it to conditional logic (as I do in my package) in such a case? I think that's a pretty valid alternative for row value (still efficient + supported in all dbs) and would save consumers, especially package authors who want to use this and don't have control over the provider, from having to worry about whether it'll be supported or not. Otherwise, there will need to be some discoverability method to know beforehand whether we can use it and then use an alternative.

And thanks for the doc issue!

[roji]

Better than what I proposed, looks great and very readable. The tuple overload is a good idea too, otherwise maybe always having it new object[] { ... } is better for maintainability (it's an expression so no boxing to worry about).

Yep, there's definitely no efficiency issue here. I do suspect that in 90% of cases, users will have 2, maybe 3 keys at most, so a shorter value tuple construct would be a bit nicer... But definitely not critical.

What do you think about EFCore translating it to conditional logic (as I do in my package) in such a case?

Absolutely. Assuming the team agrees, the thing I have in mind is a general, relational translator which produces a new RowValueExpression, which then gets generated in SQL. SQL Server (and possibly other databases which don't support rowsets) would instead opt into translating to the decomposed conditional logic variant instead. Since it's always possible to translate this and the question is only whether to choose between a more efficient variant and a less efficient one, that should be an internal detail controlled by the provider.

[mrahhal]

Awesome! If possible I'd love to work on this when a design is decided.