Re: Proposing WITH ITERATIVE - Mailing list pgsql-hackers
| From | Jonah H. Harris |
|---|---|
| Subject | Re: Proposing WITH ITERATIVE |
| Date | |
| Msg-id | CADUqk8XRkUB8bqiN9or+tSCkcJYJeoh=oy5EB9zpXO42D2S4ag@mail.gmail.com Whole thread Raw |
| In response to | Re: Proposing WITH ITERATIVE (Jeff Davis <pgsql@j-davis.com>) |
| Responses |
Re: Proposing WITH ITERATIVE
(Fabien COELHO <coelho@cri.ensmp.fr>)
|
| List | pgsql-hackers |
On Mon, Apr 27, 2020 at 8:50 PM Jeff Davis <pgsql@j-davis.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)
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;
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)
--------------------------------------------------------------------------------------------------------------------------
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
Attachment
pgsql-hackers by date: