DEIM Forum 2013 F10-6

VAST 木における圧縮による CPU ペナルティの実験と考察
山室

健†

鬼塚

真†

小西 史和†† NTT サービスイノベーション総合研究所, 180-0012 東京都武蔵野市緑町 3-9-11
E-mail: †{yamamuro.takeshi,onizuka.makoto,konishi.fumikazu}@lab.ntt.co.jp
あらまし CPU・メモリのハードウェア（HW）技術の進展を背景に，これらの HW の特性を考慮したアルゴリズムの研究が注目されている．その中でも著者らは昇順の固定長データ列の中から，指定されたデータを高速に探索する手法に着眼し，HW に最適化された探索手法である VAST 木を提案している．VAST 木では圧縮による探索木内部構造のコンパクトな表現，探索処理の SIMD 命令によるデータ並列化，また CPU キャッシュミス・TLB ミスを減らすためのメモリレイアウト等を特徴としている．内部構造のコンパクトな表現のために，探索木内に存在する比較キーの上位・下位 bit を削除する非可逆な圧縮手法を適用することで圧縮を行っている．しかし，この非可逆な圧縮の影響により低い確率で誤った比較処理が行われ，結果的に得られた探索位置が，目的の位置からずれる可能性がある．そこで探索処理後に，探索データと葉ノード上のデータを逐次的に比較して訂正（エラー訂正処理）することで，この問題に対処している．葉ノード上のデータは昇順の固定長データで，それらは可逆な圧縮手法である整数列圧縮を適用した状態で保持していることを想定している．そのため，VAST 木の探索後に発生するエラー訂正処理は，データ参照・比較のために圧縮されたデータの復元処理が必要になるため整数列圧縮手法の選択は VAST 木の性能に大きく影響する．
そこで本論文では，VAST 木のエラー訂正処理で発生する復元処理のペナルティが整数列圧縮手法の選択によってどのように変化するかを分析し，どの手法が VAST 木の葉ノードの圧縮手法に適しているかを考察することが目的となる．
キーワード

CPU 最適化，SIMD，ベクトル化，探索木，圧縮VAST-Tree Compression Penalty on Modern Processors- Experiments and Observations
Takeshi YAMAMURO† , Makoto ONIZUKA† , and Fumikazu KONISHI†† NTT Service Innovation Laboratory Group, 3-9-11 Midori-machi, Musashino-shi Tokyo, 180-0012 Japan
E-mail: †{yamamuro.takeshi,onizuka.makoto,konishi.fumikazu}@lab.ntt.co.jp

1. Introduction

年の HW の特性を考慮していないため，分岐ミス，CPU キャッ
シュミスや，TLB ミス等のペナルティが多く発生し，その結果，マルチ CPU，マルチコア CPU や，メモリサイズの増大など探索性能を著しく悪化させることが指摘されている [1]．そこのハードウェア（HW）技術の進展を背景に，これらの HW ので著者らは HW の特性を考慮した探索手法である VAST 木 [2]特性を考慮したアルゴリズムの研究が盛んにおこなわれている．

を提案している．VAST 木では，CPU とメモリ間で発生するペその中でも特に，昇順に並べられた N 個の固定長データ（e.g.,

ナルティを最小化することを目的としているため，B+木等とは固定長整数）di （d1 <d2 <...<dN ）の中から任意のデータ dk

異なりオンメモリ上のデータ構造を前提としている．探索木のを探索する処理を本論文では扱う．この操作の利用法としては，内部構造（分岐ノードと葉ノード）に圧縮を適用することで探日々出力される大量のログデータの中から任意のタイムスタン

索対象のデータが大規模化した場合にでも，コンパクトなデー

プを持つデータを取り出すような処理や，ID（e.g., 転置索引にタ構造を保ちながら，探索時のデータ並列化（SIMD 命令の適おけるドキュメント ID) などの集合が与えられた場合に特定の用），CPU キャッシュミス・TLB ミスを減らすためのメモリレ

ID のみを探索するような場合が考えられる．この操作を高速

イアウト等により，ペナルティの最小化を実現している．

に行う代表的な手法としては 2 分木や多分木の代表である B+

VAST 木では，コンパクトなデータ構造を実現するために分木などが挙げられる．しかし，これらの古くからある手法は近岐ノードに対して非可逆な圧縮手法を適用している．より具体的には，分岐ノード内に存在する比較キーの上位・下位 bitを削除することで圧縮を行っている．これは木構造内の探索において，木の根ノードから葉ノード方向に探索が進むにつれて，探索範囲が徐々に狭くなり，比較キーの値間が近づくことための方法について述べ，5. 節以降で実験・考察を行う．

2. Related Works
データベース性能のボトルネックがディスクから，CPU（特によって本質的に比較を行うために必要な bit が少なくなる特にメモリと CPU 間）に変化してきているという指摘 [5] から，性を利用している．しかし，この bit 削除の影響により低い確

それ以降データベース研究分野では様々な CPU の特性に最適化率で誤った比較が発生し，結果的に得られた探索位置が，目的された手法が提案されてきた．探索もその中の 1 つであり，特の探索位置からずれる可能性がある．そのため VAST 木では探に 2000 年前半に B+木の探索中に発生する CPU キャッシュミス

索後のエラー訂正処理として，目的の探索データと葉ノード上を低減し，性能向上を図る手法が多く提案された [6] [7] [8] [9]．

のデータを逐次的に比較することで探索位置の訂正を行っていこれらの研究の結論として得られた知見は，オンメモリ上のる．具体的な例として，探索対象の N 個の固定長データ列が di

B+木における分岐ノードのサイズをキャッシュライン（注 2）と同

（d1 <d2 <...<dk <...<dN ）であるとして，探索データが dk でじにした場合，木の高さが高くなり TLB（注 3）ミスが大きくなるある場合を考える．VAST 木内の比較処理で誤った比較が発生ため，TLB ミスのペナルティを考慮してノードサイズをキャッした結果，探索された葉ノード上の位置が dk−3 であった場合

シュラインのサイズより多少大きい値に設定することで性能をに，目的の探索位置までのエラー訂正処理として dk−3 ，dk−2 ，改善できるというものであった．また，この他にも CPU キャッdk−1 ，dk の 4 回分のデータ参照・比較（この目的の探索位置まシュミスを低減する手法として，探索処理を分岐ノード上に一でのエラー量を ∆w で表す，ここでは ∆w=4 となる) が必要に時的に留め，後でまとめて処理する手法 [11] や，次の探索ノーなる．この葉ノード上のデータは昇順に並び替えられた固定長ドをプリフェッチする手法 [10] などが提案されている．さらにデータで，整数列圧縮が適用されていることを前提としている

最近では，データ並列化のための SIMD 命令を利用した探索ため，データの参照・比較処理に復元処理が必要になる．

手法が提案 [12] され，特に Intel Lab. が提案している FAST [1]整数列圧縮は，古くからデータベースや情報検索の分野で研は，キャッシュミス・TLB ミスを考慮したメモリレイアウト，

究がされており，上記の HW 技術の進展を背景に HW に最適化

SIMD 命令を用いた探索の並列化と分岐命令を排除などを適用された手法が同様に数多く提案されている．整数列圧縮は，連した手法を提案している．著者らが提案している VAST 木 [2]続する同じデータ型の配列（例えば 32bit 符号無し整数型）をは FAST を参考にして提案したものであり，FAST に対して探圧縮するもので，有名な手法に γ 符号や δ 符号 [4] があり，よ索対象データが大きくなった場合の内部構造肥大化の圧縮により最近ではカラム志向データベースや転置索引内部の圧縮手法

る抑制，SIMD 命令によるデータ並列数の向上，葉ノード上のとして広く使われている PForDelta [3] などの HW に最適化さデータ圧縮などを適用した手法である．

れた手法が存在する．これらの手法は，データを参照する際に余剰な復元処理が必要であるため CPU ペナルティが発生する．

3. VAST-Tree

そのため，上記で説明した VAST 木の探索後に発生するエラー

ここでは 32bit の固定長データ列に対する VAST 木の概略図

訂正処理は選択する整数列圧縮手法によって VAST 木の性能にを Fig.4 に示し，この図の概要を説明する（注 4）．VAST 木では分大きく影響する．

岐ノード（図 4 の上部三角形で示されている部分）内の比較

本論文では，VAST 木のエラー訂正処理で発生する葉ノーキーを上位・下位 bit を削除する非可逆な手法で圧縮し，葉ノー

ド上の逐次探索による CPU ペナルティを，選択する整数列圧ド（図 4 の下部長方形で示されている部分）上のデータ列に縮手法によってどのように変化するのかを分析・考察するこ対しては可逆な整数列圧縮手法を適用している．図中の各 H，とが目的となる．今回評価対象とする既存の整数列圧縮手法

PH，CH，SH は各三角ブロック内に存在する 2 分木上での高として，単体整数に対して 1 つの符号を割り当てる γ 符号，

さを表し，それぞれの添え字はそのブロック内に存在する比較δ 符号，Variable-Byte 符号 [4] を，複数の整数をまとめて符号

キーの bit 長を表している．例えば，SH32 =3 の場合には，SH化する Varint-G8IU [19]，Simple9 [13]/16 [14]/8b [17]，BP [15]，ブロックが 32bit 長の比較キーを保持し，そのブロックは高さ

PForDelta [3]，VSEncoding [16] を取り扱う．また，これらの手

3（ブロック内の総比較キー数が 7）の比較キーで構成されると法は任意の位置の整数を復元することができない（注 1）ため，こいう意味である．

れを可能にするために整数列を固定長のブロックで分割して，

SH ブロックは CPU 内に実装されている SIMD の比較命令にそれぞれを個別に圧縮することで任意位置の復元に対応する．

よって，CPU の 1 命令で実行される比較キーの集合を表してい本論文の構成は，まず 2. 節において探索木に関する研究動向

る．現在広く使われている Intel 互換 x86 の CPU には 128bit 長を俯瞰し，3. 節で本論文が前提としている VAST 木の概要を説明する．続く 4. 節で本論文において評価を行う整数列圧縮手法と，VAST 木の探索に必要な任意の位置からの復元に対応する（注 2）：CPU のキャッシュとメモリ間のデータ転送最小単位で，一般的な CPU では 64B 程度である．
（注 3）：Translation Look-aside Buffer の略で，良く利用するページの論理アドレ
スと物理アドレスの対応関係をキャッシュしている CPU 内の機構である．

（注 1）：たとえば，n 個の圧縮されている整数列から先頭から k 個目の整数を復（注 4）：64-bit のデータ列に対する VAST 木の場合は，最上端部に P64 を追加し元したい場合に，必ず先頭から逐次的に復元する必要があるという意味である．

た 4 レイヤから構成される．

のレジスタが数本実装されているため，32bit 長の比較キーであ力し，その後に’1001’ を出力する．結果的に得られる γ 符号れば最大 4 データ，16bit 長であれば 8 データ，32bit 長であれは’0001010’ となる．γ 符号では先頭の連続した’0’ が元の整数ば 16 データを同時に比較可能である．実際の VAST 木の実装の桁数を表しているため，復元処理は先頭から’1’ が出現する

では，SH32 =2 として同時に 3 つの比較キーを，SH16 =3 としてまで’0’ を読み込み，読み込んだ’0’ の数+1 の後続 bit を読み込

同時に 7 つの比較キーを，SH8 =3 として同時に 3 つの比較キー

んで元の整数を復元する．δ 符号は γ 符号を改良したものでをそれぞれ並列比較する．次期 Intel の CPU である Haswell であり，桁数を先頭の連続する’0’ で表す代わりに γ 符号で記録

は 256bit 長のレジスタ上での整数比較命令が実装予定であり，し，その後続に元の整数の最上位 bit を取り除いた bit 列を格

それを利用すれば SH ブロック内の比較キーの並列実行数の向納する方式である．再度 d=9 を例に挙げると bit 長は 4 である

上が期待できる．CH ブロックは同じ上位・下位 bit が削除さため，これを γ 符号で変換すると’00100’ となるため，結果的れた比較キーの集合を表している．CH32 のブロックでは比較に’00100001’ となる．γ 符号と δ 符号は与えられた整数を bit

キーの圧縮を行わず，CH16 と CH8 のそれぞれのブロックでは単位で符号化を行うが，この符号化を byte 単位で行う手法が上位・下位 bit の合計 16bit と 24bit をそれぞれ削除して圧縮をVariable-Byte 符号である．一般的な CPU は bit 単位よりも byte

行っている．同じ CH 内に含まれる比較キーは同じ位置の上位・単位の操作のほうが効率的に扱えるため Variable-Byte 符号は

下位 bit が削除され，その削除された bit 位置情報は各 CH ブ

効率的に圧縮・復元が可能であるが，符号化が byte 単位で行わ

ロックのヘッダ情報として記録される．このヘッダ情報を利用れるため圧縮率が悪くなる傾向がある．Variable-Byte 符号は整することで，探索キーに対して同じ bit 削除処理を適用するこ

数を 7bit 単位に分割して，各 7bit を 1byte に格納する．最上位とで比較を行うことができる．このキーの上位・下位 bit の削除

1bit は後続の byte が存在するかを表すフラグで，後続の byte

によって前節で説明した目的の探索位置からのずれるエラーがが存在する場合は最上位 bit を’1’ に設定する．例えば d=553発生する．PH ブロックは隣接したページ揃える（アラインす（10001010012 ）とした場合に，7bit ずつに分割すると’0101001’

る）ための比較キーの集合をそれぞれ表している．このアライ（下位 bit）と’100’（上位 bit）になり，これらを byte に格納す

ン処理によって，ページ境界を跨ぐブロックを少なくし，CPU

ると’10101001’ と’00000100’ となる．下位 bit が格納されていキャッシュと TLB のミスの最小化を図っている．

る byte の最上位 bit に’1’ を設定しているが，これは先程の説
明通り後続の byte が存在していることを表している．

4. 2 Varint-G8IU
Variable-Byte 符号は整数毎に符号化を行うが，複数の整数をまとめて符号化するように拡張したものが Varint-G8IU [19]である．Varint-G8IU は Google の Group Variant [18] を改良したもので，2〜8 個の整数をまとめて Variable-Byte 符号で圧縮を行う．1B のディスクリプタと，それに続く固定の 8B 領域
で符号化され，8B に入る最大の整数（2〜8 個）個数が格納される．先頭のディスクリプタには，Variable-Byte 符号の上位

1bit と同じ意味を持った bit が，後続の 8B 領域に格納されている整数分だけ集められて格納される．例えば d[4]={215 (2B),
図 1 P32 ，P16 ，P8 の 3 レイヤから構成される VAST 木の概略図

223 (3B), 27 (1B), 215 (2B)} の整数列を圧縮する場合を考える．それぞれに対応した Variable-Byte 符号の上位 1bit だけを取り出

4. Leaf Compression

すと，’01’，’011’，’0’，’01’ になる．結果的に，この bit を連結した’01001101’ を先頭のディスクリプタとして，後続に必要

前節で説明したように，P16 と P8 レイヤでは分岐ノード内のbyte 数に切り詰めた整数列 8B を連結して符号化する．

比較キーを 16bit と 8bit に削除する影響で目的位置からのずれ復元処理は先頭のディスクリプタを取り出して，後続の 8B∆w（>= 0）が発生する．この ∆w のエラー訂正処理の逐次的領域に格納されている先頭（’0’ で埋められた）byte を切り詰

な参照と比較のために葉ノード上の圧縮されたデータの復元処められた整数を 32-bit 長に戻すことで容易に実現できるが，理が必要になる．そのため，葉ノードに適用する整数列圧縮手

Varint-G8IU では SIMD 命令である Intel の SSE3（注 5）で実装され法によってエラー訂正処理のペナルティが変化し，VAST 木のている pshufb を利用することで，先頭の’0’ を復元する処理を性能に大きく影響することが推測される．この節では，本論文高速化している（図 2，図中の整数値は 16 進数で表記）．pshufb

で評価対象とする既存の整数列圧縮手法の概要を説明する．

は入力用の SIMD レジスタ（図中の IN）と mask 値が書き込ま

4. 1 γ, δ, and Variable-Byte codes

れた出力用の SIMD レジスタ（図中の OUT）を受け取り，mask

γ 符号と δ 符号は古くからある整数圧縮手法 [4] であり，γ値に従い入力レジスタから出力レジスタに byte 単位で複製を符号は任意の符号無し整数 d の 2 進数での bit 長より 1 つ少ない’0’ を出力した後に，整数 d をそのまま出力する．例えば

d=9（10012 ）とした場合，bit 長が 4 であるため 3 つの’0’ を出（注 5）：shuffle と呼ばれる SIMD 命令では一般的な処理で，ARM の SIMD 命令である NEON においても同等の処理を実現可能である．

行う命令である．pshufb を利用することで図のように 32-bit 長

Algorithm 2 連続する 32 個の整数を 8bit で復元する関数の拡張処理が SIMD レジスタ上で容易に実現でき，8B 領域を

1: UNPACK8 32(uint32 t src[8], uint32 t dst[32])SIMD レジスタに読み込みと，1〜2 回の SIMD レジスタの書き

2: for i = 0 → 7 do

出しで処理が完了できる．

3:

dst[i * 4] = src[i] & 0x0F;4:

dst[1 + i * 4] = (src[i] >> 8) & 0x0F;

5:

dst[2 + i * 4] = (src[i] >> 16) & 0x0F;6:

dst[3 + i * 4] = (src[i] >> 24) & 0x0F;

7: end for4. 5 PForDelta and the variants
PForDelta [3] は Simple9/16 や BP と同じように複数の整数をまとめて符号化する手法である．PForDelta では連続する m 個
図 2 pshufb を用いた Varint-G8IU の復元処理概要の整数の大半（90%〜）が符号化可能な bit 長 b を決定し，b-bitで符号化可能なものは固定長で格納して，b-bit を超える整数は4. 3 Simple9/16/8b
一般的な CPU で効率的に扱える単位は 32bit（もしくは 64bit）の word 単位である．そのため，この 32bit の word を効率的に扱うように設計されたものが Simple9 [13] と Simple16 [14]で，64bit 向けに設計されたものが Simple8b [17] である．これ
らの手法は word の先頭 4bit と後続の bit（Simple9/16 は 28bit，Simple8b は 60bit）に分割し，先頭 4bit のディスクリプタで後続 bit の分割方法を変更する方式である．この分割方法は事前に定められており，例えば Simple9/16 において連続する 28 個の整数が全て 1bit で符号化可能であれば，後続 28bit を 28 分
割して符号化し，連続する 7 つの整数が 4bit で符号化可能であれば後続 28bit を 4bit ずつに分割して利用する．Simple9 では
分割方法が 9 通りで，Simple16/8b は 16 通りである．

