· 6 years ago · Aug 06, 2019, 12:12 AM
1-- psql -d postgres -a -f with-recursive.sql > with-recursive.sql.out 2>&1
2
3create temporary view t as select * from (values (0), (1), (2)) as t(id);
4
5-- very basic recursion
6WITH RECURSIVE r(level) AS (
7 VALUES (0)
8 UNION ALL
9 SELECT level + 1 FROM r WHERE level < 10
10)
11SELECT * FROM r;
12
13-- unlimited recursion fails at spark.sql.cte.recursion.level.limits level
14--
15-- skip because of infinite loops in pg
16--
17-- WITH RECURSIVE r(level) AS (
18-- VALUES (0)
19-- UNION ALL
20-- SELECT level + 1 FROM r
21-- )
22-- SELECT * FROM r;
23
24-- terminate recursion with LIMIT
25WITH RECURSIVE r(level) AS (
26 VALUES (0)
27 UNION ALL
28 SELECT level + 1 FROM r
29)
30SELECT * FROM r LIMIT 10;
31
32-- terminate projected recursion with LIMIT
33WITH RECURSIVE r(level) AS (
34 VALUES (0)
35 UNION ALL
36 SELECT level + 1 FROM r
37)
38SELECT level, level FROM r LIMIT 10;
39
40-- fails because using LIMIT to terminate recursion only works where Limit can be pushed through
41-- recursion
42--
43-- skip because of infinite loops in pg
44--
45-- WITH RECURSIVE r(level) AS (
46-- VALUES (0)
47-- UNION ALL
48-- SELECT level + 1 FROM r
49-- )
50-- SELECT level, level FROM r ORDER BY level LIMIT 10;
51
52-- using string column in recursion
53WITH RECURSIVE r(c) AS (
54 SELECT 'a'
55 UNION ALL
56 SELECT c || ' b' FROM r WHERE LENGTH(c) < 10
57)
58SELECT * FROM r;
59
60-- recursion works regardless the order of anchor and recursive terms
61WITH RECURSIVE r(level) AS (
62 SELECT level + 1 FROM r WHERE level < 10
63 UNION ALL
64 VALUES (0)
65)
66SELECT * FROM r;
67
68-- multiple anchor terms are supported
69WITH RECURSIVE r(level, data) AS (
70 VALUES (0, 'A')
71 UNION ALL
72 VALUES (0, 'B')
73 UNION ALL
74 SELECT level + 1, data || 'C' FROM r WHERE level < 3
75)
76SELECT * FROM r;
77
78-- multiple recursive terms are supported
79WITH RECURSIVE r(level, data) AS (
80 VALUES (0, 'A')
81 UNION ALL
82 SELECT level + 1, data || 'B' FROM r WHERE level < 2
83 UNION ALL
84 SELECT level + 1, data || 'C' FROM r WHERE level < 3
85)
86SELECT * FROM r;
87
88-- multiple anchor and recursive terms are supported
89WITH RECURSIVE r(level, data) AS (
90 VALUES (0, 'A')
91 UNION ALL
92 VALUES (0, 'B')
93 UNION ALL
94 SELECT level + 1, data || 'C' FROM r WHERE level < 2
95 UNION ALL
96 SELECT level + 1, data || 'D' FROM r WHERE level < 3
97)
98SELECT * FROM r;
99
100-- recursion without an anchor term fails
101WITH RECURSIVE r(level) AS (
102 SELECT level + 1 FROM r WHERE level < 3
103)
104SELECT * FROM r;
105
106-- UNION combinator supported to eliminate duplicates and stop recursion
107WITH RECURSIVE r(level) AS (
108 VALUES (0), (0)
109 UNION
110 SELECT (level + 1) % 10 FROM r
111)
112SELECT * FROM r;
113
114-- fails because a recursive query should contain UNION ALL or UNION combinator
115WITH RECURSIVE r(level) AS (
116 VALUES (0)
117 INTERSECT
118 SELECT level + 1 FROM r WHERE level < 10
119)
120SELECT * FROM r;
121
122-- recursive reference is not allowed in a subquery
123WITH RECURSIVE r(level) AS (
124 VALUES (0)
125 UNION ALL
126 SELECT level + 1 FROM r WHERE (SELECT SUM(level) FROM r) < 10
127)
128SELECT * FROM r;
129
130-- recursive reference can't be used multiple times in a recursive term
131WITH RECURSIVE r(level, data) AS (
132 VALUES (0, 'A')
133 UNION ALL
134 SELECT r1.level + 1, r1.data
135 FROM r AS r1
136 JOIN r AS r2 ON r2.data = r1.data
137 WHERE r1.level < 10
138)
139SELECT * FROM r;
140
141-- recursive reference is not allowed on right side of a left outer join
142WITH RECURSIVE r(level, data) AS (
143 VALUES (0, 'A')
144 UNION ALL
145 SELECT level + 1, r.data
146 FROM (
147 SELECT 'B' AS data
148 ) AS o
149 LEFT JOIN r ON r.data = o.data
150)
151SELECT * FROM r;
152
153-- recursive reference is not allowed on left side of a right outer join
154WITH RECURSIVE r(level, data) AS (
155 VALUES (0, 'A')
156 UNION ALL
157 SELECT level + 1, r.data
158 FROM r
159 RIGHT JOIN (
160 SELECT 'B' AS data
161 ) AS o ON o.data = r.data
162)
163SELECT * FROM r;
164
165-- aggregate is supported in the anchor term
166WITH RECURSIVE r(level, data) AS (
167 SELECT MAX(level) AS level, SUM(data) AS data FROM (VALUES (0, 1), (0, 2)) _t
168 UNION ALL
169 SELECT level + 1, data FROM r WHERE level < 10
170)
171SELECT * FROM r ORDER BY level;
172
173-- recursive reference is not allowed in an aggregate in a recursive term
174WITH RECURSIVE r(_group, data) AS (
175 VALUES (0, 1)
176 UNION ALL
177 SELECT 1, SUM(data) FROM r WHERE data < 10 GROUP BY _group
178)
179SELECT * FROM r;
180
181-- recursive reference is not allowed in an aggregate (made from project) in a recursive term
182WITH RECURSIVE r(level) AS (
183 VALUES (1)
184 UNION ALL
185 SELECT SUM(level) FROM r WHERE level < 10
186)
187SELECT * FROM r;
188
189-- aggregate is supported on a recursive table
190WITH RECURSIVE r(level, data) AS (
191 VALUES (0, 'A')
192 UNION ALL
193 SELECT level + 1, data FROM r WHERE level < 10
194)
195SELECT COUNT(*) FROM r;
196
197-- recursive reference is not allowed to use in combination with distinct
198WITH RECURSIVE r(level, data) AS (
199 VALUES (0, 'A')
200 UNION ALL
201 SELECT DISTINCT level + 1, data FROM r WHERE level < 10
202)
203SELECT * FROM r;
204
205-- multiple with works
206WITH RECURSIVE y AS (
207 SELECT * FROM (VALUES (1)) AS t(id)
208),
209x AS (
210 SELECT * FROM y
211 UNION ALL
212 SELECT id + 1 FROM x WHERE id < 5
213)
214SELECT * FROM x;
215
216-- multiple with works 2
217WITH RECURSIVE x AS (
218 SELECT * FROM (VALUES (1)) AS t(id)
219 UNION ALL
220 SELECT id + 1 FROM x WHERE id < 5
221),
222y AS (
223 SELECT * FROM (VALUES (1)) AS t(id)
224 UNION ALL
225 SELECT id + 1 FROM y WHERE id < 10
226)
227SELECT * FROM y LEFT JOIN x ON x.id = y.id;
228
229-- multiple with works 3
230WITH RECURSIVE x AS (
231 SELECT * FROM (VALUES (1)) AS t(id)
232 UNION ALL
233 SELECT id + 1 FROM x WHERE id < 5
234),
235y AS (
236 SELECT * FROM (VALUES (1)) AS t(id)
237 UNION ALL
238 SELECT id + 1 FROM x WHERE id < 10
239)
240SELECT * FROM y LEFT JOIN x ON x.id = y.id;
241
242-- multiple with works 4
243WITH RECURSIVE x AS (
244 SELECT 1 AS id
245 UNION ALL
246 SELECT id + 1 FROM x WHERE id < 3
247),
248y AS (
249 SELECT * FROM x
250 UNION ALL
251 SELECT * FROM x
252),
253z AS (
254 SELECT * FROM x
255 UNION ALL
256 SELECT id + 1 FROM z WHERE id < 10
257)
258SELECT * FROM z;
259
260-- multiple with works 5
261WITH RECURSIVE x AS (
262 SELECT 1 AS id
263 UNION ALL
264 SELECT id + 1 FROM x WHERE id < 3
265),
266y AS (
267 SELECT * FROM x
268 UNION ALL
269 SELECT * FROM x
270),
271z AS (
272 SELECT * FROM y
273 UNION ALL
274 SELECT id + 1 FROM z WHERE id < 10
275)
276SELECT * FROM z;
277
278-- recursion nested into WITH
279WITH t AS (
280 WITH RECURSIVE s AS (
281 SELECT * FROM (VALUES (1)) AS t(i)
282 UNION ALL
283 SELECT i + 1 FROM s
284 )
285 SELECT i AS j FROM s LIMIT 10
286)
287SELECT * FROM t;
288
289-- WITH nested into recursion
290WITH RECURSIVE outermost AS (
291 WITH innermost AS (
292 SELECT * FROM outermost
293 )
294 SELECT level + 1 FROM innermost WHERE level < 5
295 UNION ALL
296 SELECT 0 AS level
297)
298SELECT * FROM outermost;
299
300-- recursion nested into recursion
301WITH RECURSIVE t AS (
302 WITH RECURSIVE s AS (
303 SELECT * FROM (VALUES (1)) AS t(i)
304 UNION ALL
305 SELECT i + 1 FROM s WHERE i < 10
306 )
307 SELECT i AS j FROM s
308 UNION ALL
309 SELECT j + 1 FROM t WHERE j < 10
310)
311SELECT * FROM t;
312
313-- recursion nested into recursion 2
314WITH RECURSIVE t AS (
315 WITH RECURSIVE s AS (
316 SELECT j, 1 AS i FROM t
317 UNION ALL
318 SELECT j, i + 1 FROM s WHERE i < 3
319 )
320 SELECT * FROM (VALUES (1)) as t(j)
321 UNION ALL
322 SELECT j + 1 FROM s WHERE j < 3
323)
324SELECT * FROM t;
325
326-- routes represented here is as follows:
327--
328-- NewYork<--->Boston
329-- | ∧
330-- ∨ |
331-- Washington---+
332-- |
333-- ∨
334-- Raleigh
335CREATE TEMPORARY VIEW routes(origin, destination) AS VALUES
336 ('NewYork', 'Washington'),
337 ('NewYork', 'Boston'),
338 ('Boston', 'NewYork'),
339 ('Washington', 'Boston'),
340 ('Washington', 'Raleigh');
341
342-- handling cycles that could cause infinite recursion
343WITH RECURSIVE destinations_from_new_york AS (
344 SELECT 'NewYork' AS destination, array['NewYork'] AS path, 0 AS length
345 UNION ALL
346 SELECT r.destination, array_append(d.path, r.destination), d.length + 1
347 FROM routes AS r
348 JOIN destinations_from_new_york AS d ON d.destination = r.origin AND NOT d.path @> array[r.destination]
349)
350SELECT * FROM destinations_from_new_york;
351
352-- Fibonacci numbers
353WITH RECURSIVE fibonacci AS (
354 SELECT * FROM (VALUES (0, 1)) AS t(a, b)
355 UNION ALL
356 SELECT b, a + b FROM fibonacci WHERE a < 10
357)
358SELECT a FROM fibonacci ORDER BY a;
359
360-- Clean up
361DROP VIEW IF EXISTS t;
362DROP VIEW IF EXISTS routes;