クエリ最適化
注意すべき点として、このアルゴリズムでは interesting order と呼ばれるソートされた結果を生成するクエリ実行計画も保持しているのである。動的計画法では、あるクエリ実行計画と別のクエリ実行計画が同じコストならソート順がよい方を選ぶ。 これは2つの理由により行われる。まず、特定のソート順ではクエリ処理の後の方で余分なソートをする必要がなくなる。そして、うまくソートされた結果は、データがかたまっているため、その後の結合が高速化される可能性がある。
歴史的には、System Rのクエリ最適化はleft-deepクエリ実行計画のみを考慮していた(左側から順に実行するものとする方式)。すなわち、2つの関係 (表) の結合をまず行って、その結果と別の関係 (表) を結合していく。このヒューリスティックは考慮すべき計画数を減らすが(n! から 4^n)、最適なクエリ実行計画を見逃す可能性がある。このヒューリスティックは入れ子ループなどの結合アルゴリズムでは、一度には外の関係の1つのタプル(別名「行」)のみを必要とするという観測結果から出てきたものである。従ってleft-deepクエリ実行計画では常にメモリ上に保持すべきタプル数が少なくて済み、外側の関係との結合計画は1つのタプルが生成されるまで行えばよく、その後内側の関係を検索する(これを「パイプライン」と呼ぶ)。
その後、クエリ最適化は、結合演算子の両方のオペランドが別の結合の中間結果であるような複雑なクエリ実行計画にも拡張された。そのような計画は並列コンピュータでは分割して並行に計算できるので、特に重要となってきた。