DEIM Forum 2013 F3-1

アウトオブオーダ型データベースエンジン OoODE の試作とその実行挙動
合田 和生†

豊田 正史†

喜連川 優†† 東京大学 生産技術研究所 〒 153-8503 東京都目黒区駒場 4-6-1
E-mail: †{kgoda,toyoda,kitsure}@tkl.iis.u-tokyo.ac.jp
あらまし アウトオブオーダ型データベースエンジン (OoODE) と称する著者らの提案する高速データベースエンジ
ンは，問合せ処理を動的にアンフォールドし，すなわち，タスク分解して，高多重のタスク並行実行ならびに高多重の非同期入出力発行を行う．これにより，マルチコアプロセッサの演算パワーとディスクストレージの入出力帯域を高効率に活用することを可能とすることにより，中程度の選択性を有する問合せにおいて，従来型の逐次的な実行方式によるエンジンと比べて，問合せ処理の高速化が期待される．本論文では，これまで著者らがオープンソース DBMS をベースとして進めてきたアウトオブオーダ型データベースエンジンの試作機の実装を示すとともに，当該データベースエンジンの特徴である動作挙動の非決定性の検証を行い，当該データベースエンジンの有効性を明らかにする．
キーワード

OoODE，アウトオブオーダ型実行，問合せ処理，非同期入出力，データベースエンジン，非決定性

Kazuo GODA† , Masashi TOYODA† , and Masaru KITSUREGAWA†† Institute of Industrial Science, The University of Tokyo Komaba 4-6-1, Meguro-ku, Tokyo, 153-8505 Japan
E-mail: †{kgoda,toyoda,kitsure}@tkl.iis.u-tokyo.ac.jp

1. は じ め に
TPC [18] の性能ランキングリストに掲載されているハード
ウェア構成をみると，単一のシステムにおいて，64 以上のプとするアウトオブオーダ型データベースエンジンの試作機の実装を示すほか，当該データベースエンジンの特徴である動作挙動の非決定性の検証を行い，当該データベースエンジンの有効性を明らかにする．

ロセッサコアと 1,000 以上のディスクドライブが強結合されて本論文の構成は以下の通りである．第 2 章では，アウトオブいることはもはや珍しくはなく，プロセッサコアとディスクドオーダ型データベースエンジンの仕組みを紹介し，第 3 章でライブの増加傾向はハイエンド機種からミッドレンジ機種へとは，著者らが進めている試作機の実装を示す．第 4 章では，当波及している．市場においては，プロセッサコア数の増加は確

該試作機において TPC-H ベンチマークデータセットを用いて実に進展しており，また，所謂ビッグデータブームに牽引され，行った動作挙動の検証実験を報告し，第 5 章において本論文をストレージシステムの大型化・高密度化が著しいことは周知の纏める．

通りである．莫大な数のプロセッサコアとディスクドライブを有効活用することは，巨大データの管理を担うデータベース技術にとって，必須のものと言えよう．

2. アウトオブオーダ型データベースエンジン
多くのデータベースエンジンは，問合せを受け付けると，問著 者 ら は ，ア ウ ト オ ブ オ ー ダ 型 デ ー タ ベ ー ス エ ン ジ ン

合せ実行木を生成し，実行木において演算ノードを逐次的に(OoODE) と称する高速データベースエンジンの開発を進め辿って実行することにより，当該問合せを処理する．演算ノーている [22]．当該データベースエンジンは，問合せ処理を動的ドの実行においては，対象となるデータをデータベースから取にアンフォールドし，すなわち，タスク分解する機能を有して得する必要がある場合，データベースが格納されたストレージおり，高多重のタスク並行実行ならびに高多重の非同期入出力に入出力命令を発行しその完了を待って演算を実行することを，発行を行うことによって問合せを処理を行う．マルチコアプロ対象となる全てのデータを処理し終えるまで繰り返す．当該挙

セッサの演算パワーとディスクストレージの入出力帯域を高効

動を模式的に図 1(a) に示す．入出力の発行と演算の実行は事率に活用することが可能とすることにより，中程度の選択性を前にプログラムされた順序に基づき行われ，すなわち，その挙有する問合せにおいて，従来型の逐次的な実行方式によるエン動は決定的であると言え，同じデータベースに対して同じ問合ジンと比べて，問合せ処理の高速化が期待される．本論文では，せを処理する場合は，常に同じ順序で入出力と演算が実行され，これまで著者らが進めてきたオープンソース DBMS をベース

