Implement SQL-standard WITH clauses, including WITH RECURSIVE.

There are some unimplemented aspects: recursive queries must use UNION ALL
(should allow UNION too), and we don't have SEARCH or CYCLE clauses.
These might or might not get done for 8.4, but even without them it's a
pretty useful feature.

There are also a couple of small loose ends and definitional quibbles,
which I'll send a memo about to pgsql-hackers shortly.  But let's land
the patch now so we can get on with other development.

Yoshiyuki Asaba, with lots of help from Tatsuo Ishii and Tom Lane

4 files changed, 372 insertions, 49 deletions

diff --git a/doc/src/sgml/errcodes.sgml b/doc/src/sgml/errcodes.sgml
index 474c0ca8da7..574e7f5fbad 100644
--- a/doc/src/sgml/errcodes.sgml
+++ b/doc/src/sgml/errcodes.sgml
@@ -1,4 +1,4 @@
-<!-- $PostgreSQL: pgsql/doc/src/sgml/errcodes.sgml,v 1.24 2008/05/15 22:39:48 tgl Exp $ -->
+<!-- $PostgreSQL: pgsql/doc/src/sgml/errcodes.sgml,v 1.25 2008/10/04 21:56:52 tgl Exp $ -->
 
 <appendix id="errcodes-appendix">
  <title><productname>PostgreSQL</productname> Error Codes</title>
@@ -991,6 +991,12 @@
 </row>
 
 <row>
+<entry><literal>42P19</literal></entry>
+<entry>INVALID RECURSION</entry>
+<entry>invalid_recursion</entry>
+</row>
+
+<row>
 <entry><literal>42830</literal></entry>
 <entry>INVALID FOREIGN KEY</entry>
 <entry>invalid_foreign_key</entry>
diff --git a/doc/src/sgml/queries.sgml b/doc/src/sgml/queries.sgml
index e3b6be4d97b..b3d72ceb7f8 100644
--- a/doc/src/sgml/queries.sgml
+++ b/doc/src/sgml/queries.sgml
@@ -1,4 +1,4 @@
-<!-- $PostgreSQL: pgsql/doc/src/sgml/queries.sgml,v 1.45 2008/02/15 22:17:06 tgl Exp $ -->
+<!-- $PostgreSQL: pgsql/doc/src/sgml/queries.sgml,v 1.46 2008/10/04 21:56:52 tgl Exp $ -->
 
 <chapter id="queries">
  <title>Queries</title>
@@ -28,10 +28,11 @@
    used to specify queries.  The general syntax of the
    <command>SELECT</command> command is
 <synopsis>
-SELECT <replaceable>select_list</replaceable> FROM <replaceable>table_expression</replaceable> <optional><replaceable>sort_specification</replaceable></optional>
+<optional>WITH <replaceable>with_queries</replaceable></optional> SELECT <replaceable>select_list</replaceable> FROM <replaceable>table_expression</replaceable> <optional><replaceable>sort_specification</replaceable></optional>
 </synopsis>
    The following sections describe the details of the select list, the
-   table expression, and the sort specification.
+   table expression, and the sort specification.  <literal>WITH</>
+   queries are treated last since they are an advanced feature.
   </para>
 
   <para>
@@ -107,7 +108,7 @@ SELECT random();
 
   <sect2 id="queries-from">
    <title>The <literal>FROM</literal> Clause</title>
- 
+
    <para>
     The <xref linkend="sql-from" endterm="sql-from-title"> derives a
     table from one or more other tables given in a comma-separated
@@ -211,7 +212,7 @@ FROM <replaceable>table_reference</replaceable> <optional>, <replaceable>table_r
 <replaceable>T1</replaceable> { <optional>INNER</optional> | { LEFT | RIGHT | FULL } <optional>OUTER</optional> } JOIN <replaceable>T2</replaceable> USING ( <replaceable>join column list</replaceable> )
 <replaceable>T1</replaceable> NATURAL { <optional>INNER</optional> | { LEFT | RIGHT | FULL } <optional>OUTER</optional> } JOIN <replaceable>T2</replaceable>
 </synopsis>
-        
+
        <para>
         The words <literal>INNER</literal> and
         <literal>OUTER</literal> are optional in all forms.
@@ -303,7 +304,7 @@ FROM <replaceable>table_reference</replaceable> <optional>, <replaceable>table_r
           </para>
          </listitem>
         </varlistentry>
-         
+
         <varlistentry>
          <term><literal>RIGHT OUTER JOIN</></term>
 
@@ -326,7 +327,7 @@ FROM <replaceable>table_reference</replaceable> <optional>, <replaceable>table_r
           </para>
          </listitem>
         </varlistentry>
-         
+
         <varlistentry>
          <term><literal>FULL OUTER JOIN</></term>
 
@@ -1042,7 +1043,7 @@ SELECT a AS value, b + c AS sum FROM ...
    <para>
     If no output column name is specified using <literal>AS</>,
     the system assigns a default column name.  For simple column references,
-    this is the name of the referenced column.  For function 
+    this is the name of the referenced column.  For function
     calls, this is the name of the function.  For complex expressions,
     the system will generate a generic name.
    </para>
@@ -1302,7 +1303,7 @@ SELECT a, max(b) FROM table1 GROUP BY a ORDER BY 1;
 <programlisting>
 SELECT a + b AS sum, c FROM table1 ORDER BY sum + c;          -- wrong
 </programlisting>
-   This restriction is made to reduce ambiguity.  There is still 
+   This restriction is made to reduce ambiguity.  There is still
    ambiguity if an <literal>ORDER BY</> item is a simple name that
    could match either an output column name or a column from the table
    expression.  The output column is used in such cases.  This would
@@ -1455,4 +1456,185 @@ SELECT <replaceable>select_list</replaceable> FROM <replaceable>table_expression
 
  </sect1>
 
