累加器(Accumulators)

累加器是一种特殊的变量类型,它可以在遍历和探索图形的过程中累积有关图形的信息。 因为它是GSQL图形查询语言中非常独特且重要的特性,所以我们为它开辟了专门的章节。但更多详细的使用方法也会被整合到其他的章节中,比如有关“SELECT语句”的部分。 本章的介绍包括了以下这些定义的EBNF范式:

累加器有许多不同的类型,每个累加器提供特定的累加功能。 一个累加器可以被声明为一种类型,也可以是这两种类型的综合:全局(global)或附属于顶点(vertex-attached)。

从技术上讲,累加器是一种可变互斥变量,并在所有图形计算线程之间共享,探索指定的图形。 为了提高性能,图形处理引擎采用多线程方式运作。 针对累加器的修改是实时协调的,因此才能让累加运算符可以在所有线程上正确地(即相互排他)工作。 这个特性在ACCUM子句中尤为重要。 在遍历图形期间,所有被选中的边或顶点会被分配给一组线程。 这些线程共享了对累加器的互斥访问。

累加器的声明

所有累加器变量必须在查询开始时声明,紧跟在任何typedef之后,并位于其他任何类型的语句之前。 累加器变量的作用域覆盖整个查询。

附属于顶点的累加器(vertex-attached accumulator)以 “@”开头。 全局累加器的名称以“@@”开头。 另外,用户可以将全局累加器声明为静态。

附属于顶点的累加器

附属于顶点的累加器是一种状态可变的变量。它们在查询的整个持续时间内被附着到图中的每个顶点上,成为顶点在查询运行时的一个属性。 它们在所有查询进程中共享,并相互排斥。 用户可以使用等号(“=”)运算符为附属于顶点的累加器赋值。另外,累加运算符“+=”可用于更新累加器的状态; “+=”的具体效果取决于累加器类型。 在下面的示例中,每个顶点都有两个累加器。 对于某个给定类型的累加器,它的初始值是预定义好的,当然,用户也可以在声明中对其进行更改,例如下面的累加器@weight。 所有附属于顶点的累加器的名称都有一个前导符号“@”。

如果有一个包含10个顶点的图形,且每个顶点都有一个@neighbors和@weight累加器实例(即总共20个累加器实例)。 访问它们需要用到点运算符(“.”),例如,v.@neighbor)。 累加器运算符+=仅影响正在被引用的顶点上的累加器。 诸如v1.@neighbors +=1这样的语句只会影响v1的@neighbors累加器而不影响其他顶点的@neighbors累加器。

一般来说,用户只能在SELECT语句中的ACCUM或POST-ACCUM子句中访问或更新(通过=或+=操作)附属于顶点的累加器。唯一的例外是PRINT语句。用户也可以在PRINT语句中引用附属于顶点的累加器,因为PRINT可以访问附加到顶点集和的所有信息。

全局累加器

全局累加器是一种可变的累加器,可以在查询中访问或更新。 全局累加器的名称以双重符号“@@”开头。

全局累加器只能在SELECT语句之外使用=运算符赋值(即,不在ACCUM或POST-ACCUM子句中)。但用户可以通过累积运算符+=在查询中的任何位置访问或更新全局累加器,包括在SELECT语句内。

值得注意的是,ACCUM子句中的全局累加器的累加操作对每个进程都要执行一次。也就是说,如果FROM子句使用边引发的选择操作(edge-induced selection)(在“SELECT语句”一节中详述),则ACCUM子句将为选中的每条边执行一个进程。如果FROM子句使用顶点引发的选择操作(vertex-induced selection)(在“SELECT语句”一节中详述),则ACCUM子句将为选中的每个顶点执行一个进程。由于全局累加器在进程之间以互斥的方式共享,因此它的行为与非累加器变量的行为有着巨大的不同(请参阅“变量类型”一节以获取更多详细信息)。在以下示例中,全局累加器@@globalRelationshipCount在进程之间共享,并遍历每条worksFor边并累积数据。相反,relationshipCount却只增加了一次,这是因为进程之间不共享非累加器变量导致。每个进程都有自己独立的relationshipCount非共享副本,并将原始值增加1。 (例如,每个线程都将自己的relationshipCount从0增加到1.) 这种情况中没有累积,最终值为1。

静态全局累加器

静态全局累加器会在查询运行结束后仍然保留初始值。 要声明静态全局累加器,请在声明语句的开头包含STATIC关键字。 例如,如果一个查询每次执行,都讲将其静态全局累加器增加1,则最终,该累加器的值即等于查询运行的次数。 每个静态全局累加器都属于声明它的那个查询; 它不能在不同的查询之间共享。 其值仅在多次运行同一查询的过程中持续存在。当用户重新启动GPE时,该值将被重置为默认值。

