日本データベース学会和文論文誌
一般論文

Vol. 20-J, Article No. 12, 2022 年 3 月

並列プリミティブを活用した GPU 上

ングが容易であることから，クラスタ上ではなくマルチコア CPU

での SQL/Row Pattern Recognition のためのフレームワーク Mars [7] が存在する．また，MapReduce上で実装した Phoenix [10] や，MapReduce を GPU 上で実装するを行うためのフレームワークとして Apache Hadoop [6] も存在

処理手法

する．
また，大規模データ処理の技術としてメニーコアプロセッ

大原 翼 1

サである GPU を汎用計算に利用する GPGPU(General-purpose

宮崎 純 2Computing on Graphics Processing Units) が存在する．本来，GPUは膨大な単純処理を必要とする画像処理に用いられていたプロ本研究では，並列プリミティブを始めとした既に実装されていセッサであるが，その並列計算能力の高さから GPU を汎用計算

る GPU の技術を組み合わせ，SQL/Row Pattern Recognition の高に活用する研究が行われてきた．GPU を汎用計算に活用する研

速な問い合わせ処理を実現する処理手法を提案する．評価実験で究として，並列プリミティブが存在する．並列プリミティブはは，PostgreSQL を用いた SQL/RPR の実装と提案手法を比較しソートや配列の総和を求めるリダクションといった汎用計算をた．評価実験の結果から並列プリミティブなどの技術を組み合わせることで，GPU 上で SQL/RPP の処理を効率的に行うことが可GPU 上で実装したものである．並列プリミティブが実現している計算は原始的ではあるが，GPU のハードウェアアーキテクチャ

能であることが判明した．また，実行時間において提案手法は比に最適な形で処理されるよう最適化されている．

較手法と比べ約 7.1–22.6 倍の性能向上を達成した．

現在，SQL/RPR を実装しているプラットフォームとして Oracle

Database 12c [8] などが存在するが，SQL/RPR の処理において上

1

はじめに

記 GPU の技術を活用している手法はまだ存在していない．
本研究では，並列プリミティブを始めとした GPU の技術を

近年，情報通信技術，センサ技術の発展に伴い，日々大量の組み合わせ，処理の高速化，最適化を目的とした GPU 上でのデータが生成されている．こうしたデータの中には，データの連SQL/RPR の処理手法を提案する．特に先述した SQL/RPR の続性が重要な意味を持つシーケンスデータが多く含まれている．

四つの主な処理を GPU 上で実装する．評価実験では，まず比シーケンスデータは，時系列など順序に従い並んでいるデータの較手法として PostgreSQL 上で SQL/RPR を実装する．そしてことである．例えば，“株価チャート” やコンピュータシステムに

SQL/RPR のユースケースのクエリを用い提案手法と比較手法を対する “アクセスログ” がシーケンスデータとして挙げられる．

比較することで性能を評価する．

このシーケンスデータに対して，ユーザが指定した特定のパターンが含まれるかどうかを検出する技術として行パターンマッ

2

関連研究

2.1

並列プリミティブ

チングが存在する．例えば，“株価チャート” に対し，「価格が一度下がり始め，その後価格が上昇した瞬間」を抽出したい場合，

並列プリミティブはソートやリダクションといった汎用計算を

行パータンマッチングを行うことで抽出することができる．このGPU 上で実装したものである．この並列プリミティブを実装しようにシーケンスデータに対する行パターンマッチングという技

たライブラリとして現在，ModernGPU [2] や CUDPP [4] などが術は非常に有効であり，社会においても重要なものである．

知られている．本研究で用いた並列プリミティブの一部について

データベースに蓄積されたシーケンスデータに対する行パター

以下に述べる．

ンマッチングは，SQL/RPR (Row Pattern Recognition) [1] として

SQL:2016 において標準化されている．SQL/RPR の主な処理とhashtable

しては次の四つが挙げられる．(1) 処理対象データのグループ化，

この並列プリミティブはハッッシュテーブルを GPU 上で(2) 各グループ毎にユーザが指定した順序に基づき並び替える，

実現したものである．GPU 上のハッシュテーブルに key と(3) 抽出したいパターンを正規表現を用い定義する，(4) 各グルー

value のペアを挿入し，挿入時 key はハッシュ関数によってプ毎にパターンマッチングを行う．この行パターンマッチングはハッシュ化される．ある key に対し複数の value を格納する

単純に実装した場合，その処理には多くの時間がかかる．そのたことも可能であり，例えば value を取り出す際 key1 を指定

め行パターンマッチングを効率的に，また高速に処理する方法がすると key1 のペアに対応する全ての value を出力する．

