<literal>UNION</literal> (or
   <literal>UNION ALL</literal>), then a
   <firstterm>recursive term</firstterm>, where only the recursive term can contain
   a reference to the query's own output.  Such a query is executed as
   follows:
  </para>

  <procedure>
   <title>Recursive Query Evaluation</title>

   <step performance="required">
    <para>
     Evaluate the non-recursive term.  For <literal>UNION</literal> (but not
     <literal>UNION ALL</literal>), discard duplicate rows.  Include all remaining
     rows in the result of the recursive query, and also place them in a
     temporary <firstterm>working table</firstterm>.
    </para>
   </step>

   <step performance="required">
    <para>
     So long as the working table is not empty, repeat these steps:
    </para>
    <substeps>
     <step performance="required">
      <para>
       Evaluate the recursive term, substituting the current contents of
       the working table for the recursive self-reference.
       For <literal>UNION</literal> (but not <literal>UNION ALL</literal>), discard
       duplicate rows and rows that duplicate any previous result row.
       Include all remaining rows in the result of the recursive query, and
       also place them in a temporary <firstterm>intermediate table</firstterm>.
      </para>
     </step>

     <step performance="required">
      <para>
       Replace the contents of the working table with the contents of the
       intermediate table, then empty the intermediate table.
      </para>
     </step>
    </substeps>
   </step>
  </procedure>

  <note>
   <para>
    While <literal>RECURSIVE</literal> allows queries to be specified
    recursively, internally such queries are evaluated iteratively.
   </para>
  </note>

  <para>
   In the example above, the working table has just a single row in each step,
   and it takes on the values from 1 through 100 in successive steps.  In
   the 100th step, there is no output because of the <literal>WHERE</literal>
   clause, and so the query terminates.
  </para>

  <para>
   Recursive queries are typically used to deal with hierarchical or
   tree-structured data.  A useful example is this query to find all the
   direct and indirect sub-parts of a product, given only a table that
   shows immediate inclusions:

<programlisting>
WITH RECURSIVE included_parts(sub_part, part, quantity) AS (
    SELECT sub_part, part, quantity FROM parts WHERE part = 'our_product'
  UNION ALL
    SELECT p.sub_part, p.part, p.quantity * pr.quantity
    FROM included_parts pr, parts p
    WHERE p.part = pr.sub_part
)
SELECT sub_part, SUM(quantity) as total_quantity
FROM included_parts
GROUP BY sub_part
</programlisting>
  </para>

  <sect3 id="queries-with-search">
   <title>Search Order</title>

   <para>
    When computing a tree traversal using a recursive query, you might want to
    order the results in either depth-first or breadth-first order.  This can
    be done by computing an ordering column alongside the other data columns
    and using that to sort the results at the end.  Note that this does not
    actually control in which order the query evaluation visits the rows; that
    is as always in SQL implementation-dependent.  This approach merely
    provides a convenient way to order the results afterwards.
   </para>

   <para>
    To create a depth-first order, we compute for each result row an array of
    rows that we have visited so far.  For example, consider the following
    query that searches a table <structname>tree</structname> using a
    <structfield>link</structfield> field:

<programlisting>
WITH RECURSIVE search_tree(id, link, data) AS (
    SELECT t.id, t.link, t.data
    FROM tree t
  UNION ALL
    SELECT t.id, t.link, t.data
    FROM tree t, search_tree st
    WHERE t.id = st.link
)
SELECT * FROM search_tree;
</programlisting>

    To add depth-first ordering information, you can write this:

<programlisting>
WITH RECURSIVE search_tree(id, link, data, <emphasis>path</emphasis>)