GOpt: 图原生查询优化框架

GOpt 简介

GOpt是一款专为加速查询执行而设计的图原生查询优化器。它擅长处理将复杂图模式匹配与大规模图上的关系型操作相结合的混合场景。GOpt不感知底层存储数据，仅专注于数据之上的计算，这使得它能轻松快速地集成到其他图数据库或关系型数据库中。

核心功能

  1. 属性图建模: 自动推断并补全用户提供的模糊查询，以实现更精准的优化。

  2. 语言支持: 支持标准的Gremlin和Cypher语言，即将支持GQL。

  3. 图原生算法: 实现了新颖高效的复杂图模式匹配查询算法。

  4. 轻量级、无服务器集成：无缝集成支持多种存储格式的数据库。

system_overview

GOpt系统概述

为什么选择GOpt

  1. 高性能

    GOpt是基于多年学术研究设计和实现的，其关键技术已在知名系统会议上发表。如我们论文中记录的实验所示，GOpt在标准(LDBC)和实际(阿里巴巴)图工作负载中都优于大多数图和关系数据库。

  2. 用户友好界面

    GOpt提供针对不同用户需求的多层次SDK。它支持Cypher和Gremlin查询语言以降低使用门槛。用户提供的Cypher或Gremlin查询可以更加灵活和模糊，GOpt会根据属性图建模自动验证并补全查询信息。此外，它还提供底层API供需要深度集成的开发者使用。

  3. 无缝集成

    GOpt采用轻量级无服务器架构，通过小型JAR文件部署即可轻松与其他数据库集成。基于Calcite框架构建的GOpt充分利用了Calcite丰富的适配器生态，大幅简化了与各类数据格式的对接流程。这一优势使GOpt能够无缝兼容所有基于Calcite的主流关系型数据库。同时，GOpt内置原生图计算算法，显著提升了与图数据库原生API的兼容性。在入门指南章节中，我们演示了如何用极简代码将GOpt集成到Neo4j数据库。

快速开始

快速开始

GOpt是可嵌入且无服务器的，作为一个独立的包提供，仅占用JAR文件中几十MB的空间。它可以通过Apache Maven作为项目依赖快速集成到其他系统中。我们已经将GOpt集成到Neo4j系统中。在这里，您可以快速体验GOpt为Neo4j带来的优化效果。

部署

本地设置

我们准备了一个gopt-on-neo4j.tar.gz压缩包。您可以通过以下链接快速获取： Download GOpt for Neo4j

解压包后，您将获得以下文件：

├── bin
├── conf
├── data
├── import
│   └── movie
├── lib
│   └── gopt-all-0.0.1-SNAPSHOT.jar
├── plugins
└── queries
    ├── CBO
    ├── LSQB
    └── LDBC

基于原始的Neo4j组件，我们进行了以下修改：

  1. 已将movie CSV数据添加到import/movie目录。成功导入数据后，将在data目录中生成相应的数据库文件。

  2. 将gopt-0.0.1-SNAPSHOT.jar文件添加到lib目录中，使GOpt成为Neo4j的项目依赖项。

  3. 为基准测试添加了查询集。

您现在可以在本地机器上尝试运行Neo4j与GOpt。请注意，我们使用的Neo4j版本是4.4.9。请确保您的本地机器具备Neo4j-4.4.9所需的所有必要环境。如果您没有完整的开发环境，建议使用Docker设置。

Docker 环境设置

如果您没有完整的开发环境，我们也准备了相应的Docker环境。该Docker镜像包含了gopt-on-neo4j.tar.gz的所有内容以及所有必要的环境依赖项。您只需一条命令即可启动：

docker run -it registry.cn-hongkong.aliyuncs.com/graphscope/gopt-on-neo4j:latest bash

导入数据

使用Neo4j导入工具将您的数据加载到Neo4j数据库中。这里我们以movie数据集为例，它具有以下属性图模型：

movie_schema

电影数据模型

movie_data

电影数据集中的节点与关系

按照neo4j-admin的指引加载电影数据集，原始CSV文件已包含在gopt-on-neo4j项目的import/movie目录下。

cd gopt-on-neo4j

bin/neo4j-admin import \
    --database movie \
    --id-type=INTEGER \
    --ignore-empty-strings=true \
    --bad-tolerance=0 \
    --nodes=Person=import/movie/Person.csv \
    --nodes=Movie=import/movie/Movie.csv \
    --relationships=FOLLOWS=import/movie/Person_FOLLOWS_Person.csv \
    --relationships=ACTED_IN=import/movie/Person_ACTED_IN_Movie.csv \
    --delimiter '|'

配置

我们将GOpt配置集成到Neo4j标准配置文件conf/neo4j.conf中，如下所示：

  • graph.planner.rules: 将图关系规则注册到GOpt优化器框架中。

  • graph.planner.join.min.pattern.size: 指定激活JoinDecompositionRule的最小模式大小。需要注意的是，对于较小的模式，Extend可能比Join具有更好的执行效率。

  • graph.planner.intersect.cost.factor: 用于性能调优，数值越高优化器越倾向于采用基于连接的计划，数值越低则偏好基于扩展的计划。