求められている．

CUDPP の hashtable のハッシュ化は (1) で表される式により

一方，シーケンスデータをはじめとする大規模なデータを処理計算される．

する技術として MapReduce [5] が存在する．MapReduce は分割

ハッシュ値 = ((random 定数 1^key)

された大量のデータをクラスタで分散処理するためのプログラミ+ random 定数 2) % 素数定数

ングモデルおよびフレームワークのことである．そのプログラミ(1)

ここで，異なる値の二つの key から生成したハッシュ値が同1 非会員

じ値になることをハッシュ衝突と呼ぶ．本研究では，key の東京工業大学 情報理工学院

ohara@lsc.c.titech.ac.jp
2 正会員

種類数とハッシュ値の種類数を比較しハッシュ衝突が発生し東京工業大学 情報理工学院

たか確認し，ハッシュ衝突が発生した場合ランダム定数 1 お

miyazaki@c.titech.ac.jp

1

日本データベース学会和文論文誌
一般論文

Vol. 20-J, Article No. 12, 2022 年 3 月

よび 2 を変更し再度ハッシュテーブルを構築する処理を例外処理として追加した．
segmented sort

この並列プリミティブは配列を複数のセグメントに区切り各セグメント内でソートを独立に行う．入力にはセグメント毎にソートを行いたい配列とセグメント間隔を定義する配列の二つである．
2.2

PG-Strom

PG-Strom [9] は PostgreSQL 向けに設計された拡張モジュール
であり，GPU を利用することで大規模なデータセットに対する集計・解析処理やバッチ処理向けの SQL ワークロードを高速化することができる．PG-Strom は，SQL 命令から自動的に GPU
プログラムを生成するコードジェネレータと，SQL ワークロード
を GPU 上で非同期かつ並列に実行する実行エンジンからなる．
また，GPU 処理にアドバンテージがある場合には PostgreSQL 標
準の実装を置き換えることで，ユーザやアプリケーションからは透過的に動作する．
2.3

図 1 データベース例

Spark SQL 上での SQL/RPR の実現

中挾ら [11] はデータベースなどに格納されたシーケンスデータ
に対する行パターンマッチングの処理コストを削減する手法を提案した．処理コストを削減する手法として Sequence Filtering と

Row Filtering を提案した．Sequence Filtering は PARTITION BY
句によりグループ分けされたのち，DEFINE 句において PREV( )や NEXT( ) といった行パターン変数を使用しないマッピング条
件によりマッピングされる行が一行もないグループは行パターン
マッチングの対象外とする手法である．Row Filtering は DEFINE
句における行パターン変数のマッピング条件によりマッピングされた行とその前後数行だけを残し，その以外の行はフィルタリン
グする．これにより行パターンマッチングの対象となる行数が削減され，処理コストが削減される．評価実験では，SQL/RPR を

PostgreSQL と Spark に実装し，提案手法が行パターンマッチン
グの処理コストを削減したことを示した．

3

SQL/RPR の機能
本節では，SQL:2016 において標準化されている SQL/RPR の機能について述べる．図 1 にデータベースの例を示す．データ
図 2 SQL/RPR のクエリ例

ベースは，item(取引された商品のカテゴリ)，tradedate(商品が取引された年月日)，price(商品の取引価格) の三つのカラムを保持している．図 2 は図 1 のデータベースに対し SQL/RPR のクエリ同士をグループにする．

を発行した例を示している．図 2 のクエリでは，取引価格が一回• ORDER BY 句: PARTITION BY 句でグループ分けされたグ
ループ毎に ORDER BY 句で指定したカラムに基づきソート

以上下がり続け，その後取引価格が一回以上上がり続けるパターン，いわゆる V 字型のパターンが抽出される．

する．

SQL/RPR の機能を用いるためには MATCH_RECOGNIZE 句• MEASURES 句: 結果出力テーブルのカラムとなる行パターを使用する．MATCH_RECOGNIZE 句内では，PARTITION BY

ン測定列を定義する．

句，ORDER BY 句，MEASURES 句，ONE ROW PER MATCH• ONE ROW PER MATCH(又は，ALL ROWS PER MATCH):

又は，ALL ROWS PER MATCH，AFTER MATCH SKIP 句，抽出したパターン毎に結果を 1 行に集約した形で (又は，パ

PATTERN 句，SUBSET 句，DEFINE 句を用いてパターンの抽出ターンとして抽出された行を全て) 出力する．

を行う．それぞれの句についてその機能を述べる．

• AFTER MATCH SKIP 句: 空でないパターンの抽出に成功し• PARTITION BY 句: 指定したカラム名の値が同じレコード

た後，次のパターンマッチングを再開する場所 (行の位置) を2

日本データベース学会和文論文誌
一般論文

Vol. 20-J, Article No. 12, 2022 年 3 月

指定する．

CPU

• PATTERN 句 : 正規表現を用い抽出したいパターンを定義す

GPU
Partition&Sort

る，正規表現には行パターン変数と{+，＊}などの量指定子

...

を用いる．
DB/CPU• SUBSET 句: 行パターン変数の集合リストを定義する．

group1/GPU

DB/GPU

データサイズはGPU上のメモリ
内で全て処理できる範囲内• DEFINE 句: 行に対しどの行パターン変数をマッピングする

group2/GPU

group3/GPU

⾏パターン変数を暫定Mapping

かの条件を定義する，行パターン変数のマッピング条件にAFTER MATCH句に従い
Pattern Matching

は，PREV( )，NEXT( ) といった 1 レコード前や後を指定す抽出したオフセットとDB内のデータを照らし合せパータンを出力る関数，AVG( )，MAX( )，COUNT( ) といった集約関数な

Patternどを用いることができる．

...

＋
group1/GPU

group2/GPU

group3/GPU

Matchingしたパターンのオフセットを抽出

提案手法

4

本節では，GPU を用い SQL/RPR の高速な問い合わせ処理を実現する手法について提案する．特に SQL/RPR の主な処理である(p1) 処理対象データのグループ化，(p2) 各グループ毎にユーザが指定した順序に基づき並び替える，(p3) 抽出したいパターンを正

図3

提案手法のワークフロー

⼊力：

出力：

規表現を用い定義する，(p4) 各グループ毎にパターンマッチングを行う，の四つ処理を GPU 上で実行するための手法について述べる．提案手法のワークフローを図 3 に示す．提案手法のワークフローは次の通りである．CPU 上でデータベースに格納されている処理対象データを GPU 上に転送し，そのデータをパーティションする．その後，パーティションされた各データグループ
毎にユーザが指定した順序に従いソートする．各データグルー
プの各行に行パターン変数を DEFINE 句に基づき暫定的にマッ
ピング (以下，暫定マッピングと呼ぶ) する．ユーザが指定した

AFTER MATCH SKIP 句のオプションに従い，各データグルー
プ毎に並列でパターンマッチングを行う．このパターンマッチン
グによりパターンにマッチした “連続している行” のオフセットを取得する．そのオフセットとデータベースを照らし合わせマッチしたパターンを CPU 上に表示する．

GPU 上に転送された処理対象データはデータベースのカラム毎に配列として保持する．ここでは，CPU 上のデータベースで
図 4 データベースのパーティションの処理例の id を保持する配列を ID 配列と呼ぶことにする．
また，本研究では，処理対象のデータサイズは GPU 上のメモ
リ内で全て処理できる範囲内であるとする．
4.1

データベースのパーティション

ID 配列 = (group1_1,group1_2,...,

SQL/RPR における PARTITION BY 句の機能に相当する GPU

group2_1,group2_2,...,group3_1,group3_2,...)(2)

上での処理について述べる．データベースのパーティションをGPU 上で実行するために，ハッシュテーブルを用いたパーティ

二つ目の配列は，式 (3) で表される通り一つ目の配列における各ションを行う．データベースのパーティションはユーザが指定

グループの先頭要素の配列のインデックスを表したものである．

したカラム名 (以下，パーティションカラムと呼ぶ．) の値が同

しかし先頭グループの先頭要素のインデックスは出力されない．

じ列をグループとしてまとめる．パーティションを行うためにこの配列を以下 SegHead 配列と呼ぶことにする．

パーティションカラムを保持した配列と ID 配列の二つを用いる．
パーティションカラムの値を key，CPU 上のデータベースにおSegHead 配列 = (group2_1 の ID 配列における index,

ける id を value としハッシュテーブルに格納する．並列プリミgroup3_1 の ID 配列における index,...)

ティブである CUDPP の hashtable を用いることでパーティショ(3)

データベースのパーティションの処理例を図 4 に示す．図 4 でンカラムの値毎にグループ分けを行う．CUDPP の hashtable はは，パーティションカラムを item(取引された商品のカテゴリ) と二つの配列を出力する．一つ目の配列は，式 (2) で表される通りしている．

まとめられたグループが連続で並んだものを表している．

CUDPP の hashtable により，グループ毎に並んだ ID 配列と3

日本データベース学会和文論文誌
一般論文

Vol. 20-J, Article No. 12, 2022 年 3 月

SegHead 配列を出力し，データベースのパーティション処理が完
了する．
4.2

グループ毎のデータ並び替え

