This works because PostgreSQL's implementation evaluates only as many rows of a WITH query as are actually fetched by the parent query. For example, this query would loop forever without the LIMIT: If breadth-first ordering is wanted, then specifying both SEARCH and CYCLE can be useful.Ī helpful trick for testing queries when you are not certain if they might loop is to place a LIMIT in the parent query. A query can have both a SEARCH and a CYCLE clause, but a depth-first search specification and a cycle detection specification would create redundant computations, so it's more efficient to just use the CYCLE clause and order by the path column. The cycle path column is computed in the same way as the depth-first ordering column show in the previous section. For example, if we needed to compare fields f1 and f2: In the general case where more than one field needs to be checked to recognize a cycle, use an array of rows. SELECT g.id, g.link, g.data, sg.depth + 1,Īside from preventing cycles, the array value is often useful in its own right as representing the “ path” taken to reach any particular row. WITH RECURSIVE search_graph(id, link, data, depth, is_cycle, path) AS ( We add two columns is_cycle and path to the loop-prone query: Instead we need to recognize whether we have reached the same row again while following a particular path of links. Because we require a “ depth” output, just changing UNION ALL to UNION would not eliminate the looping. This query will loop if the link relationships contain cycles. SELECT g.id, g.link, g.data, sg.depth + 1 WITH RECURSIVE search_graph(id, link, data, depth) AS ( For example, consider again the following query that searches a table graph using a link field: The standard method for handling such situations is to compute an array of the already-visited values. However, often a cycle does not involve output rows that are completely duplicate: it may be necessary to check just one or a few fields to see if the same point has been reached before. Sometimes, using UNION instead of UNION ALL can accomplish this by discarding rows that duplicate previous output rows. When working with recursive queries it is important to be sure that the recursive part of the query will eventually return no tuples, or else the query will loop indefinitely. That column will implicitly be added to the output rows of the CTE. The SEARCH clause specifies whether depth- or breadth first search is wanted, the list of columns to track for sorting, and a column name that will contain the result data that can be used for sorting. This syntax is internally expanded to something similar to the above hand-written forms. ) SEARCH BREADTH FIRST BY id SET ordercol SELECT * FROM search_tree ORDER BY ordercol There is built-in syntax to compute a depth- or breadth-first sort column. The order of the rows within each level is certainly undefined, so some explicit ordering might be desired in any case.
However, this is an implementation detail and it is perhaps unsound to rely on it. The recursive query evaluation algorithm produces its output in breadth-first search order. SELECT t.id, t.link, t.data, path || ROW(t.f1, t.f2) For example, if we needed to track fields f1 and f2: In the general case where more than one field needs to be used to identify a row, use an array of rows. SELECT t.id, t.link, t.data, path || t.id WITH RECURSIVE search_tree(id, link, data, path) AS ( To add depth-first ordering information, you can write this: WITH RECURSIVE search_tree(id, link, data) AS ( For example, consider the following query that searches a table tree using a link field: To create a depth-first order, we compute for each result row an array of rows that we have visited so far. This approach merely provides a convenient way to order the results afterwards. Note that this does not actually control in which order the query evaluation visits the rows that is as always in SQL implementation-dependent. This can be done by computing an ordering column alongside the other data columns and using that to sort the results at the end. When computing a tree traversal using a recursive query, you might want to order the results in either depth-first or breadth-first order.
0 kommentar(er)
