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

*** pgsql/doc/src/sgml/ref/select.sgml 2008-02-16 07:17:06.000000000 +0900 --- pgsql.patched/doc/src/sgml/ref/select.sgml 2008-09-07 23:47:32.000000000 +0900 *************** *** 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; + + + *** pgsql/src/backend/commands/explain.c 2008-08-20 03:30:04.000000000 +0900 --- pgsql.patched/src/backend/commands/explain.c 2008-09-07 23:47:32.000000000 +0900 *************** *** 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_RECURSIVE); + + 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) { *** pgsql/src/backend/executor/Makefile 2008-02-19 19:30:07.000000000 +0900 --- pgsql.patched/src/backend/executor/Makefile 2008-09-07 23:47:32.000000000 +0900 *************** *** 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 *** pgsql/src/backend/executor/execAmi.c 2008-08-06 06:28:29.000000000 +0900 --- pgsql.patched/src/backend/executor/execAmi.c 2008-09-07 23:47:32.000000000 +0900 *************** *** 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; *************** *** 344,349 **** --- 362,368 ---- case T_TidScan: case T_FunctionScan: case T_ValuesScan: + case T_RecursiveScan: case T_Material: case T_Sort: return true; *************** *** 405,410 **** --- 424,430 ---- case T_TidScan: case T_FunctionScan: case T_ValuesScan: + case T_RecursiveScan: return true; case T_SubqueryScan: *** pgsql/src/backend/executor/execProcnode.c 2008-01-02 04:45:49.000000000 +0900 --- pgsql.patched/src/backend/executor/execProcnode.c 2008-09-07 23:47:32.000000000 +0900 *************** *** 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 */ *** pgsql/src/backend/executor/nodeAgg.c 2008-08-26 07:42:32.000000000 +0900 --- pgsql.patched/src/backend/executor/nodeAgg.c 2008-09-07 23:47:32.000000000 +0900 *************** *** 1232,1237 **** --- 1232,1238 ---- 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. *************** *** 1617,1627 **** 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; --- 1618,1630 ---- 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; *** pgsql/src/backend/executor/nodeAppend.c 2008-01-02 04:45:49.000000000 +0900 --- pgsql.patched/src/backend/executor/nodeAppend.c 2008-09-07 23:47:32.000000000 +0900 *************** *** 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; } *** pgsql/src/backend/executor/nodeHash.c 2008-01-02 04:45:49.000000000 +0900 --- pgsql.patched/src/backend/executor/nodeHash.c 2008-09-07 23:47:32.000000000 +0900 *************** *** 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 *** pgsql/src/backend/executor/nodeHashjoin.c 2008-08-16 04:20:42.000000000 +0900 --- pgsql.patched/src/backend/executor/nodeHashjoin.c 2008-09-07 23:47:33.000000000 +0900 *************** *** 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. *** pgsql/src/backend/executor/nodeMergejoin.c 2008-08-16 04:20:42.000000000 +0900 --- pgsql.patched/src/backend/executor/nodeMergejoin.c 2008-09-07 23:47:33.000000000 +0900 *************** *** 420,425 **** --- 420,433 ---- ResetExprContext(econtext); + #if 0 + /* + * Do not store a tuple into the recursive intermediate table. + * Because a recursive query does not stop loops. + */ + node->js.ps.state->es_disallow_tuplestore = true; + #endif + econtext->ecxt_outertuple = node->mj_OuterTupleSlot; econtext->ecxt_innertuple = node->mj_NullInnerTupleSlot; *** pgsql/src/backend/executor/nodeNestloop.c 2008-08-16 04:20:42.000000000 +0900 --- pgsql.patched/src/backend/executor/nodeNestloop.c 2008-09-07 23:47:33.000000000 +0900 *************** *** 179,184 **** --- 179,192 ---- */ econtext->ecxt_innertuple = node->nl_NullInnerTupleSlot; + #if 0 + /* + * Do not store a tuple into the recursive intermediate table. + * Because a recursive query does not stop loops. + */ + node->js.ps.state->es_disallow_tuplestore = true; + #endif + ENL1_printf("testing qualification for outer-join tuple"); if (otherqual == NIL || ExecQual(otherqual, econtext, false)) *** pgsql/src/backend/executor/nodeRecursion.c 1970-01-01 09:00:00.000000000 +0900 --- pgsql.patched/src/backend/executor/nodeRecursion.c 2008-09-07 23:47:33.000000000 +0900 *************** *** 0 **** --- 1,279 ---- + /*------------------------------------------------------------------------- + * + * 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; + node->ss.ps.state->es_disallow_tuplestore = false; + + /* 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 if (!node->ss.ps.state->es_disallow_tuplestore) + { + node->recursive_empty = false; + tuplestore_puttupleslot(node->intermediate_tuplestorestate, slot); + } + + /* restore flag */ + node->ss.ps.state->es_disallow_tuplestore = false; + + 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; + } *** pgsql/src/backend/executor/nodeRecursivescan.c 1970-01-01 09:00:00.000000000 +0900 --- pgsql.patched/src/backend/executor/nodeRecursivescan.c 2008-09-07 23:47:33.000000000 +0900 *************** *** 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); + } *** pgsql/src/backend/nodes/copyfuncs.c 2008-09-02 05:42:44.000000000 +0900 --- pgsql.patched/src/backend/nodes/copyfuncs.c 2008-09-07 23:47:33.000000000 +0900 *************** *** 421,426 **** --- 421,464 ---- } /* + * _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 *************** *** 745,750 **** --- 783,802 ---- } /* + * _copyWithClause + */ + static WithClause * + _copyWithClause(WithClause *from) + { + WithClause *newnode = makeNode(WithClause); + + COPY_NODE_FIELD(subquery); + COPY_SCALAR_FIELD(recursive); + + return newnode; + } + + /* * We don't need a _copyExpr because Expr is an abstract supertype which * should never actually get instantiated. Also, since it has no common * fields except NodeTag, there's no need for a helper routine to factor *************** *** 1560,1565 **** --- 1612,1619 ---- COPY_NODE_FIELD(funccoltypes); COPY_NODE_FIELD(funccoltypmods); COPY_NODE_FIELD(values_lists); + COPY_SCALAR_FIELD(self_reference); + COPY_NODE_FIELD(non_recursive_query); COPY_SCALAR_FIELD(jointype); COPY_NODE_FIELD(joinaliasvars); COPY_NODE_FIELD(alias); *************** *** 1927,1932 **** --- 1981,1987 ---- COPY_NODE_FIELD(limitCount); COPY_NODE_FIELD(rowMarks); COPY_NODE_FIELD(setOperations); + COPY_SCALAR_FIELD(recursive); return newnode; } *************** *** 1988,1993 **** --- 2043,2049 ---- COPY_NODE_FIELD(limitOffset); COPY_NODE_FIELD(limitCount); COPY_NODE_FIELD(lockingClause); + COPY_NODE_FIELD(withClause); COPY_SCALAR_FIELD(op); COPY_SCALAR_FIELD(all); COPY_NODE_FIELD(larg); *************** *** 3088,3093 **** --- 3144,3152 ---- case T_Append: retval = _copyAppend(from); break; + case T_Recursion: + retval = _copyRecursion(from); + break; case T_BitmapAnd: retval = _copyBitmapAnd(from); break; *************** *** 3121,3126 **** --- 3180,3188 ---- case T_ValuesScan: retval = _copyValuesScan(from); break; + case T_RecursiveScan: + retval = _copyRecursiveScan(from); + break; case T_Join: retval = _copyJoin(from); break; *************** *** 3170,3175 **** --- 3232,3240 ---- case T_IntoClause: retval = _copyIntoClause(from); break; + case T_WithClause: + retval = _copyWithClause(from); + break; case T_Var: retval = _copyVar(from); break; *** pgsql/src/backend/nodes/equalfuncs.c 2008-09-02 05:42:44.000000000 +0900 --- pgsql.patched/src/backend/nodes/equalfuncs.c 2008-09-07 23:47:33.000000000 +0900 *************** *** 123,128 **** --- 123,137 ---- return true; } + static bool + _equalWithClause(WithClause *a, WithClause *b) + { + COMPARE_NODE_FIELD(subquery); + COMPARE_SCALAR_FIELD(recursive); + + return true; + } + /* * We don't need an _equalExpr because Expr is an abstract supertype which * should never actually get instantiated. Also, since it has no common *************** *** 873,878 **** --- 882,888 ---- COMPARE_NODE_FIELD(limitOffset); COMPARE_NODE_FIELD(limitCount); COMPARE_NODE_FIELD(lockingClause); + COMPARE_NODE_FIELD(withClause); COMPARE_SCALAR_FIELD(op); COMPARE_SCALAR_FIELD(all); COMPARE_NODE_FIELD(larg); *************** *** 1936,1941 **** --- 1946,1953 ---- COMPARE_NODE_FIELD(funccoltypes); COMPARE_NODE_FIELD(funccoltypmods); COMPARE_NODE_FIELD(values_lists); + COMPARE_SCALAR_FIELD(self_reference); + COMPARE_NODE_FIELD(non_recursive_query); COMPARE_SCALAR_FIELD(jointype); COMPARE_NODE_FIELD(joinaliasvars); COMPARE_NODE_FIELD(alias); *************** *** 2124,2129 **** --- 2136,2144 ---- case T_IntoClause: retval = _equalIntoClause(a, b); break; + case T_WithClause: + retval = _equalWithClause(a, b); + break; case T_Var: retval = _equalVar(a, b); break; *** pgsql/src/backend/nodes/nodeFuncs.c 2008-09-02 05:42:44.000000000 +0900 --- pgsql.patched/src/backend/nodes/nodeFuncs.c 2008-09-07 23:58:49.000000000 +0900 *************** *** 1339,1344 **** --- 1339,1345 ---- { case RTE_RELATION: case RTE_SPECIAL: + case RTE_RECURSIVE: /* nothing to do */ break; case RTE_SUBQUERY: *************** *** 1964,1969 **** --- 1965,1971 ---- { case RTE_RELATION: case RTE_SPECIAL: + case RTE_RECURSIVE: /* we don't bother to copy eref, aliases, etc; OK? */ break; case RTE_SUBQUERY: *** pgsql/src/backend/nodes/outfuncs.c 2008-09-02 05:42:44.000000000 +0900 --- pgsql.patched/src/backend/nodes/outfuncs.c 2008-09-07 23:47:33.000000000 +0900 *************** *** 446,451 **** --- 446,470 ---- } 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"); *************** *** 683,688 **** --- 702,716 ---- } static void + _outWithClause(StringInfo str, WithClause *node) + { + WRITE_NODE_TYPE("WITHCLAUSE"); + + WRITE_NODE_FIELD(subquery); + WRITE_BOOL_FIELD(recursive); + } + + static void _outVar(StringInfo str, Var *node) { WRITE_NODE_TYPE("VAR"); *************** *** 1640,1645 **** --- 1668,1674 ---- WRITE_NODE_FIELD(limitOffset); WRITE_NODE_FIELD(limitCount); WRITE_NODE_FIELD(lockingClause); + WRITE_NODE_FIELD(withClause); WRITE_ENUM_FIELD(op, SetOperation); WRITE_BOOL_FIELD(all); WRITE_NODE_FIELD(larg); *************** *** 1669,1674 **** --- 1698,1734 ---- } 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 + _outRangeRecursive(StringInfo str, RangeRecursive *node) + { + WRITE_NODE_TYPE("RANGERECURSIVE"); + + WRITE_NODE_FIELD(subquery); + WRITE_NODE_FIELD(alias); + WRITE_NODE_FIELD(coldeflist); + WRITE_NODE_FIELD(non_recursive_term); + WRITE_BOOL_FIELD(recursive); + } + + static void _outLockingClause(StringInfo str, LockingClause *node) { WRITE_NODE_TYPE("LOCKINGCLAUSE"); *************** *** 1792,1797 **** --- 1852,1858 ---- WRITE_NODE_FIELD(limitCount); WRITE_NODE_FIELD(rowMarks); WRITE_NODE_FIELD(setOperations); + WRITE_BOOL_FIELD(recursive); } static void *************** *** 1856,1861 **** --- 1917,1927 ---- case RTE_VALUES: WRITE_NODE_FIELD(values_lists); break; + case RTE_RECURSIVE: + WRITE_NODE_FIELD(subquery); + WRITE_BOOL_FIELD(self_reference); + WRITE_NODE_FIELD(non_recursive_query); + break; case RTE_JOIN: WRITE_ENUM_FIELD(jointype, JoinType); WRITE_NODE_FIELD(joinaliasvars); *************** *** 2179,2184 **** --- 2245,2256 ---- 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; *************** *** 2224,2229 **** --- 2296,2304 ---- case T_IntoClause: _outIntoClause(str, obj); break; + case T_WithClause: + _outWithClause(str, obj); + break; case T_Var: _outVar(str, obj); break; *************** *** 2502,2507 **** --- 2577,2591 ---- case T_FuncCall: _outFuncCall(str, obj); break; + case T_RangeSubselect: + _outRangeSubselect(str, obj); + break; + case T_RangeFunction: + _outRangeFunction(str, obj); + break; + case T_RangeRecursive: + _outRangeRecursive(str, obj); + break; case T_DefElem: _outDefElem(str, obj); break; *** pgsql/src/backend/nodes/readfuncs.c 2008-09-02 05:42:44.000000000 +0900 --- pgsql.patched/src/backend/nodes/readfuncs.c 2008-09-07 23:47:33.000000000 +0900 *************** *** 167,172 **** --- 167,173 ---- READ_NODE_FIELD(limitCount); READ_NODE_FIELD(rowMarks); READ_NODE_FIELD(setOperations); + READ_BOOL_FIELD(recursive); READ_DONE(); } *************** *** 1015,1020 **** --- 1016,1026 ---- case RTE_VALUES: READ_NODE_FIELD(values_lists); break; + case RTE_RECURSIVE: + READ_NODE_FIELD(subquery); + READ_BOOL_FIELD(self_reference); + READ_NODE_FIELD(non_recursive_query); + break; case RTE_JOIN: READ_ENUM_FIELD(jointype, JoinType); READ_NODE_FIELD(joinaliasvars); *** pgsql/src/backend/optimizer/path/allpaths.c 2008-08-26 07:42:32.000000000 +0900 --- pgsql.patched/src/backend/optimizer/path/allpaths.c 2008-09-07 23:47:33.000000000 +0900 *************** *** 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_RECURSIVE) + { + if (rte->self_reference) + set_recursivescan_pathlist(root, rel, rte); + else + set_recursion_pathlist(root, rel, rti, rte); + } else { /* Plain relation */ *************** *** 641,646 **** --- 652,781 ---- } /* + * 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; + Query *subquery = rte->subquery; + bool *differentTypes; + double tuple_fraction; + PlannerInfo *subroot; + List *pathkeys; + + /* We need a workspace for keeping track of set-op type coercions */ + differentTypes = (bool *) + palloc0((list_length(subquery->targetList) + 1) * sizeof(bool)); + + /* + * If there are any restriction clauses that have been attached to the + * subquery relation, consider pushing them down to become WHERE or HAVING + * quals of the subquery itself. This transformation is useful because it + * may allow us to generate a better plan for the subquery than evaluating + * all the subquery output rows and then filtering them. + * + * There are several cases where we cannot push down clauses. Restrictions + * involving the subquery are checked by subquery_is_pushdown_safe(). + * Restrictions on individual clauses are checked by + * qual_is_pushdown_safe(). Also, we don't want to push down + * pseudoconstant clauses; better to have the gating node above the + * subquery. + * + * Non-pushed-down clauses will get evaluated as qpquals of the + * SubqueryScan node. + * + * XXX Are there any cases where we want to make a policy decision not to + * push down a pushable qual, because it'd result in a worse plan? + */ + if (rel->baserestrictinfo != NIL && + subquery_is_pushdown_safe(subquery, subquery, differentTypes)) + { + /* OK to consider pushing down individual quals */ + List *upperrestrictlist = NIL; + ListCell *l; + + foreach(l, rel->baserestrictinfo) + { + RestrictInfo *rinfo = (RestrictInfo *) lfirst(l); + Node *clause = (Node *) rinfo->clause; + + if (!rinfo->pseudoconstant && + qual_is_pushdown_safe(subquery, rti, clause, differentTypes)) + { + /* Push it down */ + subquery_push_qual(subquery, rte, rti, clause); + } + else + { + /* Keep it in the upper query */ + upperrestrictlist = lappend(upperrestrictlist, rinfo); + } + } + rel->baserestrictinfo = upperrestrictlist; + } + + pfree(differentTypes); + + /* + * 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 plan for the subquery */ + rel->subplan = subquery_planner(root->glob, subquery, + root->query_level + 1, + 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 */ + 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. * *************** *** 950,967 **** * * Conditions checked here: * ! * 1. The qual must not contain any subselects (mainly because I'm not sure * it will work correctly: sublinks will already have been transformed into * subplans in the qual, but not in the subquery). * ! * 2. The qual must not refer to the whole-row output of the subquery * (since there is no easy way to name that within the subquery itself). * ! * 3. The qual must not refer to any subquery output columns that were * found to have inconsistent types across a set operation tree by * subquery_is_pushdown_safe(). * ! * 4. If the subquery uses DISTINCT ON, we must not push down any quals that * refer to non-DISTINCT output columns, because that could change the set * of rows returned. (This condition is vacuous for DISTINCT, because then * there are no non-DISTINCT output columns, so we needn't check. But note --- 1085,1104 ---- * * Conditions checked here: * ! * 1. If the subquery is recursively, we must not push down any quals. ! * ! * 2. The qual must not contain any subselects (mainly because I'm not sure * it will work correctly: sublinks will already have been transformed into * subplans in the qual, but not in the subquery). * ! * 3. The qual must not refer to the whole-row output of the subquery * (since there is no easy way to name that within the subquery itself). * ! * 4. The qual must not refer to any subquery output columns that were * found to have inconsistent types across a set operation tree by * subquery_is_pushdown_safe(). * ! * 5. If the subquery uses DISTINCT ON, we must not push down any quals that * refer to non-DISTINCT output columns, because that could change the set * of rows returned. (This condition is vacuous for DISTINCT, because then * there are no non-DISTINCT output columns, so we needn't check. But note *************** *** 970,980 **** * for the case, and it's unlikely enough that we shouldn't refuse the * optimization just because it could theoretically happen.) * ! * 5. We must not push down any quals that refer to subselect outputs that * return sets, else we'd introduce functions-returning-sets into the * subquery's WHERE/HAVING quals. * ! * 6. We must not push down any quals that refer to subselect outputs that * contain volatile functions, for fear of introducing strange results due * to multiple evaluation of a volatile function. */ --- 1107,1117 ---- * for the case, and it's unlikely enough that we shouldn't refuse the * optimization just because it could theoretically happen.) * ! * 6. We must not push down any quals that refer to subselect outputs that * return sets, else we'd introduce functions-returning-sets into the * subquery's WHERE/HAVING quals. * ! * 7. We must not push down any quals that refer to subselect outputs that * contain volatile functions, for fear of introducing strange results due * to multiple evaluation of a volatile function. */ *************** *** 987,993 **** ListCell *vl; Bitmapset *tested = NULL; ! /* Refuse subselects (point 1) */ if (contain_subplans(qual)) return false; --- 1124,1134 ---- ListCell *vl; Bitmapset *tested = NULL; ! /* Recursive query (point 1) */ ! if (subquery->recursive == true) ! return false; ! ! /* Refuse subselects (point 2) */ if (contain_subplans(qual)) return false; *************** *** 1003,1009 **** Assert(var->varno == rti); ! /* Check point 2 */ if (var->varattno == 0) { safe = false; --- 1144,1150 ---- Assert(var->varno == rti); ! /* Check point 3 */ if (var->varattno == 0) { safe = false; *************** *** 1019,1025 **** continue; tested = bms_add_member(tested, var->varattno); ! /* Check point 3 */ if (differentTypes[var->varattno]) { safe = false; --- 1160,1166 ---- continue; tested = bms_add_member(tested, var->varattno); ! /* Check point 4 */ if (differentTypes[var->varattno]) { safe = false; *************** *** 1040,1053 **** break; } ! /* Refuse functions returning sets (point 5) */ if (expression_returns_set((Node *) tle->expr)) { safe = false; break; } ! /* Refuse volatile functions (point 6) */ if (contain_volatile_functions((Node *) tle->expr)) { safe = false; --- 1181,1194 ---- break; } ! /* Refuse functions returning sets (point 6) */ if (expression_returns_set((Node *) tle->expr)) { safe = false; break; } ! /* Refuse volatile functions (point 7) */ if (contain_volatile_functions((Node *) tle->expr)) { safe = false; *************** *** 1230,1235 **** --- 1371,1379 ---- ptype = "HashJoin"; join = true; break; + case T_Recursion: + ptype = "Recursion"; + break; default: ptype = "???Path"; break; *** pgsql/src/backend/optimizer/path/costsize.c 2008-09-06 06:07:29.000000000 +0900 --- pgsql.patched/src/backend/optimizer/path/costsize.c 2008-09-07 23:47:33.000000000 +0900 *************** *** 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_RECURSIVE); + + /* + * 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_RECURSIVE); + + /* + * 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_RECURSIVE); + + /* Now estimate number of output rows, etc */ + set_baserel_size_estimates(root, rel); + } + /* * set_rel_width *** pgsql/src/backend/optimizer/plan/createplan.c 2008-09-06 06:07:29.000000000 +0900 --- pgsql.patched/src/backend/optimizer/plan/createplan.c 2008-09-07 23:47:33.000000000 +0900 *************** *** 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); *************** *** 329,335 **** if (rel->rtekind != RTE_RELATION && rel->rtekind != RTE_SUBQUERY && rel->rtekind != RTE_FUNCTION && ! rel->rtekind != RTE_VALUES) return false; /* --- 356,363 ---- if (rel->rtekind != RTE_RELATION && rel->rtekind != RTE_SUBQUERY && rel->rtekind != RTE_FUNCTION && ! rel->rtekind != RTE_VALUES && ! rel->rtekind != RTE_RECURSIVE) return false; /* *************** *** 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_RECURSIVE); + + /* 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_RECURSIVE); + + /* 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) { *** pgsql/src/backend/optimizer/plan/setrefs.c 2008-08-26 07:42:33.000000000 +0900 --- pgsql.patched/src/backend/optimizer/plan/setrefs.c 2008-09-07 23:47:33.000000000 +0900 *************** *** 336,342 **** --- 336,369 ---- 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: *** pgsql/src/backend/optimizer/plan/subselect.c 2008-08-29 08:09:46.000000000 +0900 --- pgsql.patched/src/backend/optimizer/plan/subselect.c 2008-09-07 23:47:33.000000000 +0900 *************** *** 1798,1803 **** --- 1798,1805 ---- case T_Unique: case T_SetOp: case T_Group: + case T_Recursion: + case T_RecursiveScan: break; default: *** pgsql/src/backend/optimizer/prep/prepunion.c 2008-08-29 08:09:46.000000000 +0900 --- pgsql.patched/src/backend/optimizer/prep/prepunion.c 2008-09-07 23:47:33.000000000 +0900 *************** *** 1083,1089 **** /* Ignore any already-expanded UNION ALL nodes */ if (rte->rtekind != RTE_RELATION) { ! Assert(rte->rtekind == RTE_SUBQUERY); return; } /* Fast path for common case of childless table */ --- 1083,1089 ---- /* Ignore any already-expanded UNION ALL nodes */ if (rte->rtekind != RTE_RELATION) { ! Assert(rte->rtekind == RTE_SUBQUERY || rte->rtekind == RTE_RECURSIVE); return; } /* Fast path for common case of childless table */ *** pgsql/src/backend/optimizer/util/pathnode.c 2008-09-06 06:07:29.000000000 +0900 --- pgsql.patched/src/backend/optimizer/util/pathnode.c 2008-09-07 23:47:33.000000000 +0900 *************** *** 1220,1225 **** --- 1220,1264 ---- } /* + * create_subqueryscan_path + * Creates a path corresponding to a sequential scan of a subquery, + * 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. *** pgsql/src/backend/optimizer/util/plancat.c 2008-09-02 05:42:44.000000000 +0900 --- pgsql.patched/src/backend/optimizer/util/plancat.c 2008-09-07 23:47:33.000000000 +0900 *************** *** 772,777 **** --- 772,801 ---- } break; + case RTE_RECURSIVE: + subquery = rte->non_recursive_query; + foreach(l, subquery->targetList) + { + TargetEntry *tle = (TargetEntry *) lfirst(l); + + /* + * A resjunk column of the subquery can be reflected as + * resjunk in the physical tlist; we need not punt. + */ + var = makeVar(varno, + tle->resno, + exprType((Node *) tle->expr), + exprTypmod((Node *) tle->expr), + 0); + + tlist = lappend(tlist, + makeTargetEntry((Expr *) var, + tle->resno, + NULL, + tle->resjunk)); + } + break; + default: /* caller error */ elog(ERROR, "unsupported RTE kind %d in build_physical_tlist", *** pgsql/src/backend/optimizer/util/relnode.c 2008-08-15 03:47:59.000000000 +0900 --- pgsql.patched/src/backend/optimizer/util/relnode.c 2008-09-07 23:47:33.000000000 +0900 *************** *** 101,106 **** --- 101,107 ---- case RTE_SUBQUERY: case RTE_FUNCTION: case RTE_VALUES: + case RTE_RECURSIVE: /* * Subquery, function, or values list --- set up attr range and *** pgsql/src/backend/parser/Makefile 2008-08-29 22:02:32.000000000 +0900 --- pgsql.patched/src/backend/parser/Makefile 2008-09-07 23:47:33.000000000 +0900 *************** *** 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 *** pgsql/src/backend/parser/analyze.c 2008-09-02 05:42:44.000000000 +0900 --- pgsql.patched/src/backend/parser/analyze.c 2008-09-07 23:47:33.000000000 +0900 *************** *** 694,699 **** --- 694,703 ---- /* make FOR UPDATE/FOR SHARE info available to addRangeTableEntry */ pstate->p_locking_clause = stmt->lockingClause; + /* process the WITH clause (pull CTEs into the pstate's ctenamespace) */ + if (stmt->withClause) + transformWithClause(pstate, stmt->withClause); + /* process the FROM clause */ transformFromClause(pstate, stmt->fromClause); *************** *** 1059,1064 **** --- 1063,1072 ---- (errcode(ERRCODE_FEATURE_NOT_SUPPORTED), errmsg("SELECT FOR UPDATE/SHARE is not allowed with UNION/INTERSECT/EXCEPT"))); + /* process the WITH clause (pull CTEs into the pstate's ctenamespace) */ + if (stmt->withClause) + transformWithClause(pstate, stmt->withClause); + /* * Recursively transform the components of the tree. */ *** pgsql/src/backend/parser/gram.y 2008-09-03 05:37:54.000000000 +0900 --- pgsql.patched/src/backend/parser/gram.y 2008-09-07 23:47:33.000000000 +0900 *************** *** 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_expression + %type with_cte_list + %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 *************** *** 6259,6279 **** | 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: --- 6265,6316 ---- | 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_cte_list simple_select + { + insertSelectOptions((SelectStmt *) $2, + NULL, NIL, + NULL, NULL, + $1); + $$ = $2; + } + | with_cte_list select_clause sort_clause + { + insertSelectOptions((SelectStmt *) $2, $3, NIL, + NULL, NULL, + $1); + $$ = $2; + } + | with_cte_list 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_cte_list 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: *************** *** 6334,6339 **** --- 6371,6417 ---- } ; + /* + * ANSI standard WITH clause looks like: + * + * WITH [ RECURSIVE ] [ (,...) ] + * AS (query) [ SEARCH or CYCLE clause ] + * + * We don't currently support the SEARCH or CYCLE clause. + */ + with_cte_list: + WITH cte_list + { + $$ = makeNode(WithClause); + $$->recursive = false; + $$->subquery = $2; + } + | WITH RECURSIVE cte_list + { + $$ = makeNode(WithClause); + $$->recursive = true; + $$->subquery = $3; + } + ; + + cte_list: + common_table_expression { $$ = list_make1($1); } + | cte_list ',' common_table_expression { $$ = lappend($1, $3); } + ; + + common_table_expression: name opt_name_list AS select_with_parens + { + RangeSubselect *n = makeNode(RangeSubselect); + + n->subquery = $4; + n->alias = makeNode(Alias); + n->alias->aliasname = $1; + n->alias->colnames = $2; + + $$ = (Node *) n; + } + ; + into_clause: INTO OptTempTableName { *************** *** 9327,9333 **** | VIEW | VOLATILE | WHITESPACE_P - | WITH | WITHOUT | WORK | WRITE --- 9405,9410 ---- *************** *** 9510,9515 **** --- 9587,9593 ---- | VARIADIC | WHEN | WHERE + | WITH ; *************** *** 9833,9840 **** 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 --- 9911,9921 ---- 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 *************** *** 9868,9873 **** --- 9949,9962 ---- scanner_errposition(exprLocation(limitCount)))); stmt->limitCount = limitCount; } + if (withClause) + { + if (stmt->withClause) + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + errmsg("multiple WITH clauses not allowed"))); + stmt->withClause = withClause; + } } static Node * *** pgsql/src/backend/parser/keywords.c 2008-08-29 22:02:32.000000000 +0900 --- pgsql.patched/src/backend/parser/keywords.c 2008-09-07 23:47:33.000000000 +0900 *************** *** 304,309 **** --- 304,310 ---- {"real", REAL, COL_NAME_KEYWORD}, {"reassign", REASSIGN, UNRESERVED_KEYWORD}, {"recheck", RECHECK, UNRESERVED_KEYWORD}, + {"recursive", RECURSIVE, RESERVED_KEYWORD}, {"references", REFERENCES, RESERVED_KEYWORD}, {"reindex", REINDEX, UNRESERVED_KEYWORD}, {"relative", RELATIVE_P, UNRESERVED_KEYWORD}, *** pgsql/src/backend/parser/parse_clause.c 2008-09-02 05:42:44.000000000 +0900 --- pgsql.patched/src/backend/parser/parse_clause.c 2008-09-07 23:47:33.000000000 +0900 *************** *** 27,32 **** --- 27,33 ---- #include "parser/parsetree.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" *************** *** 58,63 **** --- 59,66 ---- RangeSubselect *r); static RangeTblEntry *transformRangeFunction(ParseState *pstate, RangeFunction *r); + static RangeTblEntry *transformRangeRecursive(ParseState *pstate, + RangeVar *n, RangeRecursive *r); static Node *transformFromClauseItem(ParseState *pstate, Node *n, RangeTblEntry **top_rte, int *top_rti, List **relnamespace, *************** *** 77,82 **** --- 80,165 ---- /* + * transformWithClause - + * Transform the list of WITH clause "common table expressions" into + * Query nodes. + * + * We need to add the name of the common table expression to a list that is + * used later to find them. But we do _not_ add the table itself to the current + * namespace because that would implicitly join all of them which isn't right. + */ + void + transformWithClause(ParseState *pstate, WithClause *withClause) + { + ListCell *lc; + RangeRecursive *new_cte; + + if (withClause->recursive) + { + /* register recursive cte names */ + foreach(lc, withClause->subquery) + { + RangeSubselect *cte = lfirst(lc); + + new_cte = makeNode(RangeRecursive); + new_cte->subquery = (Node *)cte->subquery; + new_cte->alias = copyObject(cte->alias); + + /* + * Check if CTE name has already registered. + */ + checkCteNameSpaceConflicts(pstate->p_recursive_namespace, cte); + + pstate->p_recursive_namespace = lappend(pstate->p_recursive_namespace, new_cte); + } + + /* + * Check well-formed subquery. + */ + checkWellFormedCte(pstate, withClause); + + foreach(lc, pstate->p_recursive_namespace) + { + RangeRecursive *cte = lfirst(lc); + if (IsA(cte->subquery, SelectStmt)) + cte->subquery = (Node*) parse_sub_analyze(cte->subquery, pstate); + } + return; + } + + foreach(lc, withClause->subquery) + { + RangeSubselect *cte = lfirst(lc); + RangeSubselect *new_cte; + Query *query; + + query = parse_sub_analyze(cte->subquery, pstate); + + /* 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"))); + + new_cte = makeNode(RangeSubselect); + new_cte->subquery = (Node*) query; + new_cte->alias = copyObject(cte->alias); + + /* + * Check if CTE name has already registered. + */ + if (!withClause->recursive) + { + checkCteNameSpaceConflicts(pstate->p_ctenamespace, new_cte); + pstate->p_ctenamespace = lappend(pstate->p_ctenamespace, new_cte); + } + } + } + + /* * transformFromClause - * Process the FROM clause and add items to the query's range table, * joinlist, and namespaces. *************** *** 422,427 **** --- 505,559 ---- return rte; } + /* + * transformRangeCTE --- transform a RangeVar which references a common table + * expression (ie, a sub-SELECT defined in a WITH clause) + */ + static RangeTblEntry * + transformRangeCTE(ParseState *pstate, RangeVar *n, RangeSubselect *r) + { + RangeTblEntry *rte; + + /* + * Unlike transformRangeSubselect we do not have to worry about: + * + * . checking for an alias because the grammar for WITH always gives us an + * alias + * + * . transforming the subquery as transformWithClause has already done that + * and the RangeSubselect contains the query tree, not the raw parse tree + * + * . checking for lateral references since WITH subqueries have their own + * scope. Since they were transformed prior to any range table entries + * being created in our pstate they were all planned with a fresh copy of + * our empty pstate (unless we're in a subquery already of course). + */ + + /* + * This is a kluge for now. Effectively we're inlining all the WITH + * clauses which isn't what we want to do + */ + + /* + * One tricky bit. We potentially have two aliases here. The WITH clause + * always specifies a relation alias and may or may not specify column + * aliases. The rangevar also may or may not specify a relation alias + * and may or may not specify column aliases. + */ + + Alias *a = copyObject(r->alias); + if (n->alias && n->alias->aliasname) + a->aliasname = n->alias->aliasname; + if (n->alias && n->alias->colnames) + a->colnames = n->alias->colnames; + + /* + * OK, build an RTE for the subquery. + */ + rte = addRangeTableEntryForSubquery(pstate, (Query*) r->subquery, a, true); + + return rte; + } /* * transformRangeSubselect --- transform a sub-SELECT appearing in FROM *************** *** 575,580 **** --- 707,738 ---- } + static RangeTblEntry * + transformRangeRecursive(ParseState *pstate, RangeVar *n, RangeRecursive *r) + { + RangeTblEntry *rte; + Alias *a = copyObject(r->alias); + + Assert(r->alias != NULL); + + if (n->alias && n->alias->aliasname) + a->aliasname = n->alias->aliasname; + if (n->alias && n->alias->colnames) + a->colnames = n->alias->colnames; + + /* + * OK, build an RTE for the subquery. + */ + + if (r->recursive == true) + rte = addRangeTableEntryForRecursive(pstate, (Query *) r->subquery, (Query *) r->non_recursive_term, a, true); + else + rte = addRangeTableEntryForSubquery(pstate, (Query *) r->subquery, a, true); + + return rte; + } + + /* * transformFromClauseItem - * Transform a FROM-clause item, adding any required entries to the *************** *** 610,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)); --- 768,818 ---- if (IsA(n, RangeVar)) { /* Plain relation reference */ + RangeVar *rv = (RangeVar *) n; RangeTblRef *rtr; ! RangeTblEntry *rte = NULL; int rtindex; ! if (!rv->schemaname) ! { ! /* ! * We have to check if this is a reference to a common table ! * expression (ie subquery defined in the WITH clause). Either ! * in this query or any parent query. ! */ ! ParseState *ps; ! ListCell *lc; ! bool found = false; ! ! for (ps = pstate; ps; ps = ps->parentParseState) ! { ! foreach(lc, ps->p_ctenamespace) ! { ! RangeSubselect *r = (RangeSubselect *) lfirst(lc); ! if (strcmp(rv->relname, r->alias->aliasname) == 0) ! { ! rte = transformRangeCTE(pstate, rv, r); ! found = true; ! break; ! } ! } ! ! foreach(lc, ps->p_recursive_namespace) ! { ! RangeRecursive *r = (RangeRecursive *) lfirst(lc); ! if (strcmp(rv->relname, r->alias->aliasname) == 0) ! { ! rte = transformRangeRecursive(pstate, rv, r); ! found = true; ! break; ! } ! } ! } ! } ! ! 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)); *** pgsql/src/backend/parser/parse_cte.c 1970-01-01 09:00:00.000000000 +0900 --- pgsql.patched/src/backend/parser/parse_cte.c 2008-09-07 23:47:33.000000000 +0900 *************** *** 0 **** --- 1,674 ---- + /*------------------------------------------------------------------------- + * + * parse_cte.c + * handle cte(common table expression) 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/makefuncs.h" + #include "parser/analyze.h" + #include "parser/parsetree.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" + + typedef struct CteNode CteNode; + struct CteNode { + int id; + RangeRecursive *subquery; + List *depend_list; + }; + + typedef enum RecursiveType + { + NON_RECURSIVE, + RECURSIVE_SELF, + RECURSIVE_OTHER + } RecursiveType; + + /* Dependency collector functions */ + static void makeDependFromCteName(ParseState *pstate, CteNode *node, int index, char *name, char *myname); + static void makeDependFromTargetList(ParseState *pstate, CteNode *node, int index, List *targetList, char *name); + static void makeDependFromFromClause(ParseState *pstate, CteNode *node, int index, List *fromClause, char *name); + static void makeDependFromSelectStmt(ParseState *pstate, CteNode *node, int index, SelectStmt *stmt, char *name); + static void TopologicalSort(CteNode *nodes, int len); + + /* Checker function */ + static RecursiveType checkCteSelectStmt(ParseState *pstate, SelectStmt *n, char *myname); + static RecursiveType checkCteTargetList(ParseState *pstate, List *targetList, char *myname); + static RecursiveType checkCteTargetListItem(ParseState *pstate, Node *target, char *myname); + static RecursiveType checkCteFromClause(ParseState *pstate, List *fromClause, char *myname); + static RecursiveType checkWhereClause(ParseState *pstate, Node *n, char *myname); + static RecursiveType checkCteFromClauseItem(ParseState *pstate, Node *n, char *myname); + static RecursiveType duplicateCteName(List *namespace, char *name, char *myname, bool check_non_recursive); + + static Query *non_recursive_term; + + static void makeDependFromCteName(ParseState *pstate, CteNode *node, int index, char *name, char *myname) + { + ListCell *l1; + int i = 0, j, len = list_length(pstate->p_recursive_namespace); + + foreach(l1, pstate->p_recursive_namespace) + { + RangeSubselect *cte = (RangeSubselect *) lfirst(l1); + const char *aliasname1 = cte->alias->aliasname; + + if (strcmp(name, aliasname1) != 0) + continue; /* definitely no conflict */ + + /* Add dependency */ + if (strcmp(name, myname) != 0) + { + for (j = 0; j < len; j++) + if (strcmp(node[j].subquery->alias->aliasname, myname) == 0) + break; + + /* Check if name has already registered */ + if (!list_member_int(node[j].depend_list, i)) + node[j].depend_list = lappend_int(node[j].depend_list, i); + elog(DEBUG1, "Cte name dependency: %s(%d) -> %s(%d)", myname, j, name, i); + break; + } + + i++; + } + } + + static void makeDependFromTargetList(ParseState *pstate, CteNode *node, int index, List *targetList, char *name) + { + ListCell *lc; + + foreach (lc, targetList) + { + Node *n = (Node *)lfirst(lc); + + 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 makeDependFromSelectStmt(pstate, node, index, (SelectStmt *) sl->subselect, name); + } + } + } + } + + static void makeDependFromFromClauseItem(ParseState *pstate, CteNode *node, int index, Node *n, char *name) + { + if (IsA(n, RangeVar)) /* table reference */ + { + RangeVar *rv = (RangeVar *)n; + if (!rv->schemaname) + makeDependFromCteName(pstate, node, index, rv->relname, name); + } + else if (IsA(n, RangeSubselect)) + { + RangeSubselect *rs = (RangeSubselect *)n; + + makeDependFromSelectStmt(pstate, node, index, (SelectStmt *)rs->subquery, name); + } + else if (IsA(n, RangeFunction)) + { + /* do nothing */ + } + else if (IsA(n, JoinExpr)) + { + JoinExpr *je = (JoinExpr *) n; + + makeDependFromFromClauseItem(pstate, node, index, je->larg, name); + makeDependFromFromClauseItem(pstate, node, index, je->rarg, name); + } + + else + elog(ERROR, "unrecognized node type: %d", (int) nodeTag(n)); + } + + static void makeDependFromFromClause(ParseState *pstate, CteNode *node, int index, List *fromClause, char *name) + { + ListCell *lc; + + foreach(lc, fromClause) + makeDependFromFromClauseItem(pstate, node, index, (Node *)lfirst(lc), name); + } + + static void makeDependFromSelectStmt(ParseState *pstate, CteNode *node, int index, SelectStmt *stmt, char *name) + { + if (stmt->op == SETOP_NONE) + { + if (stmt->targetList) + makeDependFromTargetList(pstate, node, index, stmt->targetList, name); + + if (stmt->fromClause) + makeDependFromFromClause(pstate, node, index, stmt->fromClause, name); + + if (stmt->whereClause) + ; + } + else + { + SelectStmt *larg = (SelectStmt *)stmt->larg; + SelectStmt *rarg = (SelectStmt *)stmt->rarg; + + makeDependFromSelectStmt(pstate, node, index, larg, name); + makeDependFromSelectStmt(pstate, node, index, rarg, name); + } + } + + static List *makeDependencyGraph(ParseState *pstate, CteNode *nodes, List *recursive_namespace) + { + List *list; + ListCell *lc; + int i = 0; + + /* initialize */ + i = 0; + foreach(lc, recursive_namespace) + { + nodes[i].subquery = (RangeRecursive *)lfirst(lc); + i++; + } + + i = 0; + foreach(lc, recursive_namespace) + { + RangeRecursive *rr = (RangeRecursive *)lfirst(lc); + + makeDependFromSelectStmt(pstate, nodes, i, (SelectStmt *)rr->subquery, rr->alias->aliasname); + } + + TopologicalSort(nodes, list_length(pstate->p_recursive_namespace)); + + /* Reconstruct pstate->p_recursive_namespace order by topological sort. */ + list = list_make1(nodes[0].subquery); + for (i = 1; i < list_length(pstate->p_recursive_namespace); i++) + { + list = lappend(list, nodes[i].subquery); + } + + return list; + } + + /* Sort by dependency */ + static void TopologicalSort(CteNode *nodes, int len) + { + int i, j, k; + CteNode tmp; + + for (i = 0; i < len; i++) + { + for (j = i; j < len; j++) + { + if (nodes[j].depend_list == NULL || + list_length(nodes[j].depend_list) == 0) + { + for (k = 0; k < len; k++) + nodes[k].depend_list = list_delete_int(nodes[k].depend_list, i); + + elog(DEBUG1, "swap %d <--> %d", i, j); + + /* swap */ + if (i == j) + break; + + memcpy(&tmp, &nodes[i], sizeof(CteNode)); + memcpy(&nodes[i], &nodes[j], sizeof(CteNode)); + memcpy(&nodes[j], &tmp, sizeof(CteNode)); + + break; + } + + } + + /* If this condition is true, the dependency graph has cycle */ + if (j == len) + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + errmsg("mutual recursive call is not supported"))); + } + } + + void checkWellFormedCte(ParseState *pstate, WithClause *withClause) + { + ListCell *lc; + CteNode *nodes; + int i; + Size size; + + if (list_length(pstate->p_recursive_namespace) > 1) + { + /* initialize dependency graph */ + size = list_length(pstate->p_recursive_namespace); + nodes = palloc(size * sizeof(CteNode)); + MemSet(nodes, 0, size * sizeof(CteNode)); + for (i = 0; i < size; i++) + nodes[i].id = i; + + pstate->p_recursive_namespace = makeDependencyGraph(pstate, nodes, pstate->p_recursive_namespace); + } + + i = 0; + foreach(lc, pstate->p_recursive_namespace) + { + RangeRecursive *cte = lfirst(lc); + SelectStmt *stmt = (SelectStmt *)cte->subquery; + + if (stmt->op == SETOP_NONE) + { + RecursiveType r = NON_RECURSIVE; + + r = checkCteSelectStmt(pstate, stmt, cte->alias->aliasname); + if (r != NON_RECURSIVE) + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + errmsg("recursive query must have a non-recursive term"))); + + if (non_recursive_term) + cte->non_recursive_term = copyObject(non_recursive_term); + else + { + cte->subquery = (Node *)parse_sub_analyze(cte->subquery, pstate); + cte->recursive = false; + } + non_recursive_term = NULL; + } + else + { + SelectStmt *larg = (SelectStmt *)stmt->larg; + SelectStmt *rarg = (SelectStmt *)stmt->rarg; + RecursiveType lresult = NON_RECURSIVE, rresult = NON_RECURSIVE; + + lresult = checkCteSelectStmt(pstate, larg, cte->alias->aliasname); + rresult = checkCteSelectStmt(pstate, rarg, cte->alias->aliasname); + + /* Check if a query is a recursive query */ + if (lresult == NON_RECURSIVE && rresult == NON_RECURSIVE) + { + if (non_recursive_term) + { + cte->non_recursive_term = copyObject(non_recursive_term); + } + else + { + cte->subquery = (Node *)parse_sub_analyze(cte->subquery, pstate); + cte->recursive = false; + } + non_recursive_term = NULL; + } + else if (lresult == RECURSIVE_OTHER || rresult == RECURSIVE_OTHER) + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + errmsg("mutual recursive call is not supported"))); + /* + * 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) + { + ListCell *lc; + + 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"))); + + /* check AGGREGATE(*) */ + foreach (lc, rarg->targetList) + { + Node *n = lfirst(lc); + + if (IsA(n, ResTarget)) + { + ResTarget *rt = (ResTarget *) n; + if (rt->val && IsA(rt->val, FuncCall)) + { + FuncCall *fc = (FuncCall *) lfirst(lc); + if (fc->agg_star) + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + errmsg("aggregate functions in a recursive term not allowed"))); + } + } + } + + /* + * Analyze non_recursive_term. + */ + if (non_recursive_term) + cte->non_recursive_term = copyObject(non_recursive_term); + else + cte->non_recursive_term = (Node *) parse_sub_analyze(copyObject(larg), pstate); + cte->recursive = true; + non_recursive_term = NULL; + } + + else + elog(ERROR, "unknown error in checkWellFormedCte"); + } + i++; + } + } + + static RecursiveType checkCteSelectStmt(ParseState *pstate, SelectStmt *n, char *myname) + { + RecursiveType r = NON_RECURSIVE; + + if (n->op == SETOP_UNION) + { + RecursiveType r1, r2; + + r1 = checkCteSelectStmt(pstate, n->larg, myname); + r2 = checkCteSelectStmt(pstate, n->rarg, myname); + + 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(pstate, n->targetList, myname) != 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(pstate, n->fromClause, myname); + + if (n->whereClause) + { + /* Cannot contain any recursive names in WHERE-clause */ + if (checkWhereClause(pstate, n->whereClause, myname) != 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(ParseState *pstate, List *targetList, char *myname) + { + ListCell *lc; + RecursiveType result = NON_RECURSIVE; + + foreach(lc, targetList) + { + RecursiveType r; + r = checkCteTargetListItem(pstate, lfirst(lc), myname); + 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(ParseState *pstate, Node *n, char *myname) + { + 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(pstate, (SelectStmt *) sl->subselect, myname); + } + } + + return NON_RECURSIVE; + } + + static RecursiveType checkWhereClause(ParseState *pstate, Node *n, char *myname) + { + if (IsA(n, SubLink)) + return checkCteSelectStmt(pstate, (SelectStmt *) ((SubLink *) n)->subselect, myname); + else if (IsA(n, A_Expr)) + { + RecursiveType result; + A_Expr *expr = (A_Expr *)n; + + if (expr->lexpr && IsA(expr->lexpr, SubLink)) + { + result = checkWhereClause(pstate, (Node *) expr->lexpr, myname); + if (result != NON_RECURSIVE) + return result; + } + if (expr->rexpr && IsA(expr->rexpr, SubLink)) + { + result = checkWhereClause(pstate, (Node *) expr->rexpr, myname); + if (result != NON_RECURSIVE) + return result; + } + } + + return NON_RECURSIVE; + } + + /* + * checkCteFromClause + */ + static RecursiveType checkCteFromClause(ParseState *pstate, List *fromClause, char *myname) + { + ListCell *lc; + RecursiveType result = NON_RECURSIVE; + + foreach(lc, fromClause) + { + RecursiveType r; + r = checkCteFromClauseItem(pstate, lfirst(lc), myname); + if (result == NON_RECURSIVE) + result = r; + else if (result == RECURSIVE_SELF && r == RECURSIVE_OTHER) + result = r; + } + return result; + } + + static RecursiveType checkCteFromClauseItem(ParseState *pstate, Node *n, char *myname) + { + if (IsA(n, RangeVar)) /* table reference */ + { + RangeVar *rv = (RangeVar *)n; + if (rv->schemaname) + return NON_RECURSIVE; + + return duplicateCteName(pstate->p_recursive_namespace, rv->relname, myname, true); + } + else if (IsA(n, RangeSubselect)) + { + RangeSubselect *rs = (RangeSubselect *)n; + + return checkCteSelectStmt(pstate, (SelectStmt *)rs->subquery, myname); + } + 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(pstate, je->larg, myname); + rarg = checkCteFromClauseItem(pstate, je->rarg, myname); + + /* 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; + } + + /* + * Check for common-table-expression-name conflicts between + * ctenamespace lists and new cte item. Raise an error if any is found. + */ + void + checkCteNameSpaceConflicts(List *namespace, RangeSubselect *new_cte) + { + if (duplicateCteName(namespace, new_cte->alias->aliasname, new_cte->alias->aliasname, false) != NON_RECURSIVE) + ereport(ERROR, + (errcode(ERRCODE_DUPLICATE_ALIAS), + errmsg("common table expression name \"%s\" specified more than once", + new_cte->alias->aliasname))); + } + + static RecursiveType + duplicateCteName(List *namespace, char *name, char *myname, bool check_non_recursive) + { + ListCell *l1; + + foreach(l1, namespace) + { + RangeSubselect *cte = (RangeSubselect *) lfirst(l1); + const char *aliasname1 = cte->alias->aliasname; + + if (strcmp(name, aliasname1) != 0) + continue; /* definitely no conflict */ + + if (strcmp(name, myname) == 0) + return RECURSIVE_SELF; + + if (check_non_recursive) + { + RangeRecursive *rte = (RangeRecursive *)cte; + + /* + * If the RTE has a non-recursive term, we can handle it as non-recursive query. + */ + if (rte->non_recursive_term) + { + if (non_recursive_term == NULL) + non_recursive_term = (Query *) rte->non_recursive_term; + return NON_RECURSIVE; + } + + if (rte->recursive == false) + return NON_RECURSIVE; + } + + return RECURSIVE_OTHER; + } + return NON_RECURSIVE; + } *** pgsql/src/backend/parser/parse_relation.c 2008-09-02 05:42:44.000000000 +0900 --- pgsql.patched/src/backend/parser/parse_relation.c 2008-09-07 23:47:33.000000000 +0900 *************** *** 1109,1114 **** --- 1109,1203 ---- } /* + * Add an entry for a WITH RECURSIVE query to the pstate's range table (p_rtable). + * + * This is just like addRangeTableEntry() except that it makes a recursive RTE. + * Note that an alias clause *must* be supplied. + */ + RangeTblEntry * + addRangeTableEntryForRecursive(ParseState *pstate, + Query *query, + Query *non_recursive_term, + Alias *alias, + bool inFromCl) + + { + RangeTblEntry *rte = makeNode(RangeTblEntry); + char *refname = alias->aliasname; + Alias *eref; + int numaliases; + int varattno; + ListCell *tlistitem; + + rte->rtekind = RTE_RECURSIVE; + rte->relid = InvalidOid; + if (IsA(query, Query)) + { + query->recursive = true; + rte->subquery = copyObject(query); + } + else + rte->self_reference = true; + rte->alias = alias; + rte->non_recursive_query = non_recursive_term; + + eref = copyObject(alias); + numaliases = list_length(eref->colnames); + + /* fill in any unspecified alias columns */ + varattno = 0; + foreach(tlistitem, non_recursive_term->targetList) + { + TargetEntry *te = (TargetEntry *) lfirst(tlistitem); + + if (te->resjunk) + continue; + varattno++; + Assert(varattno == te->resno); + if (varattno > numaliases) + { + char *attrname; + + attrname = pstrdup(te->resname); + eref->colnames = lappend(eref->colnames, makeString(attrname)); + } + } + 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 **** --- 1533,1577 ---- } } break; + case RTE_RECURSIVE: + { + /* Recursive RTE */ + ListCell *aliasp_item = list_head(rte->eref->colnames); + ListCell *tlistitem; + + varattno = 0; + foreach(tlistitem, rte->non_recursive_query->targetList) + { + TargetEntry *te = (TargetEntry *) lfirst(tlistitem); + + if (te->resjunk) + continue; + varattno++; + Assert(varattno == te->resno); + + if (colnames) + { + /* Assume there is one alias per target item */ + 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, + exprType((Node *) te->expr), + exprTypmod((Node *) te->expr), + sublevels_up); + + *colvars = lappend(*colvars, varnode); + } + } + } + break; default: elog(ERROR, "unrecognized RTE kind: %d", (int) rte->rtekind); } *************** *** 1750,1755 **** --- 1878,1896 ---- *vartypmod = exprTypmod(aliasvar); } break; + case RTE_RECURSIVE: + { + /* Subselect RTE --- get type info from subselect's tlist */ + TargetEntry *te = get_tle_by_resno(rte->non_recursive_query->targetList, + attnum); + + if (te == NULL || te->resjunk) + elog(ERROR, "subquery %s does not have attribute %d", + rte->eref->aliasname, attnum); + *vartype = exprType((Node *) te->expr); + *vartypmod = exprTypmod((Node *) te->expr); + } + break; default: elog(ERROR, "unrecognized RTE kind: %d", (int) rte->rtekind); } *************** *** 1788,1793 **** --- 1929,1935 ---- break; case RTE_SUBQUERY: case RTE_VALUES: + case RTE_RECURSIVE: /* Subselect and Values RTEs never have dropped columns */ result = false; break; *** pgsql/src/backend/parser/parse_target.c 2008-09-02 05:42:44.000000000 +0900 --- pgsql.patched/src/backend/parser/parse_target.c 2008-09-07 23:47:33.000000000 +0900 *************** *** 294,299 **** --- 294,300 ---- case RTE_SPECIAL: case RTE_FUNCTION: case RTE_VALUES: + case RTE_RECURSIVE: /* not a simple relation, leave it unmarked */ break; } *************** *** 1125,1130 **** --- 1126,1132 ---- case RTE_RELATION: case RTE_SPECIAL: case RTE_VALUES: + case RTE_RECURSIVE: /* * This case should not occur: a column of a table or values list *** pgsql/src/backend/rewrite/rewriteHandler.c 2008-08-29 08:09:48.000000000 +0900 --- pgsql.patched/src/backend/rewrite/rewriteHandler.c 2008-09-07 23:47:34.000000000 +0900 *************** *** 1276,1286 **** rte = rt_fetch(rt_index, parsetree->rtable); /* ! * A subquery RTE can't have associated rules, so there's nothing to ! * do to this level of the query, but we must recurse into the ! * subquery to expand any rule references in it. */ ! if (rte->rtekind == RTE_SUBQUERY) { rte->subquery = fireRIRrules(rte->subquery, activeRIRs); continue; --- 1276,1288 ---- rte = rt_fetch(rt_index, parsetree->rtable); /* ! * A subquery RTE and recursive RTE can't have associated ! * rules, so there's nothing to do to this level of the query, ! * but we must recurse into the subquery to expand any rule ! * references in it. */ ! if (rte->rtekind == RTE_SUBQUERY || ! (rte->rtekind == RTE_RECURSIVE && !rte->self_reference)) { rte->subquery = fireRIRrules(rte->subquery, activeRIRs); continue; *** pgsql/src/backend/utils/adt/ruleutils.c 2008-09-07 05:18:08.000000000 +0900 --- pgsql.patched/src/backend/utils/adt/ruleutils.c 2008-09-07 23:47:34.000000000 +0900 *************** *** 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_recursive_def(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,2248 ---- } /* ---------- + * get_with_recursive_def - Parse back a RECURSIVE clause + * ---------- + */ + static void + get_with_recursive_def(Query *query, deparse_context *context) + { + StringInfo buf = context->buf; + char *sep; + ListCell *l; + + sep = "WITH RECURSIVE "; + foreach (l, query->jointree->fromlist) + { + RangeTblRef *rtr = (RangeTblRef *) lfirst(l); + if (IsA(rtr, RangeTblRef)) + { + RangeTblEntry *rte = rt_fetch(rtr->rtindex, query->rtable); + + if (rte->rtekind == RTE_RECURSIVE) + { + appendStringInfo(buf, "%s", sep); + appendStringInfo(buf, "%s", quote_identifier(rte->alias->aliasname)); + get_from_clause_alias(rte->alias, + rt_fetch(rtr->rtindex, query->rtable), + context); + appendStringInfo(buf, " AS ("); + get_query_def(rte->subquery, buf, context->namespaces, NULL, + context->prettyFlags, context->indentLevel); + appendStringInfoChar(buf, ')'); + sep = ", "; + } + } + } + + } + + /* ---------- * get_select_query_def - Parse back a SELECT parsetree * ---------- */ *************** *** 2357,2362 **** --- 2395,2405 ---- } /* + * Add the WITH RECURSIVE clause if given + */ + get_with_recursive_def(query, context); + + /* * Build up the query string - first we say SELECT */ appendStringInfo(buf, "SELECT"); *************** *** 3259,3264 **** --- 3302,3308 ---- case RTE_RELATION: case RTE_SPECIAL: case RTE_VALUES: + case RTE_RECURSIVE: /* * This case should not occur: a column of a table or values list *************** *** 5122,5127 **** --- 5166,5175 ---- context->prettyFlags, context->indentLevel); appendStringInfoChar(buf, ')'); break; + case RTE_RECURSIVE: + /* RECURSIVE RTE */ + /* Do not build RTE name because RECURSIVE RTE always has alias name.*/ + break; case RTE_FUNCTION: /* Function RTE */ get_rule_expr(rte->funcexpr, context, true); *************** *** 5189,5195 **** get_from_clause_alias(rte->eref, rte, context); } } ! else { /* * For non-function RTEs, just report whatever the user originally --- 5237,5243 ---- get_from_clause_alias(rte->eref, rte, context); } } ! else if (rte->rtekind != RTE_RECURSIVE) { /* * For non-function RTEs, just report whatever the user originally *** pgsql/src/include/executor/nodeAppend.h 2008-01-02 04:45:57.000000000 +0900 --- pgsql.patched/src/include/executor/nodeAppend.h 2008-09-07 23:47:34.000000000 +0900 *************** *** 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 */ *** pgsql/src/include/executor/nodeRecursion.h 1970-01-01 09:00:00.000000000 +0900 --- pgsql.patched/src/include/executor/nodeRecursion.h 2008-09-07 23:47:34.000000000 +0900 *************** *** 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 */ *** pgsql/src/include/executor/nodeRecursivescan.h 1970-01-01 09:00:00.000000000 +0900 --- pgsql.patched/src/include/executor/nodeRecursivescan.h 2008-09-07 23:47:34.000000000 +0900 *************** *** 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 */ *** pgsql/src/include/nodes/execnodes.h 2008-08-22 09:16:04.000000000 +0900 --- pgsql.patched/src/include/nodes/execnodes.h 2008-09-07 23:47:34.000000000 +0900 *************** *** 349,354 **** --- 349,358 ---- List *es_subplanstates; /* List of PlanState for SubPlans */ + Tuplestorestate **es_tuplestorestate; /* Stuff used for recursive query */ + TupleDesc es_rscan_tupledesc; + bool es_disallow_tuplestore; + /* * 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 **** --- 896,902 ---- * 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 **** --- 1184,1216 ---- 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 * ---------------------------------------------------------------- *** pgsql/src/include/nodes/nodes.h 2008-08-30 10:39:14.000000000 +0900 --- pgsql.patched/src/include/nodes/nodes.h 2008-09-07 23:47:34.000000000 +0900 *************** *** 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, *************** *** 76,81 **** --- 78,84 ---- T_PlanState = 200, T_ResultState, T_AppendState, + T_RecursionState, T_BitmapAndState, T_BitmapOrState, T_ScanState, *************** *** 87,92 **** --- 90,96 ---- T_SubqueryScanState, T_FunctionScanState, T_ValuesScanState, + T_RecursiveScanState, T_JoinState, T_NestLoopState, T_MergeJoinState, *************** *** 146,151 **** --- 150,156 ---- T_JoinExpr, T_FromExpr, T_IntoClause, + T_WithClause, /* * TAGS FOR EXPRESSION STATE NODES (execnodes.h) *************** *** 333,338 **** --- 338,344 ---- T_SortBy, T_RangeSubselect, T_RangeFunction, + T_RangeRecursive, T_TypeName, T_ColumnDef, T_IndexElem, *** pgsql/src/include/nodes/parsenodes.h 2008-09-02 05:42:45.000000000 +0900 --- pgsql.patched/src/include/nodes/parsenodes.h 2008-09-07 23:47:34.000000000 +0900 *************** *** 138,143 **** --- 138,145 ---- Node *setOperations; /* set-operation tree if this is top level of * a UNION/INTERSECT/EXCEPT query */ + + bool recursive; } Query; *************** *** 388,393 **** --- 390,409 ---- } RangeFunction; /* + * RangeRecursion - recursive call appearing in a FROM clause + */ + typedef struct RangeRecursive + { + NodeTag type; + Node *subquery; + Alias *alias; /* table alias & optional column aliases */ + List *coldeflist; /* list of ColumnDef nodes to describe result + * of function returning RECORD */ + Node *non_recursive_term; + bool recursive; + } RangeRecursive; + + /* * ColumnDef - column definition (used in various creates) * * If the column has a default value, we may have the value expression *************** *** 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 --- 579,586 ---- RTE_JOIN, /* join */ RTE_SPECIAL, /* special rule relation (NEW or OLD) */ RTE_FUNCTION, /* function in FROM */ ! RTE_VALUES, /* VALUES (), (), ... */ ! RTE_RECURSIVE /* WITH RECURSIVE */ } RTEKind; typedef struct RangeTblEntry *************** *** 605,610 **** --- 622,633 ---- List *values_lists; /* list of expression lists */ /* + * Fields valid for a RECURSIVE CTE (else NIL) + */ + bool self_reference; /* delay analyzing SelectStmt */ + Query *non_recursive_query; /* non-recursive term */ + + /* * Fields valid for a join RTE (else NULL/zero): * * joinaliasvars is a list of Vars or COALESCE expressions corresponding *************** *** 697,702 **** --- 720,736 ---- bool noWait; /* NOWAIT option */ } RowMarkClause; + /* + * WithClause - + * reprensentation of WITH clause + */ + typedef struct WithClause + { + NodeTag type; + List *subquery; /* query list */ + bool recursive; /* true = WITH RECURSIVE */ + } WithClause; + /***************************************************************************** * Optimizable Statements *****************************************************************************/ *************** *** 781,786 **** --- 815,821 ---- Node *whereClause; /* WHERE qualification */ List *groupClause; /* GROUP BY clauses */ Node *havingClause; /* HAVING conditional-expression */ + WithClause *withClause; /* WITH [RECURSIVE] clause */ /* * In a "leaf" node representing a VALUES list, the above fields are all *** pgsql/src/include/nodes/plannodes.h 2008-08-08 04:35:02.000000000 +0900 --- pgsql.patched/src/include/nodes/plannodes.h 2008-09-07 23:47:34.000000000 +0900 *************** *** 355,360 **** --- 355,381 ---- 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 *** pgsql/src/include/optimizer/cost.h 2008-08-22 09:16:04.000000000 +0900 --- pgsql.patched/src/include/optimizer/cost.h 2008-09-07 23:47:34.000000000 +0900 *************** *** 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 *** pgsql/src/include/optimizer/pathnode.h 2008-08-15 03:48:00.000000000 +0900 --- pgsql.patched/src/include/optimizer/pathnode.h 2008-09-07 23:47:34.000000000 +0900 *************** *** 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, *** pgsql/src/include/parser/parse_clause.h 2008-08-07 10:11:52.000000000 +0900 --- pgsql.patched/src/include/parser/parse_clause.h 2008-09-07 23:47:34.000000000 +0900 *************** *** 16,21 **** --- 16,22 ---- #include "parser/parse_node.h" + extern void transformWithClause(ParseState *pstate, WithClause *withClause); extern void transformFromClause(ParseState *pstate, List *frmList); extern int setTargetTable(ParseState *pstate, RangeVar *relation, bool inh, bool alsoSource, AclMode requiredPerms); *** pgsql/src/include/parser/parse_cte.h 1970-01-01 09:00:00.000000000 +0900 --- pgsql.patched/src/include/parser/parse_cte.h 2008-09-07 23:47:34.000000000 +0900 *************** *** 0 **** --- 1,22 ---- + /*------------------------------------------------------------------------- + * + * parse_cte.h + * handle cte(common table expression) 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 void checkCteNameSpaceConflicts(List *namespace, RangeSubselect *new_cte); + extern void checkWellFormedCte(ParseState *pstate, WithClause *withClause); + + #endif /* PARSE_CTE_H */ *** pgsql/src/include/parser/parse_node.h 2008-09-02 05:42:45.000000000 +0900 --- pgsql.patched/src/include/parser/parse_node.h 2008-09-07 23:47:34.000000000 +0900 *************** *** 58,63 **** --- 58,71 ---- * of ParseStates, only the topmost ParseState contains paramtype info; but * we copy the p_variableparams flag down to the child nodes for speed in * coerce_type. + * + * [1] Note that p_ctenamespace is a namespace for "relations" but distinct + * from p_relnamespace. p_ctenamespace is a list of relations that can be + * referred to in a FROM or JOIN clause (in addition to normal tables and + * views). p_relnamespace is the list of relations which already have been + * listed in such clauses and therefore can be referred to in qualified + * variable references. Also, note that p_ctenamespace is a list of + * RangeSubselects, not a list of range table entries. */ typedef struct ParseState { *************** *** 68,73 **** --- 76,83 ---- * 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 expressions [1] */ + List *p_recursive_namespace; /* current namespace for recursive common table expressions */ 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 */ *************** *** 78,83 **** --- 88,94 ---- bool p_hasSubLinks; bool p_is_insert; bool p_is_update; + bool p_in_with_clause; Relation p_target_relation; RangeTblEntry *p_target_rangetblentry; } ParseState; *** pgsql/src/include/parser/parse_relation.h 2008-09-02 05:42:45.000000000 +0900 --- pgsql.patched/src/include/parser/parse_relation.h 2008-09-07 23:47:34.000000000 +0900 *************** *** 66,71 **** --- 66,76 ---- List *exprs, Alias *alias, bool inFromCl); + extern RangeTblEntry *addRangeTableEntryForRecursive(ParseState *pstate, + Query *query, + Query *non_recursive_term, + Alias *alias, + bool inFromCl); extern RangeTblEntry *addRangeTableEntryForJoin(ParseState *pstate, List *colnames, JoinType jointype, *** pgsql/src/interfaces/ecpg/preproc/preproc.y 2008-08-20 23:09:16.000000000 +0900 --- pgsql.patched/src/interfaces/ecpg/preproc/preproc.y 2008-09-07 23:47:34.000000000 +0900 *************** *** 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 *** pgsql/src/test/regress/parallel_schedule 2008-04-11 07:25:26.000000000 +0900 --- pgsql.patched/src/test/regress/parallel_schedule 2008-09-07 23:47:34.000000000 +0900 *************** *** 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 *** pgsql/src/test/regress/serial_schedule 2008-04-11 07:25:26.000000000 +0900 --- pgsql.patched/src/test/regress/serial_schedule 2008-09-07 23:47:34.000000000 +0900 *************** *** 114,118 **** --- 114,119 ---- test: returning test: largeobject test: xml + test: recursive test: stats test: tablespace *** pgsql/src/test/regress/sql/recursive.sql 1970-01-01 09:00:00.000000000 +0900 --- pgsql.patched/src/test/regress/sql/recursive.sql 2008-09-07 23:47:34.000000000 +0900 *************** *** 0 **** --- 1,330 ---- + 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; + + -- DISTINCT + WITH RECURSIVE t(n) AS ( + SELECT 1 + + UNION ALL + + SELECT DISTINCT n+1 FROM t WHERE n < 10 + ) + SELECT * FROM t; + + -- 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(*) 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 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; *** pgsql/src/test/regress/expected/recursive.out 1970-01-01 09:00:00.000000000 +0900 --- pgsql.patched/src/test/regress/expected/recursive.out 2008-09-07 23:47:34.000000000 +0900 *************** *** 0 **** --- 1,529 ---- + 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) + + -- DISTINCT + WITH RECURSIVE t(n) AS ( + SELECT 1 + + UNION ALL + + SELECT DISTINCT n+1 FROM t WHERE n < 10 + ) + SELECT * FROM t; + n + ---- + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + (10 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 + -- 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(*) 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 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 recursive call is not supported *** pgsql/src/bin/psql/tab-complete.c 2008-08-16 10:36:35.000000000 +0900 --- pgsql.patched/src/bin/psql/tab-complete.c 2008-09-07 23:47:34.000000000 +0900 *************** *** 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)