Bug: Kuzu wrongly output non-existing relations in certain cases

Kùzu version

v0.6.0

What operating system are you using?

Ubuntu 22.04

What happened?

Hi! I discovered a bug that Kuzu could produce non-existing relations in complex MATCH patterns. Steps to reproduce are as follows:

Run the following query to prepare the initial data. Please note that id field for each node and relations are unique:

CREATE NODE TABLE L0 (k0 STRING, k1 BOOLEAN, k2 BOOLEAN, k3 BOOLEAN, k4 STRING, k5 STRING, k6 STRING, id INT64, PRIMARY KEY (id));
CREATE NODE TABLE L1 (k7 STRING, k8 STRING, k9 BOOLEAN, k10 STRING, k11 INT64, k12 STRING, k13 INT64, id INT64, PRIMARY KEY (id));
CREATE NODE TABLE L2 (k14 STRING, k15 INT64, k16 STRING, k17 STRING, k18 STRING, id INT64, PRIMARY KEY (id));
CREATE NODE TABLE L3 (k19 STRING, k20 BOOLEAN, k21 INT64, k22 STRING, k23 STRING, id INT64, PRIMARY KEY (id));
CREATE NODE TABLE L4 (k24 BOOLEAN, k25 BOOLEAN, k26 BOOLEAN, k27 STRING, k28 BOOLEAN, k29 BOOLEAN, id INT64, PRIMARY KEY (id));
CREATE NODE TABLE L5 (k30 STRING, k31 INT64, k32 BOOLEAN, k33 STRING, k34 BOOLEAN, id INT64, PRIMARY KEY (id));
CREATE NODE TABLE L6 (k35 BOOLEAN, k36 BOOLEAN, k37 BOOLEAN, k38 INT64, k39 BOOLEAN, k40 STRING, id INT64, PRIMARY KEY (id));
CREATE NODE TABLE L7 (k41 BOOLEAN, k42 STRING, k43 STRING, k44 STRING, k45 STRING, k46 BOOLEAN, k47 BOOLEAN, id INT64, PRIMARY KEY (id));
CREATE NODE TABLE L8 (k48 STRING, k49 INT64, k50 BOOLEAN, k51 STRING, k52 BOOLEAN, k53 INT64, id INT64, PRIMARY KEY (id));
CREATE REL TABLE T1 (FROM L7 TO L0, k59 STRING, k60 STRING, k61 BOOLEAN, k62 BOOLEAN, k63 STRING, k64 INT64, k65 BOOLEAN, id INT64);
CREATE REL TABLE T3 (FROM L2 TO L3, k72 BOOLEAN, k73 STRING, k74 STRING, k75 STRING, k76 BOOLEAN, k77 STRING, id INT64);
CREATE REL TABLE T7 (FROM L1 TO L6, k97 INT64, k98 INT64, k99 INT64, k100 BOOLEAN, k101 STRING, k102 INT64, id INT64);
CREATE REL TABLE T8 (FROM L3 TO L7, k103 STRING, k104 INT64, k105 BOOLEAN, k106 INT64, k107 STRING, k108 BOOLEAN, k109 BOOLEAN, id INT64);
CREATE REL TABLE T9 (FROM L2 TO L3, k110 INT64, k111 BOOLEAN, k112 STRING, k113 BOOLEAN, k114 INT64, id INT64);
CREATE REL TABLE T10 (FROM L1 TO L2, k115 STRING, k116 BOOLEAN, k117 STRING, k118 STRING, k119 BOOLEAN, k120 STRING, id INT64);
CREATE REL TABLE T11 (FROM L0 TO L6, k121 STRING, k122 BOOLEAN, k123 STRING, k124 BOOLEAN, k125 BOOLEAN, k126 BOOLEAN, id INT64);
CREATE REL TABLE T12 (FROM L1 TO L3, k127 INT64, k128 STRING, k129 INT64, k130 BOOLEAN, k131 BOOLEAN, k132 STRING, id INT64);
CREATE REL TABLE T13 (FROM L6 TO L7, k133 INT64, k134 INT64, k135 INT64, k136 INT64, k137 STRING, k138 STRING, id INT64);
CREATE REL TABLE T14 (FROM L2 TO L5, k139 INT64, k140 BOOLEAN, k141 STRING, k142 INT64, k143 STRING, k144 INT64, k145 STRING, id INT64);
CREATE REL TABLE T15 (FROM L6 TO L5, k146 BOOLEAN, k147 STRING, k148 INT64, k149 INT64, k150 INT64, k151 BOOLEAN, id INT64);
CREATE REL TABLE T17 (FROM L4 TO L7, k159 BOOLEAN, k160 BOOLEAN, k161 STRING, k162 STRING, k163 INT64, k164 STRING, k165 STRING, id INT64);
CREATE REL TABLE T18 (FROM L3 TO L3, k166 BOOLEAN, k167 INT64, k168 BOOLEAN, k169 BOOLEAN, k170 STRING, k171 STRING, id INT64);
CREATE REL TABLE T20 (FROM L3 TO L1, k178 STRING, k179 STRING, k180 BOOLEAN, k181 BOOLEAN, k182 STRING, id INT64);
CREATE REL TABLE T21 (FROM L3 TO L3, k183 BOOLEAN, k184 BOOLEAN, k185 STRING, k186 INT64, k187 BOOLEAN, id INT64);
CREATE REL TABLE T22 (FROM L3 TO L5, k188 BOOLEAN, k189 BOOLEAN, k190 STRING, k191 BOOLEAN, k192 INT64, id INT64);
CREATE REL TABLE T23 (FROM L0 TO L3, k193 BOOLEAN, k194 INT64, k195 INT64, k196 BOOLEAN, k197 STRING, k198 BOOLEAN, id INT64);
CREATE REL TABLE T27 (FROM L6 TO L5, k215 BOOLEAN, k216 BOOLEAN, k217 STRING, k218 INT64, k219 BOOLEAN, k220 BOOLEAN, id INT64);
CREATE REL TABLE T28 (FROM L5 TO L4, k221 STRING, k222 BOOLEAN, k223 BOOLEAN, k224 BOOLEAN, k225 STRING, id INT64);
CREATE REL TABLE T30 (FROM L0 TO L4, k232 BOOLEAN, k233 STRING, k234 BOOLEAN, k235 BOOLEAN, k236 STRING, k237 INT64, k238 STRING, id INT64);
CREATE REL TABLE T31 (FROM L7 TO L1, k239 BOOLEAN, k240 INT64, k241 BOOLEAN, k242 INT64, k243 INT64, id INT64);
CREATE (n0 :L6{k39 : false, k38 : 6451680089028944539, k40 : "OVdn5", id : 0, k35 : true, k37 : true, k36 : false});
CREATE (n0 :L5{k31 : -7110709925932883394, k30 : "Z2gyVk", k33 : "TGTnDFpo", k32 : true, id : 2, k34 : true});
CREATE (n0 :L3{k19 : "rScz1", k20 : true, k22 : "RhUJqF5PZ", k21 : -8225046834506062883, id : 3, k23 : "RLZ71JCCl"});
CREATE (n0 :L7{k42 : "zVl5W", k41 : false, k44 : "qmJsPU", k43 : "1cq3R", id : 5, k46 : false, k45 : "tddgZm7W", k47 : false});
CREATE (n0 :L6{k38 : -2868270034940498464, k40 : "iqijZpv", id : 8, k35 : false, k37 : false, k36 : false});
CREATE (n0 :L3{k20 : true, k22 : "IrooyglYm", k21 : -7996780931417323366, id : 9, k23 : "BQ4mdvLd"});
CREATE (n0 :L2{k17 : "Vn4TXyxN", k16 : "SMl7hM2Z", k18 : "GLcLPaqiz", id : 10, k15 : 8603278643824158927, k14 : "Tsjwkq"});
MATCH (n0 {id : 1}), (n1 {id : 2}) CREATE(n0)-[r :T25{k204 : true, id : 11, k206 : 3642269942505217845, k205 : 1552925254289060035, k208 : -440872372865862201}]->(n1);
MATCH (n0 {id : 9}), (n1 {id : 2}) CREATE(n0)-[r :T22{k189 : false, k188 : false, id : 12, k192 : -8231495005118831161, k191 : false}]->(n1);
MATCH (n0 {id : 0}), (n1 {id : 5}) CREATE(n0)-[r :T13{k134 : 3233695358477561250, k133 : 1712312234490868124, k136 : 8139298401196686249, k135 : -2859283561225411564, k138 : "oTqohd", k137 : "g3tMeYB", id : 13}]->(n1);
MATCH (n0 {id : 0}), (n1 {id : 1}) CREATE(n0)-[r :T19{k172 : -2996511376664851653, k174 : false, k173 : true, k176 : -388690034533412998, k175 : true, k177 : false, id : 15}]->(n1);
MATCH (n0 {id : 9}), (n1 {id : 9}) CREATE(n0)-[r :T21{k183 : false, k185 : "Sm2tf4", k184 : true, k187 : true, k186 : 3577337712342130273, id : 17}]->(n1);
MATCH (n0 {id : 3}), (n1 {id : 5}) CREATE(n0)-[r :T8{k103 : "hHlj4Is9W", k105 : false, id : 19, k107 : "FETY6P", k106 : 6431465387480627665, k109 : true, k108 : true}]->(n1);

Run the following query:

MATCH (n0)-[r0]-(n1{k20:true}), (n2)-[r1]-(n3{k20:true}), (n4)<-[r2]-(n5), (n5{k39:false})-[r3]->(n2{k41:false}) WHERE (((r2.id) <> (r3.id)) AND true) RETURN n2.id as a0, r1.id as a1, n3.id as a2;

Please pay attention to the second pattern. Kuzu outputs n2.id=9, connected to r1.id=19, then connected to node n3.id=3. However, there isn't a relation from node with id=9 to node with id=3. Meanwhile, relation id=19 are used to connect node id=3 and id=5, according to this query:

MATCH (n0 {id : 3}), (n1 {id : 5}) CREATE(n0)-[r :T8{k103 : "hHlj4Is9W", k105 : false, id : 19, k107 : "FETY6P", k106 : 6431465387480627665, k109 : true, k108 : true}]->(n1);

Therefore, Kuzu outputs a non-existing relation somehow. Thank you!

Are there known steps to reproduce?

No response

kuzudb / kuzu