DEIM Forum 2016 D5-5

RDB と KVS を相互に利用した多次元データに対する集約演算の効率化
佑也†

渡

欅

惇志††

宮崎

純††

中村

匡秀†††

† 東京工業大学 工学部 情報工学科 〒 152–8550 東京都目黒区大岡山 2 丁目 12-1†† 東京工業大学 情報理工学研究科 〒 152–8550 東京都目黒区大岡山 2 丁目 12-1††† 神戸大学大学院システム情報学研究科 〒 657-8501 兵庫県神戸市灘区六甲台町 1-1
E-mail: †{watari,keyaki}@lsc.cs.titech.ac.jp, ††miyazaki@cs.titech.ac.jp, †††masa-n@cs.kobe-u.ac.jp
あらまし

本研究では，分散ストレージ上に蓄積された多次元のデータに対して，平均値などの集約演算値を求める

範囲クエリを効率的に処理する手法を提案する．IoT (Internet of Things) 時代の到来により，センサデータをはじめとする膨大なデータが収集できるようになってきた．こうしたデータの傾向を分析して新たな知見を得ることが重要であり，そのような分析の一例として集約演算を使用するものが存在する．リレーショナルデータベース (RDB) は多次元データを効率的に扱うことができ，集約関数も標準で用意されているが，大規模データに対してスケールアウト
しづらいという問題が存在する．また，分散キーバリューストア (分散 KVS) はスケールアウトしやすく設計されているが，多次元データへのアクセスはしばしばデータの全スキャンを伴い非効率的である．このように RDB と KVSは相補的な関係にある．提案手法では，両者を相互に活用することで，多次元データに対する集約演算を効率化する．
評価実験として集約演算の範囲クエリを最大 96 並列で与えた結果，提案手法はパラメータを適切に設定することで，PostgreSQL や HBase を単体で用いるときよりも高いクエリスループットを達成できることを示した．
キーワード

集約演算，範囲クエリ，RDB，KVS

1. は じ め に模データや処理を分散させるスケールアウトを実現しにくい

RDB の欠点が問題となってくる．

近年，社会に存在する多種多様な機器がインターネットに接一方で，NoSQL の一種である分散 KVS では，高い挿入ス

続されるようになってきた．これは IoT (Internet of Things)

ループットやスケールアウトを実現しやすく，効率的に大規と呼ばれ，IoT 時代の到来により，センサデータなどの大量の模データを扱うことができる．しかし，多くの KVS にはインデータが収集できるようになった．こうしたデータの傾向を分デックスが存在しないか，存在しても単純な機能しか持たない．

析して新たな知見を得ることが重要であり，そのような分析の従って，多次元データにアクセスする際には膨大な全データを一例として集約演算を使用するものが存在する．たとえば，セスキャンする必要があるため，極めて非効率的である．なお，（注 1）

ンサデータとしてアメダスのデータを考える．このデータ

本論文では，分散 KVS を単に KVS と呼ぶことにする．

には，観測日時や気温のほかにセンサが置かれている場所の緯このように RDB と KVS は，相補的な利点を持つ．そこで，度と経度の属性が含まれているとする．ここで「ある長方形で本研究では両者を相互に利用し，多次元のデータに対して集約表される地域内の過去一週間の平均気温 (移動平均)」をグラフ

演算値を求める範囲クエリを効率的に処理する手法を提案する．

として表すことで気温の変動を分析したいとする．これは，日提案手法では，データが属する多次元空間をグリッドに分割し時と緯度，経度に関する三次元の範囲に含まれるデータに対していき，グリッドごとの集約演算結果 (部分集約結果) を事前て集約演算を行う範囲クエリを，日時を少しずつ移動させながに計算しておく．範囲クエリを処理する際には，部分集約結果

ら行うものであるといえる．このような範囲クエリに対する処を可能な限り再利用して集約演算結果を求める．この際，デー理を実現するために，リレーショナルデータベース (RDB) [1]タ量が膨大となり頻繁に更新される実データや部分集約結果はやキーバリューストア (KVS) [2] を用いることが考えられる．

KVS で保持する．また，実データほど量は多くないが複雑な

RDB にはインデックスの概念が存在する．そのため，先の構造を持つグリッドそのものの情報を RDB で保持する．

アメダスデータのような多次元データを効率的に扱うことが出

本研究では，提案手法を PostgreSQL と HBase を用いて実来る．しかし，センサデータが継続的に入力されるようなシス

装し，集約演算のスループットを従来手法，すなわち，RDB

テムでは，短時間に大量のデータが挿入される場面に対処できと KVS をそれぞれ単体で用いる手法と比較する実験を行うこる必要があるが，RDB はデータの一貫性や整合性を保ちながとで，提案手法の性能を明らかにする．

ら書き込みリクエストを処理するため，高い挿入スループットを実現するのは困難である．また，時間の経過とともに蓄積されるデータの量は増大するため，サーバの台数を増やして大規

2. 基 礎 知 識
本節では，提案手法が利用するリレーショナルデータベース(RDB) とキーバリューストア (KVS)，および多次元データに（注 1）：http://www.jma.go.jp/jp/amedas/

対する二分探索木である k-d tree について整理する．

2. 1 リレーショナルデータベース (RDB)

HBase では，テーブルを Region と呼ばれる単位に分割する．

リレーショナルデータベース (Relational DataBase, RDB) [1]

各 Region 内の行キーは連続している．データ数の増加につれには，関係 (リレーション) やそれに対する様々な関係代数演算て，自動的に Region が分割される．Region は，Region Server

を SQL (Structured Query Language) を用いて簡単に記述でで保持される．データが増加した場合は，新たな Region Server

