<literal>WITH [RECURSIVE]</literal> Clause

*** doc/src/sgml/errcodes.sgml.orig Thu May 15 18:39:48 2008 --- doc/src/sgml/errcodes.sgml Tue Sep 30 10:37:15 2008 *************** *** 991,996 **** --- 991,1002 ---- + 42P19 + INVALID RECURSION + invalid_recursion + + + 42830 INVALID FOREIGN KEY invalid_foreign_key *** doc/src/sgml/ref/select.sgml.orig Thu Sep 25 14:54:08 2008 --- doc/src/sgml/ref/select.sgml Thu Sep 25 14:55:33 2008 *************** *** 20,25 **** --- 20,26 ---- + [WITH [RECURSIVE] with_query [, ...] ] SELECT [ ALL | DISTINCT [ ON ( expression [, ...] ) ] ] * | expression [ [ AS ] output_name ] [, ...] [ FROM from_item [, ...] ] *************** *** 39,44 **** --- 40,49 ---- function_name ( [ argument [, ...] ] ) [ AS ] alias [ ( column_alias [, ...] | column_definition [, ...] ) ] function_name ( [ argument [, ...] ] ) AS ( column_definition [, ...] ) from_item [ NATURAL ] join_type from_item [ ON join_condition | USING ( join_column [, ...] ) ] + + and with_query is: + + query_name[(column_name[, ...])] AS ( select ) *************** *** 841,846 **** --- 846,875 ---- + + <literal>WITH [RECURSIVE]</literal> Clause + + + The WITH clause allows you to specify a + subquery that can be referenced by name in the primary query, + similar to how you might use a predefined view. + + + + The column list specifies the names of the columns, or if omitted, + the column names are inferred from the subquery. + + + + If RECURSIVE is specified, it allows the + subquery to reference itself by name. Using + RECURSIVE allows you to perform queries that + might not otherwise be possible, and are not guaranteed to + complete (that is, it's possible to write a query that will + recurse infinitely). + + + *************** *** 1106,1111 **** --- 1135,1193 ---- 111 | Walt Disney + + + This example shows how to use a simple WITH clause. + + WITH t(relkind, relcount) AS ( + SELECT relkind, count(*) + FROM + pg_catalog.pg_class + GROUP BY relkind + ORDER BY relkind + ) + SELECT relkind, relcount FROM t; + relkind | relcount + ---------+---------- + i | 90 + r | 47 + t | 16 + v | 74 + + + + + + This example shows how to use WITH RECURSIVE. + + Assume you have a table employee with columns + employee_name and + manager_name. This recursive query will find all + subordinates (direct or indirect) of the employee Mary, and the + level of indirectness. Note the typical form of recursive queries: + an initial condition, followed by a UNION ALL, + followed by a 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 recurse infinitely. It's not necessary to + follow this form, but often useful. + + + 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 e, + employee_recursive er + WHERE e.manager_name = er.employee_name + ) + SELECT distance, employee_name FROM employee_recursive; + + + *** src/backend/catalog/dependency.c.orig Mon Aug 25 18:42:32 2008 --- src/backend/catalog/dependency.c Mon Sep 22 15:32:57 2008 *************** *** 1557,1563 **** * Add whole-relation refs for each plain relation mentioned in the * subquery's rtable, as well as datatype refs for any datatypes used * as a RECORD function's output. (Note: query_tree_walker takes care ! * of recursing into RTE_FUNCTION and RTE_SUBQUERY RTEs, so no need to * do that here. But keep it from looking at join alias lists.) */ foreach(rtable, query->rtable) --- 1557,1563 ---- * Add whole-relation refs for each plain relation mentioned in the * subquery's rtable, as well as datatype refs for any datatypes used * as a RECORD function's output. (Note: query_tree_walker takes care ! * of recursing into RTE_FUNCTION RTEs, subqueries, etc, so no need to * do that here. But keep it from looking at join alias lists.) */ foreach(rtable, query->rtable) *** src/backend/commands/explain.c.orig Tue Aug 19 14:30:04 2008 --- src/backend/commands/explain.c Thu Oct 2 14:49:41 2008 *************** *** 429,434 **** --- 429,437 ---- case T_Append: pname = "Append"; break; + case T_RecursiveUnion: + pname = "Recursive Union"; + break; case T_BitmapAnd: pname = "BitmapAnd"; break; *************** *** 537,542 **** --- 540,551 ---- case T_ValuesScan: pname = "Values Scan"; break; + case T_CteScan: + pname = "CTE Scan"; + break; + case T_WorkTableScan: + pname = "WorkTable Scan"; + break; case T_Material: pname = "Materialize"; break; *************** *** 721,726 **** --- 730,769 ---- quote_identifier(valsname)); } break; + case T_CteScan: + if (((Scan *) plan)->scanrelid > 0) + { + RangeTblEntry *rte = rt_fetch(((Scan *) plan)->scanrelid, + es->rtable); + + /* Assert it's on a non-self-reference CTE */ + Assert(rte->rtekind == RTE_CTE); + Assert(!rte->self_reference); + + appendStringInfo(str, " on %s", + quote_identifier(rte->ctename)); + if (strcmp(rte->eref->aliasname, rte->ctename) != 0) + appendStringInfo(str, " %s", + quote_identifier(rte->eref->aliasname)); + } + break; + case T_WorkTableScan: + if (((Scan *) plan)->scanrelid > 0) + { + RangeTblEntry *rte = rt_fetch(((Scan *) plan)->scanrelid, + es->rtable); + + /* Assert it's on a self-reference CTE */ + Assert(rte->rtekind == RTE_CTE); + Assert(rte->self_reference); + + appendStringInfo(str, " on %s", + quote_identifier(rte->ctename)); + if (strcmp(rte->eref->aliasname, rte->ctename) != 0) + appendStringInfo(str, " %s", + quote_identifier(rte->eref->aliasname)); + } + break; default: break; } *************** *** 787,792 **** --- 830,837 ---- case T_SeqScan: case T_FunctionScan: case T_ValuesScan: + case T_CteScan: + case T_WorkTableScan: show_scan_qual(plan->qual, "Filter", ((Scan *) plan)->scanrelid, *************** *** 1071,1076 **** --- 1116,1124 ---- /* The tlist of an Append isn't real helpful, so suppress it */ if (IsA(plan, Append)) return; + /* Likewise for RecursiveUnion */ + if (IsA(plan, RecursiveUnion)) + return; /* Set up deparsing context */ context = deparse_context_for_plan((Node *) outerPlan(plan), *** src/backend/executor/Makefile.orig Tue Feb 19 05:30:07 2008 --- src/backend/executor/Makefile Thu Oct 2 14:49:12 2008 *************** *** 18,26 **** nodeBitmapAnd.o nodeBitmapOr.o \ nodeBitmapHeapscan.o nodeBitmapIndexscan.o nodeHash.o \ nodeHashjoin.o nodeIndexscan.o nodeMaterial.o nodeMergejoin.o \ ! nodeNestloop.o nodeFunctionscan.o nodeResult.o nodeSeqscan.o \ ! nodeSetOp.o nodeSort.o nodeUnique.o \ ! nodeValuesscan.o nodeLimit.o nodeGroup.o \ ! nodeSubplan.o nodeSubqueryscan.o nodeTidscan.o tstoreReceiver.o spi.o include $(top_srcdir)/src/backend/common.mk --- 18,27 ---- nodeBitmapAnd.o nodeBitmapOr.o \ nodeBitmapHeapscan.o nodeBitmapIndexscan.o nodeHash.o \ nodeHashjoin.o nodeIndexscan.o nodeMaterial.o nodeMergejoin.o \ ! nodeNestloop.o nodeFunctionscan.o nodeRecursiveunion.o nodeResult.o \ ! nodeSeqscan.o nodeSetOp.o nodeSort.o nodeUnique.o \ ! nodeValuesscan.o nodeCtescan.o nodeWorktablescan.o \ ! nodeLimit.o nodeGroup.o nodeSubplan.o nodeSubqueryscan.o nodeTidscan.o \ ! tstoreReceiver.o spi.o include $(top_srcdir)/src/backend/common.mk *** src/backend/executor/execAmi.c.orig Wed Oct 1 20:22:13 2008 --- src/backend/executor/execAmi.c Thu Oct 2 14:48:05 2008 *************** *** 30,35 **** --- 30,36 ---- #include "executor/nodeMaterial.h" #include "executor/nodeMergejoin.h" #include "executor/nodeNestloop.h" + #include "executor/nodeRecursiveunion.h" #include "executor/nodeResult.h" #include "executor/nodeSeqscan.h" #include "executor/nodeSetOp.h" *************** *** 39,44 **** --- 40,47 ---- #include "executor/nodeTidscan.h" #include "executor/nodeUnique.h" #include "executor/nodeValuesscan.h" + #include "executor/nodeCtescan.h" + #include "executor/nodeWorktablescan.h" /* *************** *** 121,126 **** --- 124,133 ---- ExecReScanAppend((AppendState *) node, exprCtxt); break; + case T_RecursiveUnionState: + ExecRecursiveUnionReScan((RecursiveUnionState *) node, exprCtxt); + break; + case T_BitmapAndState: ExecReScanBitmapAnd((BitmapAndState *) node, exprCtxt); break; *************** *** 161,166 **** --- 168,181 ---- ExecValuesReScan((ValuesScanState *) node, exprCtxt); break; + case T_CteScanState: + ExecCteScanReScan((CteScanState *) node, exprCtxt); + break; + + case T_WorkTableScanState: + ExecWorkTableScanReScan((WorkTableScanState *) node, exprCtxt); + break; + case T_NestLoopState: ExecReScanNestLoop((NestLoopState *) node, exprCtxt); break; *************** *** 396,401 **** --- 411,418 ---- case T_TidScan: case T_FunctionScan: case T_ValuesScan: + case T_CteScan: + case T_WorkTableScan: return true; case T_SubqueryScan: *** src/backend/executor/execProcnode.c.orig Tue Jan 1 14:45:49 2008 --- src/backend/executor/execProcnode.c Thu Oct 2 14:48:06 2008 *************** *** 94,99 **** --- 94,100 ---- #include "executor/nodeMaterial.h" #include "executor/nodeMergejoin.h" #include "executor/nodeNestloop.h" + #include "executor/nodeRecursiveunion.h" #include "executor/nodeResult.h" #include "executor/nodeSeqscan.h" #include "executor/nodeSetOp.h" *************** *** 103,110 **** --- 104,114 ---- #include "executor/nodeTidscan.h" #include "executor/nodeUnique.h" #include "executor/nodeValuesscan.h" + #include "executor/nodeCtescan.h" + #include "executor/nodeWorktablescan.h" #include "miscadmin.h" + /* ------------------------------------------------------------------------ * ExecInitNode * *************** *** 147,152 **** --- 151,161 ---- estate, eflags); break; + case T_RecursiveUnion: + result = (PlanState *) ExecInitRecursiveUnion((RecursiveUnion *) node, + estate, eflags); + break; + case T_BitmapAnd: result = (PlanState *) ExecInitBitmapAnd((BitmapAnd *) node, estate, eflags); *************** *** 200,205 **** --- 209,224 ---- estate, eflags); break; + case T_CteScan: + result = (PlanState *) ExecInitCteScan((CteScan *) node, + estate, eflags); + break; + + case T_WorkTableScan: + result = (PlanState *) ExecInitWorkTableScan((WorkTableScan *) node, + estate, eflags); + break; + /* * join nodes */ *************** *** 323,328 **** --- 342,351 ---- result = ExecAppend((AppendState *) node); break; + case T_RecursiveUnionState: + result = ExecRecursiveUnion((RecursiveUnionState *) node); + break; + /* BitmapAndState does not yield tuples */ /* BitmapOrState does not yield tuples */ *************** *** 360,365 **** --- 383,396 ---- result = ExecValuesScan((ValuesScanState *) node); break; + case T_CteScanState: + result = ExecCteScan((CteScanState *) node); + break; + + case T_WorkTableScanState: + result = ExecWorkTableScan((WorkTableScanState *) node); + break; + /* * join nodes */ *************** *** 501,506 **** --- 532,540 ---- case T_Append: return ExecCountSlotsAppend((Append *) node); + case T_RecursiveUnion: + return ExecCountSlotsRecursiveUnion((RecursiveUnion *) node); + case T_BitmapAnd: return ExecCountSlotsBitmapAnd((BitmapAnd *) node); *************** *** 534,539 **** --- 568,579 ---- case T_ValuesScan: return ExecCountSlotsValuesScan((ValuesScan *) node); + case T_CteScan: + return ExecCountSlotsCteScan((CteScan *) node); + + case T_WorkTableScan: + return ExecCountSlotsWorkTableScan((WorkTableScan *) node); + /* * join nodes */ *************** *** 620,625 **** --- 660,669 ---- ExecEndAppend((AppendState *) node); break; + case T_RecursiveUnionState: + ExecEndRecursiveUnion((RecursiveUnionState *) node); + break; + case T_BitmapAndState: ExecEndBitmapAnd((BitmapAndState *) node); break; *************** *** 663,668 **** --- 707,720 ---- ExecEndValuesScan((ValuesScanState *) node); break; + case T_CteScanState: + ExecEndCteScan((CteScanState *) node); + break; + + case T_WorkTableScanState: + ExecEndWorkTableScan((WorkTableScanState *) node); + break; + /* * join nodes */ *** src/backend/executor/nodeCtescan.c.orig Thu Oct 2 14:50:55 2008 --- src/backend/executor/nodeCtescan.c Fri Oct 3 12:00:15 2008 *************** *** 0 **** --- 1,335 ---- + /*------------------------------------------------------------------------- + * + * nodeCtescan.c + * routines to handle CteScan nodes. + * + * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * + * IDENTIFICATION + * $PostgreSQL$ + * + *------------------------------------------------------------------------- + */ + + #include "postgres.h" + + #include "executor/execdebug.h" + #include "executor/nodeCtescan.h" + #include "miscadmin.h" + + static TupleTableSlot *CteScanNext(CteScanState *node); + + /* ---------------------------------------------------------------- + * CteScanNext + * + * This is a workhorse for ExecCteScan + * ---------------------------------------------------------------- + */ + static TupleTableSlot * + CteScanNext(CteScanState *node) + { + EState *estate; + ScanDirection dir; + bool forward; + Tuplestorestate *tuplestorestate; + bool eof_tuplestore; + TupleTableSlot *slot; + + /* + * get state info from node + */ + estate = node->ss.ps.state; + dir = estate->es_direction; + forward = ScanDirectionIsForward(dir); + tuplestorestate = node->leader->cte_table; + tuplestore_select_read_pointer(tuplestorestate, node->readptr); + slot = node->ss.ss_ScanTupleSlot; + + /* + * If we are not at the end of the tuplestore, or are going backwards, try + * to fetch a tuple from tuplestore. + */ + eof_tuplestore = tuplestore_ateof(tuplestorestate); + + if (!forward && eof_tuplestore) + { + if (!node->leader->eof_cte) + { + /* + * When reversing direction at tuplestore EOF, the first + * gettupleslot call will fetch the last-added tuple; but we want + * to return the one before that, if possible. So do an extra + * fetch. + */ + if (!tuplestore_advance(tuplestorestate, forward)) + return NULL; /* the tuplestore must be empty */ + } + eof_tuplestore = false; + } + + /* + * If we can fetch another tuple from the tuplestore, return it. + */ + if (!eof_tuplestore) + { + if (tuplestore_gettupleslot(tuplestorestate, forward, slot)) + return slot; + if (forward) + eof_tuplestore = true; + } + + /* + * If necessary, try to fetch another row from the CTE query. + * + * Note: the eof_cte state variable exists to short-circuit further calls + * of the CTE plan. It's not optional, unfortunately, because some plan + * node types are not robust about being called again when they've already + * returned NULL. + */ + if (eof_tuplestore && !node->leader->eof_cte) + { + TupleTableSlot *cteslot; + + /* + * We can only get here with forward==true, so no need to worry about + * which direction the subplan will go. + */ + cteslot = ExecProcNode(node->cteplanstate); + if (TupIsNull(cteslot)) + { + node->leader->eof_cte = true; + return NULL; + } + + /* + * Append a copy of the returned tuple to tuplestore. NOTE: because + * our read pointer is certainly in EOF state, its read position will + * move forward over the added tuple. This is what we want. Also, + * any other readers will *not* move past the new tuple, which is + * what they want. + */ + tuplestore_puttupleslot(tuplestorestate, cteslot); + + /* + * We MUST copy the CTE query's output tuple into our own slot. + * This is because other CteScan nodes might advance the CTE query + * before we are called again, and our output tuple must stay + * stable over that. + */ + return ExecCopySlot(slot, cteslot); + } + + /* + * Nothing left ... + */ + return ExecClearTuple(slot); + } + + /* ---------------------------------------------------------------- + * ExecCteScan(node) + * + * Scans the CTE sequentially and returns the next qualifying tuple. + * It calls the ExecScan() routine and passes it the access method + * which retrieves tuples sequentially. + * ---------------------------------------------------------------- + */ + TupleTableSlot * + ExecCteScan(CteScanState *node) + { + /* + * use CteScanNext as access method + */ + return ExecScan(&node->ss, (ExecScanAccessMtd) CteScanNext); + } + + + /* ---------------------------------------------------------------- + * ExecInitCteScan + * ---------------------------------------------------------------- + */ + CteScanState * + ExecInitCteScan(CteScan *node, EState *estate, int eflags) + { + CteScanState *scanstate; + ParamExecData *prmdata; + + /* check for unsupported flags */ + Assert(!(eflags & EXEC_FLAG_MARK)); + + /* + * For the moment we have to force the tuplestore to allow REWIND, because + * we might be asked to rescan the CTE even though upper levels didn't + * tell us to be prepared to do it efficiently. Annoying, since this + * prevents truncation of the tuplestore. XXX FIXME + */ + eflags |= EXEC_FLAG_REWIND; + + /* + * CteScan should not have any children. + */ + Assert(outerPlan(node) == NULL); + Assert(innerPlan(node) == NULL); + + /* + * create new CteScanState for node + */ + scanstate = makeNode(CteScanState); + scanstate->ss.ps.plan = (Plan *) node; + scanstate->ss.ps.state = estate; + scanstate->eflags = eflags; + scanstate->cte_table = NULL; + scanstate->eof_cte = false; + + /* + * Find the already-initialized plan for the CTE query. + */ + scanstate->cteplanstate = (PlanState *) list_nth(estate->es_subplanstates, + node->ctePlanId - 1); + + /* + * The Param slot associated with the CTE query is used to hold a + * pointer to the CteState of the first CteScan node that initializes + * for this CTE. This node will be the one that holds the shared + * state for all the CTEs. + */ + prmdata = &(estate->es_param_exec_vals[node->cteParam]); + Assert(prmdata->execPlan == NULL); + Assert(!prmdata->isnull); + scanstate->leader = (CteScanState *) DatumGetPointer(prmdata->value); + if (scanstate->leader == NULL) + { + /* I am the leader */ + prmdata->value = PointerGetDatum(scanstate); + scanstate->leader = scanstate; + scanstate->cte_table = tuplestore_begin_heap(true, false, work_mem); + tuplestore_set_eflags(scanstate->cte_table, scanstate->eflags); + scanstate->readptr = 0; + } + else + { + /* Not the leader */ + Assert(IsA(scanstate->leader, CteScanState)); + scanstate->readptr = + tuplestore_alloc_read_pointer(scanstate->leader->cte_table, + scanstate->eflags); + } + + /* + * Miscellaneous initialization + * + * create expression context for node + */ + ExecAssignExprContext(estate, &scanstate->ss.ps); + + /* + * initialize child expressions + */ + scanstate->ss.ps.targetlist = (List *) + ExecInitExpr((Expr *) node->scan.plan.targetlist, + (PlanState *) scanstate); + scanstate->ss.ps.qual = (List *) + ExecInitExpr((Expr *) node->scan.plan.qual, + (PlanState *) scanstate); + + #define CTESCAN_NSLOTS 2 + + /* + * tuple table initialization + */ + ExecInitResultTupleSlot(estate, &scanstate->ss.ps); + ExecInitScanTupleSlot(estate, &scanstate->ss); + + /* + * The scan tuple type (ie, the rowtype we expect to find in the work + * table) is the same as the result rowtype of the CTE query. + */ + ExecAssignScanType(&scanstate->ss, + ExecGetResultType(scanstate->cteplanstate)); + + /* + * Initialize result tuple type and projection info. + */ + ExecAssignResultTypeFromTL(&scanstate->ss.ps); + ExecAssignScanProjectionInfo(&scanstate->ss); + + scanstate->ss.ps.ps_TupFromTlist = false; + + return scanstate; + } + + int + ExecCountSlotsCteScan(CteScan *node) + { + return ExecCountSlotsNode(outerPlan(node)) + + ExecCountSlotsNode(innerPlan(node)) + + CTESCAN_NSLOTS; + } + + /* ---------------------------------------------------------------- + * ExecEndCteScan + * + * frees any storage allocated through C routines. + * ---------------------------------------------------------------- + */ + void + ExecEndCteScan(CteScanState *node) + { + /* + * Free exprcontext + */ + ExecFreeExprContext(&node->ss.ps); + + /* + * clean out the tuple table + */ + ExecClearTuple(node->ss.ps.ps_ResultTupleSlot); + ExecClearTuple(node->ss.ss_ScanTupleSlot); + + /* + * If I am the leader, free the tuplestore. + */ + if (node->leader == node) + tuplestore_end(node->cte_table); + } + + /* ---------------------------------------------------------------- + * ExecCteScanReScan + * + * Rescans the relation. + * ---------------------------------------------------------------- + */ + void + ExecCteScanReScan(CteScanState *node, ExprContext *exprCtxt) + { + Tuplestorestate *tuplestorestate; + + tuplestorestate = node->leader->cte_table; + + ExecClearTuple(node->ss.ps.ps_ResultTupleSlot); + + if (node->leader == node) + { + /* + * The leader is responsible for clearing the tuplestore if a new + * scan of the underlying CTE is required. + */ + if (node->cteplanstate->chgParam != NULL) + { + tuplestore_clear(tuplestorestate); + node->eof_cte = false; + } + else + { + tuplestore_select_read_pointer(tuplestorestate, node->readptr); + tuplestore_rescan(tuplestorestate); + } + } + else + { + /* Not leader, so just rewind my own pointer */ + tuplestore_select_read_pointer(tuplestorestate, node->readptr); + tuplestore_rescan(tuplestorestate); + } + } *** src/backend/executor/nodeRecursiveunion.c.orig Mon Sep 22 11:16:32 2008 --- src/backend/executor/nodeRecursiveunion.c Tue Sep 30 22:32:27 2008 *************** *** 0 **** --- 1,229 ---- + /*------------------------------------------------------------------------- + * + * nodeRecursiveunion.c + * routines to handle RecursiveUnion nodes. + * + * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * + * IDENTIFICATION + * $PostgreSQL$ + * + *------------------------------------------------------------------------- + */ + #include "postgres.h" + + #include "executor/execdebug.h" + #include "executor/nodeRecursiveunion.h" + #include "miscadmin.h" + + + /* ---------------------------------------------------------------- + * ExecRecursiveUnion(node) + * + * Scans the recursive query sequentially and returns the next + * qualifying tuple. + * + * 1. evaluate non recursive term and assign the result to RT + * + * 2. execute recursive terms + * + * 2.1 WT := RT + * 2.2 while WT is not empty repeat 2.3 to 2.6. if WT is empty returns RT + * 2.3 replace the name of recursive term with WT + * 2.4 evaluate the recursive term and store into WT + * 2.5 append WT to RT + * 2.6 go back to 2.2 + * ---------------------------------------------------------------- + */ + TupleTableSlot * + ExecRecursiveUnion(RecursiveUnionState *node) + { + PlanState *outerPlan = outerPlanState(node); + PlanState *innerPlan = innerPlanState(node); + RecursiveUnion *plan = (RecursiveUnion *) node->ps.plan; + TupleTableSlot *slot; + + /* 1. Evaluate non-recursive term */ + if (!node->recursing) + { + slot = ExecProcNode(outerPlan); + if (!TupIsNull(slot)) + { + tuplestore_puttupleslot(node->working_table, slot); + return slot; + } + node->recursing = true; + } + + retry: + /* 2. Execute recursive term */ + slot = ExecProcNode(innerPlan); + if (TupIsNull(slot)) + { + if (node->intermediate_empty) + return NULL; + + /* done with old working table ... */ + tuplestore_end(node->working_table); + + /* intermediate table becomes working table */ + node->working_table = node->intermediate_table; + + /* create new empty intermediate table */ + node->intermediate_table = tuplestore_begin_heap(false, false, work_mem); + node->intermediate_empty = true; + + /* and reset the inner plan */ + innerPlan->chgParam = bms_add_member(innerPlan->chgParam, + plan->wtParam); + goto retry; + } + else + { + node->intermediate_empty = false; + tuplestore_puttupleslot(node->intermediate_table, slot); + } + + return slot; + } + + /* ---------------------------------------------------------------- + * ExecInitRecursiveUnionScan + * ---------------------------------------------------------------- + */ + RecursiveUnionState * + ExecInitRecursiveUnion(RecursiveUnion *node, EState *estate, int eflags) + { + RecursiveUnionState *rustate; + ParamExecData *prmdata; + + /* check for unsupported flags */ + Assert(!(eflags & (EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK))); + + /* + * create state structure + */ + rustate = makeNode(RecursiveUnionState); + rustate->ps.plan = (Plan *) node; + rustate->ps.state = estate; + + /* initialize processing state */ + rustate->recursing = false; + rustate->intermediate_empty = true; + rustate->working_table = tuplestore_begin_heap(false, false, work_mem); + rustate->intermediate_table = tuplestore_begin_heap(false, false, work_mem); + + /* + * Make the state structure available to descendant WorkTableScan nodes + * via the Param slot reserved for it. + */ + prmdata = &(estate->es_param_exec_vals[node->wtParam]); + Assert(prmdata->execPlan == NULL); + prmdata->value = PointerGetDatum(rustate); + prmdata->isnull = false; + + /* + * Miscellaneous initialization + * + * RecursiveUnion plans don't have expression contexts because they never + * call ExecQual or ExecProject. + */ + Assert(node->plan.qual == NIL); + + #define RECURSIVEUNION_NSLOTS 1 + + /* + * RecursiveUnion nodes still have Result slots, which hold pointers to + * tuples, so we have to initialize them. + */ + ExecInitResultTupleSlot(estate, &rustate->ps); + + /* + * Initialize result tuple type and projection info. (Note: we have + * to set up the result type before initializing child nodes, because + * nodeWorktablescan.c expects it to be valid.) + */ + ExecAssignResultTypeFromTL(&rustate->ps); + rustate->ps.ps_ProjInfo = NULL; + + /* + * initialize child nodes + */ + outerPlanState(rustate) = ExecInitNode(outerPlan(node), estate, eflags); + innerPlanState(rustate) = ExecInitNode(innerPlan(node), estate, eflags); + + return rustate; + } + + int + ExecCountSlotsRecursiveUnion(RecursiveUnion *node) + { + return ExecCountSlotsNode(outerPlan(node)) + + ExecCountSlotsNode(innerPlan(node)) + + RECURSIVEUNION_NSLOTS; + } + + /* ---------------------------------------------------------------- + * ExecEndRecursiveUnionScan + * + * frees any storage allocated through C routines. + * ---------------------------------------------------------------- + */ + void + ExecEndRecursiveUnion(RecursiveUnionState *node) + { + /* Release tuple tables */ + tuplestore_end(node->working_table); + tuplestore_end(node->intermediate_table); + + /* + * clean out the upper tuple table + */ + ExecClearTuple(node->ps.ps_ResultTupleSlot); + + /* + * close down subplans + */ + ExecEndNode(outerPlanState(node)); + ExecEndNode(innerPlanState(node)); + } + + /* ---------------------------------------------------------------- + * ExecRecursiveUnionReScan + * + * Rescans the relation. + * ---------------------------------------------------------------- + */ + void + ExecRecursiveUnionReScan(RecursiveUnionState *node, ExprContext *exprCtxt) + { + PlanState *outerPlan = outerPlanState(node); + PlanState *innerPlan = innerPlanState(node); + RecursiveUnion *plan = (RecursiveUnion *) node->ps.plan; + + /* + * Set recursive term's chgParam to tell it that we'll modify the + * working table and therefore it has to rescan. + */ + innerPlan->chgParam = bms_add_member(innerPlan->chgParam, plan->wtParam); + + /* + * if chgParam of subnode is not null then plan will be re-scanned by + * first ExecProcNode. Because of above, we only have to do this to + * the non-recursive term. + */ + if (outerPlan->chgParam == NULL) + ExecReScan(outerPlan, exprCtxt); + + /* reset processing state */ + node->recursing = false; + node->intermediate_empty = true; + + /* tuplestore has no API to empty a table, so delete and recreate */ + tuplestore_end(node->working_table); + tuplestore_end(node->intermediate_table); + node->working_table = tuplestore_begin_heap(false, false, work_mem); + node->intermediate_table = tuplestore_begin_heap(false, false, work_mem); + } *** src/backend/executor/nodeWorktablescan.c.orig Mon Sep 22 11:16:32 2008 --- src/backend/executor/nodeWorktablescan.c Thu Oct 2 17:20:12 2008 *************** *** 0 **** --- 1,181 ---- + /*------------------------------------------------------------------------- + * + * nodeWorktablescan.c + * routines to handle WorkTableScan nodes. + * + * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * + * IDENTIFICATION + * $PostgreSQL$ + * + *------------------------------------------------------------------------- + */ + + #include "postgres.h" + + #include "executor/execdebug.h" + #include "executor/nodeWorktablescan.h" + + + static TupleTableSlot *WorkTableScanNext(WorkTableScanState *node); + + static TupleTableSlot * + WorkTableScanNext(WorkTableScanState *node) + { + TupleTableSlot *slot; + EState *estate; + ScanDirection direction; + Tuplestorestate *tuplestorestate; + + /* + * get information from the estate and scan state + */ + estate = node->ss.ps.state; + direction = estate->es_direction; + + tuplestorestate = node->rustate->working_table; + + /* + * Get the next tuple from tuplestore. Return NULL if no more tuples. + */ + slot = node->ss.ss_ScanTupleSlot; + (void) tuplestore_gettupleslot(tuplestorestate, + ScanDirectionIsForward(direction), + slot); + return slot; + } + + TupleTableSlot * + ExecWorkTableScan(WorkTableScanState *node) + { + /* + * use WorkTableScanNext as access method + */ + return ExecScan(&node->ss, (ExecScanAccessMtd) WorkTableScanNext); + } + + + /* ---------------------------------------------------------------- + * ExecInitWorkTableScan + * ---------------------------------------------------------------- + */ + WorkTableScanState * + ExecInitWorkTableScan(WorkTableScan *node, EState *estate, int eflags) + { + WorkTableScanState *scanstate; + ParamExecData *prmdata; + + /* check for unsupported flags */ + Assert(!(eflags & EXEC_FLAG_MARK)); + + /* + * WorkTableScan should not have any children. + */ + Assert(outerPlan(node) == NULL); + Assert(innerPlan(node) == NULL); + + /* + * create new WorkTableScanState for node + */ + scanstate = makeNode(WorkTableScanState); + scanstate->ss.ps.plan = (Plan *) node; + scanstate->ss.ps.state = estate; + + /* + * Find the ancestor RecursiveUnion's state + * via the Param slot reserved for it. + */ + prmdata = &(estate->es_param_exec_vals[node->wtParam]); + Assert(prmdata->execPlan == NULL); + Assert(!prmdata->isnull); + scanstate->rustate = (RecursiveUnionState *) DatumGetPointer(prmdata->value); + Assert(scanstate->rustate && IsA(scanstate->rustate, RecursiveUnionState)); + + /* + * Miscellaneous initialization + * + * create expression context for node + */ + ExecAssignExprContext(estate, &scanstate->ss.ps); + + /* + * initialize child expressions + */ + scanstate->ss.ps.targetlist = (List *) + ExecInitExpr((Expr *) node->scan.plan.targetlist, + (PlanState *) scanstate); + scanstate->ss.ps.qual = (List *) + ExecInitExpr((Expr *) node->scan.plan.qual, + (PlanState *) scanstate); + + #define WORKTABLESCAN_NSLOTS 2 + + /* + * tuple table initialization + */ + ExecInitResultTupleSlot(estate, &scanstate->ss.ps); + ExecInitScanTupleSlot(estate, &scanstate->ss); + + /* + * The scan tuple type (ie, the rowtype we expect to find in the work + * table) is the same as the result rowtype of the ancestor RecursiveUnion + * node. Note this depends on the assumption that RecursiveUnion doesn't + * allow projection. + */ + ExecAssignScanType(&scanstate->ss, + ExecGetResultType(&scanstate->rustate->ps)); + + /* + * Initialize result tuple type and projection info. + */ + ExecAssignResultTypeFromTL(&scanstate->ss.ps); + ExecAssignScanProjectionInfo(&scanstate->ss); + + scanstate->ss.ps.ps_TupFromTlist = false; + + return scanstate; + } + + int + ExecCountSlotsWorkTableScan(WorkTableScan *node) + { + return ExecCountSlotsNode(outerPlan(node)) + + ExecCountSlotsNode(innerPlan(node)) + + WORKTABLESCAN_NSLOTS; + } + + /* ---------------------------------------------------------------- + * ExecEndWorkTableScan + * + * frees any storage allocated through C routines. + * ---------------------------------------------------------------- + */ + void + ExecEndWorkTableScan(WorkTableScanState *node) + { + /* + * Free exprcontext + */ + ExecFreeExprContext(&node->ss.ps); + + /* + * clean out the tuple table + */ + ExecClearTuple(node->ss.ps.ps_ResultTupleSlot); + ExecClearTuple(node->ss.ss_ScanTupleSlot); + } + + /* ---------------------------------------------------------------- + * ExecWorkTableScanReScan + * + * Rescans the relation. + * ---------------------------------------------------------------- + */ + void + ExecWorkTableScanReScan(WorkTableScanState *node, ExprContext *exprCtxt) + { + ExecClearTuple(node->ss.ps.ps_ResultTupleSlot); + tuplestore_rescan(node->rustate->working_table); + } *** src/backend/nodes/copyfuncs.c.orig Tue Sep 9 14:58:08 2008 --- src/backend/nodes/copyfuncs.c Thu Oct 2 16:31:37 2008 *************** *** 177,182 **** --- 177,203 ---- } /* + * _copyRecursiveUnion + */ + static RecursiveUnion * + _copyRecursiveUnion(RecursiveUnion *from) + { + RecursiveUnion *newnode = makeNode(RecursiveUnion); + + /* + * copy node superclass fields + */ + CopyPlanFields((Plan *) from, (Plan *) newnode); + + /* + * copy remainder of node + */ + COPY_SCALAR_FIELD(wtParam); + + return newnode; + } + + /* * _copyBitmapAnd */ static BitmapAnd * *************** *** 422,427 **** --- 443,491 ---- } /* + * _copyCteScan + */ + static CteScan * + _copyCteScan(CteScan *from) + { + CteScan *newnode = makeNode(CteScan); + + /* + * copy node superclass fields + */ + CopyScanFields((Scan *) from, (Scan *) newnode); + + /* + * copy remainder of node + */ + COPY_SCALAR_FIELD(ctePlanId); + COPY_SCALAR_FIELD(cteParam); + + return newnode; + } + + /* + * _copyWorkTableScan + */ + static WorkTableScan * + _copyWorkTableScan(WorkTableScan *from) + { + WorkTableScan *newnode = makeNode(WorkTableScan); + + /* + * copy node superclass fields + */ + CopyScanFields((Scan *) from, (Scan *) newnode); + + /* + * copy remainder of node + */ + COPY_SCALAR_FIELD(wtParam); + + return newnode; + } + + /* * CopyJoinFields * * This function copies the fields of the Join node. It is used by *************** *** 1572,1583 **** COPY_SCALAR_FIELD(rtekind); COPY_SCALAR_FIELD(relid); COPY_NODE_FIELD(subquery); COPY_NODE_FIELD(funcexpr); COPY_NODE_FIELD(funccoltypes); COPY_NODE_FIELD(funccoltypmods); COPY_NODE_FIELD(values_lists); ! COPY_SCALAR_FIELD(jointype); ! COPY_NODE_FIELD(joinaliasvars); COPY_NODE_FIELD(alias); COPY_NODE_FIELD(eref); COPY_SCALAR_FIELD(inh); --- 1636,1652 ---- COPY_SCALAR_FIELD(rtekind); COPY_SCALAR_FIELD(relid); COPY_NODE_FIELD(subquery); + COPY_SCALAR_FIELD(jointype); + COPY_NODE_FIELD(joinaliasvars); COPY_NODE_FIELD(funcexpr); COPY_NODE_FIELD(funccoltypes); COPY_NODE_FIELD(funccoltypmods); COPY_NODE_FIELD(values_lists); ! COPY_STRING_FIELD(ctename); ! COPY_SCALAR_FIELD(ctelevelsup); ! COPY_SCALAR_FIELD(self_reference); ! COPY_NODE_FIELD(ctecoltypes); ! COPY_NODE_FIELD(ctecoltypmods); COPY_NODE_FIELD(alias); COPY_NODE_FIELD(eref); COPY_SCALAR_FIELD(inh); *************** *** 1632,1637 **** --- 1701,1736 ---- return newnode; } + static WithClause * + _copyWithClause(WithClause *from) + { + WithClause *newnode = makeNode(WithClause); + + COPY_NODE_FIELD(ctes); + COPY_SCALAR_FIELD(recursive); + COPY_LOCATION_FIELD(location); + + return newnode; + } + + static CommonTableExpr * + _copyCommonTableExpr(CommonTableExpr *from) + { + CommonTableExpr *newnode = makeNode(CommonTableExpr); + + COPY_STRING_FIELD(ctename); + COPY_NODE_FIELD(aliascolnames); + COPY_NODE_FIELD(ctequery); + COPY_LOCATION_FIELD(location); + COPY_SCALAR_FIELD(cterecursive); + COPY_SCALAR_FIELD(cterefcount); + COPY_NODE_FIELD(ctecolnames); + COPY_NODE_FIELD(ctecoltypes); + COPY_NODE_FIELD(ctecoltypmods); + + return newnode; + } + static A_Expr * _copyAExpr(A_Expr *from) { *************** *** 1931,1936 **** --- 2030,2037 ---- COPY_SCALAR_FIELD(hasAggs); COPY_SCALAR_FIELD(hasSubLinks); COPY_SCALAR_FIELD(hasDistinctOn); + COPY_SCALAR_FIELD(hasRecursive); + COPY_NODE_FIELD(cteList); COPY_NODE_FIELD(rtable); COPY_NODE_FIELD(jointree); COPY_NODE_FIELD(targetList); *************** *** 1999,2004 **** --- 2100,2106 ---- COPY_NODE_FIELD(whereClause); COPY_NODE_FIELD(groupClause); COPY_NODE_FIELD(havingClause); + COPY_NODE_FIELD(withClause); COPY_NODE_FIELD(valuesLists); COPY_NODE_FIELD(sortClause); COPY_NODE_FIELD(limitOffset); *************** *** 3104,3109 **** --- 3206,3214 ---- case T_Append: retval = _copyAppend(from); break; + case T_RecursiveUnion: + retval = _copyRecursiveUnion(from); + break; case T_BitmapAnd: retval = _copyBitmapAnd(from); break; *************** *** 3137,3142 **** --- 3242,3253 ---- case T_ValuesScan: retval = _copyValuesScan(from); break; + case T_CteScan: + retval = _copyCteScan(from); + break; + case T_WorkTableScan: + retval = _copyWorkTableScan(from); + break; case T_Join: retval = _copyJoin(from); break; *************** *** 3672,3677 **** --- 3783,3794 ---- case T_RowMarkClause: retval = _copyRowMarkClause(from); break; + case T_WithClause: + retval = _copyWithClause(from); + break; + case T_CommonTableExpr: + retval = _copyCommonTableExpr(from); + break; case T_FkConstraint: retval = _copyFkConstraint(from); break; *** src/backend/nodes/equalfuncs.c.orig Mon Sep 1 16:42:44 2008 --- src/backend/nodes/equalfuncs.c Tue Sep 30 10:50:31 2008 *************** *** 808,813 **** --- 808,815 ---- COMPARE_SCALAR_FIELD(hasAggs); COMPARE_SCALAR_FIELD(hasSubLinks); COMPARE_SCALAR_FIELD(hasDistinctOn); + COMPARE_SCALAR_FIELD(hasRecursive); + COMPARE_NODE_FIELD(cteList); COMPARE_NODE_FIELD(rtable); COMPARE_NODE_FIELD(jointree); COMPARE_NODE_FIELD(targetList); *************** *** 868,873 **** --- 870,876 ---- COMPARE_NODE_FIELD(whereClause); COMPARE_NODE_FIELD(groupClause); COMPARE_NODE_FIELD(havingClause); + COMPARE_NODE_FIELD(withClause); COMPARE_NODE_FIELD(valuesLists); COMPARE_NODE_FIELD(sortClause); COMPARE_NODE_FIELD(limitOffset); *************** *** 1932,1943 **** COMPARE_SCALAR_FIELD(rtekind); COMPARE_SCALAR_FIELD(relid); COMPARE_NODE_FIELD(subquery); COMPARE_NODE_FIELD(funcexpr); COMPARE_NODE_FIELD(funccoltypes); COMPARE_NODE_FIELD(funccoltypmods); COMPARE_NODE_FIELD(values_lists); ! COMPARE_SCALAR_FIELD(jointype); ! COMPARE_NODE_FIELD(joinaliasvars); COMPARE_NODE_FIELD(alias); COMPARE_NODE_FIELD(eref); COMPARE_SCALAR_FIELD(inh); --- 1935,1951 ---- COMPARE_SCALAR_FIELD(rtekind); COMPARE_SCALAR_FIELD(relid); COMPARE_NODE_FIELD(subquery); + COMPARE_SCALAR_FIELD(jointype); + COMPARE_NODE_FIELD(joinaliasvars); COMPARE_NODE_FIELD(funcexpr); COMPARE_NODE_FIELD(funccoltypes); COMPARE_NODE_FIELD(funccoltypmods); COMPARE_NODE_FIELD(values_lists); ! COMPARE_STRING_FIELD(ctename); ! COMPARE_SCALAR_FIELD(ctelevelsup); ! COMPARE_SCALAR_FIELD(self_reference); ! COMPARE_NODE_FIELD(ctecoltypes); ! COMPARE_NODE_FIELD(ctecoltypmods); COMPARE_NODE_FIELD(alias); COMPARE_NODE_FIELD(eref); COMPARE_SCALAR_FIELD(inh); *************** *** 1970,1975 **** --- 1978,2009 ---- } static bool + _equalWithClause(WithClause *a, WithClause *b) + { + COMPARE_NODE_FIELD(ctes); + COMPARE_SCALAR_FIELD(recursive); + COMPARE_LOCATION_FIELD(location); + + return true; + } + + static bool + _equalCommonTableExpr(CommonTableExpr *a, CommonTableExpr *b) + { + COMPARE_STRING_FIELD(ctename); + COMPARE_NODE_FIELD(aliascolnames); + COMPARE_NODE_FIELD(ctequery); + COMPARE_LOCATION_FIELD(location); + COMPARE_SCALAR_FIELD(cterecursive); + COMPARE_SCALAR_FIELD(cterefcount); + COMPARE_NODE_FIELD(ctecolnames); + COMPARE_NODE_FIELD(ctecoltypes); + COMPARE_NODE_FIELD(ctecoltypmods); + + return true; + } + + static bool _equalFkConstraint(FkConstraint *a, FkConstraint *b) { COMPARE_STRING_FIELD(constr_name); *************** *** 2593,2598 **** --- 2627,2638 ---- case T_RowMarkClause: retval = _equalRowMarkClause(a, b); break; + case T_WithClause: + retval = _equalWithClause(a, b); + break; + case T_CommonTableExpr: + retval = _equalCommonTableExpr(a, b); + break; case T_FkConstraint: retval = _equalFkConstraint(a, b); break; *** src/backend/nodes/nodeFuncs.c.orig Mon Sep 1 16:42:44 2008 --- src/backend/nodes/nodeFuncs.c Tue Sep 23 20:00:39 2008 *************** *** 870,875 **** --- 870,881 ---- /* XMLSERIALIZE keyword should always be the first thing */ loc = ((XmlSerialize *) expr)->location; break; + case T_WithClause: + loc = ((WithClause *) expr)->location; + break; + case T_CommonTableExpr: + loc = ((CommonTableExpr *) expr)->location; + break; default: /* for any other node type it's just unknown... */ loc = -1; *************** *** 1205,1210 **** --- 1211,1227 ---- case T_Query: /* Do nothing with a sub-Query, per discussion above */ break; + case T_CommonTableExpr: + { + CommonTableExpr *cte = (CommonTableExpr *) node; + + /* + * Invoke the walker on the CTE's Query node, so it + * can recurse into the sub-query if it wants to. + */ + return walker(cte->ctequery, context); + } + break; case T_List: foreach(temp, (List *) node) { *************** *** 1313,1318 **** --- 1330,1340 ---- return true; if (walker(query->limitCount, context)) return true; + if (!(flags & QTW_IGNORE_CTE_SUBQUERIES)) + { + if (walker((Node *) query->cteList, context)) + return true; + } if (range_table_walker(query->rtable, walker, context, flags)) return true; return false; *************** *** 1335,1344 **** --- 1357,1372 ---- { RangeTblEntry *rte = (RangeTblEntry *) lfirst(rt); + /* For historical reasons, visiting RTEs is not the default */ + if (flags & QTW_EXAMINE_RTES) + if (walker(rte, context)) + return true; + switch (rte->rtekind) { case RTE_RELATION: case RTE_SPECIAL: + case RTE_CTE: /* nothing to do */ break; case RTE_SUBQUERY: *************** *** 1806,1811 **** --- 1834,1854 ---- case T_Query: /* Do nothing with a sub-Query, per discussion above */ return node; + case T_CommonTableExpr: + { + CommonTableExpr *cte = (CommonTableExpr *) node; + CommonTableExpr *newnode; + + FLATCOPY(newnode, cte, CommonTableExpr); + + /* + * Also invoke the mutator on the CTE's Query node, so it + * can recurse into the sub-query if it wants to. + */ + MUTATE(newnode->ctequery, cte->ctequery, Node *); + return (Node *) newnode; + } + break; case T_List: { /* *************** *** 1935,1940 **** --- 1978,1987 ---- MUTATE(query->havingQual, query->havingQual, Node *); MUTATE(query->limitOffset, query->limitOffset, Node *); MUTATE(query->limitCount, query->limitCount, Node *); + if (!(flags & QTW_IGNORE_CTE_SUBQUERIES)) + MUTATE(query->cteList, query->cteList, List *); + else /* else copy CTE list as-is */ + query->cteList = copyObject(query->cteList); query->rtable = range_table_mutator(query->rtable, mutator, context, flags); return query; *************** *** 1964,1969 **** --- 2011,2017 ---- { case RTE_RELATION: case RTE_SPECIAL: + case RTE_CTE: /* we don't bother to copy eref, aliases, etc; OK? */ break; case RTE_SUBQUERY: *************** *** 2044,2046 **** --- 2092,2395 ---- else return mutator(node, context); } + + + /* + * raw_expression_tree_walker --- walk raw parse trees + * + * This has exactly the same API as expression_tree_walker, but instead of + * walking post-analysis parse trees, it knows how to walk the node types + * found in raw grammar output. (There is not currently any need for a + * combined walker, so we keep them separate in the name of efficiency.) + * Unlike expression_tree_walker, there is no special rule about query + * boundaries: we descend to everything that's possibly interesting. + * + * Currently, the node type coverage extends to SelectStmt and everything + * that could appear under it, but not other statement types. + */ + bool + raw_expression_tree_walker(Node *node, bool (*walker) (), void *context) + { + ListCell *temp; + + /* + * The walker has already visited the current node, and so we need only + * recurse into any sub-nodes it has. + */ + if (node == NULL) + return false; + + /* Guard against stack overflow due to overly complex expressions */ + check_stack_depth(); + + switch (nodeTag(node)) + { + case T_SetToDefault: + case T_CurrentOfExpr: + case T_Integer: + case T_Float: + case T_String: + case T_BitString: + case T_Null: + case T_ParamRef: + case T_A_Const: + case T_A_Star: + /* primitive node types with no subnodes */ + break; + case T_Alias: + /* we assume the colnames list isn't interesting */ + break; + case T_RangeVar: + return walker(((RangeVar *) node)->alias, context); + case T_SubLink: + { + SubLink *sublink = (SubLink *) node; + + if (walker(sublink->testexpr, context)) + return true; + /* we assume the operName is not interesting */ + if (walker(sublink->subselect, context)) + return true; + } + break; + case T_CaseExpr: + { + CaseExpr *caseexpr = (CaseExpr *) node; + + if (walker(caseexpr->arg, context)) + return true; + /* we assume walker doesn't care about CaseWhens, either */ + foreach(temp, caseexpr->args) + { + CaseWhen *when = (CaseWhen *) lfirst(temp); + + Assert(IsA(when, CaseWhen)); + if (walker(when->expr, context)) + return true; + if (walker(when->result, context)) + return true; + } + if (walker(caseexpr->defresult, context)) + return true; + } + break; + case T_RowExpr: + return walker(((RowExpr *) node)->args, context); + case T_CoalesceExpr: + return walker(((CoalesceExpr *) node)->args, context); + case T_MinMaxExpr: + return walker(((MinMaxExpr *) node)->args, context); + case T_XmlExpr: + { + XmlExpr *xexpr = (XmlExpr *) node; + + if (walker(xexpr->named_args, context)) + return true; + /* we assume walker doesn't care about arg_names */ + if (walker(xexpr->args, context)) + return true; + } + break; + case T_NullTest: + return walker(((NullTest *) node)->arg, context); + case T_BooleanTest: + return walker(((BooleanTest *) node)->arg, context); + case T_JoinExpr: + { + JoinExpr *join = (JoinExpr *) node; + + if (walker(join->larg, context)) + return true; + if (walker(join->rarg, context)) + return true; + if (walker(join->quals, context)) + return true; + if (walker(join->alias, context)) + return true; + /* using list is deemed uninteresting */ + } + break; + case T_IntoClause: + { + IntoClause *into = (IntoClause *) node; + + if (walker(into->rel, context)) + return true; + /* colNames, options are deemed uninteresting */ + } + break; + case T_List: + foreach(temp, (List *) node) + { + if (walker((Node *) lfirst(temp), context)) + return true; + } + break; + case T_SelectStmt: + { + SelectStmt *stmt = (SelectStmt *) node; + + if (walker(stmt->distinctClause, context)) + return true; + if (walker(stmt->intoClause, context)) + return true; + if (walker(stmt->targetList, context)) + return true; + if (walker(stmt->fromClause, context)) + return true; + if (walker(stmt->whereClause, context)) + return true; + if (walker(stmt->groupClause, context)) + return true; + if (walker(stmt->havingClause, context)) + return true; + if (walker(stmt->withClause, context)) + return true; + if (walker(stmt->valuesLists, context)) + return true; + if (walker(stmt->sortClause, context)) + return true; + if (walker(stmt->limitOffset, context)) + return true; + if (walker(stmt->limitCount, context)) + return true; + if (walker(stmt->lockingClause, context)) + return true; + if (walker(stmt->larg, context)) + return true; + if (walker(stmt->rarg, context)) + return true; + } + break; + case T_A_Expr: + { + A_Expr *expr = (A_Expr *) node; + + if (walker(expr->lexpr, context)) + return true; + if (walker(expr->rexpr, context)) + return true; + /* operator name is deemed uninteresting */ + } + break; + case T_ColumnRef: + /* we assume the fields contain nothing interesting */ + break; + case T_FuncCall: + { + FuncCall *fcall = (FuncCall *) node; + + if (walker(fcall->args, context)) + return true; + /* function name is deemed uninteresting */ + } + break; + case T_A_Indices: + { + A_Indices *indices = (A_Indices *) node; + + if (walker(indices->lidx, context)) + return true; + if (walker(indices->uidx, context)) + return true; + } + break; + case T_A_Indirection: + { + A_Indirection *indir = (A_Indirection *) node; + + if (walker(indir->arg, context)) + return true; + if (walker(indir->indirection, context)) + return true; + } + break; + case T_A_ArrayExpr: + return walker(((A_ArrayExpr *) node)->elements, context); + case T_ResTarget: + { + ResTarget *rt = (ResTarget *) node; + + if (walker(rt->indirection, context)) + return true; + if (walker(rt->val, context)) + return true; + } + break; + case T_TypeCast: + { + TypeCast *tc = (TypeCast *) node; + + if (walker(tc->arg, context)) + return true; + if (walker(tc->typename, context)) + return true; + } + break; + case T_SortBy: + return walker(((SortBy *) node)->node, context); + case T_RangeSubselect: + { + RangeSubselect *rs = (RangeSubselect *) node; + + if (walker(rs->subquery, context)) + return true; + if (walker(rs->alias, context)) + return true; + } + break; + case T_RangeFunction: + { + RangeFunction *rf = (RangeFunction *) node; + + if (walker(rf->funccallnode, context)) + return true; + if (walker(rf->alias, context)) + return true; + } + break; + case T_TypeName: + { + TypeName *tn = (TypeName *) node; + + if (walker(tn->typmods, context)) + return true; + if (walker(tn->arrayBounds, context)) + return true; + /* type name itself is deemed uninteresting */ + } + break; + case T_ColumnDef: + { + ColumnDef *coldef = (ColumnDef *) node; + + if (walker(coldef->typename, context)) + return true; + if (walker(coldef->raw_default, context)) + return true; + /* for now, constraints are ignored */ + } + break; + case T_LockingClause: + return walker(((LockingClause *) node)->lockedRels, context); + case T_XmlSerialize: + { + XmlSerialize *xs = (XmlSerialize *) node; + + if (walker(xs->expr, context)) + return true; + if (walker(xs->typename, context)) + return true; + } + break; + case T_WithClause: + return walker(((WithClause *) node)->ctes, context); + case T_CommonTableExpr: + return walker(((CommonTableExpr *) node)->ctequery, context); + default: + elog(ERROR, "unrecognized node type: %d", + (int) nodeTag(node)); + break; + } + return false; + } *** src/backend/nodes/outfuncs.c.orig Tue Sep 9 14:58:08 2008 --- src/backend/nodes/outfuncs.c Thu Oct 2 16:31:37 2008 *************** *** 332,337 **** --- 332,347 ---- } static void + _outRecursiveUnion(StringInfo str, RecursiveUnion *node) + { + WRITE_NODE_TYPE("RECURSIVEUNION"); + + _outPlanInfo(str, (Plan *) node); + + WRITE_INT_FIELD(wtParam); + } + + static void _outBitmapAnd(StringInfo str, BitmapAnd *node) { WRITE_NODE_TYPE("BITMAPAND"); *************** *** 447,452 **** --- 457,483 ---- } static void + _outCteScan(StringInfo str, CteScan *node) + { + WRITE_NODE_TYPE("CTESCAN"); + + _outScanInfo(str, (Scan *) node); + + WRITE_INT_FIELD(ctePlanId); + WRITE_INT_FIELD(cteParam); + } + + static void + _outWorkTableScan(StringInfo str, WorkTableScan *node) + { + WRITE_NODE_TYPE("WORKTABLESCAN"); + + _outScanInfo(str, (Scan *) node); + + WRITE_INT_FIELD(wtParam); + } + + static void _outJoin(StringInfo str, Join *node) { WRITE_NODE_TYPE("JOIN"); *************** *** 1382,1387 **** --- 1413,1419 ---- WRITE_NODE_FIELD(resultRelations); WRITE_NODE_FIELD(returningLists); WRITE_NODE_FIELD(init_plans); + WRITE_NODE_FIELD(cte_plan_ids); WRITE_NODE_FIELD(eq_classes); WRITE_NODE_FIELD(canon_pathkeys); WRITE_NODE_FIELD(left_join_clauses); *************** *** 1398,1403 **** --- 1430,1437 ---- WRITE_BOOL_FIELD(hasJoinRTEs); WRITE_BOOL_FIELD(hasHavingQual); WRITE_BOOL_FIELD(hasPseudoConstantQuals); + WRITE_BOOL_FIELD(hasRecursion); + WRITE_INT_FIELD(wt_param_id); } static void *************** *** 1648,1653 **** --- 1682,1688 ---- WRITE_NODE_FIELD(whereClause); WRITE_NODE_FIELD(groupClause); WRITE_NODE_FIELD(havingClause); + WRITE_NODE_FIELD(withClause); WRITE_NODE_FIELD(valuesLists); WRITE_NODE_FIELD(sortClause); WRITE_NODE_FIELD(limitOffset); *************** *** 1793,1798 **** --- 1828,1835 ---- WRITE_BOOL_FIELD(hasAggs); WRITE_BOOL_FIELD(hasSubLinks); WRITE_BOOL_FIELD(hasDistinctOn); + WRITE_BOOL_FIELD(hasRecursive); + WRITE_NODE_FIELD(cteList); WRITE_NODE_FIELD(rtable); WRITE_NODE_FIELD(jointree); WRITE_NODE_FIELD(targetList); *************** *** 1829,1834 **** --- 1866,1897 ---- } static void + _outWithClause(StringInfo str, WithClause *node) + { + WRITE_NODE_TYPE("WITHCLAUSE"); + + WRITE_NODE_FIELD(ctes); + WRITE_BOOL_FIELD(recursive); + WRITE_LOCATION_FIELD(location); + } + + static void + _outCommonTableExpr(StringInfo str, CommonTableExpr *node) + { + WRITE_NODE_TYPE("COMMONTABLEEXPR"); + + WRITE_STRING_FIELD(ctename); + WRITE_NODE_FIELD(aliascolnames); + WRITE_NODE_FIELD(ctequery); + WRITE_LOCATION_FIELD(location); + WRITE_BOOL_FIELD(cterecursive); + WRITE_INT_FIELD(cterefcount); + WRITE_NODE_FIELD(ctecolnames); + WRITE_NODE_FIELD(ctecoltypes); + WRITE_NODE_FIELD(ctecoltypmods); + } + + static void _outSetOperationStmt(StringInfo str, SetOperationStmt *node) { WRITE_NODE_TYPE("SETOPERATIONSTMT"); *************** *** 1861,1866 **** --- 1924,1933 ---- case RTE_SUBQUERY: WRITE_NODE_FIELD(subquery); break; + case RTE_JOIN: + WRITE_ENUM_FIELD(jointype, JoinType); + WRITE_NODE_FIELD(joinaliasvars); + break; case RTE_FUNCTION: WRITE_NODE_FIELD(funcexpr); WRITE_NODE_FIELD(funccoltypes); *************** *** 1869,1877 **** case RTE_VALUES: WRITE_NODE_FIELD(values_lists); break; ! case RTE_JOIN: ! WRITE_ENUM_FIELD(jointype, JoinType); ! WRITE_NODE_FIELD(joinaliasvars); break; default: elog(ERROR, "unrecognized RTE kind: %d", (int) node->rtekind); --- 1936,1947 ---- case RTE_VALUES: WRITE_NODE_FIELD(values_lists); break; ! case RTE_CTE: ! WRITE_STRING_FIELD(ctename); ! WRITE_UINT_FIELD(ctelevelsup); ! WRITE_BOOL_FIELD(self_reference); ! WRITE_NODE_FIELD(ctecoltypes); ! WRITE_NODE_FIELD(ctecoltypmods); break; default: elog(ERROR, "unrecognized RTE kind: %d", (int) node->rtekind); *************** *** 2060,2065 **** --- 2130,2154 ---- } static void + _outRangeSubselect(StringInfo str, RangeSubselect *node) + { + WRITE_NODE_TYPE("RANGESUBSELECT"); + + WRITE_NODE_FIELD(subquery); + WRITE_NODE_FIELD(alias); + } + + static void + _outRangeFunction(StringInfo str, RangeFunction *node) + { + WRITE_NODE_TYPE("RANGEFUNCTION"); + + WRITE_NODE_FIELD(funccallnode); + WRITE_NODE_FIELD(alias); + WRITE_NODE_FIELD(coldeflist); + } + + static void _outConstraint(StringInfo str, Constraint *node) { WRITE_NODE_TYPE("CONSTRAINT"); *************** *** 2159,2164 **** --- 2248,2256 ---- case T_Append: _outAppend(str, obj); break; + case T_RecursiveUnion: + _outRecursiveUnion(str, obj); + break; case T_BitmapAnd: _outBitmapAnd(str, obj); break; *************** *** 2192,2197 **** --- 2284,2295 ---- case T_ValuesScan: _outValuesScan(str, obj); break; + case T_CteScan: + _outCteScan(str, obj); + break; + case T_WorkTableScan: + _outWorkTableScan(str, obj); + break; case T_Join: _outJoin(str, obj); break; *************** *** 2473,2478 **** --- 2571,2582 ---- case T_RowMarkClause: _outRowMarkClause(str, obj); break; + case T_WithClause: + _outWithClause(str, obj); + break; + case T_CommonTableExpr: + _outCommonTableExpr(str, obj); + break; case T_SetOperationStmt: _outSetOperationStmt(str, obj); break; *************** *** 2509,2514 **** --- 2613,2624 ---- case T_SortBy: _outSortBy(str, obj); break; + case T_RangeSubselect: + _outRangeSubselect(str, obj); + break; + case T_RangeFunction: + _outRangeFunction(str, obj); + break; case T_Constraint: _outConstraint(str, obj); break; *** src/backend/nodes/print.c.orig Wed Jun 18 20:46:04 2008 --- src/backend/nodes/print.c Mon Sep 22 15:03:48 2008 *************** *** 272,277 **** --- 272,285 ---- printf("%d\t%s\t[subquery]", i, rte->eref->aliasname); break; + case RTE_JOIN: + printf("%d\t%s\t[join]", + i, rte->eref->aliasname); + break; + case RTE_SPECIAL: + printf("%d\t%s\t[special]", + i, rte->eref->aliasname); + break; case RTE_FUNCTION: printf("%d\t%s\t[rangefunction]", i, rte->eref->aliasname); *************** *** 280,291 **** printf("%d\t%s\t[values list]", i, rte->eref->aliasname); break; ! case RTE_JOIN: ! printf("%d\t%s\t[join]", ! i, rte->eref->aliasname); ! break; ! case RTE_SPECIAL: ! printf("%d\t%s\t[special]", i, rte->eref->aliasname); break; default: --- 288,295 ---- printf("%d\t%s\t[values list]", i, rte->eref->aliasname); break; ! case RTE_CTE: ! printf("%d\t%s\t[cte]", i, rte->eref->aliasname); break; default: *** src/backend/nodes/readfuncs.c.orig Mon Sep 1 16:42:44 2008 --- src/backend/nodes/readfuncs.c Tue Sep 30 10:50:32 2008 *************** *** 155,160 **** --- 155,162 ---- READ_BOOL_FIELD(hasAggs); READ_BOOL_FIELD(hasSubLinks); READ_BOOL_FIELD(hasDistinctOn); + READ_BOOL_FIELD(hasRecursive); + READ_NODE_FIELD(cteList); READ_NODE_FIELD(rtable); READ_NODE_FIELD(jointree); READ_NODE_FIELD(targetList); *************** *** 231,236 **** --- 233,259 ---- } /* + * _readCommonTableExpr + */ + static CommonTableExpr * + _readCommonTableExpr(void) + { + READ_LOCALS(CommonTableExpr); + + READ_STRING_FIELD(ctename); + READ_NODE_FIELD(aliascolnames); + READ_NODE_FIELD(ctequery); + READ_LOCATION_FIELD(location); + READ_BOOL_FIELD(cterecursive); + READ_INT_FIELD(cterefcount); + READ_NODE_FIELD(ctecolnames); + READ_NODE_FIELD(ctecoltypes); + READ_NODE_FIELD(ctecoltypmods); + + READ_DONE(); + } + + /* * _readSetOperationStmt */ static SetOperationStmt * *************** *** 1007,1012 **** --- 1030,1039 ---- case RTE_SUBQUERY: READ_NODE_FIELD(subquery); break; + case RTE_JOIN: + READ_ENUM_FIELD(jointype, JoinType); + READ_NODE_FIELD(joinaliasvars); + break; case RTE_FUNCTION: READ_NODE_FIELD(funcexpr); READ_NODE_FIELD(funccoltypes); *************** *** 1015,1023 **** case RTE_VALUES: READ_NODE_FIELD(values_lists); break; ! case RTE_JOIN: ! READ_ENUM_FIELD(jointype, JoinType); ! READ_NODE_FIELD(joinaliasvars); break; default: elog(ERROR, "unrecognized RTE kind: %d", --- 1042,1053 ---- case RTE_VALUES: READ_NODE_FIELD(values_lists); break; ! case RTE_CTE: ! READ_STRING_FIELD(ctename); ! READ_UINT_FIELD(ctelevelsup); ! READ_BOOL_FIELD(self_reference); ! READ_NODE_FIELD(ctecoltypes); ! READ_NODE_FIELD(ctecoltypmods); break; default: elog(ERROR, "unrecognized RTE kind: %d", *************** *** 1060,1065 **** --- 1090,1097 ---- return_value = _readSortGroupClause(); else if (MATCH("ROWMARKCLAUSE", 13)) return_value = _readRowMarkClause(); + else if (MATCH("COMMONTABLEEXPR", 15)) + return_value = _readCommonTableExpr(); else if (MATCH("SETOPERATIONSTMT", 16)) return_value = _readSetOperationStmt(); else if (MATCH("ALIAS", 5)) *** src/backend/optimizer/path/allpaths.c.orig Mon Aug 25 18:42:32 2008 --- src/backend/optimizer/path/allpaths.c Fri Oct 3 14:41:21 2008 *************** *** 57,62 **** --- 57,66 ---- RangeTblEntry *rte); static void set_values_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte); + static void set_cte_pathlist(PlannerInfo *root, RelOptInfo *rel, + RangeTblEntry *rte); + static void set_worktable_pathlist(PlannerInfo *root, RelOptInfo *rel, + RangeTblEntry *rte); static RelOptInfo *make_rel_from_joinlist(PlannerInfo *root, List *joinlist); static bool subquery_is_pushdown_safe(Query *subquery, Query *topquery, bool *differentTypes); *************** *** 173,186 **** } else if (rel->rtekind == RTE_FUNCTION) { ! /* RangeFunction --- generate a separate plan for it */ set_function_pathlist(root, rel, rte); } else if (rel->rtekind == RTE_VALUES) { ! /* Values list --- generate a separate plan for it */ set_values_pathlist(root, rel, rte); } else { /* Plain relation */ --- 177,198 ---- } else if (rel->rtekind == RTE_FUNCTION) { ! /* RangeFunction --- generate a suitable path for it */ set_function_pathlist(root, rel, rte); } else if (rel->rtekind == RTE_VALUES) { ! /* Values list --- generate a suitable path for it */ set_values_pathlist(root, rel, rte); } + else if (rel->rtekind == RTE_CTE) + { + /* CTE reference --- generate a suitable path for it */ + if (rte->self_reference) + set_worktable_pathlist(root, rel, rte); + else + set_cte_pathlist(root, rel, rte); + } else { /* Plain relation */ *************** *** 585,592 **** /* Generate the plan for the subquery */ rel->subplan = subquery_planner(root->glob, subquery, ! root->query_level + 1, ! tuple_fraction, &subroot); rel->subrtable = subroot->parse->rtable; --- 597,604 ---- /* Generate the plan for the subquery */ rel->subplan = subquery_planner(root->glob, subquery, ! root, ! false, tuple_fraction, &subroot); rel->subrtable = subroot->parse->rtable; *************** *** 641,646 **** --- 653,756 ---- } /* + * set_cte_pathlist + * Build the (single) access path for a non-self-reference CTE RTE + */ + static void + set_cte_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) + { + Plan *cteplan; + PlannerInfo *cteroot; + Index levelsup; + int ndx; + ListCell *lc; + int plan_id; + + /* + * Find the referenced CTE, and locate the plan previously made for it. + */ + levelsup = rte->ctelevelsup; + cteroot = root; + while (levelsup-- > 0) + { + cteroot = cteroot->parent_root; + if (!cteroot) /* shouldn't happen */ + elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename); + } + /* + * Note: cte_plan_ids can be shorter than cteList, if we are still working + * on planning the CTEs (ie, this is a side-reference from another CTE). + * So we mustn't use forboth here. + */ + ndx = 0; + foreach(lc, cteroot->parse->cteList) + { + CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc); + + if (strcmp(cte->ctename, rte->ctename) == 0) + break; + ndx++; + } + if (lc == NULL) /* shouldn't happen */ + elog(ERROR, "could not find CTE \"%s\"", rte->ctename); + if (ndx >= list_length(cteroot->cte_plan_ids)) + elog(ERROR, "could not find plan for CTE \"%s\"", rte->ctename); + plan_id = list_nth_int(cteroot->cte_plan_ids, ndx); + Assert(plan_id > 0); + cteplan = (Plan *) list_nth(root->glob->subplans, plan_id - 1); + + /* Mark rel with estimated output rows, width, etc */ + set_cte_size_estimates(root, rel, cteplan); + + /* Generate appropriate path */ + add_path(rel, create_ctescan_path(root, rel)); + + /* Select cheapest path (pretty easy in this case...) */ + set_cheapest(rel); + } + + /* + * set_worktable_pathlist + * Build the (single) access path for a self-reference CTE RTE + */ + static void + set_worktable_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) + { + Plan *cteplan; + PlannerInfo *cteroot; + Index levelsup; + + /* + * We need to find the non-recursive term's plan, which is in the plan + * level that's processing the recursive UNION, which is one level + * *below* where the CTE comes from. + */ + levelsup = rte->ctelevelsup; + if (levelsup == 0) /* shouldn't happen */ + elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename); + levelsup--; + cteroot = root; + while (levelsup-- > 0) + { + cteroot = cteroot->parent_root; + if (!cteroot) /* shouldn't happen */ + elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename); + } + cteplan = cteroot->non_recursive_plan; + if (!cteplan) /* shouldn't happen */ + elog(ERROR, "could not find plan for CTE \"%s\"", rte->ctename); + + /* Mark rel with estimated output rows, width, etc */ + set_cte_size_estimates(root, rel, cteplan); + + /* Generate appropriate path */ + add_path(rel, create_worktablescan_path(root, rel)); + + /* Select cheapest path (pretty easy in this case...) */ + set_cheapest(rel); + } + + /* * make_rel_from_joinlist * Build access paths using a "joinlist" to guide the join path search. * *** src/backend/optimizer/path/clausesel.c.orig Thu Aug 21 20:16:03 2008 --- src/backend/optimizer/path/clausesel.c Fri Oct 3 13:09:30 2008 *************** *** 550,578 **** if (var->varlevelsup == 0 && (varRelid == 0 || varRelid == (int) var->varno)) { ! RangeTblEntry *rte = planner_rt_fetch(var->varno, root); ! ! if (rte->rtekind == RTE_SUBQUERY) ! { ! /* ! * XXX not smart about subquery references... any way to do ! * better than default? ! */ ! } ! else ! { ! /* ! * A Var at the top of a clause must be a bool Var. This is ! * equivalent to the clause reln.attribute = 't', so we ! * compute the selectivity as if that is what we have. ! */ ! s1 = restriction_selectivity(root, ! BooleanEqualOperator, ! list_make2(var, ! makeBoolConst(true, ! false)), ! varRelid); ! } } } else if (IsA(clause, Const)) --- 550,566 ---- if (var->varlevelsup == 0 && (varRelid == 0 || varRelid == (int) var->varno)) { ! /* ! * A Var at the top of a clause must be a bool Var. This is ! * equivalent to the clause reln.attribute = 't', so we ! * compute the selectivity as if that is what we have. ! */ ! s1 = restriction_selectivity(root, ! BooleanEqualOperator, ! list_make2(var, ! makeBoolConst(true, ! false)), ! varRelid); } } else if (IsA(clause, Const)) *** src/backend/optimizer/path/costsize.c.orig Fri Sep 5 17:07:29 2008 --- src/backend/optimizer/path/costsize.c Fri Oct 3 14:09:22 2008 *************** *** 934,939 **** --- 934,1017 ---- } /* + * cost_ctescan + * Determines and returns the cost of scanning a CTE RTE. + * + * Note: this is used for both self-reference and regular CTEs; the + * possible cost differences are below the threshold of what we could + * estimate accurately anyway. Note that the costs of evaluating the + * referenced CTE query are added into the final plan as initplan costs, + * and should NOT be counted here. + */ + void + cost_ctescan(Path *path, PlannerInfo *root, RelOptInfo *baserel) + { + Cost startup_cost = 0; + Cost run_cost = 0; + Cost cpu_per_tuple; + + /* Should only be applied to base relations that are CTEs */ + Assert(baserel->relid > 0); + Assert(baserel->rtekind == RTE_CTE); + + /* Charge one CPU tuple cost per row for tuplestore manipulation */ + cpu_per_tuple = cpu_tuple_cost; + + /* Add scanning CPU costs */ + startup_cost += baserel->baserestrictcost.startup; + cpu_per_tuple += cpu_tuple_cost + baserel->baserestrictcost.per_tuple; + run_cost += cpu_per_tuple * baserel->tuples; + + path->startup_cost = startup_cost; + path->total_cost = startup_cost + run_cost; + } + + /* + * cost_recursive_union + * Determines and returns the cost of performing a recursive union, + * and also the estimated output size. + * + * We are given Plans for the nonrecursive and recursive terms. + * + * Note that the arguments and output are Plans, not Paths as in most of + * the rest of this module. That's because we don't bother setting up a + * Path representation for recursive union --- we have only one way to do it. + */ + void + cost_recursive_union(Plan *runion, Plan *nrterm, Plan *rterm) + { + Cost startup_cost; + Cost total_cost; + double total_rows; + + /* We probably have decent estimates for the non-recursive term */ + startup_cost = nrterm->startup_cost; + total_cost = nrterm->total_cost; + total_rows = nrterm->plan_rows; + + /* + * We arbitrarily assume that about 10 recursive iterations will be + * needed, and that we've managed to get a good fix on the cost and + * output size of each one of them. These are mighty shaky assumptions + * but it's hard to see how to do better. + */ + total_cost += 10 * rterm->total_cost; + total_rows += 10 * rterm->plan_rows; + + /* + * Also charge cpu_tuple_cost per row to account for the costs of + * manipulating the tuplestores. (We don't worry about possible + * spill-to-disk costs.) + */ + total_cost += cpu_tuple_cost * total_rows; + + runion->startup_cost = startup_cost; + runion->total_cost = total_cost; + runion->plan_rows = total_rows; + runion->plan_width = Max(nrterm->plan_width, rterm->plan_width); + } + + /* * cost_sort * Determines and returns the cost of sorting a relation, including * the cost of reading the input data. *************** *** 2475,2480 **** --- 2553,2596 ---- set_baserel_size_estimates(root, rel); } + /* + * set_cte_size_estimates + * Set the size estimates for a base relation that is a CTE reference. + * + * The rel's targetlist and restrictinfo list must have been constructed + * already, and we need the completed plan for the CTE (if a regular CTE) + * or the non-recursive term (if a self-reference). + * + * We set the same fields as set_baserel_size_estimates. + */ + void + set_cte_size_estimates(PlannerInfo *root, RelOptInfo *rel, Plan *cteplan) + { + RangeTblEntry *rte; + + /* Should only be applied to base relations that are CTE references */ + Assert(rel->relid > 0); + rte = planner_rt_fetch(rel->relid, root); + Assert(rte->rtekind == RTE_CTE); + + if (rte->self_reference) + { + /* + * In a self-reference, arbitrarily assume the average worktable + * size is about 10 times the nonrecursive term's size. + */ + rel->tuples = 10 * cteplan->plan_rows; + } + else + { + /* Otherwise just believe the CTE plan's output estimate */ + rel->tuples = cteplan->plan_rows; + } + + /* Now estimate number of output rows, etc */ + set_baserel_size_estimates(root, rel); + } + /* * set_rel_width *** src/backend/optimizer/path/joinpath.c.orig Thu Aug 14 14:47:59 2008 --- src/backend/optimizer/path/joinpath.c Fri Oct 3 15:15:11 2008 *************** *** 408,417 **** * If the cheapest inner path is a join or seqscan, we should consider * materializing it. (This is a heuristic: we could consider it * always, but for inner indexscans it's probably a waste of time.) */ ! if (!(IsA(inner_cheapest_total, IndexPath) || ! IsA(inner_cheapest_total, BitmapHeapPath) || ! IsA(inner_cheapest_total, TidPath))) matpath = (Path *) create_material_path(innerrel, inner_cheapest_total); --- 408,422 ---- * If the cheapest inner path is a join or seqscan, we should consider * materializing it. (This is a heuristic: we could consider it * always, but for inner indexscans it's probably a waste of time.) + * Also skip it if the inner path materializes its output anyway. */ ! if (!(inner_cheapest_total->pathtype == T_IndexScan || ! inner_cheapest_total->pathtype == T_BitmapHeapScan || ! inner_cheapest_total->pathtype == T_TidScan || ! inner_cheapest_total->pathtype == T_Material || ! inner_cheapest_total->pathtype == T_FunctionScan || ! inner_cheapest_total->pathtype == T_CteScan || ! inner_cheapest_total->pathtype == T_WorkTableScan)) matpath = (Path *) create_material_path(innerrel, inner_cheapest_total); *** src/backend/optimizer/plan/createplan.c.orig Fri Sep 5 17:07:29 2008 --- src/backend/optimizer/plan/createplan.c Fri Oct 3 15:03:38 2008 *************** *** 62,67 **** --- 62,71 ---- List *tlist, List *scan_clauses); static ValuesScan *create_valuesscan_plan(PlannerInfo *root, Path *best_path, List *tlist, List *scan_clauses); + static CteScan *create_ctescan_plan(PlannerInfo *root, Path *best_path, + List *tlist, List *scan_clauses); + static WorkTableScan *create_worktablescan_plan(PlannerInfo *root, Path *best_path, + List *tlist, List *scan_clauses); static NestLoop *create_nestloop_plan(PlannerInfo *root, NestPath *best_path, Plan *outer_plan, Plan *inner_plan); static MergeJoin *create_mergejoin_plan(PlannerInfo *root, MergePath *best_path, *************** *** 93,98 **** --- 97,106 ---- List *funccoltypes, List *funccoltypmods); static ValuesScan *make_valuesscan(List *qptlist, List *qpqual, Index scanrelid, List *values_lists); + static CteScan *make_ctescan(List *qptlist, List *qpqual, + Index scanrelid, int ctePlanId, int cteParam); + static WorkTableScan *make_worktablescan(List *qptlist, List *qpqual, + Index scanrelid, int wtParam); static BitmapAnd *make_bitmap_and(List *bitmapplans); static BitmapOr *make_bitmap_or(List *bitmapplans); static NestLoop *make_nestloop(List *tlist, *************** *** 148,153 **** --- 156,163 ---- case T_SubqueryScan: case T_FunctionScan: case T_ValuesScan: + case T_CteScan: + case T_WorkTableScan: plan = create_scan_plan(root, best_path); break; case T_HashJoin: *************** *** 270,275 **** --- 280,299 ---- scan_clauses); break; + case T_CteScan: + plan = (Plan *) create_ctescan_plan(root, + best_path, + tlist, + scan_clauses); + break; + + case T_WorkTableScan: + plan = (Plan *) create_worktablescan_plan(root, + best_path, + tlist, + scan_clauses); + break; + default: elog(ERROR, "unrecognized node type: %d", (int) best_path->pathtype); *************** *** 324,335 **** /* * We can do this for real relation scans, subquery scans, function scans, ! * and values scans (but not for, eg, joins). */ if (rel->rtekind != RTE_RELATION && rel->rtekind != RTE_SUBQUERY && rel->rtekind != RTE_FUNCTION && ! rel->rtekind != RTE_VALUES) return false; /* --- 348,360 ---- /* * We can do this for real relation scans, subquery scans, function scans, ! * values scans, and CTE scans (but not for, eg, joins). */ if (rel->rtekind != RTE_RELATION && rel->rtekind != RTE_SUBQUERY && rel->rtekind != RTE_FUNCTION && ! rel->rtekind != RTE_VALUES && ! rel->rtekind != RTE_CTE) return false; /* *************** *** 375,380 **** --- 400,407 ---- case T_SubqueryScan: case T_FunctionScan: case T_ValuesScan: + case T_CteScan: + case T_WorkTableScan: plan->targetlist = build_relation_tlist(path->parent); break; default: *************** *** 1335,1340 **** --- 1362,1506 ---- return scan_plan; } + /* + * create_ctescan_plan + * Returns a ctescan plan for the base relation scanned by 'best_path' + * with restriction clauses 'scan_clauses' and targetlist 'tlist'. + */ + static CteScan * + create_ctescan_plan(PlannerInfo *root, Path *best_path, + List *tlist, List *scan_clauses) + { + CteScan *scan_plan; + Index scan_relid = best_path->parent->relid; + RangeTblEntry *rte; + SubPlan *ctesplan = NULL; + int plan_id; + int cte_param_id; + PlannerInfo *cteroot; + Index levelsup; + int ndx; + ListCell *lc; + + Assert(scan_relid > 0); + rte = planner_rt_fetch(scan_relid, root); + Assert(rte->rtekind == RTE_CTE); + Assert(!rte->self_reference); + + /* + * Find the referenced CTE, and locate the SubPlan previously made for it. + */ + levelsup = rte->ctelevelsup; + cteroot = root; + while (levelsup-- > 0) + { + cteroot = cteroot->parent_root; + if (!cteroot) /* shouldn't happen */ + elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename); + } + /* + * Note: cte_plan_ids can be shorter than cteList, if we are still working + * on planning the CTEs (ie, this is a side-reference from another CTE). + * So we mustn't use forboth here. + */ + ndx = 0; + foreach(lc, cteroot->parse->cteList) + { + CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc); + + if (strcmp(cte->ctename, rte->ctename) == 0) + break; + ndx++; + } + if (lc == NULL) /* shouldn't happen */ + elog(ERROR, "could not find CTE \"%s\"", rte->ctename); + if (ndx >= list_length(cteroot->cte_plan_ids)) + elog(ERROR, "could not find plan for CTE \"%s\"", rte->ctename); + plan_id = list_nth_int(cteroot->cte_plan_ids, ndx); + Assert(plan_id > 0); + foreach(lc, cteroot->init_plans) + { + ctesplan = (SubPlan *) lfirst(lc); + if (ctesplan->plan_id == plan_id) + break; + } + if (lc == NULL) /* shouldn't happen */ + elog(ERROR, "could not find plan for CTE \"%s\"", rte->ctename); + + /* + * We need the CTE param ID, which is the sole member of the + * SubPlan's setParam list. + */ + cte_param_id = linitial_int(ctesplan->setParam); + + /* Sort clauses into best execution order */ + scan_clauses = order_qual_clauses(root, scan_clauses); + + /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */ + scan_clauses = extract_actual_clauses(scan_clauses, false); + + scan_plan = make_ctescan(tlist, scan_clauses, scan_relid, + plan_id, cte_param_id); + + copy_path_costsize(&scan_plan->scan.plan, best_path); + + return scan_plan; + } + + /* + * create_worktablescan_plan + * Returns a worktablescan plan for the base relation scanned by 'best_path' + * with restriction clauses 'scan_clauses' and targetlist 'tlist'. + */ + static WorkTableScan * + create_worktablescan_plan(PlannerInfo *root, Path *best_path, + List *tlist, List *scan_clauses) + { + WorkTableScan *scan_plan; + Index scan_relid = best_path->parent->relid; + RangeTblEntry *rte; + Index levelsup; + PlannerInfo *cteroot; + + Assert(scan_relid > 0); + rte = planner_rt_fetch(scan_relid, root); + Assert(rte->rtekind == RTE_CTE); + Assert(rte->self_reference); + + /* + * We need to find the worktable param ID, which is in the plan level + * that's processing the recursive UNION, which is one level *below* + * where the CTE comes from. + */ + levelsup = rte->ctelevelsup; + if (levelsup == 0) /* shouldn't happen */ + elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename); + levelsup--; + cteroot = root; + while (levelsup-- > 0) + { + cteroot = cteroot->parent_root; + if (!cteroot) /* shouldn't happen */ + elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename); + } + if (cteroot->wt_param_id < 0) /* shouldn't happen */ + elog(ERROR, "could not find param ID for CTE \"%s\"", rte->ctename); + + /* Sort clauses into best execution order */ + scan_clauses = order_qual_clauses(root, scan_clauses); + + /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */ + scan_clauses = extract_actual_clauses(scan_clauses, false); + + scan_plan = make_worktablescan(tlist, scan_clauses, scan_relid, + cteroot->wt_param_id); + + copy_path_costsize(&scan_plan->scan.plan, best_path); + + return scan_plan; + } + + /***************************************************************************** * * JOIN METHODS *************** *** 2291,2296 **** --- 2457,2504 ---- return node; } + static CteScan * + make_ctescan(List *qptlist, + List *qpqual, + Index scanrelid, + int ctePlanId, + int cteParam) + { + CteScan *node = makeNode(CteScan); + Plan *plan = &node->scan.plan; + + /* cost should be inserted by caller */ + plan->targetlist = qptlist; + plan->qual = qpqual; + plan->lefttree = NULL; + plan->righttree = NULL; + node->scan.scanrelid = scanrelid; + node->ctePlanId = ctePlanId; + node->cteParam = cteParam; + + return node; + } + + static WorkTableScan * + make_worktablescan(List *qptlist, + List *qpqual, + Index scanrelid, + int wtParam) + { + WorkTableScan *node = makeNode(WorkTableScan); + Plan *plan = &node->scan.plan; + + /* cost should be inserted by caller */ + plan->targetlist = qptlist; + plan->qual = qpqual; + plan->lefttree = NULL; + plan->righttree = NULL; + node->scan.scanrelid = scanrelid; + node->wtParam = wtParam; + + return node; + } + Append * make_append(List *appendplans, bool isTarget, List *tlist) { *************** *** 2333,2338 **** --- 2541,2566 ---- return node; } + RecursiveUnion * + make_recursive_union(List *tlist, + Plan *lefttree, + Plan *righttree, + int wtParam) + { + RecursiveUnion *node = makeNode(RecursiveUnion); + Plan *plan = &node->plan; + + cost_recursive_union(plan, lefttree, righttree); + + plan->targetlist = tlist; + plan->qual = NIL; + plan->lefttree = lefttree; + plan->righttree = righttree; + node->wtParam = wtParam; + + return node; + } + static BitmapAnd * make_bitmap_and(List *bitmapplans) { *************** *** 3284,3289 **** --- 3512,3518 ---- case T_SetOp: case T_Limit: case T_Append: + case T_RecursiveUnion: return false; default: break; *** src/backend/optimizer/plan/planner.c.orig Tue Sep 9 14:58:08 2008 --- src/backend/optimizer/plan/planner.c Thu Oct 2 14:47:27 2008 *************** *** 173,179 **** } /* primary planning entry point (may recurse for subqueries) */ ! top_plan = subquery_planner(glob, parse, 1, tuple_fraction, &root); /* * If creating a plan for a scrollable cursor, make sure it can run --- 173,180 ---- } /* primary planning entry point (may recurse for subqueries) */ ! top_plan = subquery_planner(glob, parse, NULL, ! false, tuple_fraction, &root); /* * If creating a plan for a scrollable cursor, make sure it can run *************** *** 228,234 **** * * glob is the global state for the current planner run. * parse is the querytree produced by the parser & rewriter. ! * level is the current recursion depth (1 at the top-level Query). * tuple_fraction is the fraction of tuples we expect will be retrieved. * tuple_fraction is interpreted as explained for grouping_planner, below. * --- 229,236 ---- * * glob is the global state for the current planner run. * parse is the querytree produced by the parser & rewriter. ! * parent_root is the immediate parent Query's info (NULL at the top level). ! * hasRecursion is true if this is a recursive WITH query. * tuple_fraction is the fraction of tuples we expect will be retrieved. * tuple_fraction is interpreted as explained for grouping_planner, below. * *************** *** 249,255 **** */ Plan * subquery_planner(PlannerGlobal *glob, Query *parse, ! Index level, double tuple_fraction, PlannerInfo **subroot) { int num_old_subplans = list_length(glob->subplans); --- 251,258 ---- */ Plan * subquery_planner(PlannerGlobal *glob, Query *parse, ! PlannerInfo *parent_root, ! bool hasRecursion, double tuple_fraction, PlannerInfo **subroot) { int num_old_subplans = list_length(glob->subplans); *************** *** 263,274 **** root = makeNode(PlannerInfo); root->parse = parse; root->glob = glob; ! root->query_level = level; root->planner_cxt = CurrentMemoryContext; root->init_plans = NIL; root->eq_classes = NIL; root->append_rel_list = NIL; /* * Look for ANY and EXISTS SubLinks in WHERE and JOIN/ON clauses, and try * to transform them into joins. Note that this step does not descend --- 266,293 ---- root = makeNode(PlannerInfo); root->parse = parse; root->glob = glob; ! root->query_level = parent_root ? parent_root->query_level + 1 : 1; ! root->parent_root = parent_root; root->planner_cxt = CurrentMemoryContext; root->init_plans = NIL; + root->cte_plan_ids = NIL; root->eq_classes = NIL; root->append_rel_list = NIL; + root->hasRecursion = hasRecursion; + if (hasRecursion) + root->wt_param_id = SS_assign_worktable_param(root); + else + root->wt_param_id = -1; + root->non_recursive_plan = NULL; + + /* + * If there is a WITH list, process each WITH query and build an + * initplan SubPlan structure for it. + */ + if (parse->cteList) + SS_process_ctes(root); + /* * Look for ANY and EXISTS SubLinks in WHERE and JOIN/ON clauses, and try * to transform them into joins. Note that this step does not descend *************** *** 776,782 **** /* * Construct the plan for set operations. The result will not need ! * any work except perhaps a top-level sort and/or LIMIT. */ result_plan = plan_set_operations(root, tuple_fraction, &set_sortclauses); --- 795,803 ---- /* * Construct the plan for set operations. The result will not need ! * any work except perhaps a top-level sort and/or LIMIT. Note that ! * any special work for recursive unions is the responsibility of ! * plan_set_operations. */ result_plan = plan_set_operations(root, tuple_fraction, &set_sortclauses); *************** *** 838,843 **** --- 859,867 ---- MemSet(&agg_counts, 0, sizeof(AggClauseCounts)); + /* A recursive query should always have setOperations */ + Assert(!root->hasRecursion); + /* Preprocess GROUP BY clause, if any */ if (parse->groupClause) preprocess_groupclause(root); *** src/backend/optimizer/plan/setrefs.c.orig Tue Sep 9 14:58:08 2008 --- src/backend/optimizer/plan/setrefs.c Thu Oct 2 14:47:28 2008 *************** *** 201,211 **** /* zap unneeded sub-structure */ newrte->subquery = NULL; newrte->funcexpr = NULL; newrte->funccoltypes = NIL; newrte->funccoltypmods = NIL; newrte->values_lists = NIL; ! newrte->joinaliasvars = NIL; glob->finalrtable = lappend(glob->finalrtable, newrte); --- 201,213 ---- /* zap unneeded sub-structure */ newrte->subquery = NULL; + newrte->joinaliasvars = NIL; newrte->funcexpr = NULL; newrte->funccoltypes = NIL; newrte->funccoltypmods = NIL; newrte->values_lists = NIL; ! newrte->ctecoltypes = NIL; ! newrte->ctecoltypmods = NIL; glob->finalrtable = lappend(glob->finalrtable, newrte); *************** *** 343,349 **** --- 345,372 ---- fix_scan_list(glob, splan->values_lists, rtoffset); } break; + case T_CteScan: + { + CteScan *splan = (CteScan *) plan; + + splan->scan.scanrelid += rtoffset; + splan->scan.plan.targetlist = + fix_scan_list(glob, splan->scan.plan.targetlist, rtoffset); + splan->scan.plan.qual = + fix_scan_list(glob, splan->scan.plan.qual, rtoffset); + } + break; + case T_WorkTableScan: + { + WorkTableScan *splan = (WorkTableScan *) plan; + splan->scan.scanrelid += rtoffset; + splan->scan.plan.targetlist = + fix_scan_list(glob, splan->scan.plan.targetlist, rtoffset); + splan->scan.plan.qual = + fix_scan_list(glob, splan->scan.plan.qual, rtoffset); + } + break; case T_NestLoop: case T_MergeJoin: case T_HashJoin: *************** *** 434,439 **** --- 457,467 ---- } } break; + case T_RecursiveUnion: + /* This doesn't evaluate targetlist or check quals either */ + set_dummy_tlist_references(plan, rtoffset); + Assert(plan->qual == NIL); + break; case T_BitmapAnd: { BitmapAnd *splan = (BitmapAnd *) plan; *** src/backend/optimizer/plan/subselect.c.orig Thu Aug 28 19:09:46 2008 --- src/backend/optimizer/plan/subselect.c Thu Oct 2 17:44:57 2008 *************** *** 213,218 **** --- 213,232 ---- } /* + * Assign a (nonnegative) PARAM_EXEC ID for a recursive query's worktable. + */ + int + SS_assign_worktable_param(PlannerInfo *root) + { + Param *param; + + /* We generate a Param of datatype INTERNAL */ + param = generate_new_param(root, INTERNALOID, -1); + /* ... but the caller only cares about its ID */ + return param->paramid; + } + + /* * Get the datatype of the first column of the plan's output. * * This is stored for ARRAY_SUBLINK and for exprType(), which doesn't have any *************** *** 308,315 **** * Generate the plan for the subquery. */ plan = subquery_planner(root->glob, subquery, ! root->query_level + 1, ! tuple_fraction, &subroot); /* And convert to SubPlan or InitPlan format. */ --- 322,329 ---- * Generate the plan for the subquery. */ plan = subquery_planner(root->glob, subquery, ! root, ! false, tuple_fraction, &subroot); /* And convert to SubPlan or InitPlan format. */ *************** *** 342,349 **** { /* Generate the plan for the ANY subquery; we'll need all rows */ plan = subquery_planner(root->glob, subquery, ! root->query_level + 1, ! 0.0, &subroot); /* Now we can check if it'll fit in work_mem */ --- 356,363 ---- { /* Generate the plan for the ANY subquery; we'll need all rows */ plan = subquery_planner(root->glob, subquery, ! root, ! false, 0.0, &subroot); /* Now we can check if it'll fit in work_mem */ *************** *** 549,554 **** --- 563,570 ---- { case T_Material: case T_FunctionScan: + case T_CteScan: + case T_WorkTableScan: case T_Sort: use_material = false; break; *************** *** 798,803 **** --- 814,939 ---- return true; } + + /* + * SS_process_ctes: process a query's WITH list + * + * We plan each interesting WITH item and convert it to an initplan. + * A side effect is to fill in root->cte_plan_ids with a list that + * parallels root->parse->cteList and provides the subplan ID for + * each CTE's initplan. + */ + void + SS_process_ctes(PlannerInfo *root) + { + ListCell *lc; + + Assert(root->cte_plan_ids == NIL); + + foreach(lc, root->parse->cteList) + { + CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc); + Query *subquery; + Plan *plan; + PlannerInfo *subroot; + SubPlan *splan; + Bitmapset *tmpset; + int paramid; + Param *prm; + + /* + * Ignore CTEs that are not actually referenced anywhere. + */ + if (cte->cterefcount == 0) + { + /* Make a dummy entry in cte_plan_ids */ + root->cte_plan_ids = lappend_int(root->cte_plan_ids, -1); + continue; + } + + /* + * Copy the source Query node. Probably not necessary, but let's + * keep this similar to make_subplan. + */ + subquery = (Query *) copyObject(cte->ctequery); + + /* + * Generate the plan for the CTE query. Always plan for full + * retrieval --- we don't have enough info to predict otherwise. + */ + plan = subquery_planner(root->glob, subquery, + root, + cte->cterecursive, 0.0, + &subroot); + + /* + * Make a SubPlan node for it. This is just enough unlike + * build_subplan that we can't share code. + * + * We arbitrarily use EXPR_SUBLINK for the sublink type. It doesn't + * seem worth adding an entry to enum SubLinkType, since that would + * clutter a lot of places that are unconcerned with CTEs. + * Note plan_id isn't set till further down, likewise the cost fields. + */ + splan = makeNode(SubPlan); + splan->subLinkType = EXPR_SUBLINK; + splan->testexpr = NULL; + splan->paramIds = NIL; + splan->firstColType = get_first_col_type(plan); + splan->useHashTable = false; + splan->unknownEqFalse = false; + splan->setParam = NIL; + splan->parParam = NIL; + splan->args = NIL; + + /* + * Make parParam and args lists of param IDs and expressions that + * current query level will pass to this child plan. Even though + * this is an initplan, there could be side-references to earlier + * initplan's outputs, specifically their CTE output parameters. + */ + tmpset = bms_copy(plan->extParam); + while ((paramid = bms_first_member(tmpset)) >= 0) + { + PlannerParamItem *pitem = list_nth(root->glob->paramlist, paramid); + + if (pitem->abslevel == root->query_level) + { + prm = (Param *) pitem->item; + if (!IsA(prm, Param) || + prm->paramtype != INTERNALOID) + elog(ERROR, "bogus local parameter passed to WITH query"); + + splan->parParam = lappend_int(splan->parParam, paramid); + splan->args = lappend(splan->args, copyObject(prm)); + } + } + bms_free(tmpset); + + /* + * Assign a param to represent the query output. We only really + * care about reserving a parameter ID number. + */ + prm = generate_new_param(root, INTERNALOID, -1); + splan->setParam = list_make1_int(prm->paramid); + + /* + * Add the subplan and its rtable to the global lists. + */ + root->glob->subplans = lappend(root->glob->subplans, plan); + root->glob->subrtables = lappend(root->glob->subrtables, + subroot->parse->rtable); + splan->plan_id = list_length(root->glob->subplans); + + root->init_plans = lappend(root->init_plans, splan); + + root->cte_plan_ids = lappend_int(root->cte_plan_ids, splan->plan_id); + + /* Lastly, fill in the cost estimates for use later */ + cost_subplan(root, splan, plan); + } + } + /* * convert_ANY_sublink_to_join: can we convert an ANY SubLink to a join? * *************** *** 1589,1594 **** --- 1725,1733 ---- paramid++; } + /* Also include the recursion working table, if any */ + if (root->wt_param_id >= 0) + valid_params = bms_add_member(valid_params, root->wt_param_id); /* * Now recurse through plan tree. *************** *** 1719,1724 **** --- 1858,1875 ---- &context); break; + case T_CteScan: + context.paramids = + bms_add_member(context.paramids, + ((CteScan *) plan)->cteParam); + break; + + case T_WorkTableScan: + context.paramids = + bms_add_member(context.paramids, + ((WorkTableScan *) plan)->wtParam); + break; + case T_Append: { ListCell *l; *************** *** 1790,1795 **** --- 1941,1947 ---- &context); break; + case T_RecursiveUnion: case T_Hash: case T_Agg: case T_SeqScan: *************** *** 1816,1821 **** --- 1968,1982 ---- plan->righttree, valid_params)); + /* + * RecursiveUnion *generates* its worktable param, so don't bubble that up + */ + if (IsA(plan, RecursiveUnion)) + { + context.paramids = bms_del_member(context.paramids, + ((RecursiveUnion *) plan)->wtParam); + } + /* Now we have all the paramids */ if (!bms_is_subset(context.paramids, valid_params)) *** src/backend/optimizer/prep/prepjointree.c.orig Mon Aug 25 18:42:33 2008 --- src/backend/optimizer/prep/prepjointree.c Thu Oct 2 14:47:22 2008 *************** *** 567,576 **** --- 567,584 ---- subroot->parse = subquery; subroot->glob = root->glob; subroot->query_level = root->query_level; + subroot->parent_root = root->parent_root; subroot->planner_cxt = CurrentMemoryContext; subroot->init_plans = NIL; + subroot->cte_plan_ids = NIL; subroot->eq_classes = NIL; subroot->append_rel_list = NIL; + subroot->hasRecursion = false; + subroot->wt_param_id = -1; + subroot->non_recursive_plan = NULL; + + /* No CTEs to worry about */ + Assert(subquery->cteList == NIL); /* * Pull up any SubLinks within the subquery's quals, so that we don't *************** *** 916,923 **** return false; /* ! * Can't pull up a subquery involving grouping, aggregation, sorting, or ! * limiting. */ if (subquery->hasAggs || subquery->groupClause || --- 924,931 ---- return false; /* ! * Can't pull up a subquery involving grouping, aggregation, sorting, ! * limiting, or WITH. (XXX WITH could possibly be allowed later) */ if (subquery->hasAggs || subquery->groupClause || *************** *** 925,931 **** subquery->sortClause || subquery->distinctClause || subquery->limitOffset || ! subquery->limitCount) return false; /* --- 933,940 ---- subquery->sortClause || subquery->distinctClause || subquery->limitOffset || ! subquery->limitCount || ! subquery->cteList) return false; /* *************** *** 985,995 **** return false; Assert(IsA(topop, SetOperationStmt)); ! /* Can't handle ORDER BY, LIMIT/OFFSET, or locking */ if (subquery->sortClause || subquery->limitOffset || subquery->limitCount || ! subquery->rowMarks) return false; /* Recursively check the tree of set operations */ --- 994,1005 ---- return false; Assert(IsA(topop, SetOperationStmt)); ! /* Can't handle ORDER BY, LIMIT/OFFSET, locking, or WITH */ if (subquery->sortClause || subquery->limitOffset || subquery->limitCount || ! subquery->rowMarks || ! subquery->cteList) return false; /* Recursively check the tree of set operations */ *** src/backend/optimizer/prep/prepunion.c.orig Thu Aug 28 19:09:46 2008 --- src/backend/optimizer/prep/prepunion.c Thu Oct 2 16:15:29 2008 *************** *** 56,61 **** --- 56,65 ---- List *colTypes, bool junkOK, int flag, List *refnames_tlist, List **sortClauses, double *pNumGroups); + static Plan *generate_recursion_plan(SetOperationStmt *setOp, + PlannerInfo *root, double tuple_fraction, + List *refnames_tlist, + List **sortClauses); static Plan *generate_union_plan(SetOperationStmt *op, PlannerInfo *root, double tuple_fraction, List *refnames_tlist, *************** *** 148,153 **** --- 152,165 ---- Assert(leftmostQuery != NULL); /* + * If the topmost node is a recursive union, it needs special processing. + */ + if (root->hasRecursion) + return generate_recursion_plan(topop, root, tuple_fraction, + leftmostQuery->targetList, + sortClauses); + + /* * Recurse on setOperations tree to generate plans for set ops. The final * output plan should have just the column types shown as the output from * the top-level node, plus possibly resjunk working columns (we can rely *************** *** 200,207 **** * Generate plan for primitive subquery */ subplan = subquery_planner(root->glob, subquery, ! root->query_level + 1, ! tuple_fraction, &subroot); /* --- 212,219 ---- * Generate plan for primitive subquery */ subplan = subquery_planner(root->glob, subquery, ! root, ! false, tuple_fraction, &subroot); /* *************** *** 294,299 **** --- 306,363 ---- } /* + * Generate plan for a recursive UNION node + */ + static Plan * + generate_recursion_plan(SetOperationStmt *setOp, PlannerInfo *root, + double tuple_fraction, + List *refnames_tlist, + List **sortClauses) + { + Plan *plan; + Plan *lplan; + Plan *rplan; + List *tlist; + + /* Parser should have rejected other cases */ + if (setOp->op != SETOP_UNION || !setOp->all) + elog(ERROR, "only UNION ALL queries can be recursive"); + /* Worktable ID should be assigned */ + Assert(root->wt_param_id >= 0); + + /* + * Unlike a regular UNION node, process the left and right inputs + * separately without any intention of combining them into one Append. + */ + lplan = recurse_set_operations(setOp->larg, root, tuple_fraction, + setOp->colTypes, false, -1, + refnames_tlist, sortClauses, NULL); + /* The right plan will want to look at the left one ... */ + root->non_recursive_plan = lplan; + rplan = recurse_set_operations(setOp->rarg, root, tuple_fraction, + setOp->colTypes, false, -1, + refnames_tlist, sortClauses, NULL); + root->non_recursive_plan = NULL; + + /* + * Generate tlist for RecursiveUnion plan node --- same as in Append cases + */ + tlist = generate_append_tlist(setOp->colTypes, false, + list_make2(lplan, rplan), + refnames_tlist); + + /* + * And make the plan node. + */ + plan = (Plan *) make_recursive_union(tlist, lplan, rplan, + root->wt_param_id); + + *sortClauses = NIL; /* result of UNION ALL is always unsorted */ + + return plan; + } + + /* * Generate plan for a UNION or UNION ALL node */ static Plan * *************** *** 1346,1352 **** newnode = query_tree_mutator((Query *) node, adjust_appendrel_attrs_mutator, (void *) appinfo, ! QTW_IGNORE_RT_SUBQUERIES); if (newnode->resultRelation == appinfo->parent_relid) { newnode->resultRelation = appinfo->child_relid; --- 1410,1416 ---- newnode = query_tree_mutator((Query *) node, adjust_appendrel_attrs_mutator, (void *) appinfo, ! QTW_IGNORE_RC_SUBQUERIES); if (newnode->resultRelation == appinfo->parent_relid) { newnode->resultRelation = appinfo->child_relid; *** src/backend/optimizer/util/clauses.c.orig Tue Sep 9 14:58:08 2008 --- src/backend/optimizer/util/clauses.c Mon Sep 22 14:07:15 2008 *************** *** 3361,3366 **** --- 3361,3367 ---- querytree->intoClause || querytree->hasAggs || querytree->hasSubLinks || + querytree->cteList || querytree->rtable || querytree->jointree->fromlist || querytree->jointree->quals || *** src/backend/optimizer/util/pathnode.c.orig Fri Sep 5 17:07:29 2008 --- src/backend/optimizer/util/pathnode.c Fri Oct 3 13:58:08 2008 *************** *** 1220,1225 **** --- 1220,1264 ---- } /* + * create_ctescan_path + * Creates a path corresponding to a scan of a non-self-reference CTE, + * returning the pathnode. + */ + Path * + create_ctescan_path(PlannerInfo *root, RelOptInfo *rel) + { + Path *pathnode = makeNode(Path); + + pathnode->pathtype = T_CteScan; + pathnode->parent = rel; + pathnode->pathkeys = NIL; /* XXX for now, result is always unordered */ + + cost_ctescan(pathnode, root, rel); + + return pathnode; + } + + /* + * create_worktablescan_path + * Creates a path corresponding to a scan of a self-reference CTE, + * returning the pathnode. + */ + Path * + create_worktablescan_path(PlannerInfo *root, RelOptInfo *rel) + { + Path *pathnode = makeNode(Path); + + pathnode->pathtype = T_WorkTableScan; + pathnode->parent = rel; + pathnode->pathkeys = NIL; /* result is always unordered */ + + /* Cost is the same as for a regular CTE scan */ + cost_ctescan(pathnode, root, rel); + + return pathnode; + } + + /* * create_nestloop_path * Creates a pathnode corresponding to a nestloop join between two * relations. *** src/backend/optimizer/util/plancat.c.orig Mon Sep 1 16:42:44 2008 --- src/backend/optimizer/util/plancat.c Fri Oct 3 15:03:49 2008 *************** *** 657,664 **** * dropped cols. * * We also support building a "physical" tlist for subqueries, functions, ! * and values lists, since the same optimization can occur in SubqueryScan, ! * FunctionScan, and ValuesScan nodes. */ List * build_physical_tlist(PlannerInfo *root, RelOptInfo *rel) --- 657,664 ---- * dropped cols. * * We also support building a "physical" tlist for subqueries, functions, ! * values lists, and CTEs, since the same optimization can occur in ! * SubqueryScan, FunctionScan, ValuesScan, CteScan, and WorkTableScan nodes. */ List * build_physical_tlist(PlannerInfo *root, RelOptInfo *rel) *************** *** 733,738 **** --- 733,741 ---- break; case RTE_FUNCTION: + case RTE_VALUES: + case RTE_CTE: + /* Not all of these can have dropped cols, but share code anyway */ expandRTE(rte, varno, 0, -1, true /* include dropped */ , NULL, &colvars); foreach(l, colvars) *************** *** 757,777 **** } break; - case RTE_VALUES: - expandRTE(rte, varno, 0, -1, false /* dropped not applicable */ , - NULL, &colvars); - foreach(l, colvars) - { - var = (Var *) lfirst(l); - - tlist = lappend(tlist, - makeTargetEntry((Expr *) var, - var->varattno, - NULL, - false)); - } - break; - default: /* caller error */ elog(ERROR, "unsupported RTE kind %d in build_physical_tlist", --- 760,765 ---- *** src/backend/optimizer/util/relnode.c.orig Thu Aug 14 14:47:59 2008 --- src/backend/optimizer/util/relnode.c Mon Sep 22 14:07:16 2008 *************** *** 101,106 **** --- 101,107 ---- case RTE_SUBQUERY: case RTE_FUNCTION: case RTE_VALUES: + case RTE_CTE: /* * Subquery, function, or values list --- set up attr range and *** src/backend/parser/Makefile.orig Fri Aug 29 09:02:32 2008 --- src/backend/parser/Makefile Mon Sep 22 11:16:32 2008 *************** *** 12,18 **** override CPPFLAGS := -I$(srcdir) $(CPPFLAGS) ! OBJS= analyze.o gram.o keywords.o parser.o parse_agg.o parse_clause.o \ parse_expr.o parse_func.o parse_node.o parse_oper.o parse_relation.o \ parse_type.o parse_coerce.o parse_target.o parse_utilcmd.o scansup.o --- 12,18 ---- override CPPFLAGS := -I$(srcdir) $(CPPFLAGS) ! OBJS= analyze.o gram.o keywords.o parser.o parse_agg.o parse_cte.o parse_clause.o \ parse_expr.o parse_func.o parse_node.o parse_oper.o parse_relation.o \ parse_type.o parse_coerce.o parse_target.o parse_utilcmd.o scansup.o *** src/backend/parser/analyze.c.orig Mon Sep 1 16:42:44 2008 --- src/backend/parser/analyze.c Tue Sep 30 11:52:46 2008 *************** *** 32,37 **** --- 32,38 ---- #include "parser/parse_agg.h" #include "parser/parse_clause.h" #include "parser/parse_coerce.h" + #include "parser/parse_cte.h" #include "parser/parse_oper.h" #include "parser/parse_relation.h" #include "parser/parse_target.h" *************** *** 309,314 **** --- 310,317 ---- pstate->p_relnamespace = NIL; sub_varnamespace = pstate->p_varnamespace; pstate->p_varnamespace = NIL; + /* There can't be any outer WITH to worry about */ + Assert(pstate->p_ctenamespace == NIL); } else { *************** *** 447,452 **** --- 450,462 ---- List *exprsLists = NIL; int sublist_length = -1; + /* process the WITH clause */ + if (selectStmt->withClause) + { + qry->hasRecursive = selectStmt->withClause->recursive; + qry->cteList = transformWithClause(pstate, selectStmt->withClause); + } + foreach(lc, selectStmt->valuesLists) { List *sublist = (List *) lfirst(lc); *************** *** 540,545 **** --- 550,562 ---- Assert(list_length(valuesLists) == 1); + /* process the WITH clause */ + if (selectStmt->withClause) + { + qry->hasRecursive = selectStmt->withClause->recursive; + qry->cteList = transformWithClause(pstate, selectStmt->withClause); + } + /* Do basic expression transformation (same as a ROW() expr) */ exprList = transformExpressionList(pstate, (List *) linitial(valuesLists)); *************** *** 694,699 **** --- 711,723 ---- /* make FOR UPDATE/FOR SHARE info available to addRangeTableEntry */ pstate->p_locking_clause = stmt->lockingClause; + /* process the WITH clause */ + if (stmt->withClause) + { + qry->hasRecursive = stmt->withClause->recursive; + qry->cteList = transformWithClause(pstate, stmt->withClause); + } + /* process the FROM clause */ transformFromClause(pstate, stmt->fromClause); *************** *** 814,819 **** --- 838,850 ---- Assert(stmt->havingClause == NULL); Assert(stmt->op == SETOP_NONE); + /* process the WITH clause */ + if (stmt->withClause) + { + qry->hasRecursive = stmt->withClause->recursive; + qry->cteList = transformWithClause(pstate, stmt->withClause); + } + /* * For each row of VALUES, transform the raw expressions and gather type * information. This is also a handy place to reject DEFAULT nodes, which *************** *** 1059,1064 **** --- 1090,1102 ---- (errcode(ERRCODE_FEATURE_NOT_SUPPORTED), errmsg("SELECT FOR UPDATE/SHARE is not allowed with UNION/INTERSECT/EXCEPT"))); + /* process the WITH clause */ + if (stmt->withClause) + { + qry->hasRecursive = stmt->withClause->recursive; + qry->cteList = transformWithClause(pstate, stmt->withClause); + } + /* * Recursively transform the components of the tree. */ *************** *** 1101,1121 **** TargetEntry *lefttle = (TargetEntry *) lfirst(left_tlist); char *colName; TargetEntry *tle; ! Expr *expr; Assert(!lefttle->resjunk); colName = pstrdup(lefttle->resname); ! expr = (Expr *) makeVar(leftmostRTI, ! lefttle->resno, ! colType, ! colTypmod, ! 0); ! tle = makeTargetEntry(expr, (AttrNumber) pstate->p_next_resno++, colName, false); qry->targetList = lappend(qry->targetList, tle); ! targetvars = lappend(targetvars, expr); targetnames = lappend(targetnames, makeString(colName)); left_tlist = lnext(left_tlist); } --- 1139,1160 ---- TargetEntry *lefttle = (TargetEntry *) lfirst(left_tlist); char *colName; TargetEntry *tle; ! Var *var; Assert(!lefttle->resjunk); colName = pstrdup(lefttle->resname); ! var = makeVar(leftmostRTI, ! lefttle->resno, ! colType, ! colTypmod, ! 0); ! var->location = exprLocation((Node *) lefttle->expr); ! tle = makeTargetEntry((Expr *) var, (AttrNumber) pstate->p_next_resno++, colName, false); qry->targetList = lappend(qry->targetList, tle); ! targetvars = lappend(targetvars, var); targetnames = lappend(targetnames, makeString(colName)); left_tlist = lnext(left_tlist); } *************** *** 1841,1846 **** --- 1880,1889 ---- */ transformLockingClause(pstate, rte->subquery, allrels); break; + case RTE_CTE: + /* XXX fixme */ + elog(ERROR, "FOR UPDATE of CTE not supported"); + break; default: /* ignore JOIN, SPECIAL, FUNCTION RTEs */ break; *************** *** 1908,1913 **** --- 1951,1958 ---- errmsg("SELECT FOR UPDATE/SHARE cannot be applied to VALUES"), parser_errposition(pstate, thisrel->location))); break; + case RTE_CTE: + /* XXX fixme */ default: elog(ERROR, "unrecognized RTE type: %d", (int) rte->rtekind); *** src/backend/parser/gram.y.orig Thu Sep 25 14:54:09 2008 --- src/backend/parser/gram.y Thu Sep 25 14:55:51 2008 *************** *** 119,125 **** static SelectStmt *findLeftmostSelect(SelectStmt *node); static void insertSelectOptions(SelectStmt *stmt, List *sortClause, List *lockingClause, ! Node *limitOffset, Node *limitCount); static Node *makeSetOp(SetOperation op, bool all, Node *larg, Node *rarg); static Node *doNegate(Node *n, int location); static void doNegateFloat(Value *v); --- 119,126 ---- static SelectStmt *findLeftmostSelect(SelectStmt *node); static void insertSelectOptions(SelectStmt *stmt, List *sortClause, List *lockingClause, ! Node *limitOffset, Node *limitCount, ! WithClause *withClause); static Node *makeSetOp(SetOperation op, bool all, Node *larg, Node *rarg); static Node *doNegate(Node *n, int location); static void doNegateFloat(Value *v); *************** *** 160,165 **** --- 161,167 ---- Alias *alias; RangeVar *range; IntoClause *into; + WithClause *with; A_Indices *aind; ResTarget *target; PrivTarget *privtarget; *************** *** 377,382 **** --- 379,388 ---- %type document_or_content %type xml_whitespace_option + %type common_table_expr + %type with_clause + %type cte_list + /* * If you make any token changes, update the keyword table in *************** *** 443,451 **** QUOTE ! READ REAL REASSIGN RECHECK REFERENCES REINDEX RELATIVE_P RELEASE RENAME ! REPEATABLE REPLACE REPLICA RESET RESTART RESTRICT RETURNING RETURNS REVOKE ! RIGHT ROLE ROLLBACK ROW ROWS RULE SAVEPOINT SCHEMA SCROLL SEARCH SECOND_P SECURITY SELECT SEQUENCE SERIALIZABLE SESSION SESSION_USER SET SETOF SHARE --- 449,457 ---- QUOTE ! READ REAL REASSIGN RECHECK RECURSIVE REFERENCES REINDEX RELATIVE_P RELEASE ! RENAME REPEATABLE REPLACE REPLICA RESET RESTART RESTRICT RETURNING RETURNS ! REVOKE RIGHT ROLE ROLLBACK ROW ROWS RULE SAVEPOINT SCHEMA SCROLL SEARCH SECOND_P SECURITY SELECT SEQUENCE SERIALIZABLE SESSION SESSION_USER SET SETOF SHARE *************** *** 6276,6281 **** --- 6282,6291 ---- ; /* + * This rule parses the equivalent of the standard's . + * The duplicative productions are annoying, but hard to get rid of without + * creating shift/reduce conflicts. + * * FOR UPDATE/SHARE may be before or after LIMIT/OFFSET. * In <=7.2.X, LIMIT/OFFSET had to be after FOR UPDATE * We now support both orderings, but prefer LIMIT/OFFSET before FOR UPDATE/SHARE *************** *** 6286,6306 **** | select_clause sort_clause { insertSelectOptions((SelectStmt *) $1, $2, NIL, ! NULL, NULL); $$ = $1; } | select_clause opt_sort_clause for_locking_clause opt_select_limit { insertSelectOptions((SelectStmt *) $1, $2, $3, ! list_nth($4, 0), list_nth($4, 1)); $$ = $1; } | select_clause opt_sort_clause select_limit opt_for_locking_clause { insertSelectOptions((SelectStmt *) $1, $2, $4, ! list_nth($3, 0), list_nth($3, 1)); $$ = $1; } ; select_clause: --- 6296,6346 ---- | select_clause sort_clause { insertSelectOptions((SelectStmt *) $1, $2, NIL, ! NULL, NULL, NULL); $$ = $1; } | select_clause opt_sort_clause for_locking_clause opt_select_limit { insertSelectOptions((SelectStmt *) $1, $2, $3, ! list_nth($4, 0), list_nth($4, 1), ! NULL); $$ = $1; } | select_clause opt_sort_clause select_limit opt_for_locking_clause { insertSelectOptions((SelectStmt *) $1, $2, $4, ! list_nth($3, 0), list_nth($3, 1), ! NULL); $$ = $1; } + | with_clause simple_select + { + insertSelectOptions((SelectStmt *) $2, NULL, NIL, + NULL, NULL, + $1); + $$ = $2; + } + | with_clause select_clause sort_clause + { + insertSelectOptions((SelectStmt *) $2, $3, NIL, + NULL, NULL, + $1); + $$ = $2; + } + | with_clause select_clause opt_sort_clause for_locking_clause opt_select_limit + { + insertSelectOptions((SelectStmt *) $2, $3, $4, + list_nth($5, 0), list_nth($5, 1), + $1); + $$ = $2; + } + | with_clause select_clause opt_sort_clause select_limit opt_for_locking_clause + { + insertSelectOptions((SelectStmt *) $2, $3, $5, + list_nth($4, 0), list_nth($4, 1), + $1); + $$ = $2; + } ; select_clause: *************** *** 6361,6366 **** --- 6401,6447 ---- } ; + /* + * SQL standard WITH clause looks like: + * + * WITH [ RECURSIVE ] [ (,...) ] + * AS (query) [ SEARCH or CYCLE clause ] + * + * We don't currently support the SEARCH or CYCLE clause. + */ + with_clause: + WITH cte_list + { + $$ = makeNode(WithClause); + $$->ctes = $2; + $$->recursive = false; + $$->location = @1; + } + | WITH RECURSIVE cte_list + { + $$ = makeNode(WithClause); + $$->ctes = $3; + $$->recursive = true; + $$->location = @1; + } + ; + + cte_list: + common_table_expr { $$ = list_make1($1); } + | cte_list ',' common_table_expr { $$ = lappend($1, $3); } + ; + + common_table_expr: name opt_name_list AS select_with_parens + { + CommonTableExpr *n = makeNode(CommonTableExpr); + n->ctename = $1; + n->aliascolnames = $2; + n->ctequery = $4; + n->location = @1; + $$ = (Node *) n; + } + ; + into_clause: INTO OptTempTableName { *************** *** 9349,9354 **** --- 9430,9436 ---- | READ | REASSIGN | RECHECK + | RECURSIVE | REINDEX | RELATIVE_P | RELEASE *************** *** 9416,9422 **** | VIEW | VOLATILE | WHITESPACE_P - | WITH | WITHOUT | WORK | WRITE --- 9498,9503 ---- *************** *** 9599,9604 **** --- 9680,9686 ---- | VARIADIC | WHEN | WHERE + | WITH ; *************** *** 9922,9929 **** static void insertSelectOptions(SelectStmt *stmt, List *sortClause, List *lockingClause, ! Node *limitOffset, Node *limitCount) { /* * Tests here are to reject constructs like * (SELECT foo ORDER BY bar) ORDER BY baz --- 10004,10014 ---- static void insertSelectOptions(SelectStmt *stmt, List *sortClause, List *lockingClause, ! Node *limitOffset, Node *limitCount, ! WithClause *withClause) { + Assert(IsA(stmt, SelectStmt)); + /* * Tests here are to reject constructs like * (SELECT foo ORDER BY bar) ORDER BY baz *************** *** 9957,9962 **** --- 10042,10056 ---- scanner_errposition(exprLocation(limitCount)))); stmt->limitCount = limitCount; } + if (withClause) + { + if (stmt->withClause) + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + errmsg("multiple WITH clauses not allowed"), + scanner_errposition(exprLocation((Node *) withClause)))); + stmt->withClause = withClause; + } } static Node * *** src/backend/parser/keywords.c.orig Thu Sep 25 14:54:09 2008 --- src/backend/parser/keywords.c Thu Sep 25 14:55:51 2008 *************** *** 305,310 **** --- 305,311 ---- {"real", REAL, COL_NAME_KEYWORD}, {"reassign", REASSIGN, UNRESERVED_KEYWORD}, {"recheck", RECHECK, UNRESERVED_KEYWORD}, + {"recursive", RECURSIVE, UNRESERVED_KEYWORD}, {"references", REFERENCES, RESERVED_KEYWORD}, {"reindex", REINDEX, UNRESERVED_KEYWORD}, {"relative", RELATIVE_P, UNRESERVED_KEYWORD}, *************** *** 403,417 **** {"when", WHEN, RESERVED_KEYWORD}, {"where", WHERE, RESERVED_KEYWORD}, {"whitespace", WHITESPACE_P, UNRESERVED_KEYWORD}, - - /* - * XXX we mark WITH as reserved to force it to be quoted in dumps, even - * though it is currently unreserved according to gram.y. This is because - * we expect we'll have to make it reserved to implement SQL WITH clauses. - * If that patch manages to do without reserving WITH, adjust this entry - * at that time; in any case this should be back in sync with gram.y after - * WITH clauses are implemented. - */ {"with", WITH, RESERVED_KEYWORD}, {"without", WITHOUT, UNRESERVED_KEYWORD}, {"work", WORK, UNRESERVED_KEYWORD}, --- 404,409 ---- *** src/backend/parser/parse_agg.c.orig Mon Sep 1 16:42:44 2008 --- src/backend/parser/parse_agg.c Tue Sep 30 12:51:55 2008 *************** *** 102,107 **** --- 102,108 ---- bool have_non_var_grouping; ListCell *l; bool hasJoinRTEs; + bool hasSelfRefRTEs; PlannerInfo *root; Node *clause; *************** *** 109,114 **** --- 110,130 ---- Assert(pstate->p_hasAggs || qry->groupClause || qry->havingQual); /* + * Scan the range table to see if there are JOIN or self-reference CTE + * entries. We'll need this info below. + */ + hasJoinRTEs = hasSelfRefRTEs = false; + foreach(l, pstate->p_rtable) + { + RangeTblEntry *rte = (RangeTblEntry *) lfirst(l); + + if (rte->rtekind == RTE_JOIN) + hasJoinRTEs = true; + else if (rte->rtekind == RTE_CTE && rte->self_reference) + hasSelfRefRTEs = true; + } + + /* * Aggregates must never appear in WHERE or JOIN/ON clauses. * * (Note this check should appear first to deliver an appropriate error *************** *** 157,176 **** * underlying vars, so that aliased and unaliased vars will be correctly * taken as equal. We can skip the expense of doing this if no rangetable * entries are RTE_JOIN kind. - */ - hasJoinRTEs = false; - foreach(l, pstate->p_rtable) - { - RangeTblEntry *rte = (RangeTblEntry *) lfirst(l); - - if (rte->rtekind == RTE_JOIN) - { - hasJoinRTEs = true; - break; - } - } - - /* * We use the planner's flatten_join_alias_vars routine to do the * flattening; it wants a PlannerInfo root node, which fortunately can be * mostly dummy. --- 173,178 ---- *************** *** 217,222 **** --- 219,234 ---- clause = flatten_join_alias_vars(root, clause); check_ungrouped_columns(clause, pstate, groupClauses, have_non_var_grouping); + + /* + * Per spec, aggregates can't appear in a recursive term. + */ + if (pstate->p_hasAggs && hasSelfRefRTEs) + ereport(ERROR, + (errcode(ERRCODE_INVALID_RECURSION), + errmsg("aggregates not allowed in a recursive query's recursive term"), + parser_errposition(pstate, + locate_agg_of_level((Node *) qry, 0)))); } *** src/backend/parser/parse_clause.c.orig Mon Sep 1 16:42:44 2008 --- src/backend/parser/parse_clause.c Thu Oct 2 15:14:52 2008 *************** *** 54,59 **** --- 54,61 ---- List *relnamespace, Relids containedRels); static RangeTblEntry *transformTableEntry(ParseState *pstate, RangeVar *r); + static RangeTblEntry *transformCTEReference(ParseState *pstate, RangeVar *r, + CommonTableExpr *cte, Index levelsup); static RangeTblEntry *transformRangeSubselect(ParseState *pstate, RangeSubselect *r); static RangeTblEntry *transformRangeFunction(ParseState *pstate, *************** *** 422,427 **** --- 424,443 ---- return rte; } + /* + * transformCTEReference --- transform a RangeVar that references a common + * table expression (ie, a sub-SELECT defined in a WITH clause) + */ + static RangeTblEntry * + transformCTEReference(ParseState *pstate, RangeVar *r, + CommonTableExpr *cte, Index levelsup) + { + RangeTblEntry *rte; + + rte = addRangeTableEntryForCTE(pstate, cte, levelsup, r->alias, true); + + return rte; + } /* * transformRangeSubselect --- transform a sub-SELECT appearing in FROM *************** *** 609,620 **** { if (IsA(n, RangeVar)) { ! /* Plain relation reference */ RangeTblRef *rtr; ! RangeTblEntry *rte; int rtindex; ! rte = transformTableEntry(pstate, (RangeVar *) n); /* assume new rte is at end */ rtindex = list_length(pstate->p_rtable); Assert(rte == rt_fetch(rtindex, pstate->p_rtable)); --- 625,670 ---- { if (IsA(n, RangeVar)) { ! /* Plain relation reference, or perhaps a CTE reference */ ! RangeVar *rv = (RangeVar *) n; RangeTblRef *rtr; ! RangeTblEntry *rte = NULL; int rtindex; ! /* ! * If it is an unqualified name, it might be a reference to some ! * CTE visible in this or a parent query. ! */ ! if (!rv->schemaname) ! { ! ParseState *ps; ! Index levelsup; ! ! for (ps = pstate, levelsup = 0; ! ps != NULL; ! ps = ps->parentParseState, levelsup++) ! { ! ListCell *lc; ! ! foreach(lc, ps->p_ctenamespace) ! { ! CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc); ! ! if (strcmp(rv->relname, cte->ctename) == 0) ! { ! rte = transformCTEReference(pstate, rv, cte, levelsup); ! break; ! } ! } ! if (rte) ! break; ! } ! } ! ! /* if not found as a CTE, must be a table reference */ ! if (!rte) ! rte = transformTableEntry(pstate, rv); ! /* assume new rte is at end */ rtindex = list_length(pstate->p_rtable); Assert(rte == rt_fetch(rtindex, pstate->p_rtable)); *** src/backend/parser/parse_cte.c.orig Mon Sep 22 11:16:32 2008 --- src/backend/parser/parse_cte.c Thu Oct 2 17:37:37 2008 *************** *** 0 **** --- 1,899 ---- + /*------------------------------------------------------------------------- + * + * parse_cte.c + * handle CTEs (common table expressions) in parser + * + * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * + * IDENTIFICATION + * $PostgreSQL$ + * + *------------------------------------------------------------------------- + */ + #include "postgres.h" + + #include "nodes/nodeFuncs.h" + #include "parser/analyze.h" + #include "parser/parse_cte.h" + #include "utils/builtins.h" + + + /* Enumeration of contexts in which a self-reference is disallowed */ + typedef enum + { + RECURSION_OK, + RECURSION_NONRECURSIVETERM, /* inside the left-hand term */ + RECURSION_SUBLINK, /* inside a sublink */ + RECURSION_OUTERJOIN, /* inside nullable side of an outer join */ + RECURSION_INTERSECT, /* underneath INTERSECT (ALL) */ + RECURSION_EXCEPT /* underneath EXCEPT (ALL) */ + } RecursionContext; + + /* Associated error messages --- each must have one %s for CTE name */ + static const char * const recursion_errormsgs[] = { + /* RECURSION_OK */ + NULL, + /* RECURSION_NONRECURSIVETERM */ + gettext_noop("recursive reference to query \"%s\" must not appear within its non-recursive term"), + /* RECURSION_SUBLINK */ + gettext_noop("recursive reference to query \"%s\" must not appear within a subquery"), + /* RECURSION_OUTERJOIN */ + gettext_noop("recursive reference to query \"%s\" must not appear within an outer join"), + /* RECURSION_INTERSECT */ + gettext_noop("recursive reference to query \"%s\" must not appear within INTERSECT"), + /* RECURSION_EXCEPT */ + gettext_noop("recursive reference to query \"%s\" must not appear within EXCEPT") + }; + + /* + * For WITH RECURSIVE, we have to find an ordering of the clause members + * with no forward references, and determine which members are recursive + * (i.e., self-referential). It is convenient to do this with an array + * of CteItems instead of a list of CommonTableExprs. + */ + typedef struct CteItem + { + CommonTableExpr *cte; /* One CTE to examine */ + int id; /* Its ID number for dependencies */ + Node *non_recursive_term; /* Its nonrecursive part, if identified */ + Bitmapset *depends_on; /* CTEs depended on (not including self) */ + } CteItem; + + /* CteState is what we need to pass around in the tree walkers */ + typedef struct CteState + { + /* global state: */ + ParseState *pstate; /* global parse state */ + CteItem *items; /* array of CTEs and extra data */ + int numitems; /* number of CTEs */ + /* working state during a tree walk: */ + int curitem; /* index of item currently being examined */ + List *innerwiths; /* list of lists of CommonTableExpr */ + /* working state for checkWellFormedRecursion walk only: */ + int selfrefcount; /* number of self-references detected */ + RecursionContext context; /* context to allow or disallow self-ref */ + } CteState; + + + static void analyzeCTE(ParseState *pstate, CommonTableExpr *cte); + static void analyzeCTETargetList(ParseState *pstate, CommonTableExpr *cte, List *tlist); + + /* Dependency processing functions */ + static void makeDependencyGraph(CteState *cstate); + static bool makeDependencyGraphWalker(Node *node, CteState *cstate); + static void TopologicalSort(ParseState *pstate, CteItem *items, int numitems); + + /* Recursion validity checker functions */ + static void checkWellFormedRecursion(CteState *cstate); + static bool checkWellFormedRecursionWalker(Node *node, CteState *cstate); + static void checkWellFormedSelectStmt(SelectStmt *stmt, CteState *cstate); + + + /* + * transformWithClause - + * Transform the list of WITH clause "common table expressions" into + * Query nodes. + * + * The result is the list of transformed CTEs to be put into the output + * Query. (This is in fact the same as the ending value of p_ctenamespace, + * but it seems cleaner to not expose that in the function's API.) + */ + List * + transformWithClause(ParseState *pstate, WithClause *withClause) + { + ListCell *lc; + + /* Only one WITH clause per query level */ + Assert(pstate->p_ctenamespace == NIL); + + /* + * For either type of WITH, there must not be duplicate CTE names in + * the list. Check this right away so we needn't worry later. + * + * Also, tentatively mark each CTE as non-recursive, and initialize + * its reference count to zero. + */ + foreach(lc, withClause->ctes) + { + CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc); + ListCell *rest; + + for_each_cell(rest, lnext(lc)) + { + CommonTableExpr *cte2 = (CommonTableExpr *) lfirst(rest); + + if (strcmp(cte->ctename, cte2->ctename) == 0) + ereport(ERROR, + (errcode(ERRCODE_DUPLICATE_ALIAS), + errmsg("WITH query name \"%s\" specified more than once", + cte2->ctename), + parser_errposition(pstate, cte2->location))); + } + + cte->cterecursive = false; + cte->cterefcount = 0; + } + + if (withClause->recursive) + { + /* + * For WITH RECURSIVE, we rearrange the list elements if needed + * to eliminate forward references. First, build a work array + * and set up the data structure needed by the tree walkers. + */ + CteState cstate; + int i; + + cstate.pstate = pstate; + cstate.numitems = list_length(withClause->ctes); + cstate.items = (CteItem *) palloc0(cstate.numitems * sizeof(CteItem)); + i = 0; + foreach(lc, withClause->ctes) + { + cstate.items[i].cte = (CommonTableExpr *) lfirst(lc); + cstate.items[i].id = i; + i++; + } + + /* + * Find all the dependencies and sort the CteItems into a safe + * processing order. Also, mark CTEs that contain self-references. + */ + makeDependencyGraph(&cstate); + + /* + * Check that recursive queries are well-formed. + */ + checkWellFormedRecursion(&cstate); + + /* + * Set up the ctenamespace for parse analysis. Per spec, all + * the WITH items are visible to all others, so stuff them all in + * before parse analysis. We build the list in safe processing + * order so that the planner can process the queries in sequence. + */ + for (i = 0; i < cstate.numitems; i++) + { + CommonTableExpr *cte = cstate.items[i].cte; + + pstate->p_ctenamespace = lappend(pstate->p_ctenamespace, cte); + } + + /* + * Do parse analysis in the order determined by the topological sort. + */ + for (i = 0; i < cstate.numitems; i++) + { + CommonTableExpr *cte = cstate.items[i].cte; + + /* + * If it's recursive, we have to do a throwaway parse analysis + * of the non-recursive term in order to determine the set of + * output columns for the recursive CTE. + */ + if (cte->cterecursive) + { + Node *nrt; + Query *nrq; + + if (!cstate.items[i].non_recursive_term) + elog(ERROR, "could not find non-recursive term for %s", + cte->ctename); + /* copy the term to be sure we don't modify original query */ + nrt = copyObject(cstate.items[i].non_recursive_term); + nrq = parse_sub_analyze(nrt, pstate); + analyzeCTETargetList(pstate, cte, nrq->targetList); + } + + analyzeCTE(pstate, cte); + } + } + else + { + /* + * For non-recursive WITH, just analyze each CTE in sequence and then + * add it to the ctenamespace. This corresponds to the spec's + * definition of the scope of each WITH name. + */ + foreach(lc, withClause->ctes) + { + CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc); + + analyzeCTE(pstate, cte); + pstate->p_ctenamespace = lappend(pstate->p_ctenamespace, cte); + } + } + + return pstate->p_ctenamespace; + } + + + /* + * Perform the actual parse analysis transformation of one CTE. All + * CTEs it depends on have already been loaded into pstate->p_ctenamespace, + * and have been marked with the correct output column names/types. + */ + static void + analyzeCTE(ParseState *pstate, CommonTableExpr *cte) + { + Query *query; + + /* Analysis not done already */ + Assert(IsA(cte->ctequery, SelectStmt)); + + query = parse_sub_analyze(cte->ctequery, pstate); + cte->ctequery = (Node *) query; + + /* + * Check that we got something reasonable. Many of these conditions are + * impossible given restrictions of the grammar, but check 'em anyway. + * (These are the same checks as in transformRangeSubselect.) + */ + if (!IsA(query, Query) || + query->commandType != CMD_SELECT || + query->utilityStmt != NULL) + elog(ERROR, "unexpected non-SELECT command in subquery in WITH"); + if (query->intoClause) + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + errmsg("subquery in WITH cannot have SELECT INTO"), + parser_errposition(pstate, + exprLocation((Node *) query->intoClause)))); + + if (!cte->cterecursive) + { + /* Compute the output column names/types if not done yet */ + analyzeCTETargetList(pstate, cte, query->targetList); + } + else + { + /* + * Verify that the previously determined output column types match + * what the query really produced. We have to check this because + * the recursive term could have overridden the non-recursive term, + * and we don't have any easy way to fix that. + */ + ListCell *lctlist, + *lctyp, + *lctypmod; + int varattno; + + lctyp = list_head(cte->ctecoltypes); + lctypmod = list_head(cte->ctecoltypmods); + varattno = 0; + foreach(lctlist, query->targetList) + { + TargetEntry *te = (TargetEntry *) lfirst(lctlist); + Node *texpr; + + if (te->resjunk) + continue; + varattno++; + Assert(varattno == te->resno); + if (lctyp == NULL || lctypmod == NULL) /* shouldn't happen */ + elog(ERROR, "wrong number of output columns in WITH"); + texpr = (Node *) te->expr; + if (exprType(texpr) != lfirst_oid(lctyp) || + exprTypmod(texpr) != lfirst_int(lctypmod)) + ereport(ERROR, + (errcode(ERRCODE_DATATYPE_MISMATCH), + errmsg("recursive query \"%s\" column %d has type %s in non-recursive term but type %s overall", + cte->ctename, varattno, + format_type_with_typemod(lfirst_oid(lctyp), + lfirst_int(lctypmod)), + format_type_with_typemod(exprType(texpr), + exprTypmod(texpr))), + errhint("Cast the output of the non-recursive term to the correct type."), + parser_errposition(pstate, exprLocation(texpr)))); + lctyp = lnext(lctyp); + lctypmod = lnext(lctypmod); + } + if (lctyp != NULL || lctypmod != NULL) /* shouldn't happen */ + elog(ERROR, "wrong number of output columns in WITH"); + } + } + + /* + * Compute derived fields of a CTE, given the transformed output targetlist + */ + static void + analyzeCTETargetList(ParseState *pstate, CommonTableExpr *cte, List *tlist) + { + int numaliases; + int varattno; + ListCell *tlistitem; + + /* + * We need to determine column names and types. The alias column names + * override anything coming from the query itself. (Note: the SQL spec + * says that the alias list must be empty or exactly as long as the + * output column set; but we allow it to be shorter for consistency + * with Alias handling.) + */ + cte->ctecolnames = copyObject(cte->aliascolnames); + cte->ctecoltypes = cte->ctecoltypmods = NIL; + numaliases = list_length(cte->aliascolnames); + varattno = 0; + foreach(tlistitem, tlist) + { + TargetEntry *te = (TargetEntry *) lfirst(tlistitem); + + if (te->resjunk) + continue; + varattno++; + Assert(varattno == te->resno); + if (varattno > numaliases) + { + char *attrname; + + attrname = pstrdup(te->resname); + cte->ctecolnames = lappend(cte->ctecolnames, makeString(attrname)); + } + cte->ctecoltypes = lappend_oid(cte->ctecoltypes, + exprType((Node *) te->expr)); + cte->ctecoltypmods = lappend_int(cte->ctecoltypmods, + exprTypmod((Node *) te->expr)); + } + if (varattno < numaliases) + ereport(ERROR, + (errcode(ERRCODE_INVALID_COLUMN_REFERENCE), + errmsg("WITH query \"%s\" has %d columns available but %d columns specified", + cte->ctename, varattno, numaliases), + parser_errposition(pstate, cte->location))); + } + + + /* + * Identify the cross-references of a list of WITH RECURSIVE items, + * and sort into an order that has no forward references. + */ + static void + makeDependencyGraph(CteState *cstate) + { + int i; + + for (i = 0; i < cstate->numitems; i++) + { + CommonTableExpr *cte = cstate->items[i].cte; + + cstate->curitem = i; + cstate->innerwiths = NIL; + makeDependencyGraphWalker((Node *) cte->ctequery, cstate); + Assert(cstate->innerwiths == NIL); + } + + TopologicalSort(cstate->pstate, cstate->items, cstate->numitems); + } + + /* + * Tree walker function to detect cross-references and self-references of the + * CTEs in a WITH RECURSIVE list. + */ + static bool + makeDependencyGraphWalker(Node *node, CteState *cstate) + { + if (node == NULL) + return false; + if (IsA(node, RangeVar)) + { + RangeVar *rv = (RangeVar *) node; + + /* If unqualified name, might be a CTE reference */ + if (!rv->schemaname) + { + ListCell *lc; + int i; + + /* ... but first see if it's captured by an inner WITH */ + foreach(lc, cstate->innerwiths) + { + List *withlist = (List *) lfirst(lc); + ListCell *lc2; + + foreach(lc2, withlist) + { + CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc2); + + if (strcmp(rv->relname, cte->ctename) == 0) + return false; /* yes, so bail out */ + } + } + + /* No, could be a reference to the query level we are working on */ + for (i = 0; i < cstate->numitems; i++) + { + CommonTableExpr *cte = cstate->items[i].cte; + + if (strcmp(rv->relname, cte->ctename) == 0) + { + int myindex = cstate->curitem; + + if (i != myindex) + { + /* Add cross-item dependency */ + cstate->items[myindex].depends_on = + bms_add_member(cstate->items[myindex].depends_on, + cstate->items[i].id); + } + else + { + /* Found out this one is self-referential */ + cte->cterecursive = true; + } + break; + } + } + } + return false; + } + if (IsA(node, SelectStmt)) + { + SelectStmt *stmt = (SelectStmt *) node; + ListCell *lc; + + if (stmt->withClause) + { + if (stmt->withClause->recursive) + { + /* + * In the RECURSIVE case, all query names of the WITH are + * visible to all WITH items as well as the main query. + * So push them all on, process, pop them all off. + */ + cstate->innerwiths = lcons(stmt->withClause->ctes, + cstate->innerwiths); + foreach(lc, stmt->withClause->ctes) + { + CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc); + + (void) makeDependencyGraphWalker(cte->ctequery, cstate); + } + (void) raw_expression_tree_walker(node, + makeDependencyGraphWalker, + (void *) cstate); + cstate->innerwiths = list_delete_first(cstate->innerwiths); + } + else + { + /* + * In the non-RECURSIVE case, query names are visible to + * the WITH items after them and to the main query. + */ + ListCell *cell1; + + cstate->innerwiths = lcons(NIL, cstate->innerwiths); + cell1 = list_head(cstate->innerwiths); + foreach(lc, stmt->withClause->ctes) + { + CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc); + + (void) makeDependencyGraphWalker(cte->ctequery, cstate); + lfirst(cell1) = lappend((List *) lfirst(cell1), cte); + } + (void) raw_expression_tree_walker(node, + makeDependencyGraphWalker, + (void *) cstate); + cstate->innerwiths = list_delete_first(cstate->innerwiths); + } + /* We're done examining the SelectStmt */ + return false; + } + /* if no WITH clause, just fall through for normal processing */ + } + if (IsA(node, WithClause)) + { + /* + * Prevent raw_expression_tree_walker from recursing directly into + * a WITH clause. We need that to happen only under the control + * of the code above. + */ + return false; + } + return raw_expression_tree_walker(node, + makeDependencyGraphWalker, + (void *) cstate); + } + + /* + * Sort by dependencies, using a standard topological sort operation + */ + static void + TopologicalSort(ParseState *pstate, CteItem *items, int numitems) + { + int i, j; + + /* for each position in sequence ... */ + for (i = 0; i < numitems; i++) + { + /* ... scan the remaining items to find one that has no dependencies */ + for (j = i; j < numitems; j++) + { + if (bms_is_empty(items[j].depends_on)) + break; + } + + /* if we didn't find one, the dependency graph has a cycle */ + if (j >= numitems) + ereport(ERROR, + (errcode(ERRCODE_FEATURE_NOT_SUPPORTED), + errmsg("mutual recursion between WITH items is not supported"), + parser_errposition(pstate, items[i].cte->location))); + + /* + * Found one. Move it to front and remove it from every other + * item's dependencies. + */ + if (i != j) + { + CteItem tmp; + + tmp = items[i]; + items[i] = items[j]; + items[j] = tmp; + } + /* + * Items up through i are known to have no dependencies left, + * so we can skip them in this loop. + */ + for (j = i + 1; j < numitems; j++) + { + items[j].depends_on = bms_del_member(items[j].depends_on, + items[i].id); + } + } + } + + + /* + * Check that recursive queries are well-formed. + */ + static void + checkWellFormedRecursion(CteState *cstate) + { + int i; + + for (i = 0; i < cstate->numitems; i++) + { + CommonTableExpr *cte = cstate->items[i].cte; + SelectStmt *stmt = (SelectStmt *) cte->ctequery; + + Assert(IsA(stmt, SelectStmt)); /* not analyzed yet */ + + /* Ignore items that weren't found to be recursive */ + if (!cte->cterecursive) + continue; + + /* Must have top-level UNION ALL */ + if (stmt->op != SETOP_UNION || !stmt->all) + ereport(ERROR, + (errcode(ERRCODE_INVALID_RECURSION), + errmsg("recursive query \"%s\" does not have the form non-recursive-term UNION ALL recursive-term", + cte->ctename), + parser_errposition(cstate->pstate, cte->location))); + + /* The left-hand operand mustn't contain self-reference at all */ + cstate->curitem = i; + cstate->innerwiths = NIL; + cstate->selfrefcount = 0; + cstate->context = RECURSION_NONRECURSIVETERM; + checkWellFormedRecursionWalker((Node *) stmt->larg, cstate); + Assert(cstate->innerwiths == NIL); + + /* Right-hand operand should contain one reference in a valid place */ + cstate->curitem = i; + cstate->innerwiths = NIL; + cstate->selfrefcount = 0; + cstate->context = RECURSION_OK; + checkWellFormedRecursionWalker((Node *) stmt->rarg, cstate); + Assert(cstate->innerwiths == NIL); + if (cstate->selfrefcount != 1) /* shouldn't happen */ + elog(ERROR, "missing recursive reference"); + + /* + * Disallow ORDER BY and similar decoration atop the UNION ALL. + * These don't make sense because it's impossible to figure out what + * they mean when we have only part of the recursive query's results. + * (If we did allow them, we'd have to check for recursive references + * inside these subtrees.) + */ + if (stmt->sortClause) + ereport(ERROR, + (errcode(ERRCODE_FEATURE_NOT_SUPPORTED), + errmsg("ORDER BY in a recursive query is not implemented"), + parser_errposition(cstate->pstate, + exprLocation((Node *) stmt->sortClause)))); + if (stmt->limitOffset) + ereport(ERROR, + (errcode(ERRCODE_FEATURE_NOT_SUPPORTED), + errmsg("OFFSET in a recursive query is not implemented"), + parser_errposition(cstate->pstate, + exprLocation(stmt->limitOffset)))); + if (stmt->limitCount) + ereport(ERROR, + (errcode(ERRCODE_FEATURE_NOT_SUPPORTED), + errmsg("LIMIT in a recursive query is not implemented"), + parser_errposition(cstate->pstate, + exprLocation(stmt->limitCount)))); + if (stmt->lockingClause) + ereport(ERROR, + (errcode(ERRCODE_FEATURE_NOT_SUPPORTED), + errmsg("FOR UPDATE/SHARE in a recursive query is not implemented"), + parser_errposition(cstate->pstate, + exprLocation((Node *) stmt->lockingClause)))); + + /* + * Save non_recursive_term. + */ + cstate->items[i].non_recursive_term = (Node *) stmt->larg; + } + } + + /* + * Tree walker function to detect invalid self-references in a recursive query. + */ + static bool + checkWellFormedRecursionWalker(Node *node, CteState *cstate) + { + RecursionContext save_context = cstate->context; + + if (node == NULL) + return false; + if (IsA(node, RangeVar)) + { + RangeVar *rv = (RangeVar *) node; + + /* If unqualified name, might be a CTE reference */ + if (!rv->schemaname) + { + ListCell *lc; + CommonTableExpr *mycte; + + /* ... but first see if it's captured by an inner WITH */ + foreach(lc, cstate->innerwiths) + { + List *withlist = (List *) lfirst(lc); + ListCell *lc2; + + foreach(lc2, withlist) + { + CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc2); + + if (strcmp(rv->relname, cte->ctename) == 0) + return false; /* yes, so bail out */ + } + } + + /* No, could be a reference to the query level we are working on */ + mycte = cstate->items[cstate->curitem].cte; + if (strcmp(rv->relname, mycte->ctename) == 0) + { + /* Found a recursive reference to the active query */ + if (cstate->context != RECURSION_OK) + ereport(ERROR, + (errcode(ERRCODE_INVALID_RECURSION), + errmsg(recursion_errormsgs[cstate->context], + mycte->ctename), + parser_errposition(cstate->pstate, + rv->location))); + /* Count references */ + if (++(cstate->selfrefcount) > 1) + ereport(ERROR, + (errcode(ERRCODE_INVALID_RECURSION), + errmsg("recursive reference to query \"%s\" must not appear more than once", + mycte->ctename), + parser_errposition(cstate->pstate, + rv->location))); + } + } + return false; + } + if (IsA(node, SelectStmt)) + { + SelectStmt *stmt = (SelectStmt *) node; + ListCell *lc; + + if (stmt->withClause) + { + if (stmt->withClause->recursive) + { + /* + * In the RECURSIVE case, all query names of the WITH are + * visible to all WITH items as well as the main query. + * So push them all on, process, pop them all off. + */ + cstate->innerwiths = lcons(stmt->withClause->ctes, + cstate->innerwiths); + foreach(lc, stmt->withClause->ctes) + { + CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc); + + (void) checkWellFormedRecursionWalker(cte->ctequery, cstate); + } + checkWellFormedSelectStmt(stmt, cstate); + cstate->innerwiths = list_delete_first(cstate->innerwiths); + } + else + { + /* + * In the non-RECURSIVE case, query names are visible to + * the WITH items after them and to the main query. + */ + ListCell *cell1; + + cstate->innerwiths = lcons(NIL, cstate->innerwiths); + cell1 = list_head(cstate->innerwiths); + foreach(lc, stmt->withClause->ctes) + { + CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc); + + (void) checkWellFormedRecursionWalker(cte->ctequery, cstate); + lfirst(cell1) = lappend((List *) lfirst(cell1), cte); + } + checkWellFormedSelectStmt(stmt, cstate); + cstate->innerwiths = list_delete_first(cstate->innerwiths); + } + } + else + checkWellFormedSelectStmt(stmt, cstate); + /* We're done examining the SelectStmt */ + return false; + } + if (IsA(node, WithClause)) + { + /* + * Prevent raw_expression_tree_walker from recursing directly into + * a WITH clause. We need that to happen only under the control + * of the code above. + */ + return false; + } + if (IsA(node, JoinExpr)) + { + JoinExpr *j = (JoinExpr *) node; + + switch (j->jointype) + { + case JOIN_INNER: + checkWellFormedRecursionWalker(j->larg, cstate); + checkWellFormedRecursionWalker(j->rarg, cstate); + checkWellFormedRecursionWalker(j->quals, cstate); + break; + case JOIN_LEFT: + checkWellFormedRecursionWalker(j->larg, cstate); + if (save_context == RECURSION_OK) + cstate->context = RECURSION_OUTERJOIN; + checkWellFormedRecursionWalker(j->rarg, cstate); + cstate->context = save_context; + checkWellFormedRecursionWalker(j->quals, cstate); + break; + case JOIN_FULL: + if (save_context == RECURSION_OK) + cstate->context = RECURSION_OUTERJOIN; + checkWellFormedRecursionWalker(j->larg, cstate); + checkWellFormedRecursionWalker(j->rarg, cstate); + cstate->context = save_context; + checkWellFormedRecursionWalker(j->quals, cstate); + break; + case JOIN_RIGHT: + if (save_context == RECURSION_OK) + cstate->context = RECURSION_OUTERJOIN; + checkWellFormedRecursionWalker(j->larg, cstate); + cstate->context = save_context; + checkWellFormedRecursionWalker(j->rarg, cstate); + checkWellFormedRecursionWalker(j->quals, cstate); + break; + default: + elog(ERROR, "unrecognized join type: %d", + (int) j->jointype); + } + return false; + } + if (IsA(node, SubLink)) + { + SubLink *sl = (SubLink *) node; + + /* + * we intentionally override outer context, since subquery is + * independent + */ + cstate->context = RECURSION_SUBLINK; + checkWellFormedRecursionWalker(sl->subselect, cstate); + cstate->context = save_context; + checkWellFormedRecursionWalker(sl->testexpr, cstate); + return false; + } + return raw_expression_tree_walker(node, + checkWellFormedRecursionWalker, + (void *) cstate); + } + + /* + * subroutine for checkWellFormedRecursionWalker: process a SelectStmt + * without worrying about its WITH clause + */ + static void + checkWellFormedSelectStmt(SelectStmt *stmt, CteState *cstate) + { + RecursionContext save_context = cstate->context; + + if (save_context != RECURSION_OK) + { + /* just recurse without changing state */ + raw_expression_tree_walker((Node *) stmt, + checkWellFormedRecursionWalker, + (void *) cstate); + } + else + { + switch (stmt->op) + { + case SETOP_NONE: + case SETOP_UNION: + raw_expression_tree_walker((Node *) stmt, + checkWellFormedRecursionWalker, + (void *) cstate); + break; + case SETOP_INTERSECT: + if (stmt->all) + cstate->context = RECURSION_INTERSECT; + checkWellFormedRecursionWalker((Node *) stmt->larg, + cstate); + checkWellFormedRecursionWalker((Node *) stmt->rarg, + cstate); + cstate->context = save_context; + checkWellFormedRecursionWalker((Node *) stmt->sortClause, + cstate); + checkWellFormedRecursionWalker((Node *) stmt->limitOffset, + cstate); + checkWellFormedRecursionWalker((Node *) stmt->limitCount, + cstate); + checkWellFormedRecursionWalker((Node *) stmt->lockingClause, + cstate); + break; + break; + case SETOP_EXCEPT: + if (stmt->all) + cstate->context = RECURSION_EXCEPT; + checkWellFormedRecursionWalker((Node *) stmt->larg, + cstate); + cstate->context = RECURSION_EXCEPT; + checkWellFormedRecursionWalker((Node *) stmt->rarg, + cstate); + cstate->context = save_context; + checkWellFormedRecursionWalker((Node *) stmt->sortClause, + cstate); + checkWellFormedRecursionWalker((Node *) stmt->limitOffset, + cstate); + checkWellFormedRecursionWalker((Node *) stmt->limitCount, + cstate); + checkWellFormedRecursionWalker((Node *) stmt->lockingClause, + cstate); + break; + default: + elog(ERROR, "unrecognized set op: %d", + (int) stmt->op); + } + } + } *** src/backend/parser/parse_relation.c.orig Mon Sep 1 16:42:44 2008 --- src/backend/parser/parse_relation.c Fri Oct 3 13:17:46 2008 *************** *** 1109,1114 **** --- 1109,1196 ---- } /* + * Add an entry for a CTE reference to the pstate's range table (p_rtable). + * + * This is much like addRangeTableEntry() except that it makes a CTE RTE. + */ + RangeTblEntry * + addRangeTableEntryForCTE(ParseState *pstate, + CommonTableExpr *cte, + Index levelsup, + Alias *alias, + bool inFromCl) + { + RangeTblEntry *rte = makeNode(RangeTblEntry); + char *refname = alias ? alias->aliasname : cte->ctename; + Alias *eref; + int numaliases; + int varattno; + ListCell *lc; + + rte->rtekind = RTE_CTE; + rte->ctename = cte->ctename; + rte->ctelevelsup = levelsup; + + /* Self-reference if and only if CTE's parse analysis isn't completed */ + rte->self_reference = !IsA(cte->ctequery, Query); + Assert(cte->cterecursive || !rte->self_reference); + /* Bump the CTE's refcount if this isn't a self-reference */ + if (!rte->self_reference) + cte->cterefcount++; + + rte->ctecoltypes = cte->ctecoltypes; + rte->ctecoltypmods = cte->ctecoltypmods; + + rte->alias = alias; + if (alias) + eref = copyObject(alias); + else + eref = makeAlias(refname, NIL); + numaliases = list_length(eref->colnames); + + /* fill in any unspecified alias columns */ + varattno = 0; + foreach(lc, cte->ctecolnames) + { + varattno++; + if (varattno > numaliases) + eref->colnames = lappend(eref->colnames, lfirst(lc)); + } + if (varattno < numaliases) + ereport(ERROR, + (errcode(ERRCODE_INVALID_COLUMN_REFERENCE), + errmsg("table \"%s\" has %d columns available but %d columns specified", + refname, varattno, numaliases))); + + rte->eref = eref; + + /*---------- + * Flags: + * - this RTE should be expanded to include descendant tables, + * - this RTE is in the FROM clause, + * - this RTE should be checked for appropriate access rights. + * + * Subqueries are never checked for access rights. + *---------- + */ + rte->inh = false; /* never true for subqueries */ + rte->inFromCl = inFromCl; + + rte->requiredPerms = 0; + rte->checkAsUser = InvalidOid; + + /* + * Add completed RTE to pstate's range table list, but not to join list + * nor namespace --- caller must do that if appropriate. + */ + if (pstate != NULL) + pstate->p_rtable = lappend(pstate->p_rtable, rte); + + return rte; + } + + + /* * Has the specified refname been selected FOR UPDATE/FOR SHARE? * * Note: we pay no attention to whether it's FOR UPDATE vs FOR SHARE. *************** *** 1444,1449 **** --- 1526,1566 ---- } } break; + case RTE_CTE: + { + ListCell *aliasp_item = list_head(rte->eref->colnames); + ListCell *lct; + ListCell *lcm; + + varattno = 0; + forboth(lct, rte->ctecoltypes, lcm, rte->ctecoltypmods) + { + Oid coltype = lfirst_oid(lct); + int32 coltypmod = lfirst_int(lcm); + + varattno++; + + if (colnames) + { + /* Assume there is one alias per output column */ + char *label = strVal(lfirst(aliasp_item)); + + *colnames = lappend(*colnames, makeString(pstrdup(label))); + aliasp_item = lnext(aliasp_item); + } + + if (colvars) + { + Var *varnode; + + varnode = makeVar(rtindex, varattno, + coltype, coltypmod, + sublevels_up); + *colvars = lappend(*colvars, varnode); + } + } + } + break; default: elog(ERROR, "unrecognized RTE kind: %d", (int) rte->rtekind); } *************** *** 1750,1755 **** --- 1867,1880 ---- *vartypmod = exprTypmod(aliasvar); } break; + case RTE_CTE: + { + /* CTE RTE --- get type info from lists in the RTE */ + Assert(attnum > 0 && attnum <= list_length(rte->ctecoltypes)); + *vartype = list_nth_oid(rte->ctecoltypes, attnum - 1); + *vartypmod = list_nth_int(rte->ctecoltypmods, attnum - 1); + } + break; default: elog(ERROR, "unrecognized RTE kind: %d", (int) rte->rtekind); } *************** *** 1788,1794 **** break; case RTE_SUBQUERY: case RTE_VALUES: ! /* Subselect and Values RTEs never have dropped columns */ result = false; break; case RTE_JOIN: --- 1913,1920 ---- break; case RTE_SUBQUERY: case RTE_VALUES: ! case RTE_CTE: ! /* Subselect, Values, CTE RTEs never have dropped columns */ result = false; break; case RTE_JOIN: *** src/backend/parser/parse_target.c.orig Mon Sep 1 16:42:44 2008 --- src/backend/parser/parse_target.c Mon Sep 22 19:21:52 2008 *************** *** 296,301 **** --- 296,304 ---- case RTE_VALUES: /* not a simple relation, leave it unmarked */ break; + case RTE_CTE: + /* XXX fixme */ + break; } } *************** *** 1176,1181 **** --- 1179,1187 ---- * its result columns as RECORD, which is not allowed. */ break; + case RTE_CTE: + /* XXX fixme */ + break; } /* *** src/backend/parser/parse_type.c.orig Mon Sep 1 16:42:45 2008 --- src/backend/parser/parse_type.c Mon Sep 22 11:16:32 2008 *************** *** 611,616 **** --- 611,617 ---- stmt->whereClause != NULL || stmt->groupClause != NIL || stmt->havingClause != NULL || + stmt->withClause != NULL || stmt->valuesLists != NIL || stmt->sortClause != NIL || stmt->limitOffset != NULL || *** src/backend/rewrite/rewriteDefine.c.orig Mon Aug 25 18:42:34 2008 --- src/backend/rewrite/rewriteDefine.c Mon Sep 22 15:30:59 2008 *************** *** 635,651 **** rte->checkAsUser = userid; } /* If there are sublinks, search for them and process their RTEs */ - /* ignore subqueries in rtable because we already processed them */ if (qry->hasSubLinks) query_tree_walker(qry, setRuleCheckAsUser_walker, (void *) &userid, ! QTW_IGNORE_RT_SUBQUERIES); } /* * Change the firing semantics of an existing rule. - * */ void EnableDisableRule(Relation rel, const char *rulename, --- 635,657 ---- rte->checkAsUser = userid; } + /* Recurse into subquery-in-WITH */ + foreach(l, qry->cteList) + { + CommonTableExpr *cte = (CommonTableExpr *) lfirst(l); + + setRuleCheckAsUser_Query((Query *) cte->ctequery, userid); + } + /* If there are sublinks, search for them and process their RTEs */ if (qry->hasSubLinks) query_tree_walker(qry, setRuleCheckAsUser_walker, (void *) &userid, ! QTW_IGNORE_RC_SUBQUERIES); } /* * Change the firing semantics of an existing rule. */ void EnableDisableRule(Relation rel, const char *rulename, *** src/backend/rewrite/rewriteHandler.c.orig Thu Sep 25 14:54:10 2008 --- src/backend/rewrite/rewriteHandler.c Thu Sep 25 14:56:31 2008 *************** *** 215,227 **** } } /* * Recurse into sublink subqueries, too. But we already did the ones in ! * the rtable. */ if (parsetree->hasSubLinks) query_tree_walker(parsetree, acquireLocksOnSubLinks, NULL, ! QTW_IGNORE_RT_SUBQUERIES); } /* --- 215,235 ---- } } + /* Recurse into subqueries in WITH */ + foreach(l, parsetree->cteList) + { + CommonTableExpr *cte = (CommonTableExpr *) lfirst(l); + + AcquireRewriteLocks((Query *) cte->ctequery); + } + /* * Recurse into sublink subqueries, too. But we already did the ones in ! * the rtable and cteList. */ if (parsetree->hasSubLinks) query_tree_walker(parsetree, acquireLocksOnSubLinks, NULL, ! QTW_IGNORE_RC_SUBQUERIES); } /* *************** *** 1295,1300 **** --- 1303,1309 ---- fireRIRrules(Query *parsetree, List *activeRIRs) { int rt_index; + ListCell *lc; /* * don't try to convert this into a foreach loop, because rtable list can *************** *** 1407,1419 **** heap_close(rel, NoLock); } /* * Recurse into sublink subqueries, too. But we already did the ones in ! * the rtable. */ if (parsetree->hasSubLinks) query_tree_walker(parsetree, fireRIRonSubLink, (void *) activeRIRs, ! QTW_IGNORE_RT_SUBQUERIES); return parsetree; } --- 1416,1437 ---- heap_close(rel, NoLock); } + /* Recurse into subqueries in WITH */ + foreach(lc, parsetree->cteList) + { + CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc); + + cte->ctequery = (Node *) + fireRIRrules((Query *) cte->ctequery, activeRIRs); + } + /* * Recurse into sublink subqueries, too. But we already did the ones in ! * the rtable and cteList. */ if (parsetree->hasSubLinks) query_tree_walker(parsetree, fireRIRonSubLink, (void *) activeRIRs, ! QTW_IGNORE_RC_SUBQUERIES); return parsetree; } *** src/backend/rewrite/rewriteManip.c.orig Mon Sep 1 16:42:45 2008 --- src/backend/rewrite/rewriteManip.c Tue Sep 23 17:21:19 2008 *************** *** 183,195 **** checkExprHasSubLink(Node *node) { /* ! * If a Query is passed, examine it --- but we need not recurse into ! * sub-Queries. */ return query_or_expression_tree_walker(node, checkExprHasSubLink_walker, NULL, ! QTW_IGNORE_RT_SUBQUERIES); } static bool --- 183,195 ---- checkExprHasSubLink(Node *node) { /* ! * If a Query is passed, examine it --- but we should not recurse into ! * sub-Queries that are in its rangetable or CTE list. */ return query_or_expression_tree_walker(node, checkExprHasSubLink_walker, NULL, ! QTW_IGNORE_RC_SUBQUERIES); } static bool *************** *** 543,549 **** * that sublink are not affected, only outer references to vars that belong * to the expression's original query level or parents thereof. * ! * Aggref nodes are adjusted similarly. * * NOTE: although this has the form of a walker, we cheat and modify the * Var nodes in-place. The given expression tree should have been copied --- 543,549 ---- * that sublink are not affected, only outer references to vars that belong * to the expression's original query level or parents thereof. * ! * Likewise for other nodes containing levelsup fields, such as Aggref. * * NOTE: although this has the form of a walker, we cheat and modify the * Var nodes in-place. The given expression tree should have been copied *************** *** 585,590 **** --- 585,601 ---- agg->agglevelsup += context->delta_sublevels_up; /* fall through to recurse into argument */ } + if (IsA(node, RangeTblEntry)) + { + RangeTblEntry *rte = (RangeTblEntry *) node; + + if (rte->rtekind == RTE_CTE) + { + if (rte->ctelevelsup >= context->min_sublevels_up) + rte->ctelevelsup += context->delta_sublevels_up; + } + return false; /* allow range_table_walker to continue */ + } if (IsA(node, Query)) { /* Recurse into subselects */ *************** *** 593,599 **** context->min_sublevels_up++; result = query_tree_walker((Query *) node, IncrementVarSublevelsUp_walker, ! (void *) context, 0); context->min_sublevels_up--; return result; } --- 604,611 ---- context->min_sublevels_up++; result = query_tree_walker((Query *) node, IncrementVarSublevelsUp_walker, ! (void *) context, ! QTW_EXAMINE_RTES); context->min_sublevels_up--; return result; } *************** *** 617,623 **** query_or_expression_tree_walker(node, IncrementVarSublevelsUp_walker, (void *) &context, ! 0); } /* --- 629,635 ---- query_or_expression_tree_walker(node, IncrementVarSublevelsUp_walker, (void *) &context, ! QTW_EXAMINE_RTES); } /* *************** *** 636,642 **** range_table_walker(rtable, IncrementVarSublevelsUp_walker, (void *) &context, ! 0); } --- 648,654 ---- range_table_walker(rtable, IncrementVarSublevelsUp_walker, (void *) &context, ! QTW_EXAMINE_RTES); } *** src/backend/utils/adt/ruleutils.c.orig Sat Sep 6 16:18:08 2008 --- src/backend/utils/adt/ruleutils.c Tue Sep 30 13:23:17 2008 *************** *** 145,150 **** --- 145,151 ---- static void get_query_def(Query *query, StringInfo buf, List *parentnamespace, TupleDesc resultDesc, int prettyFlags, int startIndent); static void get_values_def(List *values_lists, deparse_context *context); + static void get_with_clause(Query *query, deparse_context *context); static void get_select_query_def(Query *query, deparse_context *context, TupleDesc resultDesc); static void get_insert_query_def(Query *query, deparse_context *context); *************** *** 2205,2210 **** --- 2206,2261 ---- } /* ---------- + * get_with_clause - Parse back a WITH clause + * ---------- + */ + static void + get_with_clause(Query *query, deparse_context *context) + { + StringInfo buf = context->buf; + const char *sep; + ListCell *l; + + if (query->cteList == NIL) + return; + + if (query->hasRecursive) + sep = "WITH RECURSIVE "; + else + sep = "WITH "; + foreach(l, query->cteList) + { + CommonTableExpr *cte = (CommonTableExpr *) lfirst(l); + + appendStringInfoString(buf, sep); + appendStringInfoString(buf, quote_identifier(cte->ctename)); + if (cte->aliascolnames) + { + bool first = true; + ListCell *col; + + appendStringInfoChar(buf, '('); + foreach(col, cte->aliascolnames) + { + if (first) + first = false; + else + appendStringInfoString(buf, ", "); + appendStringInfoString(buf, + quote_identifier(strVal(lfirst(col)))); + } + appendStringInfoChar(buf, ')'); + } + appendStringInfoString(buf, " AS ("); + get_query_def((Query *) cte->ctequery, buf, context->namespaces, NULL, + context->prettyFlags, context->indentLevel); + appendStringInfoChar(buf, ')'); + sep = ", "; + } + appendStringInfoChar(buf, ' '); + } + + /* ---------- * get_select_query_def - Parse back a SELECT parsetree * ---------- */ *************** *** 2217,2226 **** char *sep; ListCell *l; /* * If the Query node has a setOperations tree, then it's the top level of ! * a UNION/INTERSECT/EXCEPT query; only the ORDER BY and LIMIT fields are ! * interesting in the top query itself. */ if (query->setOperations) { --- 2268,2280 ---- char *sep; ListCell *l; + /* Insert the WITH clause if given */ + get_with_clause(query, context); + /* * If the Query node has a setOperations tree, then it's the top level of ! * a UNION/INTERSECT/EXCEPT query; only the WITH, ORDER BY and LIMIT ! * fields are interesting in the top query itself. */ if (query->setOperations) { *************** *** 2730,2740 **** --- 2784,2798 ---- } else if (values_rte) { + /* A WITH clause is possible here */ + get_with_clause(query, context); /* Add the multi-VALUES expression lists */ get_values_def(values_rte->values_lists, context); } else { + /* A WITH clause is possible here */ + get_with_clause(query, context); /* Add the single-VALUES expression list */ appendContextKeyword(context, "VALUES (", -PRETTYINDENT_STD, PRETTYINDENT_STD, 2); *************** *** 3259,3264 **** --- 3317,3323 ---- case RTE_RELATION: case RTE_SPECIAL: case RTE_VALUES: + case RTE_CTE: /* XXX fixme */ /* * This case should not occur: a column of a table or values list *************** *** 5130,5135 **** --- 5189,5197 ---- /* Values list RTE */ get_values_def(rte->values_lists, context); break; + case RTE_CTE: + appendStringInfoString(buf, quote_identifier(rte->ctename)); + break; default: elog(ERROR, "unrecognized RTE kind: %d", (int) rte->rtekind); break; *** src/backend/utils/cache/plancache.c.orig Mon Sep 15 19:37:39 2008 --- src/backend/utils/cache/plancache.c Mon Sep 22 15:31:46 2008 *************** *** 728,742 **** } } /* * Recurse into sublink subqueries, too. But we already did the ones in ! * the rtable. */ if (parsetree->hasSubLinks) { query_tree_walker(parsetree, ScanQueryWalker, (void *) &acquire, ! QTW_IGNORE_RT_SUBQUERIES); } } --- 728,750 ---- } } + /* Recurse into subquery-in-WITH */ + foreach(lc, parsetree->cteList) + { + CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc); + + ScanQueryForLocks((Query *) cte->ctequery, acquire); + } + /* * Recurse into sublink subqueries, too. But we already did the ones in ! * the rtable and cteList. */ if (parsetree->hasSubLinks) { query_tree_walker(parsetree, ScanQueryWalker, (void *) &acquire, ! QTW_IGNORE_RC_SUBQUERIES); } } *** src/backend/utils/sort/tuplestore.c.orig Wed Oct 1 19:23:24 2008 --- src/backend/utils/sort/tuplestore.c Fri Oct 3 12:21:11 2008 *************** *** 86,92 **** typedef struct { int eflags; /* capability flags */ ! bool eof_reached; /* read reached EOF */ int current; /* next array index to read */ int file; /* temp file# */ off_t offset; /* byte offset in file */ --- 86,92 ---- typedef struct { int eflags; /* capability flags */ ! bool eof_reached; /* read has reached EOF */ int current; /* next array index to read */ int file; /* temp file# */ off_t offset; /* byte offset in file */ *************** *** 374,379 **** --- 374,412 ---- } /* + * tuplestore_clear + * + * Delete all the contents of a tuplestore, and reset its read pointers + * to the start. + */ + void + tuplestore_clear(Tuplestorestate *state) + { + int i; + TSReadPointer *readptr; + + if (state->myfile) + BufFileClose(state->myfile); + state->myfile = NULL; + if (state->memtuples) + { + for (i = 0; i < state->memtupcount; i++) + { + FREEMEM(state, GetMemoryChunkSpace(state->memtuples[i])); + pfree(state->memtuples[i]); + } + } + state->status = TSS_INMEM; + state->memtupcount = 0; + readptr = state->readptrs; + for (i = 0; i < state->readptrcount; readptr++, i++) + { + readptr->eof_reached = false; + readptr->current = 0; + } + } + + /* * tuplestore_end * * Release resources and clean up. *************** *** 463,471 **** * * Note that the input tuple is always copied; the caller need not save it. * ! * Any read pointer that is currently "AT EOF" remains so (the read pointer ! * implicitly advances along with the write pointer); otherwise the read ! * pointer is unchanged. This is for the convenience of nodeMaterial.c. * * tuplestore_puttupleslot() is a convenience routine to collect data from * a TupleTableSlot without an extra copy operation. --- 496,508 ---- * * Note that the input tuple is always copied; the caller need not save it. * ! * If the active read pointer is currently "at EOF", it remains so (the read ! * pointer implicitly advances along with the write pointer); otherwise the ! * read pointer is unchanged. Non-active read pointers do not move, which ! * means they are certain to not be "at EOF" immediately after puttuple. ! * This curious-seeming behavior is for the convenience of nodeMaterial.c and ! * nodeCtescan.c, which would otherwise need to do extra pointer repositioning ! * steps. * * tuplestore_puttupleslot() is a convenience routine to collect data from * a TupleTableSlot without an extra copy operation. *************** *** 519,529 **** --- 556,582 ---- static void tuplestore_puttuple_common(Tuplestorestate *state, void *tuple) { + TSReadPointer *readptr; + int i; + switch (state->status) { case TSS_INMEM: /* + * Update read pointers as needed; see API spec above. + */ + readptr = state->readptrs; + for (i = 0; i < state->readptrcount; readptr++, i++) + { + if (readptr->eof_reached && i != state->activeptr) + { + readptr->eof_reached = false; + readptr->current = state->memtupcount; + } + } + + /* * Grow the array as needed. Note that we try to grow the array * when there is still one free slot remaining --- if we fail, * there'll still be room to store the incoming tuple, and then *************** *** 572,577 **** --- 625,648 ---- dumptuples(state); break; case TSS_WRITEFILE: + + /* + * Update read pointers as needed; see API spec above. + * Note: BufFileTell is quite cheap, so not worth trying + * to avoid multiple calls. + */ + readptr = state->readptrs; + for (i = 0; i < state->readptrcount; readptr++, i++) + { + if (readptr->eof_reached && i != state->activeptr) + { + readptr->eof_reached = false; + BufFileTell(state->myfile, + &readptr->file, + &readptr->offset); + } + } + WRITETUP(state, tuple); break; case TSS_READFILE: *************** *** 588,593 **** --- 659,679 ---- SEEK_SET) != 0) elog(ERROR, "tuplestore seek to EOF failed"); state->status = TSS_WRITEFILE; + + /* + * Update read pointers as needed; see API spec above. + */ + readptr = state->readptrs; + for (i = 0; i < state->readptrcount; readptr++, i++) + { + if (readptr->eof_reached && i != state->activeptr) + { + readptr->eof_reached = false; + readptr->file = state->writepos_file; + readptr->offset = state->writepos_offset; + } + } + WRITETUP(state, tuple); break; default: *** src/bin/psql/tab-complete.c.orig Sun Sep 7 20:47:40 2008 --- src/bin/psql/tab-complete.c Tue Sep 30 13:07:55 2008 *************** *** 615,621 **** "GRANT", "INSERT", "LISTEN", "LOAD", "LOCK", "MOVE", "NOTIFY", "PREPARE", "REASSIGN", "REINDEX", "RELEASE", "RESET", "REVOKE", "ROLLBACK", "SAVEPOINT", "SELECT", "SET", "SHOW", "START", "TRUNCATE", "UNLISTEN", ! "UPDATE", "VACUUM", "VALUES", NULL }; static const char *const backslash_commands[] = { --- 615,621 ---- "GRANT", "INSERT", "LISTEN", "LOAD", "LOCK", "MOVE", "NOTIFY", "PREPARE", "REASSIGN", "REINDEX", "RELEASE", "RESET", "REVOKE", "ROLLBACK", "SAVEPOINT", "SELECT", "SET", "SHOW", "START", "TRUNCATE", "UNLISTEN", ! "UPDATE", "VACUUM", "VALUES", "WITH", NULL }; static const char *const backslash_commands[] = { *************** *** 2044,2049 **** --- 2044,2053 ---- pg_strcasecmp(prev2_wd, "ANALYZE") == 0)) COMPLETE_WITH_SCHEMA_QUERY(Query_for_list_of_tables, NULL); + /* WITH [RECURSIVE] */ + else if (pg_strcasecmp(prev_wd, "WITH") == 0) + COMPLETE_WITH_CONST("RECURSIVE"); + /* ANALYZE */ /* If the previous word is ANALYZE, produce list of tables */ else if (pg_strcasecmp(prev_wd, "ANALYZE") == 0) *** src/include/executor/nodeCtescan.h.orig Thu Oct 2 14:50:43 2008 --- src/include/executor/nodeCtescan.h Thu Oct 2 14:52:47 2008 *************** *** 0 **** --- 1,25 ---- + /*------------------------------------------------------------------------- + * + * nodeCtescan.h + * + * + * + * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * $PostgreSQL$ + * + *------------------------------------------------------------------------- + */ + #ifndef NODECTESCAN_H + #define NODECTESCAN_H + + #include "nodes/execnodes.h" + + extern int ExecCountSlotsCteScan(CteScan *node); + extern CteScanState *ExecInitCteScan(CteScan *node, EState *estate, int eflags); + extern TupleTableSlot *ExecCteScan(CteScanState *node); + extern void ExecEndCteScan(CteScanState *node); + extern void ExecCteScanReScan(CteScanState *node, ExprContext *exprCtxt); + + #endif /* NODECTESCAN_H */ *** src/include/executor/nodeRecursiveunion.h.orig Mon Sep 22 11:16:32 2008 --- src/include/executor/nodeRecursiveunion.h Tue Sep 30 17:20:15 2008 *************** *** 0 **** --- 1,25 ---- + /*------------------------------------------------------------------------- + * + * nodeRecursiveunion.h + * + * + * + * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * $PostgreSQL$ + * + *------------------------------------------------------------------------- + */ + #ifndef NODERECURSIVEUNION_H + #define NODERECURSIVEUNION_H + + #include "nodes/execnodes.h" + + extern int ExecCountSlotsRecursiveUnion(RecursiveUnion *node); + extern RecursiveUnionState *ExecInitRecursiveUnion(RecursiveUnion *node, EState *estate, int eflags); + extern TupleTableSlot *ExecRecursiveUnion(RecursiveUnionState *node); + extern void ExecEndRecursiveUnion(RecursiveUnionState *node); + extern void ExecRecursiveUnionReScan(RecursiveUnionState *node, ExprContext *exprCtxt); + + #endif /* NODERECURSIVEUNION_H */ *** src/include/executor/nodeWorktablescan.h.orig Mon Sep 22 11:16:32 2008 --- src/include/executor/nodeWorktablescan.h Tue Sep 30 20:21:57 2008 *************** *** 0 **** --- 1,25 ---- + /*------------------------------------------------------------------------- + * + * nodeWorktablescan.h + * + * + * + * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * $PostgreSQL$ + * + *------------------------------------------------------------------------- + */ + #ifndef NODEWORKTABLESCAN_H + #define NODEWORKTABLESCAN_H + + #include "nodes/execnodes.h" + + extern int ExecCountSlotsWorkTableScan(WorkTableScan *node); + extern WorkTableScanState *ExecInitWorkTableScan(WorkTableScan *node, EState *estate, int eflags); + extern TupleTableSlot *ExecWorkTableScan(WorkTableScanState *node); + extern void ExecEndWorkTableScan(WorkTableScanState *node); + extern void ExecWorkTableScanReScan(WorkTableScanState *node, ExprContext *exprCtxt); + + #endif /* NODEWORKTABLESCAN_H */ *** src/include/nodes/execnodes.h.orig Wed Oct 1 20:25:19 2008 --- src/include/nodes/execnodes.h Fri Oct 3 13:00:43 2008 *************** *** 947,952 **** --- 947,972 ---- } AppendState; /* ---------------- + * RecursiveUnionState information + * + * RecursiveUnionState is used for performing a recursive union. + * + * recursing T when we're done scanning the non-recursive term + * intermediate_empty T if intermediate_table is currently empty + * working_table working table (to be scanned by recursive term) + * intermediate_table current recursive output (next generation of WT) + * ---------------- + */ + typedef struct RecursiveUnionState + { + PlanState ps; /* its first field is NodeTag */ + bool recursing; + bool intermediate_empty; + Tuplestorestate *working_table; + Tuplestorestate *intermediate_table; + } RecursiveUnionState; + + /* ---------------- * BitmapAndState information * ---------------- */ *************** *** 1179,1184 **** --- 1199,1241 ---- int marked_idx; } ValuesScanState; + /* ---------------- + * CteScanState information + * + * CteScan nodes are used to scan a CommonTableExpr query. + * + * Multiple CteScan nodes can read out from the same CTE query. We use + * a tuplestore to hold rows that have been read from the CTE query but + * not yet consumed by all readers. + * ---------------- + */ + typedef struct CteScanState + { + ScanState ss; /* its first field is NodeTag */ + int eflags; /* capability flags to pass to tuplestore */ + int readptr; /* index of my tuplestore read pointer */ + PlanState *cteplanstate; /* PlanState for the CTE query itself */ + /* Link to the "leader" CteScanState (possibly this same node) */ + struct CteScanState *leader; + /* The remaining fields are only valid in the "leader" CteScanState */ + Tuplestorestate *cte_table; /* rows already read from the CTE query */ + bool eof_cte; /* reached end of CTE query? */ + } CteScanState; + + /* ---------------- + * WorkTableScanState information + * + * WorkTableScan nodes are used to scan the work table created by + * a RecursiveUnion node. We locate the RecursiveUnion node + * during executor startup. + * ---------------- + */ + typedef struct WorkTableScanState + { + ScanState ss; /* its first field is NodeTag */ + RecursiveUnionState *rustate; + } WorkTableScanState; + /* ---------------------------------------------------------------- * Join State Information * ---------------------------------------------------------------- *** src/include/nodes/nodeFuncs.h.orig Thu Aug 28 19:09:48 2008 --- src/include/nodes/nodeFuncs.h Tue Sep 23 19:58:05 2008 *************** *** 18,25 **** /* flags bits for query_tree_walker and query_tree_mutator */ #define QTW_IGNORE_RT_SUBQUERIES 0x01 /* subqueries in rtable */ ! #define QTW_IGNORE_JOINALIASES 0x02 /* JOIN alias var lists */ ! #define QTW_DONT_COPY_QUERY 0x04 /* do not copy top Query */ extern Oid exprType(Node *expr); --- 18,28 ---- /* flags bits for query_tree_walker and query_tree_mutator */ #define QTW_IGNORE_RT_SUBQUERIES 0x01 /* subqueries in rtable */ ! #define QTW_IGNORE_CTE_SUBQUERIES 0x02 /* subqueries in cteList */ ! #define QTW_IGNORE_RC_SUBQUERIES 0x03 /* both of above */ ! #define QTW_IGNORE_JOINALIASES 0x04 /* JOIN alias var lists */ ! #define QTW_EXAMINE_RTES 0x08 /* examine RTEs */ ! #define QTW_DONT_COPY_QUERY 0x10 /* do not copy top Query */ extern Oid exprType(Node *expr); *************** *** 49,52 **** --- 52,58 ---- extern Node *query_or_expression_tree_mutator(Node *node, Node *(*mutator) (), void *context, int flags); + extern bool raw_expression_tree_walker(Node *node, bool (*walker) (), + void *context); + #endif /* NODEFUNCS_H */ *** src/include/nodes/nodes.h.orig Tue Sep 9 14:58:08 2008 --- src/include/nodes/nodes.h Thu Oct 2 14:47:04 2008 *************** *** 44,49 **** --- 44,50 ---- T_Plan = 100, T_Result, T_Append, + T_RecursiveUnion, T_BitmapAnd, T_BitmapOr, T_Scan, *************** *** 55,60 **** --- 56,63 ---- T_SubqueryScan, T_FunctionScan, T_ValuesScan, + T_CteScan, + T_WorkTableScan, T_Join, T_NestLoop, T_MergeJoin, *************** *** 78,83 **** --- 81,87 ---- T_PlanState = 200, T_ResultState, T_AppendState, + T_RecursiveUnionState, T_BitmapAndState, T_BitmapOrState, T_ScanState, *************** *** 89,94 **** --- 93,100 ---- T_SubqueryScanState, T_FunctionScanState, T_ValuesScanState, + T_CteScanState, + T_WorkTableScanState, T_JoinState, T_NestLoopState, T_MergeJoinState, *************** *** 352,357 **** --- 358,365 ---- T_LockingClause, T_RowMarkClause, T_XmlSerialize, + T_WithClause, + T_CommonTableExpr, /* * TAGS FOR RANDOM OTHER STUFF *** src/include/nodes/parsenodes.h.orig Sun Sep 7 20:47:41 2008 --- src/include/nodes/parsenodes.h Tue Sep 30 10:49:18 2008 *************** *** 115,120 **** --- 115,123 ---- bool hasAggs; /* has aggregates in tlist or havingQual */ bool hasSubLinks; /* has subquery SubLink */ bool hasDistinctOn; /* distinctClause is from DISTINCT ON */ + bool hasRecursive; /* WITH RECURSIVE was specified */ + + List *cteList; /* WITH list (of CommonTableExpr's) */ List *rtable; /* list of range table entries */ FromExpr *jointree; /* table join tree (FROM and WHERE clauses) */ *************** *** 563,569 **** RTE_JOIN, /* join */ RTE_SPECIAL, /* special rule relation (NEW or OLD) */ RTE_FUNCTION, /* function in FROM */ ! RTE_VALUES /* VALUES (), (), ... */ } RTEKind; typedef struct RangeTblEntry --- 566,573 ---- RTE_JOIN, /* join */ RTE_SPECIAL, /* special rule relation (NEW or OLD) */ RTE_FUNCTION, /* function in FROM */ ! RTE_VALUES, /* VALUES (), (), ... */ ! RTE_CTE /* common table expr (WITH list element) */ } RTEKind; typedef struct RangeTblEntry *************** *** 589,594 **** --- 593,612 ---- Query *subquery; /* the sub-query */ /* + * Fields valid for a join RTE (else NULL/zero): + * + * joinaliasvars is a list of Vars or COALESCE expressions corresponding + * to the columns of the join result. An alias Var referencing column K + * of the join result can be replaced by the K'th element of joinaliasvars + * --- but to simplify the task of reverse-listing aliases correctly, we + * do not do that until planning time. In a Query loaded from a stored + * rule, it is also possible for joinaliasvars items to be NULL Consts, + * denoting columns dropped since the rule was made. + */ + JoinType jointype; /* type of join */ + List *joinaliasvars; /* list of alias-var expansions */ + + /* * Fields valid for a function RTE (else NULL): * * If the function returns RECORD, funccoltypes lists the column types *************** *** 605,622 **** List *values_lists; /* list of expression lists */ /* ! * Fields valid for a join RTE (else NULL/zero): ! * ! * joinaliasvars is a list of Vars or COALESCE expressions corresponding ! * to the columns of the join result. An alias Var referencing column K ! * of the join result can be replaced by the K'th element of joinaliasvars ! * --- but to simplify the task of reverse-listing aliases correctly, we ! * do not do that until planning time. In a Query loaded from a stored ! * rule, it is also possible for joinaliasvars items to be NULL Consts, ! * denoting columns dropped since the rule was made. */ ! JoinType jointype; /* type of join */ ! List *joinaliasvars; /* list of alias-var expansions */ /* * Fields valid in all RTEs: --- 623,635 ---- List *values_lists; /* list of expression lists */ /* ! * Fields valid for a CTE RTE (else NULL/zero): */ ! char *ctename; /* name of the WITH list item */ ! Index ctelevelsup; /* number of query levels up */ ! bool self_reference; /* is this a recursive self-reference? */ ! List *ctecoltypes; /* OID list of column type OIDs */ ! List *ctecoltypmods; /* integer list of column typmods */ /* * Fields valid in all RTEs: *************** *** 697,702 **** --- 710,752 ---- bool noWait; /* NOWAIT option */ } RowMarkClause; + /* + * WithClause - + * representation of WITH clause + * + * Note: WithClause does not propagate into the Query representation; + * but CommonTableExpr does. + */ + typedef struct WithClause + { + NodeTag type; + List *ctes; /* list of CommonTableExprs */ + bool recursive; /* true = WITH RECURSIVE */ + int location; /* token location, or -1 if unknown */ + } WithClause; + + /* + * CommonTableExpr - + * representation of WITH list element + * + * We don't currently support the SEARCH or CYCLE clause. + */ + typedef struct CommonTableExpr + { + NodeTag type; + char *ctename; /* query name (never qualified) */ + List *aliascolnames; /* optional list of column names */ + Node *ctequery; /* subquery (SelectStmt or Query) */ + int location; /* token location, or -1 if unknown */ + /* These fields are set during parse analysis: */ + bool cterecursive; /* is this CTE actually recursive? */ + int cterefcount; /* number of RTEs referencing this CTE + * (excluding internal self-references) */ + List *ctecolnames; /* list of output column names */ + List *ctecoltypes; /* OID list of output column type OIDs */ + List *ctecoltypmods; /* integer list of output column typmods */ + } CommonTableExpr; + /***************************************************************************** * Optimizable Statements *****************************************************************************/ *************** *** 781,786 **** --- 831,837 ---- Node *whereClause; /* WHERE qualification */ List *groupClause; /* GROUP BY clauses */ Node *havingClause; /* HAVING conditional-expression */ + WithClause *withClause; /* WITH clause */ /* * In a "leaf" node representing a VALUES list, the above fields are all *** src/include/nodes/plannodes.h.orig Tue Sep 9 14:58:08 2008 --- src/include/nodes/plannodes.h Thu Oct 2 16:31:29 2008 *************** *** 183,188 **** --- 183,202 ---- } Append; /* ---------------- + * RecursiveUnion node - + * Generate a recursive union of two subplans. + * + * The "outer" subplan is always the non-recursive term, and the "inner" + * subplan is the recursive term. + * ---------------- + */ + typedef struct RecursiveUnion + { + Plan plan; + int wtParam; /* ID of Param representing work table */ + } RecursiveUnion; + + /* ---------------- * BitmapAnd node - * Generate the intersection of the results of sub-plans. * *************** *** 358,363 **** --- 372,399 ---- List *values_lists; /* list of expression lists */ } ValuesScan; + /* ---------------- + * CteScan node + * ---------------- + */ + typedef struct CteScan + { + Scan scan; + int ctePlanId; /* ID of init SubPlan for CTE */ + int cteParam; /* ID of Param representing CTE output */ + } CteScan; + + /* ---------------- + * WorkTableScan node + * ---------------- + */ + typedef struct WorkTableScan + { + Scan scan; + int wtParam; /* ID of Param representing work table */ + } WorkTableScan; + + /* * ========== * Join nodes *** src/include/nodes/relation.h.orig Tue Sep 9 14:58:08 2008 --- src/include/nodes/relation.h Thu Oct 2 14:47:05 2008 *************** *** 104,109 **** --- 104,111 ---- Index query_level; /* 1 at the outermost Query */ + struct PlannerInfo *parent_root; /* NULL at outermost Query */ + /* * simple_rel_array holds pointers to "base rels" and "other rels" (see * comments for RelOptInfo for more info). It is indexed by rangetable *************** *** 138,144 **** List *returningLists; /* list of lists of TargetEntry, or NIL */ ! List *init_plans; /* init subplans for query */ List *eq_classes; /* list of active EquivalenceClasses */ --- 140,148 ---- List *returningLists; /* list of lists of TargetEntry, or NIL */ ! List *init_plans; /* init SubPlans for query */ ! ! List *cte_plan_ids; /* per-CTE-item list of subplan IDs */ List *eq_classes; /* list of active EquivalenceClasses */ *************** *** 178,183 **** --- 182,192 ---- bool hasHavingQual; /* true if havingQual was non-null */ bool hasPseudoConstantQuals; /* true if any RestrictInfo has * pseudoconstant = true */ + bool hasRecursion; /* true if planning a recursive WITH item */ + + /* These fields are used only when hasRecursion is true: */ + int wt_param_id; /* PARAM_EXEC ID for the work table */ + struct Plan *non_recursive_plan; /* plan for non-recursive term */ } PlannerInfo; *************** *** 542,549 **** } PathKey; /* ! * Type "Path" is used as-is for sequential-scan paths. For other ! * path types it is the first component of a larger struct. * * Note: "pathtype" is the NodeTag of the Plan node we could build from this * Path. It is partially redundant with the Path's NodeTag, but allows us --- 551,559 ---- } PathKey; /* ! * Type "Path" is used as-is for sequential-scan paths, as well as some other ! * simple plan types that we don't need any extra information in the path for. ! * For other path types it is the first component of a larger struct. * * Note: "pathtype" is the NodeTag of the Plan node we could build from this * Path. It is partially redundant with the Path's NodeTag, but allows us *** src/include/optimizer/cost.h.orig Thu Aug 21 20:16:04 2008 --- src/include/optimizer/cost.h Fri Oct 3 13:57:42 2008 *************** *** 72,77 **** --- 72,79 ---- RelOptInfo *baserel); extern void cost_valuesscan(Path *path, PlannerInfo *root, RelOptInfo *baserel); + extern void cost_ctescan(Path *path, PlannerInfo *root, RelOptInfo *baserel); + extern void cost_recursive_union(Plan *runion, Plan *nrterm, Plan *rterm); extern void cost_sort(Path *path, PlannerInfo *root, List *pathkeys, Cost input_cost, double tuples, int width, double limit_tuples); *************** *** 104,109 **** --- 106,113 ---- List *restrictlist); extern void set_function_size_estimates(PlannerInfo *root, RelOptInfo *rel); extern void set_values_size_estimates(PlannerInfo *root, RelOptInfo *rel); + extern void set_cte_size_estimates(PlannerInfo *root, RelOptInfo *rel, + Plan *cteplan); /* * prototypes for clausesel.c *** src/include/optimizer/pathnode.h.orig Thu Aug 14 14:48:00 2008 --- src/include/optimizer/pathnode.h Thu Oct 2 14:46:59 2008 *************** *** 54,59 **** --- 54,61 ---- extern Path *create_subqueryscan_path(RelOptInfo *rel, List *pathkeys); extern Path *create_functionscan_path(PlannerInfo *root, RelOptInfo *rel); extern Path *create_valuesscan_path(PlannerInfo *root, RelOptInfo *rel); + extern Path *create_ctescan_path(PlannerInfo *root, RelOptInfo *rel); + extern Path *create_worktablescan_path(PlannerInfo *root, RelOptInfo *rel); extern NestPath *create_nestloop_path(PlannerInfo *root, RelOptInfo *joinrel, *** src/include/optimizer/planmain.h.orig Tue Sep 9 14:58:09 2008 --- src/include/optimizer/planmain.h Tue Sep 30 19:33:29 2008 *************** *** 42,47 **** --- 42,49 ---- extern SubqueryScan *make_subqueryscan(List *qptlist, List *qpqual, Index scanrelid, Plan *subplan, List *subrtable); extern Append *make_append(List *appendplans, bool isTarget, List *tlist); + extern RecursiveUnion *make_recursive_union(List *tlist, + Plan *lefttree, Plan *righttree, int wtParam); extern Sort *make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys, double limit_tuples); extern Sort *make_sort_from_sortclauses(PlannerInfo *root, List *sortcls, *** src/include/optimizer/planner.h.orig Tue Jan 1 14:45:58 2008 --- src/include/optimizer/planner.h Tue Sep 30 15:22:29 2008 *************** *** 30,36 **** extern PlannedStmt *standard_planner(Query *parse, int cursorOptions, ParamListInfo boundParams); extern Plan *subquery_planner(PlannerGlobal *glob, Query *parse, ! Index level, double tuple_fraction, PlannerInfo **subroot); #endif /* PLANNER_H */ --- 30,37 ---- extern PlannedStmt *standard_planner(Query *parse, int cursorOptions, ParamListInfo boundParams); extern Plan *subquery_planner(PlannerGlobal *glob, Query *parse, ! PlannerInfo *parent_root, ! bool hasRecursion, double tuple_fraction, PlannerInfo **subroot); #endif /* PLANNER_H */ *** src/include/optimizer/subselect.h.orig Sat Aug 16 21:20:00 2008 --- src/include/optimizer/subselect.h Thu Oct 2 14:00:33 2008 *************** *** 15,20 **** --- 15,21 ---- #include "nodes/plannodes.h" #include "nodes/relation.h" + extern void SS_process_ctes(PlannerInfo *root); extern bool convert_ANY_sublink_to_join(PlannerInfo *root, SubLink *sublink, Relids available_rels, Node **new_qual, List **fromlist); *************** *** 28,32 **** --- 29,34 ---- bool attach_initplans); extern Param *SS_make_initplan_from_plan(PlannerInfo *root, Plan *plan, Oid resulttype, int32 resulttypmod); + extern int SS_assign_worktable_param(PlannerInfo *root); #endif /* SUBSELECT_H */ *** src/include/parser/parse_cte.h.orig Mon Sep 22 11:16:32 2008 --- src/include/parser/parse_cte.h Tue Sep 23 12:23:54 2008 *************** *** 0 **** --- 1,21 ---- + /*------------------------------------------------------------------------- + * + * parse_cte.h + * handle CTEs (common table expressions) in parser + * + * + * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * $PostgreSQL$ + * + *------------------------------------------------------------------------- + */ + #ifndef PARSE_CTE_H + #define PARSE_CTE_H + + #include "parser/parse_node.h" + + extern List *transformWithClause(ParseState *pstate, WithClause *withClause); + + #endif /* PARSE_CTE_H */ *** src/include/parser/parse_node.h.orig Mon Sep 1 16:42:45 2008 --- src/include/parser/parse_node.h Tue Sep 23 14:02:46 2008 *************** *** 50,55 **** --- 50,59 ---- * implicit RTEs into p_relnamespace but not p_varnamespace, so that they * do not affect the set of columns available for unqualified references. * + * p_ctenamespace: list of CommonTableExprs (WITH items) that are visible + * at the moment. This is different from p_relnamespace because you have + * to make an RTE before you can access a CTE. + * * p_paramtypes: an array of p_numparams type OIDs for $n parameter symbols * (zeroth entry in array corresponds to $1). If p_variableparams is true, the * set of param types is not predetermined; in that case, a zero array entry *************** *** 68,73 **** --- 72,78 ---- * node's fromlist) */ List *p_relnamespace; /* current namespace for relations */ List *p_varnamespace; /* current namespace for columns */ + List *p_ctenamespace; /* current namespace for common table exprs */ Oid *p_paramtypes; /* OIDs of types for $n parameter symbols */ int p_numparams; /* allocated size of p_paramtypes[] */ int p_next_resno; /* next targetlist resno to assign */ *** src/include/parser/parse_relation.h.orig Mon Sep 1 16:42:45 2008 --- src/include/parser/parse_relation.h Tue Sep 23 10:55:36 2008 *************** *** 72,77 **** --- 72,82 ---- List *aliasvars, Alias *alias, bool inFromCl); + extern RangeTblEntry *addRangeTableEntryForCTE(ParseState *pstate, + CommonTableExpr *cte, + Index levelsup, + Alias *alias, + bool inFromCl); extern void addRTEtoQuery(ParseState *pstate, RangeTblEntry *rte, bool addToJoinList, bool addToRelNameSpace, bool addToVarNameSpace); *** src/include/utils/errcodes.h.orig Thu May 15 18:39:49 2008 --- src/include/utils/errcodes.h Tue Sep 30 10:37:04 2008 *************** *** 246,251 **** --- 246,252 ---- #define ERRCODE_INSUFFICIENT_PRIVILEGE MAKE_SQLSTATE('4','2', '5','0','1') #define ERRCODE_CANNOT_COERCE MAKE_SQLSTATE('4','2', '8','4','6') #define ERRCODE_GROUPING_ERROR MAKE_SQLSTATE('4','2', '8','0','3') + #define ERRCODE_INVALID_RECURSION MAKE_SQLSTATE('4','2', 'P','1','9') #define ERRCODE_INVALID_FOREIGN_KEY MAKE_SQLSTATE('4','2', '8','3','0') #define ERRCODE_INVALID_NAME MAKE_SQLSTATE('4','2', '6','0','2') #define ERRCODE_NAME_TOO_LONG MAKE_SQLSTATE('4','2', '6','2','2') *** src/include/utils/tuplestore.h.orig Wed Oct 1 19:23:25 2008 --- src/include/utils/tuplestore.h Thu Oct 2 19:36:44 2008 *************** *** 74,79 **** --- 74,81 ---- extern void tuplestore_rescan(Tuplestorestate *state); + extern void tuplestore_clear(Tuplestorestate *state); + extern void tuplestore_end(Tuplestorestate *state); #endif /* TUPLESTORE_H */ *** src/interfaces/ecpg/preproc/preproc.y.orig Thu Sep 25 14:54:10 2008 --- src/interfaces/ecpg/preproc/preproc.y Thu Sep 25 14:56:45 2008 *************** *** 473,479 **** QUOTE ! READ REAL REASSIGN RECHECK REFERENCES REINDEX RELATIVE_P RELEASE RENAME REPEATABLE REPLACE REPLICA RESET RESTART RESTRICT RETURNING RETURNS REVOKE RIGHT ROLE ROLLBACK ROW ROWS RULE --- 473,479 ---- QUOTE ! READ REAL REASSIGN RECHECK RECURSIVE REFERENCES REINDEX RELATIVE_P RELEASE RENAME REPEATABLE REPLACE REPLICA RESET RESTART RESTRICT RETURNING RETURNS REVOKE RIGHT ROLE ROLLBACK ROW ROWS RULE *** src/pl/plpgsql/src/plerrcodes.h.orig Thu May 15 18:39:49 2008 --- src/pl/plpgsql/src/plerrcodes.h Tue Sep 30 10:37:26 2008 *************** *** 484,489 **** --- 484,493 ---- }, { + "invalid_recursion", ERRCODE_INVALID_RECURSION + }, + + { "invalid_foreign_key", ERRCODE_INVALID_FOREIGN_KEY }, *** src/test/regress/expected/recursive.out.orig Mon Sep 22 11:16:32 2008 --- src/test/regress/expected/recursive.out Fri Oct 3 15:35:51 2008 *************** *** 0 **** --- 1,610 ---- + CREATE TEMP TABLE department ( + id INTEGER PRIMARY KEY, -- department ID + parent_department INTEGER REFERENCES department, -- upper department ID + name TEXT -- department name + ); + NOTICE: CREATE TABLE / PRIMARY KEY will create implicit index "department_pkey" for table "department" + INSERT INTO department VALUES (0, NULL, 'ROOT'); + INSERT INTO department VALUES (1, 0, 'A'); + INSERT INTO department VALUES (2, 1, 'B'); + INSERT INTO department VALUES (3, 2, 'C'); + INSERT INTO department VALUES (4, 2, 'D'); + INSERT INTO department VALUES (5, 0, 'E'); + INSERT INTO department VALUES (6, 4, 'F'); + INSERT INTO department VALUES (7, 5, 'G'); + -- department structure represented here is as follows: + -- + -- ROOT-+->A-+->B-+->C + -- | | + -- | +->D-+->F + -- +->E-+->G + -- extract all departments under 'A'. Result should be A, B, C, D and F + WITH RECURSIVE subdepartment AS + ( + -- non recursive term + SELECT * FROM department WHERE name = 'A' + UNION ALL + -- recursive term + SELECT d.* FROM department AS d, subdepartment AS sd + WHERE d.parent_department = sd.id + ) + SELECT * FROM subdepartment ORDER BY name; + id | parent_department | name + ----+-------------------+------ + 1 | 0 | A + 2 | 1 | B + 3 | 2 | C + 4 | 2 | D + 6 | 4 | F + (5 rows) + + -- extract all departments under 'A' with "level" number + WITH RECURSIVE subdepartment(level, id, parent_department, name) AS + ( + -- non recursive term + SELECT 1, * FROM department WHERE name = 'A' + UNION ALL + -- recursive term + SELECT sd.level + 1, d.* FROM department AS d, subdepartment AS sd + WHERE d.parent_department = sd.id + ) + SELECT * FROM subdepartment ORDER BY name; + level | id | parent_department | name + -------+----+-------------------+------ + 1 | 1 | 0 | A + 2 | 2 | 1 | B + 3 | 3 | 2 | C + 3 | 4 | 2 | D + 4 | 6 | 4 | F + (5 rows) + + -- extract all departments under 'A' with "level" number. + -- Only shows 2 level or more + WITH RECURSIVE subdepartment(level, id, parent_department, name) AS + ( + -- non recursive term + SELECT 1, * FROM department WHERE name = 'A' + UNION ALL + -- recursive term + SELECT sd.level + 1, d.* FROM department AS d, subdepartment AS sd + WHERE d.parent_department = sd.id + ) + SELECT * FROM subdepartment WHERE level >= 2 ORDER BY name; + level | id | parent_department | name + -------+----+-------------------+------ + 2 | 2 | 1 | B + 3 | 3 | 2 | C + 3 | 4 | 2 | D + 4 | 6 | 4 | F + (4 rows) + + -- sum of 1..100 + WITH RECURSIVE t(n) AS ( + VALUES (1) + UNION ALL + SELECT n+1 + FROM t + WHERE n < 100 + ) + SELECT sum(n) FROM t; + sum + ------ + 5050 + (1 row) + + -- non recursive term only case: should return 1 row + WITH RECURSIVE subdepartment AS + ( + -- non recursive term + SELECT * FROM department WHERE name = 'A' + ) + SELECT * FROM subdepartment ORDER BY name; + id | parent_department | name + ----+-------------------+------ + 1 | 0 | A + (1 row) + + -- subquery + SELECT count(*) FROM ( + WITH RECURSIVE t(n) AS ( + SELECT 1 UNION ALL SELECT n + 1 FROM t WHERE n < 500 + ) + SELECT * FROM t) AS t WHERE n < ( + SELECT count(*) FROM ( + WITH RECURSIVE t(n) AS ( + SELECT 1 UNION ALL SELECT n + 1 FROM t WHERE n < 100 + ) + SELECT * FROM t WHERE n < 50000) as t WHERE n < 100); + count + ------- + 98 + (1 row) + + -- VIEW + CREATE TEMPORARY VIEW vsubdepartment AS + WITH RECURSIVE subdepartment AS + ( + -- non recursive term + SELECT * FROM department WHERE name = 'A' + UNION ALL + -- recursive term + SELECT d.* FROM department AS d, subdepartment AS sd + WHERE d.parent_department = sd.id + ) + SELECT * FROM subdepartment; + SELECT * FROM vsubdepartment ORDER BY name; + id | parent_department | name + ----+-------------------+------ + 1 | 0 | A + 2 | 1 | B + 3 | 2 | C + 4 | 2 | D + 6 | 4 | F + (5 rows) + + -- Check reverse listing + SELECT pg_get_viewdef('vsubdepartment'::regclass); + pg_get_viewdef + --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- + WITH RECURSIVE subdepartment AS (SELECT department.id, department.parent_department, department.name FROM department WHERE (department.name = 'A'::text) UNION ALL SELECT d.id, d.parent_department, d.name FROM department d, subdepartment sd WHERE (d.parent_department = sd.id)) SELECT subdepartment.id, subdepartment.parent_department, subdepartment.name FROM subdepartment; + (1 row) + + SELECT pg_get_viewdef('vsubdepartment'::regclass, true); + pg_get_viewdef + -------------------------------------------------------------------------------------------------------------------- + WITH RECURSIVE subdepartment AS ( SELECT department.id, department.parent_department, department.name + FROM department + WHERE department.name = 'A'::text + UNION ALL + SELECT d.id, d.parent_department, d.name + FROM department d, subdepartment sd + WHERE d.parent_department = sd.id) SELECT subdepartment.id, subdepartment.parent_department, subdepartment.name + FROM subdepartment; + (1 row) + + -- recursive term has UNION + WITH RECURSIVE t(i,j) AS ( + VALUES (1,2) + UNION ALL + SELECT t2.i, t.j+1 FROM + (SELECT 2 AS i UNION ALL SELECT 3 AS i) AS t2 + JOIN t ON (t2.i = t.i+1)) + SELECT * FROM t; + i | j + ---+--- + 1 | 2 + 2 | 3 + 3 | 4 + (3 rows) + + CREATE TEMPORARY TABLE tree( + id INTEGER PRIMARY KEY, + parent_id INTEGER REFERENCES tree(id) + ); + NOTICE: CREATE TABLE / PRIMARY KEY will create implicit index "tree_pkey" for table "tree" + INSERT INTO tree + VALUES (1, NULL), (2, 1), (3,1), (4,2), (5,2), (6,2), (7,3), (8,3), + (9,4), (10,4), (11,7), (12,7), (13,7), (14, 9), (15,11), (16,11); + -- + -- get all path from the "second level" node to leaf nodes + -- + WITH RECURSIVE t(id, path) AS ( + VALUES(1,ARRAY[NULL::integer]) + UNION ALL + SELECT tree.id, t.path || tree.id + FROM tree JOIN t ON (tree.parent_id = t.id) + ) + SELECT t1.*, t2.* FROM t AS t1 JOIN t AS t2 ON + (t1.path[1:2] = t2.path[1:2] AND + array_upper(t1.path,1) = 2 AND + array_upper(t2.path,1) > 2) + ORDER BY t1.id, t2.id; + id | path | id | path + ----+----------+----+------------------ + 2 | {NULL,2} | 4 | {NULL,2,4} + 2 | {NULL,2} | 5 | {NULL,2,5} + 2 | {NULL,2} | 6 | {NULL,2,6} + 2 | {NULL,2} | 9 | {NULL,2,4,9} + 2 | {NULL,2} | 10 | {NULL,2,4,10} + 2 | {NULL,2} | 14 | {NULL,2,4,9,14} + 3 | {NULL,3} | 7 | {NULL,3,7} + 3 | {NULL,3} | 8 | {NULL,3,8} + 3 | {NULL,3} | 11 | {NULL,3,7,11} + 3 | {NULL,3} | 12 | {NULL,3,7,12} + 3 | {NULL,3} | 13 | {NULL,3,7,13} + 3 | {NULL,3} | 15 | {NULL,3,7,11,15} + 3 | {NULL,3} | 16 | {NULL,3,7,11,16} + (13 rows) + + WITH RECURSIVE t(id, path) AS ( + VALUES(1,ARRAY[NULL::integer]) + UNION ALL + SELECT tree.id, t.path || tree.id + FROM tree JOIN t ON (tree.parent_id = t.id) + ) + SELECT t1.id, count(t2.*) FROM t AS t1 JOIN t AS t2 ON + (t1.path[1:2] = t2.path[1:2] AND + array_upper(t1.path,1) = 2 AND + array_upper(t2.path,1) > 2) + GROUP BY t1.id + ORDER BY t1.id; + id | count + ----+------- + 2 | 6 + 3 | 7 + (2 rows) + + -- + -- target list has a subquery + -- + WITH RECURSIVE t(id) AS ( + SELECT (VALUES(1)) + UNION ALL + SELECT id+1 FROM t WHERE id < 5 + ) + SELECT * FROM t; + id + ---- + 1 + 2 + 3 + 4 + 5 + (5 rows) + + -- + -- multiple query names + -- + WITH RECURSIVE + y (id) AS (VALUES (1)), + x (id) AS (SELECT * FROM y UNION ALL SELECT id+1 FROM x WHERE id < 5) + SELECT * FROM x; + id + ---- + 1 + 2 + 3 + 4 + 5 + (5 rows) + + WITH RECURSIVE + x(id) AS (SELECT * FROM y UNION ALL SELECT id+1 FROM x WHERE id < 5), + y(id) AS (values (1)) + SELECT * FROM x; + id + ---- + 1 + 2 + 3 + 4 + 5 + (5 rows) + + WITH RECURSIVE + x(id) AS + (VALUES (1) UNION ALL SELECT id+1 FROM x WHERE id < 5), + y(id) AS + (VALUES (1) UNION ALL SELECT id+1 FROM y WHERE id < 10) + SELECT y.*, x.* FROM y LEFT JOIN x USING (id); + id | id + ----+---- + 1 | 1 + 2 | 2 + 3 | 3 + 4 | 4 + 5 | 5 + 6 | + 7 | + 8 | + 9 | + 10 | + (10 rows) + + WITH RECURSIVE + x(id) AS + (VALUES (1) UNION ALL SELECT id+1 FROM x WHERE id < 5), + y(id) AS + (VALUES (1) UNION ALL SELECT id+1 FROM x WHERE id < 10) + SELECT y.*, x.* FROM y LEFT JOIN x USING (id); + id | id + ----+---- + 1 | 1 + 2 | 2 + 3 | 3 + 4 | 4 + 5 | 5 + 6 | + (6 rows) + + WITH RECURSIVE + x(id) AS + (SELECT 1 UNION ALL SELECT id+1 FROM x WHERE id < 3 ), + y(id) AS + (SELECT * FROM x UNION ALL SELECT * FROM x), + z(id) AS + (SELECT * FROM x UNION ALL SELECT id+1 FROM z WHERE id < 10) + SELECT * FROM z; + id + ---- + 1 + 2 + 3 + 2 + 3 + 4 + 3 + 4 + 5 + 4 + 5 + 6 + 5 + 6 + 7 + 6 + 7 + 8 + 7 + 8 + 9 + 8 + 9 + 10 + 9 + 10 + 10 + (27 rows) + + WITH RECURSIVE + x(id) AS + (SELECT 1 UNION ALL SELECT id+1 FROM x WHERE id < 3 ), + y(id) AS + (SELECT * FROM x UNION ALL SELECT * FROM x), + z(id) AS + (SELECT * FROM y UNION ALL SELECT id+1 FROM z WHERE id < 10) + SELECT * FROM z; + id + ---- + 1 + 2 + 3 + 1 + 2 + 3 + 2 + 3 + 4 + 2 + 3 + 4 + 3 + 4 + 5 + 3 + 4 + 5 + 4 + 5 + 6 + 4 + 5 + 6 + 5 + 6 + 7 + 5 + 6 + 7 + 6 + 7 + 8 + 6 + 7 + 8 + 7 + 8 + 9 + 7 + 8 + 9 + 8 + 9 + 10 + 8 + 9 + 10 + 9 + 10 + 9 + 10 + 10 + 10 + (54 rows) + + -- + -- error cases + -- + -- UNION + WITH RECURSIVE x(n) AS (SELECT 1 UNION SELECT n+1 FROM x) + SELECT * FROM x; + ERROR: recursive query "x" does not have the form non-recursive-term UNION ALL recursive-term + LINE 1: WITH RECURSIVE x(n) AS (SELECT 1 UNION SELECT n+1 FROM x) + ^ + -- INTERSECT + WITH RECURSIVE x(n) AS (SELECT 1 INTERSECT SELECT n+1 FROM x) + SELECT * FROM x; + ERROR: recursive query "x" does not have the form non-recursive-term UNION ALL recursive-term + LINE 1: WITH RECURSIVE x(n) AS (SELECT 1 INTERSECT SELECT n+1 FROM x... + ^ + WITH RECURSIVE x(n) AS (SELECT 1 INTERSECT ALL SELECT n+1 FROM x) + SELECT * FROM x; + ERROR: recursive query "x" does not have the form non-recursive-term UNION ALL recursive-term + LINE 1: WITH RECURSIVE x(n) AS (SELECT 1 INTERSECT ALL SELECT n+1 FR... + ^ + -- EXCEPT + WITH RECURSIVE x(n) AS (SELECT 1 EXCEPT SELECT n+1 FROM x) + SELECT * FROM x; + ERROR: recursive query "x" does not have the form non-recursive-term UNION ALL recursive-term + LINE 1: WITH RECURSIVE x(n) AS (SELECT 1 EXCEPT SELECT n+1 FROM x) + ^ + WITH RECURSIVE x(n) AS (SELECT 1 EXCEPT ALL SELECT n+1 FROM x) + SELECT * FROM x; + ERROR: recursive query "x" does not have the form non-recursive-term UNION ALL recursive-term + LINE 1: WITH RECURSIVE x(n) AS (SELECT 1 EXCEPT ALL SELECT n+1 FROM ... + ^ + -- no non-recursive term + WITH RECURSIVE x(n) AS (SELECT n FROM x) + SELECT * FROM x; + ERROR: recursive query "x" does not have the form non-recursive-term UNION ALL recursive-term + LINE 1: WITH RECURSIVE x(n) AS (SELECT n FROM x) + ^ + -- recursive term in the left hand side + WITH RECURSIVE x(n) AS (SELECT n FROM x UNION ALL SELECT 1) + SELECT * FROM x; + ERROR: recursive reference to query "x" must not appear within its non-recursive term + LINE 1: WITH RECURSIVE x(n) AS (SELECT n FROM x UNION ALL SELECT 1) + ^ + CREATE TEMPORARY TABLE y (a INTEGER); + INSERT INTO y SELECT generate_series(1, 10); + -- LEFT JOIN + WITH RECURSIVE x(n) AS (SELECT a FROM y WHERE a = 1 + UNION ALL + SELECT x.n+1 FROM y LEFT JOIN x ON x.n = y.a WHERE n < 10) + SELECT * FROM x; + ERROR: recursive reference to query "x" must not appear within an outer join + LINE 3: SELECT x.n+1 FROM y LEFT JOIN x ON x.n = y.a WHERE n < 10) + ^ + -- RIGHT JOIN + WITH RECURSIVE x(n) AS (SELECT a FROM y WHERE a = 1 + UNION ALL + SELECT x.n+1 FROM x RIGHT JOIN y ON x.n = y.a WHERE n < 10) + SELECT * FROM x; + ERROR: recursive reference to query "x" must not appear within an outer join + LINE 3: SELECT x.n+1 FROM x RIGHT JOIN y ON x.n = y.a WHERE n < 10) + ^ + -- FULL JOIN + WITH RECURSIVE x(n) AS (SELECT a FROM y WHERE a = 1 + UNION ALL + SELECT x.n+1 FROM x FULL JOIN y ON x.n = y.a WHERE n < 10) + SELECT * FROM x; + ERROR: recursive reference to query "x" must not appear within an outer join + LINE 3: SELECT x.n+1 FROM x FULL JOIN y ON x.n = y.a WHERE n < 10) + ^ + -- subquery + WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x + WHERE n IN (SELECT * FROM x)) + SELECT * FROM x; + ERROR: recursive reference to query "x" must not appear within a subquery + LINE 2: WHERE n IN (SELECT * FROM x)) + ^ + WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x + WHERE n = 1 AND n IN (SELECT * FROM x)) + SELECT * FROM x; + ERROR: recursive reference to query "x" must not appear within a subquery + LINE 2: ... WHERE n = 1 AND n IN (SELECT * FROM x)) + ^ + -- aggregate functions + WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT count(*) FROM x) + SELECT * FROM x; + ERROR: aggregates not allowed in a recursive query's recursive term + LINE 1: WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT count(*) F... + ^ + WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT sum(n) FROM x) + SELECT * FROM x; + ERROR: aggregates not allowed in a recursive query's recursive term + LINE 1: WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT sum(n) FRO... + ^ + -- ORDER BY + WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x ORDER BY 1) + SELECT * FROM x; + ERROR: ORDER BY in a recursive query is not implemented + LINE 1: ...VE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x ORDER BY 1) + ^ + -- LIMIT/OFFSET + WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x LIMIT 10 OFFSET 1) + SELECT * FROM x; + ERROR: OFFSET in a recursive query is not implemented + LINE 1: ... AS (SELECT 1 UNION ALL SELECT n+1 FROM x LIMIT 10 OFFSET 1) + ^ + -- FOR UPDATE + WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x FOR UPDATE) + SELECT * FROM x; + ERROR: FOR UPDATE/SHARE in a recursive query is not implemented + -- target list has a recursive query name + WITH RECURSIVE x(id) AS (values (1) + UNION ALL + SELECT (SELECT * FROM x) FROM x WHERE id < 5 + ) SELECT * FROM x; + ERROR: recursive reference to query "x" must not appear within a subquery + LINE 3: SELECT (SELECT * FROM x) FROM x WHERE id < 5 + ^ + -- mutual recursive query + WITH RECURSIVE + x (id) AS (SELECT 1 UNION ALL SELECT id+1 FROM y WHERE id < 5), + y (id) AS (SELECT 1 UNION ALL SELECT id+1 FROM x WHERE id < 5) + SELECT * FROM x; + ERROR: mutual recursion between WITH items is not supported + LINE 2: x (id) AS (SELECT 1 UNION ALL SELECT id+1 FROM y WHERE id ... + ^ + -- non-linear recursion is not allowed + WITH RECURSIVE foo(i) AS + (values (1) + UNION ALL + (SELECT i+1 FROM foo WHERE i < 10 + UNION ALL + SELECT i+1 FROM foo WHERE i < 5) + ) SELECT * FROM foo; + ERROR: recursive reference to query "foo" must not appear more than once + LINE 6: SELECT i+1 FROM foo WHERE i < 5) + ^ + WITH RECURSIVE foo(i) AS + (values (1) + UNION ALL + SELECT * FROM + (SELECT i+1 FROM foo WHERE i < 10 + UNION ALL + SELECT i+1 FROM foo WHERE i < 5) AS t + ) SELECT * FROM foo; + ERROR: recursive reference to query "foo" must not appear more than once + LINE 7: SELECT i+1 FROM foo WHERE i < 5) AS t + ^ + WITH RECURSIVE foo(i) AS + (values (1) + UNION ALL + (SELECT i+1 FROM foo WHERE i < 10 + EXCEPT + SELECT i+1 FROM foo WHERE i < 5) + ) SELECT * FROM foo; + ERROR: recursive reference to query "foo" must not appear within EXCEPT + LINE 6: SELECT i+1 FROM foo WHERE i < 5) + ^ + WITH RECURSIVE foo(i) AS + (values (1) + UNION ALL + (SELECT i+1 FROM foo WHERE i < 10 + INTERSECT + SELECT i+1 FROM foo WHERE i < 5) + ) SELECT * FROM foo; + ERROR: recursive reference to query "foo" must not appear more than once + LINE 6: SELECT i+1 FROM foo WHERE i < 5) + ^ + -- Wrong type induced from non-recursive term + WITH RECURSIVE foo(i) AS + (SELECT i FROM (VALUES(1),(2)) t(i) + UNION ALL + SELECT (i+1)::numeric(10,0) FROM foo WHERE i < 10) + SELECT * FROM foo; + ERROR: recursive query "foo" column 1 has type integer in non-recursive term but type numeric overall + LINE 2: (SELECT i FROM (VALUES(1),(2)) t(i) + ^ + HINT: Cast the output of the non-recursive term to the correct type. + WITH RECURSIVE foo(i) AS + (SELECT i::numeric(3,0) FROM (VALUES(1),(2)) t(i) + UNION ALL + SELECT (i+1)::numeric(10,0) FROM foo WHERE i < 10) + SELECT * FROM foo; + ERROR: recursive query "foo" column 1 has type numeric(3,0) in non-recursive term but type numeric overall + LINE 2: (SELECT i::numeric(3,0) FROM (VALUES(1),(2)) t(i) + ^ + HINT: Cast the output of the non-recursive term to the correct type. *** src/test/regress/parallel_schedule.orig Fri Oct 3 12:06:54 2008 --- src/test/regress/parallel_schedule Fri Oct 3 12:06:58 2008 *************** *** 83,89 **** # Another group of parallel tests # ---------- # "plpgsql" cannot run concurrently with "rules", nor can "plancache" ! test: plancache limit plpgsql copy2 temp domain rangefuncs prepare without_oid conversion truncate alter_table sequence polymorphism rowtypes returning largeobject xml # run stats by itself because its delay may be insufficient under heavy load test: stats --- 83,89 ---- # Another group of parallel tests # ---------- # "plpgsql" cannot run concurrently with "rules", nor can "plancache" ! test: plancache limit plpgsql copy2 temp domain rangefuncs prepare without_oid conversion truncate alter_table sequence polymorphism rowtypes returning largeobject xml recursive # run stats by itself because its delay may be insufficient under heavy load test: stats *** src/test/regress/serial_schedule.orig Fri Oct 3 12:06:54 2008 --- src/test/regress/serial_schedule Fri Oct 3 12:06:58 2008 *************** *** 115,119 **** --- 115,120 ---- test: returning test: largeobject test: xml + test: recursive test: stats test: tablespace *** src/test/regress/sql/recursive.sql.orig Mon Sep 22 11:16:32 2008 --- src/test/regress/sql/recursive.sql Fri Oct 3 15:35:22 2008 *************** *** 0 **** --- 1,354 ---- + CREATE TEMP TABLE department ( + id INTEGER PRIMARY KEY, -- department ID + parent_department INTEGER REFERENCES department, -- upper department ID + name TEXT -- department name + ); + + INSERT INTO department VALUES (0, NULL, 'ROOT'); + INSERT INTO department VALUES (1, 0, 'A'); + INSERT INTO department VALUES (2, 1, 'B'); + INSERT INTO department VALUES (3, 2, 'C'); + INSERT INTO department VALUES (4, 2, 'D'); + INSERT INTO department VALUES (5, 0, 'E'); + INSERT INTO department VALUES (6, 4, 'F'); + INSERT INTO department VALUES (7, 5, 'G'); + + -- department structure represented here is as follows: + -- + -- ROOT-+->A-+->B-+->C + -- | | + -- | +->D-+->F + -- +->E-+->G + + -- extract all departments under 'A'. Result should be A, B, C, D and F + WITH RECURSIVE subdepartment AS + ( + -- non recursive term + SELECT * FROM department WHERE name = 'A' + + UNION ALL + + -- recursive term + SELECT d.* FROM department AS d, subdepartment AS sd + WHERE d.parent_department = sd.id + ) + SELECT * FROM subdepartment ORDER BY name; + + -- extract all departments under 'A' with "level" number + WITH RECURSIVE subdepartment(level, id, parent_department, name) AS + ( + -- non recursive term + SELECT 1, * FROM department WHERE name = 'A' + + UNION ALL + + -- recursive term + SELECT sd.level + 1, d.* FROM department AS d, subdepartment AS sd + WHERE d.parent_department = sd.id + ) + SELECT * FROM subdepartment ORDER BY name; + + -- extract all departments under 'A' with "level" number. + -- Only shows 2 level or more + WITH RECURSIVE subdepartment(level, id, parent_department, name) AS + ( + -- non recursive term + SELECT 1, * FROM department WHERE name = 'A' + + UNION ALL + + -- recursive term + SELECT sd.level + 1, d.* FROM department AS d, subdepartment AS sd + WHERE d.parent_department = sd.id + ) + SELECT * FROM subdepartment WHERE level >= 2 ORDER BY name; + + -- sum of 1..100 + WITH RECURSIVE t(n) AS ( + VALUES (1) + UNION ALL + SELECT n+1 + FROM t + WHERE n < 100 + ) + SELECT sum(n) FROM t; + + -- non recursive term only case: should return 1 row + WITH RECURSIVE subdepartment AS + ( + -- non recursive term + SELECT * FROM department WHERE name = 'A' + ) + SELECT * FROM subdepartment ORDER BY name; + + -- subquery + SELECT count(*) FROM ( + WITH RECURSIVE t(n) AS ( + SELECT 1 UNION ALL SELECT n + 1 FROM t WHERE n < 500 + ) + SELECT * FROM t) AS t WHERE n < ( + SELECT count(*) FROM ( + WITH RECURSIVE t(n) AS ( + SELECT 1 UNION ALL SELECT n + 1 FROM t WHERE n < 100 + ) + SELECT * FROM t WHERE n < 50000) as t WHERE n < 100); + + -- VIEW + CREATE TEMPORARY VIEW vsubdepartment AS + WITH RECURSIVE subdepartment AS + ( + -- non recursive term + SELECT * FROM department WHERE name = 'A' + UNION ALL + -- recursive term + SELECT d.* FROM department AS d, subdepartment AS sd + WHERE d.parent_department = sd.id + ) + SELECT * FROM subdepartment; + + SELECT * FROM vsubdepartment ORDER BY name; + + -- Check reverse listing + SELECT pg_get_viewdef('vsubdepartment'::regclass); + SELECT pg_get_viewdef('vsubdepartment'::regclass, true); + + -- recursive term has UNION + WITH RECURSIVE t(i,j) AS ( + VALUES (1,2) + UNION ALL + SELECT t2.i, t.j+1 FROM + (SELECT 2 AS i UNION ALL SELECT 3 AS i) AS t2 + JOIN t ON (t2.i = t.i+1)) + + SELECT * FROM t; + + CREATE TEMPORARY TABLE tree( + id INTEGER PRIMARY KEY, + parent_id INTEGER REFERENCES tree(id) + ); + + INSERT INTO tree + VALUES (1, NULL), (2, 1), (3,1), (4,2), (5,2), (6,2), (7,3), (8,3), + (9,4), (10,4), (11,7), (12,7), (13,7), (14, 9), (15,11), (16,11); + + -- + -- get all path from the "second level" node to leaf nodes + -- + WITH RECURSIVE t(id, path) AS ( + VALUES(1,ARRAY[NULL::integer]) + UNION ALL + SELECT tree.id, t.path || tree.id + FROM tree JOIN t ON (tree.parent_id = t.id) + ) + SELECT t1.*, t2.* FROM t AS t1 JOIN t AS t2 ON + (t1.path[1:2] = t2.path[1:2] AND + array_upper(t1.path,1) = 2 AND + array_upper(t2.path,1) > 2) + ORDER BY t1.id, t2.id; + + WITH RECURSIVE t(id, path) AS ( + VALUES(1,ARRAY[NULL::integer]) + UNION ALL + SELECT tree.id, t.path || tree.id + FROM tree JOIN t ON (tree.parent_id = t.id) + ) + SELECT t1.id, count(t2.*) FROM t AS t1 JOIN t AS t2 ON + (t1.path[1:2] = t2.path[1:2] AND + array_upper(t1.path,1) = 2 AND + array_upper(t2.path,1) > 2) + GROUP BY t1.id + ORDER BY t1.id; + + -- + -- target list has a subquery + -- + WITH RECURSIVE t(id) AS ( + SELECT (VALUES(1)) + UNION ALL + SELECT id+1 FROM t WHERE id < 5 + ) + SELECT * FROM t; + + -- + -- multiple query names + -- + WITH RECURSIVE + y (id) AS (VALUES (1)), + x (id) AS (SELECT * FROM y UNION ALL SELECT id+1 FROM x WHERE id < 5) + SELECT * FROM x; + + WITH RECURSIVE + x(id) AS (SELECT * FROM y UNION ALL SELECT id+1 FROM x WHERE id < 5), + y(id) AS (values (1)) + SELECT * FROM x; + + WITH RECURSIVE + x(id) AS + (VALUES (1) UNION ALL SELECT id+1 FROM x WHERE id < 5), + y(id) AS + (VALUES (1) UNION ALL SELECT id+1 FROM y WHERE id < 10) + SELECT y.*, x.* FROM y LEFT JOIN x USING (id); + + WITH RECURSIVE + x(id) AS + (VALUES (1) UNION ALL SELECT id+1 FROM x WHERE id < 5), + y(id) AS + (VALUES (1) UNION ALL SELECT id+1 FROM x WHERE id < 10) + SELECT y.*, x.* FROM y LEFT JOIN x USING (id); + + WITH RECURSIVE + x(id) AS + (SELECT 1 UNION ALL SELECT id+1 FROM x WHERE id < 3 ), + y(id) AS + (SELECT * FROM x UNION ALL SELECT * FROM x), + z(id) AS + (SELECT * FROM x UNION ALL SELECT id+1 FROM z WHERE id < 10) + SELECT * FROM z; + + WITH RECURSIVE + x(id) AS + (SELECT 1 UNION ALL SELECT id+1 FROM x WHERE id < 3 ), + y(id) AS + (SELECT * FROM x UNION ALL SELECT * FROM x), + z(id) AS + (SELECT * FROM y UNION ALL SELECT id+1 FROM z WHERE id < 10) + SELECT * FROM z; + + -- + -- error cases + -- + + -- UNION + WITH RECURSIVE x(n) AS (SELECT 1 UNION SELECT n+1 FROM x) + SELECT * FROM x; + + -- INTERSECT + WITH RECURSIVE x(n) AS (SELECT 1 INTERSECT SELECT n+1 FROM x) + SELECT * FROM x; + + WITH RECURSIVE x(n) AS (SELECT 1 INTERSECT ALL SELECT n+1 FROM x) + SELECT * FROM x; + + -- EXCEPT + WITH RECURSIVE x(n) AS (SELECT 1 EXCEPT SELECT n+1 FROM x) + SELECT * FROM x; + + WITH RECURSIVE x(n) AS (SELECT 1 EXCEPT ALL SELECT n+1 FROM x) + SELECT * FROM x; + + -- no non-recursive term + WITH RECURSIVE x(n) AS (SELECT n FROM x) + SELECT * FROM x; + + -- recursive term in the left hand side + WITH RECURSIVE x(n) AS (SELECT n FROM x UNION ALL SELECT 1) + SELECT * FROM x; + + CREATE TEMPORARY TABLE y (a INTEGER); + INSERT INTO y SELECT generate_series(1, 10); + + -- LEFT JOIN + + WITH RECURSIVE x(n) AS (SELECT a FROM y WHERE a = 1 + UNION ALL + SELECT x.n+1 FROM y LEFT JOIN x ON x.n = y.a WHERE n < 10) + SELECT * FROM x; + + -- RIGHT JOIN + WITH RECURSIVE x(n) AS (SELECT a FROM y WHERE a = 1 + UNION ALL + SELECT x.n+1 FROM x RIGHT JOIN y ON x.n = y.a WHERE n < 10) + SELECT * FROM x; + + -- FULL JOIN + WITH RECURSIVE x(n) AS (SELECT a FROM y WHERE a = 1 + UNION ALL + SELECT x.n+1 FROM x FULL JOIN y ON x.n = y.a WHERE n < 10) + SELECT * FROM x; + + -- subquery + WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x + WHERE n IN (SELECT * FROM x)) + SELECT * FROM x; + + WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x + WHERE n = 1 AND n IN (SELECT * FROM x)) + SELECT * FROM x; + + -- aggregate functions + WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT count(*) FROM x) + SELECT * FROM x; + + WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT sum(n) FROM x) + SELECT * FROM x; + + -- ORDER BY + WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x ORDER BY 1) + SELECT * FROM x; + + -- LIMIT/OFFSET + WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x LIMIT 10 OFFSET 1) + SELECT * FROM x; + + -- FOR UPDATE + WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x FOR UPDATE) + SELECT * FROM x; + + -- target list has a recursive query name + WITH RECURSIVE x(id) AS (values (1) + UNION ALL + SELECT (SELECT * FROM x) FROM x WHERE id < 5 + ) SELECT * FROM x; + + -- mutual recursive query + WITH RECURSIVE + x (id) AS (SELECT 1 UNION ALL SELECT id+1 FROM y WHERE id < 5), + y (id) AS (SELECT 1 UNION ALL SELECT id+1 FROM x WHERE id < 5) + SELECT * FROM x; + + -- non-linear recursion is not allowed + WITH RECURSIVE foo(i) AS + (values (1) + UNION ALL + (SELECT i+1 FROM foo WHERE i < 10 + UNION ALL + SELECT i+1 FROM foo WHERE i < 5) + ) SELECT * FROM foo; + + WITH RECURSIVE foo(i) AS + (values (1) + UNION ALL + SELECT * FROM + (SELECT i+1 FROM foo WHERE i < 10 + UNION ALL + SELECT i+1 FROM foo WHERE i < 5) AS t + ) SELECT * FROM foo; + + WITH RECURSIVE foo(i) AS + (values (1) + UNION ALL + (SELECT i+1 FROM foo WHERE i < 10 + EXCEPT + SELECT i+1 FROM foo WHERE i < 5) + ) SELECT * FROM foo; + + WITH RECURSIVE foo(i) AS + (values (1) + UNION ALL + (SELECT i+1 FROM foo WHERE i < 10 + INTERSECT + SELECT i+1 FROM foo WHERE i < 5) + ) SELECT * FROM foo; + + -- Wrong type induced from non-recursive term + WITH RECURSIVE foo(i) AS + (SELECT i FROM (VALUES(1),(2)) t(i) + UNION ALL + SELECT (i+1)::numeric(10,0) FROM foo WHERE i < 10) + SELECT * FROM foo; + + WITH RECURSIVE foo(i) AS + (SELECT i::numeric(3,0) FROM (VALUES(1),(2)) t(i) + UNION ALL + SELECT (i+1)::numeric(10,0) FROM foo WHERE i < 10) + SELECT * FROM foo;