没有命令可以删除静态全局累加器。 如果某个静态全局累加器是一个集合累加器,但我们不再需要它了,我们应将其包含的数据清除以将内存占用降到最低。

累加器的类型

以下是我们目前支持的累加器类型。 每种类型的累加器都支持一种或多种数据类型。

累加器主要有两个大类:

  • 标量累加器(Scalar Accumulator)存储一个单独的值:

    • SumAccum

    • MinAccum, MaxAccum

    • AvgAccum

    • AndAccum, OrAccum

    • BitwiseAndAccum, BitwiseOrAccum

  • 集合累加器(Collection Accumulator)存储一系列值:

    • ListAccum

    • SetAccum

    • BagAccum

    • MapAccum

    • ArrayAccum

    • HeapAccum

    • GroupByAccum

每个累加器类型的详细信息总结在下表中。 “累加操作”列说明了在执行语句accumName += newVal时如何更新累加器accumName。 下表是每个累加器类型的示例。

图Ac1:累加器类型和累加行为描述:

SumAccum类型累加器

SumAccum类型累加器计算并存储数值的累加和或字符串的串联。 SumAccum的输出是单个数字或字符串值。 SumAccum变量仅对INT,UINT,FLOAT,DOUBLE或STRING类型的值进行操作。

用户通过+=运算符更新累加器的状态。 对于INT,FLOAT和DOUBLE类型来说,+=arg执行数字加法,而对于字符串来说,+=arg的意思是将arg添加到SumAccum当前值的末尾。

MinAccum/MaxAccum类型的累加器

MinAccum和MaxAccum累加器计算并存储一系列累加值的最小值或最大值。 MinAccum或MaxAccum的输出为单个数值。MinAccum和MaxAccum变量仅对INT,UINT,FLOAT和DOUBLE,VERTEX(可选择指定顶点类型)的值进行操作。

对于MinAccum来说,+=arg命令会检查当前值是否小于arg,并存储两者中较小的一个。 MaxAccum的逻辑与之类似,区别在于它会检查并存储更大的那个,而不是的较小值。

在顶点类上运行的MinAccum和MaxAccum的操作比较特殊。 它们比较的不是顶点id,而是TigerGraph的内部id,它们可能与外部id不同。 比较内部ID要快得多,因此MinAccum/MaxAccum <VERTEX>提供了更高效的比较和选择顶点算法。 这对于需要对顶点进行编号和排序的某些图型算法很有帮助。 例如,以下查询从每个person返回一个post。 返回的顶点的id不一定是按字母表顺序排列最大的。

AvgAccum类型的累加器

AvgAccum类型的累加器计算并存储一系列数值的累加平均值。 在内部,其状态信息包括所有输入值的总和以及它累积的输入值的数量。 输出是平均值; 使用者无法访问总和值和计数值。 AvgAccum变量的数据类型未被声明; 所有AvgAccum累加器都接受INT,UINT,FLOAT和DOUBLE类型的输入。 输出始终为DOUBLE类型。

+=arg操作将AvgAccum变量更新为所有先前结果和当前参数的均值; =arg操作清除所有先前累积的值,并将其更新为arg,计数为1。

AndAccum/OrAccum类型的累加器

AndAccum和OrAccum类型的累加器计算并存储一系列布尔运算的累积结果。 AndAccum或OrAccum的输出是单个布尔值(True或False)。 AndAccum和OrAccum变量仅对布尔值起作用,该类型计算并不需要声明数据类型。

对于AndAccum,+=arg将累加器更新为当前布尔值与arg之间的AND运算结果。 OrAccum类似,只是它存储的是OR运算的结果。

BitwiseAndAccum/BitwiseOrAccum类型的累加器

BitwiseAndAccum和BitwiseOrAccum类型的累加器计算并存储一系列逐位布尔运算的累积结果,并会存储运算得到的位序列。仅INT数据类型包含BitwiseAndAccum和BitwiseOrAccum运算符。 该类型计算不需要声明数据类型。

理解和使用逐位布尔运算需要一些基础知识:假设某个整数存储在base-2中,是一个64位的由0和1组成的序列。 “逐位”表示每个位被视为一个单独的布尔值,1表示true,0表示false。 因此,每个整数等同于一个布尔值序列。 计算两个数字A和B的逐位AND运算意味着计算比特序列C,其中C的第j位(Cj)等于(Aj AND Bj)。

对于BitwiseAndAccum来说,+=arg将累加器更新为当前状态和arg的逐位AND运算结果。 BitwiseOrAccum类似,只是它给出逐位OR运算结果。

ListAccum类型的累加器

ListAccum类型的累加器维护一个有序元素集合。 ListAccum的输出是按元素添加的顺序列出的一系列值。 元素类型可以是任何基本类,元组或压缩字符串。 此外,ListAccum还可以包含ListAccum的嵌套。 ListAccums的嵌套限制为三层深度。

