From bc1cbe54442757e973cf7d6ee9592a9e5babcb54 Mon Sep 17 00:00:00 2001 From: Satya Narlapuram 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