クエリオプティマイザの原典(と思う)

P. Selinger, et. al. "Access Path Selection in a Relational Database Management System," SIGMOD(1979).

C-Storeで引用されていたクエリオプティマイザの話。読書メモ。多分、この論文がオプティマイザの礎と思う。古い。
System-RというIBMのRDMBの初期実装の中で提案されたコストベースのクエリオプティマイザ。ページ読み込みのコストとストレージAPI呼び出しコストからコスト関数を作成して、いくつもあるアクセスパスの中からコストの低いアクセスパスを選択する。
テーブルのレコード数やページ数、セグメントの中の有効なページ数、インデックスの一意なキー数、インデックスのページ数などを総称を定義。以後、Cardinarityとしておく。
Where句に出てくるさまざまな述語によるSelectivityをCardinarityを用いて定義している。
テーブルスキャンをする場合のコスト関数をSelectivetyとCardinarityから、定義している。
Indexを用いたscanや用いないsegment scan、ソートされたことを利用するmerge scanを用いてjoinを行うときに、どのようなアクセスパスが存在するかを具体例と共に提示。各アクセスパスのコストを計算して、低いコストのパスを選択する。joinには、nested loop joinとmerge joinがあり、それらに対するコスト関数を定義。
subqueryの場合、通常は、subqueryから先に実行する。但し、親クエリの結果を参照するようなサブクエリの場合は、親クエリから行う。

明確な定義が書いてあるので、利用しやすいと思う。hash joinがまだなかったんだなあと思った。