+=arg操作将arg附加到列表的末尾。 在这种情况下,arg可以是单个元素,也可以是另一个ListAccum。

ListAccum支持两个额外的操作:

  • @list1 + @list2创建一个新的ListAccum,其中包含@list1的元素,后跟@list2的元素。 两个ListAccums必须具有相同的数据类型。

  • @list1 * @list2(仅限STRING数据)生成一个新的字符串列表,该列表包含所有来自列表一元素和列表而元素顺序连接组合而成的字符串。

ListAccum还支持以下类函数。

SetAccum类型的累加器

SetAccum 类型的累加器维护一系列不重复的元素。 SetAccum的输出的元素列表是没有顺序的。 SetAccum实例可以包含同一种类型的值。 元素类型可以是任何基本类,元组或压缩字符串。

对于SetAccum来说,+=arg会将非重复元素或元素集合添加到该集合中。 如果元素已在集合中,则SetAccum状态保持不变。

SetAccum还可以与三个标准的集合运算符一起使用:并集(UNION),交集(INTERSECT)和集合相减(MINUS)(详见“Set和Bag表达式和运算符”一节)。

SetAccum还支持以下类函数。

修改SetAccum(mutator类型函数)的函数只能在以下条件下使用:

  • 全局累加器的Mutator函数只能在查询主体层语句中使用。

  • 附属于顶点的累加器的Mutator函数只能在POST-ACCUM子句中使用。

BagAccum类型的累加器

BagAccum类型也是一类集合,但允许包含重复的元素。 BagAccum的输出是一系列没有先后顺序的元素。 BagAccum实例可以包含的值可以是同一类型。 其中的元素类型可以是任何基本类,元组或压缩字符串。

对于BagAccum,+=arg操作会在BAG中添加一个元素或一个BAG。

BagAccum也支持+运算符:

  • @bag1 + @bag2创建一个新的BagAccum,其中包含@bag1的元素和@bag2的元素。 两个BagAccums必须具有相同的数据类型。

BagAccum还支持以下类函数。

  • 全局累加器的Mutator函数只能在查询主体层语句中使用。

  • 附属于顶点的累加器的Mutator函数只能在POST-ACCUM子句中使用。

MapAccum类型的累加器

MapAccum类型的累加器是键值对的集合。 MapAccum的输出是一组键和值的配对,其中键是唯一的。

MapAccum的键类型可以是所有的基本类,元组或压缩字符串。如果键类型是VERTEX,则只存储和显示顶点的id。

除了HeapAccum之外,MapAccum值的类型可以是任何的基本类,元组,压缩字符串或任何类型的累加器。

对于MapAccum来说,如果某个键key尚未在MapAccum中使用,则+=(key->val)操作会向集合中添加该键值元素。如果MapAccum中已包含该键key,则val会被累加到当前值,这其中的具体累加操作取决于val的数据类型。 (字符串将被连接,列表将被追加,数值将被累加,等等)

MapAccum还支持+运算符:

  • @map1 + @map2会创建一个新的MapAccum,它包含添加到@map1键值对的@map2的键值对。两个MapAccums必须具有相同的数据类型。

MapAccum还支持以下类函数。

ArrayAccum的类型的累加器

ArrayAccum类型是一个累加器数组。 数组是固定长度的元素序列,可以按位置直接访问某个元素。 ArrayAccum具有以下特点:

每个元素都是累加器,而不是基本元素或基本数据类型。 累加器可以是除了HeapAccum,MapAccum和GroupByAccum之外的所有类型。

  • ArrayAccum实例可以是多维的。 尺寸数量没有限制。

  • 可以在运行时(动态)设置大小。

  • 拥有一些运算符,用于更有效地更新整个数组。

声明ArrayAccum累加器时,实例名称后面应跟着一对括号来对应每个维度。 括号内可以包含一个整数常量来设置数组的大小,但也可以为空。 在这种情况下,必须使用reallocate函数设置大小,然后才能使用ArrayAccum。

因为ArrayAccum本身的每个元素都是一个累加器,所以运算符=,+=和+可以在两种情况中使用:累加器层和元素层。

元素层级(Element-level)的运算符

如果@A是一个长度为6的ArrayAccum累加器,那么@A [0]和@A [5]分别表示引用它的第一个和最后一个元素。 引用ArrayAccum元素类似于引用对应类型的累加器。 例如,给出以下定义:

则@@Sums [0],@@Sums [1]和@@Sums [2]各自都表示一个SumAccum <INT>,@@Lists [0]和@@Lists [1]各自都是指ListAccum <STRING>,它们支持那些个累加器和数据类型的所有操作。

累加器层的运算符

