DEIM Forum 2016 D3-5

クエリへ適応的に構築される木構造によるデータ集約処理の高速化
小山田昌史†

中台 慎二†† 日本電気株式会社 情報・ナレッジ研究所 〒 211-8666 神奈川県川崎市中原区下沼部 1753
E-mail: †m-oyamada@cq.jp.nec.com, ††s-nakadai@az.jp.nec.com
あらまし 本稿は，RDBMS におけるデータ集約処理の高速化方式である部分集約法のさらなる高速化方式を提案す
る．部分集約法は，テーブルからレコード集合のグループを取り出して各グループで集約値を事前に計算し，その後の集約処理では各グループで事前に計算した集約結果を再利用する方式群である [9, 13, 19] ．本稿は，実際のデータ分
析でよく見られる「ユーザがアクセスするデータ領域に偏りがある場合」に部分集約法が高い性能を示すグループ作
成方法である APA 木 (Adaptive Partial-Aggregation Tree) を提案する．APA 木はセグメント木をユーザのクエリに対して適応的に成長・縮退させることにより，ユーザが頻繁にアクセスするデータ領域については細かく，あまりアクセスされないデータ領域については粗く，グループを作成して集約値を計算し保持する．本稿は APA 木の管理方法と，

APA 木と部分集約法を利用した集約処理について述べる．そして実験により，APA 木が水平分割方式と比べ高性能であることを見せる．
キーワード

集約処理，マテリアライズドビュー，適応的，セグメント木，キャッシュ置換アルゴリズム

1. 背rarely accessed range

景APA-Tree(in-memory)
SMA(in-memory)[0, 7][8, 15]

Min: 24
Max: 50
Count: 3

Min: 3
Max: 50

Min: 2
Max: 30

Min: 30
Max: 15

Min: 19
Max: 43

frequently accessed range[0, 15]

Min: 22
Max: 60[8, 11][8, 9]

Data(in-disk)

Min: 3
Max: 15
Count: 2

1 3 6 8 9 10 10 10 10 11 11 11 11 11 11 11 11 12 13 13 15 15 15

attribute 2

50 32 24 3 15 4 2 9 4 30 15 19 22 30 15 19 22 26 43 30 60 45 22

a record (tuple)a group

図 1 水平分割方式 [9, 13, 19][10, 10][11, 11]

Min: 2
Max: 9Count: 4

Min: 15
Max: 30
Count: 8

attribute 1(key)

1 3 6 8 9 10 10 10 10 11 11 11 11 11 11 11 11 12 13 13 15 15 15

attribute 2

50 32 24 3 15 4 2 9 4 30 15 19 22 30 15 19 22 26 43 30 60 45 22

a record (tuple)

データの最大値や標準偏差などの集約値を計算するデータ集

Min: 22
Max: 60
Count: 6[10, 11]Data(in-disk)
attribute 1(key)[12, 15]a group

図 2 APA 木 (提案方式)

約処理は，データベースシステムにおける重要な処理である．
データ集約処理は古典的な OLAP における基礎的な処理であるが，近年では機械学習処理の入力データ整形処理にも多用されるなど，複雑なデータ分析処理に必須の処理となっている．特に，機械学習処理を含むようなデータ分析処理では，分析処理
は一度の集約処理で終了することはなく，データ分析者はイン
タラクティブに集約処理やその後の分析結果を吟味しながら，何度もデータの集約処理を繰り返す．効率的にデータ分析のサ
イクルを回すためにはデータ集約処理で瞬時に結果を得られることが望ましく，データ集約処理の高速化は重要な課題といえる．

RDBMS においてデータ集約処理を高速化する方針のひとつある [9, 13, 19] ．代表的なものに，Moerkotte による SMA(Small

Materialized Aggregates) [13] や，Graefe らによる Zone Filter [9]がある．本稿では，この方針にもとづく手法群を部分集約法(Partial-Aggregation Method) と呼ぶ．これまで提案されてきた部分集約法 [9, 13, 19] は，グループを作成する際，図 1 のように，テーブル内のレコード群をキー属性でソートするなど特定の順序で並べ，一定数のレコードを先頭から順に取り出してグ
ループとしてきた（注 1）．本稿はこのグループ作成方法を水平分割方式 (Horizontal-Partitioning Approach) と呼ぶ．
本稿は実際のデータ分析でよく見られる「ユーザがアクセスするデータ領域に偏りがある場合」に水平分割方式よりも高は，テーブルからレコード集合のグループを取り出して各グ
ループで集約値を事前に計算し，その後の集約処理では各グルー（注 1）：RDBMS ではテーブルをパーティションへと水平分割し，各パーティショ

プで事前に計算した集約結果を可能な限り再利用するものでンで各属性毎に集計値を計算することに対応する．

い性能を示すグループ作成方法である APA 木 (Adaptive Partial-

Algorithm 1: 部分集約法での水平分割方式による選択演算

Aggregation Tree) を提案する．APA 木はセグメント木をユーザと集約演算の実行アルゴリズムのクエリに対して適応的に成長・縮退させることにより，ユーザが頻繁にアクセスするデータ領域については細かく，あまり

Input: B グループ (リレーション R の被覆であり∪B = {Bi }i∈I , R = i∈I Bi )アクセスされないデータ領域については粗く，グループを作成

Input: σC 選択演算

