PostgreSQLインサイド概要

SRA OSS, Inc. 日本支社
石井達夫

アジェンダ●PostgreSQLの概要●

PostgreSQLの構造概要●

PostgreSQLの実装と内部構造●問い合わせ処理の流れ

2

PostgreSQLの概要

3

PostgreSQLの概要：歴史
１９７７年スター １９８６年スター １９９４年スタート １９９６年スタート
トト
最初期の関係デー 次世代関係データ ＳＱＬ言語の実装 PostgreSQL Global
タベースの実装 ベースシステム
ＡＮＳＩ／Ｃによる Development Group
書き換えによるインターネットベ
クローズドソース フリーソフトースの開発
２５％の高速化
PostgreSQLとの ObjectGNU makeの採用 689,833ステップ
コードの直接の関 Relational
連性なし
178,976ステップ
Database
PostgreSQLの直接の祖先

p144

PostgreSQLの概要：開発体制
Core members
Bruce Momjian
Marc G. Fournier
Tom LaneJan Wieck
Peter Einsentraut
Josh Berkus
Dave Page

Major Developers
20-30人
●
一部コミット権限あり●

ボランティアによる自主独立プロジェクト● サーバ類もボランティアの提供●●

メインソースはcvs.postgresql.orgで管理，アプリケーション，関連プログラムはpgfoundry.postgresql.orgでホスティング 5

PostgreSQLのLinux上のシェア
その 他 , 4, 4%

データは＠ITより（２００３年１２月)

P o w e rG re s , 1 , 1 %H iR D B , 2 , 2 %S y m fo rw a re , 3 , 3 %D B 2, 12, 11%

O ra c le , 3 8 , 3 2 %M yS Q L , 2 1 , 1 8 %P o s tg re S Q L , 3 3 ,29%

6

Linux市場でのオープンソース
データベースのシェア
その他
F ireB ird
M yS Q L
P ostgreS Q L
020406080%

データは2005年の矢野経済研究所のアンケート調査より

7

PostgreSQLの主な機能●

SQL:2003の主要部分を実装– DDL, DML, Schema– 副問い合わせ，トリガー，外部キー，ビュー●

高度なトランザクション機能–

2レベルのトランザクション分離レベル–

トランザクションログによるリカバリ–

アーカイブログ(PITR: Point In Time Recovery)–

セーブポイント–

2相コミット–行ロック，テーブルロック–

MVCC(Multi Version Concurrency Control)8

PostgreSQLの構造概要

9PostgreSQLの利用形態
DBアプリケーション

PostgreSQL

C言語

Perl
Ruby
Pythonlibpq

PHP

DBエンジン

TCP/ IPSQL

ユーザ定義サーバサイドスクリプト• ユーザ定義関数• ストアドプロシジャ

JDBC• PL/ pgSQL• PL/ perl

ODBC

• PL/ python

p93

10

PostgreSQLのプロセス構造
postgresql.conf(設定ファイル)

接続
アプリケーション 要求

postmaster（PostgreSQL
管理デーモン)pg_hba.conf(セキュリティポリシーファイル)background writer
process

起動
問い合わせのやりとり
postgres(データベースエンジン)

statistics collector
process

データベース
トランザクション
ログ

アーカイブ
ログ

p94

11

PostgreSQLのデータ構造
データベースクラスタ
データベース
スキーマ

テーブル

テーブルスペース

インデックス

テーブルスペースp96

12

データベースクラスタの構造$PGDATA

base

1

10287

10792

10289

10793
global10290

pg_clog10292

pg_hba.conf
pg_logSun.logMon.log

pg_multixact
pg_subtranspg_tblspc
pg_twphase
pg_xlog
postgresql.conf

p98

13

PostgreSQLの実装と内部構造

14

サブシステムとその関係
frontend/
backendprotocol

パーサー

テーブル
インデックスプランナー

BufferManager

エグゼキュータ

Storage
Manager
Transaction
Manager

MemoryManager

MVCC

テーブル
インデックス

WAL
ログ

エラー処理
15

メモリーマネージャ●

メモリーリークの防止– 「メモリコンテキスト」(memory context)●

コンテキスト単位で一括メモリ解放– トランザクション単位のメモリコンテキスト– SQL文単位のメモリコンテキスト●

メモリーアロケーション効率の向上– 8KB単位でアロケーション●API– mallocの代わりにpalloc，freeの代わりにpfreeを使用

MemoryContextAlloc()16エラー/例外処理●

long jumpを利用して例外処理を実装– エラー発生時にトランザクションをアボートし，メモリを解放する

コードの簡素化● エラー処理の集中管理●– エラー番号(SQL標準のエラー番号+PostgreSQL独自)– エラーメッセージ
gettextによるメッセージカタログ● メッセージ出力先の柔軟な切り替え●●