同じ結果が返される．Ingres [14] 等初期のデータベース実装以—1—

Processing(A)Processing(B)

実行時に，演算ノードにおいて入出力と演算を逐次的に繰り返

Processing(C)Processor

Time
Request(A)Request(B)し，実行時間としては，入出力にかかる応答時間が蓄積するこ

Request(C)ととなる．これに対して，著者らの考案したアウトオブオーダ型の実行方式では，問合せ処理の実行時に，演算ノードにおいCompletion(A)StorageCompletion(B)て新たな入出力を発行する必要が生じると，都度にタスク分解Completion(C)を行い，分解された並行実行可能なタスク上で入出力と関連する演算を行う．すなわち，入出力を非同期化する．ソフトウェ(a) In-order execution.

アとしての実装は多様な方式が考えられるが，問合せ処理の実

Processing(C)Processing(B)Processing(A)Processor

Time
Request(A)Request(B)Request(C)行時に，実行論理の許す限りにおいて，必要に応じてタスク分解が行われ，多数の非同期入出力がストレージに発行されることとなる．当該挙動を模式的に図 1(b) に示す．現実的には，資Completion(B)Completion(C)Completion(A)Storage

源量は有限であるため，利用可能な主記憶の容量によって並行実行するタスクの数の上限は制約され，また，ディスクドライ
ブやディスクアレイ，ホストバスアダプタや OS カーネルの処(b) Out-of-order execution.
図 1 データベースエンジンの実行方式の比較．

Fig. 1 Comparison of execution architectures in database engines.

理能力によって同時処理可能な非同期入出力の数の上限が制約されるものの，最近のサーバにおいては数百程度の主記憶容量は珍しくなく，またストレージシステムも数百のディスクドライブを搭載するに到っており [17]，従来に対してより多くのタ来，多くのデータベースエンジンがインオーダ型の実行方式を採用してきている [4, 19]．Right Deep ハッシュ結合に見られるパイプライン処理 [12] や，主記憶指向データベースエンジンに見られる SIMD 型演算実行 [2] 等，幾多の工夫が行われてきたが，基本的な実行方式そのものには変化は見られない．本論
文では，このようなソフトウェアの実行方式をインオーダ型と称することとする．
関係モデルに基づくデータベースエンジンの実装が試みられ始めた当時，プロセッサ性能と主記憶容量は今日と比べて遙かに限定的であった．ディスクドライブに代表されるストレージ（二次記憶）の性能も今日と比べて限定的ではあったものの，プロセッサと主記憶が相対的に高価であり，これらを中心としてシステムは構築された．すなわち，演算資源と入出力資源という観点では，圧倒的に演算資源が高価であり，ソフトウェア開発においても，演算にかかるコードパスとフットプリントを節約することが肝要とされ，インオーダ型の実行方式は妥当な選択肢であったと言えよう．しかしながら，今日のハードウェア環境においては，プロセッサは著しく高速化しており，大容量の主記憶が利用可能である．対して，相対的なストレージの性能は低下しており，ストレージがシステム全体の性能を律速するケースが増え，システム設計の主眼はむしろストレージに注がれるようになってきた [5, 6]．新たなハードウェアの特性バランスに基づき，従前とは異なるソフトウェアアーキテクチャを再考する段階に入ったとも言えよう [15, 16]．圧縮技法が提案され，市場で持て囃されるようになってきている [1, 10, 11]が，著者らは，より根源的なアプローチに挑戦することとし，データベースソフトウェアの実行方式そのものを変革し，即ち，ソフトウェアの非同期化によって，相対的に安価になりつつある演算資源を活用し，入出力資源を高効率に利用するアウトオ