SQL/RPR における ORDER BY 句の機能に相当する GPU 上

図 5 クエリのユースケース 1での処理について述べる．パーティションされた各データグルー
プをユーザが指定したカラム名 (以下，ソートカラムと呼ぶ．) に従った並び替えは，ソートカラムを保持する配列と SegHead 配列，さらに 4.1 節で出力されたグループ毎に並んだ ID 配列の三つを用い処理を行う．並び替えは各データグループ内でそれぞれ独立に行われる必要がある．そのため並列プリミティブである

図 6 クエリのユースケース 2

ModernGPU の segmented sort を用いる．segmented sort はセグ
メント毎にソートを行いたい配列 A とセグメント間隔を定義す
る配列 B を入力に取り，各セグメント内でソートを行った配列

A を結果として出力する．また，配列 A のインデックスも同時にセグメント毎にソートされ結果として出力される．
図 7 クエリのユースケース 3

本手法では，入力の配列 A にソートカラムを保持する配列，配列 B に SegHead 配列を選択する．これによりソートカラムを保持する配列がセグメント毎にソートされる．またソートカラムを保持する配列のインデックスがセグメント毎にソートされた配列も出力され，この配列に従い 4.1 節で出力されたグループ毎に並んだ ID 配列を並び替える．これによりグループ毎に並び，かつグループ内がソート済みである ID 配列が出力され，グループ毎

図 8 クエリのユースケース 4のデータ並び替え処理が完了する．
4.3

正規表現を用いた抽出パターンの定義

SQL/RPR における DEFINE 句の機能に相当する GPU 上での必要がある．データグループ間をまたぐ暫定マッピングを防ぐた処理について述べる．SQL/RPR の内部処理では，一番最初の行

めに 4.2 節で出力された ID 配列と 4.1 節で出力された SegHead

から順に (1)DEFINE 句に基づく行パターン変数の暫定マッピン

配列を用い，各行並列にかつ各グループ独立に行パターン変数のグ，(2) この時点でパターンにマッチする可能性があるか確認，

暫定マッピングを行う．

(3) パターンにマッチした場合暫定マッピングされた行パターン

ここで，ユースケース 3，4 において用いられている関数 First( )変数を正式にマッピングする，あるいはマッチしなかった場合暫関数や集約関数は正式に行パターン変数がマッピングされている

定マッピングされた行パターン変数を取り消す，といった一連の行に対し操作を行う関数である．このような関数が DEFINE 句

処理を一つのパターンのマッチに成功するか失敗するまで行う．

で用いられている場合は，パターンマッチング前に暫定マッピン

しかし，本手法では，(1)DEFINE 句に基づく行パターン変数のグを行うことができない．この場合は暫定マッピングを行うこと

暫定マッピングを，(2) のパターンにマッチする可能性があるかができる条件のみあらかじめ暫定マッピングを行う．ユースケー

確認の前にあらかじめ全ての行に対し並列に行う．暫定マッピン

ス 3 においては行パターン変数 A の暫定マッピングを，ユース

グは GPU 上の各スレッドが処理対象データの各行に対して一対ケース 4 においては行パターン変数 A と B の暫定マッピングを一で処理を行うことで並列計算を実現する．

あらかじめ実行する．図 7 のユースケース 3 における行パター

ユーザが定義する行パターン変数のマッピング条件は

ン変数 B の暫定マッピング，図 8 のユースケース 4 における行

SQL:2016 において指定されている複数の関数を組み合わせてパターン変数 C の暫定マッピングなどあらかじめ行うことがで行う．そのため DEFINE 句のパターン数は無数に存在する．しきないマッピングは次の処理ステップであるパターンマッチング

かし，本研究では考え得るすべてのパターンには対応していない．

時に行う．その処理方法に関しては 4.4 節で述べる．

そこで SQL:2016 において指定されている関数を用いた DEFINE

4.4

処理対象データからパターン抽出

句のユースケースを五つ準備した．ユースケースは図 5 から図 9

SQL/RPR における PATTERN 句の機能に相当する GPU 上でに示す．これらユースケースは SQL:2016 において指定されていの処理について述べる．行パターン変数が暫定マッピングされたる関数の多くを用いている．ユーザが任意に定義する DEFINE

処理対象データからパターンを抽出する処理では CUDA-grep [3]

句は多様であるものの，多くの場合は準備したユースケースののソースコードを改変したものを用いる．CUDA-grep は一つのDEFINE 句に近い形になると考えることができる．本研究では，マッチング対象データに対し，複数の正規表現パターンのマッチ

ユースケースの DEFINE 句をそれぞれ実装し，また評価実験を