+
+ <sect1 id="queries-with">
+  <title><literal>WITH</literal> Queries</title>
+
+  <indexterm zone="queries-with">
+   <primary>WITH</primary>
+   <secondary>in SELECT</secondary>
+  </indexterm>
+
+  <indexterm>
+   <primary>common table expression</primary>
+   <see>WITH</see>
+  </indexterm>
+
+  <para>
+   <literal>WITH</> provides a way to write subqueries for use in a larger
+   <literal>SELECT</> query.  The subqueries can be thought of as defining
+   temporary tables that exist just for this query.  One use of this feature
+   is to break down complicated queries into simpler parts.  An example is:
+
+<programlisting>
+WITH regional_sales AS (
+        SELECT region, SUM(amount) AS total_sales
+        FROM orders
+        GROUP BY region
+     ), top_regions AS (
+        SELECT region
+        FROM regional_sales
+        WHERE total_sales &gt; (SELECT SUM(total_sales)/10 FROM regional_sales)
+     )
+SELECT region,
+       product,
+       SUM(quantity) AS product_units,
+       SUM(amount) AS product_sales
+FROM orders
+WHERE region IN (SELECT region FROM top_regions)
+GROUP BY region, product;
+</programlisting>
+
+   which displays per-product sales totals in only the top sales regions.
+   This example could have been written without <literal>WITH</>,
+   but we'd have needed two levels of nested sub-SELECTs.  It's a bit
+   easier to follow this way.
+  </para>
+
+  <para>
+   The optional <literal>RECURSIVE</> modifier changes <literal>WITH</>
+   from a mere syntactic convenience into a feature that accomplishes
+   things not otherwise possible in standard SQL.  Using
+   <literal>RECURSIVE</>, a <literal>WITH</> query can refer to its own
+   output.  A very simple example is this query to sum the integers from 1
+   through 100:
+
+<programlisting>
+WITH RECURSIVE t(n) AS (
+    VALUES (1)
+  UNION ALL
+    SELECT n+1 FROM t WHERE n &lt; 100
+)
+SELECT sum(n) FROM t;
+</programlisting>
+
+   The general form of a recursive <literal>WITH</> query is always a
+   <firstterm>non-recursive term</>, then <literal>UNION ALL</>, then a
+   <firstterm>recursive term</>, 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.  Include all its output rows in the
+     result of the recursive query, and also place them in a temporary
+     <firstterm>working table</>.
+    </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.  Include all its
+       output rows in the result of the recursive query, and also place them
+       in a temporary <firstterm>intermediate table</>.
+      </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>
+    Strictly speaking, this process is iteration not recursion, but
+    <literal>RECURSIVE</> is the terminology chosen by the SQL standards
+    committee.
+   </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</>
+   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
+    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>
+
+  <para>
+   When working with recursive queries it is important to be sure that
+   the recursive part of the query will eventually return no tuples,
+   or else the query will loop indefinitely.  A useful trick for
+   development purposes is to place a <literal>LIMIT</> in the parent
+   query.  For example, this query would loop forever without the
+   <literal>LIMIT</>:
+
+<programlisting>
+WITH RECURSIVE t(n) AS (
+    SELECT 1
+  UNION ALL
+    SELECT n+1 FROM t
+)
+SELECT n FROM t LIMIT 100;
+</programlisting>
+
+   This works because <productname>PostgreSQL</productname>'s implementation
+   evaluates only as many rows of a <literal>WITH</> query as are actually
+   demanded by the parent query.  Using this trick in production is not
+   recommended, because other systems might work differently.
+  </para>
+
+  <para>
+   A useful property of <literal>WITH</> queries is that they are evaluated
+   only once per execution of the parent query, even if they are referred to
+   more than once by the parent query or sibling <literal>WITH</> queries.
+   Thus, expensive calculations that are needed in multiple places can be
+   placed within a <literal>WITH</> query to avoid redundant work.  Another
+   possible application is to prevent unwanted multiple evaluations of
+   functions with side-effects.
+   However, the other side of this coin is that the optimizer is less able to
+   push restrictions from the parent query down into a <literal>WITH</> query
+   than an ordinary sub-query.  The <literal>WITH</> query will generally be
+   evaluated as stated, without suppression of rows that the parent query
+   might discard afterwards.  (But, as mentioned above, evaluation might stop
+   early if the reference(s) to the query demand only a limited number of
+   rows.)
+  </para>
+
+ </sect1>
+
 </chapter>
diff --git a/doc/src/sgml/ref/select.sgml b/doc/src/sgml/ref/select.sgml
index d8ed7aef9c6..e72d9c126f6 100644
--- a/doc/src/sgml/ref/select.sgml
+++ b/doc/src/sgml/ref/select.sgml
@@ -1,5 +1,5 @@
 <!--
-$PostgreSQL: pgsql/doc/src/sgml/ref/select.sgml,v 1.104 2008/09/23 09:20:35 heikki Exp $
+$PostgreSQL: pgsql/doc/src/sgml/ref/select.sgml,v 1.105 2008/10/04 21:56:52 tgl Exp $
 PostgreSQL documentation
 -->
 
@@ -20,6 +20,7 @@ PostgreSQL documentation
 
  <refsynopsisdiv>
 <synopsis>
+[ WITH [ RECURSIVE ] <replaceable class="parameter">with_query</replaceable> [, ...] ]
 SELECT [ ALL | DISTINCT [ ON ( <replaceable class="parameter">expression</replaceable> [, ...] ) ] ]
     * | <replaceable class="parameter">expression</replaceable> [ [ AS ] <replaceable class="parameter">output_name</replaceable> ] [, ...]
     [ FROM <replaceable class="parameter">from_item</replaceable> [, ...] ]