スクと入出力の同時処理が可能となってきている．また，ディスクドライブ内，ディスクアレイコントローラ内さらには OS内の高度なスケジューリング機構 [13, 20] により，論理的な入出力発行順序とは異なる順序で入出力の処理がなされるのが通例である．即ち，アウトオブオーダ型の実行方式では，入出力完了によって手続きが駆動されるべく制御がなされることとなる．従来のインオーダ型の実行方式の下では，プロセッサ性能と主記憶容量を節約するべく，極めて少量の入出力のみが発行されていたのに対し，アウトオブオーダ型の実行方式においては，ソフトウェアの非同期化によって，実行論理が許す限り大量の入出力を発行することを可能とし，これにより，極めて高速化の進んでいるプロセッサ資源の活用と，膨大な数のディスクドライブの並列アクセスによって，効果的な性能バランスの達成を狙う．リレーションを複数のパーティションに分割し，パーティション毎に事前に問合せ処理をタスク分割する技法も提案されたが，これはパーティション毎にインオーダ型の実行方式で問合せを処理しているに過ぎず，アウトオブオーダ型の実行方式とは根源的に異なる．
問合せ処理におけるデータベースのアクセスパスという観点
では，大きく分けて，リレーション全体の走査か，索引経由のアクセスかの選択が鍵となる．リレーション間の結合は，問合せ実行時間の多くを占める場合が多い演算であるが，基底となるリレーションに対する選択性に基づき，問合せ最適化器によって，ハッシュ結合 [3, 7] とネステッドループ（索引）結合のうちいずれかが選択され，用いられてきた．前者は，リレーション全体の走査を基本とし（注 1），選択性が低い（選択率の高い）場合に有効とされるが，リレーション規模がテラバイトからペタバイトと巨大化するにつれ [8]，単純な走査が可能な機会はより限られてくるはずであり，より選択性の高い（選択率のブオーダ型と称するデータベースエンジンの実行方式を考案した [22]．
上述する従前のインオーダ型の実行方式では，問合せ処理の（注 1）：索引を用いたハッシュ結合の可能性もあり，当該手段を含めたより広範な有効性の検証は別稿で議論したい．

—2—低い）問合せの重要性が高まる可能性が高く，即ち，ネステッ

表 1 実験システムの諸元．

ドループ結合に頼る比重が増えるものと推察される．アウトオ

Table 1 Experimental setup.
Hardware (Dell PowerEdge 720xd)

ブオーダ型の実行方式は，当該結合方式に対して，圧倒的な高速化ポテンシャルを有している．
アウトオブオーダ型の実行方式では，入出力の発行と演算の実行は事前にプログラムされた順序で行われるのではない．同
じデータベースに対して同じ問合せを処理する場合において，Processors

2x Intel Xeon E5-2680 2.70GHz (2p/16c)

Memory1,600MHz 64GB

RAID controller

Dell perc H710p

Disk drives

2x 15,000rpm 300GB SAS HDDs (OS)(2.5in)24x 10,000rpm 900GB SAS HDDs (database)

同じ結果が返されることは無論のことであるが，入出力と演算が実行される順序は，その試行毎に異なる可能性が高い．非決

SoftwareOS

CentOS 5.8 x86 64

定的な動作挙動は，他のシステムソフトウェアには見られない特徴であり，動作正当性の検証方法などを含めて，詳細な検討(customized kernel)
DBMS

OoODE (prototype, MySQL based)
MySQL 5.5.24

を今後深めていきたいと考えているが，本稿では，アウトオブオーダ型のデータベースエンジンの試作実装を用いて，実験的SUMにその動作挙動の確認を行う．

3. アウトオブオーダ型データベースエンジンの試作実装
customer

著者らは，これまで，オープンソースのデータベースソフト

PkCustomer(primary key index)

ウェアをベースとしたアウトオブオーダ型データベースエン

Ordersジンの試作実装を行ってきた．本論文では，その一実装である

MySQL [9] をベースとする試作実装を紹介する（注 2）．
開発を行っているアウトオブオーダ型データベースエンジン

PkOrders(primary key index)
PartLineitem

IdxPart(secondary index)

IdxLineitem(secondary index)

は，主に問合せ処理器，ストレージエンジンならびに挙動モニタから構成される（注 3）．問合せ処理器は，問合せ実行木に基づき問合せ処理を実行する．演算ノードにおいて新たな入出力を

図 2 実験に用いた問合せの実行木．

Fig. 2 Execution plan tree of a query used in the experiment.

発行する必要が生じると，都度にタスク分解を行い，非同期入出力をストレージエンジンに要求する．ストレージエンジンは，内部にデータベースバッファを備えており，当該バッファを経由して，問合せ処理器から要求された非同期入出力を OS を介してストレージに発行し，その応答を受け付ける．ストレージ
エンジンが非同期入出力の完了を通知すると，問合せ処理器は当該非同期入出力に関連する演算を実行する．挙動モニタは，データベースエンジンの問合せ処理には必ずしも不可欠のもの
ではないが，実験的な実装であることから，問合せ処理器ならびにストレージエンジンの動作挙動を精緻に捕捉するためのものであり，内部バッファを用いて問合せ処理器ならびにストレージエンジンのイベントを取得し，微視的な挙動把握によって動作デバッグ等に資するためのものである．

