Re: join removal

On Thu, Jul 16, 2009 at 9:02 PM, Greg Stark<stark@mit.edu> wrote:

I started looking at this patch and it looks pretty good as far as it
goes. But I think we can do a lot more. It seems to me the cases where
foreign key relationships exist are likely to be really big use cases.

I agree. But that seems a lot harder, and this is useful all by
itself because it can eliminate LEFT joins. Foreign key deductions
will be necessary to eliminate inner joins and self-joins. I've been
advised that when writing patches for PostgreSQL it's best to start
with something small. :-)

I have one big worry though. Currently you're detecting the unique
property using the planner's path mechanism. I suppose that works, but
it's only an accident of the planner design that the path for the
unique index will always be there if it's the join condition. My
instinct is that this code should be going back to the raw index info
to prove this property. The only practical effect I can think of is
that the plan will have to be marked as being dependent on that index
and that will be hard to do if you haven't identified a specific index
you're basing it on.

I had trouble figuring out where to hook in the logic. In an ideal
world, it would be nice to detect that the join is removable earlier,
but it's hard to do that, because it's not until we know the join
order that we can test whether any attributes from the inner rel are
used above the level of the join. But as it is the fact that the join
can be removed will have to be rediscovered over and over again as
planning progresses.

As for going back to "the raw index info", that was kind of my
instinct as well but I couldn't make it work. It seems that the
IndexOptInfo structure only knows the column numbers of the index's
keys, whereas the code that considers possible join strategies has
only equivalence classes to work with, and I don't see how to match
the two up. If we can figure out a way to do that it would probably
be cleaner.

I would like to see a list of cases we plan to tackle preferably with
example queries, as a kind of checklist so we can knock them down one
by one.  Right now it's unclear just how much of the problem space is
being solved.

I don't know how many cases I personally plan to handle because I
don't know how much time I'm going to have to work on this or whether
I have the needed brainpower. But I can enumerate the cases that I
know about where this is theoretically possible.

- LEFT joins can be eliminated if the nullable side of the join can be
proved unique over the join columns. The simplest and most common
case is the one where there is a unique index on any (not necessarily
proper) subset of the join columns, but it can also happen in any
other case where we can prove that the inner rel is unique over (a
subset of) the relevant columns, such as when the inner rel groups by
those columns. There is an existing function query_is_distinct_for()
that does something along these lines, but it operates on yet another
different type of data structure (a Query, rather than a list of
equivalence classes or alternatively a list of varattnos) and doesn't
handle the unique-index case, which is probably the most important one
for this optimization.

- INNER joins are more complex because what happens on the inner side
of the join can potentially wipe out rows from the result. With a
LEFT join, it's sufficient to prove that the inner rel is at least
unique enough, but for an INNER join, we have to prove that it's
exactly UNIQUE enough. I think we can only provide this when the
inner rel is a base relation with a unique index over EXACTLY (not a
subset of) the relevant columns AND there is a foreign key
relationship from the outer rel to the inner rel over the join
columns.

- Self-joins (whether they are inner, left, semi, or full) can be
collapsed into a scan of the underlying base relation if the join
columns on both sides include all the columns of the same unique
index. All the quals from both sides have to be applied.

Incidentally, guess what other database just got this feature committed...

http://askmonty.org/worklog/Client-BackLog/?tid=17

Hmm, well, it would be nice to have parity. This is a hugely
important feature for the kinds of queries I do all day.

...Robert

Robert Haas <robertmhaas@gmail.com> writes:

On Thu, Jul 16, 2009 at 9:02 PM, Greg Stark<stark@mit.edu> wrote:

I have one big worry though. Currently you're detecting the unique
property using the planner's path mechanism. I suppose that works, but
it's only an accident of the planner design that the path for the
unique index will always be there if it's the join condition. My
instinct is that this code should be going back to the raw index info
to prove this property.

I had trouble figuring out where to hook in the logic. In an ideal
world, it would be nice to detect that the join is removable earlier,
but it's hard to do that, because it's not until we know the join
order that we can test whether any attributes from the inner rel are
used above the level of the join.

Yeah. Ideally this sort of thing would happen in prepjointree.c, but
we don't have nearly enough information at that stage. I think the
approach of treating join removal as a kind of join implementation is
not unreasonable. I think though that we might have to add an actual
"dummy join" path type. The crocks you put into add_path are, well,
crocks.

But as it is the fact that the join
can be removed will have to be rediscovered over and over again as
planning progresses.

Not really. We only consider a given join once.

As for going back to "the raw index info", that was kind of my
instinct as well but I couldn't make it work.

You need to work harder --- the way it's being done here is way too
simplistic. It's failing to take any account of whether the index's
opclass has anything to do with the semantics of the join operators.
Even aside from that, I agree with Greg that depending on
the IndexPath to be there is a fatal mistake. Do we want
enable_indexscan = off to disable join removal? Even if we thought
that was okay, it seems entirely likely that the IndexPath could be
discarded on cost grounds before we get to the stage of considering
joins. And it certainly won't scale up to considering removal of
joins above the base level.

I think we want something along the lines of relation_is_distinct_for
with a list of columns and a list of comparison operators, where the
first-cut implementation will be to look for matching indexes.
This will be different from query_is_distinct_for, but it's dealing
with the same sorts of considerations about whether the operator
semantics are the right things.

regards, tom lane

On Sun, Jul 19, 2009 at 10:56 PM, Tom Lane<tgl@sss.pgh.pa.us> wrote:

Robert Haas <robertmhaas@gmail.com> writes:

On Thu, Jul 16, 2009 at 9:02 PM, Greg Stark<stark@mit.edu> wrote:

I have one big worry though. Currently you're detecting the unique
property using the planner's path mechanism. I suppose that works, but
it's only an accident of the planner design that the path for the
unique index will always be there if it's the join condition. My
instinct is that this code should be going back to the raw index info
to prove this property.

I had trouble figuring out where to hook in the logic.  In an ideal
world, it would be nice to detect that the join is removable earlier,
but it's hard to do that, because it's not until we know the join
order that we can test whether any attributes from the inner rel are
used above the level of the join.

Yeah.  Ideally this sort of thing would happen in prepjointree.c, but
we don't have nearly enough information at that stage.  I think the
approach of treating join removal as a kind of join implementation is
not unreasonable.  I think though that we might have to add an actual
"dummy join" path type.  The crocks you put into add_path are, well,
crocks.

Well, they're pretty simple crocks, but creating a dummy join type
might not be too bad. I'm thinking that it might make sense to have
the dummy join type exist only in the Path world, and to have the
create_plan() machinery strip it out when the actual Plan is built?

But as it is the fact that the join
can be removed will have to be rediscovered over and over again as
planning progresses.

Not really.  We only consider a given join once.

Well, sorta. A lot of the queries where this will apply are probably
of the form:

A LEFT JOIN B LEFT JOIN C LEFT JOIN D LEFT JOIN E LEFT JOIN F LEFT JOIN G

...where many or all of the left joins are commutable. If the join to
B is removable, then you'll discover that it's removable when you try
to join {A} and {B}, but also when you try to join {A C} to {B}, when
you try to join {A D} to {B}, when you try to join {A C D} to {B},
etc.

In fact, I think that once you've found even one path where a join is
removable, you know it's removable no matter what, so you'd ideally
like to stop caring about the best path for {A B C D E F G} and just
look for the best path for {A C D E F G}. I'm not sure how to make
that work, though.

As for going back to "the raw index info", that was kind of my
instinct as well but I couldn't make it work.

You need to work harder --- the way it's being done here is way too
simplistic.  It's failing to take any account of whether the index's
opclass has anything to do with the semantics of the join operators.
Even aside from that, I agree with Greg that depending on
the IndexPath to be there is a fatal mistake.  Do we want
enable_indexscan = off to disable join removal?  Even if we thought
that was okay, it seems entirely likely that the IndexPath could be
discarded on cost grounds before we get to the stage of considering
joins.

Good point.

And it certainly won't scale up to considering removal of
joins above the base level.

I think we want something along the lines of relation_is_distinct_for
with a list of columns and a list of comparison operators, where the
first-cut implementation will be to look for matching indexes.
This will be different from query_is_distinct_for, but it's dealing
with the same sorts of considerations about whether the operator
semantics are the right things.

That seems reasonable; my problem is (and I'm sorry if I'm being dense
here) where am I going to get the list of columns and the list of
comparison operators? add_paths_to_joinrel() just gets a list of
RestrictInfos for the join clauses, and I don't know what to do with
that.

Thanks,

...Robert

Robert Haas <robertmhaas@gmail.com> writes:

On Sun, Jul 19, 2009 at 10:56 PM, Tom Lane<tgl@sss.pgh.pa.us> wrote:

I think we want something along the lines of relation_is_distinct_for
with a list of columns and a list of comparison operators, where the
first-cut implementation will be to look for matching indexes.

That seems reasonable; my problem is (and I'm sorry if I'm being dense
here) where am I going to get the list of columns and the list of
comparison operators? add_paths_to_joinrel() just gets a list of
RestrictInfos for the join clauses, and I don't know what to do with
that.

You'd need to pull apart the clauses inside the RestrictInfos, ie look
to see if they have the form "outer.col op inner.col" and then grab the
op and the inner.col. Some of this is already done for you: you can
look at the RestrictInfo to see if it's an operator clause and which
side of the clause belongs to the relation you're interested in.
This isn't a whole lot different from what's done to extract hash or
merge join clauses from the list of join RestrictInfos.

regards, tom lane

On Jul 17, 2009, at 04:27 , Robert Haas wrote:

- INNER joins are more complex because what happens on the inner side
of the join can potentially wipe out rows from the result. With a
LEFT join, it's sufficient to prove that the inner rel is at least
unique enough, but for an INNER join, we have to prove that it's
exactly UNIQUE enough. I think we can only provide this when the
inner rel is a base relation with a unique index over EXACTLY (not a
subset of) the relevant columns AND there is a foreign key
relationship from the outer rel to the inner rel over the join
columns.

Reasoning on foreign key relationships opens up for other optimization
opportunities as well, so being able to prove that a join cannot alter
the number of rows would be nice.

For example, Limit-operators can possibly be pushed below a join that
does not alter the result set, to reduce the amount of work done by
the join.

Also, we can prove that uniqueness properties are kept.

To put both examples in context, consider tables A and B defined as
follows:

Table "public.a"
Column | Type | Modifiers
--------+---------+-----------
id | integer | not null
Indexes:
"a_pkey" PRIMARY KEY, btree (id)
Referenced by:
TABLE "b" CONSTRAINT "b_id_fkey" FOREIGN KEY (id) REFERENCES a(id)

Table "public.b"
Column | Type | Modifiers
--------+---------+-----------
id | integer | not null
Indexes:
"b_pkey" PRIMARY KEY, btree (id)
Foreign-key constraints:
"b_id_fkey" FOREIGN KEY (id) REFERENCES a(id)

The query plan for SELECT DISTINCT a.id FROM b JOIN a USING (id) ORDER
BY a.id ASC LIMIT 10 is this:

QUERY PLAN
-------------------------------------------------------------------------------------
Limit (cost=0.00..7.20 rows=10 width=4)
-> Unique (cost=0.00..36.72 rows=51 width=4)
-> Merge Join (cost=0.00..36.59 rows=51 width=4)
Merge Cond: (b.id = a.id)
-> Index Scan using b_pkey on b (cost=0.00..29.02
rows=51 width=4)
-> Index Scan using a_pkey on a (cost=0.00..13.77
rows=101 width=4)

In this case we know that joining A does not alter the result set,
because of the FK from B.id to A.id. Also, because B.id is also
unique, the uniqueness of A.id is retained.

Thus, the plan can be optimized to something like

QUERY PLAN
---------------------------------------------
Merge Join (...)
Merge Cond: (b.id = a.id)
-> Limit (...)
-> Index Scan using a_pkey on a (...)
-> Index Scan using b_pkey on b (...)

Perhaps these (and other) future opportunities make infrastructure
changes for proper join removal support more worthwhile.

--
Alex Brasetvik

On Fri, Jul 24, 2009 at 7:53 AM, Alex Brasetvik<alex@brasetvik.com> wrote:

On Jul 17, 2009, at 04:27 , Robert Haas wrote:

- INNER joins are more complex because what happens on the inner side
of the join can potentially wipe out rows from the result.  With a
LEFT join, it's sufficient to prove that the inner rel is at least
unique enough, but for an INNER join, we have to prove that it's
exactly UNIQUE enough.  I think we can only provide this when the
inner rel is a base relation with a unique index over EXACTLY (not a
subset of) the relevant columns AND there is a foreign key
relationship from the outer rel to the inner rel over the join
columns.

Reasoning on foreign key relationships opens up for other optimization
opportunities as well, so being able to prove that a join cannot alter the
number of rows would be nice.

For example, Limit-operators can possibly be pushed below a join that does
not alter the result set, to reduce the amount of work done by the join.

Interesting, I hadn't thought about that, but it's an excellent point.
Another case that comes up is:

A LEFT JOIN (B INNER JOIN C ON Pbc) ON Pab

In general, this doesn't commute, because you need to emit a
NULL-extended copy of A whenever Pab has no match in B INNER JOIN C ON
Pbc. But if you know that Pbc will always be satisfied for exactly
one row in B, then you can decide to implement the join between B and
C as a left join rather than an inner join, so you get this:

A LEFT JOIN (B LEFT JOIN C ON Pbc) ON Pab

Now it commutes:

(A LEFT JOIN B ON Pab) LEFT JOIN C ON Pbc

I'm going to try to get the basic join removal code (for left joins,
which don't need foreign-key deduction) done for CommitFest 2009-09.
The next step is the foreign key deduction so we can remove inner
joins, but I'm not sure I'll have that for 8.5 unless someone wants to
either pitch in or cough up some money. Reordering joins around
limits is, I suspect, very difficult indeed, so should probably be a
project for phase 3.

...Robert

On Sun, Jul 19, 2009 at 10:56 PM, Tom Lane<tgl@sss.pgh.pa.us> wrote:

I think we want something along the lines of relation_is_distinct_for
with a list of columns and a list of comparison operators, where the
first-cut implementation will be to look for matching indexes.
This will be different from query_is_distinct_for, but it's dealing
with the same sorts of considerations about whether the operator
semantics are the right things.

I took at a first crack at coding up an implementation of
relation_is_distinct_for() tonight. Pseudocode:

for each indexoptinfo
{
if (not unique or not predOK or contains expressions)
skip it;
for c = 0 .. ind->ncolumns
{
opid = distinct_col_search(ind->indexkeys[c], colnos, opids);
if (!OidIsValid(opid) || !equality_ops_are_compatible(opid, XXXXXXXX))
break;
}
if (found them all)
return true;
}
return false;

distinct_col_search() is going to return the relevant equality
operator from the argument list, which is ultimately going to come
from the RestrictInfo for the join clause. So I need to see whether
that's compatible with the index, but equality_ops_are_compatible()
wants two equality operators, and what I have is one equality operator
and one operator class.

Maybe it's sufficient to just check whether op_in_opfamily(opid,
ind->opfamily[c]), and skip equality_ops_are_compatible()?

I am having a hard time wrapping my brain around what it means to have
multiple, incompatible notions of equality... any help appreciated!

...Robert

Robert Haas <robertmhaas@gmail.com> writes:

distinct_col_search() is going to return the relevant equality
operator from the argument list, which is ultimately going to come
from the RestrictInfo for the join clause. So I need to see whether
that's compatible with the index, but equality_ops_are_compatible()
wants two equality operators, and what I have is one equality operator
and one operator class.

For that you just check if the operator is a member of the class.
(You might need to verify that it's an equality operator in the class
too; not clear if the context is enough to be sure that it's not '<'
for example.)

Note that you really want to think about opfamilies not opclasses.
So if you have an index opclass you really get its containing family
and look for membership in that.

I am having a hard time wrapping my brain around what it means to have
multiple, incompatible notions of equality... any help appreciated!

Well, for instance a complex-number datatype could have one btree
opclass that sorts on absolute value (distance from 0,0) and another
opclass that sorts on real part. In the first case "equal" values would
be members of the same circle around the origin, in the second case they
are members of the same vertical line.

regards, tom lane

On Sun, Aug 9, 2009 at 5:19 PM, Tom Lane<tgl@sss.pgh.pa.us> wrote:

I am having a hard time wrapping my brain around what it means to have
multiple, incompatible notions of equality... any help appreciated!

Well, for instance a complex-number datatype could have one btree
opclass that sorts on absolute value (distance from 0,0) and another
opclass that sorts on real part.  In the first case "equal" values would
be members of the same circle around the origin, in the second case they
are members of the same vertical line.

The example that came to mind for me was a case-insensitive btree
class for text.

--
greg
http://mit.edu/~gsstark/resume.pdf

I took at a first crack at coding up an implementation of
relation_is_distinct_for() tonight.

I am not sure if this will help or not, but on the 8.4 code base we
implemented two functions:

- getCandidateKeys() - would recursively traverse a tree from a given
node to the leaf nodes and determine the candidate keys for the
intermediate relation produced by that node

- getJoinCard() - determined the join cardinality of a hash join node
(1:1, 1:N, etc.) based on the candidate keys of the two input relations

It worked pretty well for our tests with equi-joins, but I am sure it is
missing many cases. I have attached the code which we used
(cardinalityFuncs.c). Some of the helper functions may also be useful
(convertUniqueIndexesToCandidateKeys, getJoinAttrs).

--
Ramon Lawrence

On Sun, Aug 9, 2009 at 12:19 PM, Tom Lane<tgl@sss.pgh.pa.us> wrote:

Robert Haas <robertmhaas@gmail.com> writes:

distinct_col_search() is going to return the relevant equality
operator from the argument list, which is ultimately going to come
from the RestrictInfo for the join clause.  So I need to see whether
that's compatible with the index, but equality_ops_are_compatible()
wants two equality operators, and what I have is one equality operator
and one operator class.

For that you just check if the operator is a member of the class.
(You might need to verify that it's an equality operator in the class
too; not clear if the context is enough to be sure that it's not '<'
for example.)

It seems that the needed checks are very similar to the ones that we
already implement when setting restrictinfo->mergeopfamilies. That is
filled in by get_mergejoin_opfamilies(), which checks for btree
opfamilies where the strategy number is BTEqualStrategyNumber. This
might cease to be the correct check in the (not-too-distant?) future
if we end up implementing other kinds of unique indices, but right now
btrees are all there is.

One possibility would be to have relation_is_distinct_for() call
get_mergejoin_opfamilies() for each operator; then for each index we
can check whether the opfamily of the relevant index column is in the
returned list. This seems a bit wasteful, though, since I believe
that relation_is_distinct_for() would be called from joinpath.c, which
has access to restrictinfo->mergeopfamilies already.

I'm wondering whether it would make more sense to modify the proposed
API for relation_is_distinct_for() in some way so that we don't lose
this information. It seems to me that the overall process here is
something like this (recalling that I'm focusing only on removing LEFT
joins at this point):

1. Given a joinrel, innerrel, and outerrel, find the list of
RestrictInfos for which (a) restrictinfo->mergeopfamilies != NIL, (b)
restrictinfo->outer_is_left is well-defined (as per logic in
select_mergejoin_clauses), and (c) the outer side is a Var. If this
list is NIL, then give up; join removal is not possible.

