Skip to content

Generate row-value tuple comparison in keyset queries when dialect supports it #4250

Open

Description

@revenant20

Update (2026-05-10): investigation found a simpler smart-OR rewrite that achieves the same Postgres plan without requiring tuple support, on every dialect. See the comment below — the reproduction repo and the proposal can be implemented with that single algebraic rewrite inside KeysetScrollDelegate.createPredicate. The original text is preserved below for context.


Summary

KeysetScrollDelegate.createPredicate always emits keyset condition as a disjunctive
normal form (OR-form), even on databases that natively support row-value tuple
comparison (a, b) < (?, ?). On Postgres this turns what should be a sub-millisecond
Index Cond into a filter scan over millions of rows. I propose detecting the
relevant preconditions and auto-using a tuple shape when they hold, keeping OR-form
as the fallback (Postgres/MySQL/H2 + uniform sort direction + non-null keys is a
common case).

Current behavior

KeysetScrollDelegate.createPredicate (spring-data-jpa
KeysetScrollDelegate.java#L76)
algorithmically builds:

WHERE (a < :ts) OR (a = :ts AND b < :id)

This is implemented through QueryStrategy.compare(Order, expression, value) which
operates on a single column (see KeysetScrollSpecification$JpqlStrategy.compare,
line 155).
A tuple comparison cannot be expressed through this API.

Performance impact (Postgres 17, 2M rows, page ~50 000)

Composite index (status, created_at, id), query: WHERE status = 'PAID' [+ keyset] ORDER BY created_at DESC, id DESC LIMIT 5.

Predicate shape Plan Time Buffers
OR-form (current) Index Cond: status + Filter (Rows Removed by Filter: 999996) 692 ms 1 005 833
(created_at, id) < (?, ?) Index Cond: status AND ROW(...) < ROW(...) 0.27 ms 8

Full EXPLAIN (ANALYZE, BUFFERS) for both shapes is printed by
KeysetSqlShapeTest.explainAnalyze_orForm_vs_rowValue in the reproduction repo
(mvn test runs it).

Two orders of magnitude on a single keyset hop, three on a representative deep page.

The Filter happens because Postgres cannot use the composite index for
(a < ?) OR (a = ? AND b < ?) — it scans matching status rows linearly.
Row-value comparison is a single index range, so it stops at LIMIT. (Postgres can in
theory plan the OR-form via BitmapOr, but does not in this case on tested versions
13–17 because per-branch selectivity estimates remain too high.)

Hibernate already handles HQL tuple comparison: (o.createdAt, o.id) < (:ts, :id)
parses as SqmTuple (HqlParser.g4 TupleExpression and BinaryExpressionPredicate)
and translates to SqlTuple. On dialects where supportsRowValueConstructorGtLtSyntax()
returns true (Postgres/MySQL/H2/CockroachDB/MariaDB), the translator emits the tuple
verbatim; on dialects where it returns false, Hibernate emulates the comparison —
which is the same OR-form rewrite Spring Data is doing now, just one layer up.
Verified by capturing org.hibernate.SQL=DEBUG output of an @Query HQL string.

Why the current shape exists

Three real constraints make OR-form a safe universal default:

  1. Dialect support is mixed. Per Hibernate 7.2.12 the default of
    Dialect.supportsRowValueConstructorGtLtSyntax()
    is true, overridden to false (directly or via supportsRowValueConstructorSyntax)
    in: Oracle, SQL Server, DB2, Sybase, HANA, Spanner, HSQLDB. Asking the dialect
    covers all current and future cases without an explicit list in Spring Data.
  2. Mixed sort directions. Row-value (a, b) < (?, ?) cannot express
    ORDER BY a ASC, b DESC — directions must align. Sort accepts arbitrary mixes,
    so OR-form is the only universal lowering for that shape.
  3. NULL semantics. (NULL, 5) < (1, 10) evaluates to UNKNOWN, which loses rows
    silently. The current JpqlStrategy.compare explicitly handles isNullsLast /
    requiresNonNullTail; equivalent NULL-aware row-value would compose
    (a, b) < (?, ?) OR a IS NULL and partly defeat the optimization.

OR-form is the right universal default. The proposal below is to keep it as a
fallback and use the tuple shape only when all three constraints are statically
known to be safe.

Why not fix it in Hibernate?

A reasonable alternative would be: have Hibernate's SqlAstTranslator recognize
the OR-shape Spring Data emits and rewrite it back to a tuple on dialects that
support GtLt. This does not work — by the time SQL AST sees the predicate it is
just a hand-written disjunction of conditions; the information that "these N
predicates form a keyset tuple" only exists at the Spring Data layer and is lost
in the lowering. The fix has to be made where the intent is still known.

Proposed solution

Auto-detect the three preconditions, no API change. When all of these hold:

  1. Dialect reports supportsRowValueConstructorGtLtSyntax() == true
  2. All Sort.Order entries point in the same direction
  3. All keyset properties are mapped to non-nullable columns (or caller opts in
    declaring NULLs forbidden)

…short-circuit inside KeysetScrollDelegate.createPredicate
to emit a tuple node before the diagonal loop runs. Falls back to the existing
OR-form construction otherwise. The QueryStrategy interface stays the same;
only JpqlStrategy (and its Criteria sibling) gain an internal helper that
produces the tuple expression via JpqlQueryBuilder.

The tuple Predicate composes with arbitrary Specification-built predicates
identically to the OR-form — it's just a different shape produced by the same
strategy — so Specification interop and the existing AOT path are preserved.

If touching JpqlStrategy is undesirable, the alternative is to add the same
logic at the JpqlQueryBuilder level and let it pick the shape based on dialect
metadata available there. Either way no public API changes.

Workaround used today

Custom repository fragment with EntityManager + manual Window.from(items, positionFunction, hasNext) and HQL string with tuple comparison. About 35 lines per
entity. Reference implementation in the reproduction repo.

This is the same shape KeysetScrollDelegate would emit, just bypassed at the
strategy layer.

Related

Reproduction

https://github.com/revenant20/spring-data-keyset-rowvalue-repro — minimal Spring Boot 4.0.6
project. Runs against Testcontainers Postgres. Two test methods capture the SQL emitted
by Spring Data's derived query (Window<T> via findFirst20ByStatus) and by a custom
repository fragment using HQL row-value, asserting the difference. EXPLAIN ANALYZE
output is printed to stdout for both shapes.

mvn test is the full reproduction.

Activity

  1. revenant20 commented on May 10, 2026

    @revenant20
    Author

    Update — simpler alternative without dialect/tuple concerns

    The original issue proposes auto-using (a, b) < (?, ?) row-value tuple comparison
    when the dialect supports it. Investigation shows there is a simpler rewrite that
    matches the same Postgres plan without needing tuple support, so it works on
    every dialect.

    The rewrite (algebraically identical):

    -- what Spring Data emits today (slow):
    WHERE (a < ? OR (a = ? AND b < ?))
    
    -- equivalent, fast on Postgres against composite (a, b) index:
    WHERE a <= ? AND (a < ? OR b < ?)

    Why it works. In the plain form, OR sits at the top level of the predicate —
    Postgres cannot fold either branch into Index Cond, both end up in Filter over the
    full prefix returned by the leading equality (status='PAID' in our test). In the
    rewrite, the leading a <= ? becomes a range condition lifted to the AND level;
    Postgres recognizes it as part of the composite Index Cond and the scan starts
    directly at the cursor position. The remaining inner OR runs on a narrow range.

    EXPLAIN (ANALYZE, BUFFERS) on Postgres 17, 50k rows, page 30k:

    Shape Plan Buffers Time
    OR plain (current Spring) Index Cond: status + Filter (rejects 30001 rows) 269 1.335 ms
    OR smart (rewrite) Index Cond: status AND a <= ? + 1-row Filter 4 0.020 ms
    Row-value (original proposal) Index Cond: status AND ROW(a,b) < ROW(?,?) 4 0.020 ms

    Smart-OR and row-value are indistinguishable in performance — same plan node, same
    buffer count, same execution time.

    Why this changes the proposal. All three constraints listed in the original
    issue weaken or vanish for the smart-OR rewrite:

    1. Dialect support is mixed. Smart-OR uses only <=, <, =, AND, OR —
      standard SQL, works on every dialect Hibernate supports. No
      supportsRowValueConstructorGtLtSyntax check needed.
    2. Mixed sort directions. For ORDER BY a ASC, b DESC the rewrite is
      WHERE a >= :a AND (a > :a OR b < :b) — same shape, works regardless of mix.
    3. NULL semantics. Identical to the original OR-form (both yield UNKNOWN on
      NULL keys), so this is not made worse.

    Practical implication. The change can be made entirely inside
    KeysetScrollDelegate.createPredicate
    — prepend the leading a <= ? (or a >= ? depending on direction) clause before
    the existing diagonal-loop output, on every dialect, with no version gating. The
    existing JpqlStrategy.compare API can stay as-is; only the assembly in
    createPredicate changes.

    Verification. The reproduction repository now exercises all three shapes:
    https://github.com/revenant20/spring-data-keyset-rowvalue-repro

    mvn test runs four tests including
    scaling_orFormGrowsLinearly_rowValueIsConstant, which walks the entire
    status='PAID' subset (175 pages × 200 rows) interleaving all three shapes and
    prints per-page Execution Time and Buffers. Sample output:

    OR plain   pages 1-10 median = 0.095 ms   pages 161-170 median = 1.563 ms   growth = 16.5x
    OR plain   buffers 1-10 max  =     21     buffers 161-170 max  =     304    growth = 14.5x
    OR smart   pages 1-10 median = 0.048 ms   pages 161-170 median = 0.049 ms   growth = 1.0x
    OR smart   buffers 1-10 max  =      6     buffers 161-170 max  =       6    growth = 1.0x
    row-value  pages 1-10 median = 0.051 ms   pages 161-170 median = 0.055 ms   growth = 1.1x
    row-value  buffers 1-10 max  =      6     buffers 161-170 max  =       6    growth = 1.0x
    

    Suggesting we keep the original ticket scope but treat smart-OR as the simpler
    implementation path; row-value can still be considered as a follow-up for cases
    where a single Index Cond expression is preferable.

  2. yeomin4242 commented on May 23, 2026

    @yeomin4242

    @revenant20 @christophstrobl

    I opened PR(#4254) with an implementation that generates the proposed smart-OR keyset predicate shape while preserving the existing null-handling fallback.

    Can you feedback about it?

  3. revenant20 commented on Jun 11, 2026

    @revenant20
    Author

    @yeomin4242 thanks for taking a stab at this — and it would be great to revive your PR. As far as I can tell, #4254 was never actually reviewed: it was opened from your fork's main, which later got reset, so the PR emptied out and was closed without any maintainer feedback. Nobody rejected the approach. The implementation commit is still reachable in this repo's object graph as 0434a56, so it can be resurrected on a dedicated branch and re-submitted.

    I read through the implementation and the overall shape looks right to me: the change is localized to KeysetScrollDelegate.createPredicate exactly as proposed above, all three strategies (Criteria, JPQL, Querydsl) are covered via the new compareInclusive, and the null-leading-key fallback preserves the existing GH-4156 behavior.

    A few weak spots I'd suggest addressing before re-opening, since the current tests only assert the generated query text:

    1. Integration tests on actual scroll results. The inclusive bound on the leading property is exactly the kind of change where an off-by-one would hide behind a correct-looking query string. A test that walks pages over a dataset with duplicate values in the leading sort key and asserts the smart-OR shape returns the exact same row sequence as the current OR shape (no skips, no repeats across page boundaries) would pin the semantics.
    2. Backward scrolling. KeysetScrollDelegate reverses the sort for backward scrolls; there's no test pinning that the inclusive bound flips direction (>= vs <=) together with it.
    3. Nulls-last and mixed directions. compareInclusive adds OR <prop> IS NULL for nulls-last orders — that branch is untested. Same for mixed ASC/DESC sorts, where the rewrite is a >= :a AND (a > :a OR b < :b) per the analysis above.
    4. Default compareInclusive. The interface default builds (a < ? OR a = ?) instead of a native <=. Semantically fine as a fallback for custom strategies, but it re-introduces a top-level-ish OR for anyone who doesn't override it — worth a javadoc note nudging implementors to override with a real <=/>=.

    For (1)–(3) the repro repository from my comment above (https://github.com/revenant20/spring-data-keyset-rowvalue-repro) already walks the full filtered dataset interleaving the predicate shapes and comparing per-page results, buffers and timings — happy to help adapt that into integration tests or to review a re-opened PR.

    @yeomin4242 if you don't have time to pick it back up, I'm also happy to resurrect your commit on a proper branch (keeping your authorship) and re-submit.

  4. yeomin4242 commented on Jun 15, 2026

    @yeomin4242

    @revenant20
    Thanks for the feedback. I’ll take another pass at this, strengthen the missing parts around the keyset predicate handling, and open a new PR once it’s ready.

  5. yeomin4242 commented on Jun 15, 2026

    @yeomin4242

    @revenant20
    I opened #4283 as a follow-up to #4254 from a dedicated branch.

    This version keeps the smart-OR predicate implementation and adds the edge-case coverage suggested above: actual scroll-result integration tests for duplicate leading sort values, backward scrolling, nulls-last with mixed directions, and Querydsl predicate scrolling. While adding the Querydsl coverage, I also fixed the null keyset equality branch to use IS NULL.

    Review would be appreciated when you have time.

  6. added a commit that references this issue on Oct 17, 2026
  7. added a commit that references this issue on Nov 14, 2026
    907872a
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions