Planner のしくみ NTTサイバースペース研究所 板垣 貴裕 postgresql.org 2004/07/26.

Presentation on theme: "Planner のしくみ NTTサイバースペース研究所 板垣 貴裕 postgresql.org 2004/07/26."— Presentation transcript:

1 Planner のしくみ NTTサイバースペース研究所 板垣 貴裕 postgresql.org 2004/07/26

2 目次 復習：PostgreSQLの概観 Planner 解析 コスト計算と統計処理 Planner のデバッグ まとめ
1. 初めにPostgresSQLの全体的な処理の流れについて。 2. 次に、今回ソースを読んでわかったPlannerの内部について。 3. Planner内部で重要な役割を持つ、コスト計算について。 4. プランがおかしい場合のデバッグ手法について。 5. 最後にまとめ。

3 復習：PostgreSQLの概観 （接続～Planner） Planner 解析 コスト計算と統計処理 Planner のデバッグ まとめ
Executor Planner Rewriter Parser SQL 結果 Data Access Storage Buffer Log 復習としてPostgreSQLで、コマンドを受け取ってからPlannerに処理が引き渡されるまでの流れ

4 PostgreSQLの通信方式 postmasterは唯一つ。接続要求に応答 Clientごとにpostgres(backend)を生成
DB Server postmaster 1.接続要求 2. postgresの生成 Client postgres 3. クエリ処理 postgres Client postmasterは唯一つ。接続要求に応答 Clientごとにpostgres(backend)を生成 以降、Clientはpostgresとやり取りする まずはPostgreSQLの全体的な通信方式。 PostgreSQLの特徴のひとつに、接続するClientごとに通信相手を立ち上げるという動作がある。Clientは唯一つあるpostmasterに接続要求をし、postmasterはそれに応答してpostgresを生成する。以降、Clientは自分専用のpostgresに対して通信を行う。

5 起動～SQL入力 * postmaster postgres PostmasterMain () ServerLoop () 接続待ち
1 * PostmasterMain () ServerLoop () 接続待ち select (sockets) BackendStartup () fork() PostgresMain () コマンド入力待ち 流れの処理手順を並べたのがこの図である。 PostgreSQLには、複数の「起動モード」がある。 ひとつは postmaster モードで、共有資源の初期化とDBに対する接続を仲介する。接続要求ごとに fork() して子プロセスを作成し、postgres モードで動作させる。 postgres モードでは、クライアントからのコマンドの入力を解析して実行をすることを繰り返す。 次は execute SQL の中身。 ReadCommand () execute SQL function blocking fn.

6 SQL処理 Parser Rewriter Planner Executor SQL 字句解析 構文解析 pg_parse_query ()
意味解析（識別子の解決、型認識） pg_parse_query () Parse parse_analyze () Raw Query Rewriter VIEWの展開 RULEの適用 QueryRewrite () Rewritten Query Planner パスの展開と枝切を平行して行う（Planner/Optimizerという区分け無し） 最良のアクセスパスの選択 実行プランの生成 planner () RelOptInfo/Path create_plan () 入力されたSQL文字列を実行するまでの流れである。 まず、Parserモジュールがテキストを解析し、QueryTreeと呼ばれるSQLの内部表現に変換する。 次に、RewriterモジュールがVIEWの展開とRULEの適用を行う。VIEWを展開する理由は最適化を促すためである。 Plannerモジュールは、QueryTreeを、中間形式を介して、PlanTreeに変換する。この際、ひとつのQueryを実現するためのPlanは複数あるため、そのうちで最も良いPlanの選択を行う。PlannerとOptimizerは分かれているわけではなく、どちらも同じものを指すと考えてよい。今回の発表では、基本的に用語をPlannerで統一する。 PlanTreeはExecutorに渡され、順番に実行されるようだ。 Plan Executor パイプライン化された デマンドプル型ネットワークを実行 Portal ExecutorStart () Result

7 Planner 解析 復習：PostgreSQLの概観 （データ構造～処理手順） コスト計算と統計処理 Planner のデバッグ まとめ
Query I/F By Rule By Cost DP GEQO 付属のドキュメント、README、ソースコードなどを解析した結果。 Path Finalize Plan

