基礎から理解するデータベースのしくみ

bgx5810

基礎から理解するデータベースのしくみ（1）

基礎から理解するデータベースのしくみ（2）

基礎から理解するデータベースのしくみ（3）

基礎から理解するデータベースのしくみ（4）

基礎から理解するデータベースのしくみ（5）

基礎から理解するデータベースのしくみ（6）

基礎から理解するデータベースのしくみ（7）

基礎から理解するデータベースのしくみ（8）

基礎から理解するデータベースのしくみ（9）

基礎から理解するデータベースのしくみ（10）

基礎から理解するデータベースのしくみ（11）

基礎から理解するデータベースのしくみ（12）

[ 本帖最后由 bgx5810 于 2007-5-28 13:35 编辑 ]

bgx5810

基礎から理解するデータベースのしくみ（1）

ブラックボックスのままでいいの？
      

図1●クライアント/サーバー型システムの構成例 [画像のクリックで拡大表示]

    　「データベースはブラックボックス。どんなSQL文を投げたらどんな結果が返ってくるかさえ知っていればよい」---そう思っている人も多いかもしれません。確かに，最近の市販のリレーショナル・データベース管理システム（RDBMS）にはGUIベースの管理ツールなどが付属し，データベースそのものについての深い知識が求められることは昔に比べれば少なくなりました。メモリーやディスクなどのハードウエア・リソースが増えて，開発者のスキル不足が表面化しにくくなったこともあるでしょう。
　しかし，本物のソフトウエア・エンジニアを目指すのであれば，データベースが動く仕組みを学ぶことは避けて通れません。「SQL文を受け取ってから結果を返すまでにRDBMSがどんな処理をしているのか」「データ・ファイルの物理構造はどうなっているのか」「インデックスはどのように格納されているのか」——。こうした知識がないと，パフォーマンスなどに問題が生じたときどこから手を付けていいのか皆目見当がつかない，といった事態に陥りかねません。知らず知らずに効率の悪いデータベース設計やパラメータ設定をしたり，SQL文を記述してしまうことも多くなるでしょう。
　市販のRDBMSの内部はかなり複雑ですが，基本的な部分を理解するのはそれほど難しくありません。この特集でデータベースの動く仕組みを理解してください。
　データベースは，多くの業務アプリケーションで不可欠なソフトウエアです。商品受発注システム，在庫管理システム，顧客管理システムといった企業の基幹系システムの中核には，必ずと言っていいほどデータベースが据えられています。データベースに関するスキルが無くては，企業システムの構築・運用には携われない，と言っても良いでしょう。
　一方で，企業システムでトラブルの原因になることが多いのもまた，データベースです。例えば，入力してから応答が返ってくるまでに時間がかかりすぎて使いものにならない，というのは，業務アプリケーションのトラブルでもっともよく見られる事例の一つです。こうしたトラブルは，検索に使っているSQL文で，「データベース側でどんなことを実行しているかをよくわかっていなくて効率が悪い処理を書いてしまった」ことが原因である場合も多いようです。
　（図1[拡大表示]）を見てください。これは，クライアント/サーバー型システム全体を模式的に表したものです。真ん中にある黄色の四角の部分がデータベースを管理する，いわば頭脳となるソフトウエア「リレーショナル・データベース管理システム（RDBMS）」です。RDBMSを表す四角の中に，最適化とか，トランザクションとかいくつかの言葉が並んでいます。それぞれがどんな仕組みで，どんなことをしているかを言うことができますか？　「簡単だよ」という人も，ちょっと詰まってしまったという人も，もう少しお付き合いください。
適切な指示を出すにはまず相手を知ることが大事　RDBMSは大きく分けて，(1)SQL文の解釈などを実行する部分と，(2)ディスク・アクセスなどを管理する部分の二つで構成します。ここではそれぞれ，リレーショナル・エンジン，ストレージ・エンジンと呼ぶことにしましょう。
　リレーショナル・エンジンは，アプリケーションから受け取ったSQL文を解析し，文法チェックなどをしてから最終的にRDBMS内部で行う処理単位に分割します。この過程で，SQLを高速に実行できるように最適化も行います。例えば，推論によってSQL文を書き換えたり，統計的な情報を基にテーブルをアクセスする際にインデックスを使うべきかどうかを検討するなど，実際にディスクにアクセスをする前の準備としてさまざまな処理を行います。そして最も効率がよいと思われる内部処理命令の組を自動生成してくれます。
　「そんなにいろいろなことをしてくれるんだったら，全部リレーショナル・エンジンに任せてしまえばいいんじゃないの」という声も聞こえそうですね。でも，そうはいきません。例えばリレーショナル・エンジンは，人間が考えれば明らかに効率が悪いと思われる処理方法を，推論の結果わざわざ選んでしまうこともあります。検索を高速化するために定義しておいたインデックスを使ってくれない，ということも起こります。そうしたことがないようにするには，一体どうすればよいのでしょうか。
　それには，リレーショナル・エンジンが効率の良い処理をするように，ユーザーやアプリケーション側から出す命令を修正してみたり，指示を与えてやれば良いのです。ただし，やみくもに命令を修正したり，指示を与えても効果はありません。リレーショナル・エンジンがどのような仕組みで動いているかを知っていないと，適切な指示はできません。これは，スポーツのコーチが選手を適切に指導して実力を発揮させるには，相手の特性や性格を知っていなければいけないのと同じです。本特集のPart1をお読みいただければ，リレーショナル・エンジンのこうした点を理解できるはずです。
データがどう格納されているかを把握しておくことも重要だ　RDBMSのもう一つの構成要素であるストレージ・エンジンは，リレーショナル・エンジンから受け取った処理命令を基に，ディスクにアクセスしてデータを読み込んだり書き込んだりするのが主な仕事です。RDBMSはデータベースを作成する際に，一つの大きなデータ・ファイルとしてディスク領域を確保したうえで，その中の領域を必要に応じてテーブルやレコードに割り当てていくのです。
　テーブルやレコードがディスク上にどのように格納されているのか，ということは重要なポイントです。ディスク上にデータがどのように格納されていて，それに対してストレージ・エンジンがどうアクセスするのかを把握していれば，効率のよい処理命令とはどのようなものなのかが，おのずとわかるからです。レコードが主キーの順に並んでいるとか，追加した順に格納されているとか思っている人は，ぜひ本特集のPart2を読んで，レコードの格納方法を理解してください。
　パフォーマンス・チューニングをするなら，インデックスの構造についての知識も不可欠でしょう。インデックスは元々，検索を高速にするために設定するものですが，効果を上げるためにはそれなりの知識が必要です。Part2では，インデックスをディスクに格納する方法として最もよく使われている「Bツリー」と呼ばれるデータ構造についても説明します。Bツリーは一般に，目的とするレコードにたどり着くまでに，ディスクに3～4回アクセスする必要があります。ある程度以下の大きさのテーブルであれば，インデックスを使うよりも全体を走査したほうが高速であることは何となくわかるんだけど…という人はここを読んでいただけば，その理由を知ることができるでしょう。
　RDBMSには，このほかにもいくつかの重要な機能があります。中でも実用システムにおいて重要なのは，複数のユーザーから同時にアクセスされたときの処理です。Part3では，トランザクション処理と，その基本となるロック機構について取り上げ，マルチユーザー環境におけるにデータの一貫性や整合性を実現する仕組みを説明します。
☆　　　　　　　　　　　　☆　　　　　　　　　　　　☆
　これまでRDBMSを「SQL文を投げてしばらく待つと答えが返ってくるブラックボックス」と見てきた人はもちろん，そうでない人も，「なぜそうなるのか」をきちんと理解して，ワンランク上の技術者を目指してみませんか。

bgx5810

基礎から理解するデータベースのしくみ（2）

SQL文はどのように実行されるのか(1)
      

図1●リレーショナル・データベース管理システム（RDBMS）が，受け取ったSQL文を実行するまでの処理の流れ [画像のクリックで拡大表示]

    　SQL文を記述してデータベースを操作することはそれほど難しいことではありません。しかし，リレーショナル・データベース管理システム（RDBMS）が問い合わせを実行する速度は，SQL文の書き方によって大きく異なります。ちょっとした記述の違いによって，応答時間が何倍も違うことはめずらしくありません。
　では，速いSQL文を書けるようになるためには，どうすればいいのでしょうか。その答えは，「RDBMSがSQL文を内部でどのように処理しているのか」を理解することです。RDBMSは，プログラマが記述したSQL文を基にさまざまな処理を行ってから実際にデータベースにアクセスします。その過程を知ることで，アクセスのしかたをコントロールできるようになるのです。
　例えば，CUSTOMERS（顧客）テーブルからNAME（名前）を抽出する「SELECT NAME FROMCUSTOMERS」という簡単なSQL文であっても，RDBMS内部ではさまざまな処理を経て結果を返します。こうした仕組みを理解することで，ただ結果を求めるだけのSQL文を書くのではなく，「目的に応じて適切なSQL文を書く」という発想が生まれてくるのではないかと思います。
　Part1では，RDBMSがSQL文を内部でどのように処理しているのかを，最適化の話を中心に解説します。あわせて，速いSQL文を書くためのポイントも紹介しましょう。アプリケーション開発やデータベース設計など，さまざまな場面で活用していただけたら幸いです。
SQL文は実行までに三つの過程を経る　最初に，RDBMSがSQL文をアプリケーションから受け取ってから実行するまでの流れを眺めてみましょう。大きく，(1)SQL文の解析，(2)SQL文の書き換え，(3)実行計画の作成，の三つの処理過程があります（図1[拡大表示]）。順に説明していきましょう。
(1)SQL文の解析　RDBMSは，SQL文を受け取るとまず，そのSQL文を解析します。具体的には，そのSQL文が文法的に正しいかどうかをチェックしたり，選択，射影，結合＊1といった処理がそれぞれどのように実施されるかという文の構造を把握します。データベースの管理情報を基に，SQL文に指定したテーブルやフィールドが実際に存在するかどうかや，ユーザーがそれらに対するアクセス権限を持っているかどうかをチェックする処理もここで行います。
(2)SQL文の書き換え　解析が終わると，次にRDBMSはSQL文をより高速に実行できるように書き換えます。同じ結果を返すSQL文であっても，具体的な処理内容の違いによって，実行速度は大きく異なります。そこで，処理の手順を工夫したり，演算の種類を変更するといった書き換えをします。書き換えられたSQL文は，最終的にRDBMS内部の処理命令の集まりに変換されます。
(3)実行計画の作成　こうして作られたRDBMS内部の処理命令の集まりを実行する方法は，一つとは限りません。例えば，一つのテーブルからデータを取り出す方法（「アクセス・パス」と呼びます）には，テーブル全体を先頭から順に検索していく方法（「全表走査」と呼びます）もあれば，インデックス＊2を利用する方法もあります。テーブルを結合する場合など，複数のテーブルを扱う際には，それらを結合するアルゴリズムや結合の順序などにもさまざまな方法が考えられます。検索条件が複雑で，かつテーブルに複数のインデックスが定義されているなら，それらのどれを使うのかも問題になるでしょう。
　RDBMSは，処理命令を実行する手続きを何通りか作成したうえで，その中から最も効率の良いものを選択します。こうして出来上がった，RDBMS内部の形式で表された一連の手続きのことを「実行計画」と呼びます。
　ただ，複雑なSQL文の場合には，個々のテーブルのアクセス・パスなどの組み合わせは何千通りにもなることがあります。これらをすべて調べていたのではそのために時間がかかってしまい，本末転倒になってしまいます。そこで通常は，最速になりそうな実行計画の候補をある程度絞り込んだうえで比較検討します。
　実行計画の作成は比較的時間がかかる処理ですから，SQL文が発行されるたびに行うのでは効率がよくありません。そこで，OracleやMicrosoft SQL Server（以下，SQLServer）などのRDBMSでは，作成した実行計画をキャッシュに保存しておき，同じSQL文が発行されたときにはそのキャッシュ上の実行計画を利用するようになっています。
　ここまで来てようやく，SQL文を実行する用意ができたわけです。いかがですか。処理の多さに驚かれている人もいるかもしれませんね。
　こうして作成された実行計画は，内部処理命令ごとに実行され，ハードディスクからテーブルのデータなどがキャッシュ・バッファに読み込まれて操作されることになります。実際にハードディスクから読み込む処理の手順などについては，Part2で解説します。
　(1)～(3)の，SQL文を解析して内部形式で表した実行計画を作成するまでの処理を，SQL文の「コンパイル」と呼ぶことがあります＊3。VisualBasicやC言語で作成したテキスト形式のソース・ファイルをコンパイルして，CPUが直接解釈できる機械語を生成するのと同じイメージですね。(2)と(3)のSQL文を高速に実行するための処理のことを，「最適化（optimization）」と呼びます。(1)のSQL文の解析は，RDBMSの「パーサー」と呼ばれる機能が，(2)(3)の最適化の処理は「オプティマイザ」という機能が担当します。
推論を行ってSQL文を書き換える　では，最適化の部分で具体的にどんな処理がなされているのかをもう少し詳しく見ていきましょう。まずはSQL文の書き換えからです。
　例えば，table1とtable2という二つのテーブルから，table1のidフィールドの値が10であり，かつtable1とtable2のidフィールドの値が一致するレコードを検索する
SELECT * FROM table1, table2
  WHERE table1.id = 10
  AND table2.id = table1.idというSQL文があったとしましょう。ここではWHERE句の「table1.id = 10」と「table2.id =table1.id」という二つの条件から，「table2.id =10」という条件が導き出せますね。このような場合，オプティマイザは上記のSQL文を
SELECT * FROM table1, table2
  WHERE table1.id = 10
  AND table2.id = table1.id
  AND table2.id = 10のように書き換えることがあります。単に無意味な条件を追加しただけのように見えるかもしれませんが，この「table2.id =10」のおかげで，それまで使えなかったインデックスが検索に利用できるようになる可能性が生じます。結果として，アクセス・パスを検討して実行計画を作成する際に，より高速なパスを選択できる可能性がでてくるというわけです。Oracleのオプティマイザは，等号「＝」以外に比較演算子などを使った「table1.id ＜ 10」のような式の場合にも上のような推論を行います。
　WHERE句にNOTが現れているような場合にも，書き換えを行ってできるだけ簡単になるようにします。例えば，
SELECT * FROM table
  WHERE NOT (id ＞= 100 OR
  aux IS NULL)のようなSQL文の場合，オプティマイザは「NOT」を除去して
SELECT * FROM table
  WHERE id ＜ 100 AND aux IS NOT NULLのように書き換えます＊4。NOTが付けられた条件にはインデックスによる検索が利用できないため，無条件に全表走査が実行されてしまうからです。上のように書き換えれば，フィールドidにインデックスが定義されている場合，それを利用できるようになります。
　ただし，人間が式を変形するのと違い，変形できる対象範囲はそれほど広くありません。例えば，左辺に複数のフィールドが現れていたり，
table1.id ＜ table3.idのように左辺と右辺の両方にフィールドが現れているような式を受け取った場合，オプティマイザがそれ以上変形することはありません。オプティマイザが推論をしてSQL文を書き換えるといっても限度があるわけです。

bgx5810

基礎から理解するデータベースのしくみ（3）

SQL文はどのように実行されるのか(2)
      

図2●オプティマイザが作成する実行計画の例。一つひとつの四角が内部処理単位を表します [画像のクリックで拡大表示]

図3●Oracle付属のSQL＊Plusで実行計画を表示したところ。画面下部のインデントは図2のツリーの親子関係を表します [画像のクリックで拡大表示]

表1●Oracleのルール・ベース・アプローチにおけるアクセス・パスのランク [画像のクリックで拡大表示]

    効率の良い実行計画を作成する　次は，実行計画の作成です。こちらも例を挙げて説明したほうがわかりやすいでしょう。Oracleに付属するサンプルの従業員テーブル（emp）と部署テーブル（dept）から，従業員の一覧を取り出す以下のようなSQL文を実行するとします。
SELECT ename, job, sal, dname
  FROM emp, dept
  WHERE emp.deptno = dept.deptnoテーブルdeptでは部署番号deptnoが主キーで，インデックスpk_deptnoが定義されています。一方テーブルempでは，deptnoが外部キー＊5になりますが，これに対してインデックスは定義されていません。
　オプティマイザは，このSQL文に対して（図2[拡大表示]）のような実行計画を作成します。図のそれぞれの四角は，RDBMS内部での処理単位を表し，四角同士をつなぐ線がデータの流れを示しています。処理の流れは，次のようになります。
(1)テーブルempからレコードを一つ取り出す
(2)そのレコードのdeptnoをキーとしてインデックスpk_deptを検索する
(3)検索して得られたROWID＊6を使ってテーブルdeptから対応するレコードを取り出す
(4)以上(1)～(3)をテーブルempの各レコードについて繰り返し実行して従業員名enameや部署名dnameなどのフィールドを取り出して出力する
　上記のSQL文を実行する方法には，ほかにもいろいろ考えられます。テーブルempとテーブルdeptの各行を総当たり的に組み合わせて一時的なテーブルを作成してから，その中で「emp.deptno =dept.deptno」という条件を満たすレコードを取り出す，という方法もあるでしょう。しかし，総当たり的に組み合わせたテーブルのレコード数は，empのレコード数×deptのレコード数になりますから，かなりの数になります。このテーブルのすべてのレコードに対して条件を満たすかどうかを一つひとつ調べていくより，先の方法のほうが高速に実行できるのは明らかでしょう。
　テーブルempとテーブルdeptの役割を逆にして，deptの各レコードについてempから「emp.deptno =dept.deptno」の条件を満たすレコードを取り出す，というのも一つの方法です。しかし，empにはdeptnoについてのインデックスが定義されていないため，条件を満たすレコードを取り出すためにはempのすべてのレコードを一つひとつ見ていかなくてはなりません。しかも，その処理をdeptのレコードの数だけ繰り返す必要があります。これも，やはり先ほどの方法よりも遅くなってしまいます。
　オプティマイザは，こうしたさまざまな実行計画の候補の中から最も効率の良い方法を選び出して，実行計画を作成するのです。
ツールを使って実際の実行計画を見てみよう　OracleやSQLServerは，SQL文を実行する際の実行計画を表示することができます。例えばOracleでは，付属ツールの「SQL＊Plus」上でPL/SQLのEXPLAIN PLANステートメントを利用して，実行計画をテキストとして見ることができます。SQLServerの場合は，付属ツールの「クエリ・アナライザ」でグラフィカルに表示することも可能です。ここでは，SQL＊Plusを使って，Oracleが作成した実行計画を見ることにしましょう。
　実行計画を表示するには，EXPLAIN PLAN FORの後ろに計画を表示するSQL文を記述します。ただ，毎回記述するのは面倒です。開発環境で実行する場合はSQL＊Plusのプロンプトで
set autotrace traceonly exlpain;と入力して，SQL文を実行するたびにトレース結果として実行計画を表示するようにしたほうが簡単でしょう。作業が終わったら，
set autotrace off;としてトレースをオフにします＊7。
　SQL＊PlusでSQL文の実行計画を表示してみたのが（図3[拡大表示]）です。「実行計画」とある部分の下のインデントされた文字列が，実行計画です。図2と同じ内容が表示されていることを確認できるでしょう。インデントは，それぞれの処理がその一つ上のレベルの下位に位置する（図2だと四角がすぐ下にあること）ことを表しています。先頭の「Optimizer =CHOOSE」は，オプティマイザとしてデフォルトの機能を使ったことを意味します。
実行計画の選択基準は大きく2通りある　オプティマイザはさまざまな実行計画の候補の中からもっとも効率の良いものを選ぶと先に書きました。ではオプティマイザは，どのような基準で最適な実行計画を選ぶのでしょうか。これには，大きく分けて二つのやり方があります。一つは，ルール・ベース・アプローチ，もう一つはコスト・ベース・アプローチです。
　ルール・ベース・アプローチは，アクセス・パスの「ランク」に基づいて実行計画を選択します。ランクは，インデックスを使用してアクセスするかどうかなど，操作の種類によって決まる効率の度合いを表す数値です。Oracleの場合，アクセス・パスのランクは15に分かれています（（表1[拡大表示]））。基本的にランクが上位のアクセス・パスの方が高速です。
　ランクの最上位に位置するアクセス・パスは，ROWIDによる単一行アクセス（ランク1）で，最下位のランクは全表走査（ランク15）となっています。オプティマイザは，SQL文のWHERE句の条件とインデックスの有無などから，使用可能なアクセス・パスを求め，その中でランクがもっとも上位のものを選択します。
　SQL文を変えると，使用可能なアクセス・パスは変化します。すなわち，オプティマイザによる処理結果を直接操作することはできませんが，SQL文を変更することで間接的に実行計画を変更できるのです。
　一方，コスト・ベース・アプローチでは，使用可能なアクセス・パスやアクセスするオブジェクト（表やインデックスなど）に関する「統計情報」を使用して，アクセス・パスの「コスト」を計算します。そして，コストがもっとも低くなるものを実行計画として選択します。
　ここで言うコストとは，処理に必要なリソースの消費量のことで，最も重要視されるのが処理に必要なディスク・アクセスの回数です。ほかにCPUの負荷やメモリーの使用量なども考慮されます。統計情報は，テーブルのレコード数や，フィールドの値の最大値/最小値などで，RDBMSがテーブル定義などの情報とともに管理しています。
　ルール・ベース・アプローチでは，ランクの上位にあるアクセス・パスを選択するのが基本です。アクセス・パスのランク付けは一般的な状況を前提にしているため，場合によっては遅いほうのパスを選択してしまうことがあります。例えば，
SELECT * FROM emp WHERE  eno ＞ 500のような範囲検索の場合，表全体の中で取り出すレコードの割合が少なければ，インデックスを使って検索したほうが高速でしょう。一方，取り出すレコードの割合が大きければ全表走査のほうが高速になります。しかし，ルール・ベース・アプローチでは，常にインデックスによる検索を選択してしまいます。
　これに対してコスト・ベース・アプローチでは，キーenoの統計情報から得たenoの値の範囲を基に「eno ＞ 500」を満たすレコードの割合を推測します。そのうえで，高速と思われるほうを選択するので，こうした問題は発生しにくくなります。
　したがって現在では，コスト・ベース・アプローチが主流になっています。例えば日本IBMのDB2はコスト・ベースのオプティマイザだけを実装しています。OracleやSQLServerはどちらも実装していますから，状況に応じて使い分けることが可能です。ただし，コスト・ベース・アプローチでしか使えない機能もあるので，注意が必要です。

bgx5810

基礎から理解するデータベースのしくみ（4）

SQL文はどのように実行されるのか(3)
      

表2●リスト1～3で利用したテーブルcustomersの内容 [画像のクリックで拡大表示]

リスト1 ●「!=」で比較した場合の実行計画。オプティマイザは全表走査を選択しています [画像のクリックで拡大表示]

リスト2 ●条件をIN 演算子で書き換えた場合の実行計画。オプティマイザは，やはり全表走査を選 [画像のクリックで拡大表示]

リスト3 ●ヒント句（赤枠内）を指定した例。オプティマイザはインデックスでアクセスしています [画像のクリックで拡大表示]

図4●ネスト・ループ結合アルゴリズム。テーブルAの各レコードについてテーブルBのすべてのレコードと比較します [画像のクリックで拡大表示]

図5●マージ結合アルゴリズム。あらかじめソートした二つのテーブルのそれぞれについてポインタを進めながら比較します [画像のクリックで拡大表示]

図6●ハッシュ結合アルゴリズム。テーブルBに対してハッシュ・テーブルを作成し，それを利用してテーブルAの各レコードについて検索を実行します [画像のクリックで拡大表示]

    データベースの統計情報は定期的に更新する　基本的には，ほとんどの場合にコスト・ベース・アプローチに基づくオプティマイザは最適な実行計画を選択してくれると考えてさほど問題はありません。ただ，コスト・ベースの基になるコストの計算は，テーブルのフィールドの値が均等に分布していると仮定して行います。そのため，データの分布に極端な偏りがある場合などは，実際には全件走査のほうが処理は早く終わるのに，インデックス検索を選択してしまうような場合もあり得ます。
　コスト・ベース・アプローチを使って効率の良い実行計画を立てるには，定期的に統計情報を更新することが重要なポイントとなります。統計情報は，あくまでもそれを作成したときのデータベースの状態を反映しています。したがって，統計情報を作成した後にデータを大量に追加したり，更新したりするとデータベースの正確な内容を反映していないものになってしまいます。
　適切なインデックスを定義しても，統計情報が不正確では，オプティマイザは最適な実行計画を選択してくれません。例えば，実際はレコードが100万件あったとしても，レコード件数100件の時点で統計情報の作成/更新を行ったままだと，オプティマイザはレコード件数が100件であることを前提に実行計画を決定してします。つまり，本来ならインデックスを使ってアクセスしたほうが高速なのに全表走査を選択し，100万件のレコードを順にアクセスしてしまう，といったことになるわけです。Oracleの場合であれば，ANALYZEコマンドやDBMS_STATSパッケージなどを使って定期的に統計情報を更新することを心がけてください。
ヒント句を指定して実行計画を立てさせる　次に，SQL文の記述のしかたによって，コスト・ベース・アプローチで作成する実行計画がどう変わるかを例で見てみましょう。ここでは，（表2[拡大表示]）のようなテーブルに対して，リスト1～3のような3種類のSQL文を発行してみます。いずれも，フィールドstatusの値がvalidでないレコードを抽出する処理です。
　（リスト1[拡大表示]）では，「status !='valid'」でデータを選択しています。statusにはインデックスを作成してありますが，リスト1の下の実行計画を見るとオプティマイザが全表走査（FULL）を選択していることがわかります。「!=」を使う場合にオプティマイザはインデックスを利用するアクセス・パスを選択しないからです。
　（リスト2[拡大表示]）では，インデックスを使うアクセス・パスを選ぶようにするために「status != 'valid'」を「status in ('canceled','overdue')」に置き換えてみました。このSQL文は，
(1)status = 'canceled'のレコードをインデックスを使って取得
(2)status = 'overdue'のレコードをインデックスを使って取得
(3)(1)，(2)の結果を連結するという手順を踏むことによって，インデックスを利用してアクセスすることを意図したものです。しかし実際には，リスト2の下の実行計画を見ると，リスト1と同じ全表走査が選択されていることがわかります。これはどうしたわけなのでしょうか。
　表2に示すように，statusフィールドは，valid，canceled，overdueの三つの値しかとりません。これらの値が平均して分布しているとすると，(1)，(2)の処理はそれぞれ1/3ずつのレコードを取り出すことになります。条件によって検索候補をあまり絞り込めない場合は，インデックスによる検索よりも全表走査のほうが高速になります。そう考えると，オプティマイザが全表走査を選択したことにも一応納得がいきます。
　ただ，今回の場合はデータの分布に偏りがあり，canceledとoverdueの値をとるレコードがごくわずかしかありません。そのため，実際にはインデックスによる検索の方が高速に実行できます。こうした事態に対処するため，多くのRDBMSでは，ユーザーがオプティマイザに対してどのような実行計画を作るかを明示的に指示するための機能を提供しています。それがヒント句です。
　ヒント句は，オプティマイザによるアクセス・パスの選択をユーザーが制御するために，SQL文の中に埋め込む指示のことです。インデックスを使うようにヒント句を与えて実行計画を立てさせたのが（リスト3[拡大表示]）です。ヒント句は，「/*+」と「*/」で囲んで指定しています。リスト3の下の実行計画を見てください。リスト2のときに説明した(1)～(3)の手順でインデックスを利用してアクセスしていることを確認できるでしょう。ヒント句は，オプティマイザに対してインデックスの使用を明示的に指示する場合だけでなく，アプローチの種類，アクセス・パス，結合順序などを指定するときにも利用できます。
結合アルゴリズムを使い分ける　ここまで述べてきたことからおわかりのように，オプティマイザによる最適化は万能ではありません。データの分布が偏っていたり統計情報が不正確だったり，といったさまざまな原因で，最適でないアクセス・パスを選択してしまい，期待通りのパフォーマンスが出ないこともあります。
　こうしたことによるパフォーマンスの低下を防ぐには，明示的にヒントをつけるなどプログラマがSQL文の書き方を工夫する必要があります。以下では，そうした点の中から，特に速度に影響が出やすいものを取り上げましょう。
　まずは，テーブルを結合（JOIN）するアルゴリズムについてです。SQL文の処理には，大きく分けて，選択，射影，結合の3種類がありますが，最も負荷が大きいのがこの結合処理です。結合処理の最適化の優劣が，SQL文の高速化のカギを握っている，といっても過言ではありません。
　RDBMSがテーブルを結合する際に利用するアルゴリズムには，「ネスト・ループ結合」「マージ結合」「ハッシュ結合」の三つがあげられます。
●ネスト・ループ結合　ネスト・ループ結合は，単純に二重ループを回してテーブルを結合する方法です。例えば，AとBの二つのテーブルがあった場合，Aの各レコードごとにBの全レコードとの比較して，フィールドの値が一致するものを探します（図4[拡大表示]）。そのため，コストは二つのテーブルのレコード数の積に比例します。Bにインデックスが定義されている場合は，Bのレコードの検索にインデックスを利用することも可能です。一般には，インデックスが設定されていない小さなテーブルと，インデックスが設定されている大きなテーブルの二つを結合する場合に効果的です。
●マージ結合　マージ結合は，ネスト・ループ結合の改良版と言える方法です。まず，二つのテーブルを，結合するフィールドについてあらかじめソートしておきます。そして，両方のテーブルのレコードに対して持たせたポインタを，レコードの上から下へと順に走査させながらフィールドの値が一致するものを探します（図5[拡大表示]）。レコードの走査が1回で済むのが特徴です。
　例えば図5では，まずA，Bのポインタの両方を先頭のレコードにおき，Aの2とBの1を比較します。Bのレコードはソート済みなので，もしBに値2を持つレコードがあるなら，下方にあるはずです。そこでBのポインタを一つ下へ移動すると，2が見つかります。
　さらにBのポインタをもう一つ下に移動して，値3のレコードを取得します。仮にAに値3のレコードがあるなら，それは下方にあるはずなのでAのポインタを一つ下に移動してレコードの値を取り出します。この値は4と，3よりも大きくなってしまったので，今度はBのポインタを一つ下げて値4のレコードを取り出します。このように，「自分が相手よりも値が大きくなったら，相手のポインタを一つ進める」ことを繰り返していけば，最終的に条件に見合うレコードを取り出すことができます。
　マージ結合では，テーブルがソート済みでない場合，ソートに要するコストも考えなくてはなりません。しかしそれでも一般的には，ネスト・ループより低コストになります。ソートは，レコードそのものをソートするほかに，インデックスをソートする方法もあります。
●ハッシュ結合　これもネスト・ループ結合の改良版と言うべきものです。ネスト・ループ結合では，テーブルAの各レコードについて，テーブルBを全件走査しています。この検索処理の部分にハッシュ法を使うことで高速化を図るのがハッシュ結合です（図6[拡大表示]）。
　まず，結合するフィールドの値をキーとして，テーブルBに対するハッシュ・テーブルを作ります。あとはテーブルAのレコードごとにフィールドの値が一致するものをハッシュ・テーブルから検索すれば，テーブルの結合が完成します。元のテーブルのサイズが大きいと作成したハッシュ・テーブルがメモリーに収まらないため，一般にはあらかじめテーブルをいくつかのパーティションに分割してから，パーティションごとにハッシュ結合を行います。
　これらの三つのアルゴリズムは，一般的に言って，ネスト・ループ結合＜マージ結合＜ハッシュ結合の順で高速になります（ハッシュ結合が最速）。ただし，二つのテーブルのレコードの数が極端に違う場合や，両方のレコードの数が十分小さいときには，必ずしもこの順番にならないこともあります。加えて，応答時間が重要なとき，すなわち「処理がすべて終了するまでの時間を短くするより，とにかく最初に検索条件に合致した1レコードを早く返したい」というような場合には，ネスト・ループが向いています。
　テーブルの内容や処理の目的などに応じて最適なアルゴリズムは変わります。ヒントを使って結合アルゴリズムを明示的に指定するなどして，状況に応じて使い分けるようにしてください。例えばOracleでは，USE_NL，USE_MERGE，USE_HASHの各ヒント句を使って，ネスト・ループ結合，マージ結合，ハッシュ結合を使用するように指定できます。SQLServerの場合は，LOOP，MERGE，HASHの各ヒントを利用すればいいでしょう。

bgx5810

基礎から理解するデータベースのしくみ（5）

SQL文はどのように実行されるのか(4)
      

図7●インデックスを作成したほうがよい場合としないほうがよい場合の例 [画像のクリックで拡大表示]

    インデックスの作り過ぎに注意　SQL文を実行する際のパフォーマンスに大きな影響を及ぼすものとして，もう一つ，インデックスがあります。インデックスについては，どう定義すべきかというデータベース設計上の問題と，インデックスを有効に使うためのSQL文をどう書くべきかというコーディング上の問題があります。
　ここではテーブル設計上の問題を主に取り上げます。SQL文のコーディングについては囲み記事「SQL文を最速にする11のポイント」を参照してください。
　インデックスは，テーブルの検索速度を向上させるためのものです。それぞれのSQL文に対して最適なインデックスを定義するのが理想的ですが，実際にはある程度限られたインデックスで，必要なパフォーマンス要件を満たすようにインデックスを定義する必要があります。加えて，どんなSQL文が実際に発行されるのかがあらかじめわかっていない場合は，適当な想定に基づいてインデックスを定義しておかなくてはなりません。
　定義するインデックスの数は，参照のみ行うSQL文であれば論理的にはいくら多くてもかまいません。しかし実際には，SQL文自体は参照しているだけであっても，データのロードやインポートなどの準備過程が必ず発生します。そのため現実には，インデックスの数を制限する必要が生じます。一般に情報系システムやマスター・テーブルのような参照のみのテーブルの場合でも，インデックスの数は6～7個以内を目安とするのが普通です。
　インデックスを作成すると検索時間は短縮できますが，データの挿入，削除，更新が遅くなることには注意しておかなければなりません。レコードに対して行う処理以外に，インデックスに対して処理を行う必要があるからです。更新が頻繁に発生するオンライン処理系でデータベースを使用するのであれば，テーブルの更新に伴うインデックス更新の負荷を考慮して，インデックスは2～3個以内にしておくのが良いでしょう。
　むやみにインデックスを定義すると，効果がないどころか，有害になることもあります。インデックスを定義するかどうかは処理の内容と頻度を考慮して決めなくてはなりません。インデックスを作成したほうがよい場合と，作成しないほうがよい場合について，（図7[拡大表示]）にまとめておきましたので，参考にしてください。

