InnoDBのclustered indexはあまり役に立ってないんじゃないのか

MySQL よくわからないこと


縁あって仕事でMySQLを使いそうなので、いまのMySQLがどうなっているのか少しずつ調べている。
で、現在のデフォルトストレージエンジンであるInnoDBの設計思想に困惑している。
InnoDBは主キーを強制的にclustered indexにするとのことだが、それって何の役に立つのだろうか？

何のためのclustered indexか？

clustered indexの利点は

  • 一般のb-tree indexに比べて、range scanが圧倒的に速い*1
  • 大量データ同士を最速で結合する「ソートなしMerge Join」が使える

の2点だ*2。
これらの利点の代償として

  • 行長を拡大するような更新が多発するとスキャンが徐々に遅くなっていく
  • 主キー値が昇順になるようにinsertしないとスキャンが徐々に遅くなっていく
  • ROWIDが存在しないので、セカンダリインデックスを経由するデータアクセスの効率が悪い*3

といった問題を受け入れるわけだ。
しかし、以下の理由によりInnoDBではrange scanや結合の高速化はあまり期待できない。

1. InnoDBではrange scanしたいキーにclustered indexを張ることができない

受注ヘッダテーブル 

{ 受注ID(PK), 受注日, 顧客番号, 合計金額 }

がInnoDB上にあって、受注IDには整数の連番が設定されているとする。
InnoDBは主キーである受注IDについてclustered indexを構築するが、無意味な連番である受注IDを範囲検索(=range scan)するアプリケーションは多分ないだろう。
いっぽう「1月1日から12月31日までの顧客ごとの合計金額を算出する」など、受注日でrange scanしたいケースは多々あるが、clustered indexは主キーである受注IDが占有済みなので、受注日にはセカンダリインデックスを張ることしかできない。よって、セカンダリインデックスのrange scan＆主キー値による低速なランダムアクセスをするか、clustered indexの全件スキャンをするか、どちらかで処理せざるを得ない*4。

2. MySQLはソートなしMerge Joinを実行できない

SQL ServerもInnoDB同様、主キーをデフォルトでclustered indexにする仕様だ。
SQL ServerのサンプルDB AdventureWorks の受注ヘッダ・受注明細テーブル

SalesOrderHeader　{ SalesOrderID(PK), ... }
SalesOrderDetail  { SalesOrderID(PK), SalesOrderDetailID(PK), ... }

をSalesOrderIDで結合するときの実行計画を見ると、結合方式はMerge Joinだが、マージの前にソートをしていない。これは、ヘッダ・明細ともに主キーがclustered indexになっているため、両テーブルをclustered index scanすればソートなしで即結合できるためだ。

この「ソートなしMerge Join」は、大型のテーブル同士を結合するための最速の結合方式だ。両方のテーブルにclustered indexがあるなら、結合はぜひ「ソートなしMerge Join」で行いたい。
ところがMySQLはマージ結合アルゴリズムを搭載していないので、テーブルにclustered indexがあっても「ソートなしMerge Join」することができない。
MySQLが持っている結合アルゴリズムはNested Loop JoinとBlock Nested Loop Joinであり、前者は大量のランダムアクセス、後者は内部表の複数回のスキャンが足かせとなって、ソートなしMerge Joinほどのパフォーマンスを出すことはできない。

InnoDBに適した用途とは？

以上のことから、InnoDBを採用しているがclustered indexを有効利用できず、そのコストだけ負担しているシステムが多々あるものと推測する。
InnoDBが広く使われている理由は他に選択肢がなかったからで、インデックス/テーブル分離型のMVCCなストレージエンジンの開発が進めば(PBXTとかFalconがそうなのですよね)、InnoDBの出番は減って行くだろう。


...と考える前提として、

  • clustered indexはrange scanと結合を高速化するための特殊なインデックスであって、諸々のデメリットのために汎用性に欠ける
  • range scanや結合を高速化できないのであれば、clustered indexは使わないほうがよい

と思っているのだがどうか。SQL Serverなどは何でもclustered indexにしようとするが、あっちの陣営が正しいのか。


仮に「clustered indexの汎用性に問題はない。主キーは常にclustered indexにすべきだ」ということであれば、clustered indexをサポートする他のDBMS(Oracleなど)でも、主キーをclustered indexにするのがベストプラクティスということになる。そうでないならば、主キーがclustered indexになってしまうInnoDBは用途を限定すべしということになる。その限定された用途とは何か？MySQLユーザ界隈ではどのように言われているのか？

*1:「一般のb-tree index」がcovering indexになっている場合を除く

*2:この他に「一般のb-tree indexに比べて、ROWIDでの行のlookupを省略できるので、index seekが速い」という利点があるが、これは「もともと非常に速いものが、もっと速くなる」話なので、clustered indexのおかげで性能問題をクリアできた！という経験をすることはないだろう。そんな経験があったらおめでとうございます

*3:これは実装による。Oracleの場合、clustered indexにもPhysical Guessと呼ばれるROWID的なものが格納されているのだそうだ

*4:逃げ道がないわけではない。{ 受注日, 受注ID }で複合インデックスを作成してうまいことやれば受注IDのrange scanに誘導できるだろう。別にエントリを立てて検証する予定