API: elog()

elog_start()17

ストレージマネージャ
ストレージ層を抽象化● 実際には磁気ディスクのみサポート
●

●

●

API–

smgr_unlink–

smgr_extend–

smgr_read–

smgr_write–

smgr_nblocks–

smgr_truncate– smgr_shutdown–

smgr_immdesync– smgr_close–

smgr_commit–

smgr_abort–

smgr_syncAPI– smgr_init– smgr_create–

storage/smgr/smgr.c

18

ストレージマネージャの位置づけ
エグゼキュータ

ソート処理など，一時ファイルを使う処理

ストレージマネージャ

磁気ディスクマネージャ

バッファードファイル
マネージャ

仮想ファイルマネージャ

read/writeシステム
コール

19

アクセスメソッドの種類(1)●ヒープ

access/heap– データが順に並ぶ単純な構造，テーブルに使用●

B+treeaccess/nbtree/README– PostgreSQLの主要なインデックス，性能や効率が優れている．スカラー値の範囲検索

●

Hash

access/hash/README– 値の一致だけを検索条件にする– 効率が悪く，ログが記録されないので非推奨●

R-treeaccess/rtree– 空間範囲検索(「含むかどうか」など)

20

アクセスメソッドの種類(2)●GiSTインデックス– 汎用的かつ抽象化されたインデックス●

consistent, union, compress, decompress, penalty,picksplit, sameの7つの演算子クラス用メソッドを定義
すればどのようなデータもインデックス可能

– 応用例
●

B-tree，全文検索，木構造探索など– R-treeと同等の実装を含む●

R-treeの実装は，ログが記録されないなどの問題あり●

R-treeは今後サポートされない予定
access/gist/README

アクセスメソッドの体系

アクセスメソッド

トランザクション

R-treeヒープ

Hashインデックス

B+tree

GiST

22

ヒープの物理構造テーブルファイル
ラインポインター
８１９２バイト
固定長のブロック(ページ)空き領域

ヒープタプル
ヒープタプル

include/storage/bufpage.h23

ヒープタプルの構造

タプル
ヘッダー

NULL
ビットマップ

OID

列1

列2列n

個々のタプルは「タプルID」(Tuple ID:TID)で識別される．タプルIDはOID(Object Identifier)と違って更新などで変化する．
タプルID(ヒープタプルの物理的な位置) =ブロックID(32bit)+ブロック内のオフセット(16bit)
32TBまでの大きさのテーブルを扱うことができる(ブロックサイズが標準の8KBの場合)
include/access/htup.h24タプルヘッダーの構造

t_xmint_cmint_xmaxt_cmax/t_xvac

4
4
4
4

t_ctidt_nattst_infomask
t_hoff6
22
1

行を挿入したトランザクションID
行を挿入したコマンドID行を削除したトランザクションID行を削除したコマンドIDまたはVACUUMによって移動された行のバージョン
この行あるいは新しい行のTID(タプルID)
列の数
フラグビット
行データへのオフセット

include/access/htup.h25

インデックスタプルの構造

TID

フラグ

NULL
ビットマップ列1列2列n最大32列のマルチカラム
インデックス作成可能

include/access/itup.h26

テーブルとインデックスの関係
TID

フラグ

NULL
ビットマップ列1列2列nインデックスタプル

テーブル

27

B+treeインデックスの構造
119

rootノード

ポインタ

242

237

231

220

119

110

105

101

100

リーフノード231

105

インデックスノード

ページ

インデックスタプル
28

MVCC(Multi Version
Concurrency Control)
行をバージョン管理する● 更新中もその行を読み出せるのでトランザクションの並列実行性に優れている●– 実際には一つ前のバージョンを読み出す●

Oracleで「読み取り一貫性」と呼ばれている機能に相当– 実装は全く異なる●

どのトランザクションからも参照されなくなった行はVACUUMコマンドで削除
29

MVCCとタプルの可視性ルールの例●

t_xmint_cmint_xmaxt_cmax/t_xvac

4444

t_ctid6

行を挿入したトランザクションID
行を挿入したコマンドID
行を削除したトランザクションID
行を削除したコマンドIDまたはVACUUMによって移動された行のバージョン
この行あるいは新しい行のTID(タプルID)

同一トランザクション内では– 自分よりもコマンドIDが小さければ可視(ハロウィーン問題の回避)●

異なるトランザクションでは– 自分よりもxminが小さければ可視(削除，更新された行を除く)

utils/time/tqual.c

30

バッファキャッシュ管理
バックエンドプロセス

バックエンドプロセス

バックエンドプロセス

共有メモリ
上のdirtyバッファ

カーネルバッファ

ディスク上のブロック
31

storage/buffer/README

バッファキャッシュからディスクへの書き込みタイミング●

dirtyバッファの再利用が必要になったとき

バックグラウンドライタープロセスが書き込んだとき● チェックポイントが発生したとき●– このときに同期書き込み32

システムカタログ●

DBのメタ情報を管理– DBの一覧,テーブルの一覧...

●●

DBローカルなシステムカタログとDB共有のシステムカタログがある
DB共有システムカタログ– pg_authid, pg_tablespace, pg_shdepened,pg_database●

システムカタログを動的に作ることはできない
include/catalog

33

キャッシュマネージャ●

ヒープメモリ上のローカルなキャッシュ– 主にシステムカタログアクセスの高速化目的●

キャッシュの種類– カタログキャッシュ(システムカタログのキャッシュ)– リレーションディスクリプタキャッシュ(pg_classのキャッシュ)– 型キャッシュ●キャッシュの無効化– 共有メモリを使った「メッセージ」を各バックエンドに送る

utils/cache/34

ロックマネージャ●

3種類のロック– スピンロック– 軽量ロック– 重量ロック●

重量ロックの機能– SQLのLOCK文– 行ロック,テーブルロックの管理– デッドロックの検出●

waiting graphの利用– トランザクション終了時に自動的にロックを解放
storage/lmgr/README

35

トランザクション管理●

トランザクションの競合の調停– ロック,MVCCの利用●

デッドロックの検出– waiting graphの利用●

トランザクションとデータの可視性の管理– タプルヘッダーのxmin, xmaxなどを利用– SERIALIZABLEとREAD COMMITTEDのサポート– MVCCとの兼ね合い●

トランザクションログの管理
storage/access/transam36明示的なトランザクションと暗黙的なトランザクション
UPDATECOMMIT

UPDATE

BEGIN

セッション1

暗黙的 暗黙的BEGIN COMMIT

37

フロントエンド・バックエンド
プロトコル●

TCP/IP上のアプリケーションレベルのプロトコル– 接続開始,問い合わせの実行要求,結果の返却など– 行データは基本的に文字列でやりとり●●

フロントエンド用,バックエンド用のC言語
API(libpq)
libpqを使わずに独自実装も可能– JDBC, ODBC, pgpool

libpq

38

問い合わせ処理の流れ39

問い合わせ処理の流れ
問い合わせを受信
問い合わせ文字列
パース処理
パーサー
raw parse tree
アナライズ処理アナライザ
query tree
リライト処理リライタ
rewrite後のquery tree
プラン処理
プランナ(オプティマイザ)plan tree
エグゼキュート処理
エグゼキュータ

40

パース処理●文字列のSQL文を解析してパースツリーを作成

この段階ではシステムカタログは参照しない● 字句解析
●– flexを利用– 数字は[0-9],整数は数字が1個以上つらなったもの,などの定義を列挙●

構文解析– bisonを利用– SQL文の構造を再帰的に定義
paraser/gram.y41

SELECT * FROM accounts
WHERE aid=100のパースツリー

NodeTag:RANGEVAR
catalogname: NULL
schemaname: NULL
relname: “t1”InhOption: INH_NO
istemp: false
alias: NULL42問い合わせ処理の流れ
問い合わせを受信
問い合わせ文字列
パース処理
パーサー
raw parse tree
アナライズ処理アナライザ
query tree
リライト処理リライタ
rewrite後のquery tree
プラン処理
プランナ(オプティマイザ)plan tree
エグゼキュート処理
エグゼキュータ43

アナライズ処理
パースツリーからクエリーツリーを作成● ステムカタログを参照してオブジェクトを決定,情報を補足●– テーブルOID– 列名リスト– 型OID– オペレータOID

parser/analyze.c

44

45

46

問い合わせ処理の流れ
問い合わせを受信
問い合わせ文字列
パース処理
パーサー
raw parse tree
アナライズ処理アナライザ
query tree
リライト処理リライタ
rewrite後のquery tree
プラン処理
プランナ(オプティマイザ)plan tree
エグゼキュート処理
エグゼキュータ47

リライト処理●

クエリーツリーを一定のルールによって書き換える●

RULEシステムやVIEWの実装に利用●

RULEの例– CREATE RULE t1rule1 AS ON INSERT TO t1

WHERE NEW.i < 100 DO INSTEAD INSERTINTO t1 VALUES(NEW.i, NEW.j);●●

RULEのパースツリーもシステムカタログに格納
RULEパースツリーを追加,置き換え
rewrite48

