要約

  • System Rが選んだのは、列挙器が検討した候補の中で推定費用が最小の計画だった。ページ取得数とストレージ・インターフェース呼び出し数を重み付けした値であり、未来の経過時間を測ったものではない。
  • 選択率の誤差は基数に伝わり、アクセス経路、結合順序、物理演算子の評価を変える。「興味深い順序」を残す考え方は、局所的に高い経路が後段のソートを省く可能性を守った。
  • SelingerはMorton Astrahan、Donald Chamberlin、Raymond Lorie、Thomas Priceらとの共同成果を組織した。持続したのは無謬な予言ではなく、仮定、選択、実測を分けて検証できる意思決定構造である。

同じ答えへ向かう異なる機械

注文、顧客、地域を結合し、期間で絞り、売上を集計する問い合わせを考える。関係モデルが定める答えは一つだ。インデックスを使っても表を走査しても、顧客から結合しても地域から始めても、正しい実装なら同じ行と集計を返す。

しかし物理的な経験は異なる。ある経路は選択性の高いインデックスから少数の行だけを読み、後の集約に都合のよい順序まで運ぶ。別の経路は大きな表を読み、中間結果を膨らませ、最後にソートする。意味は等価でも、時間と資源は等価ではない。

計画を選ぶ時点では、その実行はまだ起きていない。必要なページがキャッシュにあるか、特定のパラメータが何行に一致するか、並行処理がI/Oを奪うか、中間結果がメモリーからこぼれるかは完全には分からない。オプティマイザーは統計、仮定、式、重み、そして限られた探索結果から決める。

したがって「最安」はモデル内の順位である。実行後に初めて、実行行数、読み取り、CPU、メモリー、経過時間が観測される。この二つを混同すると、予測が事実のように扱われる。

宣言型言語が生んだ統制の空白

SQLでは、利用者は求める結果を記述し、ストレージ操作の順序を書かない。この分離によって、索引やデータ量、機器が変わっても同じ問い合わせを再計画できる。一方で、物理経路を決める権限はデータベースへ移る。

1979年の論文 Access Path Selection in a Relational Database Management System は処理を四段階に分けた。解析が内部表現を作り、最適化がアクセス仕様を選び、コード生成が実行可能な形に変え、その後で実行する。順序は本質的である。最適化は、当該実行の観測値が存在する前に行われる。

アクセス仕様は論理的意味の言い換えではない。どの関係を先に読むか、セグメント走査か索引か、どの結合順序か、どの並びを維持するかを決める。意味の正しさと物理的な経済性は別の層にある。正しいが遅い計画はあり得る。同じ正しい結果を、全く異なる費用で作る計画もある。

一度速かったという事実も一般的な最適性を証明しない。パラメータ、バッファー、同時実行、分布が変われば、物理的な勝者は変わる。

カタログ統計という圧縮された現実

System Rは計画のために表全体を先に読むのではなく、カタログ統計を用いた。論文は、関係のタプル数 NCARD、占有ページ数 TCARD、ページ占有に関わる P、索引の異なるキー数 ICARD、索引ページ数 NINDX を挙げる。

これらは巨大なデータを意思決定可能な大きさへ圧縮する。同時に詳細を捨てる。統計は UPDATE STATISTICS で初期化され、定期的に更新された。すべてのデータ変更後に同期しない理由として、カタログ更新とロックの費用が明記されている。

古い統計は単なる運用怠慢ではない。観測には価格がある。完全で常時同期した記述は維持費が高すぎる。安い要約は現実からずれる。最適化は、観測の精度と維持費の間で最初から取引している。

現在のシステムでも、サンプル量、ヒストグラム、複数列の相関、パーティション差、採取時刻が見える範囲を決める。統計はデータそのものではなく、計画のために選ばれた証拠である。

選択率から基数へ誤差が流れる

