DEIM Forum 2016 A8-2

ジョイン方式選択の精度向上をめざしたデータベース問い合わせ処理における CPU 処理コスト計算方法の検討とその評価
田中 剛†*

石川 博‡†‡首都大学東京 システムデザイン研究科 〒191-0065 東京都日野市旭が丘 6-6
E-mail: †tanaka-tsuyoshi@ed.tmu.ac.jp, ‡ishikawa-hiroshi@tmu.ac.jp
あらまし 半導体記録媒体の高速・大容量化に伴い，データベースのクエリ処理における最適な処理手順を求めるためのコスト計算ではディスク IO 処理コストに対して CPU 処理コストの割合が相対的に増大すると考えられる．
そのため，今後はより精度の高い CPU 処理コストの計算方式が求められる．報告者らは，CPU アーキテクチャを考慮したコスト計算モデルを導入し，コスト計算の精度向上に向けて研究を進めている．本研究では，実際のジョイン処理の CPU 動作解析結果を基に CPU 処理コスト計算式を作成し，データベースの種類の変更に対応も含めた方法の検討および評価を実施した．
キーワード データベース, クエリ最適化, CPU コスト, TPC-H

半導体技術の発展に伴い，SSD（Solid State Drive）の高速化および，大容量化が進んでいる．例えば HDD（Hard Disk Drive）の応答時間は約数十ミリ秒であるが，SSD の応答時間は約百マイクロ秒である．さらに 2015 年に発表された 3D XPoint memory は従来の NAND 型フラッシュメモリの 10 倍高速(～10us)[1]になっており，主記憶の応答時間に近づきつつある．また SSD のデータ格
納容量はテラバイトクラスに到達し，更に大容量化が計画されている．これまでデータベースの永続的記録媒体として HDD が広く使用されてきたが，SSD を活用するケースが増加しつつある．
HDD から SSD，さらに高速な半導体記憶にデータベースを格納する媒体が移行することで，DBMS（Database Management System）
に対してはクエリ処理の応答時間が短縮されるという面だけでな
く，DBMS の内部処理も記録媒体の高速化を活かすための施策が必要になると考えられる．
図 1 にオープンソースの DBMS で 2 表ジョインをしたときのCPU 時間とディスク時間の比を示す（計測条件ならびに計測環境は後述の表 3 および図 7 を参照）．この計測では Nested loop joinと Hash join のジョイン方式の 2 方式において，データベースを格納する媒体を HDD から SSD に変更することでディスク時間に対する CPU 時間の割合が Nested Loop Join で約 20 倍，Hash Join で
約 750 倍に増大している．
Nested Loop Join

Hash Join

1.E+02

1.E+03
SSD Nested Loop Join

HDD Nested Loop Join
1.E+01
1.E+00
1.E-01

1.E-02
0.00

0.02
0.04
外部表の選択率

0.06(CPU time) ÷ (Disk time)(CPU time) ÷ (Disk time)

1.E+03

1.E+02

いて HDD 処理時間を正確に見積ること，つまり HDD へのアクセ
ス回数を主に評価していた．しかし，高速な SSD などの記録媒体を活用するにあたっては CPU 時間の正確な見積りが必要になると考えられる．
DBMS はクエリを処理するにあたり，クエリを解析し，複数の実行プランを作成する．そして，これらの各実行プランに対してクエリ処理時間の見積り（以後，コスト計算と呼ぶ）を実施し，複数の候補の中からコストが最小な実行プランを選択する．例えば，DBMS が図 2 の(a)に示す R 表と S 表の 2 表をジョインするケースにおいて，参照する行数が最小となる実行プランとして(b)を生成する．このとき，どのジョイン方式を選択するかで処理時間が異なる．一般に(c)の列 R.C を選択する条件 x の値によって列の選択される割合（以後，選択率と呼ぶ）によって最適なジョイン方式は異なっているため，DBMS はデータベースの統計情報を元にジョイン方式ごとにコスト計算し，自動的に最適な方式を選択する必要がある．このとき(c)のグラフにある最適なジョイン方
式の切り替えとなる選択率 Xcross を正確に見積ることができないと，選択すべきジョイン方式を誤ることになる．

(a) SQL

select count(*)
from R, S
where R.C = x
and R.A = S.B;
選択条件x
選択条件
の変更
の変更

SSD Hash Join
HDD Hash Join(b) 実行プラン(c) 選択率と処理時間

Join方式の判定

Join方式2Join

σR.C=xR[クエリ処理時間]

1. はじめにS

1.E+01

Join方式2 Join方式1
を選択
を選択

Xcross [選択率]

図 2：クエリ最適化におけるコスト計算での課題

1.E+00
1.E-01

1.E-02
0.00

Join方式10.02
0.04
外部表の選択率0.06

図 1: 2 表ジョイン時の CPU 時間とディスク時間比
ディスク時間に対する CPU 時間の相対的な増大は，クエリ処理時間を見積る場合において CPU 処理の正確な見積りが重要であることを示唆している．従来はクエリ処理時間を見積る場合にお一方，データベースのクエリ最適化のためのコスト計算は IO
コストと CPU コストの和で評価することが多い [2][3][5]．例えば，
オープンソースのデータベース（PostgreSQL, MySQL）のコスト
計算式は，（総コスト）＝（CPU コスト）+（IO コスト）＝（レ
コード数）×（CPU 処理単価）＋（ページ数）×（ディスク処理単価）で与えられ，各処理単価は固定値になっている．ディスク性能が向上 し CPU 処 理コスト の精度が重 要になる と固定 的なCPU 単価ではなく，より CPU のアーキテクチャやその動作を踏まえた計算モデルが必要になると考えられる．
こ れ ま で CPU の 性 能 指 標 の 一 つ と し て CPI （ Cycles Per* 株式会社日立製作所 研究開発グループ 情報通信イノベーションセンタ, E-mail: tsuyoshi.tanaka.vz@hitachi.com

Instruction）が古くから使用されてきた．一般に CPI の計算は，実行命令の種類と実行数に着目した計算方法と命令実行パイプライ
ンの滞留（ストール）原因に着目した計算方法がある．特に命令実行パイプラインのストール原因に着目した方法では，分岐予測の失敗や演算器不足，キャッシュミス等のイベントの発生頻度と，それらのイベントによって命令実行パイプラインが停止している
時間の積の合計から CPI を算出する．データベースの CPU の処理モデルを構築する先行研究[4]では，CPU 処理単価をメモリの遅延時間(メモリレイテンシ)の関数で記述している．
以上のような CPU 処理のモデル化の先行事例を考慮すると，データベースの CPU 処理時間を処理単価という単一の指標でモデル化することは困難であると考えられる．そこで，我々は CPU コ
スト計算の精度向上のため以下の取り組みを行う．
 CPU のパイプライン・アーキテクチャを考慮し，CPU 処理を命
令キャッシュミスに起因するパイプライン・ストール時の CPU
サイクル数，分岐予測ミス時の CPU サイクル数，データキャッシュおよび主記憶アクセス時の CPU サイクル数に分類し，CPU動作を包括的に表すことができるモデル化手法を提案する．そして，データベースのジョイン処理の処理時間を見積るために，
ジョイン処理のパタンを 4 種類の部品に分解し，これらの組み合わせにより，ジョイン処理のコスト計算手法を提案する(第 2章)．
 次に，CPU に搭載されたパフォーマンスモニタを用いてジョイン処理時のキャッシュアクセス回数等のイベントの実測値の傾向を分析し，コスト計算式決定する(第 3 章)．
 最後に，コスト計算式を用いて実際の CPU 処理時間との比較検証を実施した結果，コスト計算式を作成するために実測したケースにおいて，ジョイン方式の変化点を外部表の選択率で0.0006 の差で再現することが可能なことを示す(第 4 章)．

2. CPU コスト計算モデルの検討
2.1. コスト計算の方針
報告者らは先行研究[8]にて CPU コスト計算モデルの検討を行った．本研究においては，この CPU コスト計算モデルをベースにさらに適用範囲を拡大する検討を加えた計算モデルを提案する．
最初に，CPU の処理時間を包括的にとらえるために，CPU の処理
全体を俯瞰できる計算モデルを説明する．次に，この計算モデルを構成する各要素を DBMS でクエリを実行時に測定した CPU 搭
載のパフォーマンスモニタによる統計情報を分析し，コスト計算
式を作成する．

2.2. CPU 処理時間のモデル
広くデータベースサーバの用途で用いられている CPU の典型
例 と し て Intel 社 の Nehalem の ア ー キ テ ク チ ャ を 選 択 す る ．
Nehalem アーキテクチャはその後継 CPU の基本構成になっており，
後継 CPU では，主に命令でコードを実行する Front End において
は，マイクロオペレーション(uOP)のキャッシュの追加等が，uOPを実行する Back End において Reorder Buffer の面数の増大，実行ユニットの演算器増強のような部分的な変更が行われている．
Nehalem のパイプライン処理[14]を図 3 に示す．パイプラインの構造は Front End と Back End および Memory 部分に分類される．
Front End では，命令キャッシュから命令をフェッチし， uOP にデコードする処理が行われる．Back End は Front End から発行される uOP を各種演算処理やメモリへのロード・ストア処理が実行される．分岐命令先を予測して投機的に命令実行を進める分岐予測ユニットは Front End に設置されている．図 3 の Memory にはキャッシュメモリや主記憶があり，Front End や Back End からのメ

モリアクセス要求を処理する．Front End での処理はパイプライン
で後続命令が先行命令を追い越すことはなく，インオーダで処理が行われる．そのため，命令キャッシュのミスは，命令キャッシ
ュが下位のメモリから命令をフェッチしてくるまでのサイクル数，
分岐予測ミスは投機的に実行している先行命令を全てフラッシュするため十数サイクル数，Back End に命令を発行不能になる．本
研究では，この現象を命令スタベーション状態と呼ぶことにする．
一方で Back End は命令実行スループットを向上させるためにデータの整合性を失わない範囲で非順序（アウトオブオーダ）に命令を実行する．
In-order Execution
Front End
Instruction
Fetch,
BranchPrediction
L1
Instruction
Cache

Out-of-order Execution

Active

(1)

Stall

(2)

Back End
Resource Full

境界の状態に着目(3) Starvation
Resource
Allocation

Decoder

Reorder
Buffer(ROB)

Reservation
Station(RS)

Execution
Units

Register File
L1DataCache

L2 Cache

Last Level
Cache
(LLC)

MemoryGlobal
Queue
(GQ)

Main
MemoryQuick Path Interconnect (QPI)

図 3：CPU パイプライン処理の例
先に述べたように CPU の動作解析のために CPU 処理時間をモデル化する手法として，CPI が広く用いられている．特に，キャッシュや主記憶へのアクセス特性が性能に与える影響を評価する
ために，キャッシュおよび主記憶のアクセス頻度とメモリ要求をCPU（正確には演算器のロードユニット）が発行してから期待するアドレスのデータが戻ってくる時間（レイテンシ）の積で計算するモデルが広く用いることが一般的である．あるアプリケーシ
ョンを CPU が実行するときの命令数を Iinst，全データが L1 キャッ
シュに載っているときの命令あたりの実行サイクル数を CPI0，レベル 2 以降のキャッシュメモリや主記憶のアクセス回数を Mcachei，Mmem ，各レイテンシを Lcachei ， Lmem とする． BFcachei および BFmem
は重複してロード命令が実行されるときの実効的なメモリレイテ
ンシを表現するための係数(以後，ブロッキングファクタと呼ぶ)である．このとき，CPI は式(1)のように表せる．
𝐶𝑃𝐼 = 𝐶𝑃𝐼0 + ∑𝑀𝑐𝑎𝑐ℎ𝑒𝑖(× 𝐿𝑐𝑎𝑐ℎ𝑒𝑖 × 𝐵𝐹𝑐𝑎𝑐ℎ𝑒𝑖 )
𝐼𝑖𝑛𝑠𝑡
𝑀𝑚𝑒𝑚
+(
× 𝐿𝑚𝑒𝑚 × 𝐵𝐹𝑚𝑒𝑚 )
𝐼𝑖𝑛𝑠𝑡

𝐿2 以降
𝑖

(1)

両辺に命令数掛けることで式(2)に示すアプリケーションを実行したときに要する CPU クロックサイクル数サイクル数(以後，サイクル数)が得られる．特に式(2)の右辺の第二項目のキャッシ
ュおよび主記憶へのアクセス回数とレイテンシおよびブロッキン
グファクタの積をメモリストールサイクル数と以後呼ぶことにする．
𝐶𝑃𝐼 × 𝐼𝑖𝑛𝑠𝑡 = 𝐶𝑃𝐼0 × 𝐼𝑖𝑛𝑠𝑡
+∑

𝐿2 以降
𝑖

(𝑀𝑐𝑎𝑐ℎ𝑒𝑖 × 𝐿𝑐𝑎𝑐ℎ𝑒𝑖 × 𝐵𝐹𝑐𝑎𝑐ℎ𝑒𝑖 )(2)+ (𝑀𝑚𝑒𝑚 × 𝐿𝑚𝑒𝑚 × 𝐵𝐹𝑚𝑒𝑚 )式(1)は図 3 の Back End 側，特に命令実行ユニットのうちロー
ド命令実行からみた CPU の処理モデルあると考えられる．Front
End 側の処理は全て CPI0 に集約している．CPI0 がデータベースの

性能を左右するパラメータと相関がある場合，処理時間を評価す
る上での尺度としては不十分であると考えられる．
そこで，本研究では Front End または Back End の片方の動作を元にした処理モデルではなく，CPU の処理時間全体を包括的にとらえるために，Front End と Back End の両方を考慮できる部分として，Front End と Back End の境界部分，つまりインオーダ処理とアウトオブオーダ処理の境界部分に着目する．
この境界で観測される状態は，(1)Front End で発行された uOPを滞りなく Bank End に転送するサイクル数(CActive)，(2)Back Endのリオーダバッファ等のバッファの飽和や，データの従属性が高いため後続命令が発行できない状態(この状態を以後，まとめてResource Full と呼ぶ)[9]のサイクル数(C Resource_Full )，(3)Front End がBack End に発行可能な命令が存在しない命令スタベーション状
態のサイクル数(CInst_Starvation )の 3 種類に分類できる．つまり，CPUの実行サイクル数(CTotal)は式(3)のように表現できる．
𝐶𝑇𝑜𝑡𝑎𝑙 = 𝐶𝐴𝑐𝑡𝑖𝑣𝑒 + 𝐶𝑅𝑒𝑠𝑜𝑢𝑟𝑐𝑒_𝐹𝑢𝑙𝑙 + 𝐶𝐼𝑛𝑠𝑡_𝑆𝑡𝑎𝑟𝑣𝑎𝑡𝑖𝑜𝑛(3)
命令スタベーション状態は，主に命令キャッシュミスや分岐予
測ミス(CInst_Cache_Miss )によるストールサイクル(CInst_Cache_Miss )に分類
可能なことから式(4)が得られる．BRMP は分岐予測ミスと命令キャ
ッシュミスが同時発生のケースを考慮するための補正係数である．
𝐶𝐼𝑛𝑠𝑡_𝑆𝑡𝑎𝑟𝑣𝑎𝑡𝑖𝑜𝑛 = 𝐶𝐼𝑛𝑠𝑡_𝐶𝑎𝑐ℎ𝑒_𝑀𝑖𝑠𝑠 + 𝐶𝑀𝑖𝑠𝑝𝑟𝑒𝑑𝑖𝑐𝑡 × 𝐵𝐹𝑀𝑃
(4)
先行研究[10]で意思決定処理向けのベンチマークの CPI は 1.5
から 2.5 であると報告されていることから，データベースのクエリ実行では命令はほぼシーケンシャルに実行されている可能性が高い．このような DBMS のメモリアクセス特性を考慮すると Back
End 側で uOP の実行が滞っているサイクル数 CResource_Full は，パイプラインが停止していない状況 CActive の両者はメモリアクセスレ
イテンシが大半を占めていると考え， CData_Cache_Access に一体化して扱うことが可能と考えられる(式(5))．なお， C Data_Cache_Access は式(2)のメモリストールサイクル数の式で計算することができる．
𝐶𝐷𝑎𝑡𝑎_𝐶𝑎𝑐ℎ𝑒_𝐴𝑐𝑐𝑒𝑠𝑠 = 𝐶𝐴𝑐𝑡𝑖𝑣𝑒 + 𝐶𝑅𝑒𝑠𝑜𝑢𝑟𝑐𝑒_𝐹𝑢𝑙𝑙(5)以上の検討から，式(6)の計算式を作成することで CPU での処理
サイクル数の計算が可能になる．
𝐶𝑇𝑜𝑡𝑎𝑙 = 𝐶𝐷𝑎𝑡𝑎_𝐶𝑎𝑐ℎ𝑒_𝐴𝑐𝑐𝑒𝑠𝑠 + 𝐶𝑀𝑖𝑠𝑝𝑟𝑒𝑑𝑖𝑐𝑡𝑖𝑜𝑛 + 𝐶𝐼𝑛𝑠𝑡_𝐶𝑎𝑐ℎ𝑒_𝑀𝑖𝑠𝑠(6)
本研究では，実測から得た統計情報を用いて式(6)の右辺の各項目を計算する式を作成する．
DBMS におけるクエリの処理（表の操作）は選択（selection），
射影（projection），ジョイン（join）などがある．これらの処理の中でジョイン処理はクエリで指定される行の選択率により選択すべきジョイン方式が異なるため，コスト計算の精度が処理時間の増大に結びつく可能性があると考えられる．そこで，本研究ではジョイン処理の最適化のためのコスト計算に焦点をあてる．
基本的なジョイン処理として図 4 にあげた Nested Loop Join
(NLJ)と Hash Join (HJ)の 2 種類がある．
(1)Nested Loop Join (NLJ)
index Key S表Nested Loop Join Case

Hash Join Case

参照する順番

U

U

T
R

S

X

2表ジョイン XYに縮退(a) 2表ジョイン

R

S

Y

(b-2) probeフェーズ

T
部品に分割

X

Y

(b-1) buildフェーズ

図 5：縮退・分割コスト計算
一方，HJ の場合は build フェーズと probe フェーズの繰り返し処理になるため多表のジョインをひとつにまとめて考えることは困難である．そこで，図 5 に示すように，部品(b-1)build フェーズと(b-2)probe フェーズのみのケースの部品に分解することで，外部表と内部表の組み合わせのモデル化が容易になる．これは，多くの DBMS では build フェーズ，probe フェーズの順番でシーケン
シャルに処理されており，各フェーズを分離した実機評価をベー
スにコスト計算式を検討することができるからである．
一方，NLJ と HJ の組み合わせの例も考えられるため，部品として図 6(b-3)の外部表がバッファに存在するケースからスタート
する NLJ を準備する必要がある．
NestedLoop join

X

TR

Hash JoinSY

on buffer(b-3) 外部表がバッファされたNLJ

図 6：分割コスト計算
本研究では，まず方式の有効性について検討するため，あらゆるジョイン処理の基本パタンである 2 表ジョインのケースで計算式を検討する．3 表以上の(a)と(b-3)は今後の課題とする．

2.4. コスト計算式

2.3. DBMS の処理モデル

R表

繰り返しとみなせる．そこで，コンパイラによるループ展開にな
ぞらえ，ひとつの大きな二表間の NLJ とみなすことができると考える．つまり，典型的な 2 表の NLJ（部品(a)）でコスト式を作成
し，多表ジョインでもアクセスする行数（たどる Linked List 数）
のみでコスト計算をすることで対処が可能と考えられる．

(2)Hash Join (HJ)R表Key S表表 1 にコスト計算式の入出力情報および計算式を構成するパラメータを示す．コスト計算式の入力情報は一般的な DBMS であれ
ば，表の作成時等に採取している統計情報に含まれる情報である．
これらの情報でコスト計算可能であれば提案するコスト計算式をDBMS に組み込むことは可能であると考えられる．
表 1：コスト計算式に関わる情報
入力情報

ジョインする外部表の選択率，表の行数

出力情報

計算コスト（CPU サイクル数）

図 4：モデル作成対象の Join 方式

・静的な情報キャッシュメモリおよび主記憶のレイテンシ
・実機計測から得られる情報
計算式の式(6)の右辺の各イベントのサイクル数と入力情報パラメータの関係式（例えば，入力情報と着目イベントのサイ
クル数が線形近似可能であれば，その切片と傾き）

NLJ は外部表を 1 行読み出すごとに内部表の検索を行う．NLJ
によるジョインを一般化すると図 5 に示すように複数のテーブルを順番にたどる処理になる．複数のテーブルやインデックスをた
どる処理を CPU の動作で考慮すると，Linked List をたどる処理の具体的には，前節で検討した 2 表 NLJ と HJ のコスト計算式として，それぞれケースで 2.2 節の式(6)を求める．このとき式(6)の各要素は表の選択率(P)や行数(外部表の行数 RO，内部表の行数 RI )

Key

外部表

内部表

Key

Hash表

外部表 Scan

Scan

内部表

の関数になると考えられる．TNLJ は NLJ の実行時間を，THJ，Tbuild，Tprobe は HJ と HJ の Build フェーズおよび Probe フェーズの実行時間を表す．
Probe フェーズにおいては，表の行数に対して計算値がスケールするように，コスト計算対象の表の行数(R O, R I )と，コスト計算
式のパラメータを求めるために実測データを採取した表の行数(R O_ref , R I_ref )の積の比を掛けている．
Build フェーズでは，ハッシュ表に登録するデータサイズ(D)がハッシュテーブルのサイズ（ buf）より大きい場合，（⌈𝐷⁄𝑏𝑢𝑓 ⌉）回だけ繰り返して実行される．D は外部表のレコードの中でジョインのキーとなる列や group by 句で指定している列や，select 文で抽出する列などのデータサイズおよび列の位置を示すアドレスの合計したデータのサイズを表す．
(𝑅𝑂 × 𝑅𝐼 )𝑇𝑁𝐿𝐽 = 𝐶𝑁𝐿𝐽 𝑇𝑜𝑡𝑎𝑙 (𝑃, 𝑅𝑂 , 𝑅𝐼 ) ×(𝑅𝑂 _𝑟𝑒𝑓 × 𝑅𝐼 _𝑟𝑒𝑓)(7)÷ (CPU 周波数)

𝐶{𝐵𝑢𝑙𝑑,𝑃𝑟𝑜𝑏𝑒}𝐼𝑛𝑠_𝐶𝑎𝑐ℎ𝑒_𝑀𝑖𝑠𝑠 (𝑃, {𝑅𝑂 , 𝑅𝐼 }})= 𝑀𝐿2 𝐼𝑛𝑠𝑡 (𝑃, {𝑅𝑂 , 𝑅𝐼 }}) × 𝐿𝐿2 × 𝐵𝐹𝐿2 𝐼𝑛𝑠𝑡 (𝑃, {𝑅𝑂 , 𝑅𝐼 })+𝑀𝐿𝐿𝐶 𝐼𝑛𝑠𝑡 (𝑃, {𝑅𝑂 , 𝑅𝐼 }) × 𝐿𝐿𝐿𝐶 × 𝐵𝐹𝐿𝐿𝐶 𝐼𝑛𝑠𝑡 (𝑃, {𝑅𝑂 , 𝑅𝐼 })+𝑀𝑀𝑎𝑖𝑛_𝑀𝑒𝑚_𝐼𝑛𝑠𝑡 (𝑃, {𝑅𝑂 , 𝑅𝐼 }) × 𝐿𝑀𝑎𝑖𝑛_𝑀𝑒𝑚
× 𝐵𝐹𝑀𝑎𝑖𝑛_𝑀𝑒𝑚_𝐼𝑛𝑠𝑡 (𝑃, {𝑅𝑂 , 𝑅𝐼 })(14)

𝐶{𝐵𝑢𝑙𝑑,𝑃𝑟𝑜𝑏𝑒}𝑀𝑖𝑠𝑝𝑟𝑒𝑑𝑖𝑐𝑡 (𝑃, {𝑅𝑂 , 𝑅𝐼 }})= 𝑀𝑀𝑖𝑠𝑝𝑟𝑒𝑑𝑖𝑐𝑡 (𝑃, {𝑅𝑂 , 𝑅𝐼 }) × 𝐿𝑀𝑖𝑠𝑝𝑟𝑒𝑑𝑖𝑐𝑡 × 𝐵𝐹𝑀𝑖𝑠𝑝𝑟𝑒𝑑𝑖𝑐𝑡 (𝑃, {𝑅𝑂 , 𝑅𝐼 }) (15)
𝐶{𝐵𝑢𝑖𝑙𝑑,𝑃𝑟𝑜𝑏𝑒}𝐷𝑎𝑡𝑎 𝐶𝑎𝑐ℎ𝑒 𝐴𝑐𝑐𝑒𝑠𝑠 (𝑃, {𝑅𝑂 , 𝑅𝐼 }})= 𝑀𝐿1 𝐷𝑎𝑡𝑎 (𝑃, {𝑅𝑂 , 𝑅𝐼 }) × 𝐿𝐿1 𝐷𝑎𝑡𝑎 × 𝐵𝐹𝐿1 𝐷𝑎𝑡𝑎 (𝑃, {𝑅𝑂 , 𝑅𝐼 })+ 𝑀𝐿2 𝐷𝑎𝑡𝑎 (𝑃, {𝑅𝑂 , 𝑅𝐼 }) × 𝐿𝐿2 × 𝐵𝐹𝐿2 𝐷𝑎𝑡𝑎 (𝑃, {𝑅𝑂 , 𝑅𝐼 })+ 𝑀𝐿𝐿𝐶_𝐷𝑎𝑡𝑎 (𝑃, {𝑅𝑂 , 𝑅𝐼 }) × 𝐿𝐿𝐿𝐶 × 𝐵𝐹𝐿𝐿𝐶_𝐷𝑎𝑡𝑎 (𝑃, {𝑅𝑂 , 𝑅𝐼 })(16)

コスト計算式の精度は，キャッシュや主記憶参照回数，ブロッ
キングファクタの精度に依存する．表 2 に，これらのパラメータを求める方法と推定されるメリット・デメリットを示す．
表 2：パラメータ推定方法

𝑇𝐻𝐽 = 𝑇𝐵𝑢𝑖𝑙𝑑 + 𝑇𝑃𝑟𝑜𝑏𝑒
𝐷 × 𝑃 × 𝑅𝑂
= {𝐶𝐵𝑢𝑖𝑙𝑑 𝑇𝑜𝑡𝑎𝑙 (𝑃, 𝑅𝑂 ) + 𝐶𝑃𝑟𝑜𝑏𝑒 𝑇𝑜𝑡𝑎𝑙 (𝑃, 𝑅𝐼 ) × (⌈
⌉)}
𝑏𝑢𝑓

パラメータ
推定方法
(8)

÷ (CPU 周波数)
NLJ のコスト計算式（式(9)）は，式(2)(6)(7)を組み合わせることで得られる．命令キャッシュ，分岐予測ミス，データアクセス
関連のコストは式(10)(11)(12)で表される．コスト計算式の構造は基本的に，イベントの発生回数とそのレイテンシと補正係数の積
和式になっている． L1D キャッシュ，L2 キャッシュ，LLC キャ
ッ シ ュ お よ び 主 記 憶 か ら デ ー タ 参 照 し た 回 数 (M L1D, ML2, MLLC,
MMain_mem )，分岐予測ミス回数(M Miss_Predict )とブロッキングファクタ
BF は，選択率 P や表の行数(R O，RI )の関数で表される．データ参照の場合，命令と異なり L1 キャッシュまで含めているのはストールサイクルだけでなく L1 キャッシュにヒットしたケースまで
𝐶𝑁𝐿𝐽 𝐷𝑎𝑡𝑎 𝐶𝑎𝑐ℎ𝑒 𝐴𝑐𝑐𝑒𝑠𝑠 には含めているからである．
𝐶𝑁𝐿𝐽 𝑇𝑜𝑡𝑎𝑙 (𝑃, 𝑅𝑂 , 𝑅𝐼 )= 𝐶𝑁𝐿𝐽 𝐼𝑁𝑆 𝐶𝑎𝑐ℎ𝑒 𝑀𝑖𝑠𝑠 (𝑃, 𝑅𝑂 , 𝑅𝐼 ) + 𝐶𝑁𝐿𝐽 𝑀𝑖𝑠𝑝𝑟𝑒𝑑𝑖𝑐𝑡 (𝑃, 𝑅𝑂 , 𝑅𝐼 )+ 𝐶𝑁𝐿𝐽 𝐷𝑎𝑡𝑎 𝐶𝑎𝑐ℎ𝑒 𝐴𝑐𝑐𝑒𝑠𝑠 (𝑃, 𝑅𝑂 , 𝑅𝐼 )(9)

𝐶𝑁𝐿𝐽 𝐼𝑛𝑠_𝐶𝑎𝑐ℎ𝑒_𝑀𝑖𝑠𝑠 (𝑃, 𝑅𝑂 , 𝑅𝐼 )= 𝑀𝐿2𝐼𝑛𝑠𝑡 (𝑃, 𝑅𝑂 , 𝑅𝐼 ) × 𝐿𝐿2 × 𝐵𝐹𝐿2𝐼𝑛𝑠𝑡 (𝑃, 𝑅𝑂 , 𝑅𝐼 )+𝑀𝐿𝐿𝐶𝐼𝑛𝑠𝑡 (𝑃, 𝑅𝑂 , 𝑅𝐼 ) × 𝐿𝐿𝐿𝐶 × 𝐵𝐹𝐿𝐿𝐶𝐼𝑛𝑠𝑡 (𝑃, 𝑅𝑂 , 𝑅𝐼 )+𝑀𝑀𝑎𝑖𝑛_𝑀𝑒𝑚_𝐼𝑛𝑠𝑡 (𝑃, 𝑅𝑂 , 𝑅𝐼 ) × 𝐿𝑀𝑎𝑖𝑛_𝑀𝑒𝑚
× 𝐵𝐹𝑀𝑎𝑖𝑛_𝑀𝑒𝑚_𝐼𝑛𝑠𝑡 (𝑃, 𝑅𝑂 , 𝑅𝐼 )(10)

𝐶𝑁𝐿𝐽 𝑀𝑖𝑠𝑝𝑟𝑒𝑑𝑖𝑐𝑡 (𝑃, 𝑅𝑂 , 𝑅𝐼 )= 𝑀𝑀𝑖𝑠𝑝𝑟𝑒𝑑𝑖𝑐𝑡 (𝑃, 𝑅𝑂 , 𝑅𝐼 ) × 𝐿𝑀𝑖𝑠𝑝𝑟𝑒𝑑𝑖𝑐𝑡 × 𝐵𝐹𝑀𝑖𝑠𝑟𝑒𝑑𝑖𝑐𝑡 (𝑃, 𝑅𝑂 , 𝑅𝐼 )(11)

𝐶𝑁𝐿𝐽 𝐷𝑎𝑡𝑎 𝐶𝑎𝑐ℎ𝑒 𝐴𝑐𝑐𝑒𝑠𝑠 (𝑃, 𝑅𝑂 , 𝑅𝐼 )= 𝑀𝐿1𝐷𝑎𝑡𝑎 (𝑃, 𝑅𝑂 , 𝑅𝐼 ) × 𝐿𝐿1 × 𝐵𝐹𝐿1𝐷𝑎𝑡𝑎 (𝑃, 𝑅𝑂 , 𝑅𝐼 )+ 𝑀𝐿2𝐷𝑎𝑡𝑎 (𝑃, 𝑅𝑂 , 𝑅𝐼 𝐼) × 𝐿𝐿2 × 𝐵𝐹𝐿2𝐷𝑎𝑡𝑎 (𝑃, 𝑅𝑂 , 𝑅𝐼 )+ 𝑀𝐿𝐿𝐶_𝐷𝑎𝑡𝑎 (𝑃, 𝑅𝑂 , 𝑅𝐼 ) × 𝐿𝐿𝐿𝐶 × 𝐵𝐹𝐿𝐿𝐶_𝐷𝑎𝑡𝑎 (𝑃, 𝑅𝑂 , 𝑅𝐼 )推定メリット

推定デメリットパ フ ォ ー マ ン ス モ ニ CPU パイプラインの CPU ア ー キ テ ク チ ャ が 変 更タを用いた実測
状態 の正 確な 統 計情 時のパラメータ見直しが必要
報の取得可能(再計測など)ソ フ ト ウ ェ ア の 動 作 CPU アーキテクチャ 命令キャッシュのモデル化困から机上推定の違 いや ソフ ト のバ 難ージョンの影響少
シミュレーション
計算時間増大，CPU パイプラ
インの状態を分類した評価は詳細なハードおよびソフトのエミュレーションが必要

本研究では CPU コスト計算の精度向上が可能にすることが目的であるため，CPU パイプラインの状態をモデル化が容易なパフォーマンスモニタでの計測値から統計的に計算式のパラメータを求める方法を用いる．机上推定やシミュレーションを併用した形
でパフォーマンスモニタを用いるケースのデメリットをカバーできる可能性があるので今後の検討課題とする．
レイテンシについてはハードウェアの構造に従うもので DBMSの処理内容とは独立している．一般的に分析系のクエリでは文献[9]で述べられているようにメモリに対するアクセス集中はほとんど起こらず，待ち行列によるレイテンシの増大はほとんど起きないと仮定した．

3. コスト計算式のパラメータ設定のための実機評価(12)同様に HJ のコスト計算式（式(13)）も式(2)(6)(8)を組み合わせることで得られる．命令キャッシュ，分岐予測ミス，データアクセス関連のコストは式(14)(15)(16)で表される．キャッシュおよび
主 記 憶 参 照 回 数 (ML1D ， ML2, MLLC , M Main_mem )と 分 岐 予 測 ミ ス 回 数(M Miss_Predict )とブロッキングファクタ BF は，Build フェーズでは選
択率 P と外部表の行数 R O の関数で表され，Probe フェーズでは選
択率 P と内部表の行数 RI の関数で表される．
𝐶{𝐵𝑢𝑖𝑙𝑑,𝑃𝑟𝑜𝑏𝑒}𝑇𝑜𝑡𝑎𝑙 (𝑃, {𝑅𝑂 , 𝑅𝐼 }})= 𝐶{𝐵𝑢𝑖𝑙𝑑,𝑃𝑟𝑜𝑏𝑒} 𝐼𝑛𝑠𝑡_𝐶𝑎𝑐ℎ𝑒_𝑀𝑖𝑠𝑠 (𝑃, {𝑅𝑂 , 𝑅𝐼 }})+𝐶{𝐵𝑢𝑙𝑑,𝑃𝑟𝑜𝑏𝑒}𝑀𝑖𝑠𝑝𝑒𝑑𝑖𝑐𝑡 (𝑃, {𝑅𝑂 , 𝑅𝐼 }})(13)+ 𝐶{𝐵𝑢𝑙𝑑,𝑃𝑟𝑜𝑏𝑒}𝐷𝑎𝑡𝑎 𝐶𝑎𝑐ℎ𝑒 𝐴𝑐𝑐𝑒𝑠𝑠 (𝑃, {𝑅𝑂 , 𝑅𝐼 }})表 1 のパラメータを求めるために実機計測を行った．計測環境を表 3 に示す．CPU としては Nehalem と同一のアーキテクチャである Westmere を使用した．2 ソケットのサーバを用いたため，主記憶はローカルとリモートの二種類あり，アクセスするレイテン
シが異なる NUMA（Non Uniform Memory Access）構成になっている．データベースを格納するディスク装置としては実験効率の向上を目的に，NVMe Flash SSD を用いた．DBMS としてはオープ
ンソースの MariaDB[15]を用いた．MariaDB はマルチスレッド，
非同期 IO 等をサポートしており，最新のハードウェア特性を生かすことができると考えられることと，複数のジョイン方式（4種類）をサポートしている点で選択した．なお，MariaDB がサポートする NLJ は正確には NLJ を改善した BNL（Block Nested Loop
Join）であるが，今回用いたクエリとインデックスの条件では一般的な NLJ と同様の動作をする．また，MariaDB は NUMA をサポートしていないため，OS の起動時パラメータでインターリー
ブの設定にした．本研究で使用したバージョンの MariaDB ではジ
ョイン方式の選択方法は，設定パラメータで固定的に選択する仕MariaDB 10.1.8(b) 実行プラン(a) SQL
select count(*)
from customer, orders
wherec_mktsegment = 'MACHINERY'
条件1
and c_acctbal > N
and c_custkey = o_custkey
and o_orderdate < date '1995-03-06‘;
条件2

Join方式を
DBMSの
設定で指定

γcount(*)σ条件2c_custkey=o_custkeyσ条件1(c) 選択条件と選択率

N
9998
9978
9798
9200
9000
8000
7000
条件1の
3.62E-05 4.00E-04 3.67E-03 1.45E-02 1.82E-02 3.64E-02 5.45E-02
選択率

図 7：計測およびコスト計算対象のクエリ

4. 実機計測結果およびコスト計算式

1.00E+10

2.00E+09

1.00E+09

0.00E+00

0.00E+00
0

0.02
0.04
選択率
命令 L2

0

0.02
0.04
0.06
選択率
命令 LLC local
命令 LLC remote
命令 主記憶 local
命令 主記憶 remote0.06

図 8：NLJ における命令参照回数(a) CNLJ Inst_Cache_Miss(b) CNLJ Data_Cache_Access
1.0E+124.0E+113.0E+112.0E+11

1.0E+110.0E+00
0

1E+12

2E+12

8.0E+11
6.0E+11
4.0E+112.0E+110.0E+00
0

1E+12

2E+12

ToTal Data Access [cycle]

Instruction Miss Penalty [cycle]

図 9：メモリ参照回数の合計と CNLJ Inst_Cache_Miss および，
CNLJ Data_Cache_Acces の関係
命令参照のケースと同様にデータ参照についても同様に分析
すると，データ参照についても図 10 に示すように選択率に対して直線で近似できることが分る．また，図 9(b)に示すように全メモ
リ解消のデータ参照回数とメモリレイテンシの積の合計（ Total
Data Access）と𝐶𝑁𝐿𝐽 𝐷𝑎𝑡𝑎_𝐶𝑎𝑐ℎ𝑒_𝐴𝑐𝑐𝑒𝑠𝑠 の関係も直線で近似することができる（図中の点線は回帰直線）．

4.1. NLJ の測定結果

3.E+11

4.E+093.E+09

参照回数

実機にて計測した 2 表ジョイン実行時のパフォーマンスモニタの 測 定 値 か ら 得 ら れ る デ ー タ を 加 工 ・ 分 析 し ， 式 (9) の𝐶𝑁𝐿𝐽 𝐼𝑛𝑠_𝐶𝑎𝑐ℎ𝑒_𝑀𝑖𝑠𝑠 ，𝐶𝑁𝐿𝐽 𝑀𝑖𝑠𝑝𝑟𝑒𝑑𝑖𝑐𝑡 ，𝐶𝑁𝐿𝐽 𝐷𝑎𝑡𝑎_𝐶𝑎𝑐ℎ𝑒_𝐴𝑐𝑐𝑒𝑠𝑠 の計算式を求める．
まず，ジョイン処理の外部表の選択率と命令キャッシュミス，分岐予測ミス，キャッシュおよび主記憶上の命令以外のデータへの参照回数の関係式を求める．次に，キャッシュおよび主記憶への参照回数とレイテン
シの総和と𝐶𝑁𝐿𝐽 𝐼𝑛𝑠_𝐶𝑎𝑐ℎ𝑒_𝑀𝑖𝑠𝑠 と 𝐶𝑁𝐿𝐽 𝐷𝑎𝑡𝑎_𝐶𝑎𝑐ℎ𝑒_𝐴𝑐𝑐𝑒𝑠𝑠 の実測結果の関係
式を計測結果から求める．𝐶𝑁𝐿𝐽 𝑀𝑖𝑠𝑝𝑟𝑒𝑑𝑖𝑐𝑡 については，分岐予測ミス回数に Front End のパイプライン段数（Nehalem では 12）を掛けた分岐予測
ミスペナルティ（Misprediction Penalty）と𝐶𝑁𝐿𝐽 𝑀𝑖𝑠𝑝𝑟𝑒𝑑𝑖𝑐𝑡 の関係式を実測結果から求める．メモリレイテンシは文献[16]の数値を参照する．
外部表の選択率に対する NLJ の命令のキャッシュヒット回数（キャッシュアクセス回数）および主記憶アクセス回数の関係を
図 8 に示す．計測に使用したサーバは 2 ソケット構成であるため，
LLC と主記憶は DBMS が動作した CPU コアと同じソケットに搭載される LLC や主記憶へのアクセスともう一方のソケットに搭載されている LLC と主記憶にアクセスするケースがあり，前者を1.50E+10

5.00E+09

orderscustomer

3.00E+09
参照回数

参照回数

2.00E+10

CPUサイクル数 [cycle]

DBMS

Disk (OS)4.00E+09

2.50E+10

2.E+11

参照回数

OS

PCIe NVMe Flash SSD 800GB x 1
Note: Max throughput suppressed by server’s PCIe I/F(ver.1.0a), about 1/4 max throughput.
SAS 10krpm 600GB,RAID5 (4 Data + 1 Parity)
Note: DB is stored in the measurement of 図 1.
CentOS 6.6 (x64)

Disk (DB)

ローカル（local），後者をリモート（remote）と呼ぶ．
図 8 の測定結果から，いずれのメモリ階層へアクセスする場合
でも選択率に対して線形に増大していくことが分る．図の点線は回帰直線を示しており，これらのメモリ参照回数は選択率を変数とする 1 次関数で近似することができることが分る．
図 9(a)に 式 (2)の 右 辺 第 二 項 に 相 当 す る 命 令 ミ ス ペ ナ ル テ ィ（Instruction Miss Penalty）と命令キャッシュミス時のストールサ
イクル数である𝐶𝑁𝐿𝐽 𝐼𝑛𝑠_𝐶𝑎𝑐ℎ𝑒_𝑀𝑖𝑠𝑠 の関係と，点線で回帰直線を示す．

CPUサイクル数 [cycle]

様になっている．
評 価 対 象 ク エ リ と そ の 計 測 条 件 を 図 7 に 示 す ． SQL 文 は
TPC-H[13]の Query3 を 2 表ジョインの評価用に改造し，ジョイン
のみ特化した記述になっている．データベースとして TPC-H のSF100(100GB)を用いた．クエリが検索対象とする．c_acctbal 列への検索条件を変化させることで，参照するデータの選択率を変更した．
データベースのインデックスは TPC-H の仕様[13]で規定されているうち，主キー，外部キーに設定した．CPU のパフォーマンス
カウンタのデータは，Intel® Vtune™ Amplifier XE を使用して計測した．カウンタの内容の解釈については文献[14]を参考にした．
今回計測したカウンタは，キャッシュメモリアクセスに関わるものとパイプラインの状態（ストールサイクル数）やキャッシュア
クセス回数を主に採取した．
表 3：計測環境
Xeon L5630 2.13GHz 4core, LLC 12MB
CPU
[Westmere-EP]) x2
DDR3 24GB (4GB x6)
Memory1.E+11

2.E+09

1.E+090.E+00
0

0.02
0.04
選択率
L1D

0.06

0.E+00
0

0.02
0.04
0.06
選択率
L2
LLC (Local)
LLC (Remote)
主記憶 (local)
主記憶 (Remote)

図 10：NLJ におけるデータ参照回数
𝐶𝑁𝐿𝐽 𝑀𝑖𝑠𝑝𝑟𝑒𝑑𝑖𝑐𝑡 も同様に傾向を分析すると図 11 に示すように選択率に対して直線（実線）で近似できることが分る．

1.5E+10
1.0E+105.0E+09
0.0E+00
0

0.02

0.04

0.06

選択率

(a) CHJ Build Inst Cache Miss

図 11：分岐予測ミスペナルティと𝑪𝑵𝑳𝑱 𝑴𝒊𝒔𝒑𝒓𝒆𝒅𝒊𝒄𝒕 の関係

𝐶𝑁𝐿𝐽 𝑀𝑖𝑠𝑝𝑟𝑒𝑑𝑖𝑐𝑡 = 𝑆𝑁𝐿𝐽 𝑀𝑖𝑠𝑝𝑟𝑒𝑑𝑖𝑐𝑡 × 𝑃 × 𝐿𝑀𝑖𝑠𝑝𝑟𝑒𝑑𝑖𝑐𝑡
𝐶𝑁𝐿𝐽 𝐷𝑎𝑡𝑎𝐶𝑎𝑐ℎ𝑒(18)= 𝑆𝑁𝐿𝐽 𝐿1𝐷𝑎𝑡𝑎 × 𝑃 × 𝐿𝐿1 + 𝑆𝑁𝐿𝐽 𝐿2𝐷𝑎𝑡𝑎 × 𝑝 × 𝐿𝐿2
𝐴𝑐𝑐𝑒𝑠𝑠+ 𝑆𝑁𝐿𝐽 𝐿𝐿𝐶_𝐷𝑎𝑡𝑎 × 𝑃 × 𝐿𝐿𝐿𝐶 + 𝑆𝑁𝐿𝐽 𝑀𝑎𝑖𝑛_𝑀𝑒𝑚× 𝑃 × 𝐿𝑀𝑎𝑖𝑛_𝑀𝑒𝑚

CPUサイクル数 [cycle]

以上の分析結果から，式(17)(18)(19)が得られる．ただし，𝑆𝑁𝐿𝐽 は計測結果から得られる定数値である．
𝐶𝑁𝐿𝐽 𝐼𝑛𝑠𝑡𝐶𝑎𝑐ℎ𝑒= 𝑆𝑁𝐿𝐽 𝐿2 𝐼𝑛𝑠𝑡 × 𝑃 × 𝐿𝐿2
𝑀𝑖𝑠𝑠+𝑆𝐿𝑁𝐿𝐽 𝐿𝐶 𝐼𝑛𝑠𝑡 × 𝑃 × 𝐿𝑁𝐿𝐽 𝐿𝐿𝐶𝐼𝑛𝑠𝑡 + 𝑆𝑁𝐿𝐽 𝑀𝑎𝑖𝑛_𝑀𝑒𝑚_𝐼𝑛𝑠𝑡 × 𝑃(17)× 𝐿𝑀𝑎𝑖𝑛 𝑀𝑒𝑚 𝐼𝑛𝑠𝑡

5.0E+09
4.0E+09(b) CHJ Build Data_Cache_Access
2.0E+10

6.0E+09

CPUサイクル数 [cycle]

CPUサイクル数 [cycle]

考えられる．そこで，HJ の計算式の切片は参照する表の行数に比
例すると仮定した．この仮説の検証については今後の課題とする．
命令ミスペナルティと𝐶𝐻𝐽 𝐵𝑢𝑖𝑙𝑑 𝐼𝑛𝑠 𝐶𝑎𝑐ℎ𝑒 𝑀𝑖𝑠𝑠 についてはデータの分布具合から直線で近似可能と仮定した（図 14(a)）．しかし，ばらつきが多いためデータの採取方法含め更なる検討が必要である．
𝐶𝐻𝐽 𝐵𝑢𝑖𝑙𝑑 𝐷𝑎𝑡𝑎 𝐶𝑎𝑐ℎ𝑒 𝐴𝑐𝑒𝑠𝑠 については，データ参照(Total Data Access)との相関は弱く，一定値をとると考えられる（図 14(b)）．

CNLJ Mispredict

2.0E+10

1.5E+10CHJ Build Inst Cache Miss (0)CHJ Build Data_Cache_Access(0)1.0E+103.0E+09
2.0E+09

5.0E+09

1.0E+09

0.0E+00
4.5E+09 5E+09 5.5E+09 6E+09

0.0E+00
3.5E+10Instruction Miss Penalty [cycle]

4E+10

4.5E+10

ToTal Data Access [cycle](19)
図 14：メモリ参照回数の合計と CHJ Build Instst_Cache_Miss
および CHJ Build Data_Cache_Acces の関係

4.2. HJ Build フェーズの測定結果

8.E+06

3.E+086.E+06

2.E+084.E+06

2.E+06

1.E+08

0

0.02
0.04
選択率

0

0.06

命令 L2

0.02

0.04
選択率

0.06

命令 LLC local

命令 LLC remote

命令 主記憶 local

命令 主記憶 remote

図 12: HJ の Build フェーズにおける命令参照回数
1.E+108.E+07

参照回数

参照回数

6.E+07

6.E+094.E+094.E+072.E+072.E+090.E+000.E+00
0

0.02

0.04
選択率
L1D

0.06

CHJ Build Mispredict

6.5E+08
6.3E+08
6.1E+08
5.9E+08
0.E+00

5.E+05

1.E+06

図 15：分岐予測ミスペナルティと𝑪𝑯𝑱 𝑩𝒖𝒊𝒍𝒅 𝑴𝒊𝒔𝒑𝒓𝒆𝒅𝒊𝒄𝒕の関係
以上の分析結果を踏まえると，式(20)(21)(22)が得られる．ただし，𝑆𝐻𝐽 𝐵𝑢𝑖𝑙𝑑 は計測結果から得られる定数値である．𝐶𝐻𝐽 𝐵𝑢𝑖𝑙𝑑 (0)は
図 14(a)，図 15 の近似直線の切片である．𝐶𝑁𝐿𝐽 𝐷𝑎𝑡𝑎 𝐶𝑎𝑐ℎ𝑒 𝐴𝑐𝑐𝑒𝑠𝑠 (0)は
図 14(b)に示す計測データの平均である．
𝐶𝐻𝐽 𝐵𝑢𝑖𝑙𝑑 𝐼𝑛𝑠𝑡 𝐶𝑎𝑐ℎ𝑒 𝑀𝑖𝑠𝑠 = (𝑆𝐻𝐽 𝐵𝑢𝑖𝑙𝑑 𝐿2 𝐼𝑛𝑠𝑡 × 𝑃 × 𝐿𝐿2+ 𝑆𝐻𝐽 𝐵𝑢𝑖𝑙𝑑 𝐿𝐿𝐶 𝐼𝑛𝑠𝑡 × 𝑃 × 𝐿𝐿𝐿𝐶𝐼𝑛𝑠𝑡+ 𝑆𝐻𝐽 𝐵𝑢𝑖𝑙𝑑 𝑀𝑎𝑖𝑛_𝑀𝑒𝑚_𝐼𝑛𝑠𝑡 × 𝑃(20)× 𝐿𝑀𝑎𝑖𝑛 𝑀𝑒𝑚 𝐼𝑛𝑠𝑡 )𝐶𝐻𝐽 𝐵𝑢𝑖𝑙𝑑 𝐼𝑛𝑠𝑡 𝐶𝑎𝑐ℎ𝑒 𝑀𝑖𝑠𝑠 (0)𝑅𝑂
××
𝐴𝑣𝑔(𝐼𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛 𝑀𝑖𝑠𝑠 𝑃𝑒𝑛𝑎𝑙𝑡𝑦) 𝑅𝑂_𝑟𝑒𝑓

1.E+108.E+096.7E+08

選択率×外部表行数 [行]0.E+000.E+00

𝐶𝐻𝐽 𝐵𝑢𝑖𝑙𝑑 𝑀𝑖𝑠𝑝𝑟𝑒𝑑𝑖𝑐𝑡 も同様に傾向を分析すると図 15 に示すように選択率に対して直線で近似可能なことが分る．
CPUサイクル数 [cycle]

4.E+08

参照回数

参照回数

HJ の Build フェーズでの命令参照，データ参照についても調査した結果，命令回数については選択率について直線近似できることが分る（図 12）．

0

0.02

0.04
0.06
選択率
L2
LLC (local)
LLC (Remte)
主記憶 (local)
主記憶 (Remote)図 13：HJ の Build フェーズにおける命令参照回数
データ参照については一定値になっている（図 13）．これはデータアクセスについては選択率が変化しても外部表全体をスキャンしているためデータアクセス量は変わらないためと考えられる．
一方，命令についてはハッシュテーブルへの登録処理の関数が選択率増大とともに頻度が増大するために選択率と命令参照回数に依存関係が生じているためと考えられる．ただし，NLJ ではほぼ原点を通る直線で近似可能なことがグラフより判断できるが，HJ
では基本的に表の行を全てスキャンするのでグラフの切片にあたる選択率が 0 のときのデータ参照回数が表の行数と関係があると𝐶𝐻𝐽 𝐵𝑢𝑖𝑙𝑑 𝑀𝑖𝑠𝑝𝑟𝑒𝑑𝑖𝑐𝑡 = 𝑆𝐻𝐽 𝐵𝑢𝑖𝑙𝑑 𝑀𝑖𝑠𝑝𝑟𝑒𝑑𝑖𝑐𝑡 × 𝑃 × 𝐿𝑀𝑖𝑠𝑝𝑟𝑒𝑑𝑖𝑐𝑡+ 𝐶𝐻𝐽 𝐵𝑢𝑖𝑙𝑑 𝑀𝑖𝑠𝑝𝑟𝑒𝑑𝑖𝑐𝑡 (0) × 𝑃 × 𝑅𝑂

(21)

𝐶𝐻𝐽 𝐵𝑢𝑖𝑙𝑑 𝐷𝑎𝑡𝑎 𝐶𝑎𝑐ℎ𝑒 𝐴𝑐𝑐𝑒𝑠𝑠= (𝑆𝐻𝐽 𝐵𝑢𝑖𝑙𝑑 𝐿1 𝐷𝑎𝑡𝑎 × 𝐿𝐿1 + 𝑆𝐻𝐽 𝐵𝑢𝑖𝑙𝑑 𝐿2𝐷𝑎𝑡𝑎
× 𝐿𝐿2 + 𝑆𝐻𝐽 𝐵𝑢𝑖𝑙𝑑 𝐿𝐿𝐶_𝐷𝑎𝑡𝑎 × 𝐿𝐿𝐿𝐶
+ 𝑆𝐻𝐽 𝐵𝑢𝑖𝑙𝑑 𝑀𝑎𝑖𝑛_𝑀𝑒𝑚 × 𝐿𝑀𝑎𝑖𝑛_𝑀𝑒𝑚 )𝐶𝐻𝐽 𝐵𝑢𝑖𝑙𝑑 𝐷𝑎𝑡𝑎 𝐶𝑎𝑐ℎ𝑒 𝐴𝑐𝑐𝑒𝑠𝑠 (0)𝑅𝑂+
×𝐴𝑣𝑔(𝑇𝑜𝑡𝑎𝑙 𝐷𝑎𝑡𝑎 𝐴𝑐𝑐𝑒𝑠𝑠) 𝑅𝑂_𝑟𝑒𝑓(22)4.3. J Probe フェーズの測定結果
図 16 の測定結果から，どのメモリ階層に対しても命令参照回
数については NLJ と同様に原点を通る直線で近似可能である．データ参照回数については HJ Build フェーズと同様にほぼ一定値となっている（図 17）．Probe フェーズでも基本的にテーブルスキャ
ンであるためデータ参照については Build フェーズと同じ傾向が

2.50E+10

2.50E+09

2.00E+10

2.00E+09
参照回数

1.50E+10
1.00E+10
5.00E+09

1.50E+09
1.00E+09
5.00E+08

0.00E+00

𝐶𝐻𝐽 𝑃𝑟𝑜𝑏𝑒 𝐼𝑛𝑠𝑡 𝐶𝑎𝑐ℎ𝑒 𝑀𝑖𝑠𝑠= (𝑆𝐻𝐽 𝑃𝑟𝑜𝑏𝑒 𝐿2 𝐼𝑛𝑠𝑡 × 𝑃 × 𝐿𝐿2 + 𝑆𝐻𝐽 𝑃𝑟𝑜𝑏𝑒 𝐿𝐿𝐶 𝐼𝑛𝑠𝑡 × 𝑃 × 𝐿𝐿𝐿𝐶𝐼𝑛𝑠𝑡+ 𝑆𝐻𝐽 𝑃𝑟𝑜𝑏𝑒 𝑀𝑎𝑖𝑛_𝑀𝑒𝑚_𝐼𝑛𝑠𝑡 × 𝑃 × 𝐿𝑀𝑎𝑖𝑛 𝑀𝑒𝑚 𝐼𝑛𝑠𝑡 )𝐶𝐻𝐽 𝑃𝑟𝑜𝑏𝑒 𝐼𝑛𝑠𝑡 𝐶𝑎𝑐ℎ𝑒 𝑀𝑖𝑠𝑠 (0)𝑅𝑂
××
𝐴𝑣𝑔(𝑀𝑒𝑎𝑠𝑢𝑟𝑒𝑑 𝐼𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛 𝑀𝑖𝑠𝑠 𝑃𝑒𝑛𝑎𝑙𝑡𝑦) 𝑅𝑂_𝑟𝑒𝑓(23)

𝐶𝐻𝐽 𝑃𝑟𝑜𝑏𝑒 𝑀𝑖𝑠𝑝𝑟𝑒𝑑𝑖𝑐𝑡 = 𝑆𝐻𝐽 𝑃𝑟𝑜𝑏𝑒 𝑀𝑖𝑠𝑝𝑟𝑒𝑑𝑖𝑐𝑡 × 𝑃 × 𝐿𝑀𝑖𝑠𝑝𝑟𝑒𝑑𝑖𝑐𝑡+ 𝐶𝐻𝐽 𝑃𝑟𝑜𝑏𝑒 𝑀𝑖𝑠𝑝𝑟𝑒𝑑𝑖𝑐𝑡 (0) × 𝑃 × 𝑅𝑂

(24)

𝐶𝐻𝐽 𝑃𝑟𝑜𝑏𝑒 𝐷𝑎𝑡𝑎 𝐶𝑎𝑐ℎ𝑒 𝐴𝑐𝑐𝑒𝑠𝑠= (𝑆𝐻𝐽 𝑃𝑟𝑜𝑏𝑒 𝐿1𝐷𝑎𝑡𝑎 × 𝐿𝐿1 + 𝑆𝐻𝐽 𝑃𝑟𝑜𝑏𝑒 𝐿2𝐷𝑎𝑡𝑎
× 𝐿𝐿2 + 𝑆𝐻𝐽 𝑃𝑟𝑜𝑏𝑒 𝐿𝐿𝐶_𝐷𝑎𝑡𝑎 × 𝐿𝐿𝐿𝐶
+ 𝑆𝐻𝐽 𝑃𝑟𝑜𝑏𝑒 𝑀𝑎𝑖𝑛_𝑀𝑒𝑚 × 𝐿𝑀𝑎𝑖𝑛_𝑀𝑒𝑚 )𝐶𝐻𝐽 𝑃𝑟𝑜𝑏𝑒 𝐷𝑎𝑡𝑎 𝐶𝑎𝑐ℎ𝑒 𝐴𝑐𝑐𝑒𝑠𝑠 (0)𝑅𝑂+
×𝐴𝑣𝑔(𝑇𝑜𝑡𝑎𝑙 𝐷𝑎𝑡𝑎 𝐴𝑐𝑐𝑒𝑠𝑠) 𝑅𝑂_𝑟𝑒𝑓(25)

0.00E+00
0

0.02
0.04
選択率

0.06

0

0.02
0.04
選択率

命令 LLC local
命令 主記憶 local

命令 L2

0.06

命令 LLC remote
命令 主記憶 remote

図 16: HJ の Probe フェーズにおける命令参照回数
1.E+11

8.E+088.E+10

6.E+08

参照回数

参照回数

図 14(a)，図 15 の近似直線の切片である．𝐶𝐻𝐽 𝑃𝑟𝑜𝑏𝑒 𝐷𝑎𝑡𝑎 𝐶𝑎𝑐ℎ𝑒 𝐴𝑐𝑐𝑒𝑠𝑠 (0)は図 14(b)に示す計測データの平均である．

6.E+104.E+105. コスト計算結果
実測値から推測したパラメータ用いてコスト計算式を求め，DBMS が自身で計測している CPU 処理時間との比較を行った（図20）．HJ については，DBMS の統計情報として計測している CPU
処理時間をほぼ再現できている．ジョイン方式を決定する上で特に重要なグラフの交点は選択率で 0.0006 の差があり，ほぼ再現できている．一方，NLJ については，選択率が高い部分でずれが見られ，今後の改良点である．

4.E+08600

2.E+082.E+10500

NLJ（コスト計算式）[実線]

0.E+000.E+00
0

0.02
0.04
選択率

0

0.06

0.02
0.04
選択率

L2
LLC (Remote)
主記憶 (Remote)

L1D

0.06

LLC (Local)
主記憶 (Local)

実行時間[秒]

参照回数あると考えられる．命令参照については，外部表で検索対象の行が存在しないケースでは参照される内部表の行は存在しないため，近似曲線が原点を通ると考えられる．
命令ミスペナルティと𝐶𝐻𝐽 𝑝𝑟𝑜𝑏𝑒 𝐼𝑛𝑠 𝐶𝑎𝑐ℎ𝑒 𝑀𝑖𝑠𝑠 については直線近似可能である（図 16 (a)）．𝐶𝐻𝐽 𝑃𝑟𝑜𝑏𝑒 𝐷𝑎𝑡𝑎 𝐶𝑎𝑐ℎ𝑒 𝐴𝑐𝑒𝑠𝑠 についても同様に
データ参照の合計値(Total Data Access)と正の相関があり，直線近似可能と考えられる（図 18(b)）．
𝐶𝐻𝐽 𝑃𝑟𝑜𝑏𝑒 𝑀𝑖𝑠𝑝𝑟𝑒𝑑𝑖𝑐𝑡 も同様に傾向を分析すると図 19 に示すように選択率に対して直線で近似可能なことが分る．