ングを並列に行う．しかし本研究では，パーティション化された

行う．

複数のグループに対し PATTERN 句で定義した一つの正規表現
パターンのマッチングを行う．そのため，CUDA-grep を複数の各行への暫定マッピングは各データグループ毎に独立して行う

4日本データベース学会和文論文誌
一般論文

Vol. 20-J, Article No. 12, 2022 年 3 月

比較手法

5.1

比較手法として用いる PostgreSQL 上での SQL/RPR の処理手
法の実装方法について述べる．比較手法の実装には以下の五つのタスクが存在する．
Partition&Sort

PARTITON BY 句と ORDER BY 句に従い処理対象データをグループ化，その後各グループ内でソート．
Mapping RPV

行毎に DEFINE 句に基づき行パターン変数の暫定マッピン
図9

クエリのユースケース 5

グを行う．
Concat RPV

行毎に暫定マッピングされた行パターン変数をグループ毎に連結し，長大な文字列に変換する．このタスクの処理例につマッチング対象データに対し GPU 上のスレッドが並列にパターいて図 10 に示す．

ンマッチングを行うように変更した．

Pattern Matching

パターンマッチング前にあらかじめ暫定マッピングできない行連結された行パターン変数列に対し，パターンマッチング

パターン変数がユースケース内に存在する場合の処理について述を行う．Concat RPV タスクで出力されたグループ毎の行パべる．図 7 のユースケース 3，図 8 のユースケース 4 がそれに該

ターン変数列を入力とし，1 から始まる連番である 𝑖𝑑 ，パ

当する．

ターンの出現位置にパターン番号が代入された 𝑖𝑠_𝑚𝑎𝑡𝑐ℎ の

ここでは，処理例としてユースケース 4 の行パターン変数 C の

二つのカラムを保持するテーブルを出力する．

暫定マッピングを用い説明する．ユースケース 4 の抽出パターン

Collecting Resultsは (A* B+ C) であり，既に行パターン変数 A，B は暫定マッピン

Pattern Matching の結果に従い，最終結果を出力する．Pattern

グされている．まず，パーティションされたグループ内の一番上

Matching タスクで出力されたテーブルと Mapping RPV タの行から順に処理していきパターン (A* B+) にマッチするまでスクで出力されたテーブルを元に最終結果を出力する．

パターンマッチングを行う．そして直前の行まででパターン (A*B+) にマッチしており，かつ現在処理している行に行パターン変上記の五つのタスクの中で Pattern Matching 以外のタスクは数が何もマッピングされていない場合に MAX( ) 関数の計算を行SQL クエリのみで全ての処理を行っている．Pattern Matching タう．ユースケース 4 の MAX( ) 関数は現在行パターン変数 A がスクに関しては SQL クエリのみでは実装できないため本研究で暫定マッピングされている全ての行の中で一番高い Tax の値を求は C++ で実装した．SQL/RPR を処理する比較手法をまとめた擬める関数である．この時，並列プリミティブである ModernGPU

似 SQL クエリを Algorithm1 に示す．

の MaxReduce を用いる．MaxReduce は入力配列の中で最も大使用した PostgreSQL のバージョンでは並列クエリがサポー

きい値を出力する並列プリミティブである．これにより行パター

トされておらず，また PostgreSQL の外部で計算される Pattern

ン変数 C のマッピング条件を計算でき，現在処理している行に行

Matching タスクも並列化していないため，この比較手法は逐次

パターン変数 C をマッピングするか判断することが可能になる．

実行である．

以上がパターンマッチング前にあらかじめ暫定マッピングできな

5.2

実験準備

評価実験に用いたマシンの構成を表 1 に示す．

い行パターン変数が存在する場合の処理となる．
パターンマッチングが最終行まで完了した時，どの行がマッチ

表 1 実験に用いたマシンの構成

したかを示すオフセット配列を出力する．このオフセット配列は各パターン毎にパターン番号が振られている．パターン番号はパCPUIntel Core i7-6800K (3.4GHz，6 コア)

ターンにマッチするたびに「1」インクリメントされるシーケン

RAM

32GB
NVIDIA TITAN X (Pascal)

シャルな番号であり，マッチしたパターン毎にそのパターンに含

CUDA コア数

3584

立している．つまり，最後に振られたパターン番号がそのグルー

ベースクロック

1.53GHz

プ内のパターンの総マッチ数となる．

メモリ量

12GB

まれる行全てに振られる．また，パターン番号はグループ毎に独GPU

オフセット配列とデータベースを照らし合わせマッチしたパ
ターンを最終結果として出力し，全ての処理が完了となる．

5