System Rは述語に選択率を与えた。条件を通過すると予想されるタプルの割合である。索引付き等価条件なら異なるキー数を使えるが、情報が乏しい条件には既定値が必要だった。論文の例は、索引のない等価条件を10分の1、片側範囲を3分の1、閉範囲を4分の1とする。

著者は、これらの数に粗い順位付け以上の意味はないと書いた。データベースの自然法則ではなく、情報不足でも前へ進むための仮定である。

ANDで結ばれた条件の選択率は掛け合わせられる。その簡潔さは独立性を仮定する。住所と郵便番号、商品群と価格、契約種別と期間は独立でないことが多い。相関を無視した積は、現実に多い組み合わせを極端に少なく見せたり、その逆を起こしたりする。

基数は割合を行数へ変換する。QCARDの考え方は関係の大きさと選択率を組み合わせ、その出力が後続演算子の費用に入る。外側入力を小さく見積もれば、ネステッドループは安く見える。実際には多数の外側行が同じ作業を反復する。フィルターを大きく見積もりすぎれば、本来は少数ページで済む索引経路が捨てられる。

選択率は比率、基数は数量であり、同義ではない。初期のわずかな比率誤差が入力規模と掛け合わされ、結合順序、演算子、メモリー、ソートへ連鎖する。

Leisらの2015年研究は、小さな費用式の誤差より基数推定の誤差が計画品質を損なう場合が多いと示した。2025年の回顧でも、基数、頑健性、適応は未解決の中心課題である。1979年に作られた鎖の弱点が現在も観測されている。

費用は時計ではなく比較通貨

System Rの式は簡潔だった。

COST = PAGE FETCHES + W × (RSI CALLS)

ページ取得はI/Oを、Research Storage Interfaceの呼び出しはCPU作業を近似し、W が交換比率を与える。CPUを含めたことは重要な進歩だが、異種資源の和は秒数ではない。

どのページがメモリーにあるか、読み取りが連続するか、競合があるか、結果がディスクへこぼれるか、クライアントが全件を読むかを完全には表せない。式の役割は候補を同じ通貨で並べることだった。

モデル内で低いものを「安い」と呼ぶのは正確である。それが「速い」は検証すべき仮説である。「最適」と呼ぶなら、何を最小化し、どの候補を探索したかを示さなければならない。

現在のPostgreSQL文書も同じ区別を保つ。費用単位は環境依存の慣習値で、ミリ秒ではない。EXPLAIN は実行せず推定を表示し、EXPLAIN ANALYZE は実行して実際の行数と時間を加える。前者が選択時の理由、後者が実証である。

アクセス経路、演算子、結合順序

「計画」という一語には複数の決定がある。アクセス経路は基本関係へどう到達するかを決める。物理演算子は結合、ソート、集約の方法を決める。結合順序はどの関係を先に組み合わせ、中間結果をどの大きさにするかを決める。

索引は絞り込みだけでなく順序も供給できる。早い段階の選択的結合は後段全体を小さくする。小入力向けの演算子は、基数が誤っていれば破綻する。現在のソート費用が後のソートを消すこともある。

したがって、遅い問い合わせを「オプティマイザーが間違えた」で終わらせてはならない。アクセス手段が欠けたのか、基数が順序を変えたのか、演算子の閾値を越えたのか、有用な物理属性を失ったのかを分ける必要がある。

興味深い順序が守った将来価値

ある索引経路が直近の関係だけ見れば走査より高くても、結合キー、GROUP BY、最終 ORDER BY の順序を運べば後段のソートを省ける。局所最低だけを残すと、全体では悪い計画になる。

System Rは最安の無順序計画に加え、各「興味深い順序」について最安の計画を保持した。同じ関係部分集合から同じ行を出しても、後段で価値を持つ順序が違えば、物理的には同じ候補ではない。

順序は将来の選択肢である。今少し多く払って、後の大きな作業を回避できる。この考えは最適化が単純な局所貪欲法でないことを示す。

同時に、何を保存するかにも規律を与えた。全計画は残せないが、単一の勝者だけでは情報を捨てすぎる。結果集合と有用な物理属性の組み合わせが比較単位になった。

