<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> <HTML ><HEAD ><TITLE >WITH Queries (Common Table Expressions)</TITLE ><META NAME="GENERATOR" CONTENT="Modular DocBook HTML Stylesheet Version 1.79"><LINK REV="MADE" HREF="mailto:pgsql-docs@postgresql.org"><LINK REL="HOME" TITLE="PostgreSQL 8.4.12 Documentation" HREF="index.html"><LINK REL="UP" TITLE="Queries" HREF="queries.html"><LINK REL="PREVIOUS" TITLE="VALUES Lists" HREF="queries-values.html"><LINK REL="NEXT" TITLE="Data Types" HREF="datatype.html"><LINK REL="STYLESHEET" TYPE="text/css" HREF="stylesheet.css"><META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=ISO-8859-1"><META NAME="creation" CONTENT="2012-05-31T23:30:11"></HEAD ><BODY CLASS="SECT1" ><DIV CLASS="NAVHEADER" ><TABLE SUMMARY="Header navigation table" WIDTH="100%" BORDER="0" CELLPADDING="0" CELLSPACING="0" ><TR ><TH COLSPAN="5" ALIGN="center" VALIGN="bottom" >PostgreSQL 8.4.12 Documentation</TH ></TR ><TR ><TD WIDTH="10%" ALIGN="left" VALIGN="top" ><A HREF="queries-values.html" ACCESSKEY="P" >Prev</A ></TD ><TD WIDTH="10%" ALIGN="left" VALIGN="top" ><A HREF="queries.html" >Fast Backward</A ></TD ><TD WIDTH="60%" ALIGN="center" VALIGN="bottom" >Chapter 7. Queries</TD ><TD WIDTH="10%" ALIGN="right" VALIGN="top" ><A HREF="queries.html" >Fast Forward</A ></TD ><TD WIDTH="10%" ALIGN="right" VALIGN="top" ><A HREF="datatype.html" ACCESSKEY="N" >Next</A ></TD ></TR ></TABLE ><HR ALIGN="LEFT" WIDTH="100%"></DIV ><DIV CLASS="SECT1" ><H1 CLASS="SECT1" ><A NAME="QUERIES-WITH" >7.8. <TT CLASS="LITERAL" >WITH</TT > Queries (Common Table Expressions)</A ></H1 ><A NAME="AEN4016" ></A ><A NAME="AEN4019" ></A ><P > <TT CLASS="LITERAL" >WITH</TT > provides a way to write subqueries for use in a larger <TT CLASS="LITERAL" >SELECT</TT > query. The subqueries, which are often referred to as Common Table Expressions or <ACRONYM CLASS="ACRONYM" >CTE</ACRONYM >s, 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: </P><PRE CLASS="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 > (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;</PRE ><P> which displays per-product sales totals in only the top sales regions. This example could have been written without <TT CLASS="LITERAL" >WITH</TT >, but we'd have needed two levels of nested sub-SELECTs. It's a bit easier to follow this way. </P ><P > The optional <TT CLASS="LITERAL" >RECURSIVE</TT > modifier changes <TT CLASS="LITERAL" >WITH</TT > from a mere syntactic convenience into a feature that accomplishes things not otherwise possible in standard SQL. Using <TT CLASS="LITERAL" >RECURSIVE</TT >, a <TT CLASS="LITERAL" >WITH</TT > query can refer to its own output. A very simple example is this query to sum the integers from 1 through 100: </P><PRE CLASS="PROGRAMLISTING" >WITH RECURSIVE t(n) AS ( VALUES (1) UNION ALL SELECT n+1 FROM t WHERE n < 100 ) SELECT sum(n) FROM t;</PRE ><P> The general form of a recursive <TT CLASS="LITERAL" >WITH</TT > query is always a <I CLASS="FIRSTTERM" >non-recursive term</I >, then <TT CLASS="LITERAL" >UNION</TT > (or <TT CLASS="LITERAL" >UNION ALL</TT >), then a <I CLASS="FIRSTTERM" >recursive term</I >, where only the recursive term can contain a reference to the query's own output. Such a query is executed as follows: </P ><DIV CLASS="PROCEDURE" ><P ><B >Recursive Query Evaluation</B ></P ><OL TYPE="1" ><LI CLASS="STEP" ><P > Evaluate the non-recursive term. For <TT CLASS="LITERAL" >UNION</TT > (but not <TT CLASS="LITERAL" >UNION ALL</TT >), discard duplicate rows. Include all remaining rows in the result of the recursive query, and also place them in a temporary <I CLASS="FIRSTTERM" >working table</I >. </P ></LI ><LI CLASS="STEP" ><P > So long as the working table is not empty, repeat these steps: </P ><OL CLASS="SUBSTEPS" TYPE="a" ><LI CLASS="STEP" ><P > Evaluate the recursive term, substituting the current contents of the working table for the recursive self-reference. For <TT CLASS="LITERAL" >UNION</TT > (but not <TT CLASS="LITERAL" >UNION ALL</TT >), 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 <I CLASS="FIRSTTERM" >intermediate table</I >. </P ></LI ><LI CLASS="STEP" ><P > Replace the contents of the working table with the contents of the intermediate table, then empty the intermediate table. </P ></LI ></OL ></LI ></OL ></DIV ><DIV CLASS="NOTE" ><BLOCKQUOTE CLASS="NOTE" ><P ><B >Note: </B > Strictly speaking, this process is iteration not recursion, but <TT CLASS="LITERAL" >RECURSIVE</TT > is the terminology chosen by the SQL standards committee. </P ></BLOCKQUOTE ></DIV ><P > 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 <TT CLASS="LITERAL" >WHERE</TT > clause, and so the query terminates. </P ><P > 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: </P><PRE CLASS="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</PRE ><P> </P ><P > 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. Sometimes, using <TT CLASS="LITERAL" >UNION</TT > instead of <TT CLASS="LITERAL" >UNION ALL</TT > can accomplish this by discarding rows that duplicate previous output rows. However, often a cycle does not involve output rows that are completely duplicate: it may be necessary to check just one or a few fields to see if the same point has been reached before. The standard method for handling such situations is to compute an array of the already-visited values. For example, consider the following query that searches a table <TT CLASS="STRUCTNAME" >graph</TT > using a <TT CLASS="STRUCTFIELD" >link</TT > field: </P><PRE CLASS="PROGRAMLISTING" >WITH RECURSIVE search_graph(id, link, data, depth) AS ( SELECT g.id, g.link, g.data, 1 FROM graph g UNION ALL SELECT g.id, g.link, g.data, sg.depth + 1 FROM graph g, search_graph sg WHERE g.id = sg.link ) SELECT * FROM search_graph;</PRE ><P> This query will loop if the <TT CLASS="STRUCTFIELD" >link</TT > relationships contain cycles. Because we require a <SPAN CLASS="QUOTE" >"depth"</SPAN > output, just changing <TT CLASS="LITERAL" >UNION ALL</TT > to <TT CLASS="LITERAL" >UNION</TT > would not eliminate the looping. Instead we need to recognize whether we have reached the same row again while following a particular path of links. We add two columns <TT CLASS="STRUCTFIELD" >path</TT > and <TT CLASS="STRUCTFIELD" >cycle</TT > to the loop-prone query: </P><PRE CLASS="PROGRAMLISTING" >WITH RECURSIVE search_graph(id, link, data, depth, path, cycle) AS ( SELECT g.id, g.link, g.data, 1, ARRAY[g.id], false FROM graph g UNION ALL SELECT g.id, g.link, g.data, sg.depth + 1, path || g.id, g.id = ANY(path) FROM graph g, search_graph sg WHERE g.id = sg.link AND NOT cycle ) SELECT * FROM search_graph;</PRE ><P> Aside from preventing cycles, the array value is often useful in its own right as representing the <SPAN CLASS="QUOTE" >"path"</SPAN > taken to reach any particular row. </P ><P > In the general case where more than one field needs to be checked to recognize a cycle, use an array of rows. For example, if we needed to compare fields <TT CLASS="STRUCTFIELD" >f1</TT > and <TT CLASS="STRUCTFIELD" >f2</TT >: </P><PRE CLASS="PROGRAMLISTING" >WITH RECURSIVE search_graph(id, link, data, depth, path, cycle) AS ( SELECT g.id, g.link, g.data, 1, ARRAY[ROW(g.f1, g.f2)], false FROM graph g UNION ALL SELECT g.id, g.link, g.data, sg.depth + 1, path || ROW(g.f1, g.f2), ROW(g.f1, g.f2) = ANY(path) FROM graph g, search_graph sg WHERE g.id = sg.link AND NOT cycle ) SELECT * FROM search_graph;</PRE ><P> </P ><DIV CLASS="TIP" ><BLOCKQUOTE CLASS="TIP" ><P ><B >Tip: </B > Omit the <TT CLASS="LITERAL" >ROW()</TT > syntax in the common case where only one field needs to be checked to recognize a cycle. This allows a simple array rather than a composite-type array to be used, gaining efficiency. </P ></BLOCKQUOTE ></DIV ><DIV CLASS="TIP" ><BLOCKQUOTE CLASS="TIP" ><P ><B >Tip: </B > The recursive query evaluation algorithm produces its output in breadth-first search order. You can display the results in depth-first search order by making the outer query <TT CLASS="LITERAL" >ORDER BY</TT > a <SPAN CLASS="QUOTE" >"path"</SPAN > column constructed in this way. </P ></BLOCKQUOTE ></DIV ><P > A helpful trick for testing queries when you are not certain if they might loop is to place a <TT CLASS="LITERAL" >LIMIT</TT > in the parent query. For example, this query would loop forever without the <TT CLASS="LITERAL" >LIMIT</TT >: </P><PRE CLASS="PROGRAMLISTING" >WITH RECURSIVE t(n) AS ( SELECT 1 UNION ALL SELECT n+1 FROM t ) SELECT n FROM t LIMIT 100;</PRE ><P> This works because <SPAN CLASS="PRODUCTNAME" >PostgreSQL</SPAN >'s implementation evaluates only as many rows of a <TT CLASS="LITERAL" >WITH</TT > query as are actually fetched by the parent query. Using this trick in production is not recommended, because other systems might work differently. Also, it usually won't work if you make the outer query sort the recursive query's results or join them to some other table. </P ><P > A useful property of <TT CLASS="LITERAL" >WITH</TT > 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 <TT CLASS="LITERAL" >WITH</TT > queries. Thus, expensive calculations that are needed in multiple places can be placed within a <TT CLASS="LITERAL" >WITH</TT > 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 <TT CLASS="LITERAL" >WITH</TT > query than an ordinary sub-query. The <TT CLASS="LITERAL" >WITH</TT > 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.) </P ></DIV ><DIV CLASS="NAVFOOTER" ><HR ALIGN="LEFT" WIDTH="100%"><TABLE SUMMARY="Footer navigation table" WIDTH="100%" BORDER="0" CELLPADDING="0" CELLSPACING="0" ><TR ><TD WIDTH="33%" ALIGN="left" VALIGN="top" ><A HREF="queries-values.html" ACCESSKEY="P" >Prev</A ></TD ><TD WIDTH="34%" ALIGN="center" VALIGN="top" ><A HREF="index.html" ACCESSKEY="H" >Home</A ></TD ><TD WIDTH="33%" ALIGN="right" VALIGN="top" ><A HREF="datatype.html" ACCESSKEY="N" >Next</A ></TD ></TR ><TR ><TD WIDTH="33%" ALIGN="left" VALIGN="top" ><TT CLASS="LITERAL" >VALUES</TT > Lists</TD ><TD WIDTH="34%" ALIGN="center" VALIGN="top" ><A HREF="queries.html" ACCESSKEY="U" >Up</A ></TD ><TD WIDTH="33%" ALIGN="right" VALIGN="top" >Data Types</TD ></TR ></TABLE ></DIV ></BODY ></HTML >