4. 小規模マシンを用いた実験

グ（RAID-6，セグメントサイズ 64KB）編成のボリュームを構成し，当該ボリュームからページ長 16KB，空間長 2,560GBの InnoDB 表空間を構築した．当該表空間には 1GB のデータベースバッファを割り当てた．
データベースエンジンの性能試験には，TPC-H ベンチマー
ク [18] を用いた．TPC-H の仕様に従いスキーマを作成し，この際，主鍵に対して一次索引（MySQL においては所謂索引構成表として編成される）を，外部鍵に対して二次索引を構成し，スケールファクタとして 1,000 のデータセット（ローフォーマッ
トで 1,000GB 程度）を生成して，これを表空間にインポートした．また，TPC-H 既定の問合せを簡略化した図 2 に示す問合せを作成した．この際，最外表である Part リレーションの選択率は 0.0015%程度になるように調整してある．実験においては，アウトオブオーダ型データベースエンジンの試作実装を小規模マシン環境において前節で紹介した試作実装を用いた実験を行い，その動作挙動の確認を行った．中規模環境における性能試験に関しては，[21] を参照されたい．
表 1 に著者らが構築した実験システムの諸元を示す．24 台の SAS ディスクドライブを用いて二重パリティストライピン用いて当該問合せ処理を実行した際の性能を計測するとともに，挙動モニタを用いて動作を検証した．また，比較として，MySQL における同一の問合せ処理の実行性能を計測した．
図 3(a) に問合せ処理にかかった実行時間を示す．MySQL では，問合せ処理に 1,650 秒程度を要していたが，これに対してアウトオブオーダ型データベースエンジンの試作実装において（注 2）：試作実装は InnoDB ストレージエンジンのデータフォーマットに対応している．

は，これを 32 秒程度に短縮し，すなわち，約 52 倍の高速化を（注 3）：本論文ではエンジンのカーネル部分に焦点を当て，他のコンポーネント達成している．図 3(b),(c) には，問合せ処理におけるサーバのである問合せ最適化器，更新・リカバリ機構，レプリケーション機構等に関してプロセッサ利用率ならびにディスクアクセススループットを示は，別稿に譲りたい．

—3—

す．MySQL においては，インオーダ型の実行方式によって問4.5e+09

合せが処理され，原則，1 コアのみが利用される．問合せ処理

4e+09が同期入出力によって都度ブロックされ，当該コアのプロセッ

3.5e+09サ時間のほとんどは入出力完了の割り込み待ちに利用されておドライブ分の帯域を有効利用できていないことが見て取れる．
これに対して，アウトオブオーダ型の実行方式においては，動3e+09
Address [sectors]

り，また，入出力スループットは高々160 IO/S であって，24

2.5e+09
2e+09
1.5e+09

的なタスク分解によって多数のタスクが並行実行され，また，1e+09

多数の非同期入出力が発行され，これによって，プロセッサ利

5e+08

用率は大幅に増加し，また，入出力スループットは格段に向上0している．

0200

400

600

次に，データベースエンジンのソフトウェア挙動を，より微

800
1000
Elapsed time [us]

1200

1400

1600

1800

1200

1400

1600

1800

(a) MySQL.

視的に確認したい．図 4(a),(b),(c) には，MySQL における問
4.5e+09

合せ処理において発行される当初 200 個の入出力を，縦軸とし4e+09て発行順，横軸として発行先アドレスの空間にプロットしたも3.5e+09のを示す．ここでは，同じ問合せを 3 回試行したものを示すが，違はない．これに対して，図 4(d),(e),(f) には，アウトオブオー
ダ型データベースエンジンの試作実装における入出力発行挙動

3e+09
Address [sectors]

MySQL においては試行によって入出力が発行される順序に相2.5e+09
2e+09を示す．同様に 3 回試行したそれぞれの実行を示すが，明らか

1.5e+09に試行毎に入出力の発行順序が異なっている．データベースエ

1e+09

ンジンが結果的に返す問合せの回答は同じであるものの，その5e+08実行過程が非決定的であるという特性が見て取れる．

00

図 5 には，問合せ処理全体の入出力トレースの結果を示す．

200

400

600

800
1000
Elapsed time [us]ここでは横軸は発行順序ではなく，経過時間とした．視覚的に，(b) OoODE prototype.