8 Planner概観：前半 I/F By Rule By Cost Finalize Rewritten Query
SQL Rewritten Query SQL DML の内部表現 SELECT,UPDATE,INSERT,DELETE 対象テーブル FROM, WHERE, JOIN… ソート GROUP BY, ORDER BY, DISTINCT Parser I/F pg_plan_query () planner () By Rule Query RelOptInfo ルールベースの最適化 各種 書き換えプリプロセス RelOptInfoの作成 Rewriter grouping_planner () By Cost query_planner () Query テーブル組み合わせ順序 どのテーブルから先に連結するか （方法は考慮しない） Planner Path数 多 少 動的計画法 遺伝的探索 Planner内部の処理の流れである。Planner内部にはいくつかステップがある。 Rewriterからは、Queryツリーが渡されてくる。これは、SQL DML をC言語の構造体にマッピングしたものと考えてもらってよい。 まず初めに、ルールベースの書き換え最適化を行いながら、RelOptInfoという構造を作っていく。書き換えの定石ごとに各種プリプロセスが用意されている。 RelOptInfoは、テーブルの組み合わせ順序を表す。複数のテーブルを参照している場合に、どのテーブルを処理するかのまとまりを表す。 Plan Path Finalize Executor create_plan () Plan

9 Planner概観：後半 I/F By Rule By Cost Finalize Rewritten Query コストベースの最適化
SQL Rewritten Query Parser コストベースの最適化 Path （＝連結手順）探索 　　動的計画法 or 遺伝的探索 Scan/Join法の選択 I/F pg_plan_query () planner () By Rule Query RelOptInfo Rewriter テーブル連結方法 Scan方法 SeqScan, IndexScan, TidScan Join方法 NestLoop, MergeJoin, HashJoin grouping_planner () By Cost query_planner () Query Planner Path数 多 少 動的計画法 遺伝的探索 Path⇒Plan変換 最低コストPathを選択、変換 Executorで必要ない情報を除去 その後、パスの列挙と選択を行う。基本的には動的計画法を使った全探索を行う。 ただし、10個以上のテーブルを参照する場合は、探索範囲が広くなりすぎるため、遺伝的アルゴリズムを用いた別のモジュールで処理される。（ほとんど使われないといっても良いかもしれない） このとき作成されるPathは、RelOptInfoとは異なり、具体的なテーブルの連結手順を保持している。言い方をかえると、RelOptInfoが探索木の各ノードを表し、そのノード間を繋ぐ繋ぎ方がPathといえる。 最後のFinalizeでは、PathからPlanへの変換を行う。Pathに含まれるimplicitな部分をexplicitに書き換える処理が行われる。 Planは、Executorに渡される実行処理手順である。 Plan Path Finalize Executor create_plan () 実行手順 Executorに渡される実行処理手順 Plan

10 Query×1 ⇒ RelOptInfo×1 SELECT * FROM A, B, C WHERE A.foo = B.foo AND B.bar = C.bar baserel A joinrel AB baserel B joinrel ABC baserel C baserel A baserel B joinrel ABC 複数入力 joinrel BC 2つずつ 結合 baserel C 具体的なSQLが処理される流れとして見ていこう。 左側がSQL、右側全体の構造が RelOptInfo tree である。 SQLは3つのテーブルを参照しているため、基底関連(baserel)は3つである。テーブルを組み合わせる場合は、常に2つずつ行われるため、どの2つを先に処理するかによって、3種類の方法がある。（これが右側） ただし、WHEREで関係が指定されていないテーブル同士の結合は候補から落とす。なぜなら、単純に直積(CROSS JOIN)を計算することになり、確実に悪いプランになるからだ。（というわけで、右側一番下は考えない） SQL 関係の指定が無いため baserel A joinrel CA baserel B joinrel ABC 単数出力 baserel C

