TigerGraph累加器 与 SQL中GROUP BY 的比较

TigerGraph累加器 与 SQL中GROUP BY 的比较

对于生产环境的图数据库选型,图查询语言一直是用户首要考虑的问题之一。

一些考虑因素包括但不限于易用性、表达性和与 ISO 标准的一致性。 当谈到将图数据库投入生产时,我们的经验表明,足够的表达能力是首位的。

在之前的博客中,我们剖析了累加器的基本语义和使用模式。 我们得到了很多反馈。 最常见的问题之一是,累加器是否可以实现在 SQL 中 GROUP BY聚合操作?

答案是可以的,不仅如此,通过累加器甚至可以实现一些SQL难以实现的操作! 累加器可以以简洁和清晰的形式表达特定类型,实现高性能查询。 对于这类查询,按照 SQL 的GROUP BY聚合看起来很麻烦,并且会导致浪费的计算。

在本文中,我们将继续讨论累加器,通过GSQL的聚合语法模拟不同的 SQL GROUP BY 语句。 这个练习揭示了通过聚合使用累加器优于传统 SQL GROUP 的好处。

模拟 SQL 的GROUP BY 聚合

累加器在GSQL的Select-from-where 查询块中的 Accum 子句部分进行值的聚合计算。 结果表明,这种查询块结构可以表示所有常规 SQL 的GROUP BY聚合。

对于 SQL 的5个内置聚合函数(MIN / MAX / SUM / COUNT / AVG) ,GSQL 对应了5个不同的累加器类型(MINAccum / MAXAccum / SUMAccum / SUMAccum / AVGAccum)。 这里我们展示一个简单的示例,它使用 GSQL 内置的 累加器实现 SQL 的 GROUP BY聚合。

例一:

给定一个 Employee 表,其中每一行存储雇员的姓名、性别和当前薪水,我们希望找出每个性别的最低、最高、总和平均薪水是多少,以及每个性别的雇员总数是多少? 在 SQL 中,这个查询可以通过一个查询块表示,如下所示。

SELECT gender,
MIN(salary) AS MIN_salary,
MAX(salary) AS MAX_salary,
AVG(salary) AS AVG_salary,
SUM(salary) AS tot_salary,
COUNT(*) AS tot_COUNT
FROM Employee
GROUP BY gender

如下所示:在 GSQL,我们可以通过多个累加器来实现相同的结果。

GROUP BYAccum
MINAccum MIN_salary,
MAXAccum MAX_salary,
AVGAccum AVG_salary,
SUMAccum tot_salary,
SUMAccum tot_COUNT> @@gender_aggs;

R = SELECT e


FROM Employee:e


Accum @@gender_aggs += (e.gender->e.salary, e.salary, e.salary, e.salary, 1);

在上面的 GSQL 查询中,我们声明一个名为@@ gender aggs 的 GROUP BYAccum全局累加器。 它将性别作为GROUP BY的KEY,其余5个累加器作为聚合器,以聚合每个组的VALUE值。 对于雇员这个顶点类型,我们绑定一个变量“ e” ,Accum 子句将并行地将KEY e.gender 和 VALUE (e.salary,e.salary,e.salary,e.salary,1)发送到 全局累加器@@gender_aggs中。

SQL 和 GSQL 查询都可以通过单遍算法实现,其中我们浏览一次员工表,并计算每个聚合器的聚合结果。

通常,常规的 SQL GROUP-by 聚合可以指定为

SELECT K1,K2,...,Kn, agg1(A1),agg2(A2),agg3(A3)..., aggm(Am)
FROM ...
GROUP BY K1,K2,...,Kn

以 Ki 作为按键组,以 Aj 作为聚合属性。 在 GSQL 中,这是通过 Accum 子句实现的

Accum A += (K1,K2,...,Kn → A1,A2,...,Am)

其中 A 被声明为一个包含K1,K2,… ,Kn,Acc1,Acc2,… Accm的 GROUP BYAccum类型的累加器。

模拟 SQL 的高级聚合

累加器同样可以表示多个 GROUP BY 聚合,例如 SQL GROUP BY 子句的 CUBE、 ROLLUP 和 GROUPING SET 扩展。

它们各自计算分组属性的几个子集的聚合,外部统一每个分组的结果。 其中 GROUPING SETS 扩展是最灵活的扩展,允许对分组属性子集进行目标选择。

例二

例如,对于一个定义了三个分组集(k1,k2,k3)的GROUPBY子句,GROUPING SETS((k1,k2),k3)在 GSQL 中可以按照以下格式实现

Accum A += (k1,k2,null → a1,a2,a3),
A += (null,null,k3 → a1,a2,a3)