きるという特徴がある．また，インデックスを用いることで複を追加することで簡単にスケールアウトを実現できる．

雑な処理を効率的に行うことができるほか，トランザクション

2. 3 k-d treeが存在するなど一貫性を重視した構造となっている．しかしそk-d tree とは，多次元空間をトップダウン的に分割して構築

れ故に，分散化してもスケールアウトしにくいという問題点がされる二分探索木である．分割はある軸に垂直な平面で行われ，ある．このような RDB に基づくシステムは，リレーショナル

その軸は循環的に選択される （注 3）．分割点の選び方はいくつ

データベース管理システム (Relational DataBase Management

か考えられるが，データの中央値付近で分割すると平衡な k-d

System，RDBMS) と呼ばれる．

tree が得られる．図 1 に 2 次元平面上での空間 (平面) 分割の

PostgreSQL

様子を示す．

PostgreSQL [3] は，オープンソースの RDBMS であり，点以降では，k-d tree の各ノードが表す超直方体をグリッドや長方形などを表現する幾何データ型が標準で用意されている．

(grid) と呼ぶことにする．k-d tree は二分木であるから，グリッPostgreSQL の幾何データ型のうち box 型について説明する．

ドをビット列の番号として表現できる．あるグリッドの番号がbox 型は二次元平面上の長方形 (矩形) を表し，対角線の両端ビット列 x であるとき，それを分割して出来る二つの子グリッの二点で表現される．box 型をオペランドにとり真偽値を返す

ドの番号は，x ⊕ 0 および x ⊕ 1 とすることができる．ここに二項演算子として，&&演算子と@<演算子が存在する．&&演算子⊕ は，ビット列の連結を表す．データ空間全体を示すグリッドは，2 つの box 型に共通部分がある (接する場合を含む) ときに(根ノード) は，1 ビットのビット列 0 で表現する．図 1 では，真を返し，@<演算子は，左辺が右辺に包含される (内接する場

このビット列が表現されている．

合を含む) ときに真を返す．これらの演算子は，GiST [5] イン
デックスとともに利用することが出来る．つまり，多数の box

このような番号付けを採用することで，提案手法において重要な役割を果たす次の性質が得られる．

型オブジェクトが含まれるテーブルから，ある box 型と共通部分を持ったり包含されたりするものを高速に列挙することが可性質 1 (グリッド番号の接頭辞性) グリッド Gd がグリッド G

能である．

の子孫であるとき，グリッド G の番号はグリッド Gd の接頭辞

2. 2 キーバリューストア (KVS)
キーバリューストア (Key-Value Store，KVS) [2] とは，キー(key) と値 (value) が一対一に対応する構造 (この対を行と呼ぶ) を持ったデータベースのことである．この構造は，関係モデルにしたがってテーブルを定義する RDB に比べ非常に単純なものであり，膨大なデータを扱う場合でもスケールアウトしやすいという特徴がある．その一方で，データに対するアクセとなる．
図 1 でこの性質を確認する．図 1 (b) におけるグリッド 00 は，
図 1 (c) においてグリッド 000 と 001 の 2 つの子グリッドに分割される．親グリッドの番号 00 は，ともに子グリッドの番号の接頭辞になっていることが分かる．さらに，グリッド 001 の子であるグリッド 0010，0011 も 00 を接頭辞に持つ．

スは原則としてキーによる検索に限られるため，RDB が実現する柔軟で複雑な処理を KVS で行うのは難しい．

HBase

0

00

01

HBase [4] は KVS の一種であり，特にカラム指向型のデー
タベースである．HBase の行にはカラムファミリー (column

family) が複数存在し，各カラムファミリー内に複数のカラム

(a)

(b)

(値) が存在するという階層構造を持つ．一つのカラムファミリー内では，カラムの数やそのデータ型は柔軟に変更できる．
このように一つのキーに複数の値 (カラム) を対応づけることが出来るような KVS をカラム指向型という．
また，HBase のテーブルは行の集合であり，キーでソートされている．そのため，キーの範囲検索を効率的に行うことができる．これを応用すると，キーの前方一致検索も簡単に行える

001

011

000

010

(c)

0010

0011

000

011
010

(d)
図 1 2 次元空間における k-d tree の分割の様子ことになる．たとえば，キーが “ABC” で始まるデータをスキャ
ンしたいときは，キーの範囲として [“ABC”，“ABD”)（注 2） を指定すればよいことになる．

（注 3）：循環的とは次のような意味である．n 次元空間上の k-d tree を考えると，第 1 軸で分割したあとは第 2 軸で分割する．このように順番に分割してい（注 2）：終点は含まれないことに注意する．

き，第 n 軸のあとは再び第 1 軸で分割する．

3. 関 連 研 究

スとは，属性ごとの最大値や最小値をあらかじめ計算したものである．たとえば，ブロック B1 に含まれるデータの年齢の3. 1 部分集約法

最大値が maxage (B1 ) = 13 であったとすると，上記のように部分集約法 [6] とは，データベースを複数のブロックに分割

σage<(B1 ) = B1 であると判断できる．
=15

してブロックごとに集約演算結果を事前計算した上で，集約演

なお，部分集約法を適用することが出来るのは，最大値のほ算のクエリを処理する際に事前計算結果を可能な限り再利用しか，最小値，総和，平均値のようにデータの部分的な集約演算て効率化を図る手法である．

結果から全体の結果が求まるような集約演算に限られる．その

たとえば，年齢 (age) と身長 (tall) からなるリレーション B
を考える．まず，B を 3 つのブロック B1 ，B2 ，B3 に分割すため，属性の濃度 (cardinality) に対しては，部分集約法を適用できない．