して集約値を計算し保持する（図 2）．この場合，頻繁にアクInput: f 集約演算

セスされる領域については水平分割方式と比べ細粒度のグルー

Input: g 集約演算 f のコンバイナ
Data: a1 , . . . , a|B| 事前に計算された集約結果 (ai = f (σC (Bi )))プを作成することができ，その結果として集約結果の再利用性

Data: p1 , . . . , p|B| コンバイナに渡すためにつかわれる，グループが向上する．本稿は APA 木の管理方法と，APA 木と部分集約

ごとの集約結果を格納する変数法を利用した集約処理についても述べ，ユーザがアクセスする

Output: f (σC (R)) 集約結果

データ領域に偏りがある場合に APA 木が水平分割方式と比べ1効率的となることを見せる．

2

本稿の構成は次のとおりである．2. 節で部分集約法について

foreach Bi ∈ B do
if σC (Bi ) = ∅ then
（Skip）グループ Bi 内のタプルはひとつも集計対象にな

3

らないため処理をスキップ

述べる．3. 節で APA 木について述べる．4. 節で実験結果について述べる．5. 節で関連研究について紹介したあと，6. 節でま

4

とめる．

5

pi ← 0else if σC (Bi ) = Bi then
（Reuse）グループ Bi 内の全てのタプルが集計対象となる

6

2. 部分集約法

ため，事前にグループ Bi について計算した集約結果を再利用することができる

はじめに，本稿で高速化に取り組む部分集約法の基本アイ

8

部分集約法の基本的な発想は，二次記憶やリモートノード

pi ← ai7

ディアについて述べる．

else（Read）グループ Bi 内のいくつかのタプルが集計対象に

9（クラウド）などのアクセスコストの高い領域に格納されていなるため，グループ Bi 内のデータを読み込んで集約結果

るテーブルについて事前に集約計算をおこない，その集約結果
のみをアクセスコストの低い主記憶などに保持し，その後の集約処理では事前計算結果を可能な限り使い回すことで，アクセを算出する必要がある

11

スコストの高いテーブルへのアクセスを削減しようというものである [9, 13, 19] ．この際，より多くのクエリで結果が使いまpi ← f (σC (Bi ))10

集約結果 f (σC (R)) を各グループの集約値 p1 , . . . , p|B| から計算（再集約にコンバイナ g を利用）

12

return g(p1 , . . . , p|B| )わせるように，データ全体に対して集約値を計算するのではな
く，図 1 のようにテーブルを複数のグループに水平分割し，各グループで属性の最大値や最小値などの集約値を計算する．そして，以降の集約処理では集約演算が持つ性質を利用し，各グ
ループ毎に計算した集約値を組み合わせて再利用することで，最終的な集約結果を算出する．
本節の以降では，部分集約法の高速化対象となる集約演算とクエリについて説明する．

2. 1 部分集約法により高速化できる処理

可能な演算の例としては，リレーションの属性に関する最大値・最小値，和，標準偏差，平均，ヒストグラム，の計算があげられる．他方，部分計算可能でない演算の例としてはリレーションの属性のカーディナリティ計算（一意な値の数）がある．
部分集約法は，上記の部分計算可能な集約演算に選択演算が加わったクエリを高速化する．例えば，以下のレンジ集約クエ
リが部分集約法により高速化可能である．

まず，部分集約法が高速化できる集約演算の持つ性質を以下Sumincome (σ20<=R.age<=40 (R))

で定義する．
定義 2.1 (部分計算可能) 集約演算 f : R(A1 , ..., An ) → D，リ∪レーション B = m
i=1 Bi ∈ R(A1 , ..., An ) について，

f (B) = g( f (B1 ), ..., f (Bm ))2. 2 水平分割方式のアルゴリズム
次に，部分集約法での水平分割方式による集約値計算の具体的なアルゴリズムについて述べる．
アルゴリズム 1 は部分集約法での水平分割方式による選択演となる g : Dm → D が存在するとき，集約演算 f は部分計算

算と集約演算の実行アルゴリズムをあらわす．水平分割方式は可能 (partially computable) であるという．また，このとき g をリレーション R の各グループ Bi について，下記の三つのパター

f のコンバイナ (combiner) と呼ぶ．なお，R(A1 , ..., An ) は属性

ン（Skip, Reuse, Read）で部分的な集約結果 p1 , . . . , p|B| を取得

A1 , ..., An を持つリレーション R のスキーマである．

する．

す な わ ち ，部 分 集 約 可 能 な 演 算 と は ， Max(Maxage (B1 ) ∪（ 1 ） Skip: σC (Bi ) = ∅ ならば，グループ Bi 内のタプルはひMaxage (B2 )) = Maxage (B1 ∪ B2 ) のように，リレーションを複とつも集計対象にならないため処理をスキップできる．

数のグループに分割して別々に算出した集約値から，元々のリ（ 2 ） Reuse: σC (Bi ) = Bi ならば，グループ Bi 内の全てのタレーションに対する集約値を算出できる演算をいう．部分集約

プルが集計対象となるため，事前にグループ Bi について計算した集約結果を再利用できる．

[0, 15]

APA-Tree(in-memory)（ 3 ） Read: それ以外ならば，グループ Bi 内のいくつかの[0, 7]

タプルのみ集計対象になるため，事前に集約した結果が使いま[8, 15]

