LINEAR HASHパーティショニングってなんだ？

MySQL 5.1から利用出来るパーティショニングの種類には、次の4つがある。

• RANGEパーティショニング
• LISTパーティショニング
• [LINEAR] HASHパーティショニング
• [LINEAR] KEYパーティショニング

RANGEパーティショニングは値の範囲を指定する。次のように日付を用いて範囲を指定するのが代表的な使い方だ。詳細はこちらの記事（パーティショニングの使用例 - http session情報）を見て欲しい。

mysql> CREATE TABLE http_session (
-> session_id VARCHAR(32) NOT NULL,
-> last_access TIMESTAMP NOT NULL,
-> created TIMESTAMP NOT NULL,
-> t_session_data VARCHAR(1024)
-> ...(中略)...
-> PRIMARY KEY (session_id, last_access))
-> ENGINE InnoDB
-> PARTITION BY RANGE (TO_DAYS(last_access)) (
-> PARTITION p000001 VALUES LESS THAN (TO_DAYS('2009-04-01')),
-> PARTITION p000002 VALUES LESS THAN (TO_DAYS('2009-04-02')),
-> ...(中略)...
-> PARTITION p000020 VALUES LESS THAN (TO_DAYS('2009-04-20')),
-> PARTITION pmax VALUES LESS THAN MAXVALUE
-> );

2012/02/02追記
このCREATE TABLE文はMySQL 5.1.43以降のバージョンではエラーになるので注意。詳細はリリースノートを参照のこと。TO_DAYSの代わりにUNIX_TIMESTAMPを使いましょう。（指摘サンクスです。）

LISTパーティショニングはパーティショニングに使用するカラムの値がいくつかしかない場合に利用できる。例えばDBT-2ベンチマークで利用するcustomerテーブルを次のようにパーティショニングできるだろう。

mysql> ALTER TABLE customer DROP PRIMARY KEY, ADD PRIMARY KEY (c_id, c_w_id);
mysql> ALTER TABLE customer PARTITION BY LIST (c_w_id) (
-> PARTITION p1 VALUES IN (0, 1, 2, 3),
-> PARTITION p2 VALUES IN (4, 5, 6, 7)
... 略（warehouseの数だけ続く） ...
-> );

HASHパーティショニングとKEYパーティショニングは次のように利用出来る。

mysql> ALTER TABLE Country PARTITION BY HASH (ContinentId) PARTITIONS 7;

HASHパーティショニングは行が格納されるパーティションを算出するのにMOD（剰余）を利用し、KEYパーティショニングはPASSWORD()関数を使ってハッシュ値を算出する。PASSWORD関数を利用するので、文字列に対しても利用することが出来る。文字列のカラムを使ってパーティショニング出来るのは、KEYパーティショニングだけである。他のパーティショニング手法では、必ず整数値を用いなければならない。

さて、ようやくここからが本題である。（前置きなげーよ！＞俺）

LINEAR HASHとはいかなるものだろうか。一応マニュアルににも説明はあるが、いまいち容量を得ない。LINEAR HASHには利点と欠点があり、適切に利用すればとてもメリットがある手法なので「使い方が分からないので使わない」のでは勿体ない。というわけで今日はLINEAR HASHについて解説しようと思う。

パーティショニングの定義はLINEAR HASHというキーワードを用いること以外、HASHパーティショニングと変わらない。例えば次のように定義することができる。

mysql> ALTER TABLE some_table PARTITION BY LINEAR HASH (col) PARTITIONS 10;

だが、行を格納するパーティションの算出方法が決定的に違う。MODではなく次のように論理積を使ったアルゴリズムを用いているので計算が非常に速いのである。

1. パーティション数Nより大きいか同じものの中で、最小の2の累乗Vを求める。上記の例では、V（10より大きいか同じものの中で最小の2の累乗）は16である。
   
   
2. 次の式でパーティションを求める。
   
   p = col & (V - 1)
   
   例えばcolが20の場合、20 & (16-1) = b'10100' & b'1111' = b'100' = 4 である。
   
   
3. もし求められた値がパーティション数Nより大きいか同じ場合は、さらに次の式でパーティションを算出する。
   
   p' = p & (V/2 - 1)
   
   例えばcolが30の場合、30 & (16 - 1) = b'11110' & b'1111' = b'1110' = 14となり、これはパーティション数Nよりも大きい。従って、さらに 14 & (16/2 - 1) = 14 & 7 = b'1110' & b'111' = b'110' = 6という具合にパーティションを求めるわけである。

LINEAR HASHパーティショニングでは、各パーティションに格納される行数に偏りが出てしまう。上記の例では、最初の式で求められた値が10より大きいか同じ場合はさらに再計算されて0〜7の8つのパーティションに格納されることになるので、残りのパーティション8および9に格納される行数は少なくなってしまう。このようなことが起こらないようにするには、パーティション数を2の累乗、つまり2、4、8、16、32、64、128、256、512、1024のいずれかにすれば良い。そうすればパーティションを求める計算も一度で済むから高速である。

LINEAR HASHの利点は、HASHよりも計算が高速な点である。テーブルが大規模な場合には、HASHではなくLINEAR HASHの利用を検討するといいだろう。

LINEAR KEYパーティショニングは、PASSOWRD()関数で求められたハッシュ値に対して、さらに上記のアルゴリズムを用いてパーティションを算出する手法である。こちらもテーブルが大規模な場合に利用を検討するといい。

まとめ

LINEAR HASHパーティショニングのアルゴリズムは剰余ではなく論理積を用いるため非常に高速である。テーブルが大きい場合にはHASH/KEYではなくLINEAR HASH/LINEAR KEYパーティショニングを利用すること。ただしパーティション数は2の累乗で！