Content-Type: multipart/alternative;
 boundary="------------Ho3fyGhr0cCfnVHBUQFRRvXf"
Message-ID: <c0cf4fbd-a5db-e5dc-935f-399a355c02ee@gusw.net>
Date: Thu, 29 Dec 2022 02:31:59 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:102.0) Gecko/20100101
 Thunderbird/102.6.1
Subject: Re: When you really want to force a certain join type?
Content-Language: en-US
To: Justin Pryzby <pryzby@telsasoft.com>
Cc: pgsql-performance@lists.postgresql.org
References: <70b2ee7b-8e8b-d884-8ca2-590a242308b8@gusw.net>
 <20221228154837.GX1153@telsasoft.com>
From: Gunther Schadow <raj@gusw.net>
In-Reply-To: <20221228154837.GX1153@telsasoft.com>
Archived-At: 
 <https://www.postgresql.org/message-id/c0cf4fbd-a5db-e5dc-935f-399a355c02ee%40gusw.net>
Precedence: bulk

This is a multi-part message in MIME format.
--------------Ho3fyGhr0cCfnVHBUQFRRvXf
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit

On 12/28/2022 10:48 AM, Justin Pryzby wrote:
> Maybe the new parameter in v15 would help.
>
> https://www.postgresql.org/docs/15/runtime-config-query.html#GUC-RECURSIVE-WORKTABLE-FACTOR
> recursive_worktable_factor (floating point)
>
>      Sets the planner's estimate of the average size of the working table
>      of a recursive query, as a multiple of the estimated size of the
>      initial non-recursive term of the query. This helps the planner
>      choose the most appropriate method for joining the working table to
>      the query's other tables. The default value is 10.0. A smaller value
>      such as 1.0 can be helpful when the recursion has low “fan-out” from
>      one step to the next, as for example in shortest-path queries. Graph
>      analytics queries may benefit from larger-than-default values.

Thanks that's something I will try after I upgraded.

But speaking of such other uses for recursive queries, I can say I have 
quite a bit of experience of turning graph related "traversal" and 
search and optimization and classification queries into SQL, in short, 
computing the transitive closure. And usually I have stayed away from 
the recursive WITH query and instead set up a start table and then 
perform the iterative step. And there are two ways to go about it. Say 
you have a graph, simple nodes and arcs. You want to find all paths 
through the graph.

Now you can set up start nodes and then extend them at the end by 
joining the recursive table to the simple arc table and extend your path 
every time. This is what the WITH RECURSIVE supports. These queries 
linearly iterate as many times as the length of the longest path.

with recursive arcs as (
   select source, target, 1 as distance, ...
     from ...
), paths as (
   select * from arcs
   union all
   select a.source, b.target, a.distance + 1 as distance, ...
     from paths a inner join_*arcs *_b
       on(b.source = a.target)
)
select * from paths

But another way is to join paths with paths. It would be this, which I 
think I have seen postgresql unable to deal with:

with recursive arcs as (
   select source, target, 1 as distance, ...
     from ...
), paths as (
   select * from arcs
   union all
   select a.source, b.target, a.distance + 1 as distance, ...
     from paths a inner join_*paths *_b
       on(b.source = a.target)
)
select * from paths

So, instead of the recursive union to join back to the fixed table, it 
joins the recursive table to the recursive table, and the benefit of 
that is that these queries converge much quicker. Instead of going 10 
iterations to find a path of length 10, you go 1 iteration to find all 
paths of 2 (if distance 1 is the base table of all arcs), then next you 
find paths of up to 4 then you find paths of up to 8, then 16, 32, ... 
This converges much faster. I usually do that as follows

create table paths as
select source, target, 1 as distance, ...
   from arcs;

prepare rep as
insert into paths(source, target, distance, ...)
select a.source, b.target, a.distance + b.distance as distance, ...
   from paths a inner join paths b on(b.source = a.target)
except
select * from paths;

execute rep;
execute rep;
...

or instead of the except, in order to minimize distances:

where not exists (select 1 from paths x
                    where x.source = a.source
                      and x.target = a.target
                      and x.distance < a.distance)

I have even done a group by in the recursive step which replaces the 
paths relation at every iteration (e.g. with only minimal distance paths).

Since this converges so rapidly I often prefer that approach over a 
recursive union query.

I think in IBM DB2 allowed to join the recursive table with itself. Is 
this something you want to support at some time?

Also, why even use the RECURSIVE keyword, DB2 didn't need it, and the 
query analyzer should immediately see the recursion, so no need to have 
that keyword.