400
300
NLJ（実測)[点線]200

HJ（実測）[点線]

図 17：HJ の Probe フェーズにおけるデータ参照回数(a) CHJ Probe Inst Cache Miss(b) CHJ Probe Data_Cache_Access

2.0E+100.0E+00
0

5E+11

1E+12

Instruction Miss Penalty [cycle]

00

1.2E+110.06

図 20：実測結果とコスト計算値の比較

4.0E+100.0E+00
3.5E+114E+114.5E+11
ToTal Data Access [cycle]

CHJ Probe Mispredict

3.0E+09110108

HJ（実測）[点線]106

NLJ（実測)[点線]

NLJ（コスト計算式）
[実線]

104

HJ
（コスト計算式）[実線]

102

2.0E+09
1.0E+09
0.0E+00
0.E+000.04

選択率

8.0E+10

図 18：メモリ参照回数の合計と CHJ Probe Inst Cache Missおよび CHJ Probe Data Cache Access の関係
4.0E+09

0.02

CHJ Probe Data Cache Access(0)実行時間[秒]

CHJ Probe Inst Cache Miss (0)4.0E+10

CPUサイクル数 [cycle]

6.0E+10

CPUサイクル数[cycle]HJ（コスト計算式）[実線]

1.6E+118.0E+10
CPUサイクル数 [cycle]

100

100
約0.0006

5.E+05

1.E+06

選択率×外部表行数 [行]図 19：分岐予測ミスペナルティと𝑪𝑯𝑱 𝑷𝒓𝒐𝒃𝒆 𝑴𝒊𝒔𝒑𝒓𝒆𝒅𝒊𝒄𝒕の関係
以上の分析結果を踏まえると，式(23)(24)(25)が得られる．ただし，𝑆𝐻𝐽 𝑃𝑟𝑜𝑏𝑒 は計測結果から得られる定数値である．𝐶𝐻𝐽 𝑃𝑟𝑜𝑏𝑒 (0)は

98
0.009

0.01
選択率

0.011

図 21：実測結果とコスト計算値の比較（交点の拡大）

また，計測を行った customer 表と orders 表とのジョインのケー
ス以外に，supplier 表と lineitem 表のジョインのケースでコスト計算式を適用した(図 22)．ジョインのためのキーは s_suppkey とl_suppkey を用い，選択率は外部表である supplier 表の s_acctbalで調整した．その結果を図 22 に示す．HJ の再現はほぼできてい
るが，NLJ のずれがあり，グラフの交点が選択率の差で 0.02 のずれがあった．この差分を調査し HJ の見積り精度を更に向上することが必要である．
1,000

処理時間[秒]

800

NLJ（コスト計算式）[実線]

600
400

予想切替点
NLJ（実測)[点線]200

HJ（実測）[点線]
HJ（コスト計算式）[実線]

0
0

実測切替点

0.1

0.2

0.3

選択率

図 22: supplier 表と lineitem 表のジョインのケース

6. 関連研究
DBMS の挙動解析に CPU のパフォーマンスモニタを使用してプロセッサやアプリケーションの性能を評価することは古くからおこなわれてきた．特に DBMS の動作について評価したケースもあり意思決定支援システムのベンチマーク TPC-D の評価では L1
命令キャッシュミスと L2 による処理遅延が CPI の構成要素として大きく占めており，性能上重要であることが示されている．しかし，ボトルネック解析の着眼点の紹介にとどまっている[6]．
一方，インメモリデータベース向けのコスト計算に CPI の考え方，特にメモリアクセスレイテンシに着目した研究がある[7]．この研究では，データベースのデータアクセスパタンからキャッシュミス回数を予測し，メモリレイテンシとの積でコスト計算している．本研究でもアクセスパタンの部品化をして積み上げていく
アプローチをとっているが机上計算ではなく実測に基づく計算式の提案である点が本研究と異なっている．
CPU のデータアクセスについて，データベースのデータ構造から解析的にコスト計算を可能にしているが，CPU の挙動は文献[6]にあるように命令キャッシュの影響が大きいため，精度向上には
命令キャッシュミスの影響も考慮に入れる必要があると考えられる．またシミュレーションにより命令キャッシュの状態を推測する研究もなされている[12]．しかし，解析的にヒット率などの統計を計算してはいない．本研究では命令キャッシュ関連の処理にも着目した CPU コスト計算モデルを検討した．

7. 結論および今後の課題
CPU アーキテクチャを考慮した DBMS の CPU コスト計算式をデータベースのジョイン方式向けに導出方法を提案した．実測値と計算値を比較したところデータベースの選択率で約 2%実測値のずれがあり，小規模なデータベースでは問題にならない程度であるが，巨大なデータベースに関してはさらに改善の必要性がある．Hash Join は実測値に近い予測結果を得られたが，Nested Loop
Join にはまだ改善のよりがあり今後の課題としたい．また，コスト計算式のパラメータを本研究では実測値を用いたが，他の方式を含めて検討していきたい．

文
[1]

献

H. Patel, S. Shepler, SFTD015- Next Generation Storage
Architecture: Microsoft* Storage Spaces Direct and Intel® SSD
Data Center Family for NVM Express™, Intel Developer Form
(IDF15) San Francisco, Aug. 2015.
[2] P. G. Selinger, M.M. Astrahan, D.D. Chamberlin, R. A. Lorie,
and T. G. Price, “Access path selection in a relational databasemanagement system,” Proc. 1979 ACM SIGMOD international
conference on Management of data. ACM, pp. 23-34, 1979.
[3] O. Sandstå, MySQL Cost Model, Oct. 2014.
(http://www.slideshare.net/olavsa/mysql-optimizer-cost-model)[4] S. Manegold, P. A. Boncz, and M. L. Kersten, "Optimizing
database architecture for the new bottleneck: memory access."
The VLDB Journal—The International Journal on Very Large
Data Bases 9.3 (2000): 231-246.
[5] W. Wu, Y. Chi, S. Zhu, J. Tatemura, H. Hacıgumus, and J. F.
Naughton, “Predicting query execution time: Are optimizer costmodels really unusable?.” Data Engineering (ICDE), 2013 IEEE
29th International Conference on. IEEE, pp. 1081-1092, 2013.
[6] A. Ailamaki, D. J. DeWitt, M. D. Hill, and D. A. Wood, “DBMSs
on a modern processor: Where does time go?” P.ro. 25th
International Conference on Very Large Data Bases (VLDB), pp.
266-277, Edinburgh, Scotland, UK. Sept. 1999.
[7] Stefan. Manegold, P. Boncz, and M. L. Kersten, “Generic
Database Cost Models for Hierarchical Memory Systems,” Proc.
28th international conference on Very Large Data Bases (VLDB),
pp. 191-202, Endowment, 2002.
[8] 田中, 石川, CPU アーキテクチャ考慮した性能モデルの導入によ る デー タ ベー ス 高速 化の ため の コス ト 計算 精 度向 上 ,信学技法 CPSY2015-116, Jan, 2016.
[9] J. L. Lo, L. A. Barroso, S. J. Eggers, K. Gharachorloo, H. M.
Levy, and S. S. Parekh, "An analysis of database workload
performance on simultaneous multithreaded processors." ACM
SIGARCH Computer Architecture News. Vol. 26. No. 3. IEEE
Computer Society, 1998.
[10] N. Hardavellas, I. Pandis, R. Johnson, N. G. Mancheril, A.
Ailamaki, and B. Falsafi, "Database servers on chip
multiprocessors: Limitations and opportunities." Proceedings ofthe Biennial Conference on Innovative Data Systems Research.
No. DIAS-CONF-2007-008. 2007.
[11] A. Ailamaki, D. Slutz, “Processor Performance of Selection
Queries,” Technical Report MSR-TR-99-94, Microsoft Corp.,
1999.
[12] F.Muller, D. B. Whalley, and M.Harmon, “Predicting Instruction
Cache Behavior”, ACM SIGPLAN workshop on Language,
Compiler and Tool Suport for Real-Time Systems, June 1994.
[13] TPC BENCHMARK™ H (Decision Support) Standard
Specification
Revision
2.17.1,
Transaction
Processing
Performance council (TPC), Nov. 2014.
(http://www.tpc.org/tpc_documents_current_versions/pdf/tpch2.1
7.1.pdf)[14] D. Levinthal, Performance Analysis Guide for Intel® Core™ i7
Processor and Intel® Xeon™ 5500 Processors, Intel Performance
Analysis Guide, 2009.
[15] MariaDB Foundation website, https://mariadb.org/.
[16] D. Molka, D. Hackenberg, R. Schöne, and M. S. Müller,"Memory performance and cache coherency effects on an intel
nehalem multiprocessor system." Parallel Architectures andCompilation Techniques, 2009. PACT'09. 18th International
Conference on. IEEE, 2009.