インオーダ型の実行方式である MySQL と比べて，アウトオブ

図 5 入出力トレースによる MySQL とアウトオブオーダ型データオーダ型データベースエンジンの試作実装は，格段に稠密に入ベースエンジン試作実装の全体挙動．
Fig. 5 Overall IO behavior of MySQL and out-of-order database

出力を発行しており，当該特性が問合せ処理の高速性の源泉とengine prototyep.

なっていることが判る．

5. お わ り に
本論文では，著者らが開発を進めているアウトオブオーダ型データベースエンジン (OoODE) と称する高速データベースエ

せ最適化器，更新・リカバリ機構，レプリケーション機構等に関しても，順次報告してゆきたい．

謝

辞ンジンを紹介した．当該データベースエンジンは，問合せ処理を動的にアンフォールドし，すなわち，タスク分解する機能を有しており，高多重のタスク並行実行ならびに高多重の非同期入出力発行を行うことによって問合せを処理を行う点に特徴があり，マルチコアプロセッサの演算パワーとディスクストレージの入出力帯域を高効率に活用することが可能となる利点を備えている．中程度の選択性を有する問合せにおいて，従来型の逐次的な実行方式によるエンジンと比べて，問合せ処理の高速化が期待されている．本論文では，これまで著者らが進めてきたオープンソース DBMS である MySQL をベースとするアウトオブオーダ型データベースエンジンの試作機の実装を示し，小規模環境において TPC-H ベンチマークを用いた性能比較を行い，MySQL と比較して 52 倍程度の高速性を確認したほか，実行挙動トレースを用いてその動作挙動の非決定性の検証を行った．今後，多様な問合せに対して大規模な環境を用いた検証を進めていきたい．また，本論文ではエンジンのカーネル部分に焦点を当て論じて来たが，他のコンポーネントである問合本研究の一部は，内閣府最先端研究開発支援プログラム「超巨大データベース時代に向けた最高速データベースエンジンの開発と当該エンジンを核とする戦略的社会サービスの実証・評価」の助成により行われた．
文

献[1] Daniel J. Abadi, Samuel Madden, and Miguel Ferreira.
Integrating compression and execution in column-oriented
database systems. In Proc. ACM SIGMOD Conf., pp. 671–682, 2006.
[2] Peter A. Boncz, Martin L. Kersten, and Stefan Manegold.
Breaking the memory wall in MonetDB. Comm. ACM,Vol. 51, No. 12, pp. 77–85, 2008.
[3] David J. DeWitt, Robert H. Gerber, Goetz Graefe,
Michael L. Heytens, Krishna B. Kumar, and M. Muralikrishna. GAMMA - A High Performance Dataflow Database
Machine. In Proc. Int’l. Conf. on Very Large Data Base,pp. 228–237, 1986.
[4] R. Elmasri and S. Navathe. Fundamentals of Database Systems. Addison Wesley, 1994.
[5] Kazuo Goda and Masaru Kitsuregawa. The History of Stor-—4—1800

20Wait IO

System

6000

User

1600
5000

1200
1000
800
600

Disk transfer rate [MB/s]

15CPU utilization [%]Execution time [sec.]

1400

105

400

4000

3000

2000

1000
200
00
MySQL

0

OoODE prototype

MySQL(a) Execution time.

OoODE prototype

MySQL(b) Processor utilization.

OoODE prototype(c) Disk transfer rate.

図 3 MySQL とアウトオブオーダ型データベースエンジン試作実装の性能比較．

4.5e+09

4e+09

4e+09

4e+09

3.5e+09

3.5e+09

3.5e+09

3e+09
2.5e+092e+09
1.5e+09

4.5e+09

Address [sectors]

4.5e+09

Address [sectors]

Address [sectors]

Fig. 3 Performance comparison of MySQL and out-of-order database engine prototype.

3e+09
2.5e+09
2e+09
1.5e+09

2e+09
1.5e+09

1e+09

1e+09

1e+09

5e+08

5e+08

5e+08

00050

100
IO issuing order

150

200

00(a) Trial 1 (MySQL).

50

100
IO issuing order150

2000(b) Trial 2 (MySQL).

4.5e+09

4e+09

4e+09

3.5e+09

3.5e+09

2e+09
1.5e+09

3e+09
2.5e+09
2e+09
1.5e+09

1e+091e+095e+08

5e+08

0

Address [sectors]

4e+09

3e+0950