regards,
-Gunther

--------------Ho3fyGhr0cCfnVHBUQFRRvXf
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: 8bit

<html>
  <head>
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
  </head>
  <body>
    <div class="moz-cite-prefix">On 12/28/2022 10:48 AM, Justin Pryzby
      wrote:
    </div>
    <blockquote type="cite"
      cite="mid:20221228154837.GX1153@telsasoft.com">
      <pre class="moz-quote-pre" wrap="">Maybe the new parameter in v15 would help.

<a class="moz-txt-link-freetext" href="https://www.postgresql.org/docs/15/runtime-config-query.html#GUC-RECURSIVE-WORKTABLE-FACTOR">https://www.postgresql.org/docs/15/runtime-config-query.html#GUC-RECURSIVE-WORKTABLE-FACTOR</a>
recursive_worktable_factor (floating point)

    Sets the planner's estimate of the average size of the working table
    of a recursive query, as a multiple of the estimated size of the
    initial non-recursive term of the query. This helps the planner
    choose the most appropriate method for joining the working table to
    the query's other tables. The default value is 10.0. A smaller value
    such as 1.0 can be helpful when the recursion has low “fan-out” from
    one step to the next, as for example in shortest-path queries. Graph
    analytics queries may benefit from larger-than-default values.</pre>
    </blockquote>
    <p>Thanks that's something I will try after I upgraded.</p>
    <p>But speaking of such other uses for recursive queries, I can say
      I have quite a bit of experience of turning graph related
      "traversal" and search and optimization and classification queries
      into SQL, in short, computing the transitive closure. And usually
      I have stayed away from the recursive WITH query and instead set
      up a start table and then perform the iterative step. And there
      are two ways to go about it. Say you have a graph, simple nodes
      and arcs. You want to find all paths through the graph. <br>
    </p>
    <p>Now you can set up start nodes and then extend them at the end by
      joining the recursive table to the simple arc table and extend
      your path every time. This is what the WITH RECURSIVE supports.
      These queries linearly iterate as many times as the length of the
      longest path. <br>
    </p>
    <pre>with recursive arcs as (
  select source, target, 1 as distance, ...
    from ...
), paths as (
  select * from arcs
  union all
  select a.source, b.target, a.distance + 1 as distance, ...
    from paths a inner join <u><b>arcs </b></u>b
      on(b.source = a.target)
)
select * from paths
</pre>
    <p>But another way is to join paths with paths. It would be this,
      which I think I have seen postgresql unable to deal with:</p>
    <pre>with recursive arcs as (
  select source, target, 1 as distance, ...
    from ...
), paths as (
  select * from arcs
  union all
  select a.source, b.target, a.distance + 1 as distance, ...
    from paths a inner join <u><b>paths </b></u>b
      on(b.source = a.target)
)
select * from paths</pre>
    <p></p>
    <p>So, instead of the recursive union to join back to the fixed
      table, it joins the recursive table to the recursive table, and
      the benefit of that is that these queries converge much quicker.
      Instead of going 10 iterations to find a path of length 10, you go
      1 iteration to find all paths of 2 (if distance 1 is the base
      table of all arcs), then next you find paths of up to 4 then you
      find paths of up to 8, then 16, 32, ... This converges much
      faster. I usually do that as follows<br>
    </p>
    <pre>create table paths as
select source, target, 1 as distance, ...
  from arcs;

prepare rep as
insert into paths(source, target, distance, ...)
select a.source, b.target, a.distance + b.distance as distance, ... 
  from paths a inner join paths b on(b.source = a.target) 
except
select * from paths;

execute rep;
execute rep;
...
</pre>
    <p>or instead of the except, in order to minimize distances:</p>
    <pre>where not exists (select 1 from paths x 
                   where x.source = a.source 
                     and x.target = a.target
                     and x.distance &lt; a.distance)
</pre>
    <p>I have even done a group by in the recursive step which replaces
      the paths relation at every iteration (e.g. with only minimal
      distance paths).<br>
    </p>
    <p>Since this converges so rapidly I often prefer that approach over
      a recursive union query. <br>
    </p>
    <p>I think in IBM DB2 allowed to join the recursive table with
      itself. Is this something you want to support at some time?</p>
    <p>Also, why even use the RECURSIVE keyword, DB2 didn't need it, and
      the query analyzer should immediately see the recursion, so no
      need to have that keyword.</p>
    <p>regards,<br>
      -Gunther<br>
    </p>
  </body>
</html>

--------------Ho3fyGhr0cCfnVHBUQFRRvXf--