图解Janusgraph系列-查询图数据过程源码分析

查询流程可以大致分为三部分:组装查询语句、优化查询语句、执行算子链

大家好,我是洋仔,JanusGraph图解系列文章,实时更新~

图数据库文章总目录:

**源码分析相关可查看github(求star~~)**: https://github.com/YYDreamer/janusgraph

下述流程高清大图地址:https://www.processon.com/view/link/5f471b2e7d9c086b9903b629

版本:JanusGraph-0.5.2

转载文章请保留以下声明:

作者:洋仔聊编程
微信公众号:匠心Java
原文地址:https://liyangyang.blog.csdn.net/

一:查询场景

1.1 图数据

使用JanusGraph官方提供的测试图诸神之图来测试,如下图:

在这里插入图片描述

具体的诸神之图的创建分析,请看《JanusGraph-官方测试图:诸神之图分析》文章

1.2 查询语句

查询语句如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
@Test
public void searchTest(){
// 获取name为hercules节点
GraphTraversal<Vertex, Vertex> herculesVertex = graph.traversal().V().has("name", "hercules");
// hercules节点战斗(battled)过12次的怪兽(monster)
GraphTraversal<Vertex, Vertex> monsterVertices = herculesVertex.outE().has(T.label, "battled").dedup().has("time", "12").inV();
// 获取monsterVertices节点对应的主人
GraphTraversal<Vertex, Vertex> plutoVertex = monsterVertices.inE("pet").outV().has("age", 4000);
if (plutoVertex.hasNext()){
Vertex next = plutoVertex.next();
// 输出主人的姓名
System.out.println(next.property("name"));
}
}

执行结果:

1
vp[name->pluto]

我们查询就是诸神之图的左下角部分,包含了

  • vertex的查找
  • edge的查找
  • property的过滤
  • signature key的过滤(time)
  • composite index的使用(name)
  • 第三方索引支持的mixed index使用(age)

二: 查询流程分析

查询流程可以大致分为三部分:组装查询语句、优化查询语句、执行算子链

预备知识

gremlin语句官网:http://kelvinlawrence.net/book/Gremlin-Graph-Guide.html

在gremlin语句中,查询语句的类型其中包含三种哦:初始语句、中间语句、最终语句(触发执行查询语句)

  • 初始语句:代表开始gremlin的语句,类似于V()、E()两种
  • 中间语句:不会触发查询语句执行的语句,类似于has()、outE()、inV()等,大部分都是中间语句
  • 最终语句:也叫作触发语句,这些语句会触发查询语句的执行! 访问图库并进行图数据查询;类似于hasNext()、toList()等语句

只有在执行到最终语句部分时,gremlin语句才会真正的执行!

2.1 组装查询语句

Janusgrahp的查询中,首先做的就是组装查询对象; 根据我们写的Gremlin语句,将gremlin语句拆分成不同的算子;不同的语句组装成对应的算子步骤step对象保存,生成一个查询执行算子step链;

在组装查询语句时,所有的查询Gremlin语句,通常都是通过.V()或者.E()开头,在这两部分中会创建一个查询对象,用于存放之后的每一个查询step

例如上述执行查询语句,当执行完成以下语句时,便是进行组装查询对象,不没有真正的去查询底层存储的数据!

1
2
3
4
5
6
// 获取name为hercules节点
GraphTraversal<Vertex, Vertex> herculesVertex = graph.traversal().V().has("name", "hercules");
// hercules节点战斗(battled)过12次的怪兽(monster)
GraphTraversal<Vertex, Vertex> monsterVertices = herculesVertex.outE().has(T.label, "battled").dedup().has("time", "12").inV();
// 获取monsterVertices节点对应的主人
GraphTraversal<Vertex, Vertex> plutoVertex = monsterVertices.inE("pet").outV().has("age", 4000);

执行完成后,查看组装后的查询对象:
在这里插入图片描述

其中包含:图实例对象、事务对象、查询步骤链等,我们看下最终的查询步骤链,在对象中steps的属性:

1
2
3
4
5
6
7
8
9
10
11
steps = {ArrayList@5271}  size = 10
0 = {GraphStep@5350} "GraphStep(vertex,[])"
1 = {HasStep@5351} "HasStep([name.eq(hercules)])"
2 = {VertexStep@5352} "VertexStep(OUT,edge)"
3 = {HasStep@5353} "HasStep([~label.eq(battled)])"
4 = {DedupGlobalStep@5354} "DedupGlobalStep"
5 = {HasStep@5355} "HasStep([time.eq(12)])"
6 = {EdgeVertexStep@5356} "EdgeVertexStep(IN)"
7 = {VertexStep@5357} "VertexStep(IN,[pet],edge)"
8 = {EdgeVertexStep@5358} "EdgeVertexStep(OUT)"
9 = {HasStep@5359} "HasStep([age.eq(4000)])"

上述的gremlin查询语句主要被分为10个算子step执行;

2.2 优化查询语句

