2012年12月18日

PostgreSQLのストレージアーキテクチャ(HOT編)

PostgreSQL Advent Calendar 2012(全部俺)のDay 18です。

前回のエントリでは、PostgreSQLのストレージアーキテクチャのうち、特にPage Pruningについて実際の動作状況を見ながら、その仕組みを解説しました。

ここまではテーブルのみの解説をしてきましたが、実際には(ほとんどのテーブルには)インデックスもありますので、レコードを更新する場合にはインデックスについてのケアも必要になります。

というわけで、今回はレコードに対する更新が行われている間に、インデックスがどのように動作しているのかを、具体的な動作例を交えて見てみます。

■インデックスの内部構造


B-Treeのリーフノードの内部構造は以下のようになっています。


前々回のストレージアーキテクチャの基本編で、pageinspectというcontribモジュールを紹介しました。

pageinsectモジュールで提供されているheap_page_items()関数でテーブルのブロック内部の状態を見ることができたわけですが、インデックス(B-Treeインデックス)についてもbt_page_items()という同様の関数があり、この関数を使うことによって、B-Treeインデックスのリーフノードのブロック内部の状態を見ることができます。
testdb=# INSERT INTO t1 VALUES ( 101, 'insert 1' );
INSERT 0 1
testdb=# 
testdb=# SELECT * FROM bt_page_items('t1_pkey', 1);
 itemoffset | ctid  | itemlen | nulls | vars |    data
------------+-------+---------+-------+------+-------------
          1 | (0,1) |      12 | f     | f    | 65 00 00 00
(1 row)

testdb=#
ここで確認しておいていただきたいのは、ctidカラムとdataカラムです。

dataカラムはインデックスのキーの値で、直前にプライマリキーとして「101」という値をINSERTしていますので、dataカラムのデータが16進数で「65」、10進数で「101」となっています。


上記の図の通り、インデックスは該当するレコードへのポインタを保持しているのですが、具体的にはこのctidカラムがインデックスエントリに対応するポインタ情報になります。

ここでは、ctidが「(0,1)」となっていますが、これは「テーブルファイルの0番目のブロックのラインポインタ1番目に位置している」ということを意味しています。

■インデックスとレコードの関連付け


それでは、本当にブロック0のラインポインタ1番目にレコードが存在しているかを見てみましょう。
testdb=# SELECT lp,lp_off,lp_flags,lp_len,t_xmin,t_xmax FROM heap_page_items(get_raw_page('t1', 0));
 lp | lp_off | lp_flags | lp_len | t_xmin | t_xmax
----+--------+----------+--------+--------+--------
  1 |   7880 |        1 |    309 |  43737 |      0
(1 row)

testdb=#
見てみると、確かに0番ブロックの1番目のラインポインタにレコードが存在していました。

このように、インデックスとテーブルのレコードは、ctidという「ポインタ」を介してつながっているのです。

■レコードに対する更新処理(HOT Update)


それでは、前回と同じように同一のレコードに更新処理を行いながら、「テーブルブロックの内部」と「インデックスブロックの内部」がどのように変化していくかを見てみましょう。

まず、1件目のレコードをINSERTすると以下のようになります。
testdb=# INSERT INTO t1 VALUES ( 101, 'insert 1                                                                                                                                                                                                                                                                             ' );
INSERT 0 1
testdb=# SELECT lp,lp_off,lp_flags,lp_len,t_xmin,t_xmax FROM heap_page_items(get_raw_page('t1', 0));
 lp | lp_off | lp_flags | lp_len | t_xmin | t_xmax
----+--------+----------+--------+--------+--------
  1 |   7880 |        1 |    309 |  42731 |      0
(1 row)

testdb=# select * from bt_page_items('t1_pkey', 1);
 itemoffset | ctid  | itemlen | nulls | vars |    data
------------+-------+---------+-------+------+-------------
          1 | (0,1) |      12 | f     | f    | 65 00 00 00
