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

*** doc/src/sgml/ref/select.sgml.orig Fri Feb 15 17:17:06 2008 --- doc/src/sgml/ref/select.sgml Mon Sep 22 11:16:32 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 ) *************** *** 842,847 **** --- 847,876 ---- + + <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). + + + *************** *** 1107,1112 **** --- 1136,1194 ---- 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 Mon Sep 22 19:54:38 2008 *************** *** 429,434 **** --- 429,437 ---- case T_Append: pname = "Append"; break; + case T_Recursion: + pname = "Recursion"; + break; case T_BitmapAnd: pname = "BitmapAnd"; break; *************** *** 537,542 **** --- 540,548 ---- case T_ValuesScan: pname = "Values Scan"; break; + case T_RecursiveScan: + pname = "Recursive Scan"; + break; case T_Material: pname = "Materialize"; break; *************** *** 721,726 **** --- 727,749 ---- quote_identifier(valsname)); } break; + case T_Recursion: + case T_RecursiveScan: + if (((Scan *) plan)->scanrelid > 0) + { + RangeTblEntry *rte = rt_fetch(((Scan *) plan)->scanrelid, + es->rtable); + char *valsname; + + /* Assert it's on a recursive rte */ + Assert(rte->rtekind == RTE_CTE); + + valsname = rte->eref->aliasname; + + appendStringInfo(str, " on %s", + quote_identifier(valsname)); + } + break; default: break; } *************** *** 787,792 **** --- 810,817 ---- case T_SeqScan: case T_FunctionScan: case T_ValuesScan: + case T_RecursiveScan: + case T_Recursion: show_scan_qual(plan->qual, "Filter", ((Scan *) plan)->scanrelid, *************** *** 1028,1033 **** --- 1053,1074 ---- indent + 3, es); } + if (IsA(plan, Recursion)) + { + Recursion *subqueryscan = (Recursion *) plan; + RecursionState *subquerystate = (RecursionState *) planstate; + Plan *subnode = subqueryscan->subplan; + + for (i = 0; i < indent; i++) + appendStringInfo(str, " "); + appendStringInfo(str, " -> "); + + explain_outNode(str, subnode, + subquerystate->subplan, + NULL, + indent + 3, es); + } + /* subPlan-s */ if (planstate->subPlan) { *** src/backend/executor/Makefile.orig Tue Feb 19 05:30:07 2008 --- src/backend/executor/Makefile Mon Sep 22 11:16:32 2008 *************** *** 18,25 **** 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 --- 18,25 ---- nodeBitmapAnd.o nodeBitmapOr.o \ nodeBitmapHeapscan.o nodeBitmapIndexscan.o nodeHash.o \ nodeHashjoin.o nodeIndexscan.o nodeMaterial.o nodeMergejoin.o \ ! nodeNestloop.o nodeFunctionscan.o nodeResult.o nodeRecursion.o \ ! nodeRecursivescan.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 *** src/backend/executor/execAmi.c.orig Tue Aug 5 17:28:29 2008 --- src/backend/executor/execAmi.c Mon Sep 22 11:16:32 2008 *************** *** 30,35 **** --- 30,37 ---- #include "executor/nodeMaterial.h" #include "executor/nodeMergejoin.h" #include "executor/nodeNestloop.h" + #include "executor/nodeRecursion.h" + #include "executor/nodeRecursivescan.h" #include "executor/nodeResult.h" #include "executor/nodeSeqscan.h" #include "executor/nodeSetOp.h" *************** *** 161,166 **** --- 163,176 ---- ExecValuesReScan((ValuesScanState *) node, exprCtxt); break; + case T_RecursionState: + ExecRecursionReScan((RecursionState *) node, exprCtxt); + break; + + case T_RecursiveScanState: + ExecRecursiveScanReScan((RecursiveScanState *) node, exprCtxt); + break; + case T_NestLoopState: ExecReScanNestLoop((NestLoopState *) node, exprCtxt); break; *************** *** 247,252 **** --- 257,266 ---- ExecValuesMarkPos((ValuesScanState *) node); break; + case T_RecursiveScanState: + ExecRecursiveScanMarkPos((RecursiveScanState *) node); + break; + case T_MaterialState: ExecMaterialMarkPos((MaterialState *) node); break; *************** *** 304,309 **** --- 318,327 ---- ExecValuesRestrPos((ValuesScanState *) node); break; + case T_RecursiveScanState: + ExecRecursiveScanRestrPos((RecursiveScanState *) node); + break; + case T_MaterialState: ExecMaterialRestrPos((MaterialState *) node); break; *** src/backend/executor/execProcnode.c.orig Tue Jan 1 14:45:49 2008 --- src/backend/executor/execProcnode.c Mon Sep 22 11:16:32 2008 *************** *** 94,99 **** --- 94,101 ---- #include "executor/nodeMaterial.h" #include "executor/nodeMergejoin.h" #include "executor/nodeNestloop.h" + #include "executor/nodeRecursion.h" + #include "executor/nodeRecursivescan.h" #include "executor/nodeResult.h" #include "executor/nodeSeqscan.h" #include "executor/nodeSetOp.h" *************** *** 147,152 **** --- 149,159 ---- estate, eflags); break; + case T_Recursion: + result = (PlanState *) ExecInitRecursion((Recursion *) node, + estate, eflags); + break; + case T_BitmapAnd: result = (PlanState *) ExecInitBitmapAnd((BitmapAnd *) node, estate, eflags); *************** *** 200,205 **** --- 207,217 ---- estate, eflags); break; + case T_RecursiveScan: + result = (PlanState *) ExecInitRecursiveScan((RecursiveScan *) node, + estate, eflags); + break; + /* * join nodes */ *************** *** 323,328 **** --- 335,344 ---- result = ExecAppend((AppendState *) node); break; + case T_RecursionState: + result = ExecRecursion((RecursionState *) node); + break; + /* BitmapAndState does not yield tuples */ /* BitmapOrState does not yield tuples */ *************** *** 360,365 **** --- 376,385 ---- result = ExecValuesScan((ValuesScanState *) node); break; + case T_RecursiveScanState: + result = ExecRecursiveScan((RecursiveScanState *) node); + break; + /* * join nodes */ *************** *** 507,512 **** --- 527,535 ---- case T_BitmapOr: return ExecCountSlotsBitmapOr((BitmapOr *) node); + case T_Recursion: + return ExecCountSlotsRecursion((Recursion *) node); + /* * scan nodes */ *************** *** 534,539 **** --- 557,565 ---- case T_ValuesScan: return ExecCountSlotsValuesScan((ValuesScan *) node); + case T_RecursiveScan: + return ExecCountSlotsRecursiveScan((RecursiveScan *) node); + /* * join nodes */ *************** *** 620,625 **** --- 646,655 ---- ExecEndAppend((AppendState *) node); break; + case T_RecursionState: + ExecEndRecursion((RecursionState *) node); + break; + case T_BitmapAndState: ExecEndBitmapAnd((BitmapAndState *) node); break; *************** *** 663,668 **** --- 693,702 ---- ExecEndValuesScan((ValuesScanState *) node); break; + case T_RecursiveScanState: + ExecEndRecursiveScan((RecursiveScanState *) node); + break; + /* * join nodes */ *** src/backend/executor/nodeAgg.c.orig Sun Sep 7 20:22:55 2008 --- src/backend/executor/nodeAgg.c Mon Sep 22 11:16:32 2008 *************** *** 1263,1268 **** --- 1263,1269 ---- eflags &= ~EXEC_FLAG_REWIND; outerPlan = outerPlan(node); outerPlanState(aggstate) = ExecInitNode(outerPlan, estate, eflags); + aggstate->ss.ps.has_recursivescan = (outerPlanState(aggstate))->has_recursivescan; /* * initialize source tuple type. *************** *** 1648,1658 **** return; /* ! * If we do have the hash table and the subplan does not have any ! * parameter changes, then we can just rescan the existing hash table; ! * no need to build it again. */ ! if (((PlanState *) node)->lefttree->chgParam == NULL) { ResetTupleHashIterator(node->hashtable, &node->hashiter); return; --- 1649,1661 ---- return; /* ! * If we do have the hash table and the subplan does not have ! * any parameter changes nor have Recursive Scan plan, then we ! * can just rescan the existing hash table; no need to build ! * it again. */ ! if (((PlanState *) node)->lefttree->chgParam == NULL && ! ((PlanState *) node)->lefttree->has_recursivescan == false) { ResetTupleHashIterator(node->hashtable, &node->hashiter); return; *** src/backend/executor/nodeAppend.c.orig Tue Jan 1 14:45:49 2008 --- src/backend/executor/nodeAppend.c Mon Sep 22 11:16:32 2008 *************** *** 60,67 **** #include "executor/execdebug.h" #include "executor/nodeAppend.h" - static bool exec_append_initialize_next(AppendState *appendstate); - /* ---------------------------------------------------------------- * exec_append_initialize_next --- 60,65 ---- *************** *** 71,77 **** * Returns t iff there is a "next" scan to process. * ---------------------------------------------------------------- */ ! static bool exec_append_initialize_next(AppendState *appendstate) { EState *estate; --- 69,75 ---- * Returns t iff there is a "next" scan to process. * ---------------------------------------------------------------- */ ! bool exec_append_initialize_next(AppendState *appendstate) { EState *estate; *************** *** 145,154 **** --- 143,156 ---- int nplans; int i; Plan *initNode; + TupleDesc save_tupledesc; /* check for unsupported flags */ Assert(!(eflags & EXEC_FLAG_MARK)); + /* Save tuple desc */ + save_tupledesc = estate->es_rscan_tupledesc; + /* * Set up empty vector of subplan states */ *************** *** 213,218 **** --- 215,224 ---- initNode = (Plan *) list_nth(node->appendplans, i); appendplanstates[i] = ExecInitNode(initNode, estate, eflags); + + /* save result type for RecursiveScan plan node. */ + if (i == appendstate->as_firstplan) + estate->es_rscan_tupledesc = ExecGetResultType(appendplanstates[i]); } /* *************** *** 230,235 **** --- 236,244 ---- appendstate->as_whichplan = appendstate->as_firstplan; exec_append_initialize_next(appendstate); + /* Restore tuple desc */ + estate->es_rscan_tupledesc = save_tupledesc; + return appendstate; } *** src/backend/executor/nodeHash.c.orig Tue Jan 1 14:45:49 2008 --- src/backend/executor/nodeHash.c Mon Sep 22 11:16:32 2008 *************** *** 169,174 **** --- 169,175 ---- * initialize child nodes */ outerPlanState(hashstate) = ExecInitNode(outerPlan(node), estate, eflags); + hashstate->ps.has_recursivescan = (outerPlanState(hashstate))->has_recursivescan; /* * initialize tuple type. no need to initialize projection info because *** src/backend/executor/nodeHashjoin.c.orig Fri Aug 15 15:20:42 2008 --- src/backend/executor/nodeHashjoin.c Mon Sep 22 11:16:32 2008 *************** *** 848,854 **** if (node->hj_HashTable != NULL) { if (node->hj_HashTable->nbatch == 1 && ! ((PlanState *) node)->righttree->chgParam == NULL) { /* * okay to reuse the hash table; needn't rescan inner, either. --- 848,855 ---- if (node->hj_HashTable != NULL) { if (node->hj_HashTable->nbatch == 1 && ! ((PlanState *) node)->righttree->chgParam == NULL && ! ((PlanState *) node)->righttree->has_recursivescan == false) { /* * okay to reuse the hash table; needn't rescan inner, either. *** src/backend/executor/nodeRecursion.c.orig Mon Sep 22 11:16:32 2008 --- src/backend/executor/nodeRecursion.c Mon Sep 22 11:16:32 2008 *************** *** 0 **** --- 1,276 ---- + /*------------------------------------------------------------------------- + * + * nodeRecursion.c + * routines to handle Recursion 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/instrument.h" + #include "executor/nodeAppend.h" + #include "executor/nodeRecursion.h" + #include "miscadmin.h" + + /* ---------------------------------------------------------------- + * RecursionNext + * + * This is a workhorse for ExecRecursion + * ---------------------------------------------------------------- + * * + * 1. evaluate non recursive term or partition depending on other + * partitions 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 + */ + static TupleTableSlot *RecursionNext(RecursionState *node) + { + TupleTableSlot *slot; + AppendState *appendstate; + Tuplestorestate *tmp; + + Assert(node->subplan->type == T_AppendState); + + appendstate = (AppendState *) node->subplan; + + /* 1. Evaluate non recursive plan */ + while (appendstate->as_whichplan != appendstate->as_lastplan) + { + slot = ExecProcNode(appendstate->appendplans[appendstate->as_whichplan]); + if (!TupIsNull(slot)) + { + tuplestore_puttupleslot(node->working_table, slot); + return slot; + } + appendstate->as_whichplan++; + if (!exec_append_initialize_next(appendstate)) + return ExecClearTuple(appendstate->ps.ps_ResultTupleSlot); + } + + retry: + /* 2. Execute recursive plan */ + slot = ExecProcNode(appendstate->appendplans[appendstate->as_whichplan]); + if (TupIsNull(slot)) + { + if (node->recursive_empty == false) + { + tmp = node->working_table; + node->working_table = node->intermediate_tuplestorestate; + node->intermediate_tuplestorestate = tmp; + + /* Re-create intermediate table */ + tuplestore_end(node->intermediate_tuplestorestate); + node->intermediate_tuplestorestate = tuplestore_begin_heap(true, false, 0); + + node->recursive_empty = true; + ExecReScan(appendstate->appendplans[appendstate->as_whichplan], NULL); + goto retry; + } + else if (!exec_append_initialize_next(appendstate)) + return ExecClearTuple(appendstate->ps.ps_ResultTupleSlot); + } + + else + { + node->recursive_empty = false; + tuplestore_puttupleslot(node->intermediate_tuplestorestate, slot); + } + + return slot; + } + + /* ---------------------------------------------------------------- + * ExecRecursion(node) + * + * Scans the recursive query sequentially and returns the next + * qualifying tuple. + * It calls the ExecScan() routine and passes it the access method + * which retrieve tuples sequentially. + * + */ + TupleTableSlot * + ExecRecursion(RecursionState *node) + { + /* + * use RecursivescanNext as access method + */ + return ExecScan(&node->ss, (ExecScanAccessMtd) RecursionNext); + } + + /* ---------------------------------------------------------------- + * ExecInitRecursionScan + * ---------------------------------------------------------------- + */ + RecursionState * + ExecInitRecursion(Recursion *node, EState *estate, int eflags) + { + RecursionState *recursionstate; + Tuplestorestate **save_tuplestorestate; + + /* check for unsupported flags */ + Assert(!(eflags & EXEC_FLAG_MARK)); + + /* + * SubqueryScan should not have any "normal" children. Also, if planner + * left anything in subrtable, it's fishy. + */ + Assert(outerPlan(node) == NULL); + Assert(innerPlan(node) == NULL); + Assert(node->subrtable == NIL); + + /* + * create state structure + */ + recursionstate = makeNode(RecursionState); + recursionstate->ss.ps.plan = (Plan *) node; + recursionstate->ss.ps.state = estate; + recursionstate->recursive_empty = true; + recursionstate->working_table = tuplestore_begin_heap(true, false, work_mem); + recursionstate->intermediate_tuplestorestate = tuplestore_begin_heap(true, false, work_mem); + + /* + * Save the reference for the working table to share + */ + save_tuplestorestate = estate->es_tuplestorestate; + estate->es_tuplestorestate = &recursionstate->working_table; + + /* + * Miscellaneous initialization + * + * create expression context for node + */ + ExecAssignExprContext(estate, &recursionstate->ss.ps); + + /* + * initialize child expressions + */ + recursionstate->ss.ps.targetlist = (List *) + ExecInitExpr((Expr *) node->scan.plan.targetlist, + (PlanState *) recursionstate); + recursionstate->ss.ps.qual = (List *) + ExecInitExpr((Expr *) node->scan.plan.qual, + (PlanState *) recursionstate); + + #define RECURSION_NSLOTS 2 + + /* + * tuple table initialization + */ + ExecInitResultTupleSlot(estate, &recursionstate->ss.ps); + ExecInitScanTupleSlot(estate, &recursionstate->ss); + + /* + * initialize subquery + */ + recursionstate->subplan = ExecInitNode(node->subplan, estate, eflags); + + recursionstate->ss.ps.ps_TupFromTlist = false; + + /* + * Initialize scan tuple type (needed by ExecAssignScanProjectionInfo) + */ + ExecAssignScanType(&recursionstate->ss, + ExecGetResultType(recursionstate->subplan)); + + /* + * Initialize result tuple type and projection info. + */ + ExecAssignResultTypeFromTL(&recursionstate->ss.ps); + ExecAssignScanProjectionInfo(&recursionstate->ss); + + /* Restore tuplestore */ + estate->es_tuplestorestate = save_tuplestorestate; + + return recursionstate; + } + + int + ExecCountSlotsRecursion(Recursion *node) + { + Assert(outerPlan(node) == NULL); + Assert(innerPlan(node) == NULL); + return ExecCountSlotsNode(node->subplan) + + RECURSION_NSLOTS; + } + + /* ---------------------------------------------------------------- + * ExecEndRecursionScan + * + * frees any storage allocated through C routines. + * ---------------------------------------------------------------- + */ + void + ExecEndRecursion(RecursionState *node) + { + if (node->intermediate_tuplestorestate != NULL) + tuplestore_end(node->intermediate_tuplestorestate); + node->intermediate_tuplestorestate = NULL; + + if (node->working_table != NULL) + tuplestore_end(node->working_table); + node->working_table = NULL; + + /* + * Free the exprcontext + */ + ExecFreeExprContext(&node->ss.ps); + + /* + * clean out the upper tuple table + */ + ExecClearTuple(node->ss.ps.ps_ResultTupleSlot); + node->ss.ss_ScanTupleSlot = NULL; /* not ours to clear */ + + /* + * close down subquery + */ + ExecEndNode(node->subplan); + } + + /* ---------------------------------------------------------------- + * ExecRecursionReScan + * + * Rescans the relation. + * ---------------------------------------------------------------- + */ + void + ExecRecursionReScan(RecursionState *node, ExprContext *exprCtxt) + { + EState *estate; + + estate = node->ss.ps.state; + + /* + * ExecReScan doesn't know about my subplan, so I have to do + * changed-parameter signaling myself. This is just as well, because the + * subplan has its own memory context in which its chgParam state lives. + */ + if (node->ss.ps.chgParam != NULL) + UpdateChangedParamSet(node->subplan, node->ss.ps.chgParam); + + /* + * if chgParam of subnode is not null then plan will be re-scanned by + * first ExecProcNode. + */ + if (node->subplan->chgParam == NULL) + ExecReScan(node->subplan, NULL); + + node->ss.ss_ScanTupleSlot = NULL; + node->ss.ps.ps_TupFromTlist = false; + } *** src/backend/executor/nodeRecursivescan.c.orig Mon Sep 22 11:16:32 2008 --- src/backend/executor/nodeRecursivescan.c Mon Sep 22 11:16:32 2008 *************** *** 0 **** --- 1,194 ---- + /*------------------------------------------------------------------------- + * + * nodeRecursivescan.c + * routines to handle RecursiveScan 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/executor.h" + #include "executor/instrument.h" + #include "executor/nodeRecursivescan.h" + #include "miscadmin.h" + #include "utils/memutils.h" + + static TupleTableSlot *RecursivescanNext(RecursiveScanState *node); + + static TupleTableSlot * + RecursivescanNext(RecursiveScanState *node) + { + Tuplestorestate *tuplestorestate; + TupleTableSlot *slot; + + tuplestorestate = *node->working_table; + + slot = node->ss.ss_ScanTupleSlot; + if (tuplestore_gettupleslot(tuplestorestate, true, slot)) + return slot; + + return NULL; + } + + TupleTableSlot * + ExecRecursiveScan(RecursiveScanState *node) + { + /* + * use RecursivescanNext as access method + */ + return ExecScan(&node->ss, (ExecScanAccessMtd) RecursivescanNext); + } + + + /* ---------------------------------------------------------------- + * ExecInitRecursiveScan + * ---------------------------------------------------------------- + */ + RecursiveScanState * + ExecInitRecursiveScan(RecursiveScan *node, EState *estate, int eflags) + { + RecursiveScanState *scanstate; + + /* + * create new RecursiveScanState for node + */ + scanstate = makeNode(RecursiveScanState); + scanstate->ss.ps.plan = (Plan *) node; + scanstate->ss.ps.state = estate; + scanstate->ss.ps.has_recursivescan = true; + scanstate->working_table = estate->es_tuplestorestate; + + /* + * 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 RECURSIVESCAN_NSLOTS 2 + + /* + * tuple table initialization + */ + ExecInitResultTupleSlot(estate, &scanstate->ss.ps); + ExecInitScanTupleSlot(estate, &scanstate->ss); + + scanstate->ss.ps.ps_TupFromTlist = false; + + /* + * Do not initialize scan tuple type, result tuple type and + * projection info in ExecInitRecursivescan. These types are + * initialized after initializing Recursion node. + */ + ExecAssignScanType(&scanstate->ss, + estate->es_rscan_tupledesc); + + /* + * Initialize result tuple type and projection info. + */ + ExecAssignResultTypeFromTL(&scanstate->ss.ps); + ExecAssignScanProjectionInfo(&scanstate->ss); + + return scanstate; + } + + int + ExecCountSlotsRecursiveScan(RecursiveScan *node) + { + return ExecCountSlotsNode(outerPlan(node)) + + ExecCountSlotsNode(innerPlan(node)) + + RECURSIVESCAN_NSLOTS; + } + + /* ---------------------------------------------------------------- + * ExecEndRecursiveScan + * + * frees any storage allocated through C routines. + * ---------------------------------------------------------------- + */ + void + ExecEndRecursiveScan(RecursiveScanState *node) + { + /* + * Free both exprcontexts + */ + ExecFreeExprContext(&node->ss.ps); + ExecFreeExprContext(&node->ss.ps); + + /* + * clean out the tuple table + */ + ExecClearTuple(node->ss.ps.ps_ResultTupleSlot); + ExecClearTuple(node->ss.ss_ScanTupleSlot); + } + + /* ---------------------------------------------------------------- + * ExecRecursiveScanMarkPos + * + * Marks scan position. + * ---------------------------------------------------------------- + */ + void + ExecRecursiveScanMarkPos(RecursiveScanState *node) + { + /* + * if we haven't materialized yet, just return. + */ + if (!(*node->working_table)) + return; + + tuplestore_markpos(*node->working_table); + } + + /* ---------------------------------------------------------------- + * ExecRecursiveScanRestrPos + * + * Restores scan position. + * ---------------------------------------------------------------- + */ + void + ExecRecursiveScanRestrPos(RecursiveScanState *node) + { + /* + * if we haven't materialized yet, just return. + */ + if (!(*node->working_table)) + return; + + /* + * restore the scan to the previously marked position + */ + tuplestore_restorepos(*node->working_table); + } + + /* ---------------------------------------------------------------- + * ExecRecursiveScanReScan + * + * Rescans the relation. + * ---------------------------------------------------------------- + */ + void + ExecRecursiveScanReScan(RecursiveScanState *node, ExprContext *exprCtxt) + { + ExecClearTuple(node->ss.ps.ps_ResultTupleSlot); + tuplestore_rescan(*node->working_table); + } *** src/backend/nodes/copyfuncs.c.orig Tue Sep 9 14:58:08 2008 --- src/backend/nodes/copyfuncs.c Tue Sep 23 12:03:15 2008 *************** *** 422,427 **** --- 422,465 ---- } /* + * _copyRecursion + */ + static Recursion * + _copyRecursion(Recursion *from) + { + Recursion *newnode = makeNode(Recursion); + + /* + * copy node superclass fields + */ + CopyScanFields((Scan *) from, (Scan *) newnode); + + /* + * copy remainder of node + */ + COPY_NODE_FIELD(subplan); + COPY_NODE_FIELD(subrtable); + + return newnode; + } + + /* + * _copyRecursiveScan + */ + static RecursiveScan * + _copyRecursiveScan(RecursiveScan *from) + { + RecursiveScan *newnode = makeNode(RecursiveScan); + + /* + * copy node superclass fields + */ + CopyScanFields((Scan *) from, (Scan *) newnode); + + 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); --- 1610,1626 ---- 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 **** --- 1675,1709 ---- 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_NODE_FIELD(ctecolnames); + COPY_NODE_FIELD(ctecoltypes); + COPY_NODE_FIELD(ctecoltypmods); + + return newnode; + } + static A_Expr * _copyAExpr(A_Expr *from) { *************** *** 1931,1936 **** --- 2003,2010 ---- 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 **** --- 2073,2079 ---- 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 **** --- 3179,3187 ---- case T_Append: retval = _copyAppend(from); break; + case T_Recursion: + retval = _copyRecursion(from); + break; case T_BitmapAnd: retval = _copyBitmapAnd(from); break; *************** *** 3137,3142 **** --- 3215,3223 ---- case T_ValuesScan: retval = _copyValuesScan(from); break; + case T_RecursiveScan: + retval = _copyRecursiveScan(from); + break; case T_Join: retval = _copyJoin(from); break; *************** *** 3672,3677 **** --- 3753,3764 ---- 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 23 12:03:15 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,2008 ---- } 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_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 **** --- 2626,2637 ---- 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 Tue Sep 23 12:03:16 2008 *************** *** 447,452 **** --- 447,471 ---- } static void + _outRecursion(StringInfo str, Recursion *node) + { + WRITE_NODE_TYPE("RECURSION"); + + _outScanInfo(str, (Scan *) node); + + WRITE_NODE_FIELD(subplan); + WRITE_NODE_FIELD(subrtable); + } + + static void + _outRecursiveScan(StringInfo str, RecursiveScan *node) + { + WRITE_NODE_TYPE("RECURSIVESCAN"); + + _outScanInfo(str, (Scan *) node); + } + + static void _outJoin(StringInfo str, Join *node) { WRITE_NODE_TYPE("JOIN"); *************** *** 1648,1653 **** --- 1667,1673 ---- 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 **** --- 1813,1820 ---- 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 **** --- 1851,1881 ---- } 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_NODE_FIELD(ctecolnames); + WRITE_NODE_FIELD(ctecoltypes); + WRITE_NODE_FIELD(ctecoltypmods); + } + + static void _outSetOperationStmt(StringInfo str, SetOperationStmt *node) { WRITE_NODE_TYPE("SETOPERATIONSTMT"); *************** *** 1861,1866 **** --- 1908,1917 ---- 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); --- 1920,1931 ---- 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 **** --- 2114,2138 ---- } 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"); *************** *** 2192,2197 **** --- 2265,2276 ---- case T_ValuesScan: _outValuesScan(str, obj); break; + case T_Recursion: + _outRecursion(str, obj); + break; + case T_RecursiveScan: + _outRecursiveScan(str, obj); + break; case T_Join: _outJoin(str, obj); break; *************** *** 2473,2478 **** --- 2552,2563 ---- 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 **** --- 2594,2605 ---- 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 23 12:03:16 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,258 ---- } /* + * _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_NODE_FIELD(ctecolnames); + READ_NODE_FIELD(ctecoltypes); + READ_NODE_FIELD(ctecoltypmods); + + READ_DONE(); + } + + /* * _readSetOperationStmt */ static SetOperationStmt * *************** *** 1007,1012 **** --- 1029,1038 ---- 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", --- 1041,1052 ---- 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 **** --- 1089,1096 ---- 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 Tue Sep 23 16:55:29 2008 *************** *** 57,62 **** --- 57,66 ---- RangeTblEntry *rte); static void set_values_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte); + static void set_recursion_pathlist(PlannerInfo *root, RelOptInfo *rel, + Index rti, RangeTblEntry *rte); + static void set_recursivescan_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); *************** *** 181,186 **** --- 185,197 ---- /* Values list --- generate a separate plan for it */ set_values_pathlist(root, rel, rte); } + else if (rel->rtekind == RTE_CTE) + { + if (rte->self_reference) + set_recursivescan_pathlist(root, rel, rte); + else + set_recursion_pathlist(root, rel, rti, rte); + } else { /* Plain relation */ *************** *** 550,556 **** RestrictInfo *rinfo = (RestrictInfo *) lfirst(l); Node *clause = (Node *) rinfo->clause; ! if (!rinfo->pseudoconstant && qual_is_pushdown_safe(subquery, rti, clause, differentTypes)) { /* Push it down */ --- 561,567 ---- RestrictInfo *rinfo = (RestrictInfo *) lfirst(l); Node *clause = (Node *) rinfo->clause; ! if (rte->rtekind != RTE_CTE && !rinfo->pseudoconstant && qual_is_pushdown_safe(subquery, rti, clause, differentTypes)) { /* Push it down */ *************** *** 585,591 **** /* 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; --- 596,602 ---- /* Generate the plan for the subquery */ rel->subplan = subquery_planner(root->glob, subquery, ! root, tuple_fraction, &subroot); rel->subrtable = subroot->parse->rtable; *************** *** 641,646 **** --- 652,768 ---- } /* + * set_recursion_pathlist + * Build the (single) access path for a recursive RTE + */ + static void + set_recursion_pathlist(PlannerInfo *root, RelOptInfo *rel, + Index rti, RangeTblEntry *rte) + { + Query *parse = root->parse; + CommonTableExpr *cte = NULL; + Query *subquery; + double tuple_fraction; + PlannerInfo *cteroot; + PlannerInfo *subroot; + List *pathkeys; + Index levelsup; + ListCell *lc; + + /* + * Find the referenced CTE. + */ + 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); + } + foreach(lc, cteroot->parse->cteList) + { + cte = (CommonTableExpr *) lfirst(lc); + if (strcmp(cte->ctename, rte->ctename) == 0) + break; + } + if (lc == NULL) /* shouldn't happen */ + elog(ERROR, "could not find CTE \"%s\"", rte->ctename); + + /* + * Kluge: copy the subquery and adjust any outer refs it has to match our + * own query level. We should instead be referencing a single evaluation + * of the CTE ... + */ + subquery = copyObject(cte->ctequery); + if (rte->ctelevelsup > 0) + IncrementVarSublevelsUp((Node *) subquery, rte->ctelevelsup, 1); + + /* + * We can safely pass the outer tuple_fraction down to the subquery if the + * outer level has no joining, aggregation, or sorting to do. Otherwise + * we'd better tell the subquery to plan for full retrieval. (XXX This + * could probably be made more intelligent ...) + */ + if (parse->hasAggs || + parse->groupClause || + parse->havingQual || + parse->distinctClause || + parse->sortClause || + has_multiple_baserels(root)) + tuple_fraction = 0.0; /* default case */ + else + tuple_fraction = root->tuple_fraction; + + /* + * Generate the subplan for the recursion. + * this is always "Append" as for now. + */ + rel->subplan = subquery_planner(root->glob, subquery, + root, + tuple_fraction, + &subroot); + rel->subrtable = subroot->parse->rtable; + + /* Copy number of output rows from subplan */ + rel->tuples = rel->subplan->plan_rows; + + /* Mark rel with estimated output rows, width, etc */ + set_baserel_size_estimates(root, rel); + + /* + * Convert subquery pathkeys to outer representation. For now + * this is useless since the subplan is always Append. Someday we + * implement "non_recursive_term UNION recursive_term" type CTE, + * and this will make sense... + */ + pathkeys = convert_subquery_pathkeys(root, rel, subroot->query_pathkeys); + + /* Generate appropriate path */ + add_path(rel, create_recursion_path(rel, pathkeys)); + + /* Select cheapest path (pretty easy in this case...) */ + set_cheapest(rel); + } + + /* + * set_recursivescan_pathlist + * Build the (single) access path for a recursive RTE + */ + static void + set_recursivescan_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) + { + /* Mark rel with estimated output rows, width, etc */ + set_recursivescan_size_estimates(root, rel); + + /* Generate appropriate path */ + add_path(rel, create_recursivescan_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. * *************** *** 1230,1235 **** --- 1352,1360 ---- ptype = "HashJoin"; join = true; break; + case T_Recursion: + ptype = "Recursion"; + break; default: ptype = "???Path"; break; *** src/backend/optimizer/path/clausesel.c.orig Thu Aug 21 20:16:03 2008 --- src/backend/optimizer/path/clausesel.c Mon Sep 22 15:33:09 2008 *************** *** 552,558 **** { RangeTblEntry *rte = planner_rt_fetch(var->varno, root); ! if (rte->rtekind == RTE_SUBQUERY) { /* * XXX not smart about subquery references... any way to do --- 552,559 ---- { RangeTblEntry *rte = planner_rt_fetch(var->varno, root); ! if (rte->rtekind == RTE_SUBQUERY || ! rte->rtekind == RTE_CTE) { /* * XXX not smart about subquery references... any way to do *** src/backend/optimizer/path/costsize.c.orig Fri Sep 5 17:07:29 2008 --- src/backend/optimizer/path/costsize.c Mon Sep 22 19:55:02 2008 *************** *** 934,939 **** --- 934,999 ---- } /* + * cost_recursion + * Determines and returns the cost of scanning a recursion RTE. + */ + void + cost_recursion(Path *path, RelOptInfo *baserel) + { + Cost startup_cost; + Cost run_cost; + Cost cpu_per_tuple; + + /* Should only be applied to base relations that are subqueries */ + Assert(baserel->relid > 0); + Assert(baserel->rtekind == RTE_CTE); + + /* + * Cost of path is cost of evaluating the subplan, plus cost of evaluating + * any restriction clauses that will be attached to the SubqueryScan node, + * plus cpu_tuple_cost to account for selection and projection overhead. + */ + path->startup_cost = baserel->subplan->startup_cost; + path->total_cost = baserel->subplan->total_cost; + + 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_recursivescan + * Determines and returns the cost of scanning a WITH RECURSIVE RTE. + */ + void + cost_recursivescan(Path *path, PlannerInfo *root, RelOptInfo *baserel) + { + Cost startup_cost = 0; + Cost run_cost = 0; + Cost cpu_per_tuple; + + Assert(baserel->relid > 0); + Assert(baserel->rtekind == RTE_CTE); + + /* + * For now, estimate list evaluation cost at one operator eval per list + * (probably pretty bogus, but is it worth being smarter?) + */ + cpu_per_tuple = cpu_operator_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_sort * Determines and returns the cost of sorting a relation, including * the cost of reading the input data. *************** *** 2475,2480 **** --- 2535,2562 ---- set_baserel_size_estimates(root, rel); } + /* + * set_recursivescan_size_estimates + * Set the size estimates for a recursivescan. + * + * The rel's targetlist and restrictinfo list must have been constructed + * already. + * + * We set the same fields as set_baserel_size_estimates. + */ + void + set_recursivescan_size_estimates(PlannerInfo *root, RelOptInfo *rel) + { + RangeTblEntry *rte; + + Assert(rel->relid > 0); + rte = planner_rt_fetch(rel->relid, root); + Assert(rte->rtekind == RTE_CTE); + + /* Now estimate number of output rows, etc */ + set_baserel_size_estimates(root, rel); + } + /* * set_rel_width *** src/backend/optimizer/plan/createplan.c.orig Fri Sep 5 17:07:29 2008 --- src/backend/optimizer/plan/createplan.c Mon Sep 22 19:55:25 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 RecursiveScan *create_recursivescan_plan(PlannerInfo *root, Path *best_path, + List *tlist, List *scan_clauses); + static Recursion *create_recursion_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,109 ---- List *funccoltypes, List *funccoltypmods); static ValuesScan *make_valuesscan(List *qptlist, List *qpqual, Index scanrelid, List *values_lists); + static RecursiveScan *make_recursivescan(List *qptlist, List *qpqual, + Index scanrelid); + static Recursion *make_recursion(List *qptlist, + List *qpqual, + Index scanrelid, + Plan *subplan, + List *subrtable); static BitmapAnd *make_bitmap_and(List *bitmapplans); static BitmapOr *make_bitmap_or(List *bitmapplans); static NestLoop *make_nestloop(List *tlist, *************** *** 148,153 **** --- 159,166 ---- case T_SubqueryScan: case T_FunctionScan: case T_ValuesScan: + case T_RecursiveScan: + case T_Recursion: plan = create_scan_plan(root, best_path); break; case T_HashJoin: *************** *** 270,275 **** --- 283,302 ---- scan_clauses); break; + case T_RecursiveScan: + plan = (Plan *) create_recursivescan_plan(root, + best_path, + tlist, + scan_clauses); + break; + + case T_Recursion: + plan = (Plan *) create_recursion_plan(root, + best_path, + tlist, + scan_clauses); + break; + default: elog(ERROR, "unrecognized node type: %d", (int) best_path->pathtype); *************** *** 375,380 **** --- 402,408 ---- case T_SubqueryScan: case T_FunctionScan: case T_ValuesScan: + case T_RecursiveScan: plan->targetlist = build_relation_tlist(path->parent); break; default: *************** *** 1335,1340 **** --- 1363,1431 ---- return scan_plan; } + /* + * create_recursivescan_plan + */ + static RecursiveScan * + create_recursivescan_plan(PlannerInfo *root, Path *best_path, + List *tlist, List *scan_clauses) + { + RecursiveScan *scan_plan; + Index scan_relid = best_path->parent->relid; + RangeTblEntry *rte; + + Assert(scan_relid > 0); + rte = planner_rt_fetch(scan_relid, root); + Assert(rte->rtekind == RTE_CTE); + + /* 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_recursivescan(tlist, scan_clauses, scan_relid); + + copy_path_costsize(&scan_plan->scan.plan, best_path); + + return scan_plan; + } + + /* + * create_subqueryscan_plan + * Returns a subqueryscan plan for the base relation scanned by 'best_path' + * with restriction clauses 'scan_clauses' and targetlist 'tlist'. + */ + static Recursion * + create_recursion_plan(PlannerInfo *root, Path *best_path, + List *tlist, List *scan_clauses) + { + Recursion *recursion_plan; + Index scan_relid = best_path->parent->relid; + + /* it should be a subquery base rel... */ + Assert(scan_relid > 0); + Assert(best_path->parent->rtekind == RTE_CTE); + + /* 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); + + recursion_plan = make_recursion(tlist, + scan_clauses, + scan_relid, + best_path->parent->subplan, + best_path->parent->subrtable); + + copy_path_costsize(&recursion_plan->scan.plan, best_path); + + return recursion_plan; + } + + + /***************************************************************************** * * JOIN METHODS *************** *** 2291,2296 **** --- 2382,2434 ---- return node; } + static RecursiveScan * + make_recursivescan(List *qptlist, + List *qpqual, + Index scanrelid) + { + RecursiveScan *node = makeNode(RecursiveScan); + 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; + + return node; + } + + static Recursion * + make_recursion(List *qptlist, + List *qpqual, + Index scanrelid, + Plan *subplan, + List *subrtable) + { + Recursion *node = makeNode(Recursion); + Plan *plan = &node->scan.plan; + + /* + * Cost is figured here for the convenience of prepunion.c. Note this is + * only correct for the case where qpqual is empty; otherwise caller + * should overwrite cost with a better estimate. + */ + copy_plan_costsize(plan, subplan); + plan->total_cost += cpu_tuple_cost * subplan->plan_rows; + + plan->targetlist = qptlist; + plan->qual = qpqual; + plan->lefttree = NULL; + plan->righttree = NULL; + node->scan.scanrelid = scanrelid; + node->subplan = subplan; + node->subrtable = subrtable; + + return node; + } + Append * make_append(List *appendplans, bool isTarget, List *tlist) { *** src/backend/optimizer/plan/planner.c.orig Tue Sep 9 14:58:08 2008 --- src/backend/optimizer/plan/planner.c Tue Sep 23 16:33:55 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,179 ---- } /* primary planning entry point (may recurse for subqueries) */ ! top_plan = subquery_planner(glob, parse, NULL, 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. * --- 228,234 ---- * * 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). * 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); --- 249,255 ---- */ Plan * subquery_planner(PlannerGlobal *glob, Query *parse, ! PlannerInfo *parent_root, double tuple_fraction, PlannerInfo **subroot) { int num_old_subplans = list_length(glob->subplans); *************** *** 263,269 **** 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; --- 263,270 ---- 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->eq_classes = NIL; *** src/backend/optimizer/plan/setrefs.c.orig Tue Sep 9 14:58:08 2008 --- src/backend/optimizer/plan/setrefs.c Mon Sep 22 21:42:53 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,214 ---- /* zap unneeded sub-structure */ newrte->subquery = NULL; + newrte->joinaliasvars = NIL; newrte->funcexpr = NULL; newrte->funccoltypes = NIL; newrte->funccoltypmods = NIL; newrte->values_lists = NIL; ! newrte->ctename = NULL; ! newrte->ctecoltypes = NIL; ! newrte->ctecoltypmods = NIL; glob->finalrtable = lappend(glob->finalrtable, newrte); *************** *** 343,349 **** --- 346,379 ---- fix_scan_list(glob, splan->values_lists, rtoffset); } break; + case T_RecursiveScan: + { + RecursiveScan *splan = (RecursiveScan *) 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_Recursion: + { + Recursion *rplan = (Recursion *) plan; + /* First, recursively process the subplan */ + rplan->subplan = set_plan_references(glob, rplan->subplan, rplan->subrtable); + + /* subrtable is no longer needed in the plan tree */ + rplan->subrtable = NIL; + + rplan->scan.scanrelid += rtoffset; + rplan->scan.plan.targetlist = + fix_scan_list(glob, rplan->scan.plan.targetlist, rtoffset); + rplan->scan.plan.qual = + fix_scan_list(glob, rplan->scan.plan.qual, rtoffset); + } + break; case T_NestLoop: case T_MergeJoin: case T_HashJoin: *** src/backend/optimizer/plan/subselect.c.orig Thu Aug 28 19:09:46 2008 --- src/backend/optimizer/plan/subselect.c Tue Sep 23 16:36:50 2008 *************** *** 308,314 **** * Generate the plan for the subquery. */ plan = subquery_planner(root->glob, subquery, ! root->query_level + 1, tuple_fraction, &subroot); --- 308,314 ---- * Generate the plan for the subquery. */ plan = subquery_planner(root->glob, subquery, ! root, tuple_fraction, &subroot); *************** *** 342,348 **** { /* 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); --- 342,348 ---- { /* Generate the plan for the ANY subquery; we'll need all rows */ plan = subquery_planner(root->glob, subquery, ! root, 0.0, &subroot); *************** *** 1798,1803 **** --- 1798,1805 ---- case T_Unique: case T_SetOp: case T_Group: + case T_Recursion: + case T_RecursiveScan: break; default: *** src/backend/optimizer/prep/prepjointree.c.orig Mon Aug 25 18:42:33 2008 --- src/backend/optimizer/prep/prepjointree.c Tue Sep 23 16:37:13 2008 *************** *** 567,572 **** --- 567,573 ---- 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->eq_classes = NIL; *************** *** 916,923 **** return false; /* ! * Can't pull up a subquery involving grouping, aggregation, sorting, or ! * limiting. */ if (subquery->hasAggs || subquery->groupClause || --- 917,924 ---- 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; /* --- 926,933 ---- 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 */ --- 987,998 ---- 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 Tue Sep 23 16:37:13 2008 *************** *** 200,206 **** * Generate plan for primitive subquery */ subplan = subquery_planner(root->glob, subquery, ! root->query_level + 1, tuple_fraction, &subroot); --- 200,206 ---- * Generate plan for primitive subquery */ subplan = subquery_planner(root->glob, subquery, ! root, tuple_fraction, &subroot); *************** *** 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; --- 1346,1352 ---- 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 Mon Sep 22 11:16:32 2008 *************** *** 1220,1225 **** --- 1220,1264 ---- } /* + * create_recursion_path + * Creates a path corresponding to a scan of recursion, + * returning the pathnode. + */ + Path * + create_recursion_path(RelOptInfo *rel, List *pathkeys) + { + Path *pathnode = makeNode(Path); + + pathnode->pathtype = T_Recursion; + pathnode->parent = rel; + pathnode->pathkeys = pathkeys; + + cost_recursion(pathnode, rel); + + return pathnode; + } + + + /* + * create_recursivescan_path + * Creates a path corresponding to a scan of recursive, + * returning the pathnode. + */ + Path * + create_recursivescan_path(PlannerInfo *root, RelOptInfo *rel) + { + Path *pathnode = makeNode(Path); + + pathnode->pathtype = T_RecursiveScan; + pathnode->parent = rel; + pathnode->pathkeys = NIL; /* result is always unordered */ + + cost_recursivescan(pathnode, root, rel); + + return pathnode; + } + + /* * create_nestloop_path * Creates a pathnode corresponding to a nestloop join between two * relations. *** 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 23 12:24:06 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 { *************** *** 694,699 **** --- 697,709 ---- /* 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); *************** *** 812,817 **** --- 822,828 ---- Assert(stmt->whereClause == NULL); Assert(stmt->groupClause == NIL); Assert(stmt->havingClause == NULL); + Assert(stmt->withClause == NULL); Assert(stmt->op == SETOP_NONE); /* *************** *** 1059,1064 **** --- 1070,1082 ---- (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. */ *************** *** 1841,1846 **** --- 1859,1868 ---- */ 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 **** --- 1930,1937 ---- 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 11 11:27:30 2008 --- src/backend/parser/gram.y Tue Sep 23 11:04:44 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 *************** *** 6260,6265 **** --- 6266,6275 ---- ; /* + * 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 *************** *** 6270,6290 **** | 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: --- 6280,6330 ---- | 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: *************** *** 6345,6350 **** --- 6385,6431 ---- } ; + /* + * 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 { *************** *** 9332,9337 **** --- 9413,9419 ---- | READ | REASSIGN | RECHECK + | RECURSIVE | REINDEX | RELATIVE_P | RELEASE *************** *** 9399,9405 **** | VIEW | VOLATILE | WHITESPACE_P - | WITH | WITHOUT | WORK | WRITE --- 9481,9486 ---- *************** *** 9582,9587 **** --- 9663,9669 ---- | VARIADIC | WHEN | WHERE + | WITH ; *************** *** 9905,9912 **** 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 --- 9987,9997 ---- 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 *************** *** 9940,9945 **** --- 10025,10039 ---- 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 Fri Aug 29 09:02:32 2008 --- src/backend/parser/keywords.c Mon Sep 22 13:33:32 2008 *************** *** 304,309 **** --- 304,310 ---- {"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}, *************** *** 402,416 **** {"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}, --- 403,408 ---- *** src/backend/parser/parse_agg.c.orig Mon Sep 1 16:42:44 2008 --- src/backend/parser/parse_agg.c Mon Sep 22 19:55:40 2008 *************** *** 217,222 **** --- 217,238 ---- clause = flatten_join_alias_vars(root, clause); check_ungrouped_columns(clause, pstate, groupClauses, have_non_var_grouping); + + /* + * Check if there's aggregate function in a recursive term. + */ + foreach(l, qry->rtable) + { + RangeTblEntry *rte = (RangeTblEntry *) lfirst(l); + + if (qry->hasAggs && rte->rtekind == RTE_CTE && + rte->self_reference) + { + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + errmsg("aggregate functions in a recursive term not allowed"))); + } + } } *** src/backend/parser/parse_clause.c.orig Mon Sep 1 16:42:44 2008 --- src/backend/parser/parse_clause.c Tue Sep 23 17:42:43 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,470 ---- 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; + + /* + * This is a kluge for now. Effectively we're inlining non-recursive WITH + * clauses which isn't what we want to do. But the planner currently + * thinks that all CTE RTEs are recursive, and that has to be fixed + * before this can be cleaned up. Note that we may also get the column + * names wrong when there are column aliases at both sites. + */ + if (cte->cterecursive) + { + rte = addRangeTableEntryForCTE(pstate, cte, levelsup, r->alias, true); + } + else + { + Alias *a; + Query *q; + + if (r->alias) + a = r->alias; + else + a = makeAlias(cte->ctename, cte->aliascolnames); + + Assert(IsA(cte->ctequery, Query)); + q = copyObject(cte->ctequery); + /* must adjust any outer references when copying down in level */ + if (levelsup > 0) + IncrementVarSublevelsUp((Node *) q, levelsup, 1); + rte = addRangeTableEntryForSubquery(pstate, q, a, 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)); --- 652,697 ---- { 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 Tue Sep 23 21:22:49 2008 *************** *** 0 **** --- 1,882 ---- + /*------------------------------------------------------------------------- + * + * 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 "access/heapam.h" + #include "catalog/heap.h" + #include "catalog/pg_type.h" + #include "commands/defrem.h" + #include "nodes/bitmapset.h" + #include "nodes/makefuncs.h" + #include "nodes/nodeFuncs.h" + #include "optimizer/clauses.h" + #include "parser/analyze.h" + #include "parser/parse_clause.h" + #include "parser/parse_coerce.h" + #include "parser/parse_cte.h" + #include "parser/parse_expr.h" + #include "parser/parse_oper.h" + #include "parser/parse_relation.h" + #include "parser/parse_target.h" + #include "parser/parsetree.h" + + + /* + * 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 + { + ParseState *pstate; /* global parse state */ + CteItem *items; /* array of CTEs and extra data */ + int numitems; /* number of CTEs */ + int curitem; /* index of item currently being examined */ + List *innerwiths; /* list of lists of CommonTableExpr */ + } CteState; + + typedef enum RecursiveType + { + NON_RECURSIVE, + RECURSIVE_SELF, + RECURSIVE_OTHER + } RecursiveType; + + + /* UGH FIXME */ + static Node *non_recursive_term; + + + static void analyzeCTE(ParseState *pstate, CommonTableExpr *cte); + static void analyzeCTETargetList(ParseState *pstate, CommonTableExpr *cte, List *tlist); + + /* Dependency collector functions */ + static void makeDependencyGraph(CteState *cstate); + static bool makeDependencyGraphWalker(Node *node, CteState *cstate); + static void TopologicalSort(ParseState *pstate, CteItem *items, int numitems); + + /* Checker functions */ + static void checkWellFormedCte(CteState *cstate); + static RecursiveType checkCteSelectStmt(CteState *cstate, SelectStmt *n, int myindex); + static RecursiveType checkCteTargetList(CteState *cstate, List *targetList, int myindex); + static RecursiveType checkCteTargetListItem(CteState *cstate, Node *target, int myindex); + static RecursiveType checkCteFromClause(CteState *cstate, List *fromClause, int myindex); + static RecursiveType checkCteWhereClause(CteState *cstate, Node *n, int myindex); + static RecursiveType checkCteFromClauseItem(CteState *cstate, Node *n, int myindex); + static RecursiveType findCteName(CteState *cstate, char *name, int myindex); + + + /* + * 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. + */ + 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("common table expression name \"%s\" specified more than once", + cte2->ctename), + parser_errposition(pstate, cte2->location))); + } + + cte->cterecursive = false; + } + + 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++; + } + cstate.curitem = 0; + cstate.innerwiths = NIL; + + /* + * Check well-formed subquery. + */ + checkWellFormedCte(&cstate); + + /* + * Set up the ctenamespace for parse analysis. Per spec, all + * the WITH items are visible to all others, so it's just the + * same as the original WITH list. (We keep the original order + * since this will affect display of the query by ruleutils.c.) + */ + pstate->p_ctenamespace = withClause->ctes; + + /* + * 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 is allowed to depend on have already been loaded into + * pstate->p_ctenamespace. + */ + 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; + + /* Same checks that FROM does on subqueries XXX refactor? */ + if (query->commandType != CMD_SELECT || + query->utilityStmt != NULL) + elog(ERROR, "expected SELECT query from subquery in WITH"); + if (query->intoClause) + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + errmsg("subquery in WITH cannot have SELECT INTO"))); + + /* Compute the derived fields if not done yet */ + if (!cte->cterecursive) + analyzeCTETargetList(pstate, cte, query->targetList); + } + + /* + * 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 item \"%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); + elog(DEBUG1, "CTE name dependency: %s(%d) -> %s(%d)", + cstate->items[myindex].cte->ctename, + cstate->items[myindex].id, + cte->ctename, 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, k; + + /* 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)) + continue; + + /* + * Found one. Move it to front and remove it from every other + * item's dependencies. + * + * Items before i are known to have no dependencies left, + * so we can skip them in this loop. + */ + for (k = i; k < numitems; k++) + { + items[k].depends_on = bms_del_member(items[k].depends_on, + items[j].id); + } + /* swap */ + if (i != j) + { + CteItem tmp; + + tmp = items[i]; + items[i] = items[j]; + items[j] = tmp; + } + 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))); + } + } + + + static void + checkWellFormedCte(CteState *cstate) + { + int i; + + non_recursive_term = NULL; + + /* Find all the dependencies and sort into a safe processing order */ + makeDependencyGraph(cstate); + + for (i = 0; i < cstate->numitems; i++) + { + CommonTableExpr *cte = cstate->items[i].cte; + SelectStmt *stmt = (SelectStmt *) cte->ctequery; + + if (stmt->op == SETOP_NONE) + { + RecursiveType r; + + r = checkCteSelectStmt(cstate, stmt, i); + if (r != NON_RECURSIVE) + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + errmsg("recursive query must have a non-recursive term"), + parser_errposition(cstate->pstate, cte->location))); + + if (non_recursive_term) + cstate->items[i].non_recursive_term = non_recursive_term; + non_recursive_term = NULL; + } + else + { + SelectStmt *larg = (SelectStmt *)stmt->larg; + SelectStmt *rarg = (SelectStmt *)stmt->rarg; + RecursiveType lresult, rresult; + + lresult = checkCteSelectStmt(cstate, larg, i); + rresult = checkCteSelectStmt(cstate, rarg, i); + + /* Check if a query is a recursive query */ + if (lresult == NON_RECURSIVE && rresult == NON_RECURSIVE) + { + if (non_recursive_term) + cstate->items[i].non_recursive_term = non_recursive_term; + non_recursive_term = NULL; + } + else if (lresult == RECURSIVE_OTHER || rresult == RECURSIVE_OTHER) + ereport(ERROR, + (errcode(ERRCODE_FEATURE_NOT_SUPPORTED), + errmsg("mutual recursion between WITH items is not supported"), + parser_errposition(cstate->pstate, cte->location))); + + /* + * Check non-recursive-term UNION ALL recursive-term + */ + else if (stmt->op == SETOP_UNION && stmt->all == true && + lresult != NON_RECURSIVE) + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + errmsg("Left hand side of UNION ALL must be a non-recursive term in a recursive query"))); + + else if (stmt->op == SETOP_INTERSECT) + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + errmsg("non-recursive term and recursive term must not be combined with INTERSECT"))); + + else if (stmt->op == SETOP_EXCEPT) + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + errmsg("non-recursive term and recursive term must not be combined with EXCEPT"))); + + else if (stmt->op == SETOP_UNION && stmt->all != true) + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + errmsg("non-recursive term and recursive term must be combined with UNION ALL"))); + + else if (stmt->op == SETOP_UNION && stmt->all == true && + rarg->op == SETOP_UNION) + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + errmsg("Right hand side of UNION ALL must not contain UNION operation"))); + + else if (stmt->sortClause) + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + errmsg("ORDER BY in a recursive query not allowed"))); + + else if (stmt->limitOffset || stmt->limitCount) + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + errmsg("LIMIT OFFSET in a recursive query not allowed"))); + + else if (stmt->lockingClause) + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + errmsg("FOR UPDATE in a recursive query not allowed"))); + + else if (lresult == NON_RECURSIVE && rresult == RECURSIVE_SELF) + { + if (larg->distinctClause) + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + errmsg("DISTINCT in a non recursive term not allowed"))); + + if (rarg->distinctClause) + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + errmsg("DISTINCT in a recursive term not allowed"))); + + if (rarg->groupClause) + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + errmsg("GROUP BY in a recursive term not allowed"))); + + if (rarg->havingClause) + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + errmsg("HAVING in a recursive term not allowed"))); + + /* + * Save non_recursive_term. + */ + if (non_recursive_term) + cstate->items[i].non_recursive_term = non_recursive_term; + else + cstate->items[i].non_recursive_term = (Node *) larg; + cte->cterecursive = true; + non_recursive_term = NULL; + } + else + elog(ERROR, "unknown error in checkWellFormedCte"); + } + } + } + + static RecursiveType checkCteSelectStmt(CteState *cstate, SelectStmt *n, int myindex) + { + RecursiveType r = NON_RECURSIVE; + + if (n->op != SETOP_NONE) + { + RecursiveType r1, r2; + + r1 = checkCteSelectStmt(cstate, n->larg, myindex); + r2 = checkCteSelectStmt(cstate, n->rarg, myindex); + + /* Non-linear recursion is not allowed */ + if (r1 == RECURSIVE_SELF && r2 == RECURSIVE_SELF) + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + (errmsg("non-linear recursion not allowed")))); + + else if (r1 == RECURSIVE_OTHER || r2 == RECURSIVE_OTHER) + return RECURSIVE_OTHER; + else if (r1 == RECURSIVE_SELF || r2 == RECURSIVE_SELF) + return RECURSIVE_SELF; + else + return NON_RECURSIVE; + } + + if (n->targetList) + { + /* Cannot contain any recursive term in target list */ + if (checkCteTargetList(cstate, n->targetList, myindex) != NON_RECURSIVE) + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + (errmsg("target list having subquery which uses recursive name in a recursive term not allowed")))); + } + + if (n->fromClause) + r = checkCteFromClause(cstate, n->fromClause, myindex); + + if (n->whereClause) + { + /* Cannot contain any recursive names in WHERE-clause */ + if (checkCteWhereClause(cstate, n->whereClause, myindex) != NON_RECURSIVE) + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + (errmsg("WHERE clause having subqury which uses recursive name in a recursive term not allowed")))); + + } + + return r; + } + + static RecursiveType checkCteTargetList(CteState *cstate, List *targetList, int myindex) + { + ListCell *lc; + RecursiveType result = NON_RECURSIVE; + + foreach(lc, targetList) + { + RecursiveType r; + r = checkCteTargetListItem(cstate, lfirst(lc), myindex); + if (result == NON_RECURSIVE) + result = r; + else if (result == RECURSIVE_SELF && r == RECURSIVE_OTHER) + result = r; + } + return result; + } + + /* + * Check if a target list item has a subquery which uses recursive name. + */ + static RecursiveType checkCteTargetListItem(CteState *cstate, Node *n, int myindex) + { + if (IsA(n, ResTarget)) + { + ResTarget *rs = (ResTarget *)n; + + if (rs->val && IsA(rs->val, SubLink)) + { + SubLink *sl = (SubLink *)rs->val; + + if (sl->subselect && IsA(sl->subselect, SelectStmt)) + return checkCteSelectStmt(cstate, (SelectStmt *) sl->subselect, myindex); + } + } + + return NON_RECURSIVE; + } + + static RecursiveType checkCteWhereClause(CteState *cstate, Node *n, int myindex) + { + if (IsA(n, SubLink)) + return checkCteSelectStmt(cstate, (SelectStmt *) ((SubLink *) n)->subselect, myindex); + else if (IsA(n, A_Expr)) + { + RecursiveType result; + A_Expr *expr = (A_Expr *)n; + + if (expr->lexpr && IsA(expr->lexpr, SubLink)) + { + result = checkCteWhereClause(cstate, (Node *) expr->lexpr, myindex); + if (result != NON_RECURSIVE) + return result; + } + if (expr->rexpr && IsA(expr->rexpr, SubLink)) + { + result = checkCteWhereClause(cstate, (Node *) expr->rexpr, myindex); + if (result != NON_RECURSIVE) + return result; + } + } + + return NON_RECURSIVE; + } + + /* + * checkCteFromClause + */ + static RecursiveType checkCteFromClause(CteState *cstate, List *fromClause, int myindex) + { + ListCell *lc; + RecursiveType result = NON_RECURSIVE; + + foreach(lc, fromClause) + { + RecursiveType r; + + r = checkCteFromClauseItem(cstate, lfirst(lc), myindex); + if (result == NON_RECURSIVE) + result = r; + else if (result == RECURSIVE_SELF && r == RECURSIVE_OTHER) + result = r; + } + return result; + } + + static RecursiveType checkCteFromClauseItem(CteState *cstate, Node *n, int myindex) + { + if (IsA(n, RangeVar)) /* table reference */ + { + RangeVar *rv = (RangeVar *)n; + if (rv->schemaname) + return NON_RECURSIVE; + + return findCteName(cstate, rv->relname, myindex); + } + else if (IsA(n, RangeSubselect)) + { + RangeSubselect *rs = (RangeSubselect *)n; + + return checkCteSelectStmt(cstate, (SelectStmt *)rs->subquery, myindex); + } + else if (IsA(n, RangeFunction)) + { + /* do nothing */ + return NON_RECURSIVE; + } + + /* + * SQL standard says that the following join type should not contain. + * + * 1. query including recursive query name and FULL OUTER JOIN is not allowed. + * 2. outer join query is not allowed if the right hand side of LEFT OUTER JOIN + * has recursive query name. + * 3. outer join query is not allowed if the left hand side of RIGHT OUTER JOIN + * has recursive query name. + * + */ + else if (IsA(n, JoinExpr)) + { + JoinExpr *je = (JoinExpr *) n; + RecursiveType larg, rarg; + + larg = checkCteFromClauseItem(cstate, je->larg, myindex); + rarg = checkCteFromClauseItem(cstate, je->rarg, myindex); + + /* We must not allow mutually recursion. */ + if (larg == RECURSIVE_OTHER || rarg == RECURSIVE_OTHER) + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + errmsg("cannot refer other recursive names"))); + + /* Condition #1 */ + if (je->jointype == JOIN_FULL) + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + errmsg("FULL JOIN in a recursive term not allowed"))); + /* Condition #2 */ + else if (je->jointype == JOIN_LEFT) + { + if (rarg != NON_RECURSIVE) + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + errmsg("LEFT JOIN in the right hand side of recursive term not allowed"))); + } + /* Condition #3 */ + else if (je->jointype == JOIN_RIGHT) + { + if (larg != NON_RECURSIVE) + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + errmsg("RIGHT JOIN in the left hand side of recursive term not allowed"))); + } + + return RECURSIVE_SELF; + } + else + elog(ERROR, "unrecognized node type: %d", (int) nodeTag(n)); + + return true; + } + + static RecursiveType + findCteName(CteState *cstate, char *name, int myindex) + { + int i; + + for (i = 0; i < cstate->numitems; i++) + { + CommonTableExpr *cte = cstate->items[i].cte; + + if (strcmp(name, cte->ctename) != 0) + continue; /* not the right one */ + + if (i == myindex) + return RECURSIVE_SELF; + + /* + * If the CTE has a non-recursive term, we can handle it as non-recursive query. + */ + if (cstate->items[i].non_recursive_term) + { + if (non_recursive_term == NULL) + non_recursive_term = cstate->items[i].non_recursive_term; + return NON_RECURSIVE; + } + + if (!cte->cterecursive) + return NON_RECURSIVE; + + return RECURSIVE_OTHER; + } + return NON_RECURSIVE; + } *** src/backend/parser/parse_relation.c.orig Mon Sep 1 16:42:44 2008 --- src/backend/parser/parse_relation.c Tue Sep 23 13:00:07 2008 *************** *** 1109,1114 **** --- 1109,1193 ---- } /* + * 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); + + 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 **** --- 1523,1563 ---- } } 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 **** --- 1864,1877 ---- *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,1793 **** --- 1910,1916 ---- break; case RTE_SUBQUERY: case RTE_VALUES: + case RTE_CTE: /* Subselect and Values RTEs never have dropped columns */ result = false; break; *** 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 Aug 28 19:09:48 2008 --- src/backend/rewrite/rewriteHandler.c Mon Sep 22 15:31:00 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); } /* *************** *** 1256,1261 **** --- 1264,1270 ---- fireRIRrules(Query *parsetree, List *activeRIRs) { int rt_index; + ListCell *lc; /* * don't try to convert this into a foreach loop, because rtable list can *************** *** 1368,1380 **** 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; } --- 1377,1398 ---- 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 23 12:03:46 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 * ---------- */ *************** *** 2357,2362 **** --- 2408,2418 ---- } /* + * Insert the WITH clause if given + */ + get_with_clause(query, context); + + /* * Build up the query string - first we say SELECT */ appendStringInfo(buf, "SELECT"); *************** *** 3259,3264 **** --- 3315,3321 ---- 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 **** --- 5187,5197 ---- /* Values list RTE */ get_values_def(rte->values_lists, context); break; + case RTE_CTE: + appendStringInfo(buf, "%s%s", + only_marker(rte), + 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/bin/psql/tab-complete.c.orig Sun Sep 7 20:47:40 2008 --- src/bin/psql/tab-complete.c Mon Sep 22 11:16:32 2008 *************** *** 613,621 **** "COMMENT", "COMMIT", "COPY", "CREATE", "DEALLOCATE", "DECLARE", "DELETE FROM", "DISCARD", "DROP", "END", "EXECUTE", "EXPLAIN", "FETCH", "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[] = { --- 613,621 ---- "COMMENT", "COMMIT", "COPY", "CREATE", "DEALLOCATE", "DECLARE", "DELETE FROM", "DISCARD", "DROP", "END", "EXECUTE", "EXPLAIN", "FETCH", "GRANT", "INSERT", "LISTEN", "LOAD", "LOCK", "MOVE", "NOTIFY", "PREPARE", ! "REASSIGN", "RECURSIVE", "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,2058 ---- 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) + { + static const char *const list_WITH[] = + {"RECURSIVE", NULL}; + + COMPLETE_WITH_LIST(list_WITH); + } + /* ANALYZE */ /* If the previous word is ANALYZE, produce list of tables */ else if (pg_strcasecmp(prev_wd, "ANALYZE") == 0) *** src/include/executor/nodeAppend.h.orig Tue Jan 1 14:45:57 2008 --- src/include/executor/nodeAppend.h Mon Sep 22 11:16:32 2008 *************** *** 21,25 **** --- 21,26 ---- extern TupleTableSlot *ExecAppend(AppendState *node); extern void ExecEndAppend(AppendState *node); extern void ExecReScanAppend(AppendState *node, ExprContext *exprCtxt); + extern bool exec_append_initialize_next(AppendState *appendstate); #endif /* NODEAPPEND_H */ *** src/include/executor/nodeRecursion.h.orig Mon Sep 22 11:16:32 2008 --- src/include/executor/nodeRecursion.h Mon Sep 22 11:16:32 2008 *************** *** 0 **** --- 1,25 ---- + /*------------------------------------------------------------------------- + * + * nodeRecursion.h + * + * + * + * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * $PostgreSQL$ + * + *------------------------------------------------------------------------- + */ + #ifndef NODERECURSION_H + #define NODERECURSION_H + + #include "nodes/execnodes.h" + + extern int ExecCountSlotsRecursion(Recursion *node); + extern RecursionState *ExecInitRecursion(Recursion *node, EState *estate, int eflags); + extern TupleTableSlot *ExecRecursion(RecursionState *node); + extern void ExecEndRecursion(RecursionState *node); + extern void ExecRecursionReScan(RecursionState *node, ExprContext *exprCtxt); + + #endif /* NODESUBQUERYSCAN_H */ *** src/include/executor/nodeRecursivescan.h.orig Mon Sep 22 11:16:32 2008 --- src/include/executor/nodeRecursivescan.h Mon Sep 22 11:16:32 2008 *************** *** 0 **** --- 1,27 ---- + /*------------------------------------------------------------------------- + * + * nodeRecursivescan.h + * + * + * + * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * $PostgreSQL$ + * + *------------------------------------------------------------------------- + */ + #ifndef NODERECURSIVESCAN_H + #define NODERECURSIVESCAN_H + + #include "nodes/execnodes.h" + + extern int ExecCountSlotsRecursiveScan(RecursiveScan *node); + extern RecursiveScanState *ExecInitRecursiveScan(RecursiveScan *node, EState *estate, int eflags); + extern TupleTableSlot *ExecRecursiveScan(RecursiveScanState *node); + extern void ExecEndRecursiveScan(RecursiveScanState *node); + extern void ExecRecursiveScanMarkPos(RecursiveScanState *node); + extern void ExecRecursiveScanRestrPos(RecursiveScanState *node); + extern void ExecRecursiveScanReScan(RecursiveScanState *node, ExprContext *exprCtxt); + + #endif /* NODERECURSIVESCAN_H */ *** src/include/nodes/execnodes.h.orig Thu Aug 21 20:16:04 2008 --- src/include/nodes/execnodes.h Mon Sep 22 11:16:32 2008 *************** *** 349,354 **** --- 349,357 ---- List *es_subplanstates; /* List of PlanState for SubPlans */ + Tuplestorestate **es_tuplestorestate; /* Stuff used for recursive query */ + TupleDesc es_rscan_tupledesc; + /* * this ExprContext is for per-output-tuple operations, such as constraint * checks and index-value computations. It will be reset for each output *************** *** 892,897 **** --- 895,901 ---- * State for management of parameter-change-driven rescanning */ Bitmapset *chgParam; /* set of IDs of changed Params */ + bool has_recursivescan; /* * Other run-time state needed by most if not all node types. *************** *** 1179,1184 **** --- 1183,1215 ---- int marked_idx; } ValuesScanState; + /* ---------------- + * RecursionState information + * + * RecursionState is used for scanning a recursive query. + * ---------------- + */ + typedef struct RecursionState + { + ScanState ss; /* its first field is NodeTag */ + PlanState *subplan; + bool recursive_empty; + Tuplestorestate *intermediate_tuplestorestate; + Tuplestorestate *working_table; + bool init_done; + } RecursionState; + + /* ---------------- + * RecursiveScanState information + * ---------------- + */ + typedef struct RecursiveScanState + { + ScanState ss; /* its first field is NodeTag */ + TupleDesc tupdesc; + Tuplestorestate **working_table; + } RecursiveScanState; + /* ---------------------------------------------------------------- * 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 Mon Sep 22 13:32:47 2008 *************** *** 55,65 **** --- 55,67 ---- T_SubqueryScan, T_FunctionScan, T_ValuesScan, + T_RecursiveScan, T_Join, T_NestLoop, T_MergeJoin, T_HashJoin, T_Material, + T_Recursion, T_Sort, T_Group, T_Agg, *************** *** 89,99 **** --- 91,103 ---- T_SubqueryScanState, T_FunctionScanState, T_ValuesScanState, + T_RecursiveScanState, T_JoinState, T_NestLoopState, T_MergeJoinState, T_HashJoinState, T_MaterialState, + T_RecursionState, T_SortState, T_GroupState, T_AggState, *************** *** 352,357 **** --- 356,363 ---- 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 23 12:02:48 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,750 ---- 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? */ + 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 **** --- 829,835 ---- 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 Mon Sep 22 11:16:32 2008 *************** *** 358,363 **** --- 358,384 ---- List *values_lists; /* list of expression lists */ } ValuesScan; + /* ---------------- + * RecursiveScan node + * ---------------- + */ + typedef struct RecursiveScan + { + Scan scan; + } RecursiveScan; + + /* ---------------- + * Recursion node + * ---------------- + */ + typedef struct Recursion + { + Scan scan; + Plan *subplan; + List *subrtable; /* temporary workspace for planner */ + } Recursion; + + /* * ========== * Join nodes *** src/include/nodes/relation.h.orig Tue Sep 9 14:58:08 2008 --- src/include/nodes/relation.h Tue Sep 23 16:29:39 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 *** src/include/optimizer/cost.h.orig Thu Aug 21 20:16:04 2008 --- src/include/optimizer/cost.h Mon Sep 22 11:16:32 2008 *************** *** 72,77 **** --- 72,80 ---- RelOptInfo *baserel); extern void cost_valuesscan(Path *path, PlannerInfo *root, RelOptInfo *baserel); + extern void cost_recursion(Path *path, RelOptInfo *baserel); + extern void cost_recursivescan(Path *path, PlannerInfo *root, + RelOptInfo *baserel); extern void cost_sort(Path *path, PlannerInfo *root, List *pathkeys, Cost input_cost, double tuples, int width, double limit_tuples); *************** *** 104,109 **** --- 107,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_recursivescan_size_estimates(PlannerInfo *root, RelOptInfo *rel); /* * prototypes for clausesel.c *** src/include/optimizer/pathnode.h.orig Thu Aug 14 14:48:00 2008 --- src/include/optimizer/pathnode.h Mon Sep 22 11:16:32 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_recursion_path(RelOptInfo *rel, List *pathkeys); + extern Path *create_recursivescan_path(PlannerInfo *root, RelOptInfo *rel); extern NestPath *create_nestloop_path(PlannerInfo *root, RelOptInfo *joinrel, *** src/include/optimizer/planner.h.orig Tue Jan 1 14:45:58 2008 --- src/include/optimizer/planner.h Tue Sep 23 16:33:47 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,36 ---- extern PlannedStmt *standard_planner(Query *parse, int cursorOptions, ParamListInfo boundParams); extern Plan *subquery_planner(PlannerGlobal *glob, Query *parse, ! PlannerInfo *parent_root, double tuple_fraction, PlannerInfo **subroot); #endif /* PLANNER_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/interfaces/ecpg/preproc/preproc.y.orig Wed Aug 20 10:09:16 2008 --- src/interfaces/ecpg/preproc/preproc.y Mon Sep 22 11:16:32 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/test/regress/expected/recursive.out.orig Mon Sep 22 11:16:32 2008 --- src/test/regress/expected/recursive.out Tue Sep 23 21:23:28 2008 *************** *** 0 **** --- 1,557 ---- + 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) + + -- recursive term has UNION + WITH RECURSIVE t(i,j) AS ( + VALUES (1,2) + UNION ALL + SELECT t2.i, t.j FROM (SELECT 2 AS i UNION ALL SELECT 3 AS i) AS t2 + JOIN t ON (t2.i = t.i)) + SELECT * FROM t; + i | j + ---+--- + 1 | 2 + (1 row) + + 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); + 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; + id | count + ----+------- + 3 | 7 + 2 | 6 + (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: non-recursive term and recursive term must be combined with UNION ALL + -- INTERSECT + WITH RECURSIVE x(n) AS (SELECT 1 INTERSECT SELECT n+1 FROM x) + SELECT * FROM x; + ERROR: non-recursive term and recursive term must not be combined with INTERSECT + WITH RECURSIVE x(n) AS (SELECT 1 INTERSECT ALL SELECT n+1 FROM x) + SELECT * FROM x; + ERROR: non-recursive term and recursive term must not be combined with INTERSECT + -- EXCEPT + WITH RECURSIVE x(n) AS (SELECT 1 EXCEPT SELECT n+1 FROM x) + SELECT * FROM x; + ERROR: non-recursive term and recursive term must not be combined with EXCEPT + WITH RECURSIVE x(n) AS (SELECT 1 EXCEPT ALL SELECT n+1 FROM x) + SELECT * FROM x; + ERROR: non-recursive term and recursive term must not be combined with EXCEPT + -- no non-recursive term + WITH RECURSIVE x(n) AS (SELECT n FROM x) + SELECT * FROM x; + ERROR: recursive query must have a non-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: Left hand side of UNION ALL must be a non-recursive term in a recursive query + 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: LEFT JOIN in the right hand side of recursive term not allowed + -- 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: RIGHT JOIN in the left hand side of recursive term not allowed + -- 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: FULL JOIN in a recursive term not allowed + -- 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: WHERE clause having subqury which uses recursive name in a recursive term not allowed + 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: WHERE clause having subqury which uses recursive name in a recursive term not allowed + -- GROUP BY + WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x GROUP BY n) + SELECT * FROM x; + ERROR: GROUP BY in a recursive term not allowed + -- HAVING + WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x HAVING n < 10) + SELECT * FROM x; + ERROR: HAVING in a recursive term not allowed + -- aggregate functions + WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT count(*) FROM x) + SELECT * FROM x; + ERROR: aggregate functions in a recursive term not allowed + WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT sum(n) FROM x) + SELECT * FROM x; + ERROR: aggregate functions in a recursive term not allowed + WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT max(n) FROM x) + SELECT * FROM x; + ERROR: aggregate functions in a recursive term not allowed + WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT max(n)+1 FROM x) + SELECT * FROM x; + ERROR: aggregate functions in a recursive term not allowed + WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT min(n) FROM x) + SELECT * FROM x; + ERROR: aggregate functions in a recursive term not allowed + -- 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 not allowed + -- LIMIT/OFFSET + WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x LIMIT 10 OFFSET 1) + SELECT * FROM x; + ERROR: LIMIT OFFSET in a recursive query not allowed + -- FOR UPDATE + WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x FOR UPDATE) + SELECT * FROM x; + ERROR: FOR UPDATE in a recursive query not allowed + -- 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: target list having subquery which uses recursive name in a recursive term not allowed + -- 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: non-linear recursion not allowed + 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: non-linear recursion not allowed + 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: non-linear recursion not allowed + 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: non-linear recursion not allowed + -- DISTINCT + WITH RECURSIVE t(n) AS ( + SELECT 1 + UNION ALL + SELECT DISTINCT n+1 FROM t WHERE n < 10 + ) + SELECT * FROM t; + ERROR: DISTINCT in a recursive term not allowed + WITH RECURSIVE foo(i) AS + (SELECT DISTINCT * FROM (VALUES(1),(2)) t + UNION ALL + SELECT DISTINCT i+1 FROM foo WHERE i < 10) + SELECT * FROM foo; + ERROR: DISTINCT in a non recursive term not allowed *** src/test/regress/parallel_schedule.orig Thu Apr 10 18:25:26 2008 --- src/test/regress/parallel_schedule Mon Sep 22 11:16:32 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 Thu Apr 10 18:25:26 2008 --- src/test/regress/serial_schedule Mon Sep 22 11:16:32 2008 *************** *** 114,118 **** --- 114,119 ---- 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 Mon Sep 22 11:16:32 2008 *************** *** 0 **** --- 1,367 ---- + 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; + + -- recursive term has UNION + WITH RECURSIVE t(i,j) AS ( + VALUES (1,2) + + UNION ALL + + SELECT t2.i, t.j FROM (SELECT 2 AS i UNION ALL SELECT 3 AS i) AS t2 + JOIN t ON (t2.i = t.i)) + + 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); + + 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; + + -- + -- 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; + + -- GROUP BY + WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x GROUP BY n) + SELECT * FROM x; + + -- HAVING + WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x HAVING n < 10) + 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; + + WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT max(n) FROM x) + SELECT * FROM x; + + WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT max(n)+1 FROM x) + SELECT * FROM x; + + WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT min(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; + + -- DISTINCT + WITH RECURSIVE t(n) AS ( + SELECT 1 + UNION ALL + SELECT DISTINCT n+1 FROM t WHERE n < 10 + ) + SELECT * FROM t; + + WITH RECURSIVE foo(i) AS + (SELECT DISTINCT * FROM (VALUES(1),(2)) t + UNION ALL + SELECT DISTINCT i+1 FROM foo WHERE i < 10) + SELECT * FROM foo;