る．このとき，3 つのブロックは互いに共通部分を持たず，そ3. 2 MD-HBase

れらの和集合が B に一致するように分割する．リレーション

MD-HBase [7] は，HBase を改良して多次元範囲検索を効率

B の属性 tall に対する最大値の集約演算 maxtall (B) は，
maxtall (B) = maxtall (B1 ∪ B2 ∪ B3 )= max (maxtall (B1 ), maxtall (B2 ), maxtall (B3 ))的に行えるようにした KVS である．

MD-HBase では，空間充填曲線と呼ばれる多次元空間内のすべての点を一筆書きでなぞる曲線を用いて，多次元データを一次元データへと変換し，その値をキーとして HBase 上にデーのように，ブロックごとに集約演算を行った結果 (部分集約結

タを挿入する．MD-HBase では，空間充填曲線として Z カー果) から求めることが出来る．部分集約法は，この部分集約結

ブ [8] を用いる．また，k-d tree により多次元空間を複数の領果をあらかじめ求めておくことで，実データへのアクセスを省域に分割し，領域ごとのキーの最小値と最大値をインデックス

略して集約演算を効率化する．

として保持する．

続いて，集約演算に選択演算が組み合わさる場合を考える．

多次元範囲検索を行うときは，検索領域内のキーの最小値と先ほどと同じリレーションに対して，15 歳以下の子供について最大値を求め，HBase に対してキーの範囲検索を行う．このの身長の最大値を求めたいとする．年齢 (age) が 15 歳以下でとき，検索範囲外のデータまでスキャンしてしまうのを避けるあるレコードを選択する選択演算を σage<(·) と書くことにす=15

ために，インデックスからキーの最小値と最大値の範囲内にあれば，求める最大値は，る領域を調べ，検索範囲と全く重ならない領域については，ス
キャンを省略することで範囲検索を効率化する．

maxtall (σage<(B))=15=maxtall (σage<(B1 ) ∪ σage<(B2 ) ∪ σage<(B3 )) (1)
=15
=15
=15
と計算できる．ここで，ブロック B1 ，B2 ，B3 について次の知識が与えられているとする．

•••

MD-HBase は，インデックスを含めすべてのデータ構造を
HBase 上に構築する．これは，RDB と KVS を共に利用する提案手法と異なる．また，MD-HBase において k-d tree の各領域内にあるデータのキーは連続している必要があるが，Z カー
ブの性質上，この条件を満たすためには領域のちょうど真ん中ブロック B1 に含まれるレコードはすべて 15 歳以下であの点で分割しなければならない．一方，提案手法では，グリッる (σage<(B1 ) = B1 が成り立つ．選択率が 100%)=15

ド分割の情報を RDB で保持するため，真ん中の点以外で分割

ブロック B2 には 15 歳以下であるようなレコードは含ますることができる．これにより，データの分布が不均一であっれない (σage<(B2 ) = ∅ が成り立つ．選択率が 0%)=15ても木を平衡に保ちやすくなるほか，ユーザが与えるクエリにブロック B3 には 15 歳以下であるレコードもそうでない

応じて柔軟に分割することも可能となる．

(15 歳より上の) レコードも含まれる (σage<(B3 ) は，B3
=15とも ∅ とも等しくない)
この知識により，式 (1) は，

maxtall (σage<(B1 ) ∪ σage<(B2 ) ∪ σage<(B3 ))=15=15=15

4. 提 案 手 法
4. 1 概要

図 2 に示した提案手法の概念図を用いて，提案手法の概要を説明する．提案手法において，集約演算を効率的に計算する流=maxtall (B1 ∪ σage<(B3 ))=15

れは次の通りである．

=max(maxtall (B1 ), maxtall (σage<(B3 )))=15(1) データ空間を複数のグリッドに分割する (図 2 上側)．

と変形できる．最終式の maxtall (B1 ) は事前に計算されている
ため定数時間で求めることが出来る．したがって，データの全スキャンは，maxtall (σage<(B3 )) を計算するためにブロック=15

B3 に対してのみ行えばよく，B1 ，B2 のデータをスキャンする必要はない．

(2) 各グリッドについて集約演算を行った結果 (部分集約結果)
を事前に計算し保持しておく．

(3) クエリ範囲 (図 2 上側の破線) に完全に包含されるグリッドについては部分集約結果を再利用してデータの全スキャ
ンを省略しながら，集約演算結果を求める．

上記のような知識を得るための方法として，小山田ら [6] は(1) におけるグリッド分割は k-d tree に従う．図 2 は，図 1

軽量インデックスの利用について述べている．軽量インデック(d) から，さらにグリッド 0011 を分割した後の状態である．

アウトを実現しやすい KVS (HBase) でこれらの情報を保持することとした (図 2 の右下)．

25

00111

15 0010
00110
10
000

0

10

このように RDB と KVS の双方の利点を活用することで，011

それらを単体で用いる際に発生する問題を解決する．

4. 2 用語の定義提案手法では，データを多次元空間上の点として考える．デー

010

タの定義域をデータ空間と呼ぶことにし，記号 D (⊂ Rn ) で表
す．ここに n はデータの次元数であり，データ空間は超直方体

20である．より正確にいえば，超直方体の次元 i の始点と終点を

si ，ei (si , ei ∈ R，si < ei ) とすると，D は次のように直積で
表される．

RDB

000
0010
00110
00111
⋮

KVS

(0, 0) (20, 10)(0, 10) (10, 25)(10, 10) (20, 15)(10, 15) (20, 25)
⋮
⋮