SQL文を最速にする11のポイント　たとえ最終的な結果が同じでも，SQL文は書き方一つでパフォーマンスがずいぶんと変わってきます。ここでは，速いSQL文を記述するためのポイントや注意点をいくつか紹介しておきましょう。
●WHEREの左辺で算術演算子や関数を使わない　WHERE句の左辺に算術演算や関数を指定すると，インデックスが使われません。例えば，
SELECT NAME FROM CUSTOMERS
  WHERE SAL - TAX ＞ 1000とすると，たとえSALフィールドにインデックスが定義されていてもテーブル全体を走査してしまいます。こうした場合は，
SELECT NAME FROM CUSTOMERS
  WHERE SAL ＞ TAX + 1000のように記述すれば良いでしょう。
●「後方一致」検索はなるべく避ける　インデックスが付加されているフィールドであっても，LIKE '％AAA' のような「後方一致」を指定すると，インデックスを検索せずにデータ部の全表走査が行われます。したがって「後方一致」の使用はなるべく避けるようにしましょう。どうしても必要であるなら，
・何らかの，少量まで絞り込める条件とAND条件で組み合わせる
・複数のフィールドに分割し，少しでも前方・完全一致できる範囲を広げる
といった方法を検討して下さい。
●IS NULL，IS NOT NULLを単独で使わない　条件を表すWHERE句にIS NULL/IS NOTNULLを指定したときは，インデックスを定義したフィールドであっても，全表走査が行われます。したがって，これらの条件を指定するときは，単独で指定するのではなく，何らかのかなり絞り込める条件を合わせて指定してください。例えば，問い合わせの結果を変更せずに「B =10」の条件を付加できるなら
…WHERE A IS NULLとする代わりに
…WHERE A IS NULL AND B = 10とします。
●SELECT文で「＊」を使わない　レコード長が長いときや，フィールド数が多いときには，すべてのフィールドを表す「＊」を指定するのはできるだけ避けて，使用するフィールドだけを指定するようにします。「＊」を指定すると，参照系のSQL文では，すべてのフィールドを繰り返してコピーするため，リソースを無駄に使うことになります。最低限度必要なフィールドだけを指定するのが基本です。
●ORはある程度絞り込んでから使う　論理演算子ORを使用した場合，一応インデックスが使用されるものの，個々の条件が抽出する件数が少ない（数％程度）状態でないと，あまり効果がありません。
●DISTINCTの代りにEXISTSを使う　SELECT文にDISTINCT＊Aを指定すると処理に非常に時間がかかります。DISTINCTを使用するのは極力避けましょう。DISTINCTと同等の結果を得ることのできるSQL文にEXISTSがあります。例えば，
SELECT DISTINCT a.ID1, a.NAME1 FROM
TABLE1 a, TABLE2 b WHERE a.ID1 = b.ID2のSQL文は，副問い合わせの条件としてEXISTSを指定して
SELECT a.ID1, a.NAME1 FROM TABLE1 a
  WHERE EXISTS ( SELECT 'X' FROM
  TABLE2 b WHERE a.ID1 = b.ID2)と書き換えることができます。同様に，NOT INからNOT EXISTSに代替することによってパフォーマンスが向上することもあるので，これも検討してみてください。
●GROUP BY，ORDER BY，HAVINGは注意する　GROUP BY句，ORDER BY句，HAVING句は，余分なディスク入出力が発生したりディスク領域を使うので，自分もしくはほかのプログラムのパフォーマンスに悪影響を及ぼします。このことを念頭において，使わずに済むならなるべく使わないようにしましょう。
●演算子の組み合わせで速度が変わる　検索条件に，「＞」「＜」「＝」をANDで組み合わせるときは，指定の仕方によってインデックスの使われ方が異なります。等号と不等号の組み合わせは，等号のみインデックスが使われます。例えば，
SELECT NAME FROM CUSTOMERS
  WHERE JOB = 'MANAGER'
  AND SAL ＞ 1000とすると，「JOB = 'MANAGER'」にはインデックスが使われますが，「SAL ＞ 1000」には使われません。また，不等号同士の組み合わせでは，先に指定した条件だけにインデックスが使われます。つまり
SELECT NAME FROM CUSTOMERS
  WHERE TAX ＞ 100
  AND SAL ＞ 1000のSQL文では，RDBMSは「TAX ＞ 100」だけにインデックスを使い「SAL ＞ 1000」には使いません。
●テーブルの別名を利用する　テーブルに別名をつけて，フィールド名にはその別名をつけると，SQL文の解析処理を減らすことができます。例えば，
SELECT ID, NAME FROM CUSTOMERS
  WHERE SAL ＜ 1000
よりも，
SELECT a.ID, a.NAME FROM CUSTOMERS a
  WHERE SAL ＜ 1000
のほうが高速になります。●SQL文の表現を統一する　本文中で述べたように，RDBMSは実行計画をキャッシュに保存しておいて再利用します。ところが，SQL文に定数を直接記述してしまうと，RDBMSは定数値だけが異なるSQL文を別のものと解釈するため，再利用されません＊B。バインド変数を使用して，できる限りSQL文を統一するようにします。また，文字の大小や記述の仕方なども統一しておかないと別のSQL文だと認識されてしまうので，気を付けてください。
●SQL文を簡潔に記述する　SQL文はなるべく簡潔に記述するようにします。そうすることで，SQL文の処理時間を短縮することができます。

bgx5810

基礎から理解するデータベースのしくみ（6）

データの格納方法を知ろう(1)
      

図1●データ・ファイルにおけるページとエクステントの関係 [画像のクリックで拡大表示]

    　データベースのインデックス＊1の作成やパラメータの設定は，システムのパフォーマンスを大きく左右します。加えて，メンテナンスの手間にも影響します。「面倒な設定作業はほとんどツールに任せている」なんていう人もいるかもしれませんが，こうした作業をきちんとやることは実用的なシステムを作るには避けて通れません。では，最適なインデックス作成やパラメータ設定ができるようになるにはどうすればよいのでしょうか。
　Part2では，リレーショナル・データベース管理システム（RDBMS）がデータをディスクに格納するやり方やアクセス方法について解説します。さらに，高速な検索が可能なBツリー・インデックスやハッシュ・インデックスのしくみなどを学んでいきましょう。
データベースには3種類のファイルがある　最初に，データベースを構成するファイルについて簡単に触れておきましょう。データベースは大きく分けて，「データ・ファイル」「ログ・ファイル」「コントロール・ファイル（ルート・ファイル）」の3種類のファイルで構成されます＊2。
　データ・ファイルは，レコードやインデックスなどのデータを実際に格納するファイルで，データベースの実体とも言えるファイルです。巨大なデータベースの場合には非常に大きなファイルになりますから，必要に応じて複数のデータ・ファイルを作成することもあります。
　ログ・ファイルは，データの追加，更新，削除といった，データベースに対してユーザーやアプリケーションが実行したすべての操作を記録するファイルです。システムがダウンするなどの障害が発生しても，このファイルの情報を利用すればデータベースの内容を復元できます。コントロール・ファイルは，RDBMSが管理するファイルの基本情報を保持しています。容量は小さいですが，非常に重要なファイルなので2重化することもよくあります。
　データ・ファイルについて，もう少し詳しく見てみましょう。データ・ファイルに格納するデータは，大きく分けてシステム用とそれ以外に区別されます。システム用データには，データベースにログインできるユーザーの情報，テーブル，ビュー，インデックスを管理するための情報，オプティマイザが最適化を行うための統計情報などがあります。
　システム以外のデータとしては，テーブルやインデックスの内容，トランザクション＊3処理で必要になるデータ，ソート（並べ替え）などを行う際に一時的に作成するデータなどがあげられます。これらのデータは，物理的には複数のファイルにまたがって格納されることもあります。RDBMSは，システム用データとして格納した管理情報に基づいて，物理ファイル内でのテーブルの位置などを決定し，アクセスを行います。
データ・ファイルはページが基本単位　RDBMSは，データ・ファイル内部の領域を，「ページ」と「エクステント」という二つの単位で管理します。ページはRDBMSがディスク領域を管理する際に基本となる単位で，エクステントはディスク上で連続した複数のページで構成します（図1[拡大表示]）。
　ページには，テーブルを構成するレコードや，インデックスのエントリ＊4を複数格納します。RDBMSはメモリーとディスクの間の入出力をページ単位で管理し，キャッシュ・バッファ＊5への入出力もページごとに行います。
　ページのサイズはRDBMSやOSの種類などによって異なりますが，一般的には数KB程度＊6です。Microsoft SQL Server（以下，SQL Server）は8KB固定です。Oracleでは，データベースを作成する際にページ・サイズを設定できます。
　ページ・サイズの決定は，RDBMSのパフォーマンスに影響を与えます。扱うデータやアクセスの特性に合わせて決める必要があります。例えば，1回の入出力で扱う平均的なデータ量が少ない場合には，ページ・サイズが小さいほうが有利です。レコードを一つだけ読み込めばいいような場合でも，ページ全体を読み込むことになり無駄が多くなるからです。一方，1回の入出力で扱うデータ量が多い場合は，ページ・サイズを大きくしたほうが良いでしょう。ページ・サイズが小さいとディスクとの入出力の回数が増えて，効率が悪くなります。
エクステントはオブジェクトに領域を割り当てる単位　エクステントは，テーブルやインデックスといったデータベースのオブジェクトに対して，領域を割り当てる際の単位です。例えばテーブルを一つ作成すると，RDBMSはそれに対して一つのエクステントを割り当て，その中にレコードを書き込んでいきます。レコードの数が増えてエクステント内のページを使い切ったら，新たなエクステントを追加して割り当てます＊7。
　テーブルなどのオブジェクトが複数のエクステントで構成される場合，各エクステントは必ずしも連続しているとは限りません。そのため，RDBMSは内部にエクステントを管理する情報を保持しています。テーブルを先頭から順に検索するような場合には，この管理情報に基づいて目的のエクステントを探していきます。
　エクステントのサイズはオブジェクトごとに設定できます。一般的には格納するデータ量に応じてサイズを決定します。エクステント内のページはディスク上で物理的に連続していることが保証されるため，テーブル全体を先頭から検索する際などにはエクステントのサイズを大きくして，テーブルがまたがっているエクステントの数を減らしたほうが高速になります＊8。
　ただし，むやみに大きなサイズを割り当てると，ディスク領域の無駄づかいになりかねません。小さなオブジェクトに対しても，エクステントのぶんだけの領域を確保してしまうからです。例えば，小さな参照表＊9に対してのエクステントは小さくするほうが良いでしょう。
　RDBMSは，テーブルに格納するレコードが増えると自動的にエクステントを割り当てていきますが，レコードが削除されても自動的にエクステントを解放することはありません。レコードを削除するときにページ内のレコードは消去しますが，エクステントが解放可能かどうかまではチェックしないからです。
　したがって，あるテーブルにレコードを追加しようとしたときに「データ・ファイルの領域不足でエクステントを割り当てできない」というようなエラーが発生した場合には，別のテーブルのレコードを削除しても意味がありません。領域を確保するには，別のオブジェクトに割り当てられたエクステント内の情報をすべて消去することによって，エクステントを空き領域として解放する必要があります。
　エクステントには連続したページを割り当てますから，ディスク上の空きページの合計が新しいエクテントに必要なページ数より多くても，ページが連続していない場合には割り当てに失敗することがあります。エクステントのサイズが異なるテーブルの作成や削除を繰り返すと，ファイル内の空き領域が不連続になり，こうしたことが起こりがちです。この場合には，データベースの再編成＊10をして空き領域をまとめる必要があります。

bgx5810

基礎から理解するデータベースのしくみ（7）

データの格納方法を知ろう(2)
      

図2●ページの内部構造。Oracleの場合，レコード・データはページの後ろから，レコード・ディレクトリはページの前から割り当てられる [画像のクリックで拡大表示]

