Repository navigation
Description
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:
- Dialect support is mixed. Per Hibernate 7.2.12 the default of
Dialect.supportsRowValueConstructorGtLtSyntax()
istrue, overridden tofalse(directly or viasupportsRowValueConstructorSyntax)
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. - Mixed sort directions. Row-value
(a, b) < (?, ?)cannot express
ORDER BY a ASC, b DESC— directions must align.Sortaccepts arbitrary mixes,
so OR-form is the only universal lowering for that shape. - NULL semantics.
(NULL, 5) < (1, 10)evaluates to UNKNOWN, which loses rows
silently. The currentJpqlStrategy.compareexplicitly handlesisNullsLast/
requiresNonNullTail; equivalent NULL-aware row-value would compose
(a, b) < (?, ?) OR a IS NULLand 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:
- Dialect reports
supportsRowValueConstructorGtLtSyntax() == true - All
Sort.Orderentries point in the same direction - 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
- Investigate keyset-scrolling using HQL/JPQL query methods #2886 — keyset-scrolling using HQL/JPQL query methods. Distinct from this ticket:
Investigate keyset-scrolling using HQL/JPQL query methods #2886 proposes new public surface (Window<T>return type for@Querymethods,
requiring HQL parsing changes for keyset semantics). This ticket proposes no API
change — only an internal predicate optimization in the existing derived-query /
Specificationspath. They are independent and could land in either order. - Replace derived
CriteriaQuerywith String-based JPQL queries #3588 — CriteriaQuery → JPQL string migration (closed). Showed a 3× throughput
improvement from string-based JPQL over CriteriaBuilder; relevant context that
predicate-shape choices are worth investing in. - KeysetScrollSpecification null properties support #3605 — keyset NULL property support. Orthogonal: KeysetScrollSpecification null properties support #3605 fixes correctness in
OR-form for nullable columns; this issue proposes a shape change for the non-null
case. Both can land independently. If KeysetScrollSpecification null properties support #3605 lands first, the precondition check
here gets simpler.
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
revenant20 commentedon May 10, 2026
Update — simpler alternative without dialect/tuple concerns
The original issue proposes auto-using
(a, b) < (?, ?)row-value tuple comparisonwhen 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):
Why it works. In the plain form,
ORsits at the top level of the predicate —Postgres cannot fold either branch into Index Cond, both end up in
Filterover thefull prefix returned by the leading equality (
status='PAID'in our test). In therewrite, 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:
Index Cond: status+Filter(rejects 30001 rows)Index Cond: status AND a <= ?+ 1-row FilterIndex Cond: status AND ROW(a,b) < ROW(?,?)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:
Dialect support is mixed.Smart-OR uses only<=,<,=,AND,OR—standard SQL, works on every dialect Hibernate supports. No
supportsRowValueConstructorGtLtSyntaxcheck needed.Mixed sort directions.ForORDER BY a ASC, b DESCthe rewrite isWHERE a >= :a AND (a > :a OR b < :b)— same shape, works regardless of mix.NULL keys), so this is not made worse.
Practical implication. The change can be made entirely inside
KeysetScrollDelegate.createPredicate— prepend the leading
a <= ?(ora >= ?depending on direction) clause beforethe existing diagonal-loop output, on every dialect, with no version gating. The
existing
JpqlStrategy.compareAPI can stay as-is; only the assembly increatePredicatechanges.Verification. The reproduction repository now exercises all three shapes:
https://github.com/revenant20/spring-data-keyset-rowvalue-repro
mvn testruns four tests includingscaling_orFormGrowsLinearly_rowValueIsConstant, which walks the entirestatus='PAID'subset (175 pages × 200 rows) interleaving all three shapes andprints per-page Execution Time and Buffers. Sample output:
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.
yeomin4242 commentedon May 23, 2026
@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?
revenant20 commentedon Jun 11, 2026
@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.createPredicateexactly as proposed above, all three strategies (Criteria, JPQL, Querydsl) are covered via the newcompareInclusive, 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:
KeysetScrollDelegatereverses the sort for backward scrolls; there's no test pinning that the inclusive bound flips direction (>=vs<=) together with it.compareInclusiveaddsOR <prop> IS NULLfor nulls-last orders — that branch is untested. Same for mixedASC/DESCsorts, where the rewrite isa >= :a AND (a > :a OR b < :b)per the analysis above.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.
yeomin4242 commentedon Jun 15, 2026
@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.
yeomin4242 commentedon Jun 15, 2026
@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.
Merge remote-tracking branch 'upstream/main' into spring-projectsgh-4250
Merge branch 'main' into spring-projectsgh-4250-keyset-smart-or-predi…
Generate smart-OR predicates for keyset scrolling.