Key

Value

000-0
000-1
000-2
000-min
⋮

52
47
49
47
⋮

D = [s1 , e1 ] × [s2 , e2 ] × · · · × [sn , en ]グリッドとは，データ空間を分割してできる超直方体である．
グリッドの総数を m とすると，グリッド G1 , · · · , Gm ⊂=D は，
式 (2) を満たす．これは，グリッド分割が数学的な集合の分割(どの二つのグリッドも互いに共通部分を持たず，すべてのグ
リッドの和集合はデータ空間全体となる分割) であることを意味する．

図 2 提案手法の概念図∀i =| j (Gi ∩ Gj = ∅)(2) について，新しくデータが追加されたときは，部分集約
結果を足し合わせるように更新する．

(3) について，図 2 に示したクエリ範囲を例にとると，これは三つのグリッド (000，00110，00111) と交わっている．このう

かつ∪

Gi = D(2)

i=1,...,m()
グリッド G とクエリ範囲 Q ⊂Dについて，G が Q と交わ=るとは G ∩ Q =| ∅ が成り立つことであり，G が Q に完全に包含されるとは G ∩ Q = G が成り立つことである．

ち，グリッド 000 はクエリ範囲と一部が交わるので，データの4. 3 データ構造

全スキャンを行う必要があるものの，グリッド 00110 と 00111

4. 3. 1 グリッド分割の情報

は，クエリ範囲に完全に包含されるため，部分集約結果を参照

本節の冒頭で述べたように，グリッド分割の情報は RDB でするだけでよく，データの全スキャンは不要である．

保持し，そこに n 次元のインデックスを作成することとした．

ここで，提案手法における工夫点は，図 2 の下側に示した

今回は，PostgreSQL を用いて実装したが，PostgreSQL には

ように RDB と KVS の双方の長所を最大限生かすようにデー

3 次元以上のデータを扱えるインデックスが存在しないため，タを保持する点である．提案手法で必要となるデータには，グ

2. 1 節で述べた box 型の集合で代用した．具体的には，n 次元

リッド分割の情報 (データ空間上に存在するグリッドの位置，大空間上のグリッドを ⌈n/2⌉ 個の box 型で表現し，それらに複合

きさおよび番号) と，実データ，部分集約結果がある．

インデックスを張った．

このうち，グリッド分割の情報は，グリッドが極端に小さく例として，n = 5 のときのグリッド分割の情報を保持するない限り実データに比べてデータサイズは十分小さいと考えら

PostgreSQL テーブルの定義を次に示す．列 C0，C1 がそれぞれれる．その一方で，クエリ処理を行うためにはクエリ範囲と交二次元分を表現し，C2 が残りの一次元分を表現する．列 GridID

わるグリッドを列挙するという複雑な処理を行う必要がある．

はグリッド番号を表し，列 NextSplittingDimension は，k-d

このような特徴から，提案手法では，インデックスを用いるこ

tree において次に分割すべき軸を表す．

とで多次元データを効率的に扱える RDB (PostgreSQL) でグ
リッド分割の情報を保持することとした (図 2 の左下)．グリッ
ド分割の情報は，グリッドが分割されない限り更新されず，そのグリッド分割もデータ挿入と比較すると十分に低頻度である
ため，データベースの複製を利用することも容易である．

CREATE TABLE SensorTable(C0 box, C1 box, C2 box,
GridID text, NextSplittingDimension integer)
このテーブルに対して，グリッドの列挙を高速に行うために一方，本研究が扱うデータとしてセンサデータを想定すると，

インデックスを作成する．具体的には，⌈n/2⌉ 個の box 型に対実データの量は膨大なものになると考えられる．また，絶え間する複合インデックスであり，インデックスの種類は GiST でなくデータが生成されるため，実データや部分集約結果は頻繁ある．先の例におけるインデックスの定義を次に示す．

に更新される（注 4）．そこで，高い挿入スループットとスケール

CREATE INDEX SensorTableGridBoxIndex（注 4）：4. 4 節でも述べるが，部分集約結果の計算はクエリ処理が与えられるまで遅延させることも考えられる．

ON SensorTable USING GiST (C0, C1, C2)

が出てくるときまで遅延させることも考えられる．

4. 3. 2 実データ・部分集約結果
実データと部分集約結果は，分散 KVS の一種である HBase(4) の詳細は，4. 5. 1 節で述べる．

に格納する．HBase テーブルは図 3 に示したような構造をと

4. 5 グリッド分割

る．この例は，図 2 の状況に対応している．

4. 5. 1 データの分布に応じたグリッド分割

図 3 に示した行キーは，1 文字が 1 バイトを表す．行キーの4. 4 節で述べたように，データの挿入によってグリッド内の先頭に記されている “ ? ” は，0 から 255 までの 1 バイトの整数

データ数が Nthreshold を超えた場合，k-d tree にしたがいグリッ

値であり，“ ? ” の後に続くグリッド番号の先頭の次から 8 ビッ

ドを分割する．そのアルゴリズムを次に示す．

ト分を数値として解釈した値である．ただし，ビット数が足りアルゴリズム 2 グリッド G の分割(1) 分割すべき軸の番号 i (1 <=i<= n) を PostgreSQL に問いない場合は，下位ビットが 0 であるとみなす．なお，先頭ビッ

合わせる．

トを無視するのは，それが常に 0 であるためである．
たとえば，図 3 左側の最終行の行キーは，“ ?00111-2 ” であ(2) グリッド内の軸 i についての平均値 avgi を HBase から取る．このときの “ ? ” の値は，グリッド番号の先頭を除いたビッ