図3●レコードの内部構造。先頭にレコード・ヘッダーがあり，その後ろにフィールド長とフィールド・データの組が並ぶ [画像のクリックで拡大表示]

表1●ANSIのデータ型に対応するOracleとSQL Serverのデータ型とサイズ [画像のクリックで拡大表示]

図4●SQL＊Plusで数値型のフィールドを持つテーブルを作成してフィールドの内部型を調べたところ [画像のクリックで拡大表示]

図5●図4のテーブルにレコードを追加してから各フィールドが内部で占めるサイズを調べたところ。同じデータ型でもフィールドの値によってサイズが違うことがわかる [画像のクリックで拡大表示]

図6●レコード・チェーンの様子。更新後のデータは別のページに割り当てて，元のレコードの位置にはその位置へのポインタを格納する [画像のクリックで拡大表示]

    テーブルとレコードの構造を詳しく見てみよう　次に，RDBMSの基本であるテーブルがどのようにディスクに格納されているのか，その構造について見ていくことにしましょう。
　テーブルを構成する各ページの構造は，おおよそ（図2[拡大表示]）のようになっています＊11。図の左上にある「ページ・ヘッダー」は，ページ・アドレスやページ・タイプ（例えば，格納しているのがテーブルであるかインデックスであるか）など，ページについての一般的な情報を格納しています。その右の「テーブル・ディレクトリ」は，ページが格納するテーブル名など，そのテーブルに関する情報を保持します。
　その次の「レコード・ディレクトリ」は，いわばページ内に存在するレコードの一覧表です。各レコードのROWID（行識別子）＊12と，ページ内での物理的な位置（オフセット）のペアを，レコードの数だけ保持しています。一番下の「レコード・データ」の部分が，実際のレコードの内容を格納する場所です。
　ページ・ヘッダーとテーブル・ディレクトリのサイズは固定ですが，レコード・ディレクトリとレコード・データはレコードの数や各レコードのサイズによって変化します。図2の場合，レコード・データは基本的にページの後ろから割り当てていき，レコード・ディレクトリはページの前から領域を割り当てていきます。したがって，ページの中央部分が空き領域になります。
　レコードの内部構造はRDBMSによって異なります。Oracleの場合には大体（図3[拡大表示]）のようになっています＊13。先頭にレコード・ヘッダーがあり，そのレコードのフィールド数やレコード・チェーン＊14している場合のポインタなどを格納しています。その後ろには，レコードを構成するフィールドのフィールド長とフィールド・データのペアが順に並びます＊15。レコードにフィールドが格納される順序は，すべてのレコードで同じです。
　レコードからフィールド・データを取り出すには，まずレコード・ディレクトリを参照して，ページ内部でのレコードの位置を取得します。後は，そのレコードの中でフィールドの長さを順番に調べていけば該当フィールドに到達します。これからわかるように，Oracleの場合，レコードの最後のフィールドを取り出すのは最初のフィールドを取り出すより時間がかかります＊16。
　Oracleではフィールドの値がNULL＊17の場合にはフィールド長（0）だけが記録されます。また，NULLの値を持つフィールドがレコードの最後に位置する場合は，フィールド長も省略されます。そのため，NULLになることが多いフィールドはなるべくレコードの最後に保持するほうが領域を節約できます。
フィールドのサイズは格納するデータによって変わる　データがフィールドに格納されるときの内部表現についても見ておきましょう。これも，RDBMSによって違いがあります。ANSI＊18データ型に対応するOracleとSQL Serverのデータ型および内部表現のサイズを（表1[拡大表示]）に示しておきます。
　数値データを数値型として扱う場合は，必要な精度（全体の桁数）と位取り（小数点未満の桁数）に応じて適切なデータ型を選択しなければなりません。例えば格納する値が−(2の31乗)～(2の31乗)−1の範囲で収まる場合はINTEGER型を利用できます。もっと大きな値を扱う場合は，BIGINTやDECIMALを選べばいいでしょう。
　Oracleの場合，数値はすべて内部的にNUMBER型というデータ型で扱います。ですからINTEGER，FLOAT，DECIMALなどのデータ型は，内部ではいずれもNUMBER型になります。加えて，データが占有する領域のサイズも，精度や位取りだけで決まるわけではなく，格納する値によって変わってきます。
　例えば，Oracleの付属ツールSQL＊Plusで（図4[拡大表示]）の(1)のようなSQL文を指定してテーブルを作成したとしましょう。このテーブルの各フィールドのデータ型をdescribeステートメントで表示してみると，図4の(2)のようになります。テーブルを作成時にDECIMALやINTEGERと指定しても，内部的にはNUMBER型が使用されているのがわかります。
　さらに，このテーブルにデータを格納してからOracleのvsize関数で各フィールドのサイズを調べてみたのが（図5[拡大表示]）です。図4で見たようにdecimal_cはDECIMAL(10)と定義しており，内部的にはNUMBER(10)として扱われます。“VSIZE(DECIMAL_C)”の項目を見ると，1234をインサートした場合はサイズが3バイトですが（図5の(a)），12345をインサートした場合は4バイトになっていることがわかります（同(b)）。データ型としてはNUMBER(10)ですが，フィールドが実際に占有するサイズは格納する値によって変わるわけです。
　もう一つ見てみましょう。inte_cはINTEGERで定義しており，内部的にはNUMBER(38)として定義されています。データ定義から言えば，inte_cはdecimal_cよりサイズが大きいデータ型です。しかしdecimal_cに12345，inte_cに1234をそれぞれ格納した場合の実際の格納領域は，decimal_cは4バイト，inte_cは3バイトになっています（図5(b)）。
　文字列型についてはどうでしょうか。文字列データを扱う場合は，CHARまたはVARCHARを使用します。CHARは固定長で，文字列の長さによらず，指定した長さの領域を占有します。例えばCHAR(50)と定義した場合，格納する文字列の長さが50バイトより小さければ50バイトになるように空白が埋め込まれます。“BLACK”を格納すると，BLACKの後に45バイトの空白が埋め込まれるわけです。
　一方，VARCHARは可変長であり，実際に格納する文字列の長さのぶんだけディスクを占有します。そのため，“BLACK”をVARCHAR(50)に格納した場合は5バイトだけで済みます。半面，レコードを更新する際に文字列の長さが変わるとページの空き領域の検索などの作業が発生するため，固定長を使う場合よりパフォーマンスが低下します。CHARとVARCHARのどちらで文字列データを定義するかは，文字列の最大長や更新頻度などを考えて決定する必要があります。
更新処理ではレコード・チェーンに要注意　テーブルの物理的な構造についてわかったところで，レコードの追加，削除，更新の際にRDBMSが内部でどのように動作しているのかを見ていきましょう。
　レコードを追加する場合にはまず，レコードを格納できるだけの空き領域を持つページを見つけなくてはなりません。RDBMSはそのために，レコードを追加できるページの番号を格納したリスト（フリー・リスト）を保持しています。このリストを順にあたっていけば，（もし存在するなら）必要な大きさの空き領域を見つけることができます＊19。
　十分なサイズの空き領域が見つかったら，RDBMSはその位置にレコードを書き込みます。その際，現在のレコード・ディレクトリの後ろに，そのレコードのROWIDとページ内での物理的な位置から成る新しいエントリを追加する作業も併せて行います。ただし，以前にレコードを削除したときのエントリの領域が残っている場合は，それを再利用することもあります。
　レコードを削除する場合は，該当するレコードをレコード・ディレクトリから検索し，レコード・ディレクトリのエントリと，レコード・データをページから削除します。その際，空き領域の断片化を防ぐために，レコード・データ全体を後ろ方向に詰めることもあります。ただ，削除するたびに詰めるのでは効率が悪いため，現在のOracleやSQL Server2000では新しいレコードを追加するために連続した空き領域が必要になった時点で詰めるようになっています。この場合，レコード・データを指すページ内オフセットの値は変更する必要がありますが，ROWID自体は変わらないため，インデックスなどを書き換える必要はありません。
　レコードを更新する場合は，現在格納されている位置のままで内容だけを書き換えるのが基本です。したがって，更新用に新しいページを探す必要はありません。ただし，更新によって可変長フィールドのサイズが変わる場合は，レコード全体の長さが変化するため，元の位置に収まりきらないこともあります。この場合，そのページの空き領域が十分あれば，そこに更新後のレコードの内容を書き込みます。空き領域が足りない場合は，フリー・リストから十分な空き領域を持つ別のページを探し出し，そこに更新後のレコードを書き込みます。このとき，元のレコードの位置には更新後のレコードを指すポインタを格納しておき，ROWIDが変わらないようにします。
　このように，一つのレコードが複数のページにまたがって格納される状況をレコード・チェーン（行連鎖）と呼びます（（図6[拡大表示]））。レコード・チェーンが発生すると一つのレコードを読むために複数回のディスク入出力が発生するため，パフォーマンスが低下してしまいます。
　レコード・チェーンの発生を防ぐためには，ページの空き領域が一定以下になったらそのページに新規のレコードを追加しないようにするのが効果的です。つまり，ページの空き領域の一部を，更新用に予約しておくわけです。多くのRDBMSは，そのための設定パラメータを用意しています。
　例えばOracleでは，テーブルを作成する際にPCTFREE，PCTUSEDという二つのパラメータを指定できます＊20。ページの空き領域がPCTFREEで指定した割合以下になると，以後そのページへの新規レコードの格納が禁止されます。その後，レコードが削除されるなどして使用領域の割合がPCTUSED以下になると，再び新規レコードの追加が可能になります。
　これらのパラメータはテーブルごとに設定できるので，扱うデータのサイズやアクセスの性質に合わせて適切に設定してください。例えば，検索中心のデータベースなら，各ページにできるだけ多くのレコードを格納したほうがディスクの使用量やパフォーマンスの点で有利なため，PCTFREEを小さめに設定します。対して更新処理が多いシステムであれば，レコード・チェーンが発生しないようにPCTFREEを大きめに設定する必要があります。

bgx5810

基礎から理解するデータベースのしくみ（8）

データの格納方法を知ろう(3)
      

図7●Bツリー・インデックスの構造 [画像のクリックで拡大表示]

図8●インデックス・スプリットの様子。リーフ・ノードがいっぱいでキーを挿入できないときに起こる [画像のクリックで拡大表示]

    インデックスで検索を高速にする　ここまでの説明でおわかりのように，一般にテーブル内のレコードがディスク上に格納される順序は，レコードを追加する順序やページに空きがあるかどうかなどに左右され，特定のキーの順番に並んでいるわけではありません。そのため例えば，従業員テーブル（emp）から従業員番号（eno）が71であるレコードを抽出するSQL文である
