PER句（ベータバージョン）

はじめに

パターンマッチングは仮想マッチテーブルを生成します。ACCUM句はFOR EACHループのように動作するので、マッチテーブルの各行で1回ずつ命令文を実行します。

パターンとはグラフ内のパスのことで、マッチテーブル内の各々の行は、重複を除いて一意化した、個別のパスを表しています。しかし、パスは頂点やエッジを共有することもあります。アプリケーションによっては、パス単位での集約が望まれないものもあり、その代わりに、個別の頂点エイリアスグループ単位でACCUM句を実行させることが要求されます。

次の例で考えてみましょう。このクエリは、単純な2ホップのパターンにあるパスの数を求めています。

SumAccum<int> @@cnt;

S = SELECT t
    FROM S:s - (E1:edge1) - M:m -(E2:edge2) - T:t
    ACCUM @@cnt += 1;

ここで次のようなマッチテーブルが生成されたとします。

(s, edge1, m , edge2, t)//マッチテーブルのスキーマ
v1, e1, v3, e2, v2 //マッチ 1
v1, e3, v4, e4, v2 //マッチ 2
v5, e5, v6, e6, v7 //マッチ 3
v8, e7, v9, e8, v7 //マッチ 4

ACCUM句は、デフォルトで @@cnt += 1の文を4回、マッチテーブル内の各行で実行します。その結果は@@cnt = 4になります。

ここで、同じクエリでユーザーが

マッチテーブル内の個別のパスの終着点の数を数えたい場合はどうしたらよいでしょうか。この場合には、エイリアスのtに対して反復実行させます。
マッチテーブル内の個別の（開始、終着）ペアを数えたい場合はどうしたらよいでしょうか。この場合には、個別のペアのエイリアス(s, t)に対して反復実行させます。

このような柔軟性とACCUMの反復を細かく調整できる機能を提供するために、TigerGraph 3.0 はPER句をパターンマッチングの構文（V2）に追加しました。

構文

PER句は、SELECT文のACCUM句の始めに使える任意の句です。次の例のように、キーワードPERで始まり、次に括弧があり、その中に FROMパターン内にある個別の頂点エイリアスを入れます。

selectBlock := SELECT alias
               FROM pattern
               [sampleClause]
               [whereClause]
               [[perClause] accumClause]
               [postAccumClause]*
               [havingClause]
               [orderClause]
               [limitClause]

perClause := PER (vertex_alias_1, vertex_alias_2, ...)

例. 同じFROM句を利用した、PER句の例をいくつか示します。

S1 = SELECT s
     FROM S:s - (E1:edge1) - M:m - (E2:edge2) - T:t
     PER (s)
     ACCUM @@cnt += 1;

S2 = SELECT t
     FROM S:s - (E1:edge1) - M:m - (E2:edge2) - T:t
     PER (t)
     ACCUM @@cnt += 1;

S3 = SELECT m
     FROM S:s - (E1:edge1) - M:m - (E2:edge2) - T:t
     PER (m)
     ACCUM @@cnt += 1;

S4 = SELECT t
     FROM S:s - (E1:edge1) - M:m - (E2:edge2) - T:t
     PER (s, t)
     ACCUM @@cnt += 1;

S5 = SELECT t
     FROM S:s - (E1:edge1) - M:m - (E2:edge2) - T:t
     PER (s, m, t)
     ACCUM @@cnt += 1;

表現

PER句は、頂点のエイリアスのリストを指定します。頂点のエイリアスはマッチテーブル内の行をグループ化するのに使われ、個別のエイリアスの値、または個別のエイリアスのリストの値毎にグループが作られます。個別のグループがN個あったとすると、ACCUM句はN回、個別の頂点エイリアスとの結合毎に1回ずつ実行されます。PER句は、POST-ACCUM内の頂点エイリアスを限定するほかは、POST-ACCUM句の内容には影響しないことに注意してください。

あるパターンに s と m と t の頂点エイリアスがある場合のPER句の解釈例を次にいくつか示します。各々、マッチテーブル内のグラフ要素の結合の内容によって異なります。

