INDEX概論
そもそも、INDEXって何よ？
要するに読んで字の如く「索引」である。
住所録の羅列で、特定の住所を探すのに頭から探すよりも、索引から名前を探してきたほうがずっと早い。
これと同じ事をDB上で可能にするのがINDEXである。
普通にSQLを走らせた場合
例：住所録(phone_book)から名前(last_name)がHogeさんを探したい場合
SELECT * FROM phone_book WHERE last_name = 'Hoge'
↓
Hogeさんのデータが出力される
- とりあえず、簡単なSELECT文で欲しい情報が正確に手に入る
- とりあえず、RBDMSというブラックボックス内でわずらわしい処理は全てやってくれる
一見、問題が無いように見える。
しかしRDBMS(リレーショナルデータベース管理システム)では以下のように動いている。
- phone_bookテーブル内のレコードを全て取ってくる
- last_nameフィールドを調べ、文字列「Hoge」に一致するか１件ずつ検証する
- あれば出力
この方法で希望通りの結果を出力することができなくはないが、とても非効率的。
これでも、レコードが少なければ特に気にならないが…
- レコード数が多い大規模なテーブル
- 多量のアクセスを捌く必要があると思われるDB
になると話は別だ。
対象が１０００件、１万件になれば特定のレコードを見つけるための処理が増えるため、必然的に無視できない負担になる。
これをO(n)問題と呼ぶ。（テーブル内のレコード数をnとすると、特定のレコードを見つけるための検索に要する処理量(オーダー)がレコードnに比例すること）
この問題を解決するには、本のようにレコードの場所を示す値で目次や索引(index)を作り、検索にかかる処理を節約する方法がある。
INDEXを付ける理由
クエリの実行結果から、可能性のある行を効率的に出力するため
→電話帳から「佐藤さん」を探し出す場合、
頭から探すよりも、索引（インデックス）から佐藤さんがいる可能性の高い
「さ行のページ範囲」を探してそこから漁ったほうが格段に早い
小規模データベースなら、INDEXなんて気にしないでいいかもしれないが、何十人、何百人も同時に接続し、頻繁なDBアクセスが行われ、レコードが膨大にあるような大規模なシステムの場合、当然負荷軽減を考慮する上でINDEXは無視できない問題になる。
では、全てにINDEXを付けるのが有効か？
RDBMS側はインデックスを別のリストで保管するため、データに変化がある度にインデックスを更新する必要がある。
故に、書き込み速度の低下と容量の増加を招くため、データの全てのカラムにインデックスを付けるのは逆効果である。
INDEXを付けるべき事例
- 関連を張っている場合（関連元から飛んでくる可能性がある）
- 関連を張っていなくても、頻繁にそのキーを元に検索をかける可能性が高い場合
容量を抑えたINDEXを作る方法
例：最初の4バイトにのみインデックスをつける
ALTER TABLE phone_book ADD INDEX (last_name(4))
これでインデックスの容量を抑えたインデックスができるが、同じインデックスを持つレコードが発生する場合がある。
例：「Sasaki」と「Sasaoka」の２つに4バイトの部分的インデックスを貼ると、同じインデックス(Sasa)になる。
ユニークインデックス
ネトゲのプレイヤー名、会員サイトのID、メールアドレスなど、
「そのテーブル内に１つしか存在しないはず」
の固有のデータがある場合に便利
- 検索だけでなく、挿入・更新時にも同じ値が存在しないことを確認できる。ダブるとMySQLエラーが出る。
- MySQLではADD UNIQUEを付けることで利用可能
INDEXとその種類
B木構造
- 走攻守のバランスの取れたスグレモノ。まさにDB界の松井稼頭夫である。
- 余程のマニアックな事情がない限りこれが無難
- 特定のデータをヘッダ→ブランチ→リーフの順番で追いかけることで、効率的な検索ができる
例えばHARRISさんを探す場合は
A-K L-Z(ヘッダ)
↓A-Kだな
A-D E-G H-K(ブランチ)
↓H-Kだな
HARRIS JOKER KANE(リーフ)
↓HARRIS
あったー(^○^)
と三段構えで索引を引くように効率良く探す。
ハッシュインデックス構造
- B木構造では、ヘッダ、ブランチ、リーフと何度もアクセスが必要になる
- これを１回でできるようにしたのがハッシュインデックス
- ハッシュ関数を使い、検索に使うキーとレコードを含むページを直接関連付ける
- B木と違い、範囲検索はできない
- RDBMSによっては、リファレンスで「ハッシュインデックスは推奨しない」とはっきり書いていることがある。
R木構造
- B木に似たデータ構造
- 空間データ、n次元データの扱いに用いられる
- 地図アプリや、地球科学で使われる
- 「現在地点から５００メートル圏内のラーメン店を探す」などの扱い方に向いている
- よくわかんないから調べる
インデックスがどう使われるか
MySQL上でEXPLAINを使うと、より早くレコードを検索するSELECTを得るために、
どの時どのテーブルにインデックスを追加しなければならないかを確認できる。
EXPLAIN <<table_name>>
もしくは
EXPLAIN SELECT <<select_options>>
SHOW INDEXES FROM <<table_name>>
でインデックスが付いているか確認できる
EXPLAINとは
INDEXが使われる時
- フィールド値を定数と比較する時(WHERE name == "Hoge")
- フィールド値全体でJOINする時(WHERE a.name = b.name)
- フィールド値の範囲を求める時
- LIKE(あいまい検索)で文字列の先頭が固定な時
- MIN(), MAX()
- OEDER BY, GROUP BY
- WHEREの全てのフィールドがindexの一部の場合
INDEXが使われない時
- LIKE(あいまい検索)がワイルドカードで始まるとき
- RDBMSがDB全体を読んだほうが早いと判断し、DB全体を読んだ場合
- 通常、indexはORDER BYに使われない
- WHEREとORDER BYのフィールドが違うときはどちらかしか使われない
MySQLのコマンド
SHOW INDEX;
SHOW INDEX コマンドよりインデックスを確認できる。「Key_name」のフィールドにインデックス名が、「Column_name」のフィールドにインデックスがつけられてるフィールド名が表示される。
mysql> SHOW INDEX FROM show_index_tbl;
+----------------+------------+----------+--------------+-------------+-----------+-------------
| Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality
+----------------+------------+----------+--------------+-------------+-----------+-------------
| show_index_tbl | 0 | PRIMARY | 1 | id | A | 0
| show_index_tbl | 1 | name_idx | 1 | name | A | NULL
| show_index_tbl | 1 | zip_idx | 1 | zip | A | NULL
+----------------+------------+----------+--------------+-------------+-----------+-------------
+----------+--------+------+------------+---------+
| Sub_part | Packed | Null | Index_type | Comment |
+----------+--------+------+------------+---------+
| NULL | NULL | | BTREE | NULL |
| NULL | NULL | YES | BTREE | NULL |
| NULL | NULL | YES | BTREE | NULL |
+----------+--------+------+------------+---------+
DESC <<table_name>>;
カラム表示
デッドロック
デッドロックとその処方箋
俺: デッドロックってどうやったら回避できるん…
レコードA,B,C,Dってあって、複数のプロセスがそれらをちょくちょく更新するときにデッドロックが起こると思うんだけど
例えば、ホテルビュッフェのようなトコロで、各々が好きな料理を勝手に取ろうとしてその料理にあるトングを持って料理をとって、
他の料理へ行くときに、他の料理のトングを持ってる人がそれを手放すまで待ってる
他の料理の人も、自分がトングを手放すのを待ってる
ていうのがまさしくデッドロックだと思うんだが
例えば、これって、順路を作って、料理を取る・取らないにも関わらず左端の隅っこからみんな並んで右へ行くようにすれば解決するじゃん
上記のビュッフェの例えのように、レコードA,B,C,Dからプロセスが勝手につまんで更新したりとかするよりも、
どんなプロセスでも、必ず更新するしないに関わらずレコードA→B→C→Dの順番で拾うようにするってやれば解決するのかな
セオリーとかあるの？
Y: レコードA,B,C,Dまで読んだ
俺: えー
俺: 要は、皆がわーって集まって好き勝手に料理を取るような状況を綺麗に整理するにはどうしたらいい？って話
S: まず、２つのレコードの相互の解放待ちじゃないことは確実なの？
俺: んと、まず原因からしてわからん
どのテーブルで起こったかはわかるんだが、どのレコードで起こったかがわからない
俺: １つのサーバで５つの非同期処理(delayed_job)のプロセスが走ってて、それらがそれぞれであるタスクを処理して、その結果をDBに出力するんだけど
俺: deadlockを出した時の、他のプロセスの状況がわからないのでなんとも。
S: 原因わかってないんだったら対処しようがないじゃん
俺: まあ確かに
俺: というか、そもそも
２つのレコードの相互の解放待ち
これじゃないdeadlockってあるの
S: まず「この状況で原因ってどうやったら調べられるの？」が先にくる疑問だと思うんだけど
俺: まあ確かに: む、たしかに
S: 相互のロック解放待ちだったらロック取るのを一個のメソッドにしてそれ必ず叩くようにすれば順番逆にロックしてデッドロックになることもないと思うけど
S: どーなんすかねJさん
J: デッドロック難しいんですよね…
俺: むー
J: リトライで何とか出来る範囲ならリトライで逃げる
ダメなら直列化するしかないですけど見つけるのも難しい…
俺: 現状はtransactionで巻き戻って、(delayed_jobの)リトライで回避できてるので放置しても問題ないんだよね
でも、気持ち悪い
俺: 直列化っていうのは、つまりは上記のビュッフェの下り？
J: そうですね、順番通りなら大丈夫なはず
J:
http://dev.mysql.com/doc/refman/5.1/ja/innodb-deadlocks.html
デッドロックはトランザクション データベースの中ではよく知られている問題ですが、
ある特定のトランザクションを全く起動できないほど頻繁に起きる訳ではないのならば危険では有りません。
通常は、トランザクションがデッドロックの為にロールバックされたらそれを再発行できる準備が常にできているように、
アプリケーションを書き込まなければいけません。
俺: デッドロックを絶対に起こさないという努力よりも、(たまに)デッドロックしても影響が無いようにする努力をせよ…ってことか
マルチプロセスと身に覚えがないデッドロック
「innodb_file_per_table」とは何か(Amazon RDS)
innodb_file_per_tableはMySQLが内部で使っているデータベース形式、innodbのデータを
データベースごとに1ファイルにするか、データベースのテーブル毎に1ファイルにするかの設定
0（無効）
メリット
RDSのフェイルオーバーやスナップショット取得が早い（らしい）
デメリット
Undo領域（トランザクション時に拡張される領域）がどんどん膨れたとき
DBをダンプして全部ドロップして書き戻す、とやらないと容量は元に戻らない
1（有効、デフォルト）
メリット
テーブルをdropしたときに、Undo領域も消去されるので容量問題に対処しやすい
デメリット
RDSのフェイルオーバーやスナップショット取得が重い（らしい）
※テーブルの入れ替えが激しい場合はこっちがいいかも。
A: ぱっと見 1 の方が利点大きいね
B: 1にしないとディスクI/Oは増えるんじゃ？
A: ディスクI/Oは増えないだろ。。増えるのは容量で、しかも削除が難しくなるのが問題なだけ
C: 複数のテーブルにまたがってアクセスあるときには1ファイルにログがまとまっているほうが早いかもです
A: かもレベルならあんまり怖くないかも？
AWSでは
You should set the innodb_file_per_table parameter to 0 when you have a large number of tables, such as over 1000 tables when you use standard storage or over 10,000 tables when you use Provisioned IOPS storage.
(多くの数のテーブルを抱えている…要はスタンダードストレージで1000以上、もしくは10000以上のテーブルをプロビジョンIOPSストレージで抱えている場合は、innodb_file_per_tableを0にしたほうがいいだろうね。)
参考資料
参考資料
最終更新：2013年07月23日 18:18
