ANALYZEでのサンプルデータ抽出ロジック

ANALYZE のサンプルデータ抽出ロジックを少し調べたので備忘録として。

PostgreSQL では、ANALYZE を実行したときにテーブルからサンプルデータを抽出し、それらの値に基づいて統計情報を作成しますが、サンプルデータの量（タプル数）は対象テーブルの各列の STATISTICS 設定(未設定ならばdefalut_statistics_target)にもとづいて決定されます。

コード中のコメントを見ると、サンプルデータの抽出アルゴリズムは Vitter 氏考案のサンプリングアルゴリズム(PDF)とか Knuth 氏のアルゴリズム S とかのハイブリッドになっている模様。

なお、ANALYZE 対象テーブルごとに一回のスキャンでサンプリングを完了させるため、ANALYZE対象の列のうち最も多くサンプルを必要とする列の設定に従います。各列の目標サンプル数は STATISTICS 設定の300倍ですが、Vitter アルゴリズムの制限(?)により最低目標サンプル数は100だそうです。

サンプル抽出のアルゴリズムを擬似コード化するとこんな感じです。

総ブロック数取得
if (呼び出し元が総ブロック数を要求)
    引数経由で返却
現在アクティブなトランザクションの開始時にアクティブだった最古のXIDを取得
while (まだサンプルが必要)
{
    対象ブロック番号決定
    VACUUM遅延チェック
    対象ブロックをバッファに読込
    バッファを共有ロック
    foreach(ページ内タプル)
    {
        if (DEADタプル) DEADタプルカウントアップ
        if (!Normalタプル) continue
        switch (タプル状態)
        {
            case 有効タプル:
                サンプル採用、LIVEタプルカウントアップ
            case DEADタプル:
                DEADタプルカウントアップ
            case INSERT中タプル:
                if (自TXがINSERTしたもの)
                    サンプル採用、LIVEタプルカウントアップ
            case DELETE中タプル:
                if (自TXがDELETEしたもの)
                    DEADタプルカウントアップ
                else
                    LIVEタプルカウントアップ
            default:
                エラー
        }

        if (サンプル採用)
        {
            if (サンプル数が目標数未満)
            {
                結果バッファ末尾にコピー
                サンプル数カウントアップ
            }
            else
            {
                if (残りスキップ数 < 0)
                    スキップ数決定
                if (残りスキップ数 > 0)
                    入れ替え位置を決定
                    結果バッファの入れ替え位置にコピー
                スキップ数カウントアップ
            }
        }
    }
    バッファロック解放
}

if (サンプル数が目標数に届いた)
{
    タプル位置(TID)の昇順でソート
}

総タプル数を算出
DEADタプル数を算出

サンプル数を戻り値で返却

目標サンプル数を超えた後は取得した新しい(後ろのほうにある)タプルを既存サンプルと入れ替えていくのですが、そのときの入れ替え位置は単純なランダムです。取得したレコードがすべてLIVEタプルでDEADタプルなし、ということに単純化できれば、外部データラッパでANALYZE用にサンプリングするのに使えそうな気がします。