Min: 24
Max: 50
Count: 3

わせず，グループ Bi 内のデータを実際に読み込んで集約結果を算出する必要がある．

[8, 11][8, 9]

そして，水平分割方式はこれらの部分的な集約結果をコンバイ

Min: 3
Max: 15
Count: 2

ナ g によって再集約することで，最終的な集約結果 f (σC (R)) を算出する．

Min: 22
Max: 60
Count: 6[10, 11][10, 10][11, 11]

Min: 2
Max: 9Count: 4

Min: 15
Max: 30
Count: 8

Data(in-disk)

部分集約法の中では各グループ Bi が Skip, Reuse, Read のど[12, 15]

れになるかを，グループの中に含まれているデータにアクセスすることなく，判定する必要がある．[19] はこの問題に取り組
み，グループの持つ集約値のみを用いて効率的に Skip, Reuse,

attribute 1(key)

1 3 6 8 9 10 10 10 10 11 11 11 11 11 11 11 11 12 13 13 15 15 15Read の判定をおこなう方式を提案している．

attribute 2

50 32 24 3 15 4 2 9 4 30 15 19 22 30 15 19 22 26 43 30 60 45 22

a record (tuple)

3. APAa group木

図 3 APA 木の構造

前節で，部分集約法の概要と，そのグループ作成方式のひとつである水平分割方式について述べた．本節は，ユーザのアクセスするデータ領域に偏りがあった場合に水平分割方式よりも効率的となるグループ作成方式 APA 木 (Adaptive Partial-Aggregation

Tree) を提案する．（注 2）
APA 木は水平分割方式と同様に，部分集約法におけるデータの集約単位であるグループを作成し，集約値を管理する方式である．APA 木は水平分割方式と比較すると，（ 1 ） 水平分割方式がデータを均等のサイズでグループ化す
るのに対し，APA 木は頻繁にアクセスされるデータ領域ほど細かなグループ（=再利用できる可能性が高い）を作成するため，ユーザのアクセスするデータ領域に偏りがあった場合に集約値の再利用性が高く効率的である．

APA 木は セグメント木とは異なり，バランスされた完全二分木ではない．セグメント木が値域をまんべんなく再帰的に二分割してゆくのに対し，APA 木はユーザに頻繁にアクセスされる領域をより細かく分割し（その範囲のリーフノードは深くなり），あまりアクセスされない領域は粗く分割する（その範囲のリーフノードは浅くなる）．このアクセス頻度に応じた分割
は，ユーザのクエリに応じて適応的に木が成長・縮小することで実現される．図 3 の APA 木は，[0, 7] の領域にあまりアクセスせず，[8, 15] の領域，中でも [10, 11] の領域に頻繁にアクセスした結果となっている．APA 木は細分化する領域を頻繁にアクセスされる領域に限定するため，セグメント木と比べてノード数が少なくなり，消費メモリ量も少なく済む．

（ 2 ） 水平分割方式が集約計算時に全てのグループの集約値

3. 2 APA 木と部分集約法によるレンジ集約クエリの評価を集計し再集約しなければならないのに対し，APA 木はグルー
プを木構造で管理するため，再集約計算時に計算に影響しない

Algorithm 2: evalRangeAggregationQuery(query): 部分集約

グループの枝刈りがおこなえ，再集約計算が効率的である．

法での APA 木によるレンジ集約クエリの評価アルゴリズムという違いを持つ．

Input: query: レンジクエリ

3. 1 APA 木の構造

Output: レンジクエリ query の対象となるデータに対する集約結果

APA 木はデータのキー属性を用いてデータをグループ化し，Data: rootNode: APA 木のルートノード
Data: TREE SIZE LIMIT: APA 木のノード数上限値

グループ内での集約値をインメモリで管理する木構造である．
図 3 に APA 木の例を示す．APA 木はセグメント木と同様，ノードがキー属性の値域を再帰的に二分割してゆき（各ノードがキー属性のある範囲を担当し），葉となるノードがその範囲に

1// 集約値を計算

2

aggregations ← computeAggregationForNode(rootNode, query)3

while rootNode.treeSize > TREE SIZE LIMIT do

4

属すデータ（グループ）へのポインタと，グループ内のデータ// （木の縮小）最もアクセスされていないノードを探し，その兄弟ノードとマージについて計算した集約値（属性の最大値，最小値，グループ内

5

leastAccessedLeaf ← rootNode.findLeastAccessedLeaf()のデータ数）を保有するような二分木である．図 3 ではキー属

6

leastAccessedLeaf.parent.mergeChildren()性の値域 [0, 15] が再帰的に分割されてグループが作成され，集

7

return aggregations

約値が各グループについて計算されている様子が確認できる．

（注 2）：なお，APA 木は，リレーションがある属性についてソートされており，値の追加や削除によって成長・縮小する木構造と異なり，APA

ユーザのクエリがその属性に対するレンジクエリである場合に特に有用である．

木はレンジ集約クエリを評価するたびに成長・縮小する．以下，

近年のデータ分析で一般的なタイムスタンプ付き実績データの分析が，これに該APA 木と部分集約法によるレンジ集約クエリの評価の流れを説当する．例えばクラウド型 DWH のひとつである Treasure Data [2] では，データ