得する (これは部分集約結果として保持されている)．

ト列 “0111” を 8 ビットになるよう 0 を末尾に付加して得られ(3) グリッド G 内のデータのうち，第 i 軸の値が avgi 以下でる “01110000” を数値として解釈した値，すなわち 112 である．

あるものから子グリッド Glower を，それ以外のデータからこのように行キーの先頭バイトを 0 から 255 まで分散させる子グリッド Gupper を作成する．このとき，HBase 内の実ことで，HBase テーブルを Region に分割する際にデータを分

データの行キーを新たなキーに書き換える．また，Glower ，

散させやすくなる．さらに，グリッド番号の大小関係と行キー

Gupper の部分集約結果を計算し，HBase に挿入する．

の大小関係が一致するため，グリッド番号に対する接頭辞検索(4) PostgreSQL テーブルから G の情報を削除するとともに，
Glower ，Gupper の情報を追加する．このとき，次に分割を簡単に行えることになる．
また，部分集約結果は親グリッドについても保持されていることに注意する．たとえば，図 3 右側を見るとグリッド 00110

すべき軸の番号は i + 1 (これが次元数 n を超えた場合は第 1 軸に戻る) とする．

と 00111 の体重の最大値が示されているが，それらの親である(5) Glower ，Gupper に含まれるデータ数がグリッドサイズ Nsize

グリッド 0011 の最大値も記録されている．その親についてもを超えた場合は，このアルゴリズムを再帰的に適用する．

同様である．

(3) で中央値ではなく平均値で分割しているのは，中央値の4. 4 データ挿入

計算にコストがかかるためである．

新たなデータを挿入するアルゴリズムは，次の通りである．

また，(5) で再帰的にアルゴリズムを適用するかを判断する

アルゴリズム 1 データ d (∈ D) の挿入

グリッドサイズ Nsize は，アルゴリズム 1 (4) における分割閾

(1) データ点 d が属するグリッド番号 gridID を PostgreSQL

値 Nthreshold とは異なる．両者は，Nsize <= Nthreshold なる関係を満たす．つまり，データの挿入によってグリッドサイズ Nsize

テーブルに問い合わせる．

(2) HBase テーブルに「? gridID-elementID 」をキーとしてを少し超えることは許容し，ある程度のデータ数になってから分割を開始する．これによりグリッド分割の頻度を抑制できる．

実データを挿入する．

(3) データ点 d が属するグリッドおよびすべての親グリッド

4. 5. 2 時間軸の特別な分割について，HBase 上の部分集約結果を更新する．

提案手法では，時間軸を特別扱いして最初のデータが挿入さ(4) 挿入を行った結果，グリッド内のデータ数が分割閾値

れる前にあらかじめ分割を行っておく．具体的には，グリッドを時間軸について二等分するという操作を，グリッドの幅がパ

Nthreshold を超えた場合はグリッドを分割する．
(1) は，2. 1 節で述べた box 型に対する演算子を用いる．
(3) で親グリッドに対しても更新を行うのは，4. 6. 1 節で述べる部分集約結果参照の効率化のためである．なお，(3) の作
業は，実際にクエリが与えられて部分集約結果を参照する必要

ラメータ Ltime 以下になるまで再帰的に繰り返す．このようにして出来たグリッドを初期状態とする．この分割は時間軸についてのみ繰り返し行われるため，純粋な k-d tree ではなくなる
ものの，提案手法における仮定は保たれる．
センサデータのような時系列データは，古いデータから順番に挿入される．こうした状況のもとで 4. 5. 1 節で述べたグリッ
ド分割を行うと，木が時間軸について偏ってしまう．時間軸についての特別な分割を行うことでこの問題を解決できるほか，?00110-0?00110-1?00110-2?00110-3?00111-0?00111-1?00111-2

32
40
25
26
30
33
34

170
173
159
163
175
177
180

65
71
47
50
70
81
83

?0?00?001?0011?00110?00111-

図 3 HBase テーブルの様子

97
90
83
83
71
83

初期状態にグリッドが一つ (データ空間全体を表すグリッド) しか存在しない場合に比べ，データ挿入のスループットが高まると考えられる．センサデータは時間軸についておおむね一様に分布すると期待できるのでこうした分割は理にかなっている．

4. 6 クエリ処理()
クエリ範囲 Q ⊂Dが与えられたとき，Q に含まれるデー=
タに対して集約演算を行うアルゴリズムは次の通りである．

アルゴリズム 3 クエリ範囲 Q 内のデータに対する集約演算

は 6 台あり，PostgreSQL が動作する計算機は HBase のクラス
タには含まれていない．

(1) Q と共通部分を持つグリッドを PostgreSQL テーブルか用いた PostgreSQL のバージョンは 8.4，HBase のバージョら列挙する．このとき，クエリ範囲に完全に包含されるかンは 1.0.0 である．また，各計算機の構成は次の通りである．

どうかも問い合わせる．

(2) (1) で列挙されたグリッドのうち，クエリに完全に包含されるグリッドの部分集約結果を足し合わせる．

(3) (1) で列挙されたグリッドのうち，クエリと一部が交わる
グリッドに含まれるデータをすべてスキャンし，クエリ範
囲に含まれるものについて集約演算を行う．

(4) (2) および (3) で得られた集約演算結果を足し合わせて，最終的な結果を求める．

OS CentOS 6.7
CPU Intel Core i7-3770 (3.4 GHz，4 コア/ 8 スレッド)
メモリ 32GB