4. 4 BP: block packing
BP [15] は連続する 128 個の整数列をまとめて符号化する方式で，128 個の整数列を 32 個の整数ブロック 4 つに分割して，各整数ブロックの最大 bit 長で符号化する方式である．各整数
ブロックを符号化した bit 長を 8bit で記録することで，4 つ集めて 32bit のディスクリプタとして格納し，後続に符号化した整数ブロックを連結する．各整数ブロックの符号化と復元処理のための疑似コードを Algorithm 1 と Algorithm 2 に示す．これらの疑似コードから分かるように，bit の shift 処理と mask 処理の組み合わせで容易かつ高速に実現することができる．疑似コードのように一般的な命令だけで実装されたものが BP32，復元
処理を SIMD 命令で高速化したものが SIMD-BP32 である．

最後の例外領域に元の bit 長のまま格納する．例えば，以下のような整数列（m=10）がある場合を考える．

1, 3, 2, 3, 1, 2, 203, 3, 0, 2
この場合は’203’ 以外の 90%の整数は 2bit で符号化可能であるため，b=2 となる．そのため’203’ はそのままの bit 長で例外領域に格納され，それ以外の整数は 2bit の固定長 bit で以下のように符号化されることになる．

12 , 32 , 22 , 32 , 12 , 22 , 32 , 02 , 22 , 20332
各整数の添字は符号化されている bit 長を，最後のアンダー
ラインの整数が例外領域をそれぞれ表している．’203’ の出現
位置が移動しているが，元の位置情報は別途保存しているため，復元時に元の位置に並べ替えることができる．OPTPForDelta は

PForDelta の例外領域の効率を改善したもので，OPTPForDelta
では，例外として扱われた整数の b-bit 以下の値は元の位置に格納して，b-bit を超えている bit 部のみを例外領域に格納す
る．さらに例外領域の整数列に対して Simple16 で符号化することで圧縮率の向上を測った設計になっている．OPTPForDelta
に対して，b-bit の固定長で符号化された整数列を復元する処理を SIMD-BP32 と同じように SIMD 命令で高速化した手法がSIMD-FastPFor，例外領域の符号化手法に Simple8b に変更したものが SimplePFor である [15]．

4. 6 VSEncoding
前節で説明した PForDelta では m と b の値がパラメータとなっており，これらの値は圧縮対象の整数列によって最適値が異なるため最適なパラメータ設定が難しい課題がある．そこ
で圧縮対象の整数列を k 個のブロックに分割（B1 , B1 , ..., Bk ）Algorithm 1 連続する 32 個の整数を 8bit で符号化する関数

して，各ブロックはブロック内に存在する最大 bit 長を持つ整

1: PACK8 32(uint32 t src[32], uint32 t dst[8])数に合わせて固定長 bit で符号化するものとする．そのような

2: for i = 0 → 7 do

前提のもとで，各ブロック長を動的計画法で決定する手法が3:

dst[i] = src[i * 4] & 0x0F;

4:

dst[i] ∥= (src[1 + i * 4] & 0x0F) << 8;5:

dst[i] ∥= (src[2 + i * 4] & 0x0F) << 16;

6:

dst[i] ∥= (src[3 + i * 4] & 0x0F) << 24;

7: end for

VSEncoding [16] である．最適なブロック長を動的計画法で計算するために圧縮時に２パス以上の読み込みが発生するものの，圧縮率と復元速度の観点で良いトレードオフを実現していることが特徴である．

4. 7 Block compression
今までに説明した整数列圧縮手法は研究背景で説明した通り，任意の位置の部分整数列だけを復元することができない．

そこで本評価においては，整数列を固定 k 個の整数ブロックにため実際には，元の整数を復元するために prefix-sum の処理

分割し，分割された個々の整数ブロックに対して上記で説明し（xi =δi +xi−1 ）が復元処理後に必要になるが，これは全ての整た整数列圧縮手法を適用する．そして各整数ブロックの先頭位

数列圧縮手法において共通の処理であるため今回の実験におい置を別途記録しておくことで，先頭から g 個目の整数を復元しては除外している．

たい場合に，g/k 個目の整数ブロックのみを復元するだけで目性能評価に用いたマシンは CPU がコア数 6 の Intel Xeon 5670

的の整数が復元できるようなる．例えば，ある整数列に対して

で，総メモリサイズが 16GiB である．Xeon 5670 の L1/L2/LL

単体整数を平均的に 4bit で表現可能な圧縮手法を前提に，k を(Last-Level) キャッシュは そ れ ぞ れ ，32KiB/256KiB/12MiB の256 で整数列をブロック化した場合を考える．この時，整数ブ

容量を備えている．Xeon 5670 のマイクロアーキテクチャはロック当たりに必要な平均的な領域は 128B（各ブロックの先Westmere-EP で，加減算やビット演算などの一般的な整数に対頭位置を記録している領域を除く）となる．キャッシュライン

する SIMD 命令を実装している SSE2，pshufb を実装している

サイズが 64B の一般的な CPU において，エラー量 ∆w が平均

SSE3 が命令体系に含まれている．前節で説明した整数列圧縮

的に 128 である場合に，エラー訂正処理に読む込む必要のある手法は全て C++で実装され，それらのコードは GNU Compiler

キャッシュラインの平均的な数は 1.5 となる．近年の CPU の傾

Collection v4.7.1 の-O2 -march=nocona でコンパイル（注 9）して評向として，CPU 内の演算性能の向上に対して，CPU-メモリ間価に用いた．

の転送帯域の向上は緩やかであるという指摘 [1] から，処理が5. 1 Comparison Results

参照するメモリ上のデータ量（footprint）は最小化することが人工データ UniformData と ClusterData を用いた圧縮（cod-望ましい．逆に k を小さくした場合，先頭位置を記録しているing）/復元速度（decoding）と圧縮率（bits/int）の結果を表 1 と領域のオーバヘッドにより圧縮率が悪化する．そのため探索処

表 2 に，実データ Gov2 と ClueWeb09 を用いた結果を表 3 と理の footprint と圧縮率の観点から k を 256 に設定して，本評価

表 4 に示す．圧縮と復元速度は秒間あたり圧縮/復元できた整数を行っている．

数を 1,000,000 で割った値 mis（million integers per second）で，圧縮率は整数毎に必要な平均 bit 数を表している．まず人工デー

5. Experimental

タの結果に関しては，[0,229 ) の整数範囲から 225 個の昇順の整本実験では VAST 木の葉ノードに適した整数列圧縮手法を分数列を生成して用いているため，平均的には 24 (229−25 )bits/int

析することが目的である．具体的には，この実験項では以下 2となる．UniformData と ClusteredData を比べると，値の分布

点の分析を行う．

が偏っている ClusteredData のほうが δi は部分的に小さくな（ 1 ） 各整数列圧縮手法の圧縮/復元速度と圧縮率ることから圧縮性能が良い結果になっている．個々の結果を（ 2 ） 部分復元量（∆w）を変化させた場合の性能見てみると，符号化を byte 単位で行う Variable-Byte 符号と1 つ目の項目は整数列圧縮の基本的な性能を測る目的であり，

Varint-G8IU は，その他の手法と比べて圧縮性能が劣る結果に

2 つ目は VAST 木のエラー訂正処理（任意位置に存在する ∆w

なっている．圧縮率の観点では，γ 符号や δ 符号などの整数個の部分整数列復元）の性能を表す評価である．

毎に符号化を行う手法のほうが複数の整数をまとめて扱う手評価に用いるデータセットは人工データと実データの両方を法に比べて（値にばらつきがある場合にオーバヘッドが高く扱う．人工データには UniformData と ClusterData [17] を，実なる特徴のため）有利な傾向にあるが，それでも一部の結果

データには Gov2 と ClueWeb09（注 6）を用いた．UniformData（一（UniformData のおける Simple16/Simple8b/BP32，ClusteredData

様な整数列）と ClusterData（偏りのある整数列）は github 上ににおける BP32/SimplePFor/VSEncoding) においては γ 符号や δ（注 7）

公開されているコード

29

25

個

符号の圧縮率より高い結果となっている．圧縮速度に関しては，の昇順の整数列を生成 [15] して使用した．実データの Gov2 はを参考に，[0,2 ) の範囲から 2

OPTPForDelta と VSEncoding は圧縮率を最適化するために 2 パ

TREC Terabyte Track で利用可能な評価用データの 1 つで，gov

ス以上の処理を圧縮処理中に行うため，圧縮速度が非常に劣化のドメインに含まれる html/text のドキュメントを収集したものしている．復元速度に関しては，全体的に整数毎に符号化を行である．それらを URL で辞書順に並び替え，得られた昇順のう手法に比べ，まとめて符号化を行う手法が有利な傾向にあり，

ドキュメント ID の整数列を本評価に用いた．また ClueWeb09

特に Varint-G8IU は UniformData と ClusteredData の両方においは，カーネギーメロン大学が収集して公開（注 8） している Web 上て最も復元性能が高い結果になった．これらの結果をもとに実のドキュメント集合であり，Gov2 と同じように生成した昇順

データ Gov2 と ClueWeb09 の表 3 と表 4 を見ると，次のことのドキュメント ID の整数列（URL による並び替えの前処理はが分かる．1. 圧縮率に関しては，byte 単位に符号化を行う手法

適用しない）を本評価に用いた．これら人工データと実デー

