Home • Explore • Blog • CI
☰



postgresql
6th chunk of `doc/src/sgml/arch-dev.sgml`
1844409164c73c9065d3e152529805b6bbe877c3c3a0905e0000000100000fa3
 detail for the executor to run it.
    In the rest of this section we'll ignore the distinction between paths
    and plans.
   </para>

   <sect2 id="planner-optimizer-generating-possible-plans">
    <title>Generating Possible Plans</title>

    <para>
     The planner/optimizer starts by generating plans for scanning each
     individual relation (table) used in the query.  The possible plans
     are determined by the available indexes on each relation.
     There is always the possibility of performing a
     sequential scan on a relation, so a sequential scan plan is always
     created. Assume an index is defined on a
     relation (for example a B-tree index) and a query contains the
     restriction
     <literal>relation.attribute OPR constant</literal>. If
     <literal>relation.attribute</literal> happens to match the key of the B-tree
     index and <literal>OPR</literal> is one of the operators listed in
     the index's <firstterm>operator class</firstterm>, another plan is created using
     the B-tree index to scan the relation. If there are further indexes
     present and the restrictions in the query happen to match a key of an
     index, further plans will be considered.  Index scan plans are also
     generated for indexes that have a sort ordering that can match the
     query's <literal>ORDER BY</literal> clause (if any), or a sort ordering that
     might be useful for merge joining (see below).
    </para>

    <para>
     If the query requires joining two or more relations,
     plans for joining relations are considered
     after all feasible plans have been found for scanning single relations.
     The three available join strategies are:

     <itemizedlist>
      <listitem>
       <para>
        <firstterm>nested loop join</firstterm>: The right relation is scanned
        once for every row found in the left relation. This strategy
        is easy to implement but can be very time consuming.  (However,
        if the right relation can be scanned with an index scan, this can
        be a good strategy.  It is possible to use values from the current
        row of the left relation as keys for the index scan of the right.)
       </para>
      </listitem>

      <listitem>
       <para>
        <firstterm>merge join</firstterm>: Each relation is sorted on the join
        attributes before the join starts. Then the two relations are
        scanned in parallel, and matching rows are combined to form
        join rows. This kind of join is
        attractive because each relation has to be scanned only once.
        The required sorting might be achieved either by an explicit sort
        step, or by scanning the relation in the proper order using an
        index on the join key.
       </para>
      </listitem>

      <listitem>
       <para>
        <firstterm>hash join</firstterm>: the right relation is first scanned
        and loaded into a hash table, using its join attributes as hash keys.
        Next the left relation is scanned and the
        appropriate values of every row found are used as hash keys to
        locate the matching rows in the table.
       </para>
      </listitem>
     </itemizedlist>
    </para>

    <para>
     When the query involves more than two relations, the final result
     must be built up by a tree of join steps, each with two inputs.
     The planner examines different possible join sequences to find the
     cheapest one.
    </para>

    <para>
     If the query uses fewer than <xref linkend="guc-geqo-threshold"/>
     relations, a near-exhaustive search is conducted to find the best
     join sequence.  The planner preferentially considers joins between any
     two relations for which there exists a corresponding join clause in the
     <literal>WHERE</literal> qualification (i.e., for
     which a restriction like <literal>where rel1.attr1=rel2.attr2</literal>
     exists). Join pairs with no join clause are considered only when there
     is no other
Title: Generating and Evaluating Query Plans
Summary
The planner/optimizer generates query plans by considering various scan methods for each relation, including sequential scans and index scans based on available indexes and query restrictions. Index scans are also considered if the index sort order matches the query's ORDER BY clause or is useful for merge joining. For queries involving multiple relations, the planner explores different join strategies: nested loop join, merge join, and hash join. The choice of join strategy depends on the characteristics of the relations and the query. When joining more than two relations, the planner evaluates different join sequences to find the most efficient one. For queries with fewer relations than the geqo_threshold, a near-exhaustive search is performed, prioritizing joins with explicit join clauses in the WHERE qualification.