SELECT * FROM emp WHERE eno = 71のような単純な検索処理でも，テーブル内のすべてのレコードを一つずつ調べていかなくてはなりません。これではレコード数が膨大な場合に大変な時間がかかってしまいます。そこで，こうした特定のキーに対する検索を高速化するために用意されている仕組みがインデックス（索引）です。
　インデックスの基本的な考え方は，書籍の索引と同じです。例えば，書籍の中から「テーブル」というキーワードを検索する場合，あいうえお順に並んだ索引でまず「て」の位置を探し，「テーブル」が見つかったら対応する位置（ページ）を調べて本文を参照する，という手順を踏んだほうが，本文を先頭から順に探すよりもはるかに速く探すことができますね。データベースのインデックスも，書籍の索引と同様に，キーの値とその値を持つレコードの位置の組をキーの順に格納したものです。
　ただ，これらの組を書籍の索引のように単に1列に並べてディスク上に格納してしまうと，インデックスからキーを検索する処理自体に時間がかかるため，あまり効率がよくありません。そこで，多くのRDBMSでは検索効率を上げるために，インデックスを「Bツリー」と呼ぶデータ構造で格納しています。
　Bツリーは，文字通りツリー（木）状の構造を持ち，各ノードには一定の個数のキーとポインタ（位置情報）のペアを格納しています（図7[拡大表示]）。最下層のノードをリーフ・ノード，一番上のノードをルート・ノード，その間の層のノードをブランチ・ノードと呼びます。ブランチ・ノードは図では1階層ですが，多階層にすることも可能です。一般に，レコードの数が多くなると，それにつれてブランチ・ノードの階層が深くなります。ただ，一般的なページ・サイズとレコード数では，Bツリーの階層はせいぜい3～4階層にしかならないと考えていいでしょう。
　次にノードの中身について見てみましょう。各ノードのエントリであるキーとポインタ（位置情報）のペアは，キーの値の昇順もしくは降順で並んでいます。これらのエントリはそれぞれ，そのノードの子に相当するノードと1対1に対応し，子ノードの左端のキーの値と，子ノードを指すポインタを格納します。ノードの最終階層であるリーフ・ノードのエントリには，各レコードのキーの値とレコードの位置を格納します。Bツリー・インデックスの場合は，さらにリーフ・ノードの間，およびブランチ・ノードの間を，双方向のポインタでリンクしておくのが一般的です。
　各ノードの最大サイズは，通常，ページ・サイズと同じで，1ページに1ノードが格納されます。したがってページ・サイズが大きいほど多数のエントリを格納できます。テーブルに含まれるレコード数が一つのノードに格納できる最大エントリ数より少ないときは，ルート・ノードのみが存在してルート・ノードからデータベース・レコードを直接指します。
Bツリー・インデックスは範囲検索にも有効　Bツリー・インデックスを利用したレコード検索では，二分探索＊21を行いながらルート・ノード，ブランチ・ノード，リーフ・ノードとたどって，レコードの位置情報（ポインタ）を取得します。例えば，図7でキー71を探したいとします。その場合，まずルート・ノードを二分探索してキー71を探します。71は63より大きく，87よりも小さいので，キー63から始まるブランチ・ノードを探せばよいことがわかります。
　このブランチ・ノードを調べると，69＜71＜81なので，キー71はキー69から始まるリーフ・ノードに含まれることがわかります。最後にこのリーフ・ノードでキー71のエントリが見つかれば，そのポインタを使ってレコードにアクセスできます。リーフ・ノードのエントリはデータベースのレコードと1対1に対応するため，リーフ・ノードに該当エントリが存在しない場合はデータベース中にレコードが存在しないことになります。
　Bツリー・インデックスは昇順または降順に並んでいるため，範囲検索にも使うこともできます。例えば，先ほどの従業員テーブル（emp）で従業員番号（eno）が71より大きく83より小さいレコードを探すために，図7のインデックスで
SELECT * FROM emp
  WHERE eno ＞ 71 AND eno ＜ 83を実行する場合，最初は先ほどと同様にキー71に対してルート・ノード→ブランチ・ノード→リーフ・ノードと順に検索して71を超える最小のキーを探し出します。あとはそのリーフ・ノードのエントリをキーが83以上になるまで順に取り出していくだけで，求めるレコードすべてにアクセスできます。
　各リーフ・ノードは次のリーフ・ノードへのポインタを持っています。したがって，検索するキーが複数のリーフ・ノードにまたがって格納されているような場合でも，ブランチ・ノードに戻る必要はありません。
　このほか，SQL文に“ORDER BY”を指定して結果をキーの順にソートしたい場合に，別にソート処理を行う必要がないのもメリットです。リーフ・ノードのエントリの順にレコードを取り出すことで自動的に結果がキーの順にソートされるからです。
レコードを追加しても検索性能は安定している　レコード内のあるフィールドに対してインデックスを作成した場合，レコードの追加や削除といった更新系の処理をしたら，レコード自体だけでなくインデックスの内容も更新する必要があります。レコードを追加する場合は，先の検索の場合と同じようにルート・ノードから順にたどってエントリを追加するリーフ・ノードを探し出します。ノードに空きがあるなら，昇順または降順の順序を守ってエントリを追加するだけでインデックスの追加は終了します。
　一方，ノードに空きがないときは，新たにノードを追加して空きエントリを作らなくてはなりません。この場合は，新たにページを割り当ててリーフ・ノードを作成し，現在のノードの前もしくは後ろ半分のエントリを作成したノードに移動します（図8[拡大表示]）。このように，一つのノードを二つに分割する操作をインデックス・スプリットと呼びます。インデックス・スプリットの結果，インデックスのエントリのデータがページ全体に占める割合はほぼ半分程度になります。
　インデックス・スプリットではさらに，新たに作成したノードを指すポインタを，上位のノードのエントリに追加しなければなりません。この上位ノードにも空きがない場合には，さらにインデックス・スプリットが発生することになります。
　ルート・ノードがエントリでいっぱいになったら，上位に新しいルート・ノードを作成します。この場合，自分自身はブランチ・ノードになり，さらにインデックス・スプリットでもう一つブランチ・ノードを作成します。ただし，物理的にはルート・ノードは以前のものをそのまま使用し，新たに二つのブランチ・ノードを作成します。これはルート・ノードのアドレスがデータベースの管理情報領域で多用されているため，これを変更するのは影響が大きいからです。
　インデックス・スプリットでは，ルートがスプリットするケースを除けばルート・ノードからリーフ・ノードまでの距離（階層の数）は変化しません。このためレコードを追加した場合でも，検索に要する時間が安定しているのもBツリーの特徴です。
レコードを大量に削除したらインデックスを再構築する　インデックス・エントリを削除する場合は，最初に該当エントリをルート・ノードから順にたどって検索し，該当するリーフ・ノードを見つけてそのエントリを削除します。リーフ・ノードの左端の値は，その親となるブランチ・ノードのエントリにも格納されています。したがって，左端のエントリを削除した場合は親ノードのエントリを新しい左端の値で書き換えなくてはならないように思えますが，実際にはその必要はありません。親ノードのエントリに格納した値がリーフ・ノードの左端の値よりも小さいという条件を満たす限り，検索に影響が出ないからです。
　リーフ・ノードのエントリの削除を繰り返して，隣接するリーフ・ノードのサイズがともに50％を下回るようになった場合でも，隣接するリーフノードをまとめて一つのページにする（マージする）のは行わないのが普通です。削除のたびにノードのサイズをチェックしていては時間がかかりますし，インデックスの追加と削除を繰り返す場合にはスプリットとマージが連続的に発生してパフォーマンスが大幅に悪化するという問題があるからです＊22。
　これからわかるように，レコードを大量に追加していったんブランチ・ノードの階層が増えてしまうと，後でレコードを削除してもそれが減ることはほとんどありません。すなわち，リーフ・ノードに到達するまでのディスク入出力の回数がいったん増えてしまうと，減ることはありません。このため，データを大量に削除した場合は，インデックスを再構築して適切な構造を保つようにしたほうが良いこともあります。
　レコードを更新する際は，インデックスとして使われているフィールドの値が変わらない場合には，当然ですがインデックスの書き換えは必要ありません。インデックスとして使われているフィールドの値が変わる場合は，インデックスの削除と追加が一連の処理として実行されると考えればよいでしょう。

bgx5810

基礎から理解するデータベースのしくみ（9）

データの格納方法を知ろう(4)
      

図9●ハッシュ・インデックスの仕組み。検索するキーの値をハッシュ関数に与えてレコードが格納されたページを特定する [画像のクリックで拡大表示]

図10●レコード・クラスタリングの仕組み。ハッシュ値にしたがって，empとemp_histの二つのテーブルで同じenoを持つレコードを一つのテーブルに格納している [画像のクリックで拡大表示]

図11●ビットマップ・インデックスの仕組み。1になっているビットの位置からキーが対応する値を持つレコードを特定できる [画像のクリックで拡大表示]

    RDBMSが備えるさまざまな高速化手法　RDBMSは，ここまで説明してきた基本的なデータの格納のしかたや操作方法に加え，高速化のための手法をいろいろ用意しています。Part2の最後に，これらの手法をざっと紹介しておきましょう。
●ハッシュ・インデックス　キャッシュ・バッファのサイズや使われ方にもよりますが，一般にBツリー・インデックスを使って巨大なデータベースにアクセスする際には，ルート・ノードだけがキャッシュ・バッファにあるのが普通です。そのため，レコードにたどりつくまでにブランチ・ノード，リーフ・ノード，データベース・レコードと何回もディスクにアクセスしなければなりません。これを1回のアクセスでレコードを取得できるようにしよう，というのがハッシュ・インデックスです。
　ハッシュ・インデックスでは，ハッシュ関数と呼ぶ関数を使って，検索に使用するキーとレコードを含むページを直接関係付けます（図9[拡大表示]）。例えば，従業員番号をキーとする場合，従業員番号を適当な数で割った余りを返すような関数をハッシュ関数として選び，関数の戻り値（ハッシュ値といいます）が指すページにそのキーを持つレコードを格納しておきます。こうしておけば，ある従業員番号を持つレコードを検索する際には，ハッシュ関数で特定したページを読み込むだけで済むようになります。
　ただし，Bツリーの場合と違って，範囲検索には利用できません。したがって，キーの順番にレコードをシーケンシャル（逐次的）に読み込んでいくような検索には向いていません。
　加えて，Bツリーではインデックスの作成，削除をテーブルの作成とは独立にできるのに対し，ハッシュ・インデックスではハッシュ関数の選び方がテーブルの構造に影響します。したがって，テーブル作成の時点で，どのようなハッシュ関数を使ってインデックスを作成するかを決めておく必要があります。
　さらに，通常のテーブルでは，レコードの追加できる空き領域がない場合にはエクステントを追加して割り当ていきますが，ハッシュ・インデックスを使う場合はこうしたことはしません。ハッシュ値に対応するページにレコードを格納するだけの空き領域がない場合は，新たにオーバーフロー用のページを割り当ててレコードを格納します。この場合は，ページのチェーン（連鎖）が発生するために読み出しに複数回のディスク入出力が必要になり，パフォーマンスが低下します。
　したがってハッシュ・インデックスを使う場合には，あらかじめレコードの数を見積もり，データをロードする前に十分なエクステントを割り当てておく必要があります。したがって，扱うデータ量がある程度決まっているOLTP＊23システムなどに向いています。逆に，格納するデータの量が決まっていないような場合には向きません。
　ハッシュ・インデックスを使う場合，レコードは事前に割り当てたページのうち，ハッシュ関数によって定められる場所に直接ロードされます。異なるキーの値が同じハッシュ値を返す場合は，それらのレコードは同じページに格納します。ページのサイズはすべて同じですから，各ページに格納されるレコードの数はなるべく均一になるようにしたほうがディスクの領域を節約できるわけです。
　そのため，大規模なデータベースの場合は特に，多量のキーをすべてのページになるべく均一に割り振るようなハッシュ関数を見つけることが重要になります。キーの性質があらかじめわかっている場合は，RDBMSが備えている内部ハッシュ関数を使うよりも，自前でハッシュ関数を用意したほうが均一な分布を得られることもあります。
●レコード・クラスタリング　特定のキーに対するハッシュ値にしたがって複数のテーブルのレコードを同一ページに格納することで，さらに効率の良いアクセスが可能になることもあります。これをレコード・クラスタリングと呼びます。
　（図10[拡大表示]）はレコード・クラスタリングの例です。従業員テーブル（emp）は従業員番号（eno）が主キーなので，各enoに対してレコードが1件だけ存在します。対して，従業員の経歴を記録するテーブル（emp_hist）ではenoは外部キー＊24なので，同じenoを持つレコードが複数存在する可能性があります。レコード・クラスタリングでは，emp，emp_histテーブルの両方に対して，enoに同一ハッシュ関数を適用してレコードを格納するページを決めます。したがって，同じenoを持つ複数テーブルのレコードが一つのページに存在することになります。
　このとき例えば
SELECT * FROM emp, emp_hist
  WHERE emp.eno=emp_hist.eno AND
  emp.eno=125;というSQL文を実行したとしましょう。まずemp.eno＝125の条件によってempテーブルを含むページを検索して，データを読み込みます。次に，emp.eno＝emp_hit.enoによりemp_histのレコードが読み込まれます。このページはさきほどの検索ですでにキャッシュ・バッファ上に読み込んでいるため，emp_histテーブルをアクセスする際に新たなディスク・アクセスは発生しません。
