ランダムインサートと昇順インサート
概要
MySQL、InnoDBのお話です。INSERT文を実行するとインデックスにエントリが追加されてリーフブロックがうんぬんな話です。
インデックスが存在するテーブルへのINSERTは、実レコード+インデックスのリーフブロックにエントリが追加されます。
今回の記事はランダムインサートよりも昇順インサートのほうが効率的というお話です。
リーフブロックの追加
ランダムインサートの場合
まずはランダムインサートについて考えます。
リーフブロックに保存されるデータは原則インデックスの値がソートされています。
たとえば次のようなリーフブロックがあるとします。
my $data = { # key => primary 1 => 100, 2 => 5, 3 => 40 , ... 60 => 1000, };
インデックスはソートされて並んでいます。例えば次のようなSELECT文が発行されたとします。
SELECT * FROM tbl WHERE indexKey < 20;
indexKeyが順番に並んでいる事によって20を超えるレコードはスキャンしなくても済みます。このためインデクスをソートして並べたいのですが、INSERT時にこの状態を保つために少しコストがかかります。
このリーフブロックが60対のデータで満杯になっているとします。この状態でさらに1対のエントリを追加すると、このリーフブロックが2分割されます。
my $data1 = { 1 => 100, 2 => 5, 3 => 40 , ... 30 => 60, }; my $data2 = { 31 => 1001, # 新たに追加 ... 60 => 1000, };
満杯のリーフブロックはこのような感じで分割する事によってインデックスの値を並べています。このためランダムインサートを繰り返していると、まだ空きがある、完全には使用されていないリーフブロックが大量に発生したりします。
昇順INSERTの場合
テーブルを設計する際に、created_atというカラムをつける事がよくあると思います。このcreated_atがインデックスとして指定されている場合、次のようなリーフブロックが生成されます。
my $data = { 2010-07-26 16:50:00 => 1, 2010-07-26 16:50:01 => 2, 2010-07-26 16:50:02 => 3, 2010-07-26 16:50:03 => 4, ... };
見てわかる通り昇順になっています。この場合、61個目のエントリを追加した場合は次のようになります。
my $data1 = { 2010-07-26 16:50:00 => 1, 2010-07-26 16:50:01 => 2, 2010-07-26 16:50:02 => 3, 2010-07-26 16:50:03 => 4, ... 2010-07-26 17:00:00 => 60, }; my $data1 = { 2010-07-26 17:00:01 => 61, };
既に順番になっているのでリーフブロックを分割しなくてもインデクスの値が昇順になっています。この状態でリーフブロックが追加される状態は昇順INSERTです。
昇順インサートは、ランダムインサートに比べると格段にリーフブロックの使用効率が良いのです。