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>) AS (
    SELECT t.id, t.link, t.data, <emphasis>ARRAY[t.id]</emphasis>
    FROM tree t
  UNION ALL
    SELECT t.id, t.link, t.data, <emphasis>path || t.id</emphasis>
    FROM tree t, search_tree st
    WHERE t.id = st.link
)
SELECT * FROM search_tree <emphasis>ORDER BY path</emphasis>;
</programlisting>
   </para>

   <para>
    In the general case where more than one field needs to be used to identify
    a row, use an array of rows.  For example, if we needed to track fields
    <structfield>f1</structfield> and <structfield>f2</structfield>:

<programlisting>
WITH RECURSIVE search_tree(id, link, data, <emphasis>path</emphasis>) AS (
    SELECT t.id, t.link, t.data, <emphasis>ARRAY[ROW(t.f1, t.f2)]</emphasis>
    FROM tree t
  UNION ALL
    SELECT t.id, t.link, t.data, <emphasis>path || ROW(t.f1, t.f2)</emphasis>
    FROM tree t, search_tree st
    WHERE t.id = st.link
)
SELECT * FROM search_tree <emphasis>ORDER BY path</emphasis>;
</programlisting>
   </para>

   <tip>
    <para>
     Omit the <literal>ROW()</literal> syntax in the common case where only one
     field needs to be tracked.  This allows a simple array rather than a
     composite-type array to be used, gaining efficiency.
    </para>
   </tip>

   <para>
    To create a breadth-first order, you can add a column that tracks the depth
    of the search, for example:

<programlisting>
WITH RECURSIVE search_tree(id, link, data, <emphasis>depth</emphasis>) AS (
    SELECT t.id, t.link, t.data, <emphasis>0</emphasis>
    FROM tree t
  UNION ALL
    SELECT t.id, t.link, t.data, <emphasis>depth + 1</emphasis>
    FROM tree t, search_tree st
    WHERE t.id = st.link
)
SELECT * FROM search_tree <emphasis>ORDER BY depth</emphasis>;
</programlisting>

    To get a stable sort, add data columns as secondary sorting columns.
   </para>

   <tip>
    <para>
     The recursive query evaluation algorithm produces its output in
     breadth-first search order.  However, this is an implementation detail and
     it is perhaps unsound to rely on it.  The order of the rows within each
     level is certainly undefined, so some explicit ordering might be desired
     in any case.
    </para>
   </tip>

   <para>
    There is built-in syntax to compute a depth- or breadth-first sort column.
    For example:

<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
) <emphasis>SEARCH DEPTH FIRST BY id SET ordercol</emphasis>
SELECT * FROM search_tree ORDER BY ordercol;

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
) <emphasis>SEARCH BREADTH FIRST BY id SET ordercol</emphasis>
SELECT * FROM search_tree ORDER BY ordercol;
</programlisting>
    This syntax is internally expanded to something similar