HDD 2TB
5. 2 実験で使用したデータ
5. 2. 1 室内気象データ
実験データの一つとして，室内の気象センサより得られた気(2) は，HBase テーブルに記録されている部分集約結果を取

温や湿度などからなるデータを用いた．以後，このデータを得 (get) すればよい．(3) では，行キーに対する接頭辞検索によ「室内気象データ」と呼ぶことにする．室内気象データは 23 個

り特定のグリッド内のデータのみをスキャン可能である．実際の属性を持つが，本実験においてはそのうち表 1 の 5 つの属性の実装では，クエリ範囲に含まれるデータだけを抽出するフィを用いた．室内気象データは，時刻の定義域内で 1 分ごとに記ルタを独自に作成し，HBase サーバ上で実行できるようにした

録されており，データ数は 2,032,918 件 (約 200 万件) である．

ほか，集約演算も HBase サーバ上で行うことでネットワーク
負荷を軽減する工夫も行った．

プログラム上では，5 つの属性をすべて 64 ビットの整数に変換して扱った．時刻は，定義域の始点である 2010 年 1 月 14

4. 6. 1 部分集約結果参照の効率化

日 0 時ちょうどからの経過秒数に変換した．それ以外の 4 つのグリッドは木構造をなすため，親子関係が存在する．アルゴ

属性はいずれも 1000 倍することで整数に変換した．

リズム 1 では，子に当たるグリッドだけでなく親のグリッドについても部分集約結果を保持・更新していた．これにより，ク
エリ処理のアルゴリズム 3 (2) を次のように効率化できる．

表 1 室内気象データのうち実験に用いた属性の概要
属性名 種類

定義域

時刻

日時

[2010 年 1 月 14 日, 2014 年 4 月 11 日]

グリッド番号が x ⊕ 0 および x ⊕ 1 (x は 1 文字以上のビット

気温

小数[0, 40]列) であるグリッドがクエリ範囲に完全に包含されていたとす湿度

小数[0, 70]る．この二つのグリッドの部分集約結果を参照する代わりに，

照度

小数[0, 100]

それらの親であるグリッド x の部分集約結果を用いても結果は風速

小数[0, 70]

変わらない．このようにすることでデータベースへのアクセス量を削減できる．この手続きは，再帰的に適用できる．
図 2 の例では，グリッド 00110 (= 0011 ⊕ 0) と 00111 (=0011 ⊕ 1) の代わりにグリッド 0011 (図 1(d) を参照のこと) の部分集約結果を参照すればよい．
この効率化は，クエリ範囲が大きく，したがってそれと交わるグリッドの数も多くなるときに有効であると考えられる．

5. 2. 2 拡張室内気象データ
5. 2. 1 節の室内気象データよりもさらに大きな規模のデータで実験を行うため，次のように室内気象データを拡張した．
まず，室内気象データのうち 2011 年から 2013 年までの 3 年分のデータ (1,492,314 件) を取り出した．このデータについて，
時刻を 3 年ずつ遅らせるようにして元のデータ数の 7 倍に複製

4. 6. 2 データの全スキャン省略

した．このようにして生成された 2011 年から 2031 年までのアルゴリズム 3 (3) において，集約演算が最大値または最小

21 年分の疑似的なデータ 10,446,198 件 (約 1,000 万件) を「拡値の場合，すでに得られた集約結果から全スキャンを省略でき

張室内気象データ」と呼ぶことにする．

る場合がある．最小値を例に取ると，アルゴリズム 3 (2) およ

5. 3 実 験 内 容

び (3) の途中で得られた集約結果 (最小値) がグリッドの最小

拡張室内気象データ (約 1,000 万件) に対して風速の最小値

値より小さければ，集約結果の更新は発生し得ないので，全スと総和を求める範囲クエリを行った．このクエリ問い合わせは，キャンを省略できる．最大値についても同様である．

Region Server でない 3 台の計算機をクライアントとし，各ク

5. 評 価 実 験ライアントのスレッド数を 1 から 32 まで変化させて最大 96 並列で行ったほか，1 台の計算機でスレッド数を 1 から 8 まで変提案手法のパフォーマンスを評価するため，クエリ処理のス化させた問い合わせも行った．各スレッドは 50 個のクエリ問

ループットについて RDB と KVS をそれぞれ単体で使用した

い合わせを行った．用いた範囲クエリは，風速以外の 4 つの属

ときと比較する評価実験を行った．

性を範囲とする 4 次元範囲クエリであり，クエリ範囲は次の通5. 1 実 験 環 境りである．まず，時刻の範囲は幅が 360 日であり，その開始位

10 台の計算機から構成されるクラスタ上で PostgreSQL，

置は乱数を用いて定義域内で一様に移動させた．また，時刻以HBase を動作させて実験を行った．このうち，Region Server

外の属性の範囲は次の通り固定した．

気温：[15, 35]，湿度：[20, 40]，照度：[80, 95]

表 3 提案手法における各種統計手法

提案手法でのデータ空間は，範囲クエリに用いる 4 つの属性を軸とする 4 次元空間とした．このうち，時刻の定義域は 2011 年 1
月 1 日から 2032 年 1 月 1 日であり，それ以外の 3 属性の定義域
は，表 1 に準ずる．グリッド分割に関するパラメータは，グリッド
サイズを Nsize = 50, 125, 250, 500, 1000, 2000, 4000, 8000の 8 通りに変化させ，分割閾値は Nthreshold = Nsize × 10 とした．初期状態における分割を決定する Ltime は，360 日とした．
データの挿入に先立って HBase テーブルを 12 個の Regionに分割し，各 Region Server に 2 つの Region を割り当てた．
提案手法では，データの挿入後に HBase テーブルに対するフラッシュとメジャーコンパクションを行った．これは，提案