2. Check whether any attributes from the outer side are used above the
join; if so, then give up; join removal is not possible.

3. Extract the column numbers from the Vars found in step 1(C) and the
mergeopfamilies found in step 1(A).

4. Look a unique, non-expression index (which must also have
index->indpred == NIL or index->predOK) for which every column number
appears in the list of column numbers computed in step 3, with one of
the corresponding opfamilies also found in step (2). If one is found,
then the join is removable.

Thoughts?

...Robert

On Sun, Aug 16, 2009 at 5:31 PM, Robert Haas<robertmhaas@gmail.com> wrote:

It seems that the needed checks are very similar to the ones that we
already implement when setting restrictinfo->mergeopfamilies.  That is
filled in by get_mergejoin_opfamilies(), which checks for btree
opfamilies where the strategy number is BTEqualStrategyNumber.  This
might cease to be the correct check in the (not-too-distant?) future
if we end up implementing other kinds of unique indices, but right now
btrees are all there is.

One possibility would be to have relation_is_distinct_for() call
get_mergejoin_opfamilies() for each operator; then for each index we
can check whether the opfamily of the relevant index column is in the
returned list.  This seems a bit wasteful, though, since I believe
that relation_is_distinct_for() would be called from joinpath.c, which
has access to restrictinfo->mergeopfamilies already.

I'm wondering whether it would make more sense to modify the proposed
API for relation_is_distinct_for() in some way so that we don't lose
this information.

Here is an attempt at the latter approach. This doesn't actually
remove the join yet; it just checks whether the join can be removed.
I haven't tested it extensively yet, but am hoping for some feedback
on the basic approach.

...Robert

On Sun, Jul 19, 2009 at 10:56 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Yeah.  Ideally this sort of thing would happen in prepjointree.c, but
we don't have nearly enough information at that stage.

Tom,

You've mentioned this point a couple of times - what is ideal about
prepjointree? Reading through the "optimizer functions" section of
src/backend/optimizer/README, it seems like the earliest point at
which we could do this would be just before the call to
make_one_rel(). I think that would eliminate some redundant
computation. Right now, if we have A LJ B LJ C we'll try joining A to
C and discover that it's removable; later we'll try joining {A B} to C
and again discover that C is removable. But maybe it could be
attacked from the other direction: look at C and try to figure out
whether there's a some baserel or joinrel to which we can join it
removably. If we find one, we don't need to bother generating seq
scan or index paths for C, reloptinfos for joinrels that include C,
etc.

The problem with moving it back any further seems to be that we have
to know which clauses are mergejoinable before we can do the necessary
computations; I think flattening of the query tree has to already be
done too.

Obviously this is all 9.1 material but PG east has me thinking about
this topic again...

...Robert

Robert Haas <robertmhaas@gmail.com> writes:

On Sun, Jul 19, 2009 at 10:56 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Yeah. �Ideally this sort of thing would happen in prepjointree.c, but
we don't have nearly enough information at that stage.

You've mentioned this point a couple of times - what is ideal about
prepjointree?

Well, it's the place where we like to rearrange the join tree, and
dropping a join altogether certainly counts as that. We can't do it
there, at the moment anyway, for lack of supporting data --- but if
it were possible to do it at that time I think it'd be the cleanest
approach.

Reading through the "optimizer functions" section of
src/backend/optimizer/README, it seems like the earliest point at
which we could do this would be just before the call to
make_one_rel(). I think that would eliminate some redundant
computation.

Maybe. It would also add a new pass over the join tree that, in
99% of cases, would make no useful contribution whatever. It's
possible that this would still be cheaper than a lot of failed calls
to join_is_removable, but I'm unconvinced --- we were able to make
the failure path through that pretty durn cheap for most simple cases.
The approach you're sketching still involves a combinatorial search
so I doubt it's going to be cheap.

I should maybe pause here a moment to say that my approach to
considering the cost of new planner optimizations is to focus on how
much time the added code will eat on queries where it fails to make any
useful contribution. If the optimization wins, then presumably you will
make back at execution time whatever it might have cost you to plan
(if this is debatable, you probably shouldn't be bothering with the idea
at all). So the pain will come from adding planning time on queries
where there isn't any runtime payoff; especially for something like join
removal, which only applies to a small minority of queries anyway.
Therefore I'm suspicious of adding new passes over the query structure
if they are only going to be used for low-probability wins.

The problem with moving it back any further seems to be that we have
to know which clauses are mergejoinable before we can do the necessary
computations; I think flattening of the query tree has to already be
done too.

Yeah. I had been thinking that we could build the RelOptInfo and
IndexOptInfo structs earlier, but really all of the
clause-classification work done by deconstruct_jointree is important
as well for this function's purposes, so it's not that easy to push
back to prepjointree :-(. I suspect that any such attempt would end
up requiring a massive rethinking of the order of operations in the
planner. Maybe we should do that sometime but I'm not eager for it.

regards, tom lane

On Fri, Mar 26, 2010 at 6:10 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Reading through the "optimizer functions" section of
src/backend/optimizer/README, it seems like the earliest point at
which we could do this would be just before the call to
make_one_rel().  I think that would eliminate some redundant
computation.

Maybe.  It would also add a new pass over the join tree that, in
99% of cases, would make no useful contribution whatever.  It's
possible that this would still be cheaper than a lot of failed calls
to join_is_removable, but I'm unconvinced --- we were able to make
the failure path through that pretty durn cheap for most simple cases.
The approach you're sketching still involves a combinatorial search
so I doubt it's going to be cheap.

I'm not totally sure about this but I think it's possible to do this
without a combinatorial search. Suppose we just iterate over the list
of
SpecialJoinInfo structures and look for those where jointype is LEFT,
delay_upper_joins is false, and min_righthand is a singleton; and then
consider the removability of a join between min_lefthand and
min_righthand. I might be missing a case, but I think whatever answer
we get from that calculation is the answer, period. Adding more
relations to the LHS won't change anything.

Yeah.  I had been thinking that we could build the RelOptInfo and
IndexOptInfo structs earlier, but really all of the
clause-classification work done by deconstruct_jointree is important
as well for this function's purposes, so it's not that easy to push
back to prepjointree :-(.  I suspect that any such attempt would end
up requiring a massive rethinking of the order of operations in the
planner.  Maybe we should do that sometime but I'm not eager for it.

Agree. If we ever do that, one of the things to think about is
minimizing memory consumption...

...Robert

Robert Haas <robertmhaas@gmail.com> writes:

I'm not totally sure about this but I think it's possible to do this
without a combinatorial search. Suppose we just iterate over the list
of
SpecialJoinInfo structures and look for those where jointype is LEFT,
delay_upper_joins is false, and min_righthand is a singleton; and then
consider the removability of a join between min_lefthand and
min_righthand. I might be missing a case, but I think whatever answer
we get from that calculation is the answer, period. Adding more
relations to the LHS won't change anything.

Hmm ... that last isn't obvious to me. The current computation in
join_is_removable is clearly capable of making different decisions at
different join levels, depending on whether any outputs of the RHS are
seen to be required above the current join. It might be that in
practice it has to succeed with the min LHS if it's going to succeed
anywhere, but I'm not convinced.

regards, tom lane

On Sat, Mar 27, 2010 at 10:50 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Robert Haas <robertmhaas@gmail.com> writes:

I'm not totally sure about this but I think it's possible to do this
without a combinatorial search.  Suppose we just iterate over the list
of
SpecialJoinInfo structures and look for those where jointype is LEFT,
delay_upper_joins is false, and min_righthand is a singleton; and then
consider the removability of a join between min_lefthand and
min_righthand.  I might be missing a case, but I think whatever answer
we get from that calculation is the answer, period.  Adding more
relations to the LHS won't change anything.

Hmm ... that last isn't obvious to me.  The current computation in
join_is_removable is clearly capable of making different decisions at
different join levels, depending on whether any outputs of the RHS are
seen to be required above the current join.

Right.

It might be that in
practice it has to succeed with the min LHS if it's going to succeed
anywhere, but I'm not convinced.

It's a bit difficult to wrap one's brain around all the cases, but I
think that the statement in question is in fact true. Adding more
rels to the LHS could help to pass the "rels not used above the level
of the join" test by putting more rels under the join. But that begs
the question - how exactly are those rels being used? The only answer
I can see is that they're involved in some join clause between one of
the added tables and the RHS - in which case they should be part of
the min LHS in the first place.

There are a couple of problems with making this approach actually work
that I haven't figured out yet. One is that it's not exactly clear
how you ago about removing the join at this part. In particular, if
you remove one join, it might make some other join that wasn't
previously removable now able to be removed, and it's not exactly
clear to me how to make this method cope with that. But I think it's
worth thinking about because anything based on an O(n) pass over the
SpecialJoinInfo structures should be far cheaper than participating in
the combinatorial explosion that will ensue once we actually begin
testing through all the join orders.

...Robert

Robert Haas <robertmhaas@gmail.com> writes:

On Sat, Mar 27, 2010 at 10:50 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

It might be that in
practice it has to succeed with the min LHS if it's going to succeed
anywhere, but I'm not convinced.

It's a bit difficult to wrap one's brain around all the cases, but I
think that the statement in question is in fact true. Adding more
rels to the LHS could help to pass the "rels not used above the level
of the join" test by putting more rels under the join. But that begs
the question - how exactly are those rels being used? The only answer
I can see is that they're involved in some join clause between one of
the added tables and the RHS - in which case they should be part of
the min LHS in the first place.

After further reflection I think you're right, especially now that we
have that restriction against pushed-down join clauses in there.
Removal could only succeed when the rel's Vars are used just in the
left join's own join clauses, which means that only the min LHS can be
needed in order to compute those clauses.

There are a couple of problems with making this approach actually work
that I haven't figured out yet. One is that it's not exactly clear
how you ago about removing the join at this part.

I think you just remove the RHS rel from the joinlist.

In particular, if
you remove one join, it might make some other join that wasn't
previously removable now able to be removed, and it's not exactly
clear to me how to make this method cope with that.

I'm not seeing how that would occur or would matter, but the worst case
answer is to restart the scan of the SpecialJoinInfos from scratch any
time you succeed in doing a join removal.

But I think it's
worth thinking about because anything based on an O(n) pass over the
SpecialJoinInfo structures should be far cheaper than participating in
the combinatorial explosion that will ensue once we actually begin
testing through all the join orders.

Agreed. Just deleting one rel from the join search space is an enormous
win.

regards, tom lane

On Sat, Mar 27, 2010 at 4:11 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

In particular, if
you remove one join, it might make some other join that wasn't
previously removable now able to be removed, and it's not exactly
clear to me how to make this method cope with that.

I'm not seeing how that would occur or would matter, but the worst case
answer is to restart the scan of the SpecialJoinInfos from scratch any
time you succeed in doing a join removal.

Well, say you have something like

SELECT 1 FROM A LEFT JOIN (B LEFT JOIN C ON Pbc) ON Pab

I think that the SpecialJoinInfo structure for the join between B and
C will match the criteria I articulated upthread, but the one for the
join between A and {B C} will not. If C had not been in the query
from the begining then we'd have had:

SELECT 1 FROM A LEFT JOIN B ON Pab

...under which circumstances the SpecialJoinInfo would match the
aforementioned criteria.

But I think it's
worth thinking about because anything based on an O(n) pass over the
SpecialJoinInfo structures should be far cheaper than participating in
the combinatorial explosion that will ensue once we actually begin
testing through all the join orders.

Agreed.  Just deleting one rel from the join search space is an enormous
win.

Yeah.

...Robert