Skip to content

Commit 3fd3543

Browse files
committed
fix(cypher): resolve full-graph OPTIONAL MATCH OOM and segmentation fault
Refactor cross_join_with_rels and cross_join_nodes to utilize dynamic array reallocations instead of massive upfront quadratic allocations. This resolves a 269GB memory footprint issue down to ~19MB on large graphs, preventing malloc failures and null-pointer dereferences. Added relationship-expansion node ID matching and optional match regression tests. Signed-off-by: Zbyněk Winkler <[email protected]>
1 parent a99a419 commit 3fd3543

2 files changed

Lines changed: 128 additions & 7 deletions

File tree

‎src/cypher/cypher.c‎

Lines changed: 76 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -2855,6 +2855,11 @@ static void process_edges(cbm_store_t *store, cbm_edge_t *edges, int edge_count,
28552855
node_fields_free(&found);
28562856
continue;
28572857
}
2858+
cbm_node_t *existing = binding_get(b, to_var);
2859+
if (existing && existing->id != found.id) {
2860+
node_fields_free(&found);
2861+
continue;
2862+
}
28582863
binding_t nb = {0};
28592864
binding_copy(&nb, b);
28602865
binding_set(&nb, to_var, &found);
@@ -2887,6 +2892,10 @@ static void expand_var_length(cbm_store_t *store, cbm_rel_pattern_t *rel,
28872892
if (!check_inline_props(&hop->node, target_node->props, target_node->prop_count, store)) {
28882893
continue;
28892894
}
2895+
cbm_node_t *existing = binding_get(b, to_var);
2896+
if (existing && existing->id != hop->node.id) {
2897+
continue;
2898+
}
28902899
binding_t nb = {0};
28912900
binding_copy(&nb, b);
28922901
binding_set(&nb, to_var, &hop->node);
@@ -4150,16 +4159,44 @@ static void execute_default_projection(cbm_pattern_t *pat0, binding_t *bindings,
41504159
/* Cross-join node-only pattern into existing bindings */
41514160
static void cross_join_nodes(binding_t **bindings, int *bind_count, cbm_node_t *extra_nodes,
41524161
int extra_count, const char *nvar, bool opt) {
4153-
binding_t *new_bindings = malloc(((*bind_count * extra_count) + SKIP_ONE) * sizeof(binding_t));
4162+
int capacity = *bind_count + extra_count + SKIP_ONE;
4163+
binding_t *new_bindings = malloc(capacity * sizeof(binding_t));
4164+
if (!new_bindings) {
4165+
return;
4166+
}
41544167
int new_count = 0;
41554168
for (int bi = 0; bi < *bind_count; bi++) {
41564169
for (int ni = 0; ni < extra_count; ni++) {
4170+
if (new_count >= capacity) {
4171+
capacity *= 2;
4172+
binding_t *nxt = realloc(new_bindings, capacity * sizeof(binding_t));
4173+
if (!nxt) {
4174+
for (int k = 0; k < new_count; k++) {
4175+
binding_free(&new_bindings[k]);
4176+
}
4177+
free(new_bindings);
4178+
return;
4179+
}
4180+
new_bindings = nxt;
4181+
}
41574182
binding_t nb = {0};
41584183
binding_copy(&nb, &(*bindings)[bi]);
41594184
binding_set(&nb, nvar, &extra_nodes[ni]);
41604185
new_bindings[new_count++] = nb;
41614186
}
41624187
if (opt && extra_count == 0) {
4188+
if (new_count >= capacity) {
4189+
capacity *= 2;
4190+
binding_t *nxt = realloc(new_bindings, capacity * sizeof(binding_t));
4191+
if (!nxt) {
4192+
for (int k = 0; k < new_count; k++) {
4193+
binding_free(&new_bindings[k]);
4194+
}
4195+
free(new_bindings);
4196+
return;
4197+
}
4198+
new_bindings = nxt;
4199+
}
41634200
binding_t nb = {0};
41644201
binding_copy(&nb, &(*bindings)[bi]);
41654202
new_bindings[new_count++] = nb;
@@ -4177,10 +4214,14 @@ static void cross_join_nodes(binding_t **bindings, int *bind_count, cbm_node_t *
41774214
static void cross_join_with_rels(cbm_store_t *store, cbm_pattern_t *patn, binding_t **bindings,
41784215
int *bind_count, cbm_node_t *extra_nodes, int extra_count,
41794216
const char *nvar, bool opt) {
4180-
binding_t *new_bindings =
4181-
malloc(((*bind_count * extra_count * CYP_GROWTH_10) + SKIP_ONE) * sizeof(binding_t));
4217+
int capacity = *bind_count + extra_count + SKIP_ONE;
4218+
binding_t *new_bindings = malloc(capacity * sizeof(binding_t));
4219+
if (!new_bindings) {
4220+
return;
4221+
}
41824222
int new_count = 0;
41834223
for (int bi = 0; bi < *bind_count; bi++) {
4224+
bool any_matched = false;
41844225
for (int ni = 0; ni < extra_count; ni++) {
41854226
binding_t nb = {0};
41864227
binding_copy(&nb, &(*bindings)[bi]);
@@ -4190,13 +4231,41 @@ static void cross_join_with_rels(cbm_store_t *store, cbm_pattern_t *patn, bindin
41904231
int tc = SKIP_ONE;
41914232
int tcap = SKIP_ONE;
41924233
const char *tv = nvar;
4193-
expand_pattern_rels(store, patn, &tmp, &tc, &tcap, &tv, opt);
4194-
for (int ti = 0; ti < tc; ti++) {
4195-
new_bindings[new_count++] = tmp[ti];
4234+
expand_pattern_rels(store, patn, &tmp, &tc, &tcap, &tv, false);
4235+
if (tc > 0) {
4236+
any_matched = true;
4237+
for (int ti = 0; ti < tc; ti++) {
4238+
if (new_count >= capacity) {
4239+
capacity *= 2;
4240+
binding_t *nxt = realloc(new_bindings, capacity * sizeof(binding_t));
4241+
if (!nxt) {
4242+
for (int k = 0; k < new_count; k++) {
4243+
binding_free(&new_bindings[k]);
4244+
}
4245+
free(new_bindings);
4246+
free(tmp);
4247+
return;
4248+
}
4249+
new_bindings = nxt;
4250+
}
4251+
new_bindings[new_count++] = tmp[ti];
4252+
}
41964253
}
41974254
free(tmp);
41984255
}
4199-
if (opt && extra_count == 0) {
4256+
if (opt && !any_matched) {
4257+
if (new_count >= capacity) {
4258+
capacity *= 2;
4259+
binding_t *nxt = realloc(new_bindings, capacity * sizeof(binding_t));
4260+
if (!nxt) {
4261+
for (int k = 0; k < new_count; k++) {
4262+
binding_free(&new_bindings[k]);
4263+
}
4264+
free(new_bindings);
4265+
return;
4266+
}
4267+
new_bindings = nxt;
4268+
}
42004269
binding_t nb = {0};
42014270
binding_copy(&nb, &(*bindings)[bi]);
42024271
new_bindings[new_count++] = nb;

‎tests/test_cypher.c‎

Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2222,6 +2222,27 @@ TEST(cypher_exec_with_where) {
22222222
PASS();
22232223
}
22242224

2225+
TEST(cypher_exec_optional_match_with_where_is_null) {
2226+
cbm_store_t *s = setup_cypher_store();
2227+
cbm_cypher_result_t r = {0};
2228+
int rc = cbm_cypher_execute(s,
2229+
"MATCH (f:Function) "
2230+
"OPTIONAL MATCH (caller)-[r:CALLS]->(f) "
2231+
"WITH f, r "
2232+
"WHERE r IS NULL "
2233+
"RETURN f.name",
2234+
"test", 0, &r);
2235+
ASSERT_EQ(rc, 0);
2236+
/* HandleOrder has NO incoming CALLS edge (r IS NULL)
2237+
* All other functions (ValidateOrder, SubmitOrder, LogError) have incoming CALLS edge (r is NOT NULL)
2238+
* So only HandleOrder should be returned! */
2239+
ASSERT_EQ(r.row_count, 1);
2240+
ASSERT_STR_EQ(r.rows[0][0], "HandleOrder");
2241+
cbm_cypher_result_free(&r);
2242+
cbm_store_close(s);
2243+
PASS();
2244+
}
2245+
22252246
TEST(cypher_exec_with_node_bare_prop) {
22262247
cbm_store_t *s = setup_cypher_store();
22272248
cbm_cypher_result_t r = {0};
@@ -2242,6 +2263,35 @@ TEST(cypher_exec_with_node_bare_prop) {
22422263
PASS();
22432264
}
22442265

2266+
TEST(cypher_exec_optional_match_aggregation) {
2267+
cbm_store_t *s = setup_cypher_store();
2268+
cbm_cypher_result_t r = {0};
2269+
int rc = cbm_cypher_execute(s,
2270+
"MATCH (f:Function) "
2271+
"OPTIONAL MATCH (caller)-[r:CALLS]->(f) "
2272+
"RETURN f.name, COUNT(caller) "
2273+
"LIMIT 10",
2274+
"test", 0, &r);
2275+
ASSERT_EQ(rc, 0);
2276+
/* In the mock store:
2277+
* - HandleOrder has 0 incoming calls (COUNT = 0)
2278+
* - ValidateOrder has 1 incoming call from HandleOrder (COUNT = 1)
2279+
* - SubmitOrder has 1 incoming call from ValidateOrder (COUNT = 1)
2280+
* - LogError has 1 incoming call from HandleOrder (COUNT = 1)
2281+
* Total = 4 rows! */
2282+
ASSERT_EQ(r.row_count, 4);
2283+
for (int i = 0; i < r.row_count; i++) {
2284+
if (strcmp(r.rows[i][0], "HandleOrder") == 0) {
2285+
ASSERT_STR_EQ(r.rows[i][1], "0");
2286+
} else {
2287+
ASSERT_STR_EQ(r.rows[i][1], "1");
2288+
}
2289+
}
2290+
cbm_cypher_result_free(&r);
2291+
cbm_store_close(s);
2292+
PASS();
2293+
}
2294+
22452295
TEST(cypher_exec_with_orderby_limit) {
22462296
cbm_store_t *s = setup_cypher_store();
22472297
cbm_cypher_result_t r = {0};
@@ -2685,7 +2735,9 @@ SUITE(cypher) {
26852735
RUN_TEST(cypher_exec_with_count);
26862736
RUN_TEST(cypher_exec_with_node_groupvar_prop);
26872737
RUN_TEST(cypher_exec_with_where);
2738+
RUN_TEST(cypher_exec_optional_match_with_where_is_null);
26882739
RUN_TEST(cypher_exec_with_node_bare_prop);
2740+
RUN_TEST(cypher_exec_optional_match_aggregation);
26892741
RUN_TEST(cypher_exec_with_orderby_limit);
26902742
RUN_TEST(cypher_parse_with);
26912743
RUN_TEST(cypher_parse_with_where);

0 commit comments

Comments
 (0)