DEIM Forum 2014 D8-6

SSD を用いた大規模データベースにおける複数問い合わせ処理
高速化手法とその評価
鈴木 恵介†

早水

悠登†

横山

大作†

中野美由紀††

喜連川 優†,†††† 東京大学 〒 153–8505 東京都目黒区駒場 4-6-1†† 芝浦工業大学 〒 135–8548 東京都江東区豊洲 3-7-5††† 国立情報学研究所 〒 101–8430 東京都千代田区一ツ橋 2-1-2
E-mail: †{keisuke,haya,yokoyama,kitsure}@tkl.iis.u-tokyo.ac.jp, ††miyuki@sic.shibaura-it.ac.jp
あらまし

SSD は、高い転送レートを持つストレージデバイスとして注目されており、大規模データ処理を行うデー

タセンターで導入が進んでいる。SSD のアクセス特性としては、HDD の 100 倍から 1000 倍高速なランダム I/O や、
内部のフラッシュチップの並列構造による I/O の並列処理能力などが挙げられる。これらを生かす方法として、本稿
では、まずデータベースシステムのハッシュ結合演算において、データベースバッファ使用量を小さくしランダム I/Oが増加しても、I/O の処理コストが増加しないことを実測によって確認する。これにより、さらにキャッシュ使用効率が高まり、全体の処理性能が向上することを示す。また、メモリやキャッシュの使用量を抑えることで、複数の演算でこれらを分割して使用することが可能になる。これを利用し、並列問い合わせ処理の制御を行うことで処理性能向上を実現する方法を探求する。
キーワードリレーショナルデータベース, 結合演算, OLAP, SSD

1. は じ め に
現在の計算機では、大規模データ処理性能はストレージデ
バイスの転送レートに律速される場合が多い。従来の磁気ディトを持つ。また、SSD は内部に複数のフラッシュチップを搭載しており、並列 I/O 処理によってスループットを増加させることができる。問い合わせ処理においてこれらの特性を考慮する必要がある。

スク (HDD) のスループットは、CPU の高速化と比較すると

本稿ではまず、従来の関係データベースシステムの実装方式

進展が少なく、より高速、広帯域なストレージデバイスが求め

で SSD を用いる場合の問題点を明らかにするため、ハッシュ結られている。NAND flash-based Solid State Drive (SSD) は、合演算を対象として、実際の SSD を使用した関係データベー

NAND flash chip の集積技術の進歩により、大容量化、低価

スシステムにおいて、演算処理性能を詳細に解析した。その結格化が進み、データセンターなど大規模データ処理が必要な

果以下の事実を解明した。

現場において導入が増加しており、実例として Google [7] やFacebook [14] などでの使用も見られる。

•

ハッシュ結合演算では、データベースバッファ使用量が小さいほど、中間生成データファイルがフラグメント化し、ラ

本稿では、大規模データ処理アプリケーションの典型例であンダム I/O が増える。SSD を用いる場合は、HDD を用いる場

る関係データベースシステムにおける SSD の使用について論合と異なり、ランダム I/O の処理コストが小さいためデータじる。SSD は、HDD と同様のインターフェースで扱うことがベースバッファ使用量を縮小しても、I/O コストを小さく保つ可能なので、HDD を置き換えることで使用されることが多い。

ことができる。

しかし、SSD の内部アーキテクチャは、HDD のそれとは大き•SSD を用いる場合は、I/O コストが小さくなり、CPU

く異なるため、アクセス特性の違いが大きい。現在の多くの関コスト最適化の重要性が増す。ハッシュ結合演算では、ハッシュ係データベースシステムは、HDD の特性に基づいて設計されテーブルを小さくすることでデータアクセス局所性を高め、ており、SSD を用いる利点を十分に活かしていない。そこで本キャッシュミス数の増加を抑えることができる。そのため、デー

稿では、従来の関係データベースシステムの処理方式の見直し

タベースバッファ使用量を縮小し、ハッシュテーブルを小さくを行い、SSD のアクセス特性を活用するための処理方式についするのがよい。

て検討する。

データベースバッファ使用量を小さく設定することで、キャッSSD の I/O 特性としては、高いランダムアクセススループッ

シュに空きスペースが生じるため、これを他の処理で利用でき

トや並列 I/O 処理能力が挙げられる。まず SSD は、HDD のる。SSD は並列 I/O 処理が可能であるので、問い合わせの同ように機械的な動作部品を含まず、電子回路のみで構成される

時処理により I/O スループット向上が可能である。これらの理デバイスであるので、ランダムアクセス時のデータのシークの由から、SSD を用い複数問い合わせ同時処理を行うことで全オーバーヘッドがなく、高速な処理が可能である。HDD と比体の処理速度を向上できる。同時処理による効果を検証するた

較すると、100 倍から 1000 倍のランダムアクセススループッ

め、実際の関係データベースシステムにおいて、ハッシュ結合

演算の同時処理について試験的に処理性能の計測・分析を行い、以下の事実を明らかにした。

•

2. 2 ハイブリッドハッシュ結合 [15]Grace ハッシュ結合のビルドフェーズでは、必要となるメモ

全ての問い合わせに含まれるハッシュ結合演算のハッシュ

リはそれぞれのパーティションのストレージへの書き込みバッ

テーブルがキャッシュに収まるように、データベースバッファ

ファの分のみである。ハイブリッドハッシュ結合では、残りの使用量を設定することで、キャッシュミス数の増加を抑えつつメモリを S の 1 つ目のパーティション S1 のハッシュテーブル

同時処理数を増加できる。そのため、同時処理数増加に伴ってを保持するために利用する。メモリに保持される S1 のパーティ

キャッシュミス増加のオーバーヘッドが生じる従来の HDD にションと、それと同じハッシュ値をもつ R1 のパーティション

基づいた処理方式よりも、同時処理による性能向上が大きい。

は、ストレージに書き込まれることなく処理される。これによ•

同時処理数を過度に増加してしまうと、I/O フラグメン

り、結合処理の I/O コストを削減できる。

テーションにより I/O スループットが低下してしまう。この現2. 3 ハッシュ結合の処理コスト

象の発生を防ぐため、適切な同時処理数を選択するための問い

HDD の使用を前提としたデータベースシステムでは、大規合わせスケジューリング機構が必要となる。

模データを扱う問い合わせ処理において、大量の I/O の発生に

本稿の構成は以下の通りである。2. 節では、本研究の計測でよる性能低下を防ぐため、Grace ハッシュ結合かハイブリッド

用いるハッシュを用いた結合演算の処理方法とその負荷の性質

ハッシュ結合を用いることが一般的である。本稿では、以下ハについて述べる。3. 節では、本稿の計測で使用した計算機環境

イブリッドハッシュ結合を扱うものとする。

と計測の方法について示す。4. 節では、まず SSD の基礎性能

ハッシュ結合の I/O パターンは、ハッシュテーブルを保持すについて触れ、次に SSD 上のハッシュ結合における処理性能

るためのデータベースバッファの使用量によって決まる。これ

計測結果を示す。5. 節では、ハッシュ結合を行う複数の問い合

は、各リレーションのパーティションの数とサイズが、S の全

わせの同時処理性能を計測し、同時処理の制御について考察すてのパーティションのハッシュテーブルがデータベースバッファ

る。最後に、6. 節で、SSD を用いたデータベースシステムにつに収まるように決定されるためである。そのため、データベー

いての関連研究について述べる。

スバッファが小さいときは、多数の小さなパーティションファ

2. ハッシュを用いた結合演算

イルが作られることになり、フラグメンテーションが発生する。
フラグメント化したファイル群へのアクセスは、大量のランダ

意思決定支援システムなどに代表される、大規模データ処理

ム I/O を伴うため、ランダム I/O がシーケンシャル I/O と比を行うデータベースシステムでは、集約や射影、結合といった較して 100-1000 倍程度低速な HDD では、I/O スループット

データベース演算において、ハッシュテーブルを利用したアルが大きく減少してしまう。こうした理由から、HDD 上でのハッゴリズムが用いられることが多い。本稿では、SSD を使用したシュ結合では、大きなデータベースバッファが必要とされる。

データベースにおいて、ハッシュ結合演算の処理性能を計測対

一方で SSD においては、ランダム I/O はシーケンシャル I/O象とする。ハッシュ結合演算を用いるのは、データベース演算とほぼ遜色ない速度であるため、フラグメンテーションによるの中でも最も処理の負荷の高いものの一つであるためである。

I/O スループットへの影響が小さい。よって SSD 上のハッシュ

SSD の高い I/O スループットによる、計算やメモリアクセス

結合では、データベースバッファサイズを HDD 使用時より小にかかる CPU コストや、I/O コストの変化を確認し、全体のさくできる。

処理性能が向上することを明らかにする。

プローブフェーズにおいて構築されるハッシュテーブルは、

2. 1 Grace ハッシュ結合 [10]リレーション S のタプルとマッチングされる際に、繰り返し

説明の便宜のため、リレーション R と S の結合演算で、S

アクセスされる。これは、ハッシュテーブルのデータアクセス

に対してハッシュテーブルが作成されると仮定する。ハッシュに関して局所性が生じていることを意味する。つまり、データ

テーブルサイズが使用可能メモリサイズを越えるとき、Grace

ベースバッファのサイズは、プローブフェーズのキャッシュミ

ハッシュ結合では、R、S それぞれのデータを分割し、パーティス数にも関係しているということである。ハッシュテーブルサ

ション毎に結合処理が行われる。分割数は S の各パーティショ

イズがキャッシュサイズより小さければ、ハッシュテーブル構

ンに対するハッシュテーブルがメモリサイズを越えないように築後のハッシュテーブルアクセスではキャッシュミスが発生し決定される。

ない。ハッシュテーブルサイズはデータベースバッファサイズ

Grace ハッシュ結合は、ビルドフェーズとプローブフェーズの範囲に制限されているので、データベースバッファサイズをの 2 つのフェーズで処理される。まず、ビルドフェーズでは R

キャッシュサイズ以下に定めることで、キャッシュミス数を低と S それぞれのデータを結合のキーについて同じハッシュ関

減することができる。SSD を使用したハッシュ結合では、I/O

数で分割し、ストレージに書き込む。次に、プローブフェーズ

スループットを低下することなくデータベースバッファサイズ

では、R と S のパーティションで同じハッシュ値を持つものを縮小できるので、キャッシュミス数減少による性能向上が期(Ri 、Si とする) をストレージから読み込み、Si についてハッ待される。

シュテーブルを作成する。続けて Ri の各タプルについてハッシュテーブルを利用して結合条件のマッチングを行う。これを全てのパーティションに対して繰り返して処理が完了する。

3. 計測の環境と方法
表 1 に本稿で行った計測に使用した計算機環境を示す。スト10000CPU

Xeon X7560 @ 2.27GHz x 4

L3 Cache

24MB /CPU

DRAM

64GB

Storage (SSD)

ioDrive Duo x4 (8 Logical units, Software RAID0)

Storage (HDD)

SEAGATE ST3146807FC x12 (Software RAID0)kernellinux-2.6.32-220

File system

ext4

DBMS

PostgreSQL 9.2.4

Shared buﬀer

8GB

Throughput [MB/s]

表 1: 計測環境

1000
100
10
ssd sequentialread
ssd randomread
hdd sequentialread
hdd randomread

1
0.1
1k

レージのインターフェイスは、SSD は PCI-express、HDD は

10k

100k
I/O size [B]

1M

10M

fibre channel である。それぞれのストレージの I/O スケジュー

図 1: SSD と HDD におけるシーケンシャル/ランダム I/O ス

ラには、noop を適用した。またそれぞれのデバイスは、ソフト

ループット

ウェア RAID0(チャンクサイズ = 64kB) を構築し、ext4 ファ
イルシステムを適用している。
ハッシュ結合の処理性能はパーティション数とハッシュテー

1

SELECT count(∗) FROM lineitem, part

2

WHERE l partkey = p partkey

ブルサイズに依存する。データベースバッファが小さいとき、
パーティションファイル数が多くなり、ハッシュテーブルサイ

図 2: lineitem 表と part 表の結合演算を行う問い合わせ

ズは小さくなる。HDD を用いたデータベースでは、パーティ
ションファイル数が増えフラグメンテーションにより I/O ス

ケンシャル読み込み I/O スループットは、HDD より 3.1 倍程

ループットが低下するのを避けるため、データベースバッファ

度大きく、ランダム読み込み I/O スループットは、8.6 - 23.7

サイズを大きくとることが多い。データベースバッファサイズ倍大きい。I/O サイズが小さいほど、SSD と HDD のランダを介してトレードオフが生じているため、これをワークロー

ム I/O スループットの差は大きくなっている。シーケンシャル

ドを変化させるためのパラメタとして使用し、それぞれの値

I/O スループットが I/O サイズによらず一定であるのは、ファについて処理性能を計測する。work mem は PostgreSQL [2] のイルの先読みが機能しているためである。

パラメタであり、各データベース演算当たりの使用可能データ

4. 2 単一の結合演算を行う問い合わせによる計測

ベースバッファサイズを示す。PostgreSQL はハイブリッドハッ

SSD と HDD それぞれのデータベースに対して、単一の結シュ結合を使用しているため、全体のハッシュテーブルサイズ

合演算を含む問い合わせについて計測を行う。データベースのが work mem より小さいとき、パーティションはストレージに構築には、TPC-H ベンチマーク [3] のデータを Scale Factor

書き込まれない。

= 100 で用い、SSD と HDD 上に同一のデータベースを用意

問い合わせ実行時の、CPU 使用率の内訳については mp-

する。データベースの合計サイズは 112GB である。問い合stat(1)、I/O スループットは iostat(1)、L3 キャッシュ参照・ミ

わせは、図 2 を用いる。lineitem 表のそれぞれのタプルにつス回数は linux プロファイラ perf をそれぞれ使用して取得した。

いて、part 表の part key が一致する 1 タプルが結合される。

4. SSD 上でのハッシュ結合の性能

part 表、lineitem 表それぞれのサイズは 20GB と 80GB であり、ハッシュテーブルは part 表に対して作られ、合計サイズ

本節では、まず SSD の基礎的な I/O スループットを実測には約 800MB である。work mem を、64kB - 2GB の範囲で動かよって確認する。次に、結合演算を行う問い合せの処理時間をし、それぞれの値について、実行時間とその内訳を計測する。

計測し、SSD 上でのハッシュ結合では、HDD 上の場合と比較

図 3、4 に SSD と HDD それぞれにおける、各 work mem のして、I/O コストを小さく保ったまま、データベースバッファ

ハッシュ結合の実行時間とその内訳 (usr, system, iowait, irq,を小さくできることを示す。さらに、データベースバッファを

soft irq, idle) を示す。図中では、usr が CPU コストである。

小さくすることで、ハッシュテーブルサイズが小さくなり、アsys は主にカーネルでの I/O 発行処理時間を示し、iowait はス

クセス時のキャッシュミス数が抑えられ、処理性能を向上する

トレージデバイスからの I/O の結果待ち時間を示すので、sysことを示す。

と iowait の合計が I/O コストを表す。

4. 1 SSD の基礎 I/O 性能

work mem = 64kB − 16M B の L3 キャッシュサイズより小SSD の基礎 I/O 性能を計測するため、マイクロベンチマー

さな範囲では、SSD と HDD の結果に異なる傾向が見える。

クを実行する。ベンチマークプログラムは、単一のファイルにHDD では、work mem が小さいほど I/O コストが増加してい対して、指定された I/O サイズで、シーケンシャル I/O またる。これは、パーティションファイルのフラグメンテーション

はランダム I/O を繰り返し行うものである。

により、I/O スループットが飽和していることが原因である。

図 1 は、SSD と HDD における、各 I/O サイズでのシーケン

一方、SSD では I/O コストは総じて HDD より小さく、どの

シャル I/O とランダム I/O スループットを示す。SSD のシー点においてもほぼ変化が無い。これは、フラグメンテーション

1400

idle
soft
irq
iowait
sys
usr

1200

Time [s]1000
800

L3 キャッシュの参照・ミス数とミス率を示す。work mem > 32M B

L3 cache size以降でキャッシュミス回数が増加している。work mem の値の違いによる CPU コストの差について、例として work mem= 4MB と 1GB で比較する。キャッシュミス数は work mem =1GB の方が 7 × 109 回多く、本実験環境では DRAM のアク600

セス遅延が 100ns 程度であるので、work mem = 1GB の方が400

7 × 109 × 100(ns) = 700(s) 程度 I/O コストが大きくなる。こ200

れは図 3 の CPU コストの差とおおよそ同程度の差になっている。

064k 256k 1M

4M

16M 64M 256M 1G

4G

work_mem [byte]

work mem がハッシュテーブルサイズ (約 800MB) を越える
点では、常にパーティションが 1 つに収まるため、実行時間は

図 3: 単一の結合演算を行う問い合わせの各 work mem の値に一定である。なお、work mem が 512MB から 1GB の部分で急おける実行時間 (SSD)

激にキャッシュミス数が増加しているが、これはハッシュテー
ブル中のバケツに格納されている平均タプル数が、work mem

1400

idle
soft
irq
iowait
sys
usr

1200

Time [s]1000800= 1GB のとき大きく増加しており、プローブフェーズにおけL3 cache size

るハッシュバケツのタプルスキャン数が増加したためである。
ハッシュバケツ中の平均タプル数は、work mem が 64kB のとき 2.2、128kB のとき 3.8、256kB - 512MB のとき 5.7、1GB以上のとき 10.5 であった。lineitem 表のタプル数が 6 × 108600であるので、1GB のときのハッシュバケツのタプルスキャン
400

数は 512MB のときより (10.5 − 5.7) × 6 × 108 ≈ 3 × 109 多200

くなり、図 5 のキャッシュミス数の増分と一致する。これは、PostgreSQL のハッシュ結合の実装上の問題である。

0
64k 256k 1M

4M

16M 64M 256M 1G

4G

work_mem [byte]

図 4: 単一の結合演算を行う問い合わせの各 work mem の値における実行時間 (HDD)

1.2e+10

cache-references
cache-misses
cache-miss-rates

count

1e+10
8e+09
6e+09

図 4 の結果では、データベースバッファサイズが小さいとき
は I/O コストが大きく増加している。これは、2. 3 節で述べた
ように、HDD 上ではフラグメンテーションによる I/O スルー

L3 cache size

4e+09

100
90
80
70
60
50
40
30

プットの低下を避けるため、比較的大きなデータベースバッファ
サイズを選ぶ必要があることを示している。

cache miss rate [%]1.4e+10

4. 3 SSD に適したハッシュ結合演算処理方式

20
10

2e+09

一方、図 3 の計測結果から、SSD を用いたハッシュ結合演算
では、I/O コストが減少し、全体の処理コストの中では CPU
コストが支配的であることが明らかになった。CPU コストが増加する主要な原因は、プローブフェーズにおけるハッシュテー
ブルアクセスの際に生じるキャッシュミスペナルティによるメモ
リアクセスであった。ハッシュ結合演算では、プローブフェー
ズにおいて、ハッシュテーブルを繰り返し参照するデータアク

00
64k 256k 1M 4M 16M 64M256M 1G 4G

セス局所性があり、ハッシュテーブルサイズを小さくすること

work_mem [byte]

用いたハッシュ結合演算処理では、I/O スループットが HDD

でデータアクセス局所性を高めることが可能である。SSD を

図 5: 各 work mem の値における L3 キャッシュ参照・ミス数

使用時より高いため、データベースバッファサイズを小さくし及びミス率 (SSD)ても I/O コストが小さい。このことを利用し、ハッシュテーブ
ルが L3 キャッシュに収まるようにデータベースバッファサイが生じても I/O 帯域が十分に残されているためである。

ズを設定することで、キャッシュミス数の増加を抑制すること

work mem > 32M B の L3 キャッシュサイズを越える範囲でができる。このように、SSD を用いたハッシュ結合演算では、

は、ストレージの種類に関わらず、work mem の増加に伴い、CPU コストを最適化する重要性が高いため、キャッシュサイズ

CPU コストが増加している。これは、work mem が大きいほど、を意識してデータベースバッファを管理するべきである。

ハッシュテーブルの L3 キャッシュに収まる部分の割合が小さくなり、キャッシュミス数が増加しているためである。
図 5 は、SSD 上の計測でそれぞれの work mem の値における、

図 3 の結果では、データベースバッファサイズを 64kB まで
縮小しても I/O コストは小さいままである。データベースバッ
ファサイズを小さく設定することで、キャッシュに空きスペー
スが生じ、これを他の処理に用いることができるようになると考えられる。

5. 複数問い合わせの同時処理値について、それぞれ左から同時処理数 1、2、4、8、16、32、

64 のときの結果を表している。図中、同時処理数が大きな場合に idle の割合が大きくなっているが、これはある問い合わせの関係データベースシステムにおいて、複数問い合わせの同時処理における I/O の発行が、他の処理の I/O によって妨げら処理を行うことによって、計算資源の使用効率を高め、処理性れている場合であるため、この部分は I/O コストに含まれる。

能を向上することが可能である。また、SSD の内部は複数の

5. 1. 1 CPU コストの増加傾向の変化

Flash チップを束ねた構造になっているため、並列 I/O 処理に

図 5 の単一の問い合わせの計測では、work mem の値が L3

よりスループットが増加する [6] という特性がある。そのため、キャッシュサイズを越える 32MB から CPU コストが増加してSSD の I/O 帯域を十分に活用するためには、同時処理が不可欠いるが、図 6 においては、同時処理数 2 では 16MB、4 ではである。複数問い合わせの同時処理では、ストレージ、メイン

8MB、8 では 4MB から増加している。これは、同時処理数分

メモリ、CPU 毎の共有キャッシュ等のリソースが共有される。

ハッシュテーブルが共存し、L3 キャッシュを共有しているため処理性能を向上させるためには、個々の問い合わせで使用するである。全てのハッシュテーブルが L3 キャッシュに収まる場

リソースの量をコントロールし、それぞれの干渉を最小限に留合は、キャッシュミス数が抑えられる。なお、計測を行った環

める工夫が必要である。

境では、CPU 当たりのコア数が 8 であるため、8 コア毎に L3

HDD を用いた場合は、I/O のフラグメンテーションを避けキャッシュが共有されている。よって同時処理数 16 以上では、るために、比較的大きなデータベースサイズを指定する必要がキャッシュミス数の増加の傾向は同時処理数 8 のときと同様であった。単一の問い合わせ処理でキャッシュがほとんど埋まっある。

てしまうため、他の処理を同時に実行すると、キャッシュアク

また、計測環境の全コア数は 32 であるので、同時処理数 64

セスの競合が発生してしまい、逐次処理時にはキャッシュヒッのときは、1 コア当たり 2 つの問い合わせを処理する必要があトしていたものまでミスしてしまうというオーバーヘッドが生る。そのため、CPU コストは全ての work mem の値についてじてしまう欠点があった。

32 のときの約 2 倍になっている。

一方、SSD 上では、前節の計測結果の通り、ハッシュ結合演算において I/O コストを増加させることなく、データベース

60

バッファサイズを小さく設定することができる。これにより、

50

work_mem = 256kB
work_mem = 256MB

小さくなるため、残りの領域を他の処理で使用することが可能になる。そのため、キャッシュミス数を増加させることなく同時処理数を増やすことができ、HDD を用いた場合の処理方式

Speed up

1 つのハッシュ結合演算で使用するキャッシュ・メモリサイズが
40
30
20

より同時処理による性能向上が大きくなることが期待される。
本節では、複数問い合わせ同時処理のワークロードの例とし

10て、ハッシュ結合演算を行う問い合わせの複数同時処理性能を

1

2

計測し、処理性能の向上について検討する。

4816# of queries

32

64

5. 1 複数問い合わせ同時処理性能の計測

図 7: 各問い合わせ同時処理数における CPU 処理の高速化

表 1 の環境において、図 2 の問い合わせの複数同時処理性能(work mem = 256 kB, 256 MB)を計測する。問い合わせの同時処理数を、1 - 64 で変化させ、全ての問い合わせが終了するまでの時間とその間の CPU 使
用率の内訳を計測する。データベースは、TPC-H ベンチマー
クデータの Scale Factor = 10 のものを同時処理数分用意し、個々のデータベースにおいてそれぞれ 1 つの問い合わせを実行する。なお、個々のデータベースの合計サイズは 13GB、part
表、lineitem 表のサイズはそれぞれ 320MB、8.8GB、part 表に対して作られるハッシュテーブルの合計サイズは約 80MB であった。計測を行った環境では、CPU 当たりのコア数が 8 であり、同時処理数 1-8 では 1CPU 内で同時処理数分のコア、16では 2CPU に対してそれぞれアフィニティを付与して実行し、32、64 では全ての CPU を使用して実行した。また、単一の問い合わせの計測の際と同様に work mem を 64kB - 512MB の範囲で変化させて計測する。
図 6 は、問い合わせ同時処理数毎の各 work mem の値における実行時間とその内訳を示している。図では、各 work mem の

図 7 は、全てのハッシュテーブルがキャッシュに収まるように
データベースバッファサイズを設定した場合 (work mem = 256kB) と、HDD を用いた場合の処理方式として、データベース
バッファサイズを大きく設定した場合の (work mem = 256 MB)の CPU 処理の高速化を表す。図では、work mem = 256 MB の逐次処理時 (同時処理数 1) の CPU 処理速度を 1 としたときの速度向上を示している。
逐次処理時の CPU 処理速度は、work mem = 256 kB の場合
では、work mem = 256 MB の場合の 2.2 倍となっている。同時処理による速度向上は、同時処理数 32 のときで、work mem= 256 kB の場合で 59.8、work mem = 256 MB の場合で 20.6であった。

work mem = 256 kB の場合は、キャッシュを分割して使用し、キャッシュ参照の競合を抑えることができるため、同時処理数

Time [s]

500
450
400
350
300
250
200
150
100
50
0

idle
soft
irq
iowait
sys
usr

1

8

64

64k

256k

1M

4M
16M
work_mem [byte]

64M

256M

図 6: 複数問い合わせ同時処理時の各 work mem の値における実行時間を増加してもキャッシュミス数が増加せず、CPU 処理速度の増

3000

Read
Write

の効果によって CPU 処理速度が増加はしているが、同時処理数の増加に伴いキャッシュ参照の競合の度合いが高まるため、逐次処理の場合と比較するとキャッシュミス数が増加するオー
バーヘッドが生じ、work mem = 256 kB の場合と比較すると、性能向上が小さくなっている。

5. 1. 2 I/O スループットと全体の処理性能
以下では、全ての問い合わせ処理のハッシュテーブルが L3

I/O throughput [MB/s]

加幅が大きい一方、work mem = 256 MB の場合は、同時処理
2500
2000
1500
1000
500
0
1

キャッシュに収まる、work mem < 2M B の範囲に対象を絞り議論を進める。
まず、同時処理数 1 - 8 では実行時間はほとんど増加していない。これは、SSD が並列 I/O 処理能力をもつため、複数の10# of queries100

図 9: 各問い合わせ同時処理数におけるビルドフェーズの I/O
スループット

処理で同時に I/O が発行されても、I/O コストが変化しないためである。

に増加してしまっている。図 6 を参照すると、同時処理数 32

図 8 は、work mem = 256kB のときについて、問い合わせ同から 64 では、work mem が小さいほど I/O コストが大きく増加

時処理数毎に処理中の I/O スループット (MB/S) のタイムライしている。原因としては、work mem が小さく、同時処理数がンを示したものである。各図では、読み込み I/O スループット

多いほどパーティションファイル数が増加し、フラグメンテーが高くなっているタイムラインの前半部分 (例えば、図 8a ではションが生じるため、ファイルオープンのオーバーヘッドが増

0 - 30s 部分、図 8g では 0 - 260s 部分など) は、ビルドフェー

加することや、SSD の書き込みバッファの使用効率が低下する

ズの part 表と lineitem 表のスキャンを示しており、後半部分ことが挙げられる。また、同時処理数が多いほど、多くのファはプローブフェーズにおけるパーティションファイルのスキャ

イルへの I/O が混在することになるため、テーブルスキャンのンを示している。書き込み I/O は、ビルドフェーズで生成され読み込み I/O に対する先読みが機能しにくくなる [6] というこたパーティションファイルによるものである。なお、同時処理とも考えられる。

数 1 - 4 のときは、プローブフェーズにおいてパーティション

また、I/O スループットは、ハッシュ結合のビルドフェーズ

スキャンの I/O が生じていないが、これは PostgreSQL が OSにおいてのみ飽和していたため、16 以上の同時処理数においてのファイルキャッシュを利用しており、パーティションのデー

も、I/O が重くないプローブフェーズでは、更なる I/O スルー

タが全てファイルキャッシュに収まっているためである。

プット向上が期待できる。

図 8 では、同時処理数を増やしたとき I/O スループットが飽和しているのは、ビルドフェーズの部分である。ビルドフェー

5. 2 SSD を用いた関係データベースシステムにおける問い
合わせ処理スケジューリング

ズにおける I/O スループットの平均値を図 9 に示す。同時処理

図 6 の計測によって、SSD を使用した関係データベースシス

数 1 - 8 の範囲では、同時処理数に比例して I/O スループット

テムにおいて、複数問い合わせの同時処理によって処理性能がが増加している。16 のときは、8 のときの 1.4 倍程度に留まっ向上することが明らかになった。同時に処理される全てのハッており、読み込み I/O スループットは 2600MB/s 付近まで達シュ結合演算のハッシュテーブルをキャッシュに収めるよう、し、飽和している。また、32 から 64 では 200MB/s 程度読みキャッシュレベルでデータベースバッファ管理を行うことで、込みスループットが低下しているため、I/O コストが 2 倍以上

キャッシュミス増加を抑えたまま同時処理数を増加することが

2000
1500
1000

2500
2000
1500
1000

2000
1500
1000

500

500

0

0

0

20
30
40
elapsed time [s]

50

60

0

(a) 同時処理数 = 1

20
30
40
elapsed time [s]5060

I/O throughput [MB/s]

2000
1500
1000
500

10

20
30
40
elapsed time [s]

2500
2000
1500
1000

10

20

30

40

50

60

70

80

90

0

10

20

30
40
50
elapsed time [s]6070(d) 同時処理数 = 8
Read
Write

2500
2000
1500
1000

0
0

20

40

elapsed time [s](e) 同時処理数 = 16

60

500

0
0

50

3000

500

0

1000

3500

Read
Write

3000

2500

1500

(c) 同時処理数 = 4

3500

Read
Write

3000

2000

0
0

(b) 同時処理数 = 2

3500
I/O throughput [MB/s]

10

2500

500

I/O throughput [MB/s]

10

Read
Write

3000

2500

500
0

3500

Read
Write

3000

I/O throughput [MB/s]

2500

3500

Read
Write

3000
I/O throughput [MB/s]

I/O throughput [MB/s]

3500

Read
Write

3000

I/O throughput [MB/s]

3500

60

80

100

120

140

160

elapsed time [s](f) 同時処理数 = 32

0

50

100

150

200

250

300

350

elapsed time [s](g) 同時処理数 = 64

図 8: 各問い合わせ同時処理数における処理中の I/O スループットのタイムライン (work mem = 256kB)

でき、処理性能向上が大きくなる。キャッシュレベルのデータ(TAC) schema [4], [5] では、データのアクセスパターンをモニ

ベースバッファ管理を行った場合の例として、図 6 の work mem

タリングして統計をとり、アクセス頻度に応じたキャッシュ置= 256 kB の場合では、同時処理数 1 から 16 に増やしたとき

換アルゴリズムを提案している。Kang らの提案する FaCE シに、システム全体の処理性能としては 13 倍の性能向上がみら

ステム [9] では、キャッシュ置換アルゴリズムに multiversion

れた。

FIFO を利用し、Flash の弱点であるランダム書き込みを削減

一方、I/O スループットが帯域の上限まで達した後の、同時している。バッファプール拡張は、既にいくつかの商用デー

処理数 16 から 32 の部分では、I/O コストが 2 倍以上に増加

タベースシステムで実装され組み込まれている。例としては、しており、全体の実行時間としても 2 倍以上に増加している。

Oracle Exadata [17]、IBM XIV Storage System [1] などが挙このように、同時処理数を増やしていくことで、並列 I/O 処

げられる。

理によりスループットが増加するが、一定の並列 I/O 処理数を

SSD は、現在では容量や価格の面では HDD に劣るため、こ境にスループットは低下に転じる。これは、同時に複数の処理

れらの弱点を HDD によって補うために、SSD と HDD のハイブ

で I/O を発行することで、I/O の複雑性が高まりフラグメン

リッドストレージの運用も重要である。Koltsidas らの研究 [11]テーションが生じてしまうためである。SSD においても過度なでは、モニタリングにより、データのページ毎のワークロード

フラグメンテーションによって I/O スループットが低下してしを特定し、read-intensive なページを SSD に、write-intensive

まう。

なページを HDD に配置する方法を提案している。これによこのような弊害を避けるため、同時処理数の制御が不可欠でり、SSD への書き込み回数を低減させ、書き込み回数の限度がある。SSD を用いた関係データベースシステムにおいて同時処小さい問題を緩和している。[8] で述べられているように、バッ

理を有効に利用するためには、新たに問い合わせのスケジュー

ファプール拡張やハイブリッドストレージで用いられている、リング機構が必要となる。スケジューラが考慮すべき要素としモニタリングをベースとした手法は主に OLTP のようなデーては、I/O スループットを最大化するための同時処理数の選択

タの局所性が高いワークロードで効果を発揮する。これに対と、キャッシュレベルのデータベースバッファ管理が挙げられ

し本研究では、意思決定支援システムなど、アドホックな大規

る。I/O ワークロード調節の手法や、問い合わせ間のキャッシュ

模データ問い合わせの処理を行うシステムを前提としている。

分割使用のアプローチについてはこれからの研究課題となる。

hStorage-DB [13] では、DBMS の持つ、問い合わせに関する

6. 関 連 研 究

semantic information を利用したデータ管理を行っている。この手法では、データアクセスパターンが実行前に解析される

SSD を利用したデータベースシステムに関しては、既に多くため、モニタリングのためのオーバーヘッドや処理開始直後のの研究が見られる。問い合わせの実行に関するものでは、バッ

データ配置の問題などが生じない。本稿で述べた、複数問い合

ファプールの拡張や SSD と HDD のハイブリッドストレージ

わせの同時処理スケジューリングにおいても、こうした問い合管理、インデクシングなどが中心となっている。

わせのもつ I/O ワークロードに関する情報を活用する必要がバッファプール拡張は、SSD を DRAM の下のキャッシュ階層ある。

として扱いデータベースシステムのバッファプールを拡張する

インデクシングに関する研究では、FD-tree [12] は、データものである。Bhattacharjee らの、temperature-aware caching

更新時に書き込まれたデータをバッファリングし、SSD への書き込みをシーケンシャルに行う最適化を実現している。PIO機構が必要となる。これに関しては今後の研究課題としたい。

B-tree [9] では、SSD の並列 I/O 処理能力に着目した最適化を謝行っている。インデックスは、リレーションに対するデータの選

本研究の一部は JSPS 科費 24300034 の助成を受けたもの択率が比較的小さいときに多用される。一方で、大規模データ
処理問い合わせで選択率が高い時はシーケンシャルアクセスや、
ハッシュテーブルを用いた処理などが多用される。Tsirogiannis
らの研究 [16] では、カラムストアによってデータベースを格納し、必要なカラムの読み込みだけを行いメモリ使用量及び I/Oを削減する Flash scan を提案している。また、ハッシュ結合についてもセミジョインを利用し、同様の最適化を行った Flashjoin を提案している。Flash scan 及び Flash join ではランダム
アクセスが頻発するが、SSD ではランダムアクセスが高速なた
め HDD を使用する場合と比較して I/O コストを抑えることができる。
既存研究の多くは、SSD のアクセス特性に着目し、I/O を最適化するデータ構造や処理のみを目的にしている。本稿では、

I/O の挙動のみでなく、I/O 以外のボトルネックについても分析し、SSD を用いたデータベースにおける問い合わせの処理全体の性能向上について論じている。

7. お わ り に
本稿では、関係データベースシステムにおいて、従来の HDDに基づいた問い合わせ処理方式を見直し、SSD に適した処理方式の検討を行った。
まず、大規模データ処理で多用されるハッシュ結合演算を対象として、単体での処理時の性能計測を行い、SSD を用いる場
合は CPU コスト最適化の重要性が高いことを明らかにした。