当将ArrayAccum作为一个整体时看待时,运算符=,+=和+具有特殊含义。此时的 操作会高效率地更新整个ArrayAccum累加器集。 所有ArrayAccums必须具有相同的元素类型。

ArrayAccum还支持以下类函数。

用于修改BagAccum的函数(mutator函数)只能在以下条件下使用:

  • 全局累加器的Mutator函数只能在查询主体层语句中使用。

  • 附属于顶点的累加器的Mutator函数只能在POST-ACCUM子句中使用。

HeapAccum类型的累加器

HeapAccum类型的累加器是元组的有序集合,并维持集合中元组个数不超过最大容量。 HeapAccum的输出是元组元素的有序集合。 +=arg操作按排列的顺序将元组挨个添加到集合中。 如果在应用+=运算符时HeapAccum已处于最大容量,则从HeapAccum中删除排位最后一个的元组。 对于元组的排序基于一个或多个元组字段,可选择按升序或降序排列,排序按照多个元组字段的从左到右进行。

HeapAccum的声明比大多数其他累加器更复杂,因为用户必须提供自定义元组类型,设置HeapAccum的最大容量,并说明如何对HeapAccum进行排序。 该声明的语法如下所示:

首先,HeapAccum声明必须以TYPEDEF语句开头,该语句定义元组的类型,且至少有一个字段(field_1,...,field_n)是可以被排序的数据类型。

在HeapAccum自身的声明中,关键字“HeapAccum”后面是由尖括号引用的元组类型。 随后是两个或多个参数(用括号引用)。 第一个参数是HeapAccum可以存储的最大元组数,且必须是正整数。 后续参数是元组字段的子集,用于对键的排序。键的排序按从左到右顺序进行,最左边的键是主排序键。 关键字ASC和DESC表示升序(最低值优先)或降序(最高值优先)排序。 升序是默认值。

HeapAccum还支持以下类函数。

GroupByAccum类型的累加器

GroupByAccum是复合累加器,即累加器的累加器,位于最上层。它是一个键和值都可以有多个字段的MapAccum累加器。而且,每个字段的类型都是累加器。

在上面的EBNF范式语法中, 所有type 一起构成了键集, 所有accumType一起构成了映射的值。 由于它们都是累加器,因此它们会执行分组操作。 与MapAccum一样,如果我们尝试存储一个键值对,但其中的键已经被用过了,则新值将累积到已存储的数据中。 在这种情况下,多字段值中的每个字段都有自己的累加函数。 GroupByAccum的一种理解的方式,即是每个唯一的键都是一个唯一的小组ID。

在GroupByAccum中,键类型可以是基本类,元组或压缩字符串。 这些累加器用于将小组值进行聚合。 每个累加器类型可以是除HeapAccum之外的任何类型。 每个基本类和每个累加器类型必须后跟一个别名(alias)。 下面是一个例子。

向此GroupByAccum添加新数据,数据的格式应该是(key1,key2 - > value1,value2)。

GroupByAccum还支持以下类函数。

累加器的嵌套

某些集合累加器允许嵌套。 也就是说,累加器中的元素本身也是累加器。 例如:

只有ListAccum,ArrayAccum,MapAccum和GroupByAccum类型的累加器可以包含其他类型的累加器。 但是,并非所有集合累加器的组合都是允许的。 以下为具体的限制:

  1. ListAccum: : ListAccum是唯一允许被嵌套在ListAccum中的累加器,最大深度为3

    ListAccum<ListAccum<INT>>
    ListAccum<ListAccum<ListAccum<INT>>>
    ListAccum<SetAccum<INT>> # illegal
  2. MapAccum: 可以嵌套除了 HeapAccum之外的任何累加器类型, 允许以值类型嵌套在 MapAccum内。例如,

    MapAccum<STRING, ListAccum<INT>>
    MapAccum<INT, MapAccum<INT, STRING>>
    MapAccum<VERTEX, SumAccum<INT>>
    MapAccum<STRING, SetAccum<VERTEX>>
    MapAccum<STRING, GroupByAccum<VERTEX a, MaxAccum<INT> maxs>>
    MapAccum<SetAccum<INT>, INT> # illegal
  3. GroupByAccum: 可以嵌套除了 HeapAccum之外的任何累加器类型, 允许以累加器类型嵌套在 GroupByAccum内。 例:

    GroupByAccum<INT a, STRING b, MaxAccum<INT> maxs, ListAccum<ListAccum<INT>> lists>
  4. ArrayAccum: 前面的累加器中,嵌套为可选选项;但ArrayAccum累加器的嵌套是必选项。详见 ArrayAccum 章节.

通过定义一个嵌套的ListAccum累加器来构成一个多维度的数组的操作是合法的。请特别注意下面示例中的声明语句和用于嵌套的方括号。