Re: Proposing WITH ITERATIVE

On Mon, Apr 27, 2020 at 8:50 PM Jeff Davis <pgsql(at)j-davis(dot)com> wrote:

> Can you illustrate with some examples? I get that one is appending and
> the other is modifying in-place, but how does this end up looking in
> the query language?
>

To ensure credit is given to the original authors, the initial patch I'm
working with (against Postgres 11 and 12) came from Denis Hirn, Torsten
Grust, and Christian Duta. Attached is a quick-and-dirty merge of that
patch that applies cleanly against 13-devel. It is not solid, at all, but
demonstrates the functionality. At present, my updates can be found at
https://github.com/jonahharris/postgres/tree/with-iterative

As the patch makes use of additional booleans for iteration, if there's
interest in incorporating this functionality, I'd like to discuss with Tom,
Robert, et al regarding the current use of booleans for CTE recursion
differentiation in parsing and planning. In terms of making it
production-ready, I think the cleanest method would be to use a bitfield
(rather than booleans) to differentiate recursive and iterative CTEs.
Though, as that would touch more code, it's obviously up for discussion.

I'm working on a few good standalone examples of PageRank, shortest path,
etc. But, the simplest Fibonacci example can be found here:

EXPLAIN ANALYZE
WITH RECURSIVE fib_sum (iteration, previous_number, new_number)
AS (SELECT 1, 0::numeric, 1::numeric
UNION ALL
SELECT (iteration + 1), new_number, (previous_number + new_number)
FROM fib_sum
WHERE iteration <= 10000)
SELECT r.iteration, r.new_number
FROM fib_sum r
ORDER BY 1 DESC
LIMIT 1;

QUERY PLAN

--------------------------------------------------------------------------------------------------------------------------
Limit (cost=3.81..3.81 rows=1 width=36) (actual time=44.418..44.418
rows=1 loops=1)
CTE fib_sum
-> Recursive Union (cost=0.00..3.03 rows=31 width=68) (actual
time=0.005..14.002 rows=10001 loops=1)
-> Result (cost=0.00..0.01 rows=1 width=68) (actual
time=0.004..0.004 rows=1 loops=1)
-> WorkTable Scan on fib_sum (cost=0.00..0.24 rows=3 width=68)
(actual time=0.001..0.001 rows=1 loops=10001)
Filter: (iteration <= 10000)
Rows Removed by Filter: 0
-> Sort (cost=0.78..0.85 rows=31 width=36) (actual time=44.417..44.417
rows=1 loops=1)
Sort Key: r.iteration DESC
Sort Method: top-N heapsort Memory: 27kB
-> CTE Scan on fib_sum r (cost=0.00..0.62 rows=31 width=36)
(actual time=0.009..42.660 rows=10001 loops=1)
Planning Time: 0.331 ms
Execution Time: 45.949 ms
(13 rows)

-- No ORDER/LIMIT is required with ITERATIVE as only a single tuple is
present
EXPLAIN ANALYZE
WITH ITERATIVE fib_sum (iteration, previous_number, new_number)
AS (SELECT 1, 0::numeric, 1::numeric
UNION ALL
SELECT (iteration + 1), new_number, (previous_number + new_number)
FROM fib_sum
WHERE iteration <= 10000)
SELECT r.iteration, r.new_number
FROM fib_sum r;

QUERY PLAN

--------------------------------------------------------------------------------------------------------------------------
CTE Scan on fib_sum r (cost=3.03..3.65 rows=31 width=36) (actual
time=11.626..11.627 rows=1 loops=1)
CTE fib_sum
-> Recursive Union (cost=0.00..3.03 rows=31 width=68) (actual
time=11.621..11.621 rows=1 loops=1)
-> Result (cost=0.00..0.01 rows=1 width=68) (actual
time=0.001..0.001 rows=1 loops=1)
-> WorkTable Scan on fib_sum (cost=0.00..0.24 rows=3 width=68)
(actual time=0.001..0.001 rows=1 loops=10001)
Filter: (iteration <= 10000)
Rows Removed by Filter: 0
Planning Time: 0.068 ms
Execution Time: 11.651 ms
(9 rows)

--
Jonah H. Harris