public inbox for [email protected]
help / color / mirror / Atom feedFrom: SATYANARAYANA NARLAPURAM <[email protected]>
To: PostgreSQL Hackers <[email protected]>
To: Ashutosh Bapat <[email protected]>
Subject: Limit GRAPH_TABLE path combinations to prevent memory exhaustion
Date: Wed, 29 Apr 2026 09:35:44 -0700
Message-ID: <CAHg+QDfDwcM4=DSiAV6Ly89YQ5EcMhzO1-9x=mGG1WJzODcAig@mail.gmail.com> (raw)
Hi hackers,
generate_queries_for_path_pattern_recurse() enumerates all path
combinations by recursing over the Cartesian product of matching elements
per pattern position. Without IS label filters, each position matches
ALL tables of that kind, leading to N^K combinations (N tables, K
pattern positions). Each combination allocates a Query node via palloc
causing unbounded memory growth.
A 8-table graph with a -element pattern reaches 81.3 GB RES in a few seconds
before I cancel the query. Tests in the patch (those were failed) can
reproduce the problem
without the fix included in the patch.
top - 15:04:19 up 43 days, 19:18, 5 users, load average: 0.43, 0.19, 0.08
Tasks: 1 total, 1 running, 0 sleeping, 0 stopped, 0 zombie
%Cpu(s): 0.9 us, 0.8 sy, 0.0 ni, 98.3 id, 0.0 wa, 0.0 hi, 0.0 si,
0.0 st
MiB Mem : 515766.2 total, 248412.7 free, 234847.7 used, 48014.7 buff/cache
MiB Swap: 0.0 total, 0.0 free, 0.0 used. 280918.6 avail Mem
PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+
COMMAND
649642 azureus+ 20 0 212.2g 81.3g 33948 R 100.0 16.1 0:41.20
postgres
As a POC I added a pre-computation check that calculates the total number
of path combinations before entering the
generate_queries_for_path_pattern_recurse.
If the product exceeds MAX_GRAPH_TABLE_PATH_COMBINATIONS (set to 10,000),
the rewriter reports ERRCODE_PROGRAM_LIMIT_EXCEEDED with a hint suggesting
IS label filters to reduce the search space. The limit of 10,000 is
somewhat arbitrary
but conservative. It caps memory at roughly 5 MB of Query nodes.
Patterns that would exceed the limit without labels can always be made to
succeed
by adding IS expressions to pin specific positions to fewer tables.
Alternatively, we can consider adding a GUC to control the limit but appears
to be an overkill. Thoughts?
Thanks,
Satya
Attachments:
[application/octet-stream] 0001-Limit-GRAPH_TABLE-path-combinations-to-prevent-memor.patch (10.8K, 3-0001-Limit-GRAPH_TABLE-path-combinations-to-prevent-memor.patch)
download | inline diff:
From bc1cbe54442757e973cf7d6ee9592a9e5babcb54 Mon Sep 17 00:00:00 2001
From: Satya Narlapuram <[email protected]>
Date: Wed, 29 Apr 2026 16:22:42 +0000
Subject: [PATCH] Limit GRAPH_TABLE path combinations to prevent memory
exhaustion
generate_queries_for_path_pattern_recurse() enumerates all path
combinations by recursing over the Cartesian product of matching elements
per pattern position. Without IS label filters, each position matches
ALL tables of that kind, leading to N^K combinations (N tables, K
pattern positions). Each combination allocates a Query node via palloc
into process memory with no limit, causing rapid memory exhaustion and
potential OOM kills.
Add a pre-computation check that calculates the total number of path
combinations before calling
generate_queries_for_path_pattern_recurse(). If the product exceeds
MAX_GRAPH_TABLE_PATH_COMBINATIONS (10000), report an error with a hint
suggesting IS label filters to reduce the search space.
This provides protection against memory exhaustion while
preserving correct behavior for reasonable graph patterns.
---
src/backend/rewrite/rewriteGraphTable.c | 25 ++++++++
src/test/regress/expected/graph_table.out | 70 +++++++++++++++++++++++
src/test/regress/sql/graph_table.sql | 64 +++++++++++++++++++++
3 files changed, 159 insertions(+)
diff --git a/src/backend/rewrite/rewriteGraphTable.c b/src/backend/rewrite/rewriteGraphTable.c
index 6867de6d..8a866e0c 100644
--- a/src/backend/rewrite/rewriteGraphTable.c
+++ b/src/backend/rewrite/rewriteGraphTable.c
@@ -45,6 +45,9 @@
#include "utils/ruleutils.h"
#include "utils/syscache.h"
+/* Limit on total path combinations to prevent combinatorial explosion. */
+#define MAX_GRAPH_TABLE_PATH_COMBINATIONS 10000
+
/*
* Represents one path factor in a path.
@@ -343,6 +346,28 @@ generate_queries_for_path_pattern(RangeTblEntry *rte, List *path_pattern)
path_elem_lists = lappend(path_elem_lists,
get_path_elements_for_path_factor(rte->relid, pf));
+ /*
+ * Check that the total number of path combinations doesn't exceed a
+ * reasonable limit. Without explicit IS label expressions, each element
+ * pattern matches all graph elements of the same kind, producing a
+ * Cartesian product that can easily exhaust process memory.
+ */
+ {
+ int64 total_paths = 1;
+
+ foreach_ptr(List, elems, path_elem_lists)
+ {
+ if (list_length(elems) > 0)
+ total_paths *= list_length(elems);
+ if (total_paths > MAX_GRAPH_TABLE_PATH_COMBINATIONS)
+ ereport(ERROR,
+ (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
+ errmsg("too many path combinations (%lld) in GRAPH_TABLE pattern",
+ (long long) total_paths),
+ errhint("Use explicit IS label expressions to reduce the number of matching elements.")));
+ }
+ }
+
pathqueries = generate_queries_for_path_pattern_recurse(rte, pathqueries,
NIL, path_elem_lists, 0);
if (!pathqueries)
diff --git a/src/test/regress/expected/graph_table.out b/src/test/regress/expected/graph_table.out
index 12b8706b..56fa1b5f 100644
--- a/src/test/regress/expected/graph_table.out
+++ b/src/test/regress/expected/graph_table.out
@@ -1032,4 +1032,74 @@ SELECT sname, dname FROM GRAPH_TABLE (g1 MATCH (src)->(dest) WHERE src.vprop1 >
ERROR: subqueries within GRAPH_TABLE reference are not supported
SELECT sname, dname FROM GRAPH_TABLE (g1 MATCH (src)->(dest) WHERE out_degree(src.vname) > (SELECT max(out_degree(nname)) FROM GRAPH_TABLE (g1 MATCH (node) COLUMNS (node.vname AS nname))) COLUMNS(src.vname AS sname, dest.vname AS dname));
ERROR: subqueries within GRAPH_TABLE reference are not supported
+-- Test: path combination limit prevents combinatorial explosion in the
+-- rewriter when MATCH patterns lack explicit IS label expressions.
+CREATE TABLE v4 (id int PRIMARY KEY, val int);
+CREATE TABLE v5 (id int PRIMARY KEY, val int);
+CREATE TABLE v6 (id int PRIMARY KEY, val int);
+CREATE TABLE v7 (id int PRIMARY KEY, val int);
+CREATE TABLE v8 (id int PRIMARY KEY, val int);
+CREATE TABLE v9 (id int PRIMARY KEY, val int);
+CREATE TABLE v10 (id int PRIMARY KEY, val int);
+CREATE TABLE v11 (id int PRIMARY KEY, val int);
+CREATE TABLE e1 (id int PRIMARY KEY, src int, dest int);
+CREATE TABLE e2 (id int PRIMARY KEY, src int, dest int);
+CREATE TABLE e3 (id int PRIMARY KEY, src int, dest int);
+CREATE TABLE e4 (id int PRIMARY KEY, src int, dest int);
+CREATE TABLE e5 (id int PRIMARY KEY, src int, dest int);
+CREATE TABLE e6 (id int PRIMARY KEY, src int, dest int);
+CREATE TABLE e7 (id int PRIMARY KEY, src int, dest int);
+CREATE TABLE e8 (id int PRIMARY KEY, src int, dest int);
+INSERT INTO v4 VALUES (1, 10);
+INSERT INTO e1 VALUES (1, 1, 1);
+CREATE PROPERTY GRAPH g5
+ VERTEX TABLES (
+ v4 LABEL vl PROPERTIES (id, val) LABEL vl2 PROPERTIES (id, val),
+ v5 LABEL vl PROPERTIES (id, val),
+ v6 LABEL vl PROPERTIES (id, val),
+ v7 LABEL vl PROPERTIES (id, val),
+ v8 LABEL vl PROPERTIES (id, val),
+ v9 LABEL vl PROPERTIES (id, val),
+ v10 LABEL vl PROPERTIES (id, val),
+ v11 LABEL vl PROPERTIES (id, val)
+ )
+ EDGE TABLES (
+ e1 SOURCE KEY (src) REFERENCES v4 (id) DESTINATION KEY (dest) REFERENCES v5 (id)
+ LABEL el PROPERTIES (id),
+ e2 SOURCE KEY (src) REFERENCES v5 (id) DESTINATION KEY (dest) REFERENCES v6 (id)
+ LABEL el PROPERTIES (id),
+ e3 SOURCE KEY (src) REFERENCES v6 (id) DESTINATION KEY (dest) REFERENCES v7 (id)
+ LABEL el PROPERTIES (id),
+ e4 SOURCE KEY (src) REFERENCES v7 (id) DESTINATION KEY (dest) REFERENCES v8 (id)
+ LABEL el PROPERTIES (id),
+ e5 SOURCE KEY (src) REFERENCES v8 (id) DESTINATION KEY (dest) REFERENCES v9 (id)
+ LABEL el PROPERTIES (id),
+ e6 SOURCE KEY (src) REFERENCES v9 (id) DESTINATION KEY (dest) REFERENCES v10 (id)
+ LABEL el PROPERTIES (id),
+ e7 SOURCE KEY (src) REFERENCES v10 (id) DESTINATION KEY (dest) REFERENCES v11 (id)
+ LABEL el PROPERTIES (id),
+ e8 SOURCE KEY (src) REFERENCES v11 (id) DESTINATION KEY (dest) REFERENCES v4 (id)
+ LABEL el PROPERTIES (id)
+ );
+-- 3-element unlabeled: 8 * 8 * 8 = 512 combinations (under limit, succeeds)
+SELECT count(*) FROM GRAPH_TABLE (g5 MATCH (a)-[e]->(b) COLUMNS (a.id AS aid));
+ count
+-------
+ 0
+(1 row)
+
+-- 5-element unlabeled: 8^5 = 32,768 combinations (over limit, rejected)
+SELECT count(*) FROM GRAPH_TABLE (g5 MATCH (a)-[e1]->(b)-[e2]->(c) COLUMNS (a.id AS aid));
+ERROR: too many path combinations (32768) in GRAPH_TABLE pattern
+HINT: Use explicit IS label expressions to reduce the number of matching elements.
+-- IS vl2 pins first vertex to 1 table: 1*8*8*8*8 = 4,096 (under limit)
+SELECT count(*) FROM GRAPH_TABLE (g5 MATCH (a IS vl2)-[e1]->(b)-[e2]->(c) COLUMNS (a.id AS aid));
+ count
+-------
+ 0
+(1 row)
+
+DROP PROPERTY GRAPH g5;
+DROP TABLE e8, e7, e6, e5, e4, e3, e2, e1;
+DROP TABLE v11, v10, v9, v8, v7, v6, v5, v4;
-- leave the objects behind for pg_upgrade/pg_dump tests
diff --git a/src/test/regress/sql/graph_table.sql b/src/test/regress/sql/graph_table.sql
index a5df4647..69313544 100644
--- a/src/test/regress/sql/graph_table.sql
+++ b/src/test/regress/sql/graph_table.sql
@@ -590,4 +590,68 @@ SELECT * FROM customers co WHERE co.customer_id = (SELECT customer_id FROM GRAPH
SELECT sname, dname FROM GRAPH_TABLE (g1 MATCH (src)->(dest) WHERE src.vprop1 > (SELECT max(v1.vprop1) FROM v1) COLUMNS(src.vname AS sname, dest.vname AS dname));
SELECT sname, dname FROM GRAPH_TABLE (g1 MATCH (src)->(dest) WHERE out_degree(src.vname) > (SELECT max(out_degree(nname)) FROM GRAPH_TABLE (g1 MATCH (node) COLUMNS (node.vname AS nname))) COLUMNS(src.vname AS sname, dest.vname AS dname));
+-- Test: path combination limit prevents combinatorial explosion in the
+-- rewriter when MATCH patterns lack explicit IS label expressions.
+CREATE TABLE v4 (id int PRIMARY KEY, val int);
+CREATE TABLE v5 (id int PRIMARY KEY, val int);
+CREATE TABLE v6 (id int PRIMARY KEY, val int);
+CREATE TABLE v7 (id int PRIMARY KEY, val int);
+CREATE TABLE v8 (id int PRIMARY KEY, val int);
+CREATE TABLE v9 (id int PRIMARY KEY, val int);
+CREATE TABLE v10 (id int PRIMARY KEY, val int);
+CREATE TABLE v11 (id int PRIMARY KEY, val int);
+CREATE TABLE e1 (id int PRIMARY KEY, src int, dest int);
+CREATE TABLE e2 (id int PRIMARY KEY, src int, dest int);
+CREATE TABLE e3 (id int PRIMARY KEY, src int, dest int);
+CREATE TABLE e4 (id int PRIMARY KEY, src int, dest int);
+CREATE TABLE e5 (id int PRIMARY KEY, src int, dest int);
+CREATE TABLE e6 (id int PRIMARY KEY, src int, dest int);
+CREATE TABLE e7 (id int PRIMARY KEY, src int, dest int);
+CREATE TABLE e8 (id int PRIMARY KEY, src int, dest int);
+INSERT INTO v4 VALUES (1, 10);
+INSERT INTO e1 VALUES (1, 1, 1);
+
+CREATE PROPERTY GRAPH g5
+ VERTEX TABLES (
+ v4 LABEL vl PROPERTIES (id, val) LABEL vl2 PROPERTIES (id, val),
+ v5 LABEL vl PROPERTIES (id, val),
+ v6 LABEL vl PROPERTIES (id, val),
+ v7 LABEL vl PROPERTIES (id, val),
+ v8 LABEL vl PROPERTIES (id, val),
+ v9 LABEL vl PROPERTIES (id, val),
+ v10 LABEL vl PROPERTIES (id, val),
+ v11 LABEL vl PROPERTIES (id, val)
+ )
+ EDGE TABLES (
+ e1 SOURCE KEY (src) REFERENCES v4 (id) DESTINATION KEY (dest) REFERENCES v5 (id)
+ LABEL el PROPERTIES (id),
+ e2 SOURCE KEY (src) REFERENCES v5 (id) DESTINATION KEY (dest) REFERENCES v6 (id)
+ LABEL el PROPERTIES (id),
+ e3 SOURCE KEY (src) REFERENCES v6 (id) DESTINATION KEY (dest) REFERENCES v7 (id)
+ LABEL el PROPERTIES (id),
+ e4 SOURCE KEY (src) REFERENCES v7 (id) DESTINATION KEY (dest) REFERENCES v8 (id)
+ LABEL el PROPERTIES (id),
+ e5 SOURCE KEY (src) REFERENCES v8 (id) DESTINATION KEY (dest) REFERENCES v9 (id)
+ LABEL el PROPERTIES (id),
+ e6 SOURCE KEY (src) REFERENCES v9 (id) DESTINATION KEY (dest) REFERENCES v10 (id)
+ LABEL el PROPERTIES (id),
+ e7 SOURCE KEY (src) REFERENCES v10 (id) DESTINATION KEY (dest) REFERENCES v11 (id)
+ LABEL el PROPERTIES (id),
+ e8 SOURCE KEY (src) REFERENCES v11 (id) DESTINATION KEY (dest) REFERENCES v4 (id)
+ LABEL el PROPERTIES (id)
+ );
+
+-- 3-element unlabeled: 8 * 8 * 8 = 512 combinations (under limit, succeeds)
+SELECT count(*) FROM GRAPH_TABLE (g5 MATCH (a)-[e]->(b) COLUMNS (a.id AS aid));
+
+-- 5-element unlabeled: 8^5 = 32,768 combinations (over limit, rejected)
+SELECT count(*) FROM GRAPH_TABLE (g5 MATCH (a)-[e1]->(b)-[e2]->(c) COLUMNS (a.id AS aid));
+
+-- IS vl2 pins first vertex to 1 table: 1*8*8*8*8 = 4,096 (under limit)
+SELECT count(*) FROM GRAPH_TABLE (g5 MATCH (a IS vl2)-[e1]->(b)-[e2]->(c) COLUMNS (a.id AS aid));
+
+DROP PROPERTY GRAPH g5;
+DROP TABLE e8, e7, e6, e5, e4, e3, e2, e1;
+DROP TABLE v11, v10, v9, v8, v7, v6, v5, v4;
+
-- leave the objects behind for pg_upgrade/pg_dump tests
--
2.43.0
view thread (3+ messages) latest in thread
reply
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: [email protected]
Cc: [email protected], [email protected], [email protected]
Subject: Re: Limit GRAPH_TABLE path combinations to prevent memory exhaustion
In-Reply-To: <CAHg+QDfDwcM4=DSiAV6Ly89YQ5EcMhzO1-9x=mGG1WJzODcAig@mail.gmail.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox