求一个较长路径的ngql(match)查询写法

  • 需求原因 / 使用场景
    树查询
  • 需求描述
    根据边的条件,从开始节点不断递归遍历出整个树结构

数据集:
数据集中的节点TAG为:
"CREATE TAG node (
name string NULL,
p int64 NULL
)
对name建了索引

边为:

"CREATE EDGE `link` (
  `v` double NULL
)

对v建了索引

整个数据集为n棵树.他们的节点分别为 {name:“N-0”,p:随机数},{name:“N-1”,p:随机数},{name:“N-2”,p:随机数},......(个数随机)
{name:“N-0”,p:随机数}的子节点为 {name:“N-0-0”,p:随机数},{name:“N-0-1”,p:随机数},{name:“N-0-2”,p:随机数},......(个数随机)
依次类推,所有的节点都这样繁衍生息.到了一定程度随机灭绝,不再有子节点.

目前数据集中最深的树为 12 层.
从其中一个叶子节点往回查
第1个查询:

> MATCH p=(v1)-[e:link*0..15]->(v2:node{name:"N-0-0-0-0-0-0-0-0-0-0-1-0"}) RETURN v1
> ... ...
> Got 12 rows (time spent 11202/18881 us)

耗时很令人喜悦
从根节点往下查到某个具体的叶子节点
第2个查询:

> MATCH p=(:node{name: "N-0"})-[e1:link{v:11}]->()-[e2:link{v:12}]->()-[e3:link{v:8}]->()-[e4:link{v:4}]->()-[e5:link{v:13}]->()-[e6:link{v:4}]->()-[e7:link{v:9}]->()-[e8:link{v:7}]->()-[e9:link{v:2}]->()-[e10:link{v:8}]->()-[e11:link{v:11}]->() WITH nodes(p) AS n UNWIND n AS r RETURN r;
> ... ...
> Got 12 rows (time spent 25934/31933 us)

耗时慢人点,但能接受.

做个粗暴查询,从根节点开始,往下遍历所有子节点.
第3个查询

> MATCH p=(v1:node{name:"N-0"})-[e*..12]->(v2) RETURN v2;
> ......
> Got 696387 rows (time spent 59440143/70847983 us)

这个耗时这么久可以理解,毕竟遍历这么多节点.数量摆在这里.

但在业务中,我可能遍历的和上面 [第2个查询]有点类似,是要对边做一些筛选.比如限定边属性 v <=1.
第4个查询

> MATCH p=(v1:node{name:"N-0"})-[e*..12]->(v2) WHERE e.v <= 1 RETURN p;
> +---+
> | p |
> +---+
> +---+
> Empty set (time spent 339762371/339679276 us)

惊讶,查询出结果为空.为什么要这么慢.从根节点开始.第一跳就没后续了,就可以结束循环.难道和go语句一样.要把指定跳数内所有线路都遍历一下吗?不管前面的步骤能不能持续下去.
这耗时339762371 远远比没指定过滤条件的第3个查询的耗时 59440143 大多了.这多出来的这么多时间是干什么去了.这是我的第一个疑问
再做个查询确定下和go是不是一样的[遍历到前面的步骤如果不满足条件,还会继续遍历后面的步骤,不会提前退出循环.]
从 第2个查询 可以知道,边上有个v属性值为2.算是最小的属性值.那就换下条件再筛选
第5个查询

> MATCH p=(v1:node{name:"N-0"})-[e*..12]->(v2) WHERE e.v <= 2 RETURN p;
> +---+
> | p |
> +---+
> +---+
> Empty set (time spent 303019113/302944554 us)

显然,也是没结果.后续即使有满足条件的也不会拾取(幸亏是这样,这是我想要的).耗时上和第4个查询倒是不差上下. 所有我的第二个疑问来了,为什么不提前结束循环

另外,再补一个疑问.
从studio的节点扩展的功能里可以查看到相应的ngql语句.



它为什么要这样查询.直觉上,他是从整个数据集里筛选出满足条件的所有的边.难道以节点上的边为基数来过滤不香吗,数据量上可能要少很多
我也拿他的这个试运行了下
第6个查询

MATCH p=(v1:node{name:"N-0"})-[e*..12]->(v2) WHERE ALL(l IN e WHERE  l.v <= 1) RETURN p;
+---+
| p |
+---+
+---+
Empty set (time spent 337851985/337768806 us)

耗时上,和 第4个查询 差不多.所以对他的查询模式有个推测"为什么没有提前终止,他是要把筛选出来满足条件的所有数据都遍历一遍,不管模式上是不是匹配"
也因此对 第4个查询 耗时339762371 远远比没指定WHERE过滤条件的第3个查询 的耗时 59440143 大那么多.有一个推测"有where条件的边数很多,没筛选条件的,是从根节点遍历完所有的子节点,不管模式会不会匹配都继续下去,直到没有后续子节点"

所有:
这几个疑问我觉得可能是官方ngql查询可以优化的方面.不然长路径查询起来很慢.
另外也请都下各位大佬,这样的查询场景,目前有没有比较优化的ngql写法.

2 个赞

@yuanliangding 感谢您的提问,非常:+1:t2:,我抛砖尝试回答一下哈。

首先,当 [e*..12] 的时候 WHERE 里 e.v 的数据类型已经不是单个元素了,所以只要是超过一跳的,这里 e.v 的条件无论是什么范围返回一定是空的因为条件是一个 array变量与 int作比较,正确的写法参考您从studio 拓展里看到的。

第一个疑问,关于3与4的差别应该是读索引(左匹配 range )与读边数据的区别 @yee 老师我的理解对么?

第二个疑问我猜测, e.v 实际上蕴含着先取得 e这个 list,再去比较,所以不会提前结束 loop,因为取得 e 蕴含着遍历到头。

第三个疑问(good catch) @yee 老师,这里我们的 ALL 的情况没有短路优化对么?

2 个赞

第一个疑问
我理解你的查询应该是针对这条路径上的所有边做过滤,正确的写法是:

MATCH p=(v1:node{name:"N-0"})-[e*..12]->(v2) 
WHERE ALL(i in e where i.v < 1) 
RETURN p;

因为这里的 e 其实是一个变长的边的集合,所以,如果对所有的边做过滤需要使用 list 函数。

这里为啥会这么慢?其实是因为现在的 match 实现中还没有把类似的过滤下推到 storage 层。不过这个正在做优化了,再丰富 match 相关功能的同时,会提高相关的性能。

如果用 GO M TO N STEPS WHERE 也是在最后做过滤,这里也会遇到下推的问题,如果想快速,可以通过 GO 1 STEP WHERE + pipe 的方式来做。

第二个疑问

类似上面的回答,这里提前结束循环的必要条件是把每一步的 filter 都应用到对应的拓展过程中,这个属于正在考虑的优化部分,目前还没做好。
正确的查询写法参考 1.

问题三

你的推测很正确,这是个很大的优化点,前期对执行计划的构造我们也有思考不周的地方,所以在优化器那里有些地方比较难做过滤下推等优化,目前已经再重新设计执行计划这块了。包括现在 match 拓展的时候会去取所有点边的属性,这里也有很大的优化空间。

非常细致的观察和思考,很赞。感谢你的反馈。

4 个赞

谢谢老师的回复.
(1)

当 [e*…12] 的时候 WHERE 里 e.v 的数据类型已经不是单个元素了
那我就理解这个e的变量含义了.有点像c语言里.int *c .c是一个指针.反直观了.以后懂了.
基于这个勘误,第5个查询应该改成 第5-1个查询
±------------------------------------------------------------------------------+
| p |
±------------------------------------------------------------------------------+
| <(:node{name: “N-0”})-[:link{v: 1.0}]->(:node{name: “N-0-2”})> |
±------------------------------------------------------------------------------+
Got 1 rows (time spent 303184576/303111044 us) (为了显示简洁点.这里对返回结果做了非重要内容的删减)
确实没返回后续的边.这里返回的边是去向了别的节点.

(2)第一疑问

(3)第二疑问

(4)第三疑问

谢谢老师的指点:
我改成你说的GO 1 STEP WHERE + pipe 的方式,确实爽多了.
比如我把 第6个查询 改成等价的 GO 1 STEP WHERE + pipe

GO FROM “4d59713f-7352-4048-9aa3-2316567d07fa” OVER link WHERE link.v <=1 YIELD link._dst AS dst | GO FROM $-.dst OVER link WHERE link.v <=1 YIELD link._dst AS dst | GO FROM $-.dst OVER link WHERE link.v <=1 YIELD link._dst AS dst | GO FROM $-.dst OVER link WHERE link.v <=1 YIELD link._dst AS dst | GO FROM $-.dst OVER link WHERE link.v <=1 YIELD link._dst AS dst | GO FROM $-.dst OVER link WHERE link.v <=1 YIELD link._dst AS dst | GO FROM $-.dst OVER link WHERE link.v <=1 YIELD link._dst AS dst | GO FROM $-.dst OVER link WHERE link.v <=1 YIELD link._dst AS dst | GO FROM $-.dst OVER link WHERE link.v <=1 YIELD link._dst AS dst | GO FROM $-.dst OVER link WHERE link.v <=1 YIELD link._dst AS dst | GO FROM $-.dst OVER link WHERE link.v <=1 YIELD link._dst AS dst
±----+
| dst |
±----+
±----+
Empty set (time spent 6294/9634 us)

这耗时爽多了.
虽然ngql很冗长,但还好是用代码自己生成.
但是还有一个小麻烦.这里是固定了树的深度.如果叶子节点处于不同的深度.估计要接合case语句.写起来更冗长了.不知道老师有没更好的办法.

1 个赞

如果树的深度不同,不清楚应该走几步的情况下,可以在客户端做些工作,目前 nGQL 在兼顾性能的同时确实不是特别好表达一些复杂场景。这块 nebula 寄希望于对 match 的实现做深度的优化,通过 openCypher 的表达能力来实现一些复杂场景的查询。

2 个赞

期待.可以透入一下.新功能的match大概什么时间点会上线吗.

我们match语句在持续完善,10月份有个版本发布,1月份有个版本发布,应该能满足你这边的需求。

1 个赞

该话题在最后一个回复创建后7天后自动关闭。不再允许新的回复。