Re: enable_incremental_sort changes query behavior - Mailing list pgsql-hackers

On Fri, Nov 20, 2020 at 1:51 PM James Coleman <jtc331@gmail.com> wrote:
> > This isn't a counterexample, because there's no join tree here -- or,
> > well, there is, but it's trivial, because there's only one relation
> > involved. You can't have a non-Var expression computed before you
> > finish all the joins, because there are no joins.
> >
> > What I said was: "target lists for any nodes below the top of the join
> > tree were previously always just Var nodes." The topmost join allowed
> > non-Var nodes before, but not lower levels.
>
> As I understand what you're saying, the attached (from the repro case
> in [1]'s discussion about parallel safety here) is a counterexample.
>
> Specifically we have a plan like:
>
> Merge Right Join
>   -> Unique
>     -> Gather Merge
>       -> Sort
>         -> Nested Loop
>
> The pathtarget of the nested loop contains non-var expressions (in
> this case a CASE expression).

Well, in this case there are two join trees, one for the subquery and
one for the outer query. The expressions for the subquery are computed
at the top of the plan tree for that subquery.

I guess I didn't specify before that I meant "at the top of the join
tree for a subquery level," but I did mean that. On principle, the
planner can't very realistically postpone evaluating a subquery's
expressions until the top of the outer query's join tree, because, as
in your example here, the subquery might contain an ORDER BY or
DISTINCT clause. And anyway, if you look at the planner code, you'll
see that every subquery is basically planned separately, unless it
gets flattened into the parent query, so even if it were possible to
postpone expression evaluation to outer subquery levels in some case,
the current code structure definitely would fail to achieve that goal.

However, apart from incremental sort, you can postpone evaluating a
join tree's expressions until you reach the top of the join tree, and
I think that's what we have always done in the past. Each baserel in
the join tree gets a target list containing a list of vars which
corresponds to its column list, and the joinrels get lists of vars
which correspond to the columns from the inputs are needed at higher
levels of the plan tree. At the top of the join tree, we stick in the
expressions, replacing the target list of the top node in the plan
tree; the expressions have to be computable from the inputs because
the inputs contain all the columns that we figured out were needed at
this level at the beginning of planning. But, if there are scans or
joins below the top level of the plan tree, then do they bubble up to
higher levels of the plan? Should they? It's pretty complicated.
Theoretically if I've computed length(somelongvar) then perhaps I can
just bubble the computed value up the plan tree, rather than the
original column, which might be cheaper. But that only works if the
higher levels only need length(somelongvar) and not somelongvar
itself. I don't think there's any logic to work stuff like this out,
unless the incremental sort patch added some, because I don't think we
ever did it before. And it may be that it doesn't really matter, at
least when there aren't volatile functions: perhaps the worst case is
that we evaluate a non-volatile function twice, and maybe that's just
a performance consequence that we can live with. But on the other
hand, maybe it breaks stuff.

Or, on the third hand, maybe I'm wrong about what the rule was in the
first place. This is certainly a complicated topic. I don't think I'm
wrong, or I wouldn't be bothering to write emails about it, but that
doesn't mean I'm not wrong anyway.

-- 
Robert Haas
EDB: http://www.enterprisedb.com