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

  图数据库19 分钟读完 (大约2873个字)

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

大家好，我是洋仔，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

四：总结

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

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

http://coderstudy.vip/article/图解Janusgraph系列-查询图数据过程源码分析.html

作者

洋仔

发布于

2021-03-03

更新于

2021-03-03

许可协议

 

喜欢这篇文章？打赏一下作者吧

扫码关注微信公众号

分类

标签

20221
2022最新IDEA激活码1
Git1
IDEA1
IDEA正版官方稳定激活码1
IDEA激活码1
IDEA破解1
Intellij IDEA最新激活码1
JVM1
JanusGraph10
MySql1
Spring系列1
idea1
maven1
中间件1
二进制1
代理模式1
内存泄漏1
分布式1
动静态代理1
操作系统1
激活码1
算法1
线程池1
高并发1

最新文章

链接

×