　ちなみに，レコード・クラスタリングはハッシュ・インデックスに特有の方法というわけではありません。Bツリー・インデックスでも使えます。この場合は，キーの値ごとにレコードをまとめて格納することになります。ただし，Bツリーでは複数回のディスク入出力が必要になるため，検索速度は低下します。
●ビットマップ・インデックス　ビットマップ・インデックスはデータ・ウエアハウス＊25などで，取り得る値の数が少ない＊26フィールドに対して複雑な検索を行う場合に適しているインデックスの手法です。OracleをはじめいくつかのRDBMSに実装されています。
　ビットマップ・インデックスは，キーの取り得る値の一つひとつに対してビットマップ（ビット列）を用意します。例として，市販の音楽用CDの情報を格納するテーブルがあり，そのフィールドの一つに「ジャンル」があったとしましょう。ジャンルは「クラシック」「ロック」「ジャズ」のいずれかの値をとるものとします。この場合，クラシック，ロック，ジャズのそれぞれについてビットマップを用意します（図11[拡大表示]）。
　ビットマップの各ビットは，レコードの位置（ROWID）に対応し，そのビットがオンなら対応するレコードのフィールドがその値であることを示します。例えば図11の場合，クラシックのビットマップを見ると，m番目とn番目のビットがオンになっているので，ジャンル・フィールドの値がクラシックであるのはm番目とn番目のレコードであることがわかります。
　ビットマップ・インデックスの特徴は，WHERE句にANDやORなどが含まれる検索を高速に実行できることです。例えば，音楽用CDのテーブル（cd）から，ジャンルを表すフィールド（genre）の値がクラシックかロックであるレコードを取り出す，
SELECT * FROM cd
  WHERE genre = 'クラシック'
  OR genre = 'ロック'のような検索なら，クラシックのビットマップとロックのビットマップで，ビット単位のORをとるだけで求めるレコードの集合を得ることができます。ビットマップの各ビットが直接ROWIDに対応するため，Bツリーのようにノードをたどっていく必要もありません。
　複数のフィールドに対してビットマップ・インデックスを定義することも可能です。例えば「顧客」テーブルの「性別」「職業」「趣味」の各フィールドにビットマップ・インデックスを作成しておけば，「男性の会社員で趣味がドライブであるレコードを取り出す」といった検索も簡単に実行できます。このほか，1レコードが各キーに対して1ビットしかディスクを占有しないため，インデックスに必要なディスク容量が少なくてすむのもメリットと言えるでしょう。
　半面，ビットマップ・インデックスはレコードの追加，削除，更新に時間がかかるという欠点があります。このため，更新の多いOLTP（オンライン・トランザクション処理）系のシステムには向いていません。データ・ウエアハウスなどのデータが頻繁に更新されないシステムで，テーブルを作成してデータをロードした後でビットマップ・インデックスを作るようにするのが基本です。

bgx5810

基礎から理解するデータベースのしくみ（10）

トランザクションとは何だろう
      

図1●Oracleでトランザクションのロールバックを実現するための仕組み [画像のクリックで拡大表示]

リスト1 ●口座間の振り込みの処理を記述した [画像のクリックで拡大表示]

    　Part1とPart2では，リレーショナル・データベース管理システム（RDBMS）の基本的な機能であるSQLの解析/最適化やデータ・アクセスの方法について学んできました。RDBMSは，このほかにもいくつか重要な機能を備えています。Part3ではその中からデータの一貫性・整合性を保つための仕組みであるトランザクション処理機能について取り上げます。これは複数のユーザーが同時に利用するようなデータベース・アプリケーションに，なくてはならない機能です。
　トランザクションの概念自体はそれほど難しくはありません。ただ，複数のユーザーが同時にアクセスするような状況では，考慮すべきことがいくつかあります。いくつかの概念を押さえながら，RDBMSがトランザクションをどう処理しているかを見ていきましょう。
複数の処理をひとまとめにして扱う　まず，トランザクションとは何なのかを簡単に解説しておきましょう。銀行の口座間で振り込み作業をする場合を考えてください。システムが行う処理は，大体以下のような流れになるはずです。
(1)振り込み人の預金から振り込む金額を差し引く
(2)振込先の預金をそのぶん増やす
(3)取引を記録する
このとき，仮に(2)の処理が，口座番号が見つからないとか，途中でシステムがダウンした，などの理由で，正常に終了できなかったとしたらどうなるでしょうか。振り込み人のほうは預金が減っているのにそのお金はどこにも振り込まれていない，といった不整合性が生じてしまいます。

　こうした不整合性が生じないようにするためには，(2)や(3)の処理に失敗したら，（図1[拡大表示]）の処理を白紙に戻すようにする必要があります。すなわち，これら(1)～(3)の処理は，本来ひとまとまりの処理として扱うべきもので，処理がすべて実行されるか，それともまったく行われないか，のどちらか一方にしなくてはなりません＊1。言い換えれば，処理の一部だけが実行される，というのは許されないのです。
　多くのRDBMSは，こうした目的のために，複数のSQL文からなる一連の処理を，論理的にひとまとめにして扱う機能を備えています。この論理的なひとまとまりの処理をトランザクションと呼びます。トランザクションの中で実行したSQL文の結果は（少なくとも論理的には），すぐにはデータベースに反映されません。「コミット」と呼ぶ操作を行った時点で初めて確定します。
　コミットの反対の操作が「ロールバック」です。ロールバックを行うと，それ以前のトランザクション処理の結果はすべてキャンセルされ，データベースには反映されません。すなわち，データベースはトランザクション処理を開始する前の状態のままです。
　実際に，口座間の振り込みの処理をSQL文で記述してみたのが（リスト1[拡大表示]）です（Oracleの場合）。OracleやSQL Serverでは，特に何も指定しなくても，SQL文のならびを自動的にトランザクションとして扱うようになっています。
　トランザクションは，最初に現れた実行可能文から始まります。そして，
COMMIT WORKと指示された時点で，そのトランザクション内で変更した結果を確定し，データベースに反映します。トランザクションで実行した処理を取り消すなら
ROLLBACKとすればOKです。コミットもしくはロールバックをすると，その次の実行可能文から自動的に次のトランザクションが始まります。
ロールバックには変更履歴を利用する　RDBMSが内部でトランザクションを処理する際の動作を見てみましょう。トランザクション処理を実現するための基本的な方法は，トランザクションの中で行われたデータの変更の履歴を保持することです。この履歴を利用すれば，必要に応じてロールバックができます。ここでは，Oracleの場合を例にとって解説しましょう（図1）。
　トランザクションを開始するとOracleはまず，ロールバック用の情報を保存するためディスク領域の一部を，そのトランザクションに対して割り当てます。この領域をロールバック・セグメントと呼びます。そして，トランザクションの中でレコードの追加や更新などの変更を行うたびに
(1)そのレコードを含むデータ・ページの（変更前の）内容をロールバック・セグメントに保存する
(2)REDOログ・バッファに変更の履歴を記録する
(3)データ・ページの内容を更新する（変更後の内容をデータ・ページに書き出す）
という処理を実行します。ここで，REDOログ・バッファは，変更の履歴を記録しておくためのメモリー上のバッファで，後でディスク上のREDOログ・ファイルに内容が保存されます。REDOログ・ファイルは，システムの障害時などにデータベースの内容を復旧するために不可欠です。
　トランザクションをコミットすると，Oracleはトランザクションを識別するための「システム変更番号（SCN）」を割り当て，ロールバック・セグメントにこの番号とコミット済みであることを記録します。そしてREDOログ・バッファの内容を，REDOログ・ファイルに書き出します。これでトランザクションは完了です。
　ロールバックをする場合は，トランザクション中に実行したすべての変更について，ロールバック・セグメントに保存した元のデータを書き戻します。これで，そのトランザクションはなかったことになるわけです。RDBMSによっては，途中のポイントまでロールバックすることも可能です。その場合は，そのポイント以降に行った変更に対し，ロールバック・セグメントの内容をデータ・ページに書き戻します。
　ロールバック・セグメントやデータ・ページへの書き出しは，実際にはいったんメモリー上のキャッシュ・バッファに対して行われ，後でまとめてディスクに反映します。ただし，REDOログ・バッファの内容は，コミット時に必ずディスクに保存します。コミットの直後にシステムがダウンしても，データを復元できるようにするためです。

bgx5810

基礎から理解するデータベースのしくみ（11）

トランザクションとは何だろう
      

表1●トランザクション処理の分離レベルと，それぞれで発生する可能性がある現象。分離レベルは下に行くほど高くなります [画像のクリックで拡大表示]

図2●Oracleでシリアライザブル分離レベルのトランザクションを実現するための仕組み [画像のクリックで拡大表示]

    マルチユーザー環境では新たな問題が発生　ここまでの説明は基本的に，一人のユーザーがデータベースにアクセスしていることを前提にしていました。しかし実際には，複数のユーザーが同時にデータベースにアクセスすることはよくあります。むしろ，受発注システムや座席予約システムなど，実用データベース・アプリケーションのほとんどは，複数のユーザーが同時に使うことを前提にしていると言ってよいでしょう。こうしたマルチユーザー環境では，ユーザーが一人のときには無かったさまざまな問題が起こります。
