Horton

Thread

Commits

  1. Reconsider the representation of join alias Vars.

  2. Make parser rely more heavily on the ParseNamespaceItem data structure.

  3. Refactor parser's generation of Var nodes.

  1. Clarifying/rationalizing Vars' varno/varattno/varnoold/varoattno

    Tom Lane <tgl@sss.pgh.pa.us> — 2019-12-16T17:00:43Z

    I started to think a little harder about the rough ideas I sketched
yesterday in [1] about making the planner deal with outer joins in
a less ad-hoc manner.  One thing that emerged very quickly is that
I was misremembering how the parser creates join alias Vars.
Consider for example

create table t1(a int, b int);
create table t2(x int, y int);

select a, t1.a, x, t2.x from t1 left join t2 on b = y;

The Vars that the parser will produce in the SELECT's targetlist have,
respectively,

	         :varno 3 
	         :varattno 1 

	         :varno 1 
	         :varattno 1 

	         :varno 3 
	         :varattno 3 

	         :varno 2 
	         :varattno 1 

(where "3" is the rangetable index of the unnamed join relation).
So as far as the parser is concerned, a "join alias" var is just
one that you named by referencing the join output column; it's
not tracking whether the value is one that's affected by the join
semantics.

What I'd like, in order to make progress with the planner rewrite,
is that all four Vars in the tlist have varno 3, showing that
they are (potentially) semantically distinct from the Vars in
the JOIN ON clause (which'd have varnos 1 and 2 in this example).

This is a pretty small change as far as most of the system is
concerned; there should be noplace that fails to cope with a
join alias Var, since it'd have been legal to write a join
alias Var in anyplace that would change.

However, it's a bit sticky for ruleutils.c, which needs to be
able to regurgitate these Vars in their original spellings.
(This is "needs", not "wants", because there are various
conditions under which we don't have the option of spelling
it either way.  For instance, if both tables expose columns
named "z", then you must write "t1.z" or "t2.z"; the columns
won't have unique names at the join level.)

What I'd like to do about that is redefine the existing
varnoold/varoattno fields as being the "syntactic" identifier
of the Var, versus the "semantic" identifier that varno/varattno
would be, and have ruleutils.c always use varnoold/varoattno
when trying to print a Var.

I think that this approach would greatly clarify what those fields
mean and how they should be manipulated --- for example, it makes
it clear that _equalVar() should ignore varnoold/varoattno, since
Vars with the same semantic meaning should be considered equal
even if they were spelled differently.

While at it, I'd be inclined to rename those fields, since the
existing names aren't even consistently spelled, much less meaningful.
Perhaps "varsno/varsattno" or "varnosyn/varattnosyn".

Thoughts?

			regards, tom lane

[1] https://www.postgresql.org/message-id/7771.1576452845%40sss.pgh.pa.us

  2. Re: Clarifying/rationalizing Vars' varno/varattno/varnoold/varoattno

    Robert Haas <robertmhaas@gmail.com> — 2019-12-16T20:55:26Z

    On Mon, Dec 16, 2019 at 12:00 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
> What I'd like, in order to make progress with the planner rewrite,
> is that all four Vars in the tlist have varno 3, showing that
> they are (potentially) semantically distinct from the Vars in
> the JOIN ON clause (which'd have varnos 1 and 2 in this example).
>
> This is a pretty small change as far as most of the system is
> concerned; there should be noplace that fails to cope with a
> join alias Var, since it'd have been legal to write a join
> alias Var in anyplace that would change.

I don't have an opinion about the merits of this change, but I'm
curious how this manages to work. It seems like there would be a fair
number of places that needed to map the join alias var back to some
baserel that can supply it. And it seems like there could be multiple
levels of join alias vars as well, since you could have joins nested
inside of other joins, possibly with subqueries involved.

At some point I had the idea that it might make sense to have
equivalence classes that had both a list of full members (which are
exactly equivalent) and nullable members (which are either equivalent
or null). I'm not sure whether that idea is of any practical use,
though. It does seems strange to me that the representation you are
proposing gets at the question only indirectly. The nullable version
of the Var has got a different varno and varattno than the
non-nullable version of the Var, but other than that there's no
connection between them. How do you go about matching those together?
I guess varnoold/varoattno can do the trick, but if that's only being
used by ruleutils.c then there must be some other mechanism.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

  3. Re: Clarifying/rationalizing Vars' varno/varattno/varnoold/varoattno

    Tom Lane <tgl@sss.pgh.pa.us> — 2019-12-16T21:40:42Z

    Robert Haas <robertmhaas@gmail.com> writes:
> On Mon, Dec 16, 2019 at 12:00 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> What I'd like, in order to make progress with the planner rewrite,
>> is that all four Vars in the tlist have varno 3, showing that
>> they are (potentially) semantically distinct from the Vars in
>> the JOIN ON clause (which'd have varnos 1 and 2 in this example).

> I don't have an opinion about the merits of this change, but I'm
> curious how this manages to work. It seems like there would be a fair
> number of places that needed to map the join alias var back to some
> baserel that can supply it. And it seems like there could be multiple
> levels of join alias vars as well, since you could have joins nested
> inside of other joins, possibly with subqueries involved.

Sure.  Right now, we smash join aliases down to the ultimately-referenced
base vars early in planning (see flatten_join_alias_vars).  After the
patch that I'm proposing right now, that would continue to be the case,
so there'd be little change in most of the planner from this.  However,
the later changes that I speculated about in the other thread would
involve delaying that smashing in cases where the join output value is
possibly different from the input value, so that we would have a clear
representational distinction between those things, something we lack
today.

> At some point I had the idea that it might make sense to have
> equivalence classes that had both a list of full members (which are
> exactly equivalent) and nullable members (which are either equivalent
> or null).

Yeah, this is another way that you might get at the problem, but it
seems to me it's not really addressing the fundamental squishiness.
If the "nullable members" might be null, then what semantics are
you promising exactly?  You certainly haven't got anything that
defines a sort order for them.

> I'm not sure whether that idea is of any practical use,
> though. It does seems strange to me that the representation you are
> proposing gets at the question only indirectly. The nullable version
> of the Var has got a different varno and varattno than the
> non-nullable version of the Var, but other than that there's no
> connection between them. How do you go about matching those together?

You'd have to look into the join's joinaliasvars list (or more likely,
some new planner data structure derived from that) to discover that
there's any connection.  That seems fine to me, because AFAICS
relatively few places would need to do that.  It's certainly better
than using a representation that suggests that two values are the same
when they're not.  (TBH, I've spent the last dozen years waiting for
someone to come up with an example that completely breaks equivalence
classes, if not our entire approach to outer joins.  So far we've been
able to work around every case, but we've sometimes had to give up on
optimizations that would be nice to have.)

A related example that is bugging me is that the grouping-sets patch
broke the meaning of Vars that represent post-grouping values ---
there again, the value might have gone to null as a result of grouping,
but you can't tell it apart from values that haven't.  I think this is
less critical because such Vars can't appear in FROM/WHERE so they're
of little interest to most of the planner, but we've still had to put
in kluges like 90947674f because of that.  We might be well advised
to invent some join-alias-like mechanism for those.  (I have a vague
memory now that Gierth wanted to do something like that and I
discouraged it because it was unlike the way we did outer joins ...
so he was right, but what we should have done was fix outer joins not
double down on the kluge.)

> I guess varnoold/varoattno can do the trick, but if that's only being
> used by ruleutils.c then there must be some other mechanism.

Actually, they're nothing but debug support currently --- ruleutils
doesn't use them either.  It's possible that this change would allow
ruleutils to save cycles in a lot of cases by not having to drill down
through subplans to identify the ultimate referent of upper-plan Vars.
But I haven't investigated that yet.

			regards, tom lane

  4. Re: Clarifying/rationalizing Vars' varno/varattno/varnoold/varoattno

    Tom Lane <tgl@sss.pgh.pa.us> — 2019-12-20T16:12:53Z

    I wrote:
> I started to think a little harder about the rough ideas I sketched
> yesterday in [1] about making the planner deal with outer joins in
> a less ad-hoc manner.
> [1] https://www.postgresql.org/message-id/7771.1576452845%40sss.pgh.pa.us

After further study, the idea of using join alias vars to track
outer-join semantics basically doesn't work at all.  Join alias vars in
their current form (ie, references to the output columns of a JOIN RTE)
aren't suitable for the purpose of representing possibly-nulled inputs
to that same RTE.  There are two big stumbling blocks:

* In the presence of JOIN USING, we don't necessarily have a JOIN output
column that is equivalent to either input column.  The output is
definitely not equal to the nullable side of an OJ, since it won't go to
NULL; and it might not be equivalent to the non-nullable side either,
because JOIN USING might've coerced it to some common datatype.

* We also don't have any output column that could represent a whole-row
reference to either input table.  I thought about representing that with
a RowExpr of join output Vars, but that fails to preserve the existing
semantics: a whole-row reference to the nullable side goes to NULL, not
to a row of NULLs, when we're null-extending the join.

So that kind of crashed and burned.  We could maybe fake it by inventing
some new conventions about magic attnums of the join RTE that correspond
to the values we want, but that seems really messy and error-prone.

The alternatives that seem plausible at this point are

(1) Create some sort of wrapper node indicating "the contents of this
expression might be replaced by NULL".  This is basically what the
planner's PlaceHolderVars do, so maybe we'd just be talking about
introducing those at some earlier stage.

(2) Explicitly mark Vars as being nullable by some outer join.  I think
we could probably get this down to one additional integer field in
struct Var, so it wouldn't be too much of a penalty.

The wrapper approach is more general since you can wrap something
that's not necessarily a plain Var; but it's also bulkier and so
probably a bit less efficient.  I'm not sure which idea I like better.

With either approach, we could either make parse analysis inject the
nullability markings, or wait to do it in the planner.  On a purely
abstract system structural level, I like the former better: it is
exactly the province of parse analysis to decide what are the semantics
of what the user typed, and surely what a Var means is part of that.
OTOH, if we do it that way, the planner potentially has to rearrange the
markings after it does join strength reduction; so maybe it's best to
just wait till after that planning phase to address this at all.

Any thoughts about that?

Anyway, I had started to work on getting parse analysis to label
outer-join-nullable Vars properly, and soon decided that no matter how
we do it, there's not enough information available at the point where
parse analysis makes a Var.  The referenced RTE is not, in itself,
enough info, and I don't think we want to decorate RTEs with more info
that's only needed during parse analysis.  What would be saner is to add
any extra info to the ParseNamespaceItem structs.  But that requires
some refactoring to allow the ParseNamespaceItems, not just the
referenced RTEs, to be passed down through Var lookup/construction.
So attached is a patch that refactors things that way.  As proof of
concept, I added the rangetable index to ParseNamespaceItem, and used
that to get rid of the RTERangeTablePosn() searches that we formerly had
in a bunch of places.  Now, RTERangeTablePosn() isn't likely to be all
that expensive, but still this should be a little faster and cleaner.
Also, I was able to confine the fuzzy-lookup heuristic stuff to within
parse_relation.c instead of letting it bleed out to the rest of the
parser.

This seems to me to be good cleanup regardless of whether we ever
ask parse analysis to label outer-join-nullable Vars.  So, barring
objection, I'd like to push it soon.

			regards, tom lane

  5. Re: Clarifying/rationalizing Vars' varno/varattno/varnoold/varoattno

    Robert Haas <robertmhaas@gmail.com> — 2019-12-20T17:11:31Z

    On Fri, Dec 20, 2019 at 11:13 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
> The alternatives that seem plausible at this point are
>
> (1) Create some sort of wrapper node indicating "the contents of this
> expression might be replaced by NULL".  This is basically what the
> planner's PlaceHolderVars do, so maybe we'd just be talking about
> introducing those at some earlier stage.
>
> (2) Explicitly mark Vars as being nullable by some outer join.  I think
> we could probably get this down to one additional integer field in
> struct Var, so it wouldn't be too much of a penalty.
>
> The wrapper approach is more general since you can wrap something
> that's not necessarily a plain Var; but it's also bulkier and so
> probably a bit less efficient.  I'm not sure which idea I like better.

I'm not sure which is better, either, although I would like to note in
passing that the name PlaceHolderVar seems to me to be confusing and
terrible. It took me years to understand it, and I've never been
totally sure that I actually do. Why is it not called
MightBeNullWrapper or something?

If you chose to track it in the Var, maybe you could do better than to
track whether it might have gone to NULL. For example, perhaps you
could track the set of baserels that are syntactically below the Var
location and have the Var on the nullable side of a join, rather than
just have a Boolean that indicates whether there are any. I don't know
whether the additional effort would be worth the cost of maintaining
the information, but it seems like it might be.

> With either approach, we could either make parse analysis inject the
> nullability markings, or wait to do it in the planner.  On a purely
> abstract system structural level, I like the former better: it is
> exactly the province of parse analysis to decide what are the semantics
> of what the user typed, and surely what a Var means is part of that.
> OTOH, if we do it that way, the planner potentially has to rearrange the
> markings after it does join strength reduction; so maybe it's best to
> just wait till after that planning phase to address this at all.
>
> Any thoughts about that?

Generally, I like the idea of driving this off the parse tree, because
it seems to me that, ultimately, whether a Var is *potentially*
nullable or not depends on the query as provided by the user. And, if
we replan the query, these determinations don't change, at least as
long as they are only driven by the query syntax and not, say,
attisnull or opclass details. It would be nice not to redo the work
unnecessarily. However, that seems to require some way of segregating
the information we derive as a preliminary and syntactical judgement
from subsequent inferences made during query planning, because the
latter CAN change during replanning.

It might be useful 'Relids' with each Var rather than just 'bool'. In
other words, based on where the reference to the Var is in the
original query text, figure out the set of joins where (1) the Var is
syntactically above the join and (2) on the nullable side, and then
put the relations on the other sides of those joins into the Relids.
Then if you later determine that A LEFT JOIN B actually can't make
anything go to null, you can just ignore the presence of A in this set
for the rest of planning. I feel like this kind of idea might have
other applications too, although I admit that it also has a cost.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

  6. Re: Clarifying/rationalizing Vars' varno/varattno/varnoold/varoattno

    Tom Lane <tgl@sss.pgh.pa.us> — 2019-12-20T18:16:35Z

    Robert Haas <robertmhaas@gmail.com> writes:
> On Fri, Dec 20, 2019 at 11:13 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> The alternatives that seem plausible at this point are
>> ...
>> (2) Explicitly mark Vars as being nullable by some outer join.  I think
>> we could probably get this down to one additional integer field in
>> struct Var, so it wouldn't be too much of a penalty.

> It might be useful 'Relids' with each Var rather than just 'bool'. In
> other words, based on where the reference to the Var is in the
> original query text, figure out the set of joins where (1) the Var is
> syntactically above the join and (2) on the nullable side, and then
> put the relations on the other sides of those joins into the Relids.
> Then if you later determine that A LEFT JOIN B actually can't make
> anything go to null, you can just ignore the presence of A in this set
> for the rest of planning. I feel like this kind of idea might have
> other applications too, although I admit that it also has a cost.

Yeah, a bitmapset might be a better idea than just recording the topmost
relevant join's relid.  But it's also more expensive, and I think we ought
to keep the representation of Vars as cheap as possible.  (On the third
hand, an empty BMS is cheap, while if the alternative to a non-empty BMS
is to put a separate wrapper node around the Var, that's hardly better.)

The key advantage of a BMS, really, is that it dodges the issue of needing
to re-mark Vars when you re-order two outer joins using the outer join
identities.  You really don't want that to result in having to consider
Vars above the two joins to be different depending on the order you chose
for the OJs, because that'd enormously complicate considering both sorts
of Paths at the same time.  The rough idea I'd had about coping with that
issue with just a single relid is that maybe it doesn't matter --- maybe
we can always mark Vars according to the *syntactically* highest nulling
OJ, regardless of the actual join order.  But I'm not totally sure that
can work.

In any case, what the planner likes to work with is sets of baserel
relids covered by a join, not the relid(s) of the join RTEs themselves.
So maybe there's going to be a conversion step required anyhow.

			regards, tom lane

  7. Re: Clarifying/rationalizing Vars' varno/varattno/varnoold/varoattno

    Andres Freund <andres@anarazel.de> — 2019-12-21T00:19:10Z

    Hi,

On 2019-12-20 11:12:53 -0500, Tom Lane wrote:
> (2) Explicitly mark Vars as being nullable by some outer join.  I think
> we could probably get this down to one additional integer field in
> struct Var, so it wouldn't be too much of a penalty.

I've for a while wished that we could, e.g. so execution can use faster
tuple deforming code, infer nullability of columns above the scan
level. Right now there's no realistic way ExecTypeFromTL() can figure
that out, for upper query nodes. If we were to introduce something like
the field you suggest, it'd be darn near trivial.

OTOH, I'd really at some point like to start moving TupleDesc
computations to the planner - they're quite expensive, and we do them
over and over again. And that would not necessarily need a convenient
execution time representation anymore. But I don't think moving
tupledesc computation into the planner is a small rearrangement...


Would we want to have only boolean state, or more information (e.g. not
null, maybe null, is null)?


Greetings,

Andres Freund

  8. Re: Clarifying/rationalizing Vars' varno/varattno/varnoold/varoattno

    Tom Lane <tgl@sss.pgh.pa.us> — 2019-12-31T03:50:21Z

    I wrote:
> Anyway, I had started to work on getting parse analysis to label
> outer-join-nullable Vars properly, and soon decided that no matter how
> we do it, there's not enough information available at the point where
> parse analysis makes a Var.  The referenced RTE is not, in itself,
> enough info, and I don't think we want to decorate RTEs with more info
> that's only needed during parse analysis.  What would be saner is to add
> any extra info to the ParseNamespaceItem structs.

Here is a further step on this journey.  It's still just parser
refactoring, and doesn't (AFAICT) result in any change in generated
parse trees, but it seems worth posting and committing separately.

The two key ideas here are:

1. Integrate ParseNamespaceItems a bit further into the parser's
relevant APIs.  In particular, the addRangeTableEntryXXX functions
no longer return just a bare RTE, but a ParseNamespaceItem wrapper
for it.  This gets rid of a number of kluges we had for finding out
the RT index of the new RTE, since that's now carried along in the
nsitem --- we no longer need fragile assumptions about how the new
RTE is still the last one in the rangetable, at some point rather
distant from where it was actually appended to the list.

Most of the callers of addRangeTableEntryXXX functions just turn
around and pass the result to addRTEtoQuery, which I've renamed
to addNSItemtoQuery; it doesn't gin up a new nsitem anymore but
just installs the one it's passed.  It's perhaps a bit inconsistent
that I renamed that function but not addRangeTableEntryXXX.
I considered making those addNamespaceItemXXX, but desisted on the
perhaps-thin grounds that they don't link the new nsitem into the
parse state, only the RTE.  This could be argued of course.

2. Add per-column information to the ParseNamespaceItems.  As of
this patch, the useful part of that is column type/typmod/collation
info which can be used to generate Vars referencing this RTE.
I envision that the next step will involve generating the Vars'
identity (varno/varattno columns) from that as well, and this
patch includes logic to set up some associated per-column fields.
But those are not actually getting fed into the Vars quite yet.
(The step after that will be to add outer-join-nullability info.)

But independently of those future improvements, this patch is
a win because it allows carrying forward column-type info that's
known at the time we do addRangeTableEntryXXX, and using that
when we make a Var, instead of having to do the rather expensive
computations involved in expandRTE() or get_rte_attribute_type().
get_rte_attribute_type() is indeed gone altogether, and while
expandRTE() is still needed, it's not used in any performance-critical
parse analysis code paths.

On a complex-query test case that I've used before [1], microbenchmarking
just raw parsing plus parse analysis shows a full 20% speedup over HEAD,
which I think can mostly be attributed to getting rid of the syscache
lookups that get_rte_attribute_type() did for Vars referencing base
relations.  The total impact over a complete query execution cycle
is a lot less of course.  Still, it's pretty clearly a performance win,
and to my mind the code is also cleaner --- this is paying down some
technical debt from when we bolted JOIN syntax onto pre-existing
parsing code.

Barring objections, I plan to commit this fairly soon and get onto the
next step, which will start to have ramifications outside the parser.

			regards, tom lane

[1] https://www.postgresql.org/message-id/6970.1545327857%40sss.pgh.pa.us

  9. Re: Clarifying/rationalizing Vars' varno/varattno/varnoold/varoattno

    Tom Lane <tgl@sss.pgh.pa.us> — 2020-01-02T17:37:26Z

    I wrote:
> Here is a further step on this journey.  It's still just parser
> refactoring, and doesn't (AFAICT) result in any change in generated
> parse trees, but it seems worth posting and committing separately.

Pushed at 5815696bc.

> 2. Add per-column information to the ParseNamespaceItems.  As of
> this patch, the useful part of that is column type/typmod/collation
> info which can be used to generate Vars referencing this RTE.
> I envision that the next step will involve generating the Vars'
> identity (varno/varattno columns) from that as well, and this
> patch includes logic to set up some associated per-column fields.
> But those are not actually getting fed into the Vars quite yet.

Here's a further step that does that.

The core idea of this patch is to make the parser generate join alias
Vars (that is, ones with varno pointing to a JOIN RTE) only when the
alias Var is actually different from any raw join input, that is a type
coercion and/or COALESCE is necessary to generate the join output value.
Otherwise just generate varno/varattno pointing to the relevant join
input column.

In effect, this means that the planner's flatten_join_alias_vars()
transformation is already done in the parser, for all cases except
(a) columns that are merged by JOIN USING and are transformed in the
process, and (b) whole-row join Vars.  In principle that would allow
us to skip doing flatten_join_alias_vars() in many more queries than
we do now, but we don't have quite enough infrastructure to know that
we can do so --- in particular there's no cheap way to know whether
there are any whole-row join Vars.  I'm not sure if it's worth the
trouble to add a Query-level flag for that, and in any case it seems
like fit material for a separate patch.  But even without skipping the
work entirely, this should make flatten_join_alias_vars() faster,
particularly where there are nested joins that it had to flatten
recursively.

An essential part of this change is to replace Var nodes'
varnoold/varoattno fields with varnosyn/varattnosyn, which have
considerably more tightly-defined meanings than the old fields: when
they differ from varno/varattno, they identify the Var's position in
an aliased JOIN RTE, and the join alias is what ruleutils.c should
print for the Var.  This is necessary because the varno change
destroyed ruleutils.c's ability to find the JOIN RTE from the Var's
varno.

Another way in which this change broke ruleutils.c is that it's no
longer feasible to determine, from a JOIN RTE's joinaliasvars list,
which join columns correspond to which columns of the join's immediate
input relations.  (If those are sub-joins, the joinaliasvars entries
may point to columns of their base relations, not the sub-joins.)
But that was a horrid mess requiring a lot of fragile assumptions
already, so let's just bite the bullet and add some more JOIN RTE
fields to make it more straightforward to figure that out.  I added
two integer-List fields containing the relevant column numbers from
the left and right input rels, plus a count of how many merged columns
there are.

This patch depends on the ParseNamespaceColumn infrastructure that
I added in commit 5815696bc.  The biggest bit of code change is
restructuring transformFromClauseItem's handling of JOINs so that
the ParseNamespaceColumn data is propagated upward correctly.

Other than that and the ruleutils fixes, everything pretty much
just works, though some processing is now inessential.  I grabbed
two pieces of low-hanging fruit in that line:

1. In find_expr_references, we don't need to recurse into join alias
Vars anymore.  There aren't any except for references to merged USING
columns, which are more properly handled when we scan the join's RTE.
This change actually fixes an edge-case issue: we will now record a
dependency on any type-coercion function present in a USING column's
joinaliasvar, even if that join column has no references in the query
text.  The odds of the missing dependency causing a problem seem quite
small: you'd have to posit somebody dropping an implicit cast between
two data types, without removing the types themselves, and then having
a stored rule containing a whole-row Var for a join whose USING merge
depends on that cast.  So I don't feel a great need to change this in
the back branches.  But in theory this way is more correct.

2. markRTEForSelectPriv and markTargetListOrigin don't need to recurse
into join alias Vars either, because the cases they care about don't
apply to alias Vars for USING columns that are semantically distinct
from the underlying columns.  This removes the only case in which
markVarForSelectPriv could be called with NULL for the RTE, so adjust
the comments to describe that hack as being strictly internal to
markRTEForSelectPriv.

			regards, tom lane

  10. Re: Clarifying/rationalizing Vars' varno/varattno/varnoold/varoattno

    Tom Lane <tgl@sss.pgh.pa.us> — 2020-02-04T20:24:21Z

    Robert Haas <robertmhaas@gmail.com> writes:
> On Fri, Dec 20, 2019 at 11:13 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> The alternatives that seem plausible at this point are
>> (1) Create some sort of wrapper node indicating "the contents of this
>> expression might be replaced by NULL".  This is basically what the
>> planner's PlaceHolderVars do, so maybe we'd just be talking about
>> introducing those at some earlier stage.
>> ...

> I'm not sure which is better, either, although I would like to note in
> passing that the name PlaceHolderVar seems to me to be confusing and
> terrible. It took me years to understand it, and I've never been
> totally sure that I actually do. Why is it not called
> MightBeNullWrapper or something?

Here's a data dump about my further thoughts in this area.  I've concluded
that the "wrapper" approach is the right way to proceed, and that rather
than having the planner introduce the wrappers as happens now, we should
indeed have the parser introduce the wrappers from the get-go.  There are
a few arguments for that:

* Arguably, this is a question of decorating the parse tree with
information about query semantics.  I've always held that parse analysis
is what should introduce knowledge of semantics; the planner ought not be
reverse-engineering that.

* AFAICS, we would need an additional pass over the query tree in order to
do this in the planner.  There is no existing recursive tree-modification
pass that happens at an appropriate time.

* We can use the same type of wrapper node to solve the problems with
grouping-set expressions that were discussed in
https://www.postgresql.org/message-id/flat/7dbdcf5c-b5a6-ef89-4958-da212fe10176%40iki.fi
although I'd leave that for a follow-on patch rather than try to fix
it immediately.  Here again, it'd be better to introduce the wrappers
at parse time --- check_ungrouped_columns() is already detecting the
presence of grouping-expression references, so we could make it inject
wrappers around them at relatively little extra cost.

Per Robert's complaint above, these wrappers need better documentation,
and they should be called something other than PlaceHolderVar, even though
they're basically that (and hopefully will replace those completely).
I'm tentatively thinking of calling them "NullableVar", but am open to
better ideas.  And here is a proposed addition to optimizer/README to
explain why they exist.  I'm not quite satisfied with the explanation yet
--- in particular, if we don't need them at runtime, why do we need them
at parse time?  Any thoughts about how to explain this more solidly are
welcome.

----------

To simplify handling of some issues with outer joins, we use NullableVars,
which are produced by the parser and used by the planner, but do not
appear in finished plans.  A NullableVar is a wrapper around another
expression, decorated with a set of outer-join relids, and notionally
having the semantics

	CASE WHEN any-of-these-outer-joins-produced-a-null-extended-row
	THEN NULL
	ELSE contained-expression
	END

It's only notional, because no such calculation is ever done explicitly.
In a finished plan, the NullableVar construct is replaced by a plain Var
referencing an output column of the topmost mentioned outer join, while
the "contained expression" is the corresponding input to the bottommost
join.  Any forcing to null happens in the course of calculating the
outer join results.  (Because we don't ever have to do the calculation
explicitly, it's not necessary to distinguish which side of an outer join
got null-extended, which'd otherwise be essential information for FULL
JOIN cases.)

A NullableVar wrapper is placed around a Var referencing a column of the
nullable side of an outer join when that reference appears syntactically
above (outside) the outer join, but not when the reference is below the
outer join, such as within its ON clause.  References to the non-nullable
side of an outer join are never wrapped.  NullableVars mentioning multiple
join nodes arise from cases with nested outer joins.

It might seem that the NullableVar construct is unnecessary (and indeed,
we got by without it for many years).  In a join row that's null-extended
for lack of a matching nullable-side row, the only reasonable value to
impute to a Var of that side is NULL, no matter where you look in the
parse tree.  However there are pressing reasons to use NullableVars
anyway:

* NullableVars simplify reasoning about where to evaluate qual clauses.
Consider
	SELECT * FROM t1 LEFT JOIN t2 ON (t1.x = t2.y) WHERE foo(t2.z)
(Assume foo() is not strict, so that we can't reduce the left join to
a plain join.)  A naive implementation might try to push the foo(t2.z)
call down to the scan of t2, but that is not correct because (a) what
foo() should actually see for a null-extended join row is NULL, and
(b) if foo() returns false, we should suppress the t1 row from the join
altogether, not emit it with a null-extended t2 row.  On the other hand,
it *would* be correct (and desirable) to push the call down if the query
were
	SELECT * FROM t1 LEFT JOIN t2 ON (t1.x = t2.y AND foo(t2.z))
If the upper WHERE clause is represented as foo(NullableVar(t2.z)), then
we can recognize that the NullableVar construct must be evaluated above
the join, since it references the join's relid.  Meanwhile, a t2.z
reference within the ON clause receives no such decoration, so in the
second case foo(t2.z) can be seen to be safe to push down to the scan
level.  Thus we can solve the qual-placement problem in a simple and
general fashion.

* NullableVars simplify reasoning around EquivalenceClasses.  Given say
	SELECT * FROM t1 LEFT JOIN t2 ON (t1.x = t2.y) WHERE t1.x = 42
we would like to put t1.x and t2.y and 42 into the same EquivalenceClass
and then derive "t2.y = 42" to use as a restriction clause for the scan
of t2.  However, it'd be wrong to conclude that t2.y will always have
the value 42, or that it's equal to t1.x in every joined row.  The use
of NullableVar wrappers sidesteps this problem: we can put t2.y in the
EquivalenceClass, and we can derive all the equalities we want about it,
but they will not lead to conclusions that NullableVar(t2.y) is equal to
anything.

* NullableVars are necessary to avoid wrong results when flattening
sub-selects.  If t2 in the above example is a sub-select or view in which
the y output column is a constant, and we want to pull up that sub-select,
we cannot simply substitute that constant for every use of t2.y in the
outer query: a Const node will not produce "NULL" when that's needed.
But it does work if the t2.y Vars are wrapped in NullableVars.  The
NullableVar shows that the contained value might be replaced by a NULL,
and it carries enough information so that we can generate a plan tree in
which that replacement does happen when necessary (by evaluating the
Const below the outer join and making upper references to it be Vars).
Moreover, when pulling up the constant into portions of the parse tree
that are below the outer join, the right things also happen: those
references can validly become plain Consts.

In essence, these examples show that it's useful to treat references to
a column of the nullable side of an outer join as being semantically
distinct depending on whether they are "above" or "below" the outer join,
even though no distinction exists once the calculation of a particular
join output row is complete.

----------

As you might gather from that, I'm thinking of changing the planner
so that (at least for outer joins) the relid set for a join includes
the RTE number of the join node itself.  I haven't decided yet if
that should happen across-the-board or just in the areas where we
use relid sets to decide which qual expressions get evaluated where.

Some other exciting things that will happen:

* RestrictInfo.is_pushed_down will go away; as sketched above, the
presence of the outer join's relid in the qual's required_relids
(due to NullableVars' outer join relid sets getting added into that
by pull_varnos) will tell us whether the qual must be treated as
a join or filter qual for the current join level.

* I think a lot of hackery in distribute_qual_to_rels can go away,
such as the below_outer_join flag, and maybe check_outerjoin_delay.
All of that is basically trying to reverse-engineer the qual
placement semantics that the wrappers will make explicit.

* As sketched above, equivalence classes will no longer need to
treat outer-join equalities with suspicion, and I think the
reconsider_outer_join_clauses stuff goes away too.

* There's probably other hackery that can be simplified; I've not
gone looking in detail yet.

I've not written any actual code, but am close to being ready to.
One thing I'm still struggling with is how to continue to support
outer join "identity 3":

        3.      (A leftjoin B on (Pab)) leftjoin C on (Pbc)
                = A leftjoin (B leftjoin C on (Pbc)) on (Pab)

        Identity 3 only holds if predicate Pbc must fail for all-null B
        rows (that is, Pbc is strict for at least one column of B).

Per this sketch, if the query is initially written the first way, Pbc's
references to B Vars would have NullableVars indicating a dependence on
the A/B join, seemingly preventing Pbc from being pushed into the RHS of
that join per the identity.  But if the query is initially written the
second way, there will be no NullableVar wrappers in either predicate.
Maybe it's sufficient to strip the NullableVar wrappers once we've
detected the applicability of the identity.  (We'll need code for that
anyway, since outer-join strength reduction will create cases where
NullableVar wrappers need to go away.)

			regards, tom lane

  11. Re: Clarifying/rationalizing Vars' varno/varattno/varnoold/varoattno

    Andrei Lepikhov <a.lepikhov@postgrespro.ru> — 2021-12-22T13:17:35Z

    On 5/2/2020 01:24, Tom Lane wrote:
> I've not written any actual code, but am close to being ready to.
This thread gives us hope to get started on solving some of the basic 
planner problems.
But there is no activity for a long time, as I see. Have You tried to 
implement this idea? Is it actual now?

-- 
regards,
Andrey Lepikhov
Postgres Professional

  12. Re: Clarifying/rationalizing Vars' varno/varattno/varnoold/varoattno

    Tom Lane <tgl@sss.pgh.pa.us> — 2021-12-22T15:42:44Z

    Andrey Lepikhov <a.lepikhov@postgrespro.ru> writes:
> On 5/2/2020 01:24, Tom Lane wrote:
>> I've not written any actual code, but am close to being ready to.

> This thread gives us hope to get started on solving some of the basic 
> planner problems.
> But there is no activity for a long time, as I see. Have You tried to 
> implement this idea? Is it actual now?

It's been on the back burner for awhile :-(.  I've not forgotten
about it though.

			regards, tom lane

  13. Re: Clarifying/rationalizing Vars' varno/varattno/varnoold/varoattno

    Andrei Lepikhov <a.lepikhov@postgrespro.ru> — 2021-12-22T17:01:22Z

    On 22/12/2021 20:42, Tom Lane wrote:
> Andrey Lepikhov <a.lepikhov@postgrespro.ru> writes:
>> On 5/2/2020 01:24, Tom Lane wrote:
>>> I've not written any actual code, but am close to being ready to.
> 
>> This thread gives us hope to get started on solving some of the basic
>> planner problems.
>> But there is no activity for a long time, as I see. Have You tried to
>> implement this idea? Is it actual now?
> 
> It's been on the back burner for awhile :-(.  I've not forgotten
> about it though.
I would try to develop this feature. Idea is clear for me, but 
definition of the NullableVars structure is not obvious. Maybe you can 
prepare a sketch of this struct or you already have some draft code?

-- 
regards,
Andrey Lepikhov
Postgres Professional