除了GOpt配置外，我们将默认数据库设置为movie。

# GOpt Configuration
graph.planner.rules=FilterIntoJoinRule,FilterMatchRule,ExtendIntersectRule,JoinDecompositionRule,ExpandGetVFusionRule
graph.planner.join.min.pattern.size:3
graph.planner.intersect.cost.factor:1

# The name of the default database
dbms.default_database=movie

启动Neo4j服务

./bin/neo4j start

# wait unitl neo4j service started
...

./bin/cypher-shell

# check graph model
call apoc.meta.graph();

# check data
Match (a) Return count(a);
Match (a)-[b]->(c) Return count(b);

查询分析

要体验GOpt的优化效果，您可以运行多种类型的查询并观察详细的性能分析结果。GOpt集成了Neo4j的Profile工具来显示每个操作的预估计数。通过将这些预估与实际行数进行对比，您可以验证GOpt基数估计的准确性。

模糊模式

执行未明确定义类型约束的查询。

Profile Match (a)-[]->(b), (b)-[]->(c), (c)-[]->(a) Return a, b, c;

从Neo4j性能分析工具提供的执行说明中可以明显看出，节点a、b、c以及它们之间的关系类型都被准确推断出来。这使得GOpt优化器能够有效运作，而不会因查询中缺少类型细节而受阻，从而解决了Neo4j在缺乏此类信息时默认采用基于规则的优化(RBO)的局限性——该优化方式会优先处理已定义类型的节点。

triangle_pattern_profile

模糊模式分析结果

需要注意的重要一点是，如果数据模型中不包含查询指定的模式，GOpt可以在实际数据执行前的编译阶段通过静态分析及时提供错误提示。例如，如果GOpt的静态分析确定数据模型中Movie没有关联的出边，它将立即报错。

Profile Match (a:Movie)-[]->(b) Return a, b;
type_error_profile

带类型错误分析结果的模式

图模式匹配

查找所有方形图案。

Profile Match (a)-[]->(b), (a)-[]->(c), (d)-[]->(b), (d)-[]->(c)
Where a<>d AND b<>c
Return a, b, c, d;

采用图原生算法（即worst-case-optimal join算法）来优化复杂的图模式匹配工作负载。Neo4j执行层本身并不支持WCO实现。不过，我们仍然可以使用GOpt来优化Neo4j中Expand操作的执行顺序。对于循环模式，我们将WCO算法生成的逻辑运算符转换为Neo4j特定的物理运算符ExpandInto。

square_pattern_profile

方形模式分析结果

混合图关系

根据提供的过滤条件，优化器将图原生算法与传统的关系型规则FilterPushDown无缝集成，从而产生与query-2不同的执行顺序。

Profile Match (a)-[]->(b), (a)-[]->(c), (d)-[]->(b), (d)-[]->(c)
Where d.name = 'Kean' AND a<>d AND b<>c
Return a, b, c, d;
square_pattern_with_filter_profile

带过滤性能分析结果的方形模式

ST路径

计算两个给定顶点之间所有简单路径的数量。GraphScope针对ST路径查询提供了特定的优化。对于给定起点和终点之间的长路径，它会基于基数估计选择合适的拆分点，以减少单方向上的数据扩展。这是原生Neo4j规划器所不具备的功能。

Profile Match (a)-[:ACTED_IN*5..6]-(b)
Where a.name = 'Kean' AND b.name = 'Top Gun'
Return count(a);
st_path_profile

ST路径模式性能分析结果

安装

我们提供两个版本的GOpt JAR包，每个大小约为35MB：

  • gopt-core: 包含GOpt的核心功能，并使用GraphBuilderSDK来构建GOpt输入。

  • gopt-all: 在gopt-core的基础上，提供了额外的Cypher SDK和Gremlin SDK，允许用户直接编写Cypher或Gremlin查询来构建GOpt输入。

要在您自己的项目中试用GOpt，请下载最新版本的gopt-core或gopt-all并将其放置在src/main/resources目录中。

<dependency>
    <artifactId>gopt</artifactId>
    <groupId>com.alibaba.graphscope</groupId>
    <version>0.0.1-SNAPSHOT</version>
    <scope>system</scope>
    <systemPath>${project.basedir}/src/main/resources/gopt-core-0.0.1-SNAPSHOT.jar</systemPath>
</dependency>

<dependency>
    <artifactId>gopt</artifactId>
    <groupId>com.alibaba.graphscope</groupId>
    <version>0.0.1-SNAPSHOT</version>
    <scope>system</scope>
    <systemPath>${project.basedir}/src/main/resources/gopt-all-0.0.1-SNAPSHOT.jar</systemPath>
</dependency>

教程

在入门指南部分，我们探讨了GOpt的一些基础功能。本节将带您深入了解GOpt的高级特性，并演示如何利用这些功能来优化您的系统，包括：

  • GOpt基准测试工具：本指南详细介绍了如何使用基准测试工具来评估GOpt在处理更复杂查询和更大数据集时的性能。

  • 将GOpt集成到其他系统中: 以Neo4j为例，我们详细介绍了如何在不同层级将GOpt集成到其他系统中。

基准测试工具

我们提供了一个基准测试工具，用于在更大数据集上运行复杂模式查询。该基准测试工具包含三个组件：

  • 数据集: 我们已在构件gopt-on-neo4j中的data目录下预先准备了sf=1的LDBC数据。

  • 查询: 我们在queries目录中准备了三组查询集合，包括:

    1. CBO: 专为常用图模式设计，包括三角形、方形、路径和4-团。

    2. LSQB: 标准LSQB查询的一个子集。

    3. LDBC: 标准LDBC查询的简化版本。

  • 脚本: bin/bench.sh 脚本用于运行基准测试。

您现在可以体验我们的一键式基准测试功能。

步骤

  1. 首先，停止正在运行的服务

    bin/neo4j stop

  2. 将数据库重新配置为ldbc1，并为GOpt设置性能调优配置

    dbms.default_database=ldbc1
graph.planner.intersect.cost.factor:3

  3. 重启Neo4j服务，并确认数据已就绪

    bin/neo4j start
# 等待neo4j服务启动完成
...

./bin/cypher-shell

# 检查图模型
call apoc.meta.graph();

# 检查数据
Match (a) Return count(a);

  4. 通过传递不同的参数来体验bench.sh的各种功能。

    1. 在性能分析模式下运行CBO查询集以打印详细的性能分析结果。或者，您可以使用解释模式，该模式会返回优化后的执行计划而无需实际执行。

      ./bin/bench.sh ./queries/CBO --profile
./bin/bench.sh ./queries/CBO --explain

    2. 您可以选择其他查询集或运行queries目录下的所有查询集

      ./bin/bench.sh ./queries/LSQB --profile
./bin/bench.sh ./queries/LDBC --profile
./bin/bench.sh ./queries --profile

    3. 默认情况下，我们会跳过耗时较长的大型查询。您可以使用--all参数来运行所有查询，但由于Neo4j在单节点资源上的执行效率较低，这将花费更多时间。

      ./bin/bench.sh ./queries --profile --all

    4. 可选地，您可以通过设置--neo4j切换到Neo4j原生规划器。这使您能够分析其与GOpt的差异。请注意在切换规划器前清除查询缓存。

      # 清理查询缓存
./bin/cypher-shell 'call db.clearQueryCaches();'

./bin/bench.sh ./queries --profile --neo4j --all

GOpt的集成

关于GOpt的详细集成说明将在后续章节中提供。敬请期待更多信息。

GOpt的设计

动机

在大规模图查询场景中，显著影响性能的一项核心技术是优化器。随着图数据及其应用持续快速增长，众多配备了原生优化器的图处理系统相继问世。然而这些优化方法往往过度专注于图特定或关系型特定的处理方式。这种局限性导致其无法整体性解决同时涉及图数据和关系型数据的查询，从而造成性能欠佳。 为解决这一问题，GOpt的设计方案如下：

  1. 统一的图关系设计: 为Graph Relational开发一个统一的结构，能够表达Gremlin或Cypher查询，作为优化的初始结构。

  2. 统一优化框架: 在统一的关系优化框架内优化图关系结构。我们扩展了传统关系框架的接口，以实现高级图优化，包括高阶统计和最坏情况最优连接算法。

  3. 图特定优化: 我们还针对图模式匹配的特点进行了特定优化。例如，我们基于属性图建模扩展了图模式的类型推断，在传统优化框架中利用图同构进行剪枝，并实现了专门的图分解算法以减少优化过程中的搜索空间。

design_of_gopt

GOpt的设计

详细介绍

规则

规则在GOpt的优化框架中扮演着关键角色，能够实现高效且有效的查询转换。以下是GOpt中实现的一些关键规则概述：

ScanEarlyStopRule: 将limit操作下推到扫描节点。在扫描过程中，一旦达到指定的limit计数，扫描就会停止。

ScanExpandFusionRule: 该规则尽可能将边扩展转换为边扫描。例如，考虑以下Cypher查询：

Match (a:PERSON)-[b:KNOWS]->(c:PERSON) Return b.name;

尽管查询涉及Scan和GetV步骤，但它们的结果并未被后续的投影操作直接利用。唯一实际使用的数据是由Expand操作生成的边数据。在这种情况下，我们可以执行融合操作，将模式 (a:PERSON)-[b:KNOWS]->(c:PERSON)转换为对KNOWS边的扫描操作。需要注意的是，融合是否可行还取决于节点和边之间的标签依赖关系。如果边标签严格由三元组(src_label, edge_label, dst_label)决定，则无法执行融合。例如，考虑以下查询：

Match (a:PERSON)-[b:LIKES]->(c:COMMENT) Return b.name;

TopKPushDownRule: 该规则将topK操作下推到project节点，基于Calcite的SortProjectTransposeRule，尽可能复用原有规则。但在我们更复杂的分布式场景中，延迟执行project节点会破坏已排序的数据。为此，我们修改了SortProjectTransposeRule中的匹配逻辑。目前仅当排序字段为空时才会应用PushDown操作，这意味着只有limit会被下推到project节点。