　例えば，ユーザー1がトランザクションの途中で特定のレコードの内容を変更したあとで，別のユーザー2がそのレコードを読み込んだとしましょう。そのあとでユーザー1がトランザクションをロールバックしたら，ユーザー2は，誤ったデータを読み込んだことになります。
　あるトランザクションをしているのと別のユーザーが，そのトランザクションでまだコミットしていないデータを読み込んでしまうことを「ダーティ・リード」と呼びます。ダーティ・リードを回避するためには，コミットしていないデータを別のユーザーが読め込めないようにしなければなりません。
　コミットしていないデータを外部から読めないようにしても，まだ問題は起こり得ます。先の例でユーザー2が同じレコードを2度読み込むような場合，1度目と2度目の読み込みの間にユーザー1がトランザクションをコミットすると，1度目に読み込んだ内容と2度目に読み込んだ内容が異なる可能性があります。このように，複数回の読み込みの結果が，ほかのトランザクションのコミットのタイミングによって変わってくることを「反復不可能読み込み（non-repeatable read）」と呼びます。
　加えて，2回の読み込みの間にユーザー1のトランザクションがレコードを追加したり削除したら，2回目の読み込みでは1回目には無かったレコードが現れたり，それまであったレコードが無くなったりすることになります。この現象を「ファントム」と呼びます
分離性と同時実行性はトレードオフ　こうした問題を解決するためにもっとも簡単な方法は，それぞれのユーザーが一つひとつ順番に（シリアルに）実行されるようにすることです。そうすれば，トランザクションが互いに影響を及ぼし合うことはなくなります。しかし，それでは単位時間内に実行できるトランザクションの数が少なくなり，パフォーマンスが低下してしまいます。
　このように，トランザクション間の分離性と同時実行性には，トレードオフの関係があります＊2。そのため現実には，アプリケーションの性格に合わせてトランザクションの分離性と同時実行性のバランスをとらなくてはいけません。
　ANSI/ISO＊3は，トランザクションの分離の度合い（各トランザクションがそれぞれどの程度互いに影響を及ぼし合うか）を表す指標として，（表1[拡大表示]）の四つの「分離レベル」を定義しています。これらは，それぞれ先にあげた「ダーティ・リード」「反復不可能読み込み」「ファントム」の三つの現象が発生するかどうかで区別されます。下にいくほど分離の度合いが高くなり，表の一番上の「未コミット読み込み」ではすべての現象が起こり得ますが，一番下の「シリアライザブル」ではいずれも発生しません。
　多くのRDBMSは複数の分離レベルをサポートしており，トランザクションの開始時などに設定が可能です。例えばSQLServerは表1の四つの分離レベルをすべてサポートしています。一方，Oracleは，コミット済み読み込みとシリアライザブル以外に，更新を行わないトランザクションに使用できる「読取専用」分離レベルを用意しています。いずれのRDBMSも，デフォルトのレベルはコミット済み読み込みです。
ロックがトランザクション分離の基本　トランザクション分離するための基本的な方法は，トランザクションが終了（コミットもしくはロールバック）するまでロックをかけることです。ロックは，あるトランザクションがレコードにアクセスしているときに，別のトランザクションからそのレコードにアクセスできないようにする仕組みです（囲み記事「ロックには2種類ある」を参照）。
　SQLServerの場合で説明しましょう。「コミット済み読み込み」分離レベルでは，トランザクションの途中でデータの更新処理を行うと，その時点で取得したロック（排他ロック）をトランザクションの終わりまで保持します。排他ロックでは，そのレコードに対するほかのトランザクションからの読み書きを，ロックがかかっている間は一切禁止します。これによって，ダーティ・リードを防げます。
　「反復可能読み込み（repeatableread）」分離レベルでは，あるトランザクションがデータを読み込むと，その時点でロック（共有ロック）を取得し，トランザクションが終わるまで保持します。共有ロックでは，ほかのトランザクションはデータを読み込むことはできますが，データを変更することはできません。したがって，最初のトランザクションが終わるまで，データがほかから書き換えられないことが保証され，反復不可能読み込みは発生しません。
　「シリアライザブル」分離レベルを実現するのは少し面倒です。例えば
SELECT * FROM emp
  WHERE empno BETWEEN 10 AND 100といったSQL文に対してファントムが起こらないようにするためには，10から100の間のempnoフィールドを持つレコードを追加したり，削除させないようにしなければなりません。SQL Serverでは，empnoが10～100に対してキー範囲ロック＊4をかけて，ほかのトランザクションがこの間のempnoを持つレコードを追加したり削除できないようにします。
　ここまでの説明でおわかりのように，分離レベルが高くなるほど，保持されるロックが多くなり，同時実行性は低くなります。アプリケーションの分野によりますが，反復不可能読み込みやファントムを禁止する必要があることはそれほどないので，一般にはデフォルトの「コミット済み読み込み」分離レベルをそのまま使うのがお勧めです。反復不可能読み込みを禁止する必要があるなら，該当する部分だけ明示的にロックかけるようにするのが良いでしょう＊5。
　Oracleではどうなっているでしょうか。「コミット済み読み込み」で排他ロックをトランザクションの終わりまで保持する点はSQL Serverと同じですが＊6，「シリアライザブル」を実現する方法は異なります。Oracleでシリアライザブル分離レベルのトランザクションを行う場合には，まずデータを読み込む際にそのデータのSCNを調べます。そして，データの内容がトランザクション開始以降に更新されている場合には，ロールバック・セグメントから更新前のデータを取り出して読み込みます（図2[拡大表示]）。こうすることで，反復不可能読み込みやファントムの発生を回避しているわけです。
　Oracleは，シリアライザブル分離レベルに限らず，常にこのような仕組みで読み込みを行います＊7。そのため，読み込みではロックの必要がありません。つまり，読み込みによってほかのトランザクションの書き込み処理が待機することもなければ，読み込みがほかのトランザクションの書き込みを待つこともないのです。これは同時実行性の点では非常に有利です。半面，ロールバック・セグメントがいっぱいになると，古いデータから順に捨てられてしまうので，短期間に更新を繰り返すような場合に，更新前のデータを読み込めなくなることがあります。そうした場合にOracleは「ORA-1555:スナップショットが古すぎます」というエラーを発生します。このエラーが頻繁に出る場合は，ロールバック・セグメントのサイズを大きくするなどして対処する必要があります。

ロックには2種類ある　ロックは，複数のプロセスがテーブルやレコードなどの各種リソースを利用しようとした際の同時アクセスを制限することで，データの不整合性などが生じないようにするための仕組みです。例えば，あるプロセスがデータ書き出しのためレコードに対してロックを取得すると，ほかのプロセスがそのレコードにデータを書き出そうとしても，ロックが解除されるまで待機することになります。テーブルにアクセスする場合，Oracle，SQLServerのいずれも，デフォルトでレコード単位のロックを行います。
　ロックには，大きく分けて「排他ロック」と「共有ロック」の2種類があります。排他ロックは，レコードのデータを変更するために取得するロックで，一つのレコードに対して一つのプロセスだけが取得できます。OracleやSQLServerでは，あるプロセスがデータを更新する際には自動的に排他ロックを取得します。これによって，データを更新している途中で，ほかのプロセスがデータを読み込んだり，変更できないようになります。
　共有ロックは，リソースに対して同時に複数のプロセスが取得できるロックで，基本的に読み込みの際に利用します。あるプロセスが特定のリソースに対して共有ロックを保持していると，ほかのプロセスはそのリソースに対して共有ロックを取得できますが，排他ロックを取得することはできません。共有ロックでは，それぞれのプロセスはロックされているレコードのデータを変更できませんが，読み込むことは可能です。SQLServerは，データを読み込む際に共有ロックを自動的に取得します。なお，あるプロセスが排他ロックを保持している間，ほかのプロセスは排他ロックも共有ロックも取得できません。
　SQLServerは「更新ロック」と呼ばれるロックも用意しています。更新ロックは働き自体は共有ロックと同じですが，取得できるのは一つのレコードに対して一つのプロセスに限られます。あるプロセスが更新ロックを取得すると，別のプロセスは共有ロックを取得できますが，排他ロックや更新ロックを取得することはできません。主に，あるレコードのデータを読み込んだ後に，排他ロックに切り替えてデータを書き込む，といった用途で使われます。

bgx5810

基礎から理解するデータベースのしくみ（12）

トランザクションとは何だろう
      

図3●口座間の振り込みの処理でデッドロックが起こる様子 [画像のクリックで拡大表示]

図4●図3のSQL文を実行してデッドロックが起こったときのSQL＊Plusの画面 [画像のクリックで拡大表示]

    両すくみで処理が停止することも　ロック機能は複数のユーザーが利用するデータベース・アプリケーションには不可欠なのですが，新たな問題の元にもなります。それは「デッドロック」と呼ばれる現象です。
　先の銀行口座間の振り込みの例で次のような場合を考えてください（図3[拡大表示]）。トランザクション1は，口座番号10の口座から口座番号20の口座に1万円を振り込もうとしています。一方，トランザクション2は，これとは逆に口座番号20の口座から口座番号10の口座に5000円を振り込みます。ここで仮に，トランザクション1が，(1)口座番号10のレコードを変更してから，トランザクション2が(2)口座番号20のレコードを変更したとしましょう。この時点で，トランザクション1は口座番号10のレコードを，トランザクション2は口座番号20のレコードを排他ロックします。これらのレコードは，トランザクションが終了するまでロックされ続けることになります。
　その後，トランザクション1は，口座番号20のレコードを変更しようとしますが，そのレコードにはトランザクション2が排他ロックを掛けているため，待機状態になります。一方，トランザクション2は，口座番号10のレコードを変更しようとしますが，このレコードはトランザクション1が排他ロックを掛けているため，やはり待機状態になってしまいます。
　このように二つのトランザクションが両すくみの状態になってしまうと，もはやこれ以上処理が進むことはありません。トランザクション1がレコード20のロックを取得するためには，トランザクション2が終了しなければなりません。しかし，トランザクション2が終了するためには，トランザクション1が終了してレコード10のロックが解除される必要があるからです。
　二つのトランザクションが，互いに相手の所有するロックが解除されるのを待機して処理が進まなくなる状態をデッドロックと言います。デッドロックは，必ずしもトランザクションが関係しなくても，複数の処理が同時に実行されている状態では発生する可能性があります。ただし，トランザクションがあるとロックの期間が長くなりがちなため，発生しやすいと言えるでしょう。
　いったんデッドロックに陥ったトランザクションは永久に待ち状態になってしまい，外部からの介入なしには抜け出すことができません。そこで多くのRDBMSは，デッドロックを自動的に検出して解決する仕組みを備えています。こうしたRDBMSは，ロックを待機しているプロセス＊8のリストを調べてループ状態になっていないかどうかをチェックしたり，タイムアウト（時間切れ）を利用してデッドロックを検出します。
　デッドロックに陥っているトランザクションがわかれば，その一方に対して待機中のSQL文を強制的に失敗させて，待機状態から抜け出させます。その後，そのプロセスがトランザクションをロールバックしてロックを解放すれば，もう一方のプロセスはロックを取得して処理を再開できるというわけです。
　実験をしてみましょう。Oracleの付属ツールSQL＊Plusを二つ起動し，一方に図3のトランザクション1のSQL文を，もう一方にトランザクション2のSQL文を(1)～(4)の順に入力してみてください＊9。二つのウィンドウがしばらく入力を受け付けなくなるはずです。
　でも，ご心配なく。しばらくすると，一方に「ORA-00060: リソース待機の間にデッドロックが検出されました。」というメッセージが表示されます（図4[拡大表示]）。ここでROLLBACKと入力して処理を中断すれば，もう一方のウィンドウの処理が再開されて正常に終了します。
デッドロックが起こらないようにする　デッドロックが発生すると，長い待ち時間が生じるうえにロールバックによるコストもかさみます。したがって，デッドロックはできるだけ発生しないようにしなければなりません。そのためにはまず，一つのトランザクションに要する時間をできるだけ短くするのが基本です。先に書いたように，いったん排他ロックを取得したプロセスは，トランザクションが終了するまでロックを保持し続けます。トランザクションが長ければ長いほどロックしている期間は長くなり，それだけデッドロックが発生する可能性は高くなります。
　特に，トランザクションの途中でユーザー入力を待つようなことはできるだけ避けるべきでしょう。一般にユーザー入力はコンピュータが行う処理と比較してはるかに時間がかかるからです。ユーザーが入力の途中で昼食に出掛けてしまうかもしれません。その場合は，何10分もロックが保持されることになります＊10。
　複数のテーブルをアクセスする処理がアプリケーションのいたるところに現れるような場合は，アクセスする（ロックを取得する）テーブルの順序を同じにしておく，というのも効果があります。例えば，マスター・テーブルと明細テーブルに連続してアクセスすることが多ければ，「アクセスはマスター・テーブル→明細テーブルの順に行う」と決めておくわけです。図3の例からわかるように，デッドロックの多くは二つのプロセスが複数のリソース（図3では口座番号10と20のレコード）を逆の順序でロックしようとすることから生じます。順序を決めておけば，こうしたデッドロックは発生しなくなります。
☆　　　　　　　　　　　　☆　　　　　　　　　　　　☆
　RDBMSはここで説明したほかにも，さまざまな機能を備えています。例えば，分散している複数のデータベースを更新する場合には，互いの内容の整合性を確保するため「2フェーズ・コミット」という機能を利用します＊11。RDBMSのすべての仕組みを一度に理解する必要はありませんが，折に触れて「この機能はどういうしくみで実現されているのか」ということを調べてみてはいかがでしょうか。