100
IO issuing order150(d) Trial 1 (OoODE prototype).

200150200150

200

3e+09
2.5e+09
2e+09
1.5e+09
1e+09
5e+08

00100
IO issuing order

4.5e+09

3.5e+09

2.5e+0950(c) Trial 3 (MySQL).

4.5e+09

Address [sectors]

Address [sectors]

3e+09
2.5e+090050

100
IO issuing order150(e) Trial 2 (OoODE prototype).

200050100
IO issuing order(f) Trial 3 (OoODE prototype).

図 4 入出力トレースによる MySQL とアウトオブオーダ型データベースエンジン試作実装の微視的挙動．
Fig. 4 Microscopic IO behavior of MySQL and out-of-order database engine prototyep.

[6]

[7]

[8]
[9]
[10]
[11]

[12]

[13]

age Systems. Proc. of IEEE, Vol. 100, No. Special Centennial Issue, pp. 1433–1440, 2012.
Masaru Kitsuregawa, Kazuo Goda, and Takashi Hoshino.
Storage Fusion. In Proc. of 2nd Int’l Conf. on UbiquitousInformation Mgmt. and Comm., pp. 287–294, 2008.
Masaru Kitsuregawa, Hidehiko Tanaka, and Tohru MotoOka. Application of Hash to Data Base Machine and ItsArchitecture. New Generation Comput., Vol. 1, No. 1, pp.
63–74, 1983.
McKinsey Global Institute. Big data: The next frontier for
innovation, competition, and productivity, 2011.
Oracle Corp. MySQL: The World’s Most Popular Open
Source Database. http://www.mysql.com/.
Oracle Corp. Hybrid Columnar Compression (HCC) on Exadata. An Oracle White Paper, 2012.
PostgreSQL Global Development Group. The Netezza Data
Appliance Architecture: A Platform for High Performance
Data Warehousing and Analytics. IBM Redbooks, 2011.
Donovan A. Schneider and David J. DeWitt. Tradeoffs inprocessing complex join queries via hashing in multiprocessor database machines. In Proc. Int’l. Conf. on Very Large
Data Base, pp. 469–480, 1990.
Margo I. Seltzer, Peter M. Chen, and John K. Ousterout.

[14]

[15]

[16]
[17]

[18]

[19]

[20]

Disk Scheduling Revisited. In Proc. USENIX Tech. Conf.,
pp. 313–323, 1990.
M. Stonebraker, Eugene Wong, Peter Kreps, and Gerald
Held. The Design and Implementation of INGRES. ACM
Trans. Database Syst., Vol. 1, No. 3, pp. 189–222, 1976.
Michael Stonebraker, Daniel J. Abadi, Adam Batkin, Xuedong Chen, Mitch Cherniack, Miguel Ferreira, EdmondLau, Amerson Lin, Samuel Madden, Elizabeth J. O’Neil,Patrick E. O’Neil, Alex Rasin, Nga Tran, and Stanley B.
Zdonik. C-Store: A Column-oriented DBMS. In Proc. Int’l.
Conf. on Very Large Data Base, pp. 553–564, 2005.
Ivan Sutherland. The tyranny of the clock. Comm. ACM,Vol. 55, No. 10, pp. 35–36, 2012.
N. Takahashi and H. Yoshida. Hitachi TagmaStore Universal Storage Platform: Virtualization without Limits. WhitePaper, Hitachi Ltd., 2004.
Transaction Processing Performance Council. TPC-H, anad-doc, decision support benchmark. http://www.tpc.org/tpch/.
Eugene Wong and Karel Youssefi. Decomposition ― a strategy for query processing. ACM Trans. Database Syst.,
Vol. 1, No. 3, pp. 223–241, 1976.
Bruce L. Worthington, Gregory R. Ganger, and Yale N.

—5—Patt. Scheduling Algorithms for Modern Disk Drives. In
Proc. ACM SIGMETRICS Conf., pp. 241–251, 1994.
[21] 早水悠登, 合田和生, 喜連川優. アウトオブオーダ型データベー
スエンジン OoODE によるクエリ処理性能の実験的評価. 電子
情報通信学会／日本データベース学会データ工学と情報マネジ
メントに関するフォーラム, 2013 (to appear).
[22] 合田和生, 喜連川優. アウトオブオーダ型データベースエンジ
ン OoODE の構想と初期実験. 日本データベース学会論文誌,
Vol. 8, No. 1, pp. 131–136, 2009.

—6—