問い合わせ処理の流れ
問い合わせを受信
問い合わせ文字列
パース処理
パーサー
raw parse tree
アナライズ処理アナライザ
query tree
リライト処理リライタ
rewrite後のquery tree
プラン処理
プランナ(オプティマイザ)plan tree
エグゼキュート処理
エグゼキュータ49プランナ
一般に「オプティマイザ」と呼ばれている部分● 「ルールベース」と「コストベース」オプティマイザ● クエリツリーからプランツリーを生成●– 組み込みルールを適用してクエリをより効率のよいものに書き換え– 可能な実行方法(path)を生成– その中から最適なものを選ぶ– 選んだpathをプランに変換
optimizer/README

50

プランナによる書き換えの例●INをJOINに変換●

foo OR TRUE -> TRUE●(NOT (A < B)) -> (A >= B)51

問い合わせ処理の流れ
問い合わせを受信
問い合わせ文字列
パース処理
パーサー
raw parse tree
アナライズ処理アナライザ
query tree
リライト処理リライタ
rewrite後のquery tree
プラン処理
プランナ(オプティマイザ)plan tree
エグゼキュート処理
エグゼキュータ52

エグゼキュート処理
プランナが作成したプランを実行● 固有の情報●– スナップショット●

実行中のトランザクションに関する情報– DestReceiver●

実行結果の送信先

executor/README

53

SELECT count(*) FROM t1のプランツリー
Plantype: AGG
startup_cost: 36.75
total_cost: 36.76
plan_rows: 1
plan_width: 0
target_list
qual:
leftree:righttree:
initPlan:

TargetEntry
NodeTag: TARGETENTRY
expr:
resno: 1
resname: countresorigtbl: 0
resorigcol: 0resjunk: false

AggRef
NodeTag: AGGREF
aggfnoid: 2147
aggtype: 20
target:agglevelsup: 0
aggstar: true
aggdistinct: false

Const
NodeTag: CONST
aggfnoid: 23
aggtype: 4
constvalue:
constisnull: false
constbyval: true

Plantype: SEQSCAN
startup_cost: 0.00
total_cost: 31.40
plan_rows: 240
plan_width: 0
target_list
qual:
leftree:righttree:
initPlan:

TargetEntry
NodeTag: TARGETENTRY
expr:
resno: 1
resname: countresorigtbl: 0
resorigcol: 0
resjunk: false

Var
NodeTag: AGGREF
varno: 1
varattno: 1
vartype: 23
vartypmod: -1
varnoold: 1
varoattno: 1

54

エグゼキュータの実行
フロントエンド
count(*)

テーブル名からrelfilenodeへの変換

DestReceiver

SysCache
RelCachefrontend/
backendprotocolpg_class

heap
access method
BufferManager
Storage
Manager

磁気ディスクManager

55

まとめ
●

PostgreSQLの概要– 歴史,開発体制,市場動向– 機能,構造●

実装と内部構造– 各サブシステムの役割と構造●

問い合わせ処理の流れ– パーサー,プランナ,リライト,プランナ,エグゼ

キュータ

56

参考文献/URL●●

PostgreSQL完全攻略ガイド改訂第5版/石井達夫/技術評論社/2006
WEB+DB PRESS「徒然PostgreSQL散策」– Vol.16「SQLをカスタマイズしよう」●

http://www2b.biglobe.ne.jp/~caco/webdb-pdfs/vol16_200-211.pdf– Vol.20「トランザクションログ」●

http://www2b.biglobe.ne.jp/~caco/webdb-pdfs/vol20_224-232.pdf– Vol.24「テーブルの構造とディスク容量の見積もり」●●

http://www2b.biglobe.ne.jp/~caco/webdb-pdfs/vol24_214-221.pdf
57

参考文献/URL●

WEB+DB PRESS「徒然PostgreSQL散策」– Vol.25「テーブルの構造とディスク容量の見積もり(2)」●●http://www2b.biglobe.ne.jp/~caco/webdb-pdfs/vol25.pdf

WEB+DB PRESS「PostgreSQL研究所」– Vol.27「パース処理とアナライズ処理」●

http://www2b.biglobe.ne.jp/~caco/webdb-pdfs/vol27.pdf– Vol.28「リライト処理」●

http://www2b.biglobe.ne.jp/~caco/webdb-pdfs/vol28.pdf– Vol.29「プラン処理(1)」●http://www2b.biglobe.ne.jp/~caco/webdb-pdfs/vol29.pdf

58

参考文献/URL●

WEB+DB PRESS「PostgreSQL研究所」– Vol.30「プラン処理(2)」●http://www2b.biglobe.ne.jp/~caco/webdb-pdfs/vol30.pdf– Vol.31「エグゼキュート処理」●

http://www2b.biglobe.ne.jp/~caco/webdb-pdfs/vol31.pdf

59