明し，APA 木が処理のなかでいかに成長・縮小してゆくかにつは時刻情報によりパーティショニングされており，ユーザのクエリには基本的に時刻属性に対するレンジ条件が含まれることが想定されている．

いて述べる．

Algorithm 3: computeAggregationForNode(node, query): ノー
ド node 以下のデータに対する部分集約法での APA 木によるレンジ集約クエリの評価アルゴリズム

1

集約値の再利用はできない．このとき (a) そのノードが子ノー

Input: query: レンジクエリ

ドを持つならば，下位のノードはより細粒度に統計値を計算しOutput: node 下の query 対象となるデータについての集約結果ており再利用できる場合があるため，下位ノードについて再帰// この node 下のデータが query の範囲内 / 範囲外にあるのかを的に探索を続ける． (b) それ以外のとき（そのノードがリーフ

compare 関数をつかって確認する

ノードである場合）は，集約値の再利用ができないため，将来

answer ← compare(node.range, query)3

if answer = OUTSIDE QUERY then// node 下のデータは query の範囲外なので，それ以上の探索は
しない

5
6
7

8
9

（ 2 ） も し「 い く つ か の デ ー タ が ク エ リ の 範 囲 内(PART DATA IN QUERY)」であれば，そのノードの粒度ではInput: node: 集約値の計算対象ノード

2

4

りも下位のノードの探索を打ち切る（Skip）

return null
if answer = ALL DATA IN QUERY then

同様のクエリが来た場合に集約値が再利用できるようにそのノードを分割し，各ノードの集約値を二次記憶のデータを読み込んで計算する（Read）（ 3 ） も し「 す べ て の デ ー タ が ク エ リ の 範 囲 内(ALL DATA IN QUERY)」であれば，そのノードの関するデー// node 下のすべてのデータが query の範囲内なので，事前に計

タはすべてクエリの対象となっているため，ノード下のグルー

算した集約値を再利用

プに対して事前に計算した集約値を使いまわす（Reuse）

return node.getPrecomputedAggregations()
if answer = PART DATA IN QUERY then

以上のように，APA 木は木を再帰的にたどりながら部分集約法の Skip，Reuse，Read をおこなうため，クエリに関係のない10// node 下のいくつかのデータが query の範囲内のときノード（グループ）の探索を枝刈りすることができ，全てのグ

11

if node.isLeafNode() then

ループを走査する水平分割方式と比べ効率的である．また，あ（木の成長）リーフノードまで探索したが，再利用はでき12なかった．今後，この区間で再利用ができるように，ノードを分割してより細かな粒度で集約値を計算

node.split(query)13

るクエリで Read が発生した場合，APA 木は次にそのクエリが来た場合に Read が発生しないよう，木を成長させる．そのため，ユーザがアクセスするデータ領域に偏りがある場合，Readが発生せず，水平分割方式と比べ効率的となる．

14// 自身の子の集約値を再利用するため，再帰的に探索

15

leftAggregations = computeAggregationForNode(node.leftChild,

3. 3 キャッシュ置換アルゴリズムによる APA 木の肥大化防止

query)

木を成長させると Read が発生する確率は減るが，ノード数16rightAggregations =が増え，ストレージコストと探索コストが肥大する（注 4）．そこ

computeAggregationForNode(node.rightChild, query)

で，APA 木は最大のノード数 TREE SIZE LIMIT を設け，その17// 両方の子から得た集約値を部分集約法で併合して返却

制限下で最適な木を構築しようとする．ここでの最適な木とは，

18

return leftAggregations.merge(rightAggregations)「最もアクセスされる領域が最も深く，最もアクセスされない領域が最も浅い木」をいう．このため，APA 木は木を成長させた

APA 木と部分集約法をつかったレンジ集約クエリの評価アル
ゴリズムをアルゴリズム 2 とアルゴリズム 3 に示す．アルゴリ
ズム 2 は，APA 木をルートノードから再帰的に探索し，レンジ
集約クエリを評価する．あるノード以下のデータに対する集約値の計算は，アルゴリズム 3 がおこなう．アルゴリズム 3 は，ノードが• 「すべてのデータがレンジ集約クエリの範囲外 (OUTSIDE QUERY)」• 「いくつかのデータがレンジ集約クエリの範囲内(PART DATA IN QUERY)」• 「すべてのデータがレンジ集約クエリの範囲内(ALL DATA IN QUERY)」のどれになるかを判定し（注 3），そのノードに対する集約値を下記のように取得する．
（ 1 ） も し「 す べ て の デ ー タ が ク エ リ の 範 囲 外 (OUT-

SIDE QUERY)」であれば，そのノード以下のノードはクエリの対象外であり，探索しても無駄であるため，そのノードよ

あとにノード数が制限を超えた場合，キャッシュ置換アルゴリ
ズムにもとづいて「最もアクセスされていないリーフノード」
を探し，その葉ノードを兄弟ノードとマージする（アルゴリズ
ム 2）．これは近年提案されたレンジクエリ向け Bloom Filter である ARF (Adaptive Range Filter) [5] と同じ発想である．具体的なキャッシュ置換アルゴリズムとしては，例えば軽量で管理情報の少ない CLOCK [17] の利用が考えられる [5]．

3. 4 APA 木の成長と縮小処理
上で，APA 木ではクエリの実行時に木の成長・縮小を必要に応じておこなうと述べた．ここでは，具体的な APA 木の成長・縮小処理にいて説明する．

a ) リーフノードの分割処理 (木の成長)
リーフノードの分割処理は，あるリーフノードの担当する
キー属性値の領域を二つに分割し，元のリーフノードの配下にあったデータをキー属性の値に応じて両領域に分配した上で，それらの統計値を再計算し，新たなリーフノードを作成する．
例えば 図 4 の APA 木において，[0, 49] の年齢を担当するリー（注 4）：あらゆるクエリで Read が発生しないような APA 木の構築にはデータ数（注 3）：単純なレンジのオーバーラップ判定である．

n に対し O(n log n) の空間が必要となり，これを主記憶に置くことは困難である．

age (key): [0, 100]
[0, 50)[50, 100]age (key): [0, 49]
weight: {max: 92.0, min: 45.0, mean: 66.3, sum: 398.0, count: 6.0}
height: {max: 185.0, min: 162.0, mean: 171.7, sum: 1030.0, count: 6.0}

age (key): [50, 100]weight: {max: 93.0, min: 45.0, mean: 71.5, sum: 286.0, count: 4.0}
height: {max: 160.0, min: 140.0, mean: 148.5, sum: 594.0, count: 4.0}age (key): 10,18,20,25,30,38
weight: 78,92,64,45,51,68
height: 165,163,162,185,179,176

age (key): 50,65,70,75
weight: 45,86,93,62
height: 145,160,149,140

図4

深さが 1 の APA 木の例
age (key): [0, 100]
[0, 50)age (key): [0, 49][0, 25)age (key): [50, 100]weight: {max: 93.0, min: 45.0, mean: 71.5, sum: 286.0, count: 4.0}
height: {max: 160.0, min: 140.0, mean: 148.5, sum: 594.0, count: 4.0}[25, 49]age (key): [0, 24]weight: {max: 92.0, min: 64.0, mean: 78.0, sum: 234.0, count: 3.0}
height: {max: 165.0, min: 162.0, mean: 163.3, sum: 490.0, count: 3.0}

age (key): [25, 49]
weight: {max: 68.0, min: 45.0, mean: 54.7, sum: 164.0, count: 3.0}
height: {max: 185.0, min: 176.0, mean: 180.0, sum: 540.0, count: 3.0}

age (key): 10,18,20
weight: 78,92,64
height: 165,163,162

age (key): 25,30,38
weight: 45,51,68
height: 185,179,176

図5[50, 100]age (key): 50,65,70,75
weight: 45,86,93,62
height: 145,160,149,140

図 4 の APA 木で左のリーフノードを分割した後の APA 木

フノードを分割すると， 図 5 のように [0, 24] の年齢を担当すするデータ領域に偏りがある」場合に効果的となる．このことるリーフノードと，[25, 49] の年齢を担当するリーフノードのを確認するため，実験では以下の二種類のワークロードを人工二つが生成される．

的に生成し用いた．

b ) リーフノードの併合処理 (木の縮小)（ 1 ） ワークロード (a) は，まんべんなくデータがアクセス

リーフノードの併合処理は，二つの隣接する（同じ親ノード

されるケースを再現する．このワークロードは，次の手順で一を持つ）リーフノードの担当する領域を併合して新たなリーフ様分布から生成されたキー属性 age に対するレンジ集約クエリ

ノードを作成し，親ノードを新たなリーフノードで置き換え[l, l + w] 群からなる: まず，レンジの左端 l を一様分布から生成る．この際，新たなリーフノードの集約値を計算する必要があする．次に，レンジクエリのレンジ幅 w を，正規分布 N(µ, σ2 )るが，これは元々のリーフノード二つの持つ集約値を部分集約から生成する．

法によって集約することで計算できる．すなわち，実際のデー（ 2 ） ワークロード (b)〜(d) は，アクセスされるデータがタをスキャンして集約値を再計算する必要はない．

偏っているケースを再現する．このワークロードは，次の手順

4. 実

験

で Ziphian に従うよう生成されたキー属性 age に対するレンジ集
約クエリ [l, l + w] 群からなる: まず，レンジの左端 l を，Ziphian

本節では，実験によって APA 木と 水平分割方式を比較する．

に従うよう生成する．次に，レンジクエリのレンジ幅 w を，正4. 1 実規分布 N(µ, σ2 ) から生成する．アクセスするデータの偏りの強装実験では APA 木と 水平分割方式をそれぞれ実装し用いた．

さをコントロールする Ziphian のパラメータ s については，偏APA 木でマージ対象のリーフを選ぶアルゴリズムとしては LRUりの強さが結果に与える影響を見るため， s = 2, s = 3, s = 4 のポリシーの効率的な近似アルゴリズムである CLOCK [17] を用

三通りを選び，異なるワークロードとする．

いた．

それぞれのワークロードは，上記の手順で生成された 100 個の4. 2 データセット

クエリから構成した．なお，上記のワークロード生成において，実験ではレンジ幅を生成する正規分布のパラメータは µ = 5, σ2 = 10 にMembers(age INT, height DOUBLE, weight DOUBLE)固定した．
図 6 は，上記の手順で生成された各ワークロードのアクセス