PER (s) ACCUM は、個別のs頂点毎にACCUM節を1回実行せよ、という意味です。
PER (s,t) ACCUM は、個別の (s,t) のペア毎にACCUM節を1回実行せよ、という意味です。
PER (s,m,t) ACCUM は、個別の (s,t,t) のタプル毎にACCUM節を1回実行せよ、という意味です。

PER句の表現の例

//マッチテーブル
(s, edge1, m , edge2, t)//スキーマ
v1, e1, v3, e2, v2 //マッチ 1
v1, e3, v4, e4, v2 //マッチ 2
v5, e5, v6, e6, v7 //マッチ 3
v8, e7, v9, e8, v7 //マッチ 4

//v1とv5とv8があるので、3つの個別の頂点がsと結合しています
//ACCUM節は3回実行されます
S1 = SELECT s
     FROM S:s - (E1:edge1) - M:m -(E2:edge2) - T:t
     PER (s)
     ACCUM @@cnt += 1;

//v2とv7の2つの個別の頂点がtと結合しています
//ACCUM節は2回実行されます
S2 = SELECT t
     FROM S:s - (E1:edge1) - M:m -(E2:edge2) - T:t
     PER (t)
     ACCUM @@cnt += 1;

//V3とv4とv6とv9があるので、4つの個別の頂点がmと結合しています
//ACCUM節は4回実行されます
S3 = SELECT m
     FROM S:s - (E1:edge1) - M:m -(E2:edge2) - T:t
     PER (m)
     ACCUM @@cnt += 1;

//（v1、v2）と（v5、v7）と（v8、v7）の3つの個別の頂点のペアが
//（s、t）に結合しているので、ACCUM句は3回実行されます
S4 = SELECT t
     FROM S:s - (E1:edge1) - M:m -(E2:edge2) - T:t
     PER (s, t)
     ACCUM @@cnt += 1;


//（v1、v3、v2）、（v1、v4、v2）、（v5、v6、v7）、（v8、v9、v7）と4つの
//個別の頂点のグループが（s、m、t）に結合しているので、ACCUM句は4回実行されます。
S5 = SELECT t
     FROM S:s - (E1:edge1) - M:m -(E2:edge2) - T:t
     PER (s, m, t)
     ACCUM @@cnt += 1;

PER句がSELECTクエリのブロックで使われている場合には、SELECT句やACCUM句やPOST-ACCUM句が使う頂点エイリアスは、PER句に表れるエイリアスのみに限定されます。

次に規則違反の例を示します。

//セマンティックエラー SELECT tとなっていますが、tはPER句にはありません
S1 = SELECT t
     FROM S:s - (E1:edge1) - M:m -(E2:edge2) - T:t
     PER (s, m)
     ACCUM @@cnt += 1;

//セマンティックエラー ACCUM t.@cntとなっていますが、tはPER句にはありません
S2 = SELECT t
     FROM S:s - (E1:edge1) - M:m -(E2:edge2) - T:t
     PER (s, m)
     ACCUM t.@cnt += 1;

//セマンティックエラー POST-ACCUM t.@cntとなっていますが、tはPER句にはありません
S3 = SELECT s
     FROM S:s - (E1:edge1) - M:m -(E2:edge2) - T:t
     PER (s)
     ACCUM s.@cnt += 1
     POST-ACCUM t.@cnt =1;

PER句の例

例1. 投稿を好きだという人が住んでいる都市がある国の数を求める。

//例1.
USE GRAPH ldbc_snb

INTERPRET QUERY () SYNTAX v2 {
  SumAccum<int> @@cnt;

 R =   SELECT c
       FROM   Country:c -(<IS_PART_OF.<IS_LOCATED_IN.LIKES>)- Post:p
       PER    (c)
       ACCUM  @@cnt +=1;

 PRINT @@cnt;
}

//結果
Using graph 'ldbc_snb'
The query AA is dropped.
{
  "error": false,
  "message": "",
  "version": {
    "schema": 0,
    "edition": "enterprise",
    "api": "v2"
  },
  "results": [{"@@cnt": 111}]
}

例2. ある国に属する都市にいる人によって好かれている投稿の数を求める。（どの都市も国に属しているのは当然ですが、例に使うものとして捉えてください。ここで示している例は、すべて同じFROMパターンを基にしています。）