(1 row)

testdb=# 
テーブルブロックおよびインデックスブロック双方にアイテムが1件挿入されていることが分かります。

次に、このレコードに対して更新処理を行い、同じようにテーブルブロックとインデックスブロックの内部の状態を見てみます。
testdb=# UPDATE t1 SET uname = 'update 0-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------' WHERE uid=101;
UPDATE 1
testdb=# SELECT lp,lp_off,lp_flags,lp_len,t_xmin,t_xmax FROM heap_page_items(get_raw_page('t1', 0));
 lp | lp_off | lp_flags | lp_len | t_xmin | t_xmax
----+--------+----------+--------+--------+--------
  1 |   7880 |        1 |    309 |  42731 |  42732
  2 |   7568 |        1 |    309 |  42732 |      0
(2 rows)

testdb=# select * from bt_page_items('t1_pkey', 1);
 itemoffset | ctid  | itemlen | nulls | vars |    data
------------+-------+---------+-------+------+-------------
          1 | (0,1) |      12 | f     | f    | 65 00 00 00
(1 row)

testdb=#
今度は、テーブルブロックの方は古いレコードが削除され、新しいレコードが追記されていることが分かりますが、一方でインデックスのブロックの方はエントリが増えていません。

これが「HOT: Heap Only Tuple」と呼ばれる仕組みで、インデックスのキーが更新されない限り、テーブルのタプルは増えていってもインデックスのエントリは増加しないことになります。

これが、追記型のストレージアーキテクチャの弱点をカバーするための工夫のひとつであり、このような更新処理を「HOT Update」と呼びます。

上記の状態で、インデックスのキーから(最新の)レコードを取得する場合、
  • インデックスキー(dataカラムの値)からレコードの位置(ctidカラムの値)を取得
  • ctidカラムから読みだしたテーブル内の位置のレコード(lp==1)を取得
  • 当該レコードは削除済(t_xmax==42732)のため、t_xmaxとt_xminのチェーンを辿ってlp==2のレコードを見つける
  • lp==2はまだ削除されていない(t_xmaxが空)レコードなので、これを使う
という流れになります。

なお、HOT Updateが有効になるのは「インデックスの張られていないカラムを更新する場合」であり、インデックスのあるカラムを更新するとHOT Updateとなりませんのでその点は注意が必要です。

■Page Pruning処理とインデックス


それでは、前回見たようなブロックの空き領域が少なくなってPage Pruning処理が行われた場合、インデックスとテーブルレコードの状態はどうなるのでしょうか。実際に動作させて見てみましょう。
 lp | lp_off | lp_flags | lp_len | t_xmin | t_xmax
----+--------+----------+--------+--------+--------
  1 |   7880 |        1 |    309 |  42731 |  42732
  2 |   7568 |        1 |    309 |  42732 |  42733
  3 |   7256 |        1 |    309 |  42733 |  42734
  4 |   6944 |        1 |    309 |  42734 |  42735
  5 |   6632 |        1 |    309 |  42735 |  42736
  6 |   6320 |        1 |    309 |  42736 |  42737
  7 |   6008 |        1 |    309 |  42737 |  42738
  8 |   5696 |        1 |    309 |  42738 |  42739
  9 |   5384 |        1 |    309 |  42739 |  42740
 10 |   5072 |        1 |    309 |  42740 |  42741
 11 |   4760 |        1 |    309 |  42741 |  42742
 12 |   4448 |        1 |    310 |  42742 |  42743
 13 |   4136 |        1 |    310 |  42743 |  42744
 14 |   3824 |        1 |    310 |  42744 |  42745
 15 |   3512 |        1 |    310 |  42745 |  42746
 16 |   3200 |        1 |    310 |  42746 |  42747
 17 |   2888 |        1 |    310 |  42747 |  42748
 18 |   2576 |        1 |    310 |  42748 |  42749
 19 |   2264 |        1 |    310 |  42749 |  42750
 20 |   1952 |        1 |    310 |  42750 |  42751
 21 |   1640 |        1 |    310 |  42751 |  42752
 22 |   1328 |        1 |    310 |  42752 |  42753
 23 |   1016 |        1 |    310 |  42753 |  42754
 24 |    704 |        1 |    310 |  42754 |      0