@@ -36,9 +37,14 @@ where <replaceable class="parameter">from_item</replaceable> can be one of:
 
     [ ONLY ] <replaceable class="parameter">table_name</replaceable> [ * ] [ [ AS ] <replaceable class="parameter">alias</replaceable> [ ( <replaceable class="parameter">column_alias</replaceable> [, ...] ) ] ]
     ( <replaceable class="parameter">select</replaceable> ) [ AS ] <replaceable class="parameter">alias</replaceable> [ ( <replaceable class="parameter">column_alias</replaceable> [, ...] ) ]
+    <replaceable class="parameter">with_query_name</replaceable> [ [ AS ] <replaceable class="parameter">alias</replaceable> [ ( <replaceable class="parameter">column_alias</replaceable> [, ...] ) ] ]
     <replaceable class="parameter">function_name</replaceable> ( [ <replaceable class="parameter">argument</replaceable> [, ...] ] ) [ AS ] <replaceable class="parameter">alias</replaceable> [ ( <replaceable class="parameter">column_alias</replaceable> [, ...] | <replaceable class="parameter">column_definition</replaceable> [, ...] ) ]
     <replaceable class="parameter">function_name</replaceable> ( [ <replaceable class="parameter">argument</replaceable> [, ...] ] ) AS ( <replaceable class="parameter">column_definition</replaceable> [, ...] )
     <replaceable class="parameter">from_item</replaceable> [ NATURAL ] <replaceable class="parameter">join_type</replaceable> <replaceable class="parameter">from_item</replaceable> [ ON <replaceable class="parameter">join_condition</replaceable> | USING ( <replaceable class="parameter">join_column</replaceable> [, ...] ) ]
+
+and <replaceable class="parameter">with_query</replaceable> is:
+
+    <replaceable class="parameter">with_query_name</replaceable> [ ( <replaceable class="parameter">column_name</replaceable> [, ...] ) ] AS ( <replaceable class="parameter">select</replaceable> )
 </synopsis>
 
  </refsynopsisdiv>
@@ -53,6 +59,17 @@ where <replaceable class="parameter">from_item</replaceable> can be one of:
    <orderedlist>
     <listitem>
      <para>
+      All queries in the <literal>WITH</literal> list are computed.
+      These effectively serve as temporary tables that can be referenced
+      in the <literal>FROM</literal> list.  A <literal>WITH</literal> query
+      that is referenced more than once in <literal>FROM</literal> is
+      computed only once.
+      (See <xref linkend="sql-with" endterm="sql-with-title"> below.)
+     </para>
+    </listitem>
+
+    <listitem>
+     <para>
       All elements in the <literal>FROM</literal> list are computed.
       (Each element in the <literal>FROM</literal> list is a real or
       virtual table.)  If more than one element is specified in the
@@ -163,6 +180,56 @@ where <replaceable class="parameter">from_item</replaceable> can be one of:
  <refsect1>
   <title>Parameters</title>
 
+  <refsect2 id="SQL-WITH">
+   <title id="sql-with-title"><literal>WITH</literal> Clause</title>
+
+   <para>
+    The <literal>WITH</literal> clause allows you to specify one or more
+    subqueries that can be referenced by name in the primary query.
+    The subqueries effectively act as temporary tables or views
+    for the duration of the primary query.
+   </para>
+
+   <para>
+    A name (without schema qualification) must be specified for each
+    <literal>WITH</literal> query.  Optionally, a list of column names
+    can be specified; if this is omitted,
+    the column names are inferred from the subquery.
+   </para>
+
+   <para>
+    If <literal>RECURSIVE</literal> is specified, it allows a
+    subquery to reference itself by name.  Such a subquery must have
+    the form
+<synopsis>
+<replaceable class="parameter">non_recursive_term</replaceable> UNION ALL <replaceable class="parameter">recursive_term</replaceable>
+</synopsis>
+    where the recursive self-reference must appear on the right-hand
+    side of <literal>UNION ALL</>.  Only one recursive self-reference
+    is permitted per query.
+   </para>
+
+   <para>
+    Another effect of <literal>RECURSIVE</literal> is that
+    <literal>WITH</literal> queries need not be ordered: a query
+    can reference another one that is later in the list.  (However,
+    circular references, or mutual recursion, are not implemented.)
+    Without <literal>RECURSIVE</literal>, <literal>WITH</literal> queries
+    can only reference sibling <literal>WITH</literal> queries
+    that are earlier in the <literal>WITH</literal> list.
+   </para>
+
+   <para>
+    A useful property of <literal>WITH</literal> queries is that they
+    are evaluated only once per execution of the primary query,
+    even if the primary query refers to them more than once.
+   </para>
+
+   <para>
+    See <xref linkend="queries-with"> for additional information.
+   </para>
+  </refsect2>
+
   <refsect2 id="SQL-FROM">
    <title id="sql-from-title"><literal>FROM</literal> Clause</title>
 