SSD を使用したデータベースでは、ランダム I/O の処理コストが小さいため I/O コストを小さく保ちながら、データベー
スバッファサイズを小さくすることが可能である。本稿で行った計測では、データベースバッファサイズを 64kB まで縮小しても、I/O コストは増加しなかった。ハッシュテーブルアクセ
スにデータアクセス局所性があることを利用し、データベース
バッファを小さく設定することで、ハッシュテーブルをキャッシュに収めキャッシュミス数を抑えることで処理性能を向上できることを示した。
また、データベースバッファ使用量を低減することで、複数問い合わせの同時処理においてキャッシュを分割して使用することが可能になり、キャッシュミスの増加を抑えて同時処理を行うことが可能になった。ハッシュ結合演算の複数同時処理において、同時処理中の全てのハッシュ結合演算のハッシュテー
ブルをキャッシュに収めるようデータベースバッファを管理する処理方式によって、従来の HDD の特性に基づいた処理方式の場合よりも処理性能向上が大きくなることを実証した。
一方、問い合わせの同時処理数を増加させ、I/O スループッ
トが帯域の上限に達した後、更に時処理数を増加させると、パーティションファイルのフラグメンテーションにより、I/O
スループットが低下し、全体の処理性能が低下する現象が見られた。こうした弊害を避けるため、新たに SSD を用いた関係
データベースシステムにおいて、問い合わせスケジューリング

辞

です。
文

献

[1] IBM XIV Storage System.
http://www-03.ibm.com/
systems/storage/disk/xiv/index.html.
[2] PostgreSQL. http://www.postgresql.org/.
[3] Transaction Processing Performance Council, an ad-hoc, decision support benchmark. http://www.tpc.org/tpch/.
[4] Bishwaranjan Bhattacharjee, Kenneth A. Ross, ChristianLang, George A. Mihaila, and Mohammad Banikazemi. Enhancing recovery using an ssd buﬀer pool extension. DaMoN’11, pp. 10–16. ACM, 2011.
[5] Mustafa Canim, George A. Mihaila, Bishwaranjan Bhattacharjee, Kenneth A. Ross, and Christian A. Lang. SSD
buﬀerpool extensions for database systems. Proc. VLDB
Endow., Vol. 3, No. 1-2, pp. 1435–1446, September 2010.
[6] Feng Chen, David A. Koufaty, and Xiaodong Zhang. Understanding Intrinsic Characteristics and System Implicationsof Flash Memory Based Solid State Drives. SIGMETRICS
Perform. Eval. Rev., Vol. 37, No. 1, pp. 181–192, June 2009.
[7] Thomas Claburn. Google Plans To Use Intel SSD Storage In Servers, 2008. http://www.informationweek.com/
infrastructure/storage/google-plans-to-use-intel-ssd-storagein-servers/d/d-id/1067741?
[8] Jaeyoung Do, Donghui Zhang, Jignesh M. Patel, David J.
DeWitt, Jeﬀrey F. Naughton, and Alan Halverson. Turbocharging DBMS buﬀer pool using SSDs. SIGMOD ’11,
pp. 1113–1124. ACM, 2011.
[9] Woon-Hak Kang, Sang-Won Lee, and Bongki Moon. Flashbased extended cache for higher throughput and faster recovery. Proc. VLDB Endow., Vol. 5, No. 11, pp. 1615–1626,
July 2012.
[10] Masaru Kitsuregawa, Hidehiko Tanaka, and Tohru MotoOka. Relational Algebra Machine GRACE. In Proceedingsof RIMS Symposium on Software Science and Engineering,pp. 191–214. Springer-Verlag, 1983.
[11] Ioannis Koltsidas and Stratis D. Viglas. Flashing up thestorage layer. Proc. VLDB Endow., Vol. 1, No. 1, pp. 514–
525, August 2008.
[12] Yinan Li, Bingsheng He, Robin Jun Yang, Qiong Luo, andKe Yi. Tree indexing on solid state drives. Proc. VLDB
Endow., Vol. 3, No. 1-2, pp. 1195–1206, September 2010.
[13] Tian Luo, Rubao Lee, Michael Mesnier, Feng Chen, andXiaodong Zhang. hStorage-DB: heterogeneity-aware data
management to exploit the full capability of hybrid storage
systems. Proc. VLDB Endow., Vol. 5, No. 10, pp. 1076–
1087, June 2012.
[14] Domas Mituzas. Flashcache at Facebook: From 2010 to2013 and beyond, 2013. https://www.facebook.com/notes/
facebook-engineering/flashcache-at-facebook-from-2010-to-2013and-beyond/10151725297413920.
[15] Donovan A. Schneider and David J. DeWitt. A performance evaluation of four parallel join algorithms in a sharednothing multiprocessor environment. SIGMOD ’89, pp.
110–121. ACM, 1989.
[16] Dimitris Tsirogiannis, Stavros Harizopoulos, Mehul A.
Shah, Janet L. Wiener, and Goetz Graefe. Query Processing Techniques for Solid State Drives. SIGMOD ’09, pp.
59–72. ACM, 2009.
[17] Ronald Weiss. A Technical Overview of the Oracle Exadata
Database Machine and Exadata Storage Server. White paper, Oracle, 6 2012. http://www.oracle.com/technetwork/
database/exadata/exadata-technical-whitepaper-134575.pdf.