Re: make add_paths_to_append_rel aware of startup cost

On Mon, Sep 18, 2023 at 11:58 AM David Rowley <dgrowleyml(at)gmail(dot)com> wrote:

> On Mon, 18 Sept 2023 at 01:42, Andy Fan <zhihui(dot)fan1213(at)gmail(dot)com> wrote:
> > On Fri, Sep 15, 2023 at 3:15 PM David Rowley <dgrowleyml(at)gmail(dot)com>
> wrote:
> >> Instead of doing that, why don't you just create a completely new
> >> AppendPath containing all the cheapest_startup_paths and add that to
> >> the append rel. You can optimise this and only do it when
> >> rel->consider_startup is true.
> >>
> >> Does the attached do anything less than what your patch does?
> >
> >
> > We can work like this, but there is one difference from what
> > my current patch does. It is cheapest_startup_path vs cheapest
> > fraction path. For example if we have the following 3 paths with
> > all of the estimated rows is 100 and the tuple_fraction is 10.
>
> Yeah, it's true that the version I wrote didn't consider the
> fractional part, but I didn't really see it as worse than what you
> did. It looks like you're assuming that every append child will have

the same number of tuples read from it, but it seems to me that it
> would only be valid to use the fractional part for the first child.

The path chosen for subsequent child paths would, if done correctly,
> need to account for the estimated rows from the previous child paths.
>

Actually this is consistent with what generate_union_paths does now.

/*
* If plain UNION, tell children to fetch all tuples.
*
* Note: in UNION ALL, we pass the top-level tuple_fraction unmodified to
* each arm of the UNION ALL. One could make a case for reducing the
* tuple fraction for later arms (discounting by the expected size of the
* earlier arms' results) but it seems not worth the trouble. The normal
* case where tuple_fraction isn't already zero is a LIMIT at top level,
* and passing it down as-is is usually enough to get the desired result
* of preferring fast-start plans.
*/
if (!op->all)
root->tuple_fraction = 0.0;

UNION ALL is pretty like append rel.

It's not valid here to copy the code in generate_orderedappend_paths()
> as MergeAppend won't necessarily exhaust the first child subpath first
> like Append will.
>

Not sure which code you are referring to, but the code I refer to
much is generate_union_paths and set_subquery_pathlist.

> > Path 1: startup_cost = 60, total_cost = 80 -- cheapest total cost.
> > Path 2: startup_cost = 10, total_cost = 1000 -- cheapest startup cost
> > Path 3: startup_cost = 20, total_cost = 90 -- cheapest fractional cost
> >
> > So with the patch you propose, Path 1 & Path 3 are chosen to build
> > append path. but with my current patch, Only path 3 is kept. IIUC,
> > path 3 should be the best one in this case.
>
> I assume you mean mine would build AppendPaths for 1+2, not 1+3.

Yes, it should be 1+2.

>
>
You mentioned:
>
> > I just find it is hard to build the case for Identifier 2/3/4.
>
> I wonder if this is because generate_orderedappend_paths() handles
> startup paths and most cases will that need a cheap startup plan will
> require some sort of pathkeys.
>

Probably yes.

> The example you mentioned of:
>
> (select * from tenk1 order by hundred)
> UNION ALL
> (select * from tenk1 order by hundred)
> limit 3;
>
> I don't find this to be a compellingly real-world case. The planner
> is under no obligation to output rows from the 1st branch of the UNION
> ALL before the 2nd one. If the user cared about that then they'd have
> instead added a top-level ORDER BY, in which case the planner seems
> happy to use the index scan:
>

Sorry about the test case, here is the one with more compelling
real-world.

with s1 as (select * from tenk1 join tenk2 using (hundred)),
s2 as (select * from tenk1 join tenk2 using (hundred))
select * from s1
union all
select * from s2
limit 3;

It would be good if you could provide a bit more detail on the cases
> you want to improve here. For example, if your #4 case, you have
> "WHERE xxx". I don't know if "xxx" is just a base qual or if there's a
> correlation to the outer query in there.
>

for the #4, the quickest test case is

select * from tenk1 where exists
(
with s1 as (select * from tenk1 join tenk2 using (hundred)),
s2 as (select * from tenk1 join tenk2 using (hundred))
select * from s1
union all
select * from s2
where random() > 0.4);

random() is used to make it can't be pull-up. and exists implies
LIMIT 1;

Another concern I have with your patch is that it seems to be under
> the impression that there being further joins to evaluate at this
> query level is the only reason that we would have to pull more than
> the tuple fraction number of rows from the query. What gives you the
> confidence that's the only reason we may want to pull more than the
> tuple fraction of tuples from the append child?
>

I think you are talking about something like ORDER BY, GROUP BY
clause, I do overlook it. but if we admit cheapest fractional cost
is a right factor to consider, this issue is not unresolvable since parse
is at hand.

At last, you ignore the part of set_subquery_pathlist. I always use it
to prove the value of the cheapest fractional cost. Am I missing something?

/*
* We can safely pass the outer tuple_fraction down to the subquery
if the
* outer level has no joining, aggregation, or sorting to do.
Otherwise
* we'd better tell the subquery to plan for full retrieval. (XXX
This
* could probably be made more intelligent ...)
*/
if (parse->hasAggs ||
parse->groupClause ||
parse->groupingSets ||
root->hasHavingQual ||
parse->distinctClause ||
parse->sortClause ||
has_multiple_baserels(root))
tuple_fraction = 0.0; /* default case */
else
tuple_fraction = root->tuple_fraction;

What do you think about this in my last reply? "If my above
analysis is correct, I think the best way to handle this is if there
is no more tables to join, we use cheapest fraction cost for all
the kinds of relations, including plain relation, append rel,
subquery and so on, If we have more tables to join, we use
cheapest startup cost.". This is what is in my mind now.

--
Best Regards
Andy Fan