@@ -197,7 +264,7 @@ where <replaceable class="parameter">from_item</replaceable> can be one of:
        </para>
       </listitem>
      </varlistentry>
-     
+
      <varlistentry>
       <term><replaceable class="parameter">alias</replaceable></term>
       <listitem>
@@ -215,7 +282,7 @@ where <replaceable class="parameter">from_item</replaceable> can be one of:
        </para>
       </listitem>
      </varlistentry>
-     
+
      <varlistentry>
       <term><replaceable class="parameter">select</replaceable></term>
       <listitem>
@@ -234,6 +301,21 @@ where <replaceable class="parameter">from_item</replaceable> can be one of:
      </varlistentry>
 
      <varlistentry>
+      <term><replaceable class="parameter">with_query_name</replaceable></term>
+      <listitem>
+       <para>
+        A <literal>WITH</> query is referenced by writing its name,
+        just as though the query's name were a table name.  (In fact,
+        the <literal>WITH</> query hides any real table of the same name
+        for the purposes of the primary query.  If necessary, you can
+        refer to a real table of the same name by schema-qualifying
+        the table's name.)
+        An alias can be provided in the same way as for a table.
+       </para>
+      </listitem>
+     </varlistentry>
+
+     <varlistentry>
       <term><replaceable class="parameter">function_name</replaceable></term>
       <listitem>
        <para>
@@ -256,7 +338,7 @@ where <replaceable class="parameter">from_item</replaceable> can be one of:
        </para>
       </listitem>
      </varlistentry>
-     
+
      <varlistentry>
       <term><replaceable class="parameter">join_type</replaceable></term>
       <listitem>
@@ -339,7 +421,7 @@ where <replaceable class="parameter">from_item</replaceable> can be one of:
        </para>
       </listitem>
      </varlistentry>
-     
+
      <varlistentry>
       <term><literal>ON <replaceable class="parameter">join_condition</replaceable></literal></term>
       <listitem>
@@ -352,7 +434,7 @@ where <replaceable class="parameter">from_item</replaceable> can be one of:
        </para>
       </listitem>
      </varlistentry>
-     
+
      <varlistentry>
       <term><literal>USING ( <replaceable class="parameter">join_column</replaceable> [, ...] )</literal></term>
       <listitem>
@@ -380,7 +462,7 @@ where <replaceable class="parameter">from_item</replaceable> can be one of:
     </variablelist>
    </para>
   </refsect2>
-   
+
   <refsect2 id="SQL-WHERE">
    <title id="sql-where-title"><literal>WHERE</literal> Clause</title>
 
@@ -397,7 +479,7 @@ WHERE <replaceable class="parameter">condition</replaceable>
     substituted for any variable references.
    </para>
   </refsect2>
-  
+
   <refsect2 id="SQL-GROUPBY">
    <title id="sql-groupby-title"><literal>GROUP BY</literal> Clause</title>
 
@@ -444,7 +526,7 @@ HAVING <replaceable class="parameter">condition</replaceable>
     where <replaceable class="parameter">condition</replaceable> is
     the same as specified for the <literal>WHERE</literal> clause.
    </para>
