· 6 years ago · Aug 06, 2019, 12:10 AM
1-- psql -d postgres -a -f with-recursive.sql > with-recursive.sql.out 2>&1
2create temporary view t as select * from (values (0), (1), (2)) as t(id);
3CREATE VIEW
4-- very basic recursion
5WITH RECURSIVE r(level) AS (
6 VALUES (0)
7 UNION ALL
8 SELECT level + 1 FROM r WHERE level < 10
9)
10SELECT * FROM r;
11 level
12-------
13 0
14 1
15 2
16 3
17 4
18 5
19 6
20 7
21 8
22 9
23 10
24(11 rows)
25
26-- unlimited recursion fails at spark.sql.cte.recursion.level.limits level
27--
28-- skip because of infinite loops in pg
29--
30-- WITH RECURSIVE r(level) AS (
31-- VALUES (0)
32-- UNION ALL
33-- SELECT level + 1 FROM r
34-- )
35-- SELECT * FROM r;
36-- terminate recursion with LIMIT
37WITH RECURSIVE r(level) AS (
38 VALUES (0)
39 UNION ALL
40 SELECT level + 1 FROM r
41)
42SELECT * FROM r LIMIT 10;
43 level
44-------
45 0
46 1
47 2
48 3
49 4
50 5
51 6
52 7
53 8
54 9
55(10 rows)
56
57-- terminate projected recursion with LIMIT
58WITH RECURSIVE r(level) AS (
59 VALUES (0)
60 UNION ALL
61 SELECT level + 1 FROM r
62)
63SELECT level, level FROM r LIMIT 10;
64 level | level
65-------+-------
66 0 | 0
67 1 | 1
68 2 | 2
69 3 | 3
70 4 | 4
71 5 | 5
72 6 | 6
73 7 | 7
74 8 | 8
75 9 | 9
76(10 rows)
77
78-- fails because using LIMIT to terminate recursion only works where Limit can be pushed through
79-- recursion
80--
81-- skip because of infinite loops in pg
82--
83-- WITH RECURSIVE r(level) AS (
84-- VALUES (0)
85-- UNION ALL
86-- SELECT level + 1 FROM r
87-- )
88-- SELECT level, level FROM r ORDER BY level LIMIT 10;
89-- using string column in recursion
90WITH RECURSIVE r(c) AS (
91 SELECT 'a'
92 UNION ALL
93 SELECT c || ' b' FROM r WHERE LENGTH(c) < 10
94)
95SELECT * FROM r;
96 c
97-------------
98 a
99 a b
100 a b b
101 a b b b
102 a b b b b
103 a b b b b b
104(6 rows)
105
106-- recursion works regardless the order of anchor and recursive terms
107WITH RECURSIVE r(level) AS (
108 SELECT level + 1 FROM r WHERE level < 10
109 UNION ALL
110 VALUES (0)
111)
112SELECT * FROM r;
113psql:with-recursive.sql:66: ERROR: recursive reference to query "r" must not appear within its non-recursive term
114LINE 2: SELECT level + 1 FROM r WHERE level < 10
115 ^
116-- multiple anchor terms are supported
117WITH RECURSIVE r(level, data) AS (
118 VALUES (0, 'A')
119 UNION ALL
120 VALUES (0, 'B')
121 UNION ALL
122 SELECT level + 1, data || 'C' FROM r WHERE level < 3
123)
124SELECT * FROM r;
125 level | data
126-------+------
127 0 | A
128 0 | B
129 1 | AC
130 1 | BC
131 2 | ACC
132 2 | BCC
133 3 | ACCC
134 3 | BCCC
135(8 rows)
136
137-- multiple recursive terms are supported
138WITH RECURSIVE r(level, data) AS (
139 VALUES (0, 'A')
140 UNION ALL
141 SELECT level + 1, data || 'B' FROM r WHERE level < 2
142 UNION ALL
143 SELECT level + 1, data || 'C' FROM r WHERE level < 3
144)
145SELECT * FROM r;
146psql:with-recursive.sql:86: ERROR: recursive reference to query "r" must not appear within its non-recursive term
147LINE 4: SELECT level + 1, data || 'B' FROM r WHERE level < 2
148 ^
149-- multiple anchor and recursive terms are supported
150WITH RECURSIVE r(level, data) AS (
151 VALUES (0, 'A')
152 UNION ALL
153 VALUES (0, 'B')
154 UNION ALL
155 SELECT level + 1, data || 'C' FROM r WHERE level < 2
156 UNION ALL
157 SELECT level + 1, data || 'D' FROM r WHERE level < 3
158)
159SELECT * FROM r;
160psql:with-recursive.sql:98: ERROR: recursive reference to query "r" must not appear within its non-recursive term
161LINE 6: SELECT level + 1, data || 'C' FROM r WHERE level < 2
162 ^
163-- recursion without an anchor term fails
164WITH RECURSIVE r(level) AS (
165 SELECT level + 1 FROM r WHERE level < 3
166)
167SELECT * FROM r;
168psql:with-recursive.sql:104: ERROR: recursive query "r" does not have the form non-recursive-term UNION [ALL] recursive-term
169LINE 1: WITH RECURSIVE r(level) AS (
170 ^
171-- UNION combinator supported to eliminate duplicates and stop recursion
172WITH RECURSIVE r(level) AS (
173 VALUES (0), (0)
174 UNION
175 SELECT (level + 1) % 10 FROM r
176)
177SELECT * FROM r;
178 level
179-------
180 0
181 1
182 2
183 3
184 4
185 5
186 6
187 7
188 8
189 9
190(10 rows)
191
192-- fails because a recursive query should contain UNION ALL or UNION combinator
193WITH RECURSIVE r(level) AS (
194 VALUES (0)
195 INTERSECT
196 SELECT level + 1 FROM r WHERE level < 10
197)
198SELECT * FROM r;
199psql:with-recursive.sql:120: ERROR: recursive query "r" does not have the form non-recursive-term UNION [ALL] recursive-term
200LINE 1: WITH RECURSIVE r(level) AS (
201 ^
202-- recursive reference is not allowed in a subquery
203WITH RECURSIVE r(level) AS (
204 VALUES (0)
205 UNION ALL
206 SELECT level + 1 FROM r WHERE (SELECT SUM(level) FROM r) < 10
207)
208SELECT * FROM r;
209psql:with-recursive.sql:128: ERROR: recursive reference to query "r" must not appear within a subquery
210LINE 4: ...ELECT level + 1 FROM r WHERE (SELECT SUM(level) FROM r) < 10
211 ^
212-- recursive reference can't be used multiple times in a recursive term
213WITH RECURSIVE r(level, data) AS (
214 VALUES (0, 'A')
215 UNION ALL
216 SELECT r1.level + 1, r1.data
217 FROM r AS r1
218 JOIN r AS r2 ON r2.data = r1.data
219 WHERE r1.level < 10
220)
221SELECT * FROM r;
222psql:with-recursive.sql:139: ERROR: recursive reference to query "r" must not appear more than once
223LINE 6: JOIN r AS r2 ON r2.data = r1.data
224 ^
225-- recursive reference is not allowed on right side of a left outer join
226WITH RECURSIVE r(level, data) AS (
227 VALUES (0, 'A')
228 UNION ALL
229 SELECT level + 1, r.data
230 FROM (
231 SELECT 'B' AS data
232 ) AS o
233 LEFT JOIN r ON r.data = o.data
234)
235SELECT * FROM r;
236psql:with-recursive.sql:151: ERROR: recursive reference to query "r" must not appear within an outer join
237LINE 8: LEFT JOIN r ON r.data = o.data
238 ^
239-- recursive reference is not allowed on left side of a right outer join
240WITH RECURSIVE r(level, data) AS (
241 VALUES (0, 'A')
242 UNION ALL
243 SELECT level + 1, r.data
244 FROM r
245 RIGHT JOIN (
246 SELECT 'B' AS data
247 ) AS o ON o.data = r.data
248)
249SELECT * FROM r;
250psql:with-recursive.sql:163: ERROR: recursive reference to query "r" must not appear within an outer join
251LINE 5: FROM r
252 ^
253-- aggregate is supported in the anchor term
254WITH RECURSIVE r(level, data) AS (
255 SELECT MAX(level) AS level, SUM(data) AS data FROM (VALUES (0, 1), (0, 2)) _t
256 UNION ALL
257 SELECT level + 1, data FROM r WHERE level < 10
258)
259SELECT * FROM r ORDER BY level;
260psql:with-recursive.sql:171: ERROR: column "level" does not exist
261LINE 2: SELECT MAX(level) AS level, SUM(data) AS data FROM (VALUES...
262 ^
263-- recursive reference is not allowed in an aggregate in a recursive term
264WITH RECURSIVE r(_group, data) AS (
265 VALUES (0, 1)
266 UNION ALL
267 SELECT 1, SUM(data) FROM r WHERE data < 10 GROUP BY _group
268)
269SELECT * FROM r;
270psql:with-recursive.sql:179: ERROR: aggregate functions are not allowed in a recursive query's recursive term
271LINE 4: SELECT 1, SUM(data) FROM r WHERE data < 10 GROUP BY _group
272 ^
273-- recursive reference is not allowed in an aggregate (made from project) in a recursive term
274WITH RECURSIVE r(level) AS (
275 VALUES (1)
276 UNION ALL
277 SELECT SUM(level) FROM r WHERE level < 10
278)
279SELECT * FROM r;
280psql:with-recursive.sql:187: ERROR: aggregate functions are not allowed in a recursive query's recursive term
281LINE 4: SELECT SUM(level) FROM r WHERE level < 10
282 ^
283-- aggregate is supported on a recursive table
284WITH RECURSIVE r(level, data) AS (
285 VALUES (0, 'A')
286 UNION ALL
287 SELECT level + 1, data FROM r WHERE level < 10
288)
289SELECT COUNT(*) FROM r;
290 count
291-------
292 11
293(1 row)
294
295-- recursive reference is not allowed to use in combination with distinct
296WITH RECURSIVE r(level, data) AS (
297 VALUES (0, 'A')
298 UNION ALL
299 SELECT DISTINCT level + 1, data FROM r WHERE level < 10
300)
301SELECT * FROM r;
302 level | data
303-------+------
304 0 | A
305 1 | A
306 2 | A
307 3 | A
308 4 | A
309 5 | A
310 6 | A
311 7 | A
312 8 | A
313 9 | A
314 10 | A
315(11 rows)
316
317-- multiple with works
318WITH RECURSIVE y AS (
319 SELECT * FROM (VALUES (1)) AS t(id)
320),
321x AS (
322 SELECT * FROM y
323 UNION ALL
324 SELECT id + 1 FROM x WHERE id < 5
325)
326SELECT * FROM x;
327 id
328----
329 1
330 2
331 3
332 4
333 5
334(5 rows)
335
336-- multiple with works 2
337WITH RECURSIVE x AS (
338 SELECT * FROM (VALUES (1)) AS t(id)
339 UNION ALL
340 SELECT id + 1 FROM x WHERE id < 5
341),
342y AS (
343 SELECT * FROM (VALUES (1)) AS t(id)
344 UNION ALL
345 SELECT id + 1 FROM y WHERE id < 10
346)
347SELECT * FROM y LEFT JOIN x ON x.id = y.id;
348 id | id
349----+----
350 1 | 1
351 2 | 2
352 3 | 3
353 4 | 4
354 5 | 5
355 6 |
356 7 |
357 8 |
358 9 |
359 10 |
360(10 rows)
361
362-- multiple with works 3
363WITH RECURSIVE x AS (
364 SELECT * FROM (VALUES (1)) AS t(id)
365 UNION ALL
366 SELECT id + 1 FROM x WHERE id < 5
367),
368y AS (
369 SELECT * FROM (VALUES (1)) AS t(id)
370 UNION ALL
371 SELECT id + 1 FROM x WHERE id < 10
372)
373SELECT * FROM y LEFT JOIN x ON x.id = y.id;
374 id | id
375----+----
376 1 | 1
377 2 | 2
378 3 | 3
379 4 | 4
380 5 | 5
381 6 |
382(6 rows)
383
384-- multiple with works 4
385WITH RECURSIVE x AS (
386 SELECT 1 AS id
387 UNION ALL
388 SELECT id + 1 FROM x WHERE id < 3
389),
390y AS (
391 SELECT * FROM x
392 UNION ALL
393 SELECT * FROM x
394),
395z AS (
396 SELECT * FROM x
397 UNION ALL
398 SELECT id + 1 FROM z WHERE id < 10
399)
400SELECT * FROM z;
401 id
402----
403 1
404 2
405 3
406 2
407 3
408 4
409 3
410 4
411 5
412 4
413 5
414 6
415 5
416 6
417 7
418 6
419 7
420 8
421 7
422 8
423 9
424 8
425 9
426 10
427 9
428 10
429 10
430(27 rows)
431
432-- multiple with works 5
433WITH RECURSIVE x AS (
434 SELECT 1 AS id
435 UNION ALL
436 SELECT id + 1 FROM x WHERE id < 3
437),
438y AS (
439 SELECT * FROM x
440 UNION ALL
441 SELECT * FROM x
442),
443z AS (
444 SELECT * FROM y
445 UNION ALL
446 SELECT id + 1 FROM z WHERE id < 10
447)
448SELECT * FROM z;
449 id
450----
451 1
452 2
453 3
454 1
455 2
456 3
457 2
458 3
459 4
460 2
461 3
462 4
463 3
464 4
465 5
466 3
467 4
468 5
469 4
470 5
471 6
472 4
473 5
474 6
475 5
476 6
477 7
478 5
479 6
480 7
481 6
482 7
483 8
484 6
485 7
486 8
487 7
488 8
489 9
490 7
491 8
492 9
493 8
494 9
495 10
496 8
497 9
498 10
499 9
500 10
501 9
502 10
503 10
504 10
505(54 rows)
506
507-- recursion nested into WITH
508WITH t AS (
509 WITH RECURSIVE s AS (
510 SELECT * FROM (VALUES (1)) AS t(i)
511 UNION ALL
512 SELECT i + 1 FROM s
513 )
514 SELECT i AS j FROM s LIMIT 10
515)
516SELECT * FROM t;
517 j
518----
519 1
520 2
521 3
522 4
523 5
524 6
525 7
526 8
527 9
528 10
529(10 rows)
530
531-- WITH nested into recursion
532WITH RECURSIVE outermost AS (
533 WITH innermost AS (
534 SELECT * FROM outermost
535 )
536 SELECT level + 1 FROM innermost WHERE level < 5
537 UNION ALL
538 SELECT 0 AS level
539)
540SELECT * FROM outermost;
541psql:with-recursive.sql:298: ERROR: missing recursive reference
542-- recursion nested into recursion
543WITH RECURSIVE t AS (
544 WITH RECURSIVE s AS (
545 SELECT * FROM (VALUES (1)) AS t(i)
546 UNION ALL
547 SELECT i + 1 FROM s WHERE i < 10
548 )
549 SELECT i AS j FROM s
550 UNION ALL
551 SELECT j + 1 FROM t WHERE j < 10
552)
553SELECT * FROM t;
554 j
555----
556 1
557 2
558 3
559 4
560 5
561 6
562 7
563 8
564 9
565 10
566 2
567 3
568 4
569 5
570 6
571 7
572 8
573 9
574 10
575 3
576 4
577 5
578 6
579 7
580 8
581 9
582 10
583 4
584 5
585 6
586 7
587 8
588 9
589 10
590 5
591 6
592 7
593 8
594 9
595 10
596 6
597 7
598 8
599 9
600 10
601 7
602 8
603 9
604 10
605 8
606 9
607 10
608 9
609 10
610 10
611(55 rows)
612
613-- recursion nested into recursion 2
614WITH RECURSIVE t AS (
615 WITH RECURSIVE s AS (
616 SELECT j, 1 AS i FROM t
617 UNION ALL
618 SELECT j, i + 1 FROM s WHERE i < 3
619 )
620 SELECT * FROM (VALUES (1)) as t(j)
621 UNION ALL
622 SELECT j + 1 FROM s WHERE j < 3
623)
624SELECT * FROM t;
625psql:with-recursive.sql:324: ERROR: missing recursive reference
626-- routes represented here is as follows:
627--
628-- NewYork<--->Boston
629-- | ∧
630-- ∨ |
631-- Washington---+
632-- |
633-- ∨
634-- Raleigh
635CREATE TEMPORARY VIEW routes(origin, destination) AS VALUES
636 ('NewYork', 'Washington'),
637 ('NewYork', 'Boston'),
638 ('Boston', 'NewYork'),
639 ('Washington', 'Boston'),
640 ('Washington', 'Raleigh');
641CREATE VIEW
642-- handling cycles that could cause infinite recursion
643WITH RECURSIVE destinations_from_new_york AS (
644 SELECT 'NewYork' AS destination, array['NewYork'] AS path, 0 AS length
645 UNION ALL
646 SELECT r.destination, array_append(d.path, r.destination), d.length + 1
647 FROM routes AS r
648 JOIN destinations_from_new_york AS d ON d.destination = r.origin AND NOT d.path @> array[r.destination]
649)
650SELECT * FROM destinations_from_new_york;
651 destination | path | length
652-------------+------------------------------+--------
653 NewYork | {NewYork} | 0
654 Boston | {NewYork,Boston} | 1
655 Washington | {NewYork,Washington} | 1
656 Raleigh | {NewYork,Washington,Raleigh} | 2
657 Boston | {NewYork,Washington,Boston} | 2
658(5 rows)
659
660-- Fibonacci numbers
661WITH RECURSIVE fibonacci AS (
662 SELECT * FROM (VALUES (0, 1)) AS t(a, b)
663 UNION ALL
664 SELECT b, a + b FROM fibonacci WHERE a < 10
665)
666SELECT a FROM fibonacci ORDER BY a;
667 a
668----
669 0
670 1
671 1
672 2
673 3
674 5
675 8
676 13
677(8 rows)
678
679-- Clean up
680DROP VIEW IF EXISTS t;
681DROP VIEW
682DROP VIEW IF EXISTS routes;
683DROP VIEW