BUG #19758: Nested BETWEEN grows time and space exponentially in parse analysis

The following bug has been logged on the website:

Bug reference: 19758
Logged by: Alperen Keles
Email address: alpkeles99(at)gmail(dot)com
PostgreSQL version: 18.6
Operating system: macOS 26.7, arm64
Description:

A short query with nested BETWEEN expressions makes parse analysis take
time and memory exponential in the nesting depth, and neither
statement_timeout nor pg_cancel_backend() takes effect until parse
analysis has finished.

This report provides a small proof of concept, a brief analysis on the
exponential growth,
and a minimal potential mitigation that doesn't solve the exponential growth
but allows it
to be cancelled.

Versions tested (both built from git with --enable-cassert --enable-debug,
CFLAGS="-O2 -g"; default postgresql.conf except fsync=off, empty .psqlrc):
- master 158b6d5109f: PostgreSQL 20devel on aarch64-apple-darwin25.6.0,
compiled by Apple clang version 21.0.0 (clang-2100.3.34.2), 64-bit
- REL_18_STABLE a85b5523e67: PostgreSQL 18.6 on
aarch64-apple-darwin25.6.0,
same compiler
Platform: macOS 26.7 (Darwin 25.6.0), Apple M5 Pro (arm64), 64 GB RAM.

Reproduction (no tables needed; 521-byte query, depth 20):

```
\timing on
SET statement_timeout = '100ms';
SELECT 1 WHERE ((((((((((((((((((((true BETWEEN true AND false) BETWEEN
true AND false) BETWEEN true AND false) BETWEEN true AND false) BETWEEN true
AND false) BETWEEN true AND false) BETWEEN true AND false) BETWEEN true AND
false) BETWEEN true AND false) BETWEEN true AND false) BETWEEN true AND
false) BETWEEN true AND false) BETWEEN true AND false) BETWEEN true AND
false) BETWEEN true AND false) BETWEEN true AND false) BETWEEN true AND
false) BETWEEN true AND false) BETWEEN true AND false) BETWEEN true AND
false);
```

Actual:
```
ERROR: canceling statement due to statement timeout
Time: 1642.107 ms (00:01.642) -- master; 1604.506 ms on 18.6
The backend's RSS reaches about 1.65 GB first. With log_parser_stats = on,
PARSE ANALYSIS reports 1.42 s elapsed, i.e. the timeout is acted on only
once parse analysis returns.
```

Expected: the statement is cancelled shortly after 100 ms.

The same happens with pg_cancel_backend() from another session: sent at
0.21 s, the query still ran to 1.63 s (the same as without a cancel) and
then reported "canceling statement due to user request". EXPLAIN and
PREPARE of the same query behave the same (PREPARE at depth 20 with a
100 ms timeout: cancelled after 1732 ms; PARSE ANALYSIS 1.40 s).

Scaling (master; 18.6 is within a few percent). analyze = PARSE ANALYSIS
elapsed from log_parser_stats, RSS = backend peak:

per level: (e BETWEEN true AND false)
depth 14: 0.017 s, 19 MB
depth 16: 0.073 s, 111 MB
depth 18: 0.353 s, 419 MB
depth 20: 1.445 s, 1652 MB (2x per level; 25 bytes per level)
per level: (e BETWEEN SYMMETRIC true AND false)
depth 6: 0.003 s, 16 MB
depth 8: 0.048 s, 93 MB
depth 10: 0.892 s, 1729 MB (4x per level; 371-byte query)
per level: (e NOT BETWEEN true AND false)
depth 18: 0.327 s, 622 MB; depth 20 exceeded 2 GB (I stopped it)

Cause: in src/backend/parser/parse_expr.c, transformAExprBetween()
expands "a BETWEEN b AND c" into "a >= b AND a <= c" by copyObject()ing the
raw left operand and transforming each copy separately (two copies for
[NOT] BETWEEN, four of the left operand plus two of each bound for
[NOT] BETWEEN SYMMETRIC). When the left operand itself contains a
BETWEEN, the work doubles (or quadruples) at each level.
transformExprRecurse() calls
check_stack_depth() but never CHECK_FOR_INTERRUPTS(), and there is no
CHECK_FOR_INTERRUPTS() anywhere in src/backend/parser or
src/backend/nodes, so a pending cancel or timeout waits for the whole
transform.

A minimal mitigation is to let the recursion be cancelled:

```
--- a/src/backend/parser/parse_expr.c
+++ b/src/backend/parser/parse_expr.c
@@ -145,6 +145,9 @@ transformExprRecurse(ParseState *pstate, Node *expr)
/* Guard against stack overflow due to overly complex expressions */
check_stack_depth();

+ /* Also allow complex expressions to be cancelled */
+ CHECK_FOR_INTERRUPTS();
+
switch (nodeTag(expr))
{
case T_ColumnRef:
```

With this on master, the reproduction above is cancelled after 111 ms
(peak RSS 162 MB). A pg_cancel_backend() sent at 0.22 s ends the query at
0.25 s. PREPARE is cancelled at 137 ms. "make check" passes (239 tests).
This does not remove the exponential growth itself; that would need a
BETWEEN representation that does not duplicate its operands.