-    
+
    <para>
     <literal>HAVING</literal> eliminates group rows that do not
     satisfy the condition.  <literal>HAVING</literal> is different
@@ -456,7 +538,7 @@ HAVING <replaceable class="parameter">condition</replaceable>
     unambiguously reference a grouping column, unless the reference
     appears within an aggregate function.
    </para>
-    
+
    <para>
     The presence of <literal>HAVING</literal> turns a query into a grouped
     query even if there is no <literal>GROUP BY</> clause.  This is the
@@ -518,7 +600,7 @@ HAVING <replaceable class="parameter">condition</replaceable>
     the output column names will be the same as the table columns' names.
    </para>
   </refsect2>
-  
+
   <refsect2 id="SQL-UNION">
    <title id="sql-union-title"><literal>UNION</literal> Clause</title>
 
@@ -537,7 +619,7 @@ HAVING <replaceable class="parameter">condition</replaceable>
     the <literal>UNION</literal>, not to its right-hand input
     expression.)
    </para>
-    
+
    <para>
     The <literal>UNION</literal> operator computes the set union of
     the rows returned by the involved <command>SELECT</command>
@@ -548,7 +630,7 @@ HAVING <replaceable class="parameter">condition</replaceable>
     number of columns, and corresponding columns must be of compatible
     data types.
    </para>
-    
+
    <para>
     The result of <literal>UNION</> does not contain any duplicate
     rows unless the <literal>ALL</> option is specified.
@@ -556,13 +638,13 @@ HAVING <replaceable class="parameter">condition</replaceable>
     <literal>UNION ALL</> is usually significantly quicker than
     <literal>UNION</>; use <literal>ALL</> when you can.)
    </para>
-    
+
    <para>
     Multiple <literal>UNION</> operators in the same
     <command>SELECT</command> statement are evaluated left to right,
     unless otherwise indicated by parentheses.
    </para>
-    
+
    <para>
     Currently, <literal>FOR UPDATE</> and <literal>FOR SHARE</> cannot be
     specified either for a <literal>UNION</> result or for any input of a
@@ -590,7 +672,7 @@ HAVING <replaceable class="parameter">condition</replaceable>
     <command>SELECT</command> statements.  A row is in the
     intersection of two result sets if it appears in both result sets.
    </para>
-    
+
    <para>
     The result of <literal>INTERSECT</literal> does not contain any
     duplicate rows unless the <literal>ALL</> option is specified.
@@ -598,7 +680,7 @@ HAVING <replaceable class="parameter">condition</replaceable>
     left table and <replaceable>n</> duplicates in the right table will appear
     min(<replaceable>m</>,<replaceable>n</>) times in the result set.
    </para>
-    
+
    <para>
     Multiple <literal>INTERSECT</literal> operators in the same
     <command>SELECT</command> statement are evaluated left to right,
@@ -608,7 +690,7 @@ HAVING <replaceable class="parameter">condition</replaceable>
     C</literal> will be read as <literal>A UNION (B INTERSECT
     C)</literal>.
    </para>
-    
+
    <para>
     Currently, <literal>FOR UPDATE</> and <literal>FOR SHARE</> cannot be
     specified either for an <literal>INTERSECT</> result or for any input of
@@ -635,7 +717,7 @@ HAVING <replaceable class="parameter">condition</replaceable>
     that are in the result of the left <command>SELECT</command>
     statement but not in the result of the right one.
    </para>
-    
+
    <para>
     The result of <literal>EXCEPT</literal> does not contain any
     duplicate rows unless the <literal>ALL</> option is specified.
@@ -643,14 +725,14 @@ HAVING <replaceable class="parameter">condition</replaceable>
     left table and <replaceable>n</> duplicates in the right table will appear
     max(<replaceable>m</>-<replaceable>n</>,0) times in the result set.
    </para>
-    
+
    <para>
     Multiple <literal>EXCEPT</literal> operators in the same
     <command>SELECT</command> statement are evaluated left to right,
     unless parentheses dictate otherwise.  <literal>EXCEPT</> binds at
     the same level as <literal>UNION</>.
    </para>
-    
+
    <para>
     Currently, <literal>FOR UPDATE</> and <literal>FOR SHARE</> cannot be
     specified either for an <literal>EXCEPT</> result or for any input of
@@ -689,7 +771,7 @@ ORDER BY <replaceable class="parameter">expression</replaceable> [ ASC | DESC |
     possible to assign a name to an output column using the
     <literal>AS</> clause.
    </para>
-    
+
    <para>
     It is also possible to use arbitrary expressions in the
     <literal>ORDER BY</literal> clause, including columns that do not
@@ -712,7 +794,7 @@ SELECT name FROM distributors ORDER BY code;
     make in the same situation.  This inconsistency is made to be
     compatible with the SQL standard.
    </para>
-    
+
    <para>
     Optionally one can add the key word <literal>ASC</> (ascending) or
     <literal>DESC</> (descending) after any expression in the
@@ -789,7 +871,7 @@ SELECT DISTINCT ON (location) location, time, report
     desired precedence of rows within each <literal>DISTINCT ON</> group.
    </para>
   </refsect2>
-  
+
   <refsect2 id="SQL-LIMIT">
    <title id="sql-limit-title"><literal>LIMIT</literal> Clause</title>
 
@@ -1106,8 +1188,60 @@ SELECT * FROM distributors_2(111) AS (f1 int, f2 text);
  111 | Walt Disney
 </programlisting>
   </para>
+
+  <para>
+   This example shows how to use a simple <literal>WITH</> clause:
+
+<programlisting>
+WITH t AS (
+    SELECT random() as x FROM generate_series(1, 3)
+  )
+SELECT * FROM t
+UNION ALL
+SELECT * FROM t
+
+         x          
+--------------------
+  0.534150459803641
+  0.520092216785997
+ 0.0735620250925422
+  0.534150459803641
+  0.520092216785997
+ 0.0735620250925422
+</programlisting>
+
+   Notice that the <literal>WITH</> query was evaluated only once,
+   so that we got two sets of the same three random values.
+  </para>
+
+  <para>
+   This example uses <literal>WITH RECURSIVE</literal> to find all
+   subordinates (direct or indirect) of the employee Mary, and their
+   level of indirectness, from a table that shows only direct
+   subordinates:
+
+<programlisting>
+WITH RECURSIVE employee_recursive(distance, employee_name, manager_name) AS (
+    SELECT 1, employee_name, manager_name
+    FROM employee
+    WHERE manager_name = 'Mary'
+  UNION ALL
+    SELECT er.distance + 1, e.employee_name, e.manager_name
+    FROM employee_recursive er, employee e
+    WHERE er.employee_name = e.manager_name
+  )
+SELECT distance, employee_name FROM employee_recursive;
+</programlisting>
+
+   Notice the typical form of recursive queries:
+   an initial condition, followed by <literal>UNION ALL</literal>,
+   followed by the recursive part of the query. Be sure that the
+   recursive part of the query will eventually return no tuples, or
+   else the query will loop indefinitely.  (See <xref linkend="queries-with">
+   for more examples.)
+  </para>
  </refsect1>
- 
+
  <refsect1>
   <title>Compatibility</title>
 
@@ -1116,7 +1250,7 @@ SELECT * FROM distributors_2(111) AS (f1 int, f2 text);
    with the SQL standard.  But there are some extensions and some
    missing features.
   </para>
-  
+
   <refsect2>
    <title>Omitted <literal>FROM</literal> Clauses</title>
 
@@ -1196,7 +1330,7 @@ SELECT distributors.* WHERE distributors.name = 'Westward';
 
    <para>
     SQL:1999 and later use a slightly different definition which is not
-    entirely upward compatible with SQL-92.  
+    entirely upward compatible with SQL-92.
     In most cases, however, <productname>PostgreSQL</productname>
     will interpret an <literal>ORDER BY</literal> or <literal>GROUP
     BY</literal> expression the same way SQL:1999 does.
diff --git a/doc/src/sgml/ref/select_into.sgml b/doc/src/sgml/ref/select_into.sgml
index 915e859ea98..de9a86a878c 100644
--- a/doc/src/sgml/ref/select_into.sgml
+++ b/doc/src/sgml/ref/select_into.sgml
@@ -1,5 +1,5 @@
 <!--
-$PostgreSQL: pgsql/doc/src/sgml/ref/select_into.sgml,v 1.40 2008/02/15 22:17:06 tgl Exp $
+$PostgreSQL: pgsql/doc/src/sgml/ref/select_into.sgml,v 1.41 2008/10/04 21:56:52 tgl Exp $
 PostgreSQL documentation
 -->
 
@@ -20,17 +20,18 @@ PostgreSQL documentation
 
  <refsynopsisdiv>
 <synopsis>
-SELECT [ ALL | DISTINCT [ ON ( <replaceable class="PARAMETER">expression</replaceable> [, ...] ) ] ]
-    * | <replaceable class="PARAMETER">expression</replaceable> [ [ AS ] <replaceable class="PARAMETER">output_name</replaceable> ] [, ...]
-    INTO [ TEMPORARY | TEMP ] [ TABLE ] <replaceable class="PARAMETER">new_table</replaceable>
-    [ FROM <replaceable class="PARAMETER">from_item</replaceable> [, ...] ]
-    [ WHERE <replaceable class="PARAMETER">condition</replaceable> ]
-    [ GROUP BY <replaceable class="PARAMETER">expression</replaceable> [, ...] ]
-    [ HAVING <replaceable class="PARAMETER">condition</replaceable> [, ...] ]
-    [ { UNION | INTERSECT | EXCEPT } [ ALL ] <replaceable class="PARAMETER">select</replaceable> ]
+[ WITH [ RECURSIVE ] <replaceable class="parameter">with_query</replaceable> [, ...] ]
+SELECT [ ALL | DISTINCT [ ON ( <replaceable class="parameter">expression</replaceable> [, ...] ) ] ]
+    * | <replaceable class="parameter">expression</replaceable> [ [ AS ] <replaceable class="parameter">output_name</replaceable> ] [, ...]
+    INTO [ TEMPORARY | TEMP ] [ TABLE ] <replaceable class="parameter">new_table</replaceable>
+    [ FROM <replaceable class="parameter">from_item</replaceable> [, ...] ]
+    [ WHERE <replaceable class="parameter">condition</replaceable> ]
+    [ GROUP BY <replaceable class="parameter">expression</replaceable> [, ...] ]
+    [ HAVING <replaceable class="parameter">condition</replaceable> [, ...] ]
+    [ { UNION | INTERSECT | EXCEPT } [ ALL ] <replaceable class="parameter">select</replaceable> ]
     [ ORDER BY <replaceable class="parameter">expression</replaceable> [ ASC | DESC | USING <replaceable class="parameter">operator</replaceable> ] [ NULLS { FIRST | LAST } ] [, ...] ]
-    [ LIMIT { <replaceable class="PARAMETER">count</replaceable> | ALL } ]
-    [ OFFSET <replaceable class="PARAMETER">start</replaceable> ]
+    [ LIMIT { <replaceable class="parameter">count</replaceable> | ALL } ]
+    [ OFFSET <replaceable class="parameter">start</replaceable> ]
     [ FOR { UPDATE | SHARE } [ OF <replaceable class="parameter">table_name</replaceable> [, ...] ] [ NOWAIT ] [...] ]
 </synopsis>
  </refsynopsisdiv>
@@ -46,7 +47,7 @@ SELECT [ ALL | DISTINCT [ ON ( <replaceable class="PARAMETER">expression</replac
    output columns of the <command>SELECT</command>.
   </para>
  </refsect1>
-  
+
  <refsect1>
   <title>Parameters</title>