提案
(50)

提案
(125)

提案
(250)

提案
(500)

提案
提案
提案
提案
(1000) (2000) (4000) (8000)

1
⃝
1,736
470
165
58
20
7
1
0
2
⃝
477
180
77
32
12
4
1
0
3
⃝
46,478 34,877 25,386 18,420 12,519 8,533 2,691787
4⃝40.8% 31.0% 21.0% 14.2%
8.8%
5.5%
1.6%
0.4%
5
⃝
3,294 1,641
905
515
290
165
89
52
6
⃝
1,845
890
446
239
127
74
39
20
7
⃝
91,996 122,834 142,624 169,459 192,659 221,188 243,363 280,469
8 100.0% 100.0% 99.0% 96.6% 91.2% 83.8% 64.5% 26.4%⃝
9 384,279 143,758 67,941 32,699 16,192 8,000 3,916 1,976⃝
1 ：部分集約結果を再利用できたグリッド数 (4. 6. 1 節の効率化前) の⃝平均，手法についても実験を行った．PostgreSQL では，範囲クエリ

2 ：部分集約結果を再利用できたグリッド数 (効率化後) の平均，⃝3 ：⃝
1 (または⃝2 ) のグリッドに含まれていた総データ数の平均，⃝4 ：再利用率 (クエリ範囲にあったデータ数に対する⃝3 の割合)，⃝
5 ：部分集約結果を再利用できなかったグリッド数 (効率化前) の平均，⃝
6 ：部分集約結果を再利用できなかったグリッド数 (効率化後) の平均，⃝
7 ：⃝
5 (または⃝6 ) のグリッドに含まれていた総データ数の平均 (=⃝の対象となる 4 つの属性に B-Tree の複合インデックスを張った総和の集約演算においてスキャンを行ったデータ数)，

手法では HBase テーブルに対して大量の put と delete を行う
ため，コンパクションを行っていないと提案手法に関係のない箇所でパフォーマンスの低下が発生する可能性を避けるためである．なお，同じ作業は比較対象の HBase でも行った．
また，比較対象として PostgreSQL と HBase を単体で用いる

上でデータを挿入し，クエリ処理を行った．HBase では，データの属性のうち時刻のバイナリ表現をキーとしてデータを挿入した．クエリ処理では，時刻に関するキーの範囲検索を行って

8 ：スキップ率 (最小値の集約演算において，⃝
6 のグリッドのうち全⃝データスキャンを省略できたものの割合)，

9 ：データ空間内に存在する総グリッド数．
⃝

範囲内にあるすべてのデータをスキャンし，クエリ範囲に含ま

5. 4 実 験 結 果
クエリにより選択されたデータ (クエリ範囲内にあったデータ) は平均で 104,271 件であり，選択率は 1.0%であった．
各手法におけるデータ挿入のスループットを次の表 2 に示す．
「提案 (Nsize )」は，グリッドサイズが Nsize のときの提案手法を示している．以降の図表でも同様である．表 2 におけるス

1200

クエリスループット(クエリ/秒)

れているものについて集約演算を行った．

ループットとは，データ数を挿入にかかった時間 (秒) で割った値である．なお，提案手法と HBase(単体) におけるテーブルの提案(250)
提案(500)1000
800

提案(1000)
提案(125)600

提案(2000)

400

提案(50)
提案(4000)200
提案(8000)
PostgreSQL(単体)0
HBase(単体)
0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150
同時接続クライアント数

フラッシュやメジャーコンパクションの時間は含まれていない．

図 4 最小値のクエリスループット

提案手法のスループットは PostgreSQL，HBase のいずれよ
スループットが高いのは，グリッド分割の発生回数が少ないためであると考えられる．
表2
手法

各手法におけるデータ挿入スループット
提案
(50)

提案
提案
(125) (250)

提案
提案
提案
(500) (1000) (2000)

スループット 4,129 5,798 6,837 7,733
手法
スループット

8,456

8,959

提案
提案
PostgreSQL HBase(4000) (8000)
(単体)
(単体)

9,217

9,318

45,887180

クエリスループット(クエリ/秒)

りも低かった．また，提案手法でグリッドサイズが大きいほど提案(50)

16040

提案(125)
提案(250)
提案(500)
提案(1000)
提案(2000)
提案(4000)
提案(8000)
PostgreSQL(単体)20

HBase(単体)

140
120
100
80

60

0
0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150
同時接続クライアント数

63,491
図 5 総和のクエリスループット

各手法のクエリスループットを，最小値のクエリについて図4 に，総和のクエリについて図 5 に示す．さらに，提案手法における各種統計情報を表 3 に示す．
これらの結果をまとめる．図 4，5 を見ると，最小値，総和の両クエリにおいて，提案手法はすべてのグリッドサイズでHBase を単体で用いた手法よりもクエリスループットは高かった．また，PostgreSQL と比較すると，Nsize = 8000 のときが

ほぼ同じスループットであり，それ以外では高いスループット

ることで，両者の利点を活用して提案手法を実現した．

を実現できた．同時接続クライアント数を 96 とした各クエリに評価実験として，室内気象センサのデータをもとに生成したおいて，提案手法が最も高いスループットを実現できたグリッ

約 1,000 万件のデータに対する 4 次元の範囲クエリを同時に 96

ドサイズと，そのときの従来手法に対するスループットの比率

並列で処理する実験を行った結果，提案手法はグリッドサイズ

は次の通りである．

を適切に設定することで，HBase を単体で用いた場合に比べ最小値 Nsize = 250 のとき，PostgreSQL に対して 13.8 倍，

