incubator-hugegraph icon indicating copy to clipboard operation
incubator-hugegraph copied to clipboard

Published 20 hours ago • verified publisher icon apache

[Bug] Query partitioning return false results

Open llooFlashooll opened this issue 1 year ago • 3 comments

Bug Type (问题类型)

gremlin (结果不合预期)

Before submit

  • [X] 我已经确认现有的 Issues 与 FAQ 中没有相同 / 重复问题 (I have confirmed and searched that there are no similar problems in the historical issue and documents)

Environment (环境信息)

  • HugeGraph Version: 0.12.0
  • Storage Backend: inmemory
  • Mixed Index Backend: none
  • Link to discussed bug: none
  • Operating system: macOS 13.2.1
  • API/Driver: Java

Expected & Actual behavior (期望与实际表现)

  • Expected behavior: We construct the following scenario: we split a given query Q into three derived sub-queries, in which the predicate is evaluated to TRUE, FALSE, and IS NULL, respectively. The union of the three derived result sets should be equal to the result set of query Q. We generate graph schema and data based on random strings and values. Here is one of our examples that triggered the bug.
  1. g.V().count() returns 10
  2. g.V().has('vp0', inside(0.5804740550941045,0.45305711119170766)).count() returns 0
  3. g.V().has('vp0', not(inside(0.5804740550941045,0.45305711119170766))).count() returns 6
  4. g.V().hasNot('vp0').count() returns 5 We can see that sub-queries 2, 3, 4 results: 0 + 6 + 5 != 10
  • Actual behavior: The sum of sub-queries 2, 3, 4 results: 0 + 6 + 5 != 10

Vertex/Edge example (问题点 / 边数据举例)

  • Steps to reproduce: We are developing a fuzzing technique to test your GraphDB. We create a graph with 10 nodes and 20 edges. And try to make it clear to reproduce the bugs, hope to not cause much inconvenience to your reviewing, but we believe the problem does exist. Following the following graph data generation query, we can reproduce the bugs:
  • Create data
Vertex:
g.addV('vl1').property('vp2','5574433807181218360').property(T.id,698931944968159232)
g.addV('vl2').property('vp1','6734362169804229224').property(T.id,698931944997519360)
g.addV('vl0').property('vp0','0.6329616125435166').property(T.id,698931945022685184)
g.addV('vl0').property('vp0','0.6329616125435166').property(T.id,698931945043656704)
g.addV('vl2').property('vp1','5309446427344485779').property(T.id,698931945060433920)
g.addV('vl2').property('vp1','-3558853306979155692').property(T.id,698931945077211136)
g.addV('vl2').property('vp1','-8943982883114759437').property(T.id,698931945093988352)
g.addV('vl1').property('vp0','0.16393365972677754').property('vp2','7817799776452691691').property(T.id,698931945110765568)
g.addV('vl1').property('vp0','0.4210924705367233').property(T.id,698931945127542784)
g.addV('vl1').property('vp0','0.47655165657875387').property(T.id,698931945144320000)
Edge:
g.V(698931945144320000).as('698931945144320000').V(698931945110765568).as('698931945110765568').addE('el2').from('698931945144320000').to('698931945110765568')
g.V(698931944968159232).as('698931944968159232').V(698931945110765568).as('698931945110765568').addE('el0').from('698931944968159232').to('698931945110765568')
g.V(698931945110765568).as('698931945110765568').V(698931945127542784).as('698931945127542784').addE('el0').from('698931945110765568').to('698931945127542784')
g.V(698931945127542784).as('698931945127542784').V(698931945144320000).as('698931945144320000').addE('el0').from('698931945127542784').to('698931945144320000')
g.V(698931945110765568).as('698931945110765568').V(698931945093988352).as('698931945093988352').addE('el1').from('698931945110765568').to('698931945093988352')
g.V(698931945127542784).as('698931945127542784').V(698931944968159232).as('698931944968159232').addE('el2').from('698931945127542784').to('698931944968159232')
g.V(698931945127542784).as('698931945127542784').V(698931945093988352).as('698931945093988352').addE('el3').from('698931945127542784').to('698931945093988352')
g.V(698931944968159232).as('698931944968159232').V(698931945093988352).as('698931945093988352').addE('el1').from('698931944968159232').to('698931945093988352')
g.V(698931945127542784).as('698931945127542784').V(698931945093988352).as('698931945093988352').addE('el1').from('698931945127542784').to('698931945093988352')
g.V(698931944968159232).as('698931944968159232').V(698931945127542784).as('698931945127542784').addE('el2').from('698931944968159232').to('698931945127542784')
g.V(698931945110765568).as('698931945110765568').V(698931945077211136).as('698931945077211136').addE('el3').from('698931945110765568').to('698931945077211136')
g.V(698931945110765568).as('698931945110765568').V(698931945110765568).as('698931945110765568').addE('el0').from('698931945110765568').to('698931945110765568')
g.V(698931945110765568).as('698931945110765568').V(698931945110765568).as('698931945110765568').addE('el2').from('698931945110765568').to('698931945110765568')
g.V(698931944968159232).as('698931944968159232').V(698931944997519360).as('698931944997519360').addE('el1').from('698931944968159232').to('698931944997519360')
g.V(698931945144320000).as('698931945144320000').V(698931945060433920).as('698931945060433920').addE('el3').from('698931945144320000').to('698931945060433920')
g.V(698931945110765568).as('698931945110765568').V(698931944968159232).as('698931944968159232').addE('el2').from('698931945110765568').to('698931944968159232')
g.V(698931945127542784).as('698931945127542784').V(698931945077211136).as('698931945077211136').addE('el3').from('698931945127542784').to('698931945077211136')
g.V(698931945110765568).as('698931945110765568').V(698931945144320000).as('698931945144320000').addE('el2').from('698931945110765568').to('698931945144320000')
g.V(698931945110765568).as('698931945110765568').V(698931944997519360).as('698931944997519360').addE('el3').from('698931945110765568').to('698931944997519360')
g.V(698931945110765568).as('698931945110765568').V(698931945060433920).as('698931945060433920').addE('el3').from('698931945110765568').to('698931945060433920')

Schema [VertexLabel, EdgeLabel, IndexLabel] (元数据结构)

  • Create schema
schema().propertyKey('vp0').asDouble().ifNotExist().create();
schema().propertyKey('vp1').asLong().ifNotExist().create();
schema().propertyKey('vp2').asLong().ifNotExist().create();
schema().vertexLabel('vl0').ifNotExist().create();
schema().vertexLabel('vl0').properties('vp0').nullableKeys('vp0').append();
schema().indexLabel('vl0byvp0Shard').onV('vl0').by('vp0').shard().ifNotExist().create();
schema().vertexLabel('vl1').ifNotExist().create();
schema().vertexLabel('vl1').properties('vp0').nullableKeys('vp0').append();
schema().indexLabel('vl1byvp0Shard').onV('vl1').by('vp0').shard().ifNotExist().create();
schema().vertexLabel('vl1').properties('vp2').nullableKeys('vp2').append();
schema().indexLabel('vl1byvp2Shard').onV('vl1').by('vp2').shard().ifNotExist().create();
schema().vertexLabel('vl2').ifNotExist().create();
schema().vertexLabel('vl2').properties('vp1').nullableKeys('vp1').append();
schema().indexLabel('vl2byvp1Shard').onV('vl2').by('vp1').shard().ifNotExist().create();
schema().propertyKey('ep0').asLong().ifNotExist().create();
schema().propertyKey('ep1').asText().ifNotExist().create();
schema().propertyKey('ep2').asLong().ifNotExist().create();
schema().propertyKey('ep3').asInt().ifNotExist().create();
schema().propertyKey('ep4').asDouble().ifNotExist().create();
schema().propertyKey('ep5').asFloat().ifNotExist().create();
schema().propertyKey('ep6').asDouble().ifNotExist().create();
schema().edgeLabel('el0').link('vl1', 'vl1').ifNotExist().create();
schema().edgeLabel('el0').properties('ep0').nullableKeys('ep0').append();
schema().indexLabel('el0byep0Shard').onE('el0').by('ep0').shard().ifNotExist().create();
schema().edgeLabel('el0').properties('ep2').nullableKeys('ep2').append();
schema().indexLabel('el0byep2Shard').onE('el0').by('ep2').shard().ifNotExist().create();
schema().edgeLabel('el0').properties('ep3').nullableKeys('ep3').append();
schema().indexLabel('el0byep3Shard').onE('el0').by('ep3').shard().ifNotExist().create();
schema().edgeLabel('el0').properties('ep6').nullableKeys('ep6').append();
schema().indexLabel('el0byep6Shard').onE('el0').by('ep6').shard().ifNotExist().create();
schema().edgeLabel('el0').properties('ep5').nullableKeys('ep5').append();
schema().indexLabel('el0byep5Shard').onE('el0').by('ep5').shard().ifNotExist().create();
schema().edgeLabel('el0').properties('ep1').nullableKeys('ep1').append();
schema().indexLabel('el0byep1Shard').onE('el0').by('ep1').shard().ifNotExist().create();
schema().edgeLabel('el1').link('vl2', 'vl1').ifNotExist().create();
schema().edgeLabel('el1').properties('ep5').nullableKeys('ep5').append();
schema().indexLabel('el1byep5Shard').onE('el1').by('ep5').shard().ifNotExist().create();
schema().edgeLabel('el1').properties('ep0').nullableKeys('ep0').append();
schema().indexLabel('el1byep0Shard').onE('el1').by('ep0').shard().ifNotExist().create();
schema().edgeLabel('el1').properties('ep3').nullableKeys('ep3').append();
schema().indexLabel('el1byep3Shard').onE('el1').by('ep3').shard().ifNotExist().create();
schema().edgeLabel('el1').properties('ep1').nullableKeys('ep1').append();
schema().indexLabel('el1byep1Shard').onE('el1').by('ep1').shard().ifNotExist().create();
schema().edgeLabel('el1').properties('ep6').nullableKeys('ep6').append();
schema().indexLabel('el1byep6Shard').onE('el1').by('ep6').shard().ifNotExist().create();
schema().edgeLabel('el2').link('vl1', 'vl1').ifNotExist().create();
schema().edgeLabel('el2').properties('ep1').nullableKeys('ep1').append();
schema().indexLabel('el2byep1Shard').onE('el2').by('ep1').shard().ifNotExist().create();
schema().edgeLabel('el2').properties('ep4').nullableKeys('ep4').append();
schema().indexLabel('el2byep4Shard').onE('el2').by('ep4').shard().ifNotExist().create();
schema().edgeLabel('el2').properties('ep2').nullableKeys('ep2').append();
schema().indexLabel('el2byep2Shard').onE('el2').by('ep2').shard().ifNotExist().create();
schema().edgeLabel('el3').link('vl2', 'vl1').ifNotExist().create();
schema().edgeLabel('el3').properties('ep2').nullableKeys('ep2').append();
schema().indexLabel('el3byep2Shard').onE('el3').by('ep2').shard().ifNotExist().create();
schema().edgeLabel('el3').properties('ep4').nullableKeys('ep4').append();
schema().indexLabel('el3byep4Shard').onE('el3').by('ep4').shard().ifNotExist().create();
schema().edgeLabel('el3').properties('ep6').nullableKeys('ep6').append();
schema().indexLabel('el3byep6Shard').onE('el3').by('ep6').shard().ifNotExist().create();
schema().edgeLabel('el3').properties('ep1').nullableKeys('ep1').append();
schema().indexLabel('el3byep1Shard').onE('el3').by('ep1').shard().ifNotExist().create();

llooFlashooll avatar Mar 10 '23 08:03 llooFlashooll

Because not(inside(0.5804740550941045,0.45305711119170766), that's vp0.or(lte(0.5804740550941045), gte(0.45305711119170766)) will be split 2 subquery, and they may produce duplicate results.

please try explain(): g.V().has('vp0', not(inside(0.5804740550941045,0.45305711119170766))).explain()

The root cause is the illegal conditions in inside(), it's ok if query with inside(0.4, 0.5):

g.V().count() // 10
g.V().has('vp0', inside(0.4, 0.5)).count() // 2
g.V().has('vp0', not(inside(0.4, 0.5))).count() // 3
g.V().hasNot('vp0').count() // 5

gremlin sample:

g.addV('vl1').property('vp2', 5574433807181218360)
.addV('vl2').property('vp1', 6734362169804229224)
.addV('vl0').property('vp0', 0.6329616125435166)
.addV('vl0').property('vp0', 0.6329616125435166)
.addV('vl2').property('vp1', 5309446427344485779)
.addV('vl2').property('vp1', -3558853306979155692)
.addV('vl2').property('vp1', -8943982883114759437)
.addV('vl1').property('vp0', 0.16393365972677754).property('vp2', 7817799776452691691)
.addV('vl1').property('vp0', 0.4210924705367233)
.addV('vl1').property('vp0', 0.47655165657875387)

g.V().count() // 10
g.V().has('vp0', inside(0.5804740550941045,0.45305711119170766)).count() // 0
g.V().has('vp0', not(inside(0.5804740550941045,0.45305711119170766))).count() // 6
g.V().hasNot('vp0').count() // 5

list1=g.V().hasNot('vp0').id().map{it.get().toString()}.toList()
list2=g.V().has('vp0', not(inside(0.5804740550941045,0.45305711119170766))).id().map{it.get().toString()}.toList()
[list1,list2]

g.V().has('vp0', not(inside(0.5804740550941045,0.45305711119170766))).explain()

javeme avatar Mar 10 '23 14:03 javeme

Received with thanks! I'll further check this.

llooFlashooll avatar Mar 10 '23 14:03 llooFlashooll

Sorry, but during my continuous testing, I believe there're still some problems in this part. And other classical GDBs actually support such queries, and even the syntax such as outside() has the wrong arguments order. Let me give you another example.

  1. g.V().count() returns 10
  2. g.V().has('vp1', gte(0.43878973).or(inside(0.0207991,0.9933907))).count() returns 14
  3. g.V().has('vp1', not(gte(0.43878973).or(inside(0.0207991,0.9933907)))).count() returns 0
  4. g.V().hasNot('vp1').count() returns 2 We can see that sub-queries 2, 3, 4 results: 14 + 0 + 2 != 10
  • Schema
schema().propertyKey('vp0').asDouble().ifNotExist().create();
schema().propertyKey('vp1').asFloat().ifNotExist().create();
schema().propertyKey('vp2').asInt().ifNotExist().create();
schema().propertyKey('vp3').asInt().ifNotExist().create();
schema().propertyKey('vp4').asDouble().ifNotExist().create();
schema().propertyKey('vp5').asFloat().ifNotExist().create();
schema().propertyKey('vp6').asInt().ifNotExist().create();
schema().propertyKey('vp7').asDouble().ifNotExist().create();
schema().propertyKey('vp8').asInt().ifNotExist().create();
schema().vertexLabel('vl0').ifNotExist().create();
schema().vertexLabel('vl0').properties('vp2').nullableKeys('vp2').append();
schema().indexLabel('vl0byvp2Shard').onV('vl0').by('vp2').shard().ifNotExist().create();
schema().vertexLabel('vl0').properties('vp6').nullableKeys('vp6').append();
schema().indexLabel('vl0byvp6Shard').onV('vl0').by('vp6').shard().ifNotExist().create();
schema().vertexLabel('vl0').properties('vp0').nullableKeys('vp0').append();
schema().indexLabel('vl0byvp0Shard').onV('vl0').by('vp0').shard().ifNotExist().create();
schema().vertexLabel('vl0').properties('vp4').nullableKeys('vp4').append();
schema().indexLabel('vl0byvp4Shard').onV('vl0').by('vp4').shard().ifNotExist().create();
schema().vertexLabel('vl0').properties('vp1').nullableKeys('vp1').append();
schema().indexLabel('vl0byvp1Shard').onV('vl0').by('vp1').shard().ifNotExist().create();
schema().propertyKey('ep0').asText().ifNotExist().create();
schema().propertyKey('ep1').asBoolean().ifNotExist().create();
schema().propertyKey('ep2').asDouble().ifNotExist().create();
schema().propertyKey('ep3').asLong().ifNotExist().create();
schema().propertyKey('ep4').asDouble().ifNotExist().create();
schema().propertyKey('ep5').asFloat().ifNotExist().create();
schema().propertyKey('ep6').asText().ifNotExist().create();
schema().edgeLabel('el0').link('vl0', 'vl0').ifNotExist().create();
schema().edgeLabel('el0').properties('ep3').nullableKeys('ep3').append();
schema().indexLabel('el0byep3Shard').onE('el0').by('ep3').shard().ifNotExist().create();
schema().edgeLabel('el0').properties('ep4').nullableKeys('ep4').append();
schema().indexLabel('el0byep4Shard').onE('el0').by('ep4').shard().ifNotExist().create();
schema().edgeLabel('el0').properties('ep5').nullableKeys('ep5').append();
schema().indexLabel('el0byep5Shard').onE('el0').by('ep5').shard().ifNotExist().create();
schema().edgeLabel('el0').properties('ep1').nullableKeys('ep1').append();
schema().indexLabel('el0byep1Shard').onE('el0').by('ep1').shard().ifNotExist().create();
schema().edgeLabel('el1').link('vl0', 'vl0').ifNotExist().create();
schema().edgeLabel('el1').properties('ep5').nullableKeys('ep5').append();
schema().indexLabel('el1byep5Shard').onE('el1').by('ep5').shard().ifNotExist().create();
schema().edgeLabel('el2').link('vl0', 'vl0').ifNotExist().create();
schema().edgeLabel('el2').properties('ep1').nullableKeys('ep1').append();
schema().indexLabel('el2byep1Shard').onE('el2').by('ep1').shard().ifNotExist().create();
schema().edgeLabel('el2').properties('ep0').nullableKeys('ep0').append();
schema().indexLabel('el2byep0Shard').onE('el2').by('ep0').shard().ifNotExist().create();
schema().edgeLabel('el2').properties('ep6').nullableKeys('ep6').append();
schema().indexLabel('el2byep6Shard').onE('el2').by('ep6').shard().ifNotExist().create();
schema().edgeLabel('el2').properties('ep5').nullableKeys('ep5').append();
schema().indexLabel('el2byep5Shard').onE('el2').by('ep5').shard().ifNotExist().create();
  • Data
Vertex:
g.addV('vl0').property('vp1','0.5955419').property('vp0','0.8441227912306933').property('vp2','182867451').property(T.id,701230294451093504)
g.addV('vl0').property('vp1','0.030927777').property('vp0','0.15811197000651445').property('vp2','-1774039734').property('vp4','0.15811197000651445').property('vp6','-1826077902').property(T.id,701230294509813760)
g.addV('vl0').property('vp1','0.9729499').property('vp2','2030399260').property('vp4','0.8418697950711984').property('vp6','-660038979').property(T.id,701230294539173888)
g.addV('vl0').property('vp1','0.70119077').property('vp0','0.15811197000651445').property('vp2','-1295112053').property('vp4','0.6037576527787519').property(T.id,701230294572728320)
g.addV('vl0').property('vp1','0.83885396').property('vp0','0.7566388111146612').property('vp2','-660038979').property('vp4','0.15811197000651445').property('vp6','182867451').property(T.id,701230294610477056)
g.addV('vl0').property('vp0','-1.774039734E9').property('vp2','1327492548').property('vp4','0.5017301422106627').property('vp6','-660038979').property(T.id,701230294639837184)
g.addV('vl0').property('vp4','0.21033403102542247').property(T.id,701230294665003008)
g.addV('vl0').property('vp1','0.11220425').property('vp0','0.15811197000651445').property('vp4','0.6083243954171486').property('vp6','-1826077902').property(T.id,701230294690168832)
g.addV('vl0').property('vp1','0.49904156').property('vp0','0.7726984864965903').property('vp2','-874981646').property('vp4','0.9525222806364477').property('vp6','-1433016180').property(T.id,701230294719528960)
g.addV('vl0').property('vp1','0.82727903').property('vp6','1174319813').property(T.id,701230294744694784)
Edge:
g.V(701230294572728320).as('701230294572728320').V(701230294744694784).as('701230294744694784').addE('el1').from('701230294572728320').to('701230294744694784')
g.V(701230294639837184).as('701230294639837184').V(701230294744694784).as('701230294744694784').addE('el2').from('701230294639837184').to('701230294744694784')
g.V(701230294744694784).as('701230294744694784').V(701230294610477056).as('701230294610477056').addE('el0').from('701230294744694784').to('701230294610477056')
g.V(701230294610477056).as('701230294610477056').V(701230294610477056).as('701230294610477056').addE('el2').from('701230294610477056').to('701230294610477056')
g.V(701230294744694784).as('701230294744694784').V(701230294572728320).as('701230294572728320').addE('el2').from('701230294744694784').to('701230294572728320')
g.V(701230294539173888).as('701230294539173888').V(701230294665003008).as('701230294665003008').addE('el2').from('701230294539173888').to('701230294665003008')
g.V(701230294690168832).as('701230294690168832').V(701230294719528960).as('701230294719528960').addE('el2').from('701230294690168832').to('701230294719528960')
g.V(701230294610477056).as('701230294610477056').V(701230294572728320).as('701230294572728320').addE('el0').from('701230294610477056').to('701230294572728320')
g.V(701230294572728320).as('701230294572728320').V(701230294639837184).as('701230294639837184').addE('el1').from('701230294572728320').to('701230294639837184')
g.V(701230294665003008).as('701230294665003008').V(701230294539173888).as('701230294539173888').addE('el1').from('701230294665003008').to('701230294539173888')
g.V(701230294451093504).as('701230294451093504').V(701230294451093504).as('701230294451093504').addE('el1').from('701230294451093504').to('701230294451093504')
g.V(701230294610477056).as('701230294610477056').V(701230294572728320).as('701230294572728320').addE('el1').from('701230294610477056').to('701230294572728320')
g.V(701230294572728320).as('701230294572728320').V(701230294690168832).as('701230294690168832').addE('el1').from('701230294572728320').to('701230294690168832')
g.V(701230294690168832).as('701230294690168832').V(701230294639837184).as('701230294639837184').addE('el0').from('701230294690168832').to('701230294639837184')
g.V(701230294665003008).as('701230294665003008').V(701230294690168832).as('701230294690168832').addE('el2').from('701230294665003008').to('701230294690168832')
g.V(701230294719528960).as('701230294719528960').V(701230294665003008).as('701230294665003008').addE('el0').from('701230294719528960').to('701230294665003008')
g.V(701230294744694784).as('701230294744694784').V(701230294719528960).as('701230294719528960').addE('el1').from('701230294744694784').to('701230294719528960')
g.V(701230294719528960).as('701230294719528960').V(701230294690168832).as('701230294690168832').addE('el1').from('701230294719528960').to('701230294690168832')
g.V(701230294665003008).as('701230294665003008').V(701230294639837184).as('701230294639837184').addE('el2').from('701230294665003008').to('701230294639837184')
g.V(701230294744694784).as('701230294744694784').V(701230294719528960).as('701230294719528960').addE('el0').from('701230294744694784').to('701230294719528960')

llooFlashooll avatar Mar 16 '23 16:03 llooFlashooll