評価実験
本節では，提案手法と PostgreSQL 上で SQL/RPR の処理を実CUDA

CUDA 8.0

OS

CentOS 7.7

データベース

PostgreSQL 9.2

また，本実験で用いた PostgreSQL はパラメータをチューニン
グしている．変更後のパラメータの値を表 2 に示す．

装した比較手法を比較し評価を行う．

5

日本データベース学会和文論文誌
一般論文

Vol. 20-J, Article No. 12, 2022 年 3 月

Algorithm 1 SQL/RPR を処理する比較手法の擬似 SQL クエリ
Require: 𝑖𝑛𝑝𝑢𝑡_𝑡𝑎𝑏𝑙𝑒// Partition&Sort
𝑡𝑎𝑏𝑙𝑒1 ← SELECT * FROM 𝑖𝑛𝑝𝑢𝑡_𝑡𝑎𝑏𝑙𝑒
ORDER BY 𝑝𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛_𝑐𝑜𝑙𝑢𝑚𝑛, 𝑠𝑜𝑟𝑡_𝑐𝑜𝑙𝑢𝑚𝑛;// Mapping RPV
𝑡𝑎𝑏𝑙𝑒2 ← SELECT *,CASE WHEN [𝑚𝑎 𝑝_𝑐𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛1] THEN ’𝑟 𝑝𝑣1’
WHEN [𝑚𝑎 𝑝_𝑐𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛2] THEN ’𝑟 𝑝𝑣2’：// 𝑚𝑎 𝑝_𝑐𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛 には 𝑟 𝑝𝑣 のマッピング条件を
記述

ELSE ’E’
END AS 𝑟 𝑝𝑣
FROM 𝑡𝑎𝑏𝑙𝑒1;
ALTER TABLE 𝑡𝑎𝑏𝑙𝑒2 ALTER 𝑟 𝑝𝑣 TYPE varchar;//次タスクでは varchar でしか扱えないため

図 10 Concat RPV タスクの処理例// Concat RPV
𝑡𝑎𝑏𝑙𝑒3 ← SELECT 𝑝𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛_𝑐𝑜𝑙𝑢𝑚𝑛,

表 2 PostgreSQL のパラメータ

パラメータ

string_agg(𝑟 𝑝𝑣, ”) AS 𝑟 𝑝𝑣𝑠

変更前

変更後

max_connections

100

4shared_buﬀers

32MB

10GB

𝑝𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛_𝑐𝑜𝑙𝑢𝑚𝑛;

設定なし

5GB

// Pattern Matching

work_mem

FROM 𝑡𝑎𝑏𝑙𝑒2
GROUP

BY

𝑝𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛_𝑐𝑜𝑙𝑢𝑚𝑛

ORDER

BY

𝑡𝑎𝑏𝑙𝑒4 ←pattern_matching(𝑡𝑎𝑏𝑙𝑒3)
5.3// 𝑡𝑎𝑏𝑙𝑒4 : 連番である 𝑖𝑑 ，パターンの出現位置にパターン番

実験内容

号が

本実験では，実行時間の計測範囲として CPU 上のデータベー代入された 𝑖𝑠_𝑚𝑎𝑡𝑐ℎ を保持する

スにデータが読み込まれている状態から，計算結果が CPU 上のメモリに書き込まれるまでとした．そのため CPU-GPU 間のデー// Collecting Results

タ転送時間も実行時間に含まれる．

𝑡𝑎𝑏𝑙𝑒5 ← SELECT *, row_number() OVER() FROM 𝑡𝑎𝑏𝑙𝑒2;//連番を振り直す

CPU 上のデータベースにはテストテーブルを設計している．

𝑜𝑢𝑡 𝑝𝑢𝑡_𝑡𝑎𝑏𝑙𝑒 ←SELECT 𝑝𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛_𝑐𝑜𝑙𝑢𝑚𝑛, 𝑠𝑜𝑟𝑡_𝑐𝑜𝑙𝑢𝑚𝑛,

テストテーブルは四つのカラムを保持しており，それらは item(取𝑜𝑡ℎ𝑒𝑟_𝑐𝑜𝑙𝑢𝑚𝑛, 𝑟 𝑝𝑣, 𝑖𝑠_𝑚𝑎𝑡𝑐ℎ

引された商品のカテゴリ)，tradedate(商品が取引された年月日)，

price(商品の取引価格)，tax(商品の取引価格の税金) である．テ

FROM 𝑡𝑎𝑏𝑙𝑒5

ストテーブルに読み込むデータには人工データを用いる．各カ

JOIN𝑡𝑎𝑏𝑙𝑒4