なる，３つの属性を持つ人工データを生成して用いた．このうするデータ領域の分布をあらわした図である．図 6 から，一ち age 属性をクラスタ索引として用いた．各属性の値は一様分様分布がまんべんなくデータ領域全体へアクセスすることと，布から生成した．全ての実験を通して，データセットのレコー

Ziphian がパラメータ s の値が大きくなるほど特定のキー領域

ド数は 100K とした．

へ集中的にアクセスすることが確認できる．本節の以降では，

4. 3 ワークロード

これらのワークロードを提案方式である APA 木と従来方式で本稿で提案するグループ方式 APA 木は「ユーザがアクセス

ある 水平分割方式で処理し，クエリのアクセスするデータ領域

ことがそのまま性能向上に繋がるわけではない．また，グルーの偏りがこれら方式に与える影響を見る．

プ作成数を増やすと管理すべき集約値の数も増え，主記憶を圧

4. 4 I/O 量の比較迫する．以上から，グループ作成につかわれる属性の一意な属提案方式 APA 木の有効性を確認するため，上述の 100K の性値が小さい場合は従来方式水平分割方式が有効であるというレコードからなるデータセットについて，グループ作成方式として APA 木と 水平分割方式を選んで上述のワークロードを実行した際の，部分集約法の I/O 量 （注 5） を計測した．APA 木はことがいえる．

5. 関 連 研 究

データをクエリに応じて定められたグループ数の制限のなかで

5. 1 Data Skipping

動的にグループ分けし，水平分割方式はデータを指定されたグテーブルを複数のグループへ水平分割しグループ毎に軽量イループ数で静的に分割する．水平分割方式はグループ数が大き

ンデックスを持つという試みは，問合せの実行時にグループのくなるほど I/O 量が減るため [18]，APA 木との比較のために，スキャンを省いて高速化を図る Data Skipping の領域で研究され実験ではグループ数（APA 木ではグループ数の上限）が，32,てきた [15, 16]．これら Data Skipping 技術は軽量インデックス

64, 128, 256 であるときの四通りについてワークロード実行時

を，選択演算 σC でスキャン対象のブロック B のスキャン処理の I/O 量を計測した．

をスキップすることができるか，すなわち σC (B) = ∅ となるか

図 7，図 8，図 9，図 10 の各図は，グループ数が 32, 64, 128,を判定するために利用する．これに対し，部分集約法では軽量

256 であるときに，前述のワークロード内のクエリを順に実行

インデックスを，対象のグループの結果が選択演算により全てした際の累積 I/O 量をあらわしている．図中，APA-Tree は提案選択され部分計算結果が再利用できるか，すなわち σC (B) = B

方式，SMA は従来方式 [9, 13, 19] に対応する．図の横軸は順にとなるかの判定に活用する．Data Skipping の分野では近年グ実行されたワークロード内のクエリをあらわし，縦軸はクエリ

ループのスキップ効率を高めるためのレコードの並び順を求め実行時の I/O 量の積み上げ値をあらわす．すなわち，右端におる試み [16] があり，これは部分集約法で部分計算結果の再利用

ける縦軸の値は，ワークロード内のクエリを全て実行し終えた

効率を高めるために利用することができると考えられる．

時点での，トータルの I/O 量をあらわす．この値が小さいほど，

5. 2 SQL-on-Hadoop におけるファイルフォーマット

方式は有効であるといえる．

SQL-on-Hadoop は分散ファイルシステム HDFS 上に置かれた

4. 4. 1 データ領域の偏りが与える影響

データを問合せ対象とし，CSV をはじめとする様々なファイル

はじめに，ユーザのアクセスするデータ領域の偏りが提案方

形式のデータに対し直接 SQL の問合せを実行することができ

式と従来方式に与える影響を見る．図 7 は，グループ数が 32

る．このとき，システムの定めるファイル形式にデータを変換であるときの実験結果をあらわしている．図 7 から，全てのすることで問合せを高速化することも可能であり，特に集約処ワークロードで，提案方式 APA 木が従来方式である水平分割

理をはじめとするデータ分析タスクは列指向的であるため，列方式よりも少ない I/O 量でワークロードを実行できたことがわ

指向のファイルフォーマットがよく用いられている [1, 10, 12]．

かる．また，(a)〜(d) を比較することで，アクセス領域の偏り

近年注目を集めている列指向のファイルフォーマットに，Hiveが強くなる（Zipfian のパラメータ s の値が大きくなる）ほど，で用いられている ORC File [12] と，Impala で用いられている

その I/O 量の差が大きくなることが分かる．以上から，提案方

Apache Parquet [1] がある．これらは列指向のファイルフォー

式 APA 木が水平分割方式と比べ高性能であり，その性能差がマットであるが，同じ行に属す値ができるだけ同じノードにユーザのアクセスするデータ領域に偏りがあるほど大きくなる格納されるようにデータを分割して HDFS へ分散配置するたことがいえる．

め（注 8），行単位でのアクセスも効率的であるという特徴を持つ．

4. 4. 2 グループ数が与える影響

これは PAX [4] や RCFile [10] の考えにもとづく．また，ORC

つぎに，グループ数が提案方式と従来方式に与える影響を見File/Parquet は列方向のデータ圧縮やファイル内に格納された軽る．図 7〜図 10 を比較すると，グループ数を増やすほど両方式

量のインデックスを利用して問合せ時の計算量や I/O 量を削減