は同様に性能が悪く，一方で（一部を除き）まとめて符号化を

タは昇順の整数列であるため，整数列圧縮の慣例に従って前行う手法のオーバヘッドが人工データと比べて小さくなってい後の差分値 δi (=xi -xi−1 -1) に対して圧縮手法を適用する．そのる．2. 圧縮速度は人工データと概ね同じ傾向を示しているため，データの分布の影響が小さいものと考えられる．3. 復元速度は，（注 6）：http://boytsov.info/datasets/clueweb09gap/（注 7）：https://github.com/lemire/FastPFor（注 9）：また使用する整数列圧縮手法が SSE を利用している場合には，対応した（注 8）：http://lemurproject.org/clueweb09.php/

SSE を有効化するオプションを追加している．

平均 bits/int が小さい Gov2 においては Simle9/16，PForDelta，

表 3 圧縮/復元速度と圧縮率（Gov2)

coding decoding bits/int

OPTPForDelta，VSEncoding の性能が Varint-G8IU と同等，もしくはそれ以上の高い性能を出している，一方で平均 bits/int がGov2 に比べて高い ClueWeb09 では優劣の差は小さくなっているものの Varint-G8IU が最も性能が良くなっている．
表1δ 符号
Variable-Byte 符号
Varint-G8IU
Simple9

46
60
117
56

34
127
139
1267
404

174

1.4

68

142

8.3

Varint-G8IU

119

1254

9.2

Simple9

88

1239

1.7

Simple16

81

1206

1.7

Simple8b

190

935

1.4

BP32

204

997

1.2

SIMD-BP32

218

848

8.8

PForDelta

83

1346

1.9

OPTPForDelta

27

1355

1.9

SIMD-FastPFor

110

514

2.5

SimplePFor

136

703

1.3

VSEncoding

6.9

1291

1.3

7.2
8.4
9.3

Simple16

30

381

6.4

Simple8b

101

521

6.9

BP32

197

1189

7.0

SIMD-BP32

221

826

8.8

PForDelta

46

743

7.8

OPTPForDelta

4

811

7.7

SIMD-FastPFor

94

372

8.7

SimplePFor

115

960

7.2

VSEncoding

表2

7

527

7.8

表4

圧縮/復元速度と圧縮率（ClueWeb09)

coding decoding bits/int

38

5.7

δ 符号

47

113

5.7

Variable-Byte 符号

57

130

8.7

Varint-G8IU

115

1241

9.3

Simple9

56

491

5.9

Simple16

34

456

5.4

Simple8b

109

522

5.8

BP32

57

130

8.7

SIMD-BP32

210

683

8.9

PForDelta

50

752

6.7

OPTPForDelta

5

927

5.1

SIMD-FastPFor

85

368

7.6

SimplePFor

103

695

6.0

VSEncoding

7

562

6.6

55

79

1.7

δ 符号

57

147

1.7

73

144

8.2

Varint-G8IU

119

1280

9.3

Simple9

79

930

2.2

Simple16

64

927

2.1

Simple8b

142

716

2.3

BP32

207

883

2.2

SIMD-BP32

225

843

8.8

PForDelta

74

1021

2.8

OPTPForDelta

19

1000

2.6

SIMD-FastPFor

87

365

4.5

SimplePFor

111

677

2.3

VSEncoding

7.1

846

2.2

coding decoding bits/int46

γ 符号
Variable-Byte 符号

圧縮/復元速度と圧縮率（ClusteredData)

γ 符号

1.4

59

7.2

7.3

82

δ 符号

coding decoding bits/int
45

58

Variable-Byte 符号

圧縮/復元速度と圧縮率（UniformData)

γ 符号

γ 符号

次にそれぞれのデータを用いて復元量（∆w）を変化させた
場合の部分復元性能測定結果を図 3，図 4，図 5 と，図 6 に示

図3

部分復元性能の評価（UniformData）

す．これらの部分復元性能の性能結果は，各整数列圧縮の全体復元性能を概ね反映した結果になっており，復元量 ∆w が小さに正規化した結果をプロットしている．復元速度に関しては，

い場合に性能が高くなる傾向を持つ手法はないことが分かる．

∆w の値で速度差に優劣が大きく発生しなかったため，中央値

6. Discussionである ∆w=27 の結果を用いている．圧縮率が高く，復元速度が速いものが図中の右下にプロットされるため，トレードオフ

この節では評価を行った整数列圧縮手法の圧縮率と復元速度という観点では Gov2 と ClueWeb09 の両方の実験データにおいのトレードオフに関する分析を行う．圧縮速度に関しては，一て VSEncoding が最も良い，という結果になった．一方で，圧般的に復元処理に対して圧縮処理は 1 度しか行わないため，今縮率が優先される環境では γ 符号と δ 符号が，逆に復元速度が回は分析対象外としている．実データ Gov2 と ClueWeb09 の優先される環境では PForDelta と OPTPForDelta が良いという評価結果をもとにトレードオフ分析を行ったものを図 7 と図 8ことも併せて判断できる．

に示す．図では圧縮率・復元速度それぞれの最大値で 0.0〜1.0

図4

部分復元性能の評価（ClusteredData）

図8

圧縮率/復元速度のトレードオフ評価（ClueWeb09）

能を優先した場合には γ 符号と δ 符号が，性能面（単位時間当たりの展開可能な整数数）を優先した場合には PForDelta とOPTPForDelta が良く，また圧縮率と復元速度のトレードオフの観点では VSEncoding が葉ノードに適用する整数列圧縮手法
として適していることが分かった．
文
図 5 部分復元性能の評価（Gov2）

図 6 部分復元評価（ClueWeb09）

図7

圧縮率/復元速度のトレードオフ評価（gov2）

7. Conclusions
本論文では，VAST 木の葉ノードに用いる整数列圧縮手法の実験と考察を行った．VAST 木の分岐ノードでは比較キーの bit
削除の影響により低い確率で誤った比較が行われる可能性がある．その結果，目的の探索位置からのずれるエラーが発生する
ため探索後に訂正処理が必要になる．そのため葉ノードに用いる整数列圧縮手法によって，この訂正処理のペナルティが大きく変化して，VAST 木の探索性能に影響することが考えられる．そこで本実験では VAST 木の葉ノードの圧縮手法に適した圧縮手法を分析することが目的となる．結果的に，圧縮性

献[1] Changkyu Kim et al. “Designing Fast Architecture Sensitive Tree
Search on Modern Multi-Core/Many-Core Processors”, ACM Transactions on Database Systems, 9(4), 2011.
[2] Takeshi Yamamuro et al. “VAST-Tree: a vector-advanced and compressed structure for massive data tree traversal”, Proc. of EDBT’12,
pp. 396-407, 2012.
[3] Marcin Zukowski et al. “Super-Scalar RAM-CPU Cache Compression”, Proc. of ICDE’06, pp. 59-71, 2006.
[4] Ian H. Witten et al. “Managing Gigabytes: Compressing and Indexing Documents and Images”, Morgan Kaufmann, 1999
[5] P. A. Boncz et al. “Database Architecture Optimized for the New
Bottleneck: Memory Access”, Proc. of VLDB’99, pp. 54-65, 1999.
[6] J. Rao and K. A. Ross. “Cache Conscious Indexing for DecisionSupport in Main Memory”, Proc. of VLDB’99, pp. 78-89, 1999.
[7] J. Rao and K. A. Ross. “Making B+-trees cache conscious in main
memory”, Proc. of SIGMOD’00, pp. 475-486, 2000.
[8] G. Graefe and P.-A. Larson. “B-Tree Indexes and CPU Caches”,
Proc. of ICDE’01, pp. 349-361, 2001.
[9] R. A. Hankins and J. M. Patel. “Effect of node size on the performance of cache-conscious B+-trees.”, Proc. of SIGMETRICS’03, pp.
283-294, 2003.
[10] S. Chen, P. B. Gibbons, and T. C. Mowry. “Improving index performance through prefetching.”, SIGMOD Record, 30(2), pp. 235-246,
2001.
[11] J. Zhou and K. A. Ross. “Buffering accesses to memory-resident index structures.”, Proc. of VLDB’03, pp. 405-416, 2003.
[12] B. Schlegel, R. Gemulla, and W. Lehner. “k-ary search on modern
processors.”, Proc. of DaMoN’09, pp. 52-60, 2009.
[13] Vo Ngoc Anh and Alistair Moffat. “Inverted Index Compression Using Word-Aligned Binary Codes”, Journal of Information Retrieval,Vol. 8, Issue. 1, pp. 151-166, 2005.
[14] Hao Yan et al. “Inverted index compression and query processing
with optimized document ordering”, Proc. of WWW’09, pp. 401410, 2009.
[15] D. Lemire and L. Boytsov. “Decoding billions of integers per second
through vectorization”, Journal of CoRR, 2012.
[16] Fabrizio Silvestri and Rossano Venturini “VSEncoding: efficientcoding and fast decoding of integer lists via dynamic programming”,
Proc. of CIKM’10, pp. 1219-1228, 2010.
[17] Anh VN and Moffat A. “Index compression using 64-bit words. Software”, Practice and Experience, Vol. 40, Issue. 2, pp. 131-147, 2010.
[18] Dean J. “Challenges in building large-scale information retrieval systems”, Proc. of WSDM’09, 2009.
[19] Stepanov AA. and et al. “SIMD-based decoding of posting lists”,
Proc. of CIKM’11, 2011.