ON𝑡𝑎𝑏𝑙𝑒5.𝑟𝑜𝑤_𝑛𝑢𝑚𝑏𝑒𝑟=

𝑡𝑎𝑏𝑙𝑒4.𝑖𝑑

ラムのデータはそれぞれ一様分布に従う乱数とし，全体サイズ
は 870MB，1.7GB，10GB の三種類となるようにした．三種類

WHERE 𝑖𝑠_𝑚𝑎𝑡𝑐ℎ != 0;のデータベースのレコード数はそれぞれ 1.74 × 107 ，3.47 × 107 ，// 𝑖𝑠_𝑚𝑎𝑡𝑐ℎ = 0 の行はパターンにマッチ

2.08 × 108 である．また，item カラムのデータの種類は 10 種類

していない行，最終結果には表示しない

return 𝑜𝑢𝑡 𝑝𝑢𝑡_𝑡𝑎𝑏𝑙𝑒となるようにした．
実験で用いるクエリを図 11 に示す．

AFTER MATCH SKIP 句，PATTERN 句，DEFINE 句には，図5 から図 9 に示した五つのユースケースを用いた．
5.4

スク，Mapping RPV は DEFINE 句で定義されている行パターン

実験結果

変数のマッピング条件に従い処理対象データの各行に行パター

提案手法における実行時間を各タスク毎に計測した．タスク

ン変数を暫定マッピングするタスク，Pattern Matching は処理対には copyHostToDevice，Partition，Sort，Mapping RPV，Pattern

象データからパターンを抽出するタスク，copyDeviceToHost はMatching，copyDeviceToHost がある．copyHostToDevice は CPU

GPU 上の計算結果を CPU に転送するタスクである．また，比較上のデータを GPU に転送するタスク，Partition は GPU 上で処理手法における実行時間も 5.1 節で述べた各タスク毎に計測した.

対象データのパーティションを行うタスク，Sort はパーティショ

ここでは，図 5 に示したユースケース 1 に対する各タスクのンされた各データグループ毎をソートカラムに従い並び替えるタ

実行時間と全タスクの合計時間を図 12 から図 14 に示す．各タ6

日本データベース学会和文論文誌
一般論文

Vol. 20-J, Article No. 12, 2022 年 3 月

図 12

図 11 評価実験に用いるクエリ

ユースケース 1，870MB

スクの実行時間と全タスクの合計時間の図はデータベースのサイズ毎に示す．提案手法は比較手法と比べ約 7.1–16.9 倍の性能となっている．
また，その他のユースケースにおいては，ユースケース 2 では
提案手法は比較手法と比べ約 7.5–17.8 倍の性能，ユースケース

3 では提案手法は比較手法と比べ約 12.0–22.6 倍の性能，ユース
ケース 4 では提案手法は比較手法と比べ約 10.5–22.5 倍の性能，
ユースケース 5 では提案手法は比較手法と比べ約 10.3–20.2 倍の性能となっている．
提案手法では Sort タスクと Pattern Matching タスクの実行時間がデータベースサイズの変化により大きく変化が見られる．比図 13 ユースケース 1，1.7GB

較手法では全てのタスクでデータベースサイズの増加に伴い実行時間も増加している．
提案手法では全体の実行時間の内 Pattern Matching タスクが支配的となっている．表 3 に提案手法のユースケース毎の Pattern

Matching タスクの実行時間を示す．ユースケース 4 の実行時間
はユースケース間において僅かに差が見られるが，抽出パターン
がその他のユースケースと違うことが一つの要因として考えられる．
また，提案手法の Partition，Sort，Mapping RPV タスクは全体の実行時間に及ぼす影響は少なかった．一方，比較手法ではPartition，Sort，Mapping RPV タスクは全体の実行時間に比べ無視できる範囲ではない．従い，Partition，Sort，Mapping RPV タ
スクは提案手法で極めて高速化されたと言える．

図 14

表 3 各ユースケースにおける提案手法の Pattern Matching の実行時間

実行時間 (sec)

5.5

ユースケース 1，10GB

グループ数による実行時間の変化

データベースの item カラムのデータの種類数，つまりグルー

データベースのサイズ

プ数を変化させた時の各タスクの実行時間と全タスクの合計時間

870MB

1.7GB

10GB

ユースケース 1

15.61731.228186.957

を表 4 と表 5 に示す．これらはデータベースのサイズが 870MB，

ユースケース 2

15.21330.325181.821

AFTER MATCH SKIP 句，PATTERN 句，DEFINE 句には，図 5

ユースケース 3

15.63531.093186.157に示したユースケース 1 を用い計測を行った．また，グループ数

ユースケース 4

14.41128.637172.212が 10，1000，10000 の三パターン計測を行った．

ユースケース 5

15.22130.291180.606

提案手法ではグループ数の増加に伴い Pattern Matching タスクの実行時間が減少した．Pattern Matching タスクはグループ毎に並列にパターンマッチングを行っている．そのためグループ数の7日本データベース学会和文論文誌
一般論文

Vol. 20-J, Article No. 12, 2022 年 3 月

増加に伴い並列度の高い処理が行われ実行時間の減少につながっ謝辞たと考えられる．
一方，比較手法ではグループ数の増加に伴い Partition&Sort タ

本 研 究 の 一 部 は ，JSPS 科 研 費 (18H03242, 18H03342,

19H01138) の助成を受けたものである．

スクの実行時間が増加した．Partition&Sort タスクの実行時間が増加した原因としてはグループ数の増加によりパーティション計

参考文献

算が複雑になったことが考えられる．

[1] ISO/IEC 2016. Information technology – database languages – sql
technical reports - part 5: Row pattern recognition in sql. Technicalreport, ISO copyright oﬃce, 2016.
[2] SeanBaxter.
moderngpu
2.0.
https://github.com/moderngpu/moderngpu. 2021 年 1 月 20 日
アクセス.
[3] Cuda-grep. https://github.com/bkase/CUDA-grep. 2021 年 1 月 20
日アクセス.
[4] Cudpp. https://github.com/cudpp/cudpp. 2021 年 1 月 20 日アクセス.
[5] J. Dean and S. Ghemawat. Mapreduce: simpliﬁed data processing onlarge clusters. Commun. ACM, 51(1):107–113, 2008.
[6] Hadoop. https://hadoop.apache.org/. 2021 年 1 月 20 日アクセス.
[7] B. He, W. Fang, Q. Luo, N. K. Govindaraju, and T. Wang. Mars:
A mapreduce framework on graphics processors. In Proc. of PACT
2008, pages 260–269, 2008.
[8] Patterns everywhere - ﬁnd them fast! sql pattern matching in oracle
database 12c an oracle white paper, 6 2013.
[9] Pg-strom. https://heterodb.github.io/pg-strom/ja/. 2021 年 1 月 20 日
アクセス.
[10] C. Ranger, R. Raghuraman, A. Penmetsa, G. Bradski, andC. Kozyrakis. Evaluating mapreduce for multi-core and multiprocessor systems. In Proc. of IEEE 13th International Symposium on
High Performance Computer Architecture (HPCA ’07), pages 13–24,
2007.
[11] 中挾 晃介，北川 博之. シーケンスデータに対する行パターンマッ
チングの効率化. 情報処理学会論文誌, 62(1):302–320, 2021.

この結果からパーティションされるグループ数が多い程，並列度の高い提案手法がより有効な処理手法となることが判明した．

表4

グループ数を変化させた時の提案手法の実行時間

グループ数

実行時間 (sec)

タスク

表5

10

1000

10000

copyHostToDevice

0.303

0.298

0.299

Partition

0.029

0.028

0.029

Sort

0.999

0.992

0.974

Mapping RPV

0.001

0.001

0.001

Pattern Matching
copyDeviceToHost

15.6170.080

12.414
0.081

8.154
0.076

合計時間

17.02913.814

9.533

グループ数を変化させた時の比較手法の実行時間

グループ数

実行時間 (sec)

タスク

6

10

1000

10000

Partition & Sort

44.12984.768103.966

Mapping RPV

17.89117.66317.905

Concat RPV

5.370

5.083

4.625

Pattern Matching

19.37919.70818.582

Collecting Results

34.04338.10435.229

合計時間120.812165.326

180.307

おわりに
本研究では並列プリミティブを始めとした GPU の技術を用い

SQL/RPR の高速な問い合わせ処理を実現する手法を提案した．
評価実験では，比較手法として PostgreSQL 上で SQL/RPR を実装した．そして SQL/RPR のユースケースのクエリを用い提案
手法と比較手法を比較することで性能を評価した．評価実験の結果から並列プリミティブなどの技術を組み合わせることで，GPU
上で SQL/RPP の処理を効率的に行うことが可能であることが判明した．また，実行時間において提案手法は比較手法と比べ約7.1–22.6 倍の性能向上を達成した．
今後の課題として，ユーザが自由に定義できる DEFINE 句に対し GPU 上での処理を自動生成するコンパイラの構築，AFTER

MATCH SKIP 句に存在する複数のオプションの対応，SQL/RPRのクエリの対象となるデータベース上のデータが GPU 上のメモ
リに全て乗り切らない場合の処理手法の考案が考えられる．

8