探索にも予算がある

関係が増えると結合順序は組合せ爆発する。すべての順列を試せば階乗的に増える。実行時間を節約するための探索が、問い合わせより長くなっては意味がない。

System Rは動的計画法を使った。関係部分集合ごとに、興味深い順序を含む最良代表を保存し、より大きな部分集合を作る時に再利用した。結合条件のない直積は大きな中間結果を作りやすいため、必要になるまで遅らせた。

論文は、探索を部分集合と興味深い順序の組み合わせとして抑え、IBM 370/158で八表結合を数秒で最適化できたと報告する。これは探索空間を巧みに設計した成果である。

ただし枝刈りは、想像可能な全物理計画を調べた証明ではない。動的計画法が最良を保証するのは、列挙器、演算子、木の形、等価変換、保持規則が定めた空間内である。大域最適性を語るなら、その境界を省けない。

最適化時間と実行時間も別の費用である。高価な分析には広い探索が有益だが、短い反復問い合わせでは探索費が支配する。汎用の準備済み計画は計画時間を節約する一方、理想経路がパラメータに依存する時は不利になり得る。

誤差を隠さなかった

1979年論文は、予測費用の絶対値がしばしば正確でないと認めた。同時に、試したアクセス経路の中で実際に最良のものを多数の場合に選び、さらに検証が必要だとした。校正が不完全でも順位付けが役立つことは矛盾しない。

1986年、MackertとLohmanはR*の推定資源と実測を比較した。I/Oモデルの多くは機能したが、CPUは詳細化が必要だった。バッファー仮定が結果を左右し、ネステッドループは結合基数、外側基数、利用可能ページが絡むため難しかった。

この検証は、数式を権威から仮説へ戻す。差が集中する場所を見れば、統計、係数、演算子仮定、フィードバックを改良できる。

IBMの後のジャストインタイム統計も同じ姿勢である。独立に収集された統計が欠けたり古くなったりした時、最適化中に必要な観測を狙って取得する。すべてを知るのではなく、意思決定価値が採取費を上回る情報を買う。

一人の神話ではなく、組織された共同作業

Patricia G. Selingerは1975年にIBM Researchへ入った。IBMの歴史は、彼女がSystem R最適化を率い、その後R*やデータベース技術組織を担ったと記す。1994年にIBM Fellow、1999年に米国National Academy of Engineering会員となり、2018年にIBMを退職した。

1979年論文はP. Griffiths Selingerを筆頭に、Morton M. Astrahanと共同で書かれ、さらにDonald D. Chamberlin、Raymond A. Lorie、そしてThomas G. Priceが著者に加わった。Chamberlinは口述史で、Selingerが最適化作業と重要論文を組織したと述べつつ、Lorie、Price、Astrahanの重要な貢献を明記した。IBMの広い歴史には、Edgar Coddの関係モデル、ChamberlinとRaymond BoyceのSQL、Lorieのコンパイラー、System R全体の仕事がある。

共同性はSelingerの指導性を弱めない。統計、選択率、基数、費用、物理属性、探索を実装可能な契約へまとめた点にこそ指導の中身がある。明示的な規則と動的計画法の成果を、後世の流行語で「AI」と呼ぶ必要もない。

修正できることが強さだった

永遠に正しい経路を見つけたのではない。問い合わせの意味を安定させたまま、物理的な方法を入れ替えられる層を作った。統計を豊かにし、相関を扱い、費用重みを変え、新しい演算子を加え、実行フィードバックを使っても、利用者の宣言は保てる。

選ばれた計画は「承認された予測」と呼ぶのが正確だ。利用可能な証拠と実装済みの探索の中で勝ったから実行される。現実に勝ったことは、まだ証明されていない。

推定と実測の両方を保存すれば、差から学べる。成熟したオプティマイザーは無謬を装わず、何を信じ、何を選び、何が起きたかを区別する。

出典