での総 I/O 量が小さくなることが分かる．また，グループ数をし，大幅な問合せの高速化を実現する [7]．

増やすほど APA 木と水平分割方式の性能差は縮まり，グループ

5. 3 ARF (Adaptive Range Filter)

数が 256 の場合では全てのワークロードで APA 木よりも水平σC (B) = ∅ の判定については，C がレンジクエリである場合

分割方式の方が有効となることが分かる．これは前述のとおり，に利用できるデータ構造 Adaptive Range Filter (ARF) が近年提水平分割方式ではグループ数がグループ分けの基準となる属性

案されている [6]．ARF は，問合せの条件としてある属性の範の一意な値の数に近づくほど，I/O 量が減るためである [18]（注 6）．

囲が指定された場合，グループ内にその条件を満たすレコー

しかし，水平分割方式ではグループ数 N に対して集約値の再集

ド群がひとつも存在しないかどうかを効果的に判定すること

約の計算量が O(N) であるため（注 7），グループ数を大きくするができる．Bloom filter のように，条件を満たすレコードがひ（注 5）：本稿では I/O 量として，参照されたレコード数を用いる．
（注 6）：究極的には，グループ分けの基準となる属性値で Group-by し，グループも小さい．

ごとに集約値を持つことで，I/O 量は最小となる．

（注 8）：ORC File では同じ行に属す値は必ず同じノードに格納されるが，Parquet（注 7）：APA 木の計算量は最良 O(log N)，最悪 O(N) であり，水平分割方式よりでは異なるノードに格納されてしまうことがある．

(a) 一様分布

図6(b) Zipfian (s=2)

Zipf (s = 4)
500
400
300
200
100
00 20 40 60 80 100120140
Accessed key

Frequency

Zipf (s = 3)
500
400
300
200
100
00 20 40 60 80 100120140
Accessed key

Frequency

Zipf (s = 2)
500
400
300
200
100
00 20 40 60 80 100120140
Accessed key

Frequency

Frequency

Uniform
500
400
300
200
100
00 20 40 60 80 100120140
Accessed key(c) Zipfian (s=3)(d) Zipfian (s=4)

各ワークロードでの，クエリのアクセスするレコードのキー値のヒストグラムを算出した
もの．Zipfian からクエリを生成した場合，パラメータ s の値が大きくなるほど，アクセスする領域に偏りが生まれることが確認できる．

100000
00

20

40 60
Queries

80(a) 一様分布

APA-Tree
SMA

20

40 60
Queries80

60000050000040000030000020000010000000(b) Zipfian (s=2)

APA-Tree
SMA

20

40 60
Queries80

60000050000040000030000020000010000000# of read (cumulative)

30000020000060000050000040000030000020000010000000# of read (cumulative)

APA-Tree
SMA# of read (cumulative)# of read (cumulative)

500000400000(c) Zipfian (s=3)

APA-Tree
SMA

20

40 60
Queries80(d) Zipfian (s=4)

図 7 APA 木と 水平分割方式で 100K のレコードに対して 32 個のグループを作成し，各ワーク
ロード内のクエリを順に実行した際の累積 I/O 量．

40 60
Queries

80(a) 一様分布

APA-Tree
SMA

20

40 60
Queries80

160000140000120000100000
80000
60000
40000
20000
00

(b) Zipfian (s=2)

APA-Tree
SMA

20

40 60
Queries80

35000030000025000020000015000010000050000
00# of read (cumulative)

20

180000160000140000120000100000
80000
60000
40000
20000
00

# of read (cumulative)

APA-Tree
SMA# of read (cumulative)# of read (cumulative)

3000002500002000001500001000005000000(c) Zipfian (s=3)

APA-Tree
SMA

20

40 60
Queries80(d) Zipfian (s=4)

図 8 APA 木と 水平分割方式で 100K のレコードに対して 64 個のグループを作成し，各ワーク
ロード内のクエリを順に実行した際の累積 I/O 量．

(a) 一様分布(b) Zipfian (s=2)

20

APA-TreeSMA
40 60 80
Queries(c) Zipfian (s=3)

40000
35000
30000
25000
20000
15000
10000
50000

# of read (cumulative)

20

APA-TreeSMA
40 60 80
Queries

60000
50000
40000
30000
20000
10000
00

# of read (cumulative)

20

APA-TreeSMA
40 60 80
Queries

80000
70000
60000
50000
40000
30000
20000
10000
00

# of read (cumulative)# of read (cumulative)

180000160000140000120000100000
80000
60000
40000
20000
00

20

APA-TreeSMA
40 60 80
Queries(d) Zipfian (s=4)

図 9 APA 木と 水平分割方式で 100K のレコードに対して 128 個のグループを作成し，各ワーク
ロード内のクエリを順に実行した際の累積 I/O 量．

とつも存在しないにも関わらず，存在すると判定してしまう

保持するデータ構造を提案している [11]．彼らの提案するデー

False-positive 性を持つのが特徴である．なお，[8] は ARF の対タ構造はアクセス頻度を考慮せず，全領域について均等に事前象とした問題を理論的に解析し，指定した False-positive 率を得計算をおこなうという点で，本研究とはコンセプトが異なる．

るためのデータ構造の理論的最小サイズなどについて議論して本研究と彼らの提案するデータ構造は相互補完的な関係にあり，いる．

彼らの提案するデータ構造に本研究で用いたアクセス頻度に応

5. 4 OLAP

じた成長と併合処理を組み合わせることで，多次元 OLAP におHo らは多次元 OLAP キューブにおけるレンジ集約計算の高ける集計値データのサイズを縮小できると考えられる．

速化のため，レンジ上の Prefix-Sum や Prefix-Max を計算して(a) 一様分布(b) Zipfian (s=2)

20

APA-TreeSMA
40 60 80
Queries(c) Zipfian (s=3)

35000
30000
25000
20000
15000
10000
50000

# of read (cumulative)

20

APA-TreeSMA
40 60 80
Queries

45000
40000
35000
30000
25000
20000
15000
10000
5000
00

# of read (cumulative)

20

APA-TreeSMA
40 60 80
Queries

80000
70000
60000
50000
40000
30000
20000
10000
00

# of read (cumulative)# of read (cumulative)

180000160000140000120000100000
80000
60000
40000
20000
00

20

APA-TreeSMA
40 60 80
Queries(d) Zipfian (s=4)

図 10 APA 木と 水平分割方式で 100K のレコードに対して 256 個のグループを作成し，各ワー
クロード内のクエリを順に実行した際の累積 I/O 量．

5. 5 サンプリングによる集約処理の高速化
集約演算の高速化アプローチのひとつは，データのサンプリングである．BlinkDB [3] は Hive を拡張し，HDFS 上の処理対
象データをサンプリングし近似結果を算出することで，集約演算を含んだ問合せへの応答時間を短縮している．BlinkDB は問合せへの応答時間と近似による誤差のトレードオフ関係をシス
テマティックに扱い，ユーザの要求する応答時間から，結果に生じる最大誤差を算出することができる．[14] にも同様の試み
がある．

6. 結

論

本稿は，実際のデータ分析でよく見られる「ユーザがアクセスするデータ領域に偏りがある場合」に部分集約法が高い性能を示すためのグループ作成方法として，APA 木 (Adaptive

Partial-Aggregation Tree) を提案した．APA 木はセグメント木をユーザのクエリに対して適応的に成長・縮退させることにより，ユーザが頻繁にアクセスするデータ領域については細かく，あまりアクセスされないデータ領域については粗く，グループを作成して集約値を計算し保持する．本稿は APA 木の管理方法と，APA 木と部分集約法を利用した集約処理について述べた．
そして，実験により，ユーザがアクセスするデータ領域に偏りがある場合 APA 木が水平分割方式と比べ効率的となることを
見せた．
文

献

[1] Parquet. http://parquet.io/.
[2] Treasure Data. https://www.treasuredata.com/.
[3] S. Agarwal et al. BlinkDB: queries with bounded errors and bounded
response times on very large data. In EuroSys, pages 29–42. ACM,
2013.
[4] A. Ailamaki et al. Weaving Relations for Cache Performance. In
VLDB, pages 169–180, 2001.
[5] K. Alexiou, D. Kossmann, P. Larson. Adaptive Range Filters for Cold
Data: Avoiding Trips to Siberia. PVLDB, 6(14):1714–1725, 2013.
[6] A. Eldawy, J. J. Levandoski, P. Larson. Trekking Through Siberia:
Managing Cold Data in a Memory-Optimized Database. PVLDB,
7(11):931–942, 2014.
[7] A. Floratou, U. F. Minhas, F. Özcan. SQL-on-Hadoop: Full
Circle Back to Shared-Nothing Database Architectures. PVLDB,
7(12):1295–1306, 2014.
[8] M. Goswami et al. Approximate Range Emptiness in Constant Time
and Optimal Space. In SODA, pages 769–775, 2015.
[9] G. Graefe, H. A. Kuno. Fast Loads and Queries. TLDKS, 2:31–72,
2010.
[10] Y. He et al. RCFile: A fast and space-eﬃcient data placement structure in MapReduce-based warehouse systems. In ICDE, pages 1199–

1208, 2011.
[11] C. Ho et al. Range Queries in OLAP Data Cubes. In SIGMOD, pages
73–88, 1997.
[12] Y. Huai et al. Major technical advancements in apache hive. In SIGMOD, pages 1235–1246. ACM, 2014.
[13] G. Moerkotte. Small Materialized Aggregates: A Light Weight Index
Structure for Data Warehousing. In VLDB, pages 476–487, 1998.
[14] S. Nirkhiwale, A. Dobra, C. M. Jermaine. A Sampling Algebra for
Aggregate Estimation. PVLDB, 6(14):1798–1809, 2013.
[15] V. Raman et al. DB2 with BLU Acceleration: So Much More than
Just a Column Store. PVLDB, 6(11):1080–1091, 2013.
[16] L. Sun et al. Fine-grained partitioning for aggressive data skipping.
In SIGMOD, pages 1115–1126, 2014.
[17] A. S. Tanenbaum. Modern Operating Systems. Prentice Hall Press,
Upper Saddle River, NJ, USA, 3rd edition, 2007.
[18] 小山田昌史 et al. データの部分集約による高速かつ正確なデータ
集計処理の実現. Technical Report 19, nov 2014.
[19] 小山田昌史 et al. PA-Proxy: SQL-on-Hadoop におけるデータ集
計処理を精度の劣化なく高速化するフレームワーク. In DEIM,
2015.