HBase に対して 36.3 倍．
総和 Nsize = 50 の と き ，PostgreSQL に 対 し て 2.9 倍 ，HBase に対して 5.4 倍．
上記結果について考察する．まず，最小値の集約演算につい5.4〜36.3 倍，PostgreSQL に対しても 2.9〜13.8 倍の高いクエ
リスループットを実現した．しかし，グリッドサイズを小さくすると実データのスキャン量は減少するものの，グリッドの数が増加するためにクエリスループットは必ずしも高くならないという問題が明らかとなった．また，データ挿入のスループッ
トも従来手法に及ばなかった．

8 を見ると，グリッドサイズが小さくなるにつれてて表 3 の⃝今後の課題としては次のようなものが挙げられる．まず，評

スキップ率が高くなっていることが分かる．これが高いスルー

価実験で用いた範囲クエリは，時間軸についてランダムに移動

プットを実現できた主な理由である．このようにスキップ率がさせて生成したものであったが，ユーザが与えるクエリには何十分高い場合，クエリと一部が交わるグリッドに含まれるデー

らかの傾向が存在すると考えられる．その傾向に応じたグリッ

タのうちスキャンするものの数は少ないので，クエリ処理時間

ド分割を行うことでクエリ処理時間を短縮させることが課題のは部分集約結果の参照時間，すなわちクエリと交わるグリッド一つである．また，実際のシステムにおいて，センサデータは

2 ，⃝6 から，その値はグリッドサイ
数に支配される．表 3 の⃝

複数の箇所から同時に挿入される．そのような状況の下でも適ズが小さいほど多くなっている．これが原因で，グリッドサイ

切にデータ挿入がなされるよう排他制御を行うことが課題であズが小さい Nsize = 50, 125 では，スキップ率が 100.0%でありる．また，データ挿入のスループットを改善することも課題でながらスループットがそれほど高くならなかったと考えられる．

ある．

一方，総和のクエリ処理時間はスキャンを行ったデータ数7 ) に支配されるはずである．その値はグリッドサイ( 表 3 の⃝謝辞

ズが小さいほど減少しており，それにつれてスループットが高本研究の一部は，科研費基盤研究 (B)(課題番号：26280115)，

くなっていることが図 5 から分かる．ここで，同時接続クラ基盤研究 (B)(課題番号：15H02701) の支援による．ここに記し

イアント数 p を固定したとき，クエリ処理の応答時間が単純て謝意を表す．

にスキャンを行ったデータ数 DNsize に比例すると仮定すれば，
スループット Tp は DNsize に反比例することになる．したがって，Tp · DNsize = (一定) が成り立つはずであるが，p = 96 のとき，この値はグリッドサイズが小さくなるにつれて緩やかに減少する．グリッドサイズが小さいほどクエリと一部が交わる
グリッドの数は多くなるが，これは，全データスキャンを行う
際に HBase テーブルに対して細かな範囲検索が多数行われることを意味する．したがって，ディスクのランダムアクセスな
どのオーバーヘッドが生じて応答時間が長くなり，Tp · DNsizeの値が減少したと考えられる．このことから，グリッドサイズ
を小さくしていくとクエリスループットが減少に転じる点，すなわち最大となる点が存在すると予想される．
上記の結果から，提案手法はグリッドサイズを適切に設定することで，従来手法よりも高いクエリスループットを達成できることが判明した．

6. お わ り に本研究では，RDB と KVS を相互に利用して，多次元デー
タに対する集約演算を効率化する手法を提案した．多次元デー
タを複数のグリッドに分割した上で，あらかじめ計算しておいたグリッドごとの部分集約結果を再利用する．その際，膨大な量に上る実データや頻繁に更新される部分集約結果を KVS(HBase) で保持し，実データほど情報量は多くないが複雑な構造を持つグリッド分割の情報を RDB (PostgreSQL) で保持す

文

献[1] 増永良文, “リレーショナルデータベース入門 [新訂版]”, サイエ
ンス社, 2003.
[2] Avinash Lakshman, Prashant Malik, “Cassandra - A Decentralized Structured Storage System”, ACM SIGOPS Operating Systems Review, Volume 44, Issue 2, pp. 35–40, 2010.
[3] Korry Douglas, Susan Douglas, “PostgreSQL: a comprehensive guide to building, programming, and administering
PostgreSQL databases”, SAMS publishing, 2003.
[4] Fay Chang, Jeﬀrey Dean, Sanjay Ghemawat, Wilson C.
Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, Robert E. Gruber, “Bigtable: A Distributed Storage System for Structured Data”, OSDI ’06,
pp. 205–218, 2006.
[5] Joseph M. Hellerstein, Jeﬀrey F. Naughton, Avi Pfeﬀer,“Generalized Search Trees for Database Systems”, Proceedings of the 21st VLDB Conference, pp. 562–573, 1995.
[6] 小山田昌史, 陳テイ, 成田和世, 荒木拓也, “PA-Proxy: SQL-onHadoop におけるデータ集計処理を精度の劣化なく高速化する
フレームワーク”, DEIM 2015, E5-6, 2015.
[7] Shoji Nishimura, Sudipto Das, Divyakant Agrawal, Amr
El Abbadi, “MD-HBase: design and implementation of anelastic data infrastructure for cloud-scale location services”,
Distributed and Parallel Databases June 2013, Volume 31,
Issue 2, pp. 289–319, 2013.
[8] G.M. Morton, “A computer oriented geodetic data base anda new technique in file sequencing”, Tech.rep., IBM Ottawa,
Canada, 1966.