nocfbot-0036-Avoid-INF-valued-quantifier-bound-in-RPR-consecut.txt
text/plain
Filename: nocfbot-0036-Avoid-INF-valued-quantifier-bound-in-RPR-consecut.txt
Type: text/plain
Part: 35
Message:
Re: Row pattern recognition
From 337bec7e5251ec89fac6636e53046b60a79d3908 Mon Sep 17 00:00:00 2001
From: Henson Choi <assam258@gmail.com>
Date: Mon, 1 Jun 2026 17:03:04 +0900
Subject: [PATCH 36/38] Avoid INF-valued quantifier bound in RPR
consecutive-merge optimization
mergeConsecutiveVars() and mergeConsecutiveGroups() accumulate the min and
max bounds of two adjacent pattern elements, guarding against overflow with
prev->min <= RPR_QUANTITY_INF - child->min (and likewise for max). The <=
let a sum land exactly on RPR_QUANTITY_INF (INT32_MAX), the value reserved as
the sentinel for an unbounded max. The merged element then carried
min == INF, which is not a valid finite lower bound: it tripped the Assert in
fillRPRPattern* at plan time, and in a non-assert build silently produced a
pattern that can never match.
Tighten both guards to a strict <, so a sum reaching INF falls back and
leaves the elements unmerged. This matches the >= INF check already used by
the quantifier-multiply path and the strict bound in mergeGroupPrefixSuffix.
Per a report from a static analysis tool.
---
src/backend/optimizer/plan/rpr.c | 22 ++++---
src/test/regress/expected/rpr_base.out | 83 ++++++++++++++++++++++++++
src/test/regress/sql/rpr_base.sql | 43 +++++++++++++
3 files changed, 140 insertions(+), 8 deletions(-)
diff --git a/src/backend/optimizer/plan/rpr.c b/src/backend/optimizer/plan/rpr.c
index 2a98977b288..b989fcc5162 100644
--- a/src/backend/optimizer/plan/rpr.c
+++ b/src/backend/optimizer/plan/rpr.c
@@ -245,13 +245,16 @@ mergeConsecutiveVars(List *children)
/* ----------------------
* Can merge consecutive VAR nodes if:
* 1. Same variable name
- * 2. No min overflow: prev->min + child->min <= INF
- * 3. No max overflow: prev->max + child->max <= INF (or either is INF)
+ * 2. No min overflow: prev->min + child->min < INF
+ * 3. No max overflow: prev->max + child->max < INF (or either is INF)
+ *
+ * Strict <: a sum equal to INF would alias the unbounded sentinel
+ * (min must stay finite; a finite max must not become INF).
*/
if (prev != NULL &&
strcmp(prev->varName, child->varName) == 0 &&
- prev->min <= RPR_QUANTITY_INF - child->min &&
- (prev->max <= RPR_QUANTITY_INF - child->max ||
+ prev->min < RPR_QUANTITY_INF - child->min &&
+ (prev->max < RPR_QUANTITY_INF - child->max ||
prev->max == RPR_QUANTITY_INF ||
child->max == RPR_QUANTITY_INF))
{
@@ -319,13 +322,16 @@ mergeConsecutiveGroups(List *children)
/* ----------------------
* Can merge consecutive GROUP nodes if:
* 1. Identical children
- * 2. No min overflow: prev->min + child->min <= INF
- * 3. No max overflow: prev->max + child->max <= INF (or either is INF)
+ * 2. No min overflow: prev->min + child->min < INF
+ * 3. No max overflow: prev->max + child->max < INF (or either is INF)
+ *
+ * Strict <: a sum equal to INF would alias the unbounded sentinel
+ * (min must stay finite; a finite max must not become INF).
*/
if (prev != NULL &&
rprPatternChildrenEqual(prev->children, child->children) &&
- prev->min <= RPR_QUANTITY_INF - child->min &&
- (prev->max <= RPR_QUANTITY_INF - child->max ||
+ prev->min < RPR_QUANTITY_INF - child->min &&
+ (prev->max < RPR_QUANTITY_INF - child->max ||
prev->max == RPR_QUANTITY_INF ||
child->max == RPR_QUANTITY_INF))
{
diff --git a/src/test/regress/expected/rpr_base.out b/src/test/regress/expected/rpr_base.out
index c96a1216cc3..ebc1088018a 100644
--- a/src/test/regress/expected/rpr_base.out
+++ b/src/test/regress/expected/rpr_base.out
@@ -3459,6 +3459,25 @@ WINDOW w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
-> Seq Scan on rpr_plan
(7 rows)
+-- Consecutive VAR merge at the boundary: A{1073741823,} A{1073741823,} ->
+-- a{2147483646,}. The min sum 2147483646 = INT32_MAX - 1 is the largest
+-- still-finite bound, so the merge proceeds; a sum of exactly INF instead
+-- falls back (see the Optimization Fallback Tests).
+EXPLAIN (COSTS OFF)
+SELECT COUNT(*) OVER w FROM rpr_plan
+WINDOW w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
+ PATTERN (A{1073741823,} A{1073741823,}) DEFINE A AS val > 0);
+ QUERY PLAN
+-------------------------------------------------------------------------------
+ WindowAgg
+ Window: w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING)
+ Pattern: a{2147483646,}"
+ Nav Mark Lookback: 0
+ -> Sort
+ Sort Key: id
+ -> Seq Scan on rpr_plan
+(7 rows)
+
-- Consecutive GROUP merge with finite quantifiers: ((A B){5}) ((A B){10}) -> merged
EXPLAIN (COSTS OFF)
SELECT COUNT(*) OVER w FROM rpr_plan
@@ -3509,6 +3528,25 @@ WINDOW w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
-> Seq Scan on rpr_plan
(7 rows)
+-- Consecutive GROUP merge at the boundary: (A B){1073741823,} (A B){1073741823,}
+-- -> (a b){2147483646,}. The min sum INT32_MAX - 1 is still finite, so the
+-- merge proceeds; a sum of exactly INF instead falls back (see the
+-- Optimization Fallback Tests).
+EXPLAIN (COSTS OFF)
+SELECT COUNT(*) OVER w FROM rpr_plan
+WINDOW w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
+ PATTERN ((A B){1073741823,} (A B){1073741823,}) DEFINE A AS val <= 50, B AS val > 50);
+ QUERY PLAN
+-------------------------------------------------------------------------------
+ WindowAgg
+ Window: w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING)
+ Pattern: (a' b'){2147483646,}"
+ Nav Mark Lookback: 0
+ -> Sort
+ Sort Key: id
+ -> Seq Scan on rpr_plan
+(7 rows)
+
-- PREFIX merge: A B (A B)+ -> (a b){2,}
EXPLAIN (COSTS OFF)
SELECT COUNT(*) OVER w FROM rpr_plan
@@ -5269,6 +5307,51 @@ WINDOW w AS (
(7 rows)
-- Expected: Fallback - prefix elements don't match GROUP content
+-- Test: consecutive VAR merge whose min sum is exactly INF causes fallback.
+-- 1073741824 + 1073741823 = 2147483647 = INT32_MAX = RPR_QUANTITY_INF.
+-- Merging would yield a VAR with min == INF, so the merge must fall back and
+-- leave the two VARs unmerged (mirrors the multiply path's >= INF guard).
+EXPLAIN (COSTS OFF)
+SELECT COUNT(*) OVER w FROM rpr_fallback
+WINDOW w AS (
+ ORDER BY id
+ ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
+ PATTERN (A{1073741824,} A{1073741823,})
+ DEFINE A AS val > 0
+);
+ QUERY PLAN
+-------------------------------------------------------------------------------
+ WindowAgg
+ Window: w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING)
+ Pattern: a{1073741824,}" a{1073741823,}
+ Nav Mark Lookback: 0
+ -> Sort
+ Sort Key: id
+ -> Seq Scan on rpr_fallback
+(7 rows)
+
+-- Expected: Fallback - VARs not merged (min sum 2147483647 == INF)
+-- Test: consecutive GROUP merge whose min sum is exactly INF causes fallback.
+EXPLAIN (COSTS OFF)
+SELECT COUNT(*) OVER w FROM rpr_fallback
+WINDOW w AS (
+ ORDER BY id
+ ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
+ PATTERN ((A B){1073741824,} (A B){1073741823,})
+ DEFINE A AS val > 0, B AS val > 5
+);
+ QUERY PLAN
+-------------------------------------------------------------------------------
+ WindowAgg
+ Window: w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING)
+ Pattern: (a' b'){1073741824,}" (a b){1073741823,}
+ Nav Mark Lookback: 0
+ -> Sort
+ Sort Key: id
+ -> Seq Scan on rpr_fallback
+(7 rows)
+
+-- Expected: Fallback - GROUPs not merged (min sum 2147483647 == INF)
DROP TABLE rpr_fallback;
-- ============================================================
-- Planner Integration Tests
diff --git a/src/test/regress/sql/rpr_base.sql b/src/test/regress/sql/rpr_base.sql
index d7b63cfc690..63173615273 100644
--- a/src/test/regress/sql/rpr_base.sql
+++ b/src/test/regress/sql/rpr_base.sql
@@ -2386,6 +2386,15 @@ SELECT COUNT(*) OVER w FROM rpr_plan
WINDOW w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
PATTERN (A A+) DEFINE A AS val > 0);
+-- Consecutive VAR merge at the boundary: A{1073741823,} A{1073741823,} ->
+-- a{2147483646,}. The min sum 2147483646 = INT32_MAX - 1 is the largest
+-- still-finite bound, so the merge proceeds; a sum of exactly INF instead
+-- falls back (see the Optimization Fallback Tests).
+EXPLAIN (COSTS OFF)
+SELECT COUNT(*) OVER w FROM rpr_plan
+WINDOW w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
+ PATTERN (A{1073741823,} A{1073741823,}) DEFINE A AS val > 0);
+
-- Consecutive GROUP merge with finite quantifiers: ((A B){5}) ((A B){10}) -> merged
EXPLAIN (COSTS OFF)
SELECT COUNT(*) OVER w FROM rpr_plan
@@ -2406,6 +2415,15 @@ SELECT COUNT(*) OVER w FROM rpr_plan
WINDOW w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
PATTERN ((A B){2} (A B)+) DEFINE A AS val <= 50, B AS val > 50);
+-- Consecutive GROUP merge at the boundary: (A B){1073741823,} (A B){1073741823,}
+-- -> (a b){2147483646,}. The min sum INT32_MAX - 1 is still finite, so the
+-- merge proceeds; a sum of exactly INF instead falls back (see the
+-- Optimization Fallback Tests).
+EXPLAIN (COSTS OFF)
+SELECT COUNT(*) OVER w FROM rpr_plan
+WINDOW w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
+ PATTERN ((A B){1073741823,} (A B){1073741823,}) DEFINE A AS val <= 50, B AS val > 50);
+
-- PREFIX merge: A B (A B)+ -> (a b){2,}
EXPLAIN (COSTS OFF)
SELECT COUNT(*) OVER w FROM rpr_plan
@@ -3213,6 +3231,31 @@ WINDOW w AS (
);
-- Expected: Fallback - prefix elements don't match GROUP content
+-- Test: consecutive VAR merge whose min sum is exactly INF causes fallback.
+-- 1073741824 + 1073741823 = 2147483647 = INT32_MAX = RPR_QUANTITY_INF.
+-- Merging would yield a VAR with min == INF, so the merge must fall back and
+-- leave the two VARs unmerged (mirrors the multiply path's >= INF guard).
+EXPLAIN (COSTS OFF)
+SELECT COUNT(*) OVER w FROM rpr_fallback
+WINDOW w AS (
+ ORDER BY id
+ ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
+ PATTERN (A{1073741824,} A{1073741823,})
+ DEFINE A AS val > 0
+);
+-- Expected: Fallback - VARs not merged (min sum 2147483647 == INF)
+
+-- Test: consecutive GROUP merge whose min sum is exactly INF causes fallback.
+EXPLAIN (COSTS OFF)
+SELECT COUNT(*) OVER w FROM rpr_fallback
+WINDOW w AS (
+ ORDER BY id
+ ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
+ PATTERN ((A B){1073741824,} (A B){1073741823,})
+ DEFINE A AS val > 0, B AS val > 5
+);
+-- Expected: Fallback - GROUPs not merged (min sum 2147483647 == INF)
+
DROP TABLE rpr_fallback;
-- ============================================================
--
2.50.1 (Apple Git-155)