类似地,CUBE (k1,k2,k3)扩展可以用8个 累加器来描述(对应{ k1,k2,k3}的8个子集)和 ROLLUP (k1,k2,k3)扩展可以用4个累加器来描述(分别对应{ k1,k2,k3} ,{ k1,k2} ,{ k1} ,{ k1} ,{{})。

TigerGraph 是当前 SQL/PGQ 和 GQL 标准草案的积极参与者和贡献者,我们调查了市场上其他流行的图查询语言,现有的图查询语言都不支持GROUP BY语法扩展(CUBE / ROLLUP / GROUPING SET)。 相比之下,如上面的示例所示,GSQL 的累加器便于直接添加 CUBE、 ROLLUP 和 GROUPING SET 关键字,将其作为语法糖来保证预期的单次遍历得到结果。

SQL 聚合中 CUBE / ROLLUP / GROUPING SET 的缺陷

CUBE、 ROLLUP 和 GROUPING SET 本质上是方便的语法糖,可以通过属性指定组的子集,我们可以在这些属性上计算所有的聚合结果。 这些GROUP BY语法扩展的一个缺点是,它们不允许 SQL 用户将 SELECT 子句中的不同聚合指定为不同的分组集。  也就是说,出现在 SELECT 子句上的任何聚合函数将会作用于高级GROUP BY语法糖产生的每个分组集。

当用户希望将特定的聚合器绑定到不同的分组集时,这将导致浪费计算。

示例3每个GROUPING SET的造成的聚合浪费

假设我们希望分别对GROUPING SET(K1)、(K2)、(K3)进行求和、最小值 和 平均值 聚合计算,那么 GROUPING SET 语义将强制计算每个分组集合的所有三个聚合(其中两个是不需要的)。 在 GSQL 形式中,它表示为

Accum A1 += (k1 → a1, a2, a3), A2 += (k2 → a1, a2, a3),A3 += (k3 → a1, a2,a3)

相比之下,在 GSQL 中,我们可以为每个分组集合 Ki 设置一个单独的累加器 Ai,每个 Ai 只执行所需的聚合:

Accum A1 +=(k1 → a1), A2 += (k2 → a2), A3 += (k3 → a3)

很明显,聚合器的精细绑定避免了对 k1进行 a1、 a3计算 ,对k2进行 a1、 a3计算,以及对k3进行 a1、 a2计算,这是一种浪费的工作。

量化聚合浪费

经我方实验报告显示,我们量化了基于 GSQL 累加器的聚合对比SQL聚合所节省的资源消耗。

在遍历图的过程中,浪费在不需要的聚合计算中的开销会造成可测量的性能损失。 我们通过一个实验来说明这一点,该实验比较了两种类型的多聚合的性能:

  • 基于累加器的
  • SQL GROUPING SET (这是 SQL 选项中最有效的一个,因为它避免了计算不需要的分组集——但是,像其他所有选项一样,它不能避免计算每个分组集合不需要的聚合)。

数据: 为了使用可伸缩的图形,我们采用了 LDBC SNB 基准数据,使用的数据大小从1GB 到1TB 不等。

查询:我们调整了 SNB 提供的查询场景来计算多个聚合。 我们在这里列举其中一个查询(它的衡量方式可用于其他查询)。 这个查询列举了2010年至2012年间所有发布的信息中,

人们及他们所居住的城市和他们喜欢的评论(人、城市和评论被建模为顶点,之间的关系被建模成边)

它计算三个GROUP SET,每个集合都有自己的聚合:

1、每(评论出版年) ,它计算

  • 最近的20条评论,优先取评论最长的评论,
  • 最早的20条评论,优先最长的评论,
  • 20条最长的评论,优先最新的评论,
  • 20条最短的评论,优先最新的评论,
  • 最年长作者的十大评论,优先最长的
  • 最年轻作者的十大评论,优先最长的。

2、每(作者的城市,浏览器类型,出版年份,月份,评论长度) ,计算评论次数

3、每(作者的城市,性别,浏览器类型,出版年份和月份) ,计算平均评论长度

我们使用 GSQL 表达查询,遵循两种风格:

Q_gs 使用累加器模拟 SQL GROUPING SET 聚合,如示例3所示,满足 GROUPING SET 语义前提下,G_qs 为三个分组集中的每一个计算所有8个聚合。 这个查询发布在 GitHub 上。 (注意,这个查询需要 TigerGraph 3.0特性,其中 HeapAccum 可以在 GROUP BYAccum 中使用)。

使用适当的累加器,Q_acc 只为每个分组集计算所需的聚合,如示例3所示。 这个查询亦发布在 GitHub 上。

我们测量的内容: 我们测量了由 SNB 生成器生成的图的 Q_gs 和 Q_acc 的运行时间,在标度因子 SF-1(1GB)、 SF-10(10GB)、 SF-100(100GB)和 SF-1000(1TB)上。 对于每个图形,我们运行每个查询5次,记录运行时间的中位数。

结果:我们观察了以下查询的运行时间(全部以秒表示) ,结果显示,在图大小从1GB 到1TB 不等的情况下,

与 SQL 风格的聚合相比,基于累加器的聚合最多可以提高3倍的计算效率。

平台: 我们在一个类型为 r4.8 xlarge 的 Amazon EC2实例上按比例因子1、10和100加载图表(并运行查询)。 对于比例因子1000,我们使用了微软 Azure 3个节点的集群,每个节点类型为 E64a v4(图存储和查询执行都是基于 TigerGraph 3.0引擎做了分布式处理,这意味着用户查询不需要编辑)。

总结

我们对GSQL的累加器 和 SQL 风格的聚合做了详尽的对比。 ,累加器不仅涵盖了 SQL 风格聚合的表达能力,同时在简洁性和避免浪费性方面具备一定的优势。

我们设计累加器的目的是使图分析查询更容易编写。 另一方面,它为针对特定类型的聚合查询编写单遍聚合查询提供了简洁性和灵活性,而 SQL GROUP BY聚合语法则不能轻松实现。 如本研究所示,SQL 用户不能轻松地将单个聚合从 SELECT 子句绑定到一个GROUP SET上,而累加器是可以做到的。

在 GSQL 早期的设计(2015年夏天)中,使我们关注和兴奋的是利用运行时属性(局部累加器)和全局状态变量(全局累加器)修饰图拓扑,降低了编写图分析查询的复杂度。 累加器是通过修饰顶点和查询块之间共享计算状态的图来实现强大和高效的组合结果的一种手段。 有了这些修饰,图形分析变得简单而有趣。 你同意吗?

欢迎到TigerGraph技术社区与我们参与讨论: https://community.TigerGraph.com.cn/