//例2.
USE GRAPH ldbc_snb

INTERPRET QUERY () SYNTAX v2 {
  SumAccum<int> @@cnt;

 R =   SELECT p
       FROM   Country:c -(<IS_PART_OF.<IS_LOCATED_IN.LIKES>)- Post:p
       PER    (p)
       ACCUM  @@cnt +=1;

 PRINT @@cnt;

//結果
Using graph 'ldbc_snb'
{
  "error": false,
  "message": "",
  "version": {
    "schema": 0,
    "edition": "enterprise",
    "api": "v2"
  },
  "results": [{"@@cnt": 70668}]
}

例3. ドミニカ共和国、アンゴラ、カンボジア（"Dominican_Republic","Angola", "Cambodia"）に含まれる国の1つひとつで、そこの住民が好きな投稿の数を求める。

//例3
USE GRAPH ldbc_snb

INTERPRET QUERY () SYNTAX v2{

 MapAccum<string, SumAccum<int>> @@postPerCountry;

 R =   SELECT p
       FROM   Country:c -(<IS_PART_OF.<IS_LOCATED_IN.LIKES>)- Post:p
       WHERE  c.name in  ("Dominican_Republic","Angola", "Cambodia")
       PER    (c, p)
       ACCUM  @@postPerCountry += (c.name -> 1);

 PRINT @@postPerCountry;
}

//結果
Using graph 'ldbc_snb'
{
  "error": false,
  "message": "",
  "version": {
    "schema": 0,
    "edition": "enterprise",
    "api": "v2"
  },
  "results": [{"@@postPerCountry": {
    "Dominican_Republic": 395,
    "Angola": 12,
    "Cambodia": 4002
  }}]
}

例4. ドミニカ共和国、アンゴラ、カンボジア（"Dominican_Republic","Angola", "Cambodia"）に含まれる国の1つひとつで、そこの住民が好きな投稿の数を求める。この例ではローカルのアキュムレータを使う。

USE GRAPH ldbc_snb

INTERPRET QUERY () SYNTAX v2{

 SumAccum<int> @postCnt;

 R =   SELECT c
       FROM   Country:c -(<IS_PART_OF.<IS_LOCATED_IN.LIKES>)- Post:p
       WHERE  c.name in  ("Dominican_Republic","Angola", "Cambodia")
       PER    (c, p) //(country, post) 毎に、c.@postCntに１を加算
       ACCUM  c.@postCnt += 1;

 PRINT R;
}

//結果
Using graph 'ldbc_snb'
{
  "error": false,
  "message": "",
  "version": {
    "schema": 0,
    "edition": "enterprise",
    "api": "v2"
  },
  "results": [{"R": [
    {
      "v_id": "2",
      "attributes": {
        "@postCnt": 12,
        "name": "Angola",
        "id": 2,
        "url": "http://dbpedia.org/resource/Angola"
      },
      "v_type": "Country"
    },
    {
      "v_id": "67",
      "attributes": {
        "@postCnt": 4002,
        "name": "Cambodia",
        "id": 67,
        "url": "http://dbpedia.org/resource/Cambodia"
      },
      "v_type": "Country"
    },
    {
      "v_id": "11",
      "attributes": {
        "@postCnt": 395,
        "name": "Dominican_Republic",
        "id": 11,
        "url": "http://dbpedia.org/resource/Dominican_Republic"
      },
      "v_type": "Country"
    }
  ]}]
}

パフォーマンスとベストプラクティス

PER句は、ACCUM句の表現のコントロールに役立つばかりでなく、クエリの実行が最適化できるので、パターンマッチクエリのパフォーマンスを大幅に引き上げます。

最大のパフォーマンスを得るには、次のガイドラインに従って効率のよいクエリを作成することをお勧めします。

可能であればPER（ターゲット）を使う

ターゲット毎の処理は、ソース毎の処理よりも一般的に速くなります。次の例では、クエリq2の方がクエリq1よりも速くなります。q2のFROMパターンはq1のFROMパターンを反転させたものであることが唯一の相違点です。

USE GRAPH ldbc_snb

# 次はPER (src)、ソース毎の実行になるので推奨できません
CREATE QUERY q1 () SYNTAX v2 {

  SumAccum<int> @@cnt ;

  T = SELECT c
      FROM Comment:c - (<LIKES) - Person:ps - (IS_LOCATED_IN>) - City:city
      WHERE year(c.creationDate) >= 2006
      PER (c)
      ACCUM @@cnt += 1;

  PRINT @@cnt;
}

# 次はPER (tgt)、ターゲット毎の実行になるのでお勧めです
CREATE QUERY q2 () SYNTAX v2 {

  SumAccum<int> @@cnt ;

  T = SELECT c
      FROM City:city - (<IS_LOCATED_IN) - Person:ps - (LIKES>) - Comment:c
      WHERE year(c.creationDate) >= 2006
      PER (c)
      ACCUM @@cnt += 1;

  PRINT @@cnt;
}

最小と思われる頂点セットが左にくるようにパターンを作る

マッチテーブルは、パターンを左から右に横断して構築されます。いらないものは早めに取り除くという基本方針に従って、小さめのカーディナリティのあるセットを左側にもってくるようにクエリを記述してください。この方法を使えば、最少のマッチ候補数が生成されるので、クエリの計算負荷が軽減できます。次の例では、個別のタグの数が人の数より少ない場合、クエリq4がクエリq3より速くなります。

USE GRAPH ldbc_snb

# カーディナリティが大きい頂点タイプ（Person）からパターンが始まっていて
# カーディナリティが小さい頂点タイプ（Tag）で終わるので推奨できません
CREATE QUERY q3 () SYNTAX v2 {

  SumAccum<int> @cnt;

  V = SELECT s
      FROM Person:s- (LIKES>)-Post:p - (<CONTAINER_OF)-:f - (HAS_TAG>) - :t
      PER (s)
      ACCUM s.@cnt += 1;

  PRINT V.size();
}

# カーディナリティが小さい方の (Tag) から始まって、PER がターゲットに対して指定されているのでお勧めです
CREATE QUERY q4 () SYNTAX v2 {

  SumAccum<int> @cnt;

  V = SELECT s
      FROM Tag:t-(<HAS_TAG)-Forum:f -(CONTAINER_OF>)-Post:p  - (<LIKES)- Person:s
      PER (s)
      ACCUM s.@cnt += 1;

  PRINT V.size();
}

タイプ情報をすべて指定する

タイプ情報をすべて指定するとパフォーマンスが向上されます。例えば、クエリq6とクエリq5は理論上同一なのに、q6の方が速くなります。Forum（サイト）はPOST（投稿）のCONTAINER_OF（コンテナ）なので、q5で指定する必要はありません。しかし、q6ではForumを明示していることがパフォーマンスを加速させます。

USE GRAPH ldbc_snb

#Forumは :f の前にあえて入れません
CREATE QUERY q5 () SYNTAX v2 {

  SumAccum<int> @@person_cnt;

  V = SELECT s
      FROM Person:s- (LIKES>)-Post:p - (<CONTAINER_OF)-:f - (HAS_TAG>) - :t
      PER (s)
      ACCUM @@person_cnt += 1;

  PRINT @@person_cnt;
}


#Forumをタイプの情報として挿入する、この方法をお勧めします
CREATE QUERY q6 () SYNTAX v2 {

  SumAccum<int> @@person_cnt;

  V = SELECT s
      FROM Person:s- (LIKES>)-Post:p - (<CONTAINER_OF)-Forum:f - (HAS_TAG>) - :t
      PER (s)
      ACCUM @@person_cnt += 1;

  PRINT @@person_cnt;
}

LDBCベンチマークのクエリ

すべてのLDBC-SNBのクエリを、PER句節と平面正則のパスパターンを使って解釈したものをgithub https://github.com/tigergraph/ecosys/tree/ldbc/ldbc_benchmark/tigergraph/queries_linear/queries　に掲載しました。ほとんどのクエリは関数としてインストールされています。サンプルのパラメーターは https://github.com/tigergraph/ecosys/tree/ldbc/ldbc_benchmark/tigergraph/queries/seeds　にあります。