Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.98.2) (envelope-from ) id 1xHDkN-00000002t1v-2dJZ for pgsql-bugs@arkaria.postgresql.org; Thu, 15 Oct 2026 05:11:20 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.98.2) (envelope-from ) id 1xHDkM-000000072qc-2QIm for pgsql-bugs@arkaria.postgresql.org; Thu, 15 Oct 2026 05:11:18 +0000 Received: from magus.postgresql.org ([2a02:c0:301:0:ffff::29]) by malur.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.98.2) (envelope-from ) id 1xH2XL-00000004USG-3xj3 for pgsql-bugs@lists.postgresql.org; Wed, 14 Oct 2026 17:13:07 +0000 Received: from mahout.postgresql.org ([2001:4800:3e1:1::227]) by magus.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.98.2) (envelope-from ) id 1xH2XJ-000000026Bx-3MAb for pgsql-bugs@lists.postgresql.org; Wed, 14 Oct 2026 17:13:07 +0000 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=postgresql.org; s=20171124; h=Message-ID:Date:Reply-To:Cc:From:To:Subject: Content-Transfer-Encoding:MIME-Version:Content-Type:Sender:Content-ID: Content-Description:In-Reply-To:References; bh=Tv4By+D9tCg+nL4C3/nT5ctsX0KFpXHuCZ98MAMuk3I=; b=n0sn91soz4EF7EsoSV0QU4ArMi zZJyVry5gOLzzqpfjhVz59NHbSSRQe+4CbBf5I1aZJkzggjr6EuBknowgZOBH+EEFb1VVzbMID98C vDIpA65iTGxjL9XfXjcNx4Qt2Jwh910VFWasuq5cngt4FT9W2p4BboRqxSZablfpgd+sdioaO/CxG dfflQ1LklN32LTedMuGE2rlvJKoy6PaVGaE+NKPW/oZ82hVX2iYCof2s52b4uIAI6q6jFK7EVHFq1 4vjPJpewedf5SP/peytCvUuSjsqS51nYhKgjU2MXJt+M8wHGUeNVVIjrUkujYYSi+ZndXwj8EtBL0 aGs8qG4A==; Received: from wrigleys.postgresql.org ([2a02:16a8:dc51::60]) by mahout.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.98.2) (envelope-from ) id 1xH2XI-00000005sGg-2UND for pgsql-bugs@lists.postgresql.org; Wed, 14 Oct 2026 17:13:04 +0000 Received: from localhost ([127.0.0.1] helo=wrigleys.postgresql.org) by wrigleys.postgresql.org with esmtp (Exim 4.98.2) (envelope-from ) id 1xH2XH-00000000bJF-0Vnf for pgsql-bugs@lists.postgresql.org; Wed, 14 Oct 2026 17:13:03 +0000 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Subject: BUG #19758: Nested BETWEEN grows time and space exponentially in parse analysis To: pgsql-bugs@lists.postgresql.org From: PG Bug reporting form Cc: alpkeles99@gmail.com Reply-To: alpkeles99@gmail.com, pgsql-bugs@lists.postgresql.org Date: Wed, 14 Oct 2026 17:12:07 +0000 Message-ID: <19758-d074798b35cc9215@postgresql.org> X-Auto-Response-Suppress: All Auto-Submitted: auto-generated List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk The following bug has been logged on the website: Bug reference: 19758 Logged by: Alperen Keles Email address: alpkeles99@gmail.com PostgreSQL version: 18.6 Operating system: macOS 26.7, arm64 Description: =20 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=3D"-O2 -g"; default postgresql.conf except fsync=3Doff, empty .psqlr= c): - 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 =3D '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 =3D 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 =3D PARSE ANALYSIS elapsed from log_parser_stats, RSS =3D 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 >=3D b AND a <=3D 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(); =20 + /* 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.