(24 rows)
上記が、Page Pruning処理が起こる直前のテーブルブロックの状態です。更新のチェーンが長くなっていることが分かります。
 itemoffset | ctid  | itemlen | nulls | vars |    data
------------+-------+---------+-------+------+-------------
          1 | (0,1) |      12 | f     | f    | 65 00 00 00
(1 row)
一方、上記がインデックスの状態です。テーブルのレコードが何度も更新されているにも関わらず、インデックスエントリは最初に作成したものから変わっていない(更新されていない)ことが分かります。

この状態でレコードのUPDATEを行うと、Page Pruning処理が実行されます。
 lp | lp_off | lp_flags | lp_len | t_xmin | t_xmax
----+--------+----------+--------+--------+--------
  1 |     24 |        2 |      0 |        |
  2 |   7568 |        1 |    310 |  42755 |      0
  3 |      0 |        0 |      0 |        |
  4 |      0 |        0 |      0 |        |
  5 |      0 |        0 |      0 |        |
  6 |      0 |        0 |      0 |        |
  7 |      0 |        0 |      0 |        |
  8 |      0 |        0 |      0 |        |
  9 |      0 |        0 |      0 |        |
 10 |      0 |        0 |      0 |        |
 11 |      0 |        0 |      0 |        |
 12 |      0 |        0 |      0 |        |
 13 |      0 |        0 |      0 |        |
 14 |      0 |        0 |      0 |        |
 15 |      0 |        0 |      0 |        |
 16 |      0 |        0 |      0 |        |
 17 |      0 |        0 |      0 |        |
 18 |      0 |        0 |      0 |        |
 19 |      0 |        0 |      0 |        |
 20 |      0 |        0 |      0 |        |
 21 |      0 |        0 |      0 |        |
 22 |      0 |        0 |      0 |        |
 23 |      0 |        0 |      0 |        |
 24 |   7880 |        1 |    310 |  42754 |  42755
(24 rows)
この時、インデックスエントリは変化せず、相変わらず ctid=(0,1) を指しています。
 itemoffset | ctid  | itemlen | nulls | vars |    data
------------+-------+---------+-------+------+-------------
          1 | (0,1) |      12 | f     | f    | 65 00 00 00
(1 row)
この時、テーブルのlp==1のレコードはlp_flags==2となっていますが、このlp_flags==2というのは「HOT更新後のリダイレクト」を意味し、その時のlp_offはブロック内のオフセットではなく、ラインポインタの番号を意味しています(詳細はソースコードの include/storage/itemid.h を参照してください)。

つまり、レコードを探す順序としては、
  • インデックスの ctid==(0,1) からテーブルのlp==1のレコードを見る
  • lp==1がリダイレクトなので、lp_off==24からラインポインタ24番(lp==24)を見る
  • lp==24は削除済(t_xmax==42755)なので、チェーンをたどって次の新しいレコード(lp==2)を探す
  • lp==2はまだ生きているので、このレコードを使う
という流れになります。

■まとめ


今回は、HOT Updateにおけるテーブルのレコードとインデックスの関係について解説しました。

PostgreSQLは追記型のストレージアーキテクチャを取るために、更新処理によって古いレコードが増えていくことはその通りなのですが、実際には、これまで見てきた通り、レコードやブロックが極力増えないような工夫が随所に凝らされています。

PostgreSQLがどのように動作しているのかを正しく理解し、その特徴をうまく捉えて、設計やパフォーマンスチューニングしていただければと思います。

明日は、ストレージアーキテクチャの最終回として「FILLFACTOR」を取り上げます。

では、また。

0 件のコメント:

コメントを投稿