Horton
Menu

0001-Limit-GRAPH_TABLE-path-combinations-to-prevent-memor.patch

application/octet-stream

Download
Filename: 0001-Limit-GRAPH_TABLE-path-combinations-to-prevent-memor.patch
Type: application/octet-stream
Part: 0
Message: Limit GRAPH_TABLE path combinations to prevent memory exhaustion

Patch

Same data as JSON: GET /api/v1/attachments/:id/patch the parsed metadata as JSON — format, series position, per-file stats; never the diff bytes. API reference →
Format: format-patch
Series: patch 0001
Subject: Limit GRAPH_TABLE path combinations to prevent memory exhaustion
File+−
src/backend/rewrite/rewriteGraphTable.c 25 0
src/test/regress/expected/graph_table.out 70 0
src/test/regress/sql/graph_table.sql 64 0 
From bc1cbe54442757e973cf7d6ee9592a9e5babcb54 Mon Sep 17 00:00:00 2001
From: Satya Narlapuram <satyanarlapuram@gmail.com>
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