Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit3696a60

Browse files
committed
SEARCH and CYCLE clauses
This adds the SQL standard feature that adds the SEARCH and CYCLEclauses to recursive queries to be able to do produce breadth- ordepth-first search orders and detect cycles. These clauses can berewritten into queries using existing syntax, and that is what thispatch does in the rewriter.Reviewed-by: Vik Fearing <vik@postgresfriends.org>Reviewed-by: Pavel Stehule <pavel.stehule@gmail.com>Discussion:https://www.postgresql.org/message-id/flat/db80ceee-6f97-9b4a-8ee8-3ba0c58e5be2@2ndquadrant.com
1 parentbb513b3 commit3696a60

28 files changed

+2301
-33
lines changed

‎doc/src/sgml/queries.sgml

Lines changed: 63 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2218,6 +2218,39 @@ SELECT * FROM search_tree <emphasis>ORDER BY depth</emphasis>;
22182218
in any case.
22192219
</para>
22202220
</tip>
2221+
2222+
<para>
2223+
There is built-in syntax to compute a depth- or breadth-first sort column.
2224+
For example:
2225+
2226+
<programlisting>
2227+
WITH RECURSIVE search_tree(id, link, data) AS (
2228+
SELECT t.id, t.link, t.data
2229+
FROM tree t
2230+
UNION ALL
2231+
SELECT t.id, t.link, t.data
2232+
FROM tree t, search_tree st
2233+
WHERE t.id = st.link
2234+
) <emphasis>SEARCH DEPTH FIRST BY id SET ordercol</emphasis>
2235+
SELECT * FROM search_tree ORDER BY ordercol;
2236+
2237+
WITH RECURSIVE search_tree(id, link, data) AS (
2238+
SELECT t.id, t.link, t.data
2239+
FROM tree t
2240+
UNION ALL
2241+
SELECT t.id, t.link, t.data
2242+
FROM tree t, search_tree st
2243+
WHERE t.id = st.link
2244+
) <emphasis>SEARCH BREADTH FIRST BY id SET ordercol</emphasis>
2245+
SELECT * FROM search_tree ORDER BY ordercol;
2246+
</programlisting>
2247+
This syntax is internally expanded to something similar to the above
2248+
hand-written forms. The <literal>SEARCH</literal> clause specifies whether
2249+
depth- or breadth first search is wanted, the list of columns to track for
2250+
sorting, and a column name that will contain the result data that can be
2251+
used for sorting. That column will implicitly be added to the output rows
2252+
of the CTE.
2253+
</para>
22212254
</sect3>
22222255

22232256
<sect3 id="queries-with-cycle">
@@ -2305,10 +2338,39 @@ SELECT * FROM search_graph;
23052338
</para>
23062339
</tip>
23072340

2341+
<para>
2342+
There is built-in syntax to simplify cycle detection. The above query can
2343+
also be written like this:
2344+
<programlisting>
2345+
WITH RECURSIVE search_graph(id, link, data, depth) AS (
2346+
SELECT g.id, g.link, g.data, 1
2347+
FROM graph g
2348+
UNION ALL
2349+
SELECT g.id, g.link, g.data, sg.depth + 1
2350+
FROM graph g, search_graph sg
2351+
WHERE g.id = sg.link
2352+
) <emphasis>CYCLE id SET is_cycle TO true DEFAULT false USING path</emphasis>
2353+
SELECT * FROM search_graph;
2354+
</programlisting>
2355+
and it will be internally rewritten to the above form. The
2356+
<literal>CYCLE</literal> clause specifies first the list of columns to
2357+
track for cycle detection, then a column name that will show whether a
2358+
cycle has been detected, then two values to use in that column for the yes
2359+
and no cases, and finally the name of another column that will track the
2360+
path. The cycle and path columns will implicitly be added to the output
2361+
rows of the CTE.
2362+
</para>
2363+
23082364
<tip>
23092365
<para>
23102366
The cycle path column is computed in the same way as the depth-first
2311-
ordering column show in the previous section.
2367+
ordering column show in the previous section. A query can have both a
2368+
<literal>SEARCH</literal> and a <literal>CYCLE</literal> clause, but a
2369+
depth-first search specification and a cycle detection specification would
2370+
create redundant computations, so it's more efficient to just use the
2371+
<literal>CYCLE</literal> clause and order by the path column. If
2372+
breadth-first ordering is wanted, then specifying both
2373+
<literal>SEARCH</literal> and <literal>CYCLE</literal> can be useful.
23122374
</para>
23132375
</tip>
23142376