Gremlin的查询优化中,存在由策略模式设计实现的19个执行策略类,包含:

  1. Connective Strategy:连接策略
  2. Match Predicate Strategy:匹配谓词策略
  3. Filter Ranking Strategy:过滤排名策略
  4. Inline Filter Strategy:内联过滤策略
  5. Incident To Adjacent Strategy:相邻策略事件
  6. Adjacent To Incident Strategy:邻近事件策略
  7. Early Limit Strategy:早期限制策略
  8. Count Strategy:计数策略
  9. Repeat Unroll Strategy:重复展开策略
  10. Path Retraction Strategy:路径收回策略
  11. Lazy Barrier Strategy:惰性屏障策略
  12. Adjacent Vertex Has Id Optimizer Strategy:相邻顶点有Id优化器策略
  13. Adjacent Vertex Is Optimizer Strategy:相邻顶点是优化器策略
  14. Adjacent Vertex Filter Optimizer Strategy:相邻顶点过滤器优化器策略
  15. JanusGraph Local Query Optimizer Strategy:JanusGraph局部查询优化器策略
  16. JanusGraph Step Strategy:JanusGraph步骤策略
  17. JanusGraphIo Registration Strategy:JanusGraphIo注册策略
  18. Profile Strategy:配置文件策略
  19. Standard Verification Strategy:标准验证策略

将上述的查询算子链循环执行所有的19个策略,针对不同的策略进行不同的处理;

我们主要收一下上述的Match Predicate Strategy、:

Filter Ranking Strategy

依据优先级调整算子链算子执行顺序! 采用while+for循环的方式,将所有的算子调整到对应的位置!

1
2
3
4
5
6
7
8
while (modified) {
modified = false;
final List<Step> steps = traversal.getSteps();
for (int i = 0; i < steps.size() - 1; i++) {
// do somthing
// update modified!
}
}

优先级如下,数字越大,优先级越低,执行的时机越靠后:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
if (!(step instanceof FilterStep || step instanceof OrderGlobalStep))
return 0;
else if (step instanceof IsStep || step instanceof ClassFilterStep)
rank = 1;
else if (step instanceof HasStep)
rank = 2;
else if (step instanceof WherePredicateStep && ((WherePredicateStep) step).getLocalChildren().isEmpty())
rank = 3;
else if (step instanceof TraversalFilterStep || step instanceof NotStep)
rank = 4;
else if (step instanceof WhereTraversalStep)
rank = 5;
else if (step instanceof OrStep)
rank = 6;
else if (step instanceof AndStep)
rank = 7;
else if (step instanceof WherePredicateStep) // has by()-modulation
rank = 8;
else if (step instanceof DedupGlobalStep)
rank = 9;
else if (step instanceof OrderGlobalStep)
rank = 10;

调整过后的算子链:

1
2
3
4
5
6
7
8
9
10
11
steps = {ArrayList@5271}  size = 10
0 = {GraphStep@5350} "GraphStep(vertex,[])"
1 = {HasStep@5351} "HasStep([name.eq(hercules)])"
2 = {VertexStep@5352} "VertexStep(OUT,edge)"
3 = {HasStep@5353} "HasStep([~label.eq(battled)])"
4 = {HasStep@5355} "HasStep([time.eq(12)])"
5 = {DedupGlobalStep@5354} "DedupGlobalStep"
6 = {EdgeVertexStep@5356} "EdgeVertexStep(IN)"
7 = {VertexStep@5357} "VertexStep(IN,[pet],edge)"
8 = {EdgeVertexStep@5358} "EdgeVertexStep(OUT)"
9 = {HasStep@5359} "HasStep([age.eq(4000)])"

Inline Filter Strategy

同作用域多个算子内联为一个一个算子

相同作用域下,相同算子的内联整合:

例如,下述语句的两个has会在第一部分的步骤生成两个has算子

1
has(T.label,"battled").has("time", "12")

两个has同时作用于V()在同一作用域,又是相同类型,所以在Inline Filter Strategy策略中,会将两个has内联为一个has算子

相同作用域下,不同算子的内联整合:

包含好多种情况,也是举一个例子,如果一个has算子一个vertex算子如下:

1
outE().has(label,"battled")

满足以下三个条件:

  1. has算子的前置算子为vertex算子(也就是上述out()产生的算子类型)
  2. 前置的vertex算子返回的类型时edge类型,也就是outE、inE、bothE这三种
  3. 前置的vertex算子,也就是outE、inE、bothE这三种没有指定edge label

的前提下,has算子的内容为过滤Edge的label;则可以将上述的两种组合成一个vertex算子,可以用以下语句表示:

1
outE().has(label,"battled") ==内联为==>  outE("battled")

调整过后的算子链:

1
2
3
4
5
6
7
8
9
10
steps = {ArrayList@5271}  size = 9
0 = {GraphStep@5350} "GraphStep(vertex,[])"
1 = {HasStep@5351} "HasStep([name.eq(hercules)])"
2 = {VertexStep@5463} "VertexStep(OUT,[battled],edge)"
3 = {HasStep@5355} "HasStep([time.eq(12)])"
4 = {DedupGlobalStep@5354} "DedupGlobalStep"
5 = {EdgeVertexStep@5356} "EdgeVertexStep(IN)"
6 = {VertexStep@5357} "VertexStep(IN,[pet],edge)"
7 = {EdgeVertexStep@5358} "EdgeVertexStep(OUT)"
8 = {HasStep@5359} "HasStep([age.eq(4000)])"

Incident To Adjacent Strategy

作用也是合并算子,但是合并的是vertex算子(outE、inE、bothE)和edge算子(outV、inV、bothV);

举个例子,如下语句,包含一个vertex算子(inE)和一个edge算子(outV)

1
inE("pet").outV()

这个策略的作用就是将这两个算子合成一个in("pet")算子,如下:

1
inE("pet").outV() ==合并==> in("pet")

调整后的算子链:

1
2
3
4
5
6
7
8
9
steps = {ArrayList@5271}  size = 8
0 = {GraphStep@5350} "GraphStep(vertex,[])"
1 = {HasStep@5351} "HasStep([name.eq(hercules)])"
2 = {VertexStep@5463} "VertexStep(OUT,[battled],edge)"
3 = {HasStep@5355} "HasStep([time.eq(12)])"
4 = {DedupGlobalStep@5354} "DedupGlobalStep"
5 = {EdgeVertexStep@5356} "EdgeVertexStep(IN)"
6 = {VertexStep@5514} "VertexStep(IN,[pet],vertex)"
7 = {HasStep@5359} "HasStep([age.eq(4000)])"

JanusGraph Step Strategy

获取GraphStep算子,也就是V()、E()等对应产生的算子; 将Gremlin的GraphStep算子转换为图库自身的JanusGraphStep算子对象;

JanusGraphStep算子对象中包含查询图库获取数据的lambda语句;在下一部分执行查询中通过调用get()来进行图库数据查询!

调整后的算子链:

1
2
3
4
5
6
7
8
steps = {ArrayList@5291}  size = 7
0 = {JanusGraphStep@5630} "JanusGraphStep([],[name.eq(hercules)])"
1 = {JanusGraphVertexStep@5610} "JanusGraphVertexStep([time.eq(12)])"
2 = {DedupGlobalStep@5341} "DedupGlobalStep"
3 = {EdgeVertexStep@5343} "EdgeVertexStep(IN)"
4 = {JanusGraphVertexStep@5611} "JanusGraphVertexStep(IN,[pet],vertex)"
5 = {NoOpBarrierStep@5513} "NoOpBarrierStep(2500)"
6 = {HasStep@5346} "HasStep([age.eq(4000)])"

其他

策略共19种,每一种都有自己的作用;优化算子链、优化调整index的使用、count语句的优化、repeat多度路径查询的优化等等

查询语句优化部分,对用户自定义的gremlin语句进行正确性验证优化查询过程的算子链两个作用;

最终,执行到第优化后的算子链为:

1
2
3
4
5
6
7
8
steps = {ArrayList@5271}  size = 7
0 = {JanusGraphStep@6302} "JanusGraphStep([],[name.eq(hercules)])"
1 = {JanusGraphVertexStep@6124} "JanusGraphVertexStep([time.eq(12)])"
2 = {DedupGlobalStep@5354} "DedupGlobalStep"
3 = {EdgeVertexStep@5356} "EdgeVertexStep(IN)"
4 = {JanusGraphVertexStep@6125} "JanusGraphVertexStep(IN,[pet],vertex)"
5 = {NoOpBarrierStep@5857} "NoOpBarrierStep(2500)"
6 = {HasStep@5359} "HasStep([age.eq(4000)])"

扩展:

Gremlin查询语句执行过程,把执行语句转为由多个step组成对应的算子链,经过优化策略优化调整转化为确定最终可执行算子链。

Gremlin语言执行过程:

  • [D] ecoration-应用级的迭代逻辑上迭代策略
  • [O]ptimization在ThinkPop图架构级别上高效迭代策略
  • [P]rovider optimization 从系统,语言,驱动级别优化
  • [F]inalization 对以上策略做调整确定最终执行策略
  • [V]erification:迭代策略做迭代引擎的验证
    如下图所示:
    在这里插入图片描述

2.3 执行算子链

执行算子链的触发时机在最终语句时进行触发;也就是我们示例语句中下述语句的hasNext()

1
plutoVertex.hasNext()

对于hasNext的源码伪代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
@Override
public boolean hasNext() {
if (null != this.nextEnd)
return true;
else {
try {
while (true) {
this.nextEnd = this.processNextStart();
if (null != this.nextEnd.get() && 0 != this.nextEnd.bulk())
return true;
else
this.nextEnd = null;
}
} catch (final NoSuchElementException e) {
return false;
}
}
}

对于数据执行调用get()触发lambda表达式内容;

针对不同的算子针对中间结果进行顺序遍历;

三:源码分析

源码分析已经push到github:https://github.com/YYDreamer/janusgraph

四:总结

整体流程如下:
在这里插入图片描述

作者

洋仔

发布于

2021-03-03

更新于

2021-03-03

许可协议


评论