11 RelOptInfo×1 ⇒ Path×N Path = RelOptInfoノードをどのような方法で結ぶか Pathの例
baserel A SeqScan IndexScan on A.foo Pathの例 joinrel AB NestLoop MergeJoin HashJoin joinrel ABC NestLoop MergeJoin HashJoin baserel B SeqScan IndexScan on B.foo IndexScan on B.bar baserel C SeqScan IndexScan on C.bar baserel A joinrel BC この図は、ABを先に、その後ABとCを処理する流れである。ただし、同時並行で、BCが先の場合についても行われている。 2つのテーブルを参照して、それを組み合わせる場合、2つのことを考慮しなければならない。一つは、それぞれのテーブルに対するScan方法、もう一つは、その2つを連結させるJoin方法である。 あるテーブルが今回のクエリに関係のある、N個のインデックスを持っている場合、それらのインデックスに対するIndexScanとSeqScanを加えた、全部でN+1個のScan方法がある。 また、Join方法は、NestLoop, MergeJoin, HashJoinの3種類の方法がある。Plannerは、それぞれのすべての組み合わせについて、ボトムアップで（baserelから上に向かって）コストを計算していく。 基本的には、既にそれよりも安いPathがある場合、新たなPathはすぐに捨てられる。しかし、それがJoin後で何かしらのカラムでソートされている場合、コスト的には効果でも、将来的な使えるかもしれないので、保持しておく。 Path = RelOptInfoノードをどのような方法で結ぶか 並び順 ・・・後のSORTの省略を期待(pathkeysとして保持） コスト ・・・同じソート状態ならば、最低コストのものだけを記憶

12 Path×1 ⇒ Plan×1 Plan = Pathの暗黙性を排除したもの Hash Sort Pathを矛盾無く繋ぐ 処理の挿入
baserel A SeqScan Hash Sort Pathを矛盾無く繋ぐ 処理の挿入 joinrel AB HashJoin baserel B IndexScan on B.foo joinrel ABC MergeJoin baserel C IndexScan on C.bar Pathが出揃ったところで、最もコストの低いPathを選択する。そして、そのPathとRelOptInfoに含まれる情報を統合し、Planを生成する。このとき、今後Executorでは必要の無い情報は削られる。 基本的にPathとPlanは1対1対応で変換できる。ただし、Pathを矛盾無く繋ぐためのSortの挿入などをする場合もある。PathよりもPlanのほうが、粒度の細かいオペレーションに分割されている。 ここまでが、具体的なPlannningの流れである。 Plan = Pathの暗黙性を排除したもの RelOptInfoとPathの情報を併合 必要ない情報の削除（中間状態での並び順など） 明示的なサブ処理（ソートなど）の挿入

13 ルールベースの最適化 処理回数を減らす&最適化に適した形に変換 継承の処理 条件句の最適化 定石：サブクエリや条件句を主クエリに一体化
WHERE IN ⇒ JOIN HAVING ⇒ WHERE OUTER JOIN ⇒ INNER JOIN JOIN vs. FROM （なるべくFROMを使いたい） JOIN　= 順序指定あり ⇒ 最適化の余地が減少 FROM= 順序指定なし ⇒ 探索経路の増加 継承の処理 継承親へのクエリを、継承子孫へ置換 条件句の最適化 関数のインライン化 SQLで書かれた関数のみ immutable式の事前評価 例：100+1 ⇒ 101 暗黙の条件の明示化 例：A=B and B=C ⇒ A=C Query I/F By Rule By Cost DP GEQO もう一度、最適化処理を大枠で見ていこう。 まず、ルールベースの書き換え最適化が行われる。 サブクエリは再帰呼び出しで処理されるので、クエリ数を減らすことが効率化に繋がる。 JOIN と 複数のテーブルを対象にとるFROM にはトレードオフ関係がある。JOIN は結合順序の指定があるが、FROM にはそれがないため、最適化の自由度がある。ただし、テーブル数の増加に伴って候補が指数関数的に増加するため、FROM対象は適当な数に抑える必要がある。 もう一つの重要なものは、継承の処理である。PostgreSQLでは継承関係をテーブルで扱っており、継承祖先を表すテーブルに対する呼び出しを継承子孫を表すテーブルに書き換えることで、late-bindingを実現している。“Optimizer” という名前にもかかわらず、この処理を通さないと間違った結果が返ることに留意する必要があるかもしれない。 冗長部分を単純化したり、定数ではじめから結果がわかっている条件部分を先に処理しておく。 Path Finalize Plan

14 コストベースの最適化 アルゴリズムの選択 テーブル結合の順番と方向 コスト計算での考慮事項
Scan方法の選択 (SeqScan, IndexScan, TidScan) Join方法の選択 (Nest Loop, Merge Join, Hash Join) テーブル結合の順番と方向 順番 = 結合は2つずつ ⇒ 3つ以上の場合に自由度あり 方向 = inner, outer の割り振り = 二重ループの内と外 コスト計算での考慮事項 並び順を考慮 ORDER BY, GROUP BY のためのソートを減らす Merge Join はソート済みでなければならない 統計情報の利用 取得数の多少 ⇒ SeqScan vs. IndexScan 値の重複が多ければHashの効果は小さい 2つのコスト基準：Startup cost と Total cost EXISTS などの場合には、全部処理しなくて良い Query I/F By Rule By Cost DP GEQO 次に、コストベースの最適化を行う。 テーブルをスキャンする方法、JOINの方法の選択を処理する。結合の方向というのは、JOINする場合に、INNER側とOUTER側のどちらを割り当てるかということ。たとえば、NestLoopではINNER側はソートされていると高速になる。またOUTER側の並び順はJOIN後も保持できる。 また、これらの候補を絞り込む際には、並び順と予測取得数が参照される。 SQLでORDER BY, GROUP BYなどが指定されたものの他、MergeJoinでは双方がソートされていなければならない。TreeIndexScan後はソート済みになることに注意。SeqScan, HashIndexScanではバラバラ。 IndexScanの場合は、ディクスにランダムアクセスすることになるため、そのぶんシーケンシャルアクセスよりもコストがかかる。 このコスト計算に絡む部分が、Plannerのキモである。 Path Finalize Plan

15 コスト計算と統計処理 復習：PostgreSQLの概観 Planner 解析 （チューニングパラメータ～統計情報）
まとめ では次に、コスト計算に関係する部分を見ていく。

16 c/p=cost/page c/t=cost/tuple
コスト計算に使用されるパラメータ c/p=cost/page c/t=cost/tuple 種別 名前 説明 基本値 IO effective_cache_size ページキャッシュ効果 1000 page (sequential_page_cost) シーケンシャルページアクセス 1 c/p random_page_cost ランダムページアクセス 4 c/p CPU cpu_tuple_cost タプル処理 0.01 c/t cpu_index_tuple_cost インデクス タプル処理 0.001 c/t cpu_operator_cost WHERE処理 c/t バッファ sort_mem Sort, Materialize用の一時バッファ 1024KB 統計 MCV: most common values 重複した値とその割合のランキング HISTOGRAM 値の分布。範囲指定選択で使用 CORRELATION 物理的な並び順とインデクスの相関 stanullfrac NULL エントリの割合 stadistinct 重複の無いエントリの割合 INDEX XXXcostestimate() インデクス依存のコスト関数 選択性 DEFAULT_EQ_SEL デフォルトの選択性 ： A = b 0.5% DEFAULT_INEQ_SEL デフォルトの選択性 ： A < b 33.3% DEFAULT_BOOL_SEL デフォルトの選択性 ： boolean 50% 設定ファイル 起動引数 SET命令 VACUUM ANALYZE 具体的なチューニングパラメータの内容がこの表である。 IOとCPUのコストとソート用バッファサイズは設定ファイルで調整し、統計情報はVACUUM ANALYZE時に再計算される。いくつかのデフォルト値は、コンパイル時の定数になっている。 コスト : Cost シーケンシャルアクセス1ページが単位 選択性 : Selectivity WHERE, JOIN ONの条件を満たすタプルの割合 Distinct ある列の値が取る種類。重複したものは1種類と数える MCV(Most Common Value) 重複した値の多いもの順 Compressed Histogram 全体からMCVを除いた残りのヒストグラム。 初めに帯数を決定。 同じ数だけ分配されるように帯幅を調節。 OidFunctionCall(function-oid) カタログに登録されている関数を間接的に呼ぶ。 関数追加が自由にでき、拡張性に富む。 compile

17 コスト対象と参照情報 Pathの構成要素ごとに、ボトムアップでコストを計算 ○ コスト対象 IO/CPU バッファ コスト推定関数
SeqScan TidScan Agg Group etc. ○ IndexScan OidFunctionCall(IndexKind) Sort Materialize NestLoop MergeJoin approx_selectivity() HashJoin estimate_hash_bucketsize() 各操作ごとにコスト推定関数が用意されている。それらの関数から参照される情報を表にするとこのようになる。 一般調整変数、ソートバッファ、統計情報、実装依存関数の4つの大別できる。 次は、コスト推定関数について。 Pathの構成要素ごとに、ボトムアップでコストを計算

18 Join/Scanコスト推定関数 Joinコスト推定関数 Scanコスト推定関数 approx_selectivity()
演算子（ =, <, >, LIKE, 正規表現 ）ごとの推定関数⇒ヒストグラム estimate_hash_bucketsize() ハッシュの有効性の推定 ⇒ MCV:Most Common Values Scanコスト推定関数 インデクスアルゴリズムごとに存在するように見えるが… btcostestimate() for B+-tree（2分割ツリー） rtcostestimate() for R-tree（領域ツリー） gistcostestimate() for GiST（一般化ツリー） hashcostestimate() for Hash（線形ハッシュ） …実は同じ関数で処理されている genericcostestimate() ⇒ 抽出数（ MCV）、参照ページ数、etc. B+-treeだけは追加処理 ⇒ 上記＋相関 B+-tree :範囲述語(<、=、>)のみをサポート R-tree : n次元の範囲述語(含む、含まれる、等しい)のみをサポート GiST : 汎用検索ツリー(Generalized Search Tree)　任意のインデックススキーマを実装する基本的なテンプレート。B+-treeとR-treeを一般化したもの。 Selectivity：選択率とは、その条件でどれくらいの割合のタプルを拾ってくるか。それぞれの演算子ごとに用意されており、統計情報のうちのヒストグラムを参照して値を計算している。（実は、いくつかの選択率計算関数は実装をサボっている） ハッシュは、ハッシュコードがぶつかることが多い場合には有効なアルゴリズムではない。そこで、MCVという値の重複を考慮してコストを見積もる。 Scanは、OID関数呼び出しを通じてインデクスのアルゴリズムごとのコスト計算関数を呼ぶ。しかし、実は内部で同じ関数を呼び出している。この関数では、抽出数、参照ページ数、条件句処理コストなどから一般的なコストを推定している。ただし、B-treeだけはその後特別処理が行われる。 次は、コスト計算に使用される統計情報。

19 集計される統計情報 VACUUM ANALYZE コマンドにて更新 MCV: Most Common Values
大量更新／インデックス作成後には忘れずに！ MCV: Most Common Values 重複のある値を、重複数の多い順に並べたもの ヒストグラム (Compressed Histogram) (全体 － MCV) に対するヒストグラム 値の重複が多い場合に、より正確になる 各帯の中のサンプル数が一定になるように、帯幅を調整 相関 値でソートした順序と、ディスク上の順序の相関 B-treeのコストに影響 相関 = 0 （ランダム） 選択率 > 1% で SeqScanに切り替え 相関 = 1 （完全一致） 選択率 > 80% で SeqScanに切り替え cf. CLUSTER コマンド 任意の順序付インデックスと物理的な並び順を一致させる VACUUM FULL のついでにやっておくと良いかも？ VACUUM ANALYZE コマンドにて、3種類の統計情報を集計する。 一つ目は、MCV: Most Common Values である。これは、重複のある値を、その重複数の多いものから順にならべたランキングである。 二つ目は、ヒストグラムである。PostgreSQLでは、Compressed Histogramという工夫されたヒストグラムを使用している。 三つ目は、インデックス順と物理的なディスク上の配置順の相関である。これは、B-treeのコストを計算する際に使用される。人工的ではあるもの、相関が0と1の場合について、どれくらいの選択率でB-tree IndexScanからSeqScanに切り替わるかを調べてみた。実は、予想以上に相関の影響は大きい。 物理的な並び順は、CLUSTERコマンドにより整列できる。CLUSTER コマンドは、実装的にVACUUM FULL の効果も兼ね備えているような？

20 デフォルトの選択性 選択性 絞込み条件に一致するタプルの割合 デフォルト値は、統計情報を利用できない場合のみ使用
定数名 default 説明 例 DEFAULT_EQ_SEL 0.5% 等号 A = b DEFAULT_INEQ_SEL 33.3% 不等号 A < b DEFAULT_MATCH_SEL パターンマッチ LIKE DEFAULT_UNK_SEL IS NULL DEFAULT_BOOL_SEL 50% boolean test 選択性 絞込み条件に一致するタプルの割合 デフォルト値は、統計情報を利用できない場合のみ使用 ⇒ 不適切なプランになることが多い デフォルトを使わせないためには… 統計情報を使えるようにしてやる これにはいくつかの条件が必要… ⇒ 次のページ 統計情報が利用できない場合は、選択性を見積もることができないため、デフォルトの選択性が用いられる。 ただし、図を見てもらえばわかるように、非常におおざっぱな値である。（情報が何も無いから仕方ないのだけれど） デフォルト値を使った時点で、ほとんどの場合、そのプランは不適切なものになってしまう。よって、統計情報を使ってもらえるようなクエリを発行することが第一の課題になる。 DEFAULT_EQ_SEL = 0.5% について： ページあたりのタプル数は、典型的な場合ならば100個程度（1タプル80bytes）。よって、1%以上にすると、計算上全ページスキャンすることになってしまう。そこで、0.5%という値が設定してある。

21 条件句の左辺に対する書式制限 SELECT * FROM t WHERE t.x = k ;
左辺の制限 インデックスを使うためには、 『登録された値』 そのものでなくてはならない 関数インデックスとして登録済みなら使用される 統計情報を使うためには、 『カラム名』 そのものでなくてはならない 関数インデックスは不可 関数インデックス用の統計情報を収集しないため 条件句の左辺値に大きな制限がある。 条件句というのは、WHERE のほか、JOIN ~ ON を含む。 統計情報を使うための制限があるので、関数インデックスはそのままでは使われにくい。 abs(x)=k という条件を書きたい場合も、左辺がカラム名になるように展開してやる必要がある。 左辺はカラム名のみを書くべし （※ Plannerだけでなく、 Executor, Analyzer も原因） ◎ WHERE abs(x)=k × WHERE x=k or x=-k

22 Planner のデバッグ 復習：PostgreSQLの概観 Planner 解析 コスト計算と統計処理 （ヒントもどき～内部情報ダンプ）
まとめ デバッグ…というか、クエリの処理がおかしい場合の内部調査法について。

23 Plannerのデバッグ：はじめに デバッグ前に確認すること デバッグの方針 VACUUM ANALYZE を忘れていませんか？
そもそも他の有効なプランは選択肢に挙がっているか？ 『Plannerの動作制限』 ヒントもどき 最適化方針を変えさせて、有効なプランを探す コスト計算のどの時点で選択肢から落とされているか？ 『Planner内部情報のダンプ』 有効なはずのプランと、選ばれてしまうプランのコストを比較する 基本は、EXPLAIN ANALYZE 。特に良くあるミスが、ANALYZEをしていないために予測選択率がボロボロになっていること。 それでもダメなら、デバッグをしてみる。 デバッグの方針としては、まず、Plannerに動作制限をかけて、望みのクエリが候補としてあがっているかを確かめること。このとき、PostgreSQLにはヒントという機能は無いが、非常に大まかなレベルで動作を制御することは可能、 候補としてあがっているにもかからわらず、それが最終選考プランに残っていない場合には、どこでどうコストが計算されているか、Plannerに内部情報をダンプさせる。

24 ヒントもどき（アクセスメソッド操作） アクセスメソッド制限 コストの強制変更 SET enable_XXX = [true|false];
SQL文単位でしか変更できない 特定のサブクエリのみ or テーブルのみ の指定できない 実装はコストを跳ね上げているだけ コストの強制変更 例） random_page_cost を下げて インデクスを使いやすくなる seqscan indexscan tidscan sort hashagg nestloop mergejoin hashjoin PostgreSQLでは、それほど詳細なプラン指定はできない。 アクセスメソッド単位に完全に制限してしまうか、random_page_cost をいじる程度。そのほかのパラメータはほとんど意味が無い。 種別 名前 説明 基本値 IO random_page_cost ランダムページアクセス 4 c/p CPU cpu_tuple_cost タプル処理 0.01 c/t cpu_index_tuple_cost インデクス タプル処理 0.001 c/t cpu_operator_cost WHERE処理 c/t

25 ヒントもどき（条件句判定順操作） サブクエリに追い出し、マージを抑制する 無駄な “OFFSET 0” を追加する
そのままでは {賢くも | お節介にも}マージしてしまう aggregate, sort, limit を持つサブクエリはマージしない 基本的には、最適化の余地が多い形のクエリが良い SELECT * FROM A, B WHERE A.a1 = B.b1 AND A.a2 = K AND B.b2 = L ; 条件句の判定順を制御したいのならば… SELECT * FROM A, (SELECT * FROM B WHERE B.b2 = L OFFSET 0) AS tmp WHERE A.a1 = tmp.b1 AND A.a2 = K; 条件句の判定順序、処理順序を限定するには、サブクエリに追い出してやる方法が有効。このとき、そのままではマージされてしまうため、OFFSET 0 という HACK をする。 Planner内にマージが可能か否かを判定する部分は、 prepjointree.c : is_simple_query()

26 内部情報のダンプ #define OPTIMIZER_DEBUG Planning時の内部情報を標準出力へダンプ
cannonicalize_qual() 後の式を表示 条件句の最適化/正規化を行う関数 ただし、式がOID表記のため、読みづらい 切り捨てられる前のPathを表示 EXPLAIN ANALYZEと同程度の情報 候補に挙がってる複数のプランを確認できる 望みのプランは僅差で負けていないか？ ただし、本当のN-bestではない 同じソート状態の場合は切り捨てられるため 内部情報のダンプは、コンパイルオプション一つで可能。ただし、デフォルトでは読みづらいため、簡単なパッチを当てた。 ダンプされる情報： 正規化後の式。ただし、OIDが表示されるだけなので判読は難しい。 候補に上がってるPath。ただし、ソート状態が同じ場合はどんどん切り捨てられるため、本当の N-best ではない。真のN-bestを表示させたい場合は、Planner自体に手を入れる必要がありそう。

27 Pathダンプの例 select * from A, B where A.a1 = B.b1 and A.a2 < K and B.b2 < L order by B.b1; RELOPTINFO (1:A 2:B): rows=3 width=24 path list: MergeJoin(1:A 2:B) rows=3 cost= pathkeys: ((A.a1, B.b1)) clauses: A.a1 = B.b1 sortouter=0 sortinner=1 IdxScan(1:A) rows=634 cost= pathkeys: ((A.a1, B.b1)) SeqScan(2:B) rows=258 cost= NestLoop(1:A 2:B) rows=3 cost= IdxScan(1:A) rows=634 cost= MergeJoin(1:A 2:B) rows=3 cost= pathkeys: ((A.a1, B.b1)) IdxScan(2:B) rows=258 cost= pathkeys: ((A.a1, B.b1)) cheapest total path cheapest startup path 並び順 具体的なダンプの一部。A, B という2つのテーブルを結合するクエリの、最終選考に残った3つのプラン。 EXISTS や IN 句の場合は、初めの結果を見つけた時点で処理が終了するため、startup cost で評価する。 一般のクエリの場合は、total コストで評価する。 1番目：total コストが安いから 2番目：スタートアップコストが安いから 3番目：スタートアップコストが安い上、pathkeysを持っているから（pathkeysが考慮されるので、コスト的には2番目に負けていても、最後まで保持される） この場合、1番目と2番目のコストは僅差。設定したCPU/IOコストが完全に実情と一致していなければ、実際には2のほうが速いこともありうる。

28 復習：PostgreSQLの概観 Planner 解析 コスト計算と統計処理 Planner のデバッグ まとめ 最後に、まとめを。

29 Plannerをうまく働かせるコツ 環境に合わせたパラメータ設定を こまめな VACUUM ANALYZE Plannerの得意なクエリを
CPUが高速化してきた IOコスト > CPUコスト 大量のメモリを搭載できるようになった sort_mem の増量（デフォルト1MB） こまめな VACUUM ANALYZE 統計情報を { うまく利用 | 大きく依存 } しているため Plannerの得意なクエリを 最適化はPlannerに一任すべし サブクエリ, JOIN よりも FROM~WHERE 左辺にはカラム名を： f (x) = k ⇒ x = f -1(k) 演算子を数学的に捕らえてはいけない x = k の意味 ⇒ x をスキャンせよ。フィルタは(=k)。 最適化処理と、コスト計算を考慮した、Plannerをうまく働かせるコツについて。 統計情報は、Plannerにとっての生命線。

30 Plannerの問題点 統計情報の収集・利用に関して インデックスの使用可否判定に関して 統計情報収集方法の改善ができないか？
現状：scalar型のみ対応 “=”, “<”, “&&”, “&<” ユーザ拡張できる収集関数 “x % k” に対する統計情報 実行状態を考慮できないか？ キャッシュや他プロセスの状態 “実際にどうなったか” を反映できないか？ cf. Oracle: 稼動履歴に基づく予測機能(ADDM/AWR) インデックスの使用可否判定に関して 左辺の式・関数には非対応 (ex. x+1=100) インデックスの流用ができない 組み込みのパターンマッチのみ、ハードコーディングで対応 文字列に対するB-tree を LIKE, SIMILAR TO で前方一致検索 interger に対するB-treeを、interger/100 に流用できない ユーザ定義演算子には非対応 自動データベース分析モニタ(ADDM) 自動ワークロードリポジトリ(AWR) いくつかの機能はハードコーディングになっており、拡張できないのが問題か？

31 SQL/MM に対応できない？ f (x) = k SQL/MM で規定されている書式 制限の回避例：tsearch2 （テキスト全文検索）
Full-Text: 長大なテキスト内の曖昧検索 contains(txt, ‘IS ABOUT “PostgreSQL”’) = TRUE Spacial: 地理情報の問合せ distance(出発地, 目的地) < 1000; Still-Image: 画像検索 SI_findTexture(newLogo).SI_Score(Logo) > 1.2 制限の回避例：tsearch2 （テキスト全文検索） と 比較器作成関数 to_tsquery() A SELECT * FROM t WHERE t.txt to_tsquery(…, ‘PostgreSQL’) これをSQL/TEXT式に書き換えるとインデックスが使えない B SELECT * FROM t WHERE CONTAINS(t.txt, ‘PostgreSQL’) = TRUE ; ……字面だけの問題だと無視して良いのか？ 左辺が関数形式 f (x) = k SQL/MM では、左辺に関数書きまくり。 たとえば、テキスト全文検索機能を追加する tsearch2 というモジュールがある。回避例と入っても、必ずしも悪いとか劣っているというわけではない。 これは、比較器(Comparator)という、比較のための情報を詰め込んだオブジェクトを生成した後、ユーザ定義演算子によって比較することで、書式的に左辺にカラム名が書けるようになっている。 これを、SQL/TEXTの書式にしたがって下のようには書くと、インデックスは使えない。 機能的には同等なのでこれでかまわないと言えばかまわないのだが、標準準拠度のような言い方をされると問題になるかも。 比較器：演算子には左辺、右辺以外の引数を渡せないため、右辺に比較のための情報を詰め込んで引き渡す方法

32 まとめ Plannerは以下の最適化機構を持つ 高速化にはインデックスと統計情報が重要 Plannerのデバッグ手法を示した
ルールベース 処理しやすい形へSQLを書き換え 条件句や定数式の事前評価 コストベース DP:動的計画法 GEQO:遺伝的アルゴリズム 高速化にはインデックスと統計情報が重要 統計情報を適切に更新すべし Plannerが対応した形のクエリを発行すべし Plannerのデバッグ手法を示した