‎doc/src/sgml/ref/select.sgml

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -73,6 +73,8 @@ SELECT [ ALL | DISTINCT [ ON ( <replaceable class="parameter">expression</replac
7373
<phrase>and <replaceable class="parameter">with_query</replaceable> is:</phrase>
7474

7575
<replaceable class="parameter">with_query_name</replaceable> [ ( <replaceable class="parameter">column_name</replaceable> [, ...] ) ] AS [ [ NOT ] MATERIALIZED ] ( <replaceable class="parameter">select</replaceable> | <replaceable class="parameter">values</replaceable> | <replaceable class="parameter">insert</replaceable> | <replaceable class="parameter">update</replaceable> | <replaceable class="parameter">delete</replaceable> )
76+
[ SEARCH { BREADTH | DEPTH } FIRST BY <replaceable>column_name</replaceable> [, ...] SET <replaceable>search_seq_col_name</replaceable> ]
77+
[ CYCLE <replaceable>column_name</replaceable> [, ...] SET <replaceable>cycle_mark_col_name</replaceable> TO <replaceable>cycle_mark_value</replaceable> DEFAULT <replaceable>cycle_mark_default</replaceable> USING <replaceable>cycle_path_col_name</replaceable> ]
7678

7779
TABLE [ ONLY ] <replaceable class="parameter">table_name</replaceable> [ * ]
7880
</synopsis>
@@ -276,6 +278,48 @@ TABLE [ ONLY ] <replaceable class="parameter">table_name</replaceable> [ * ]
276278
queries that do not use recursion or forward references.
277279
</para>
278280

281+
<para>
282+
The optional <literal>SEARCH</literal> clause computes a <firstterm>search
283+
sequence column</firstterm> that can be used for ordering the results of a
284+
recursive query in either breadth-first or depth-first order. The
285+
supplied column name list specifies the row key that is to be used for
286+
keeping track of visited rows. A column named
287+
<replaceable>search_seq_col_name</replaceable> will be added to the result
288+
column list of the <literal>WITH</literal> query. This column can be
289+
ordered by in the outer query to achieve the respective ordering. See
290+
<xref linkend="queries-with-search"/> for examples.
291+
</para>
292+
293+
<para>
294+
The optional <literal>CYCLE</literal> clause is used to detect cycles in
295+
recursive queries. The supplied column name list specifies the row key
296+
that is to be used for keeping track of visited rows. A column named
297+
<replaceable>cycle_mark_col_name</replaceable> will be added to the result
298+
column list of the <literal>WITH</literal> query. This column will be set
299+
to <replaceable>cycle_mark_value</replaceable> when a cycle has been
300+
detected, else to <replaceable>cycle_mark_default</replaceable>.
301+
Furthermore, processing of the recursive union will stop when a cycle has
302+
been detected. <replaceable>cycle_mark_value</replaceable> and
303+
<replaceable>cycle_mark_default</replaceable> must be constants and they
304+
must be coercible to a common data type, and the data type must have an
305+
inequality operator. (The SQL standard requires that they be character
306+
strings, but PostgreSQL does not require that.) Furthermore, a column
307+
named <replaceable>cycle_path_col_name</replaceable> will be added to the
308+
result column list of the <literal>WITH</literal> query. This column is
309+
used internally for tracking visited rows. See <xref
310+
linkend="queries-with-cycle"/> for examples.
311+
</para>
312+
313+
<para>
314+
Both the <literal>SEARCH</literal> and the <literal>CYCLE</literal> clause
315+
are only valid for recursive <literal>WITH</literal> queries. The
316+
<replaceable>with_query</replaceable> must be a <literal>UNION</literal>
317+
(or <literal>UNION ALL</literal>) of two <literal>SELECT</literal> (or
318+
equivalent) commands (no nested <literal>UNION</literal>s). If both
319+
clauses are used, the column added by the <literal>SEARCH</literal> clause
320+
appears before the columns added by the <literal>CYCLE</literal> clause.
321+
</para>
322+
279323
<para>
280324
The primary query and the <literal>WITH</literal> queries are all
281325
(notionally) executed at the same time. This implies that the effects of

‎src/backend/catalog/dependency.c

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2264,6 +2264,21 @@ find_expr_references_walker(Node *node,
22642264
context->addrs);
22652265
/* fall through to examine substructure */
22662266
}
2267+
elseif (IsA(node,CTECycleClause))
2268+
{
2269+
CTECycleClause*cc= (CTECycleClause*)node;
2270+
2271+
if (OidIsValid(cc->cycle_mark_type))
2272+
add_object_address(OCLASS_TYPE,cc->cycle_mark_type,0,
2273+
context->addrs);
2274+
if (OidIsValid(cc->cycle_mark_collation))
2275+
add_object_address(OCLASS_COLLATION,cc->cycle_mark_collation,0,
2276+
context->addrs);
2277+
if (OidIsValid(cc->cycle_mark_neop))
2278+
add_object_address(OCLASS_OPERATOR,cc->cycle_mark_neop,0,
2279+
context->addrs);
2280+
/* fall through to examine substructure */
2281+
}
22672282
elseif (IsA(node,Query))
22682283
{
22692284
/* Recurse into RTE subquery or not-yet-planned sublink subquery */

‎src/backend/nodes/copyfuncs.c

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2589,6 +2589,38 @@ _copyOnConflictClause(const OnConflictClause *from)
25892589
returnnewnode;
25902590
}
25912591

2592+
staticCTESearchClause*
2593+
_copyCTESearchClause(constCTESearchClause*from)
2594+
{
2595+
CTESearchClause*newnode=makeNode(CTESearchClause);
2596+
2597+
COPY_NODE_FIELD(search_col_list);
2598+
COPY_SCALAR_FIELD(search_breadth_first);
2599+
COPY_STRING_FIELD(search_seq_column);
2600+
COPY_LOCATION_FIELD(location);
2601+
2602+
returnnewnode;
2603+
}
2604+
2605+
staticCTECycleClause*
2606+
_copyCTECycleClause(constCTECycleClause*from)
2607+
{
2608+
CTECycleClause*newnode=makeNode(CTECycleClause);
2609+
2610+
COPY_NODE_FIELD(cycle_col_list);
2611+
COPY_STRING_FIELD(cycle_mark_column);
2612+
COPY_NODE_FIELD(cycle_mark_value);
2613+
COPY_NODE_FIELD(cycle_mark_default);
2614+
COPY_STRING_FIELD(cycle_path_column);
2615+
COPY_LOCATION_FIELD(location);
2616+
COPY_SCALAR_FIELD(cycle_mark_type);
2617+
COPY_SCALAR_FIELD(cycle_mark_typmod);
2618+
COPY_SCALAR_FIELD(cycle_mark_collation);
2619+
COPY_SCALAR_FIELD(cycle_mark_neop);
2620+
2621+
returnnewnode;
2622+
}
2623+
25922624
staticCommonTableExpr*
25932625
_copyCommonTableExpr(constCommonTableExpr*from)
25942626
{
@@ -2598,6 +2630,8 @@ _copyCommonTableExpr(const CommonTableExpr *from)
25982630
COPY_NODE_FIELD(aliascolnames);
25992631
COPY_SCALAR_FIELD(ctematerialized);
26002632
COPY_NODE_FIELD(ctequery);
2633+
COPY_NODE_FIELD(search_clause);
2634+
COPY_NODE_FIELD(cycle_clause);
26012635
COPY_LOCATION_FIELD(location);
26022636
COPY_SCALAR_FIELD(cterecursive);
26032637
COPY_SCALAR_FIELD(cterefcount);
@@ -5682,6 +5716,12 @@ copyObjectImpl(const void *from)
56825716
caseT_OnConflictClause:
56835717
retval=_copyOnConflictClause(from);
56845718
break;
5719+
caseT_CTESearchClause:
5720+
retval=_copyCTESearchClause(from);
5721+
break;
5722+
caseT_CTECycleClause:
5723+
retval=_copyCTECycleClause(from);
5724+
break;
56855725
caseT_CommonTableExpr:
56865726
retval=_copyCommonTableExpr(from);
56875727
break;

‎src/backend/nodes/equalfuncs.c

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2841,13 +2841,43 @@ _equalOnConflictClause(const OnConflictClause *a, const OnConflictClause *b)
28412841
return true;
28422842
}
28432843

2844+
staticbool
2845+
_equalCTESearchClause(constCTESearchClause*a,constCTESearchClause*b)
2846+
{
2847+
COMPARE_NODE_FIELD(search_col_list);
2848+
COMPARE_SCALAR_FIELD(search_breadth_first);
2849+
COMPARE_STRING_FIELD(search_seq_column);
2850+
COMPARE_LOCATION_FIELD(location);
2851+
2852+
return true;
2853+
}
2854+
2855+
staticbool
2856+
_equalCTECycleClause(constCTECycleClause*a,constCTECycleClause*b)
2857+
{
2858+
COMPARE_NODE_FIELD(cycle_col_list);
2859+
COMPARE_STRING_FIELD(cycle_mark_column);
2860+
COMPARE_NODE_FIELD(cycle_mark_value);
2861+
COMPARE_NODE_FIELD(cycle_mark_default);
2862+
COMPARE_STRING_FIELD(cycle_path_column);
2863+
COMPARE_LOCATION_FIELD(location);
2864+
COMPARE_SCALAR_FIELD(cycle_mark_type);
2865+
COMPARE_SCALAR_FIELD(cycle_mark_typmod);
2866+
COMPARE_SCALAR_FIELD(cycle_mark_collation);
2867+
COMPARE_SCALAR_FIELD(cycle_mark_neop);
2868+
2869+
return true;
2870+
}
2871+
28442872
staticbool
28452873
_equalCommonTableExpr(constCommonTableExpr*a,constCommonTableExpr*b)
28462874
{
28472875
COMPARE_STRING_FIELD(ctename);
28482876
COMPARE_NODE_FIELD(aliascolnames);
28492877
COMPARE_SCALAR_FIELD(ctematerialized);
28502878
COMPARE_NODE_FIELD(ctequery);
2879+
COMPARE_NODE_FIELD(search_clause);
2880+
COMPARE_NODE_FIELD(cycle_clause);
28512881
COMPARE_LOCATION_FIELD(location);
28522882
COMPARE_SCALAR_FIELD(cterecursive);
28532883
COMPARE_SCALAR_FIELD(cterefcount);
@@ -3735,6 +3765,12 @@ equal(const void *a, const void *b)
37353765
caseT_OnConflictClause:
37363766
retval=_equalOnConflictClause(a,b);
37373767
break;
3768+
caseT_CTESearchClause:
3769+
retval=_equalCTESearchClause(a,b);
3770+
break;
3771+
caseT_CTECycleClause:
3772+
retval=_equalCTECycleClause(a,b);
3773+
break;
37383774
caseT_CommonTableExpr:
37393775
retval=_equalCommonTableExpr(a,b);
37403776
break;

‎src/backend/nodes/nodeFuncs.c

Lines changed: 41 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1566,6 +1566,12 @@ exprLocation(const Node *expr)
15661566
caseT_OnConflictClause:
15671567
loc= ((constOnConflictClause*)expr)->location;
15681568
break;
1569+
caseT_CTESearchClause:
1570+
loc= ((constCTESearchClause*)expr)->location;
1571+
break;
1572+
caseT_CTECycleClause:
1573+
loc= ((constCTECycleClause*)expr)->location;
1574+
break;
15691575
caseT_CommonTableExpr:
15701576
loc= ((constCommonTableExpr*)expr)->location;
15711577
break;
@@ -1909,6 +1915,7 @@ expression_tree_walker(Node *node,
19091915
caseT_NextValueExpr:
19101916
caseT_RangeTblRef:
19111917
caseT_SortGroupClause:
1918+
caseT_CTESearchClause:
19121919
/* primitive node types with no expression subnodes */
19131920
break;
19141921
caseT_WithCheckOption:
@@ -2148,6 +2155,16 @@ expression_tree_walker(Node *node,
21482155
return true;
21492156
}
21502157
break;
2158+
caseT_CTECycleClause:
2159+
{
2160+
CTECycleClause*cc= (CTECycleClause*)node;
2161+
2162+
if (walker(cc->cycle_mark_value,context))
2163+
return true;
2164+
if (walker(cc->cycle_mark_default,context))
2165+
return true;
2166+
}
2167+
break;
21512168
caseT_CommonTableExpr:
21522169
{
21532170
CommonTableExpr*cte= (CommonTableExpr*)node;
@@ -2156,7 +2173,13 @@ expression_tree_walker(Node *node,
21562173
* Invoke the walker on the CTE's Query node, so it can
21572174
* recurse into the sub-query if it wants to.
21582175
*/
2159-
returnwalker(cte->ctequery,context);
2176+
if (walker(cte->ctequery,context))
2177+
return true;
2178+
2179+
if (walker(cte->search_clause,context))
2180+
return true;
2181+
if (walker(cte->cycle_clause,context))
2182+
return true;
21602183
}
21612184
break;
21622185
caseT_List:
@@ -2615,6 +2638,7 @@ expression_tree_mutator(Node *node,
26152638
caseT_NextValueExpr:
26162639
caseT_RangeTblRef:
26172640
caseT_SortGroupClause:
2641+
caseT_CTESearchClause:
26182642
return (Node*)copyObject(node);
26192643
caseT_WithCheckOption:
26202644
{
@@ -3019,6 +3043,17 @@ expression_tree_mutator(Node *node,
30193043
return (Node*)newnode;
30203044
}
30213045
break;
3046+
caseT_CTECycleClause:
3047+
{
3048+
CTECycleClause*cc= (CTECycleClause*)node;
3049+
CTECycleClause*newnode;
3050+
3051+
FLATCOPY(newnode,cc,CTECycleClause);
3052+
MUTATE(newnode->cycle_mark_value,cc->cycle_mark_value,Node*);
3053+
MUTATE(newnode->cycle_mark_default,cc->cycle_mark_default,Node*);
3054+
return (Node*)newnode;
3055+
}
3056+
break;
30223057
caseT_CommonTableExpr:
30233058
{
30243059
CommonTableExpr*cte= (CommonTableExpr*)node;
@@ -3031,6 +3066,10 @@ expression_tree_mutator(Node *node,
30313066
* recurse into the sub-query if it wants to.
30323067
*/
30333068
MUTATE(newnode->ctequery,cte->ctequery,Node*);
3069+
3070+
MUTATE(newnode->search_clause,cte->search_clause,CTESearchClause*);
3071+
MUTATE(newnode->cycle_clause,cte->cycle_clause,CTECycleClause*);
3072+
30343073
return (Node*)newnode;
30353074
}
30363075
break;
@@ -3913,6 +3952,7 @@ raw_expression_tree_walker(Node *node,
39133952
}
39143953
break;
39153954
caseT_CommonTableExpr:
3955+
/* search_clause and cycle_clause are not interesting here */
39163956
returnwalker(((CommonTableExpr*)node)->ctequery,context);
39173957
default:
39183958
elog(ERROR,"unrecognized node type: %d",

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp