Thread

Re: join removal

Greg Stark <stark@mit.edu> — 2009-07-17T01:02:06Z

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 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 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.

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

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

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

Re: join removal

Robert Haas <robertmhaas@gmail.com> — 2009-07-17T02:27:08Z

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

Re: join removal

Tom Lane <tgl@sss.pgh.pa.us> — 2009-07-20T02:56:52Z

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

Re: join removal

Robert Haas <robertmhaas@gmail.com> — 2009-07-20T03:58:34Z

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

Re: join removal

Tom Lane <tgl@sss.pgh.pa.us> — 2009-07-20T04:22:43Z

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

Re: join removal

Alex Brasetvik <alex@brasetvik.com> — 2009-07-24T11:53:14Z

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

Re: join removal

Robert Haas <robertmhaas@gmail.com> — 2009-07-24T13:37:14Z

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

Re: join removal

Robert Haas <robertmhaas@gmail.com> — 2009-08-09T03:33:57Z

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

Re: join removal

Tom Lane <tgl@sss.pgh.pa.us> — 2009-08-09T16:19:06Z

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

Re: join removal

Greg Stark <stark@mit.edu> — 2009-08-09T16:46:32Z

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

Re: join removal

Lawrence, Ramon <ramon.lawrence@ubc.ca> — 2009-08-10T15:30:44Z

> 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

Re: join removal

Robert Haas <robertmhaas@gmail.com> — 2009-08-16T21:31:23Z

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

Re: join removal

Robert Haas <robertmhaas@gmail.com> — 2009-08-28T03:23:48Z

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

Re: join removal

Robert Haas <robertmhaas@gmail.com> — 2010-03-26T21:36:03Z

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

Re: join removal

Tom Lane <tgl@sss.pgh.pa.us> — 2010-03-26T22:10:38Z

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

Re: join removal

Robert Haas <robertmhaas@gmail.com> — 2010-03-27T11:13:21Z

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

Re: join removal

Tom Lane <tgl@sss.pgh.pa.us> — 2010-03-27T14:50:21Z

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

Re: join removal

Robert Haas <robertmhaas@gmail.com> — 2010-03-27T19:06:53Z

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

Re: join removal

Tom Lane <tgl@sss.pgh.pa.us> — 2010-03-27T20:11:37Z

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

Re: join removal

Robert Haas <robertmhaas@gmail.com> — 2010-03-27T20:19:48Z

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

Re: join removal

Tom Lane <tgl@sss.pgh.pa.us> — 2010-03-28T04:19:39Z

Robert Haas <robertmhaas@gmail.com> writes:
> On Sat, Mar 27, 2010 at 4:11 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> 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.

I experimented with this and found that you're correct: the tests on the
different SpecialJoinInfos do interact, which I hadn't believed
initially.  The reason for this is that when we find out we can remove a
particular rel, we have to remove the bits for it in other relations'
attr_needed bitmaps.  In the above example, we first discover we can
remove C.  Whatever B vars were used in Pbc will have an attr_needed
set of {B,C}, and that C bit will prevent us from deciding that B can
be removed when we are examining the upper SpecialJoinInfo (which will
not consider C to be part of either min_lefthand or min_righthand).
So we have to remove the C bits when we remove C.

Attached is an extremely quick-and-dirty, inadequately commented draft
patch that does it along the lines you are suggesting.  This was just to
see if I could get it to work at all; it's not meant for application in
anything like its current state.  However, I feel a very strong
temptation to finish it up and apply it before we enter beta.  As you
noted, this way is a lot cheaper than the original coding, whether one
focuses on the cost of failing cases or the cost when the optimization
is successful.  And if we hold it off till 9.1, then any bug fixes that
have to be made in the area later will need to be made against two
significantly different implementations, which will be a real PITA.

Things that would need to be cleaned up:

* I left join_is_removable where it was, mainly so that it was easy to
compare how much it changed for this usage (not a lot).  I'm not sure
that joinpath.c is an appropriate place for it anymore, though I can't
see any obviously better place either.  Any thoughts on that?

* The removed relation has to be taken out of the set of baserels
somehow, else for example the Assert in make_one_rel will fail.
The current hack is to change its reloptkind to RELOPT_OTHER_MEMBER_REL,
which I think is a bit unclean.  We could try deleting it from the
simple_rel_array altogether, but I'm worried that that could result in
dangling-pointer failures, since we're probably not going to go to the
trouble of removing every single reference to the rel from the planner
data structures.  A possible compromise is to invent another reloptkind
value that is only used for "dead" relations.

* It would be good to not count the removed relation in
root->total_table_pages.  If we made either of the changes suggested
above then we could move the calculation of total_table_pages down to
after remove_useless_joins and ignore the removed relation(s)
appropriately.  Otherwise I'm tempted to just subtract off the relation
size from total_table_pages on-the-fly when we remove it.

* I'm not sure yet about the adjustment of PlaceHolder bitmaps --- we
might need to break fix_placeholder_eval_levels into two steps to get
it right.

* Still need to reverse out the now-dead code from the original patch,
in particular the NoOpPath support.

Thoughts?

			regards, tom lane

Re: join removal

Tom Lane <tgl@sss.pgh.pa.us> — 2010-03-28T05:15:32Z

I wrote:
> [ crude patch ]

Oh, btw, if you try to run the regression test additions in that patch
against CVS HEAD, you'll find out that HEAD actually fails to optimize
the two-levels-of-removable-joins case.  Seems like another reason to
press ahead with making the change.

			regards, tom lane

Re: join removal

Robert Haas <robertmhaas@gmail.com> — 2010-03-28T11:16:09Z

On Sun, Mar 28, 2010 at 12:19 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Robert Haas <robertmhaas@gmail.com> writes:
>> On Sat, Mar 27, 2010 at 4:11 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>>> 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.
>
> I experimented with this and found that you're correct: the tests on the
> different SpecialJoinInfos do interact, which I hadn't believed
> initially.  The reason for this is that when we find out we can remove a
> particular rel, we have to remove the bits for it in other relations'
> attr_needed bitmaps.  In the above example, we first discover we can
> remove C.  Whatever B vars were used in Pbc will have an attr_needed
> set of {B,C}, and that C bit will prevent us from deciding that B can
> be removed when we are examining the upper SpecialJoinInfo (which will
> not consider C to be part of either min_lefthand or min_righthand).
> So we have to remove the C bits when we remove C.
>
> Attached is an extremely quick-and-dirty, inadequately commented draft
> patch that does it along the lines you are suggesting.  This was just to
> see if I could get it to work at all; it's not meant for application in
> anything like its current state.  However, I feel a very strong
> temptation to finish it up and apply it before we enter beta.  As you
> noted, this way is a lot cheaper than the original coding, whether one
> focuses on the cost of failing cases or the cost when the optimization
> is successful.  And if we hold it off till 9.1, then any bug fixes that
> have to be made in the area later will need to be made against two
> significantly different implementations, which will be a real PITA.
>
> Things that would need to be cleaned up:
>
> * I left join_is_removable where it was, mainly so that it was easy to
> compare how much it changed for this usage (not a lot).  I'm not sure
> that joinpath.c is an appropriate place for it anymore, though I can't
> see any obviously better place either.  Any thoughts on that?

I dislike the idea of leaving it in joinpath.c.  I don't even think it
properly belongs in the path subdirectory since it no longer has
anything to do with paths.  Also worth thinking about where we would
put the logic I pontificated about here:

http://archives.postgresql.org/pgsql-hackers/2009-10/msg01012.php

> * The removed relation has to be taken out of the set of baserels
> somehow, else for example the Assert in make_one_rel will fail.
> The current hack is to change its reloptkind to RELOPT_OTHER_MEMBER_REL,
> which I think is a bit unclean.  We could try deleting it from the
> simple_rel_array altogether, but I'm worried that that could result in
> dangling-pointer failures, since we're probably not going to go to the
> trouble of removing every single reference to the rel from the planner
> data structures.  A possible compromise is to invent another reloptkind
> value that is only used for "dead" relations.

+1 for dead relation type.

> * It would be good to not count the removed relation in
> root->total_table_pages.  If we made either of the changes suggested
> above then we could move the calculation of total_table_pages down to
> after remove_useless_joins and ignore the removed relation(s)
> appropriately.  Otherwise I'm tempted to just subtract off the relation
> size from total_table_pages on-the-fly when we remove it.

Sounds good.

> * I'm not sure yet about the adjustment of PlaceHolder bitmaps --- we
> might need to break fix_placeholder_eval_levels into two steps to get
> it right.

Not familiar enough with that code to comment.

> * Still need to reverse out the now-dead code from the original patch,
> in particular the NoOpPath support.

Yeah.

> Thoughts?

I'm alarmed by your follow-on statement that the current code can't
handle the two-levels of removable join case.  Seems like it ought to
form {B C} as a path over {B} and then {A B C} as a path over {A}.
Given that it doesn't, we already have a fairly serious bug, so we've
either got to put more work into the old implementation or switch to
this new one - and I think at this point you and I are both fairly
convinced that this is a better way going forward.

...Robert

Re: join removal

Tom Lane <tgl@sss.pgh.pa.us> — 2010-03-28T15:56:28Z

Robert Haas <robertmhaas@gmail.com> writes:
> I'm alarmed by your follow-on statement that the current code can't
> handle the two-levels of removable join case.  Seems like it ought to
> form {B C} as a path over {B} and then {A B C} as a path over {A}.

Actually I think it ought to form {A B} as a no-op join and then be able
to join {A B} to {C} as a no-op join.  It won't recognize joining A to
{B C} as a no-op because the RHS isn't a baserel.  But yeah, I was quite
surprised at the failure too.  We should take the time to understand why
it's failing before we go further.  I ran out of steam last night but
will have a look into that today.

			regards, tom lane

Re: join removal

Simon Riggs <simon@2ndquadrant.com> — 2010-03-28T16:24:51Z

On Sun, 2010-03-28 at 02:15 -0400, Tom Lane wrote:
> I wrote:
> > [ crude patch ]
> 
> Oh, btw, if you try to run the regression test additions in that patch
> against CVS HEAD, you'll find out that HEAD actually fails to optimize
> the two-levels-of-removable-joins case.  Seems like another reason to
> press ahead with making the change.

Yes, please.

Does the new patch find more than two levels of join removal?

-- 
 Simon Riggs           www.2ndQuadrant.com

Re: join removal

Tom Lane <tgl@sss.pgh.pa.us> — 2010-03-28T16:38:08Z

Simon Riggs <simon@2ndQuadrant.com> writes:
> Does the new patch find more than two levels of join removal?

Well, I'd assume if it can do two nested levels then it should work for
any number, but I plead guilty to not having actually tested that.

			regards, tom lane

Re: join removal

Tom Lane <tgl@sss.pgh.pa.us> — 2010-03-28T17:23:11Z

I wrote:
> Robert Haas <robertmhaas@gmail.com> writes:
>> I'm alarmed by your follow-on statement that the current code can't
>> handle the two-levels of removable join case.  Seems like it ought to
>> form {B C} as a path over {B} and then {A B C} as a path over {A}.

> Actually I think it ought to form {A B} as a no-op join and then be able
> to join {A B} to {C} as a no-op join.  It won't recognize joining A to
> {B C} as a no-op because the RHS isn't a baserel.  But yeah, I was quite
> surprised at the failure too.  We should take the time to understand why
> it's failing before we go further.

OK, I traced through it, and the reason HEAD fails on this example is
that it *doesn't* recognize {A B} as a feasible no-op join, for
precisely the reason that it sees some B vars marked as being needed for
the not-yet-done {B C} join.  So that path is blocked, and the other
possible path to the desired result is also blocked because it won't
consider {B C} as a valid RHS for a removable join.

I don't see any practical way to escape the false-attr_needed problem
given the current code structure.  We could maybe hack our way to a
solution by weakening the restriction against the RHS being a join,
eg by noting that the best path for the RHS is a no-op join and then
drilling down to the one baserel.  But it seems pretty ugly.

So I think the conclusion is clear: we should consign the current
join-removal code to the dustbin and pursue the preprocessing way
instead.  Will work on it today.

			regards, tom lane

Re: join removal

Tom Lane <tgl@sss.pgh.pa.us> — 2010-03-28T18:04:05Z

Robert Haas <robertmhaas@gmail.com> writes:
> On Sun, Mar 28, 2010 at 12:19 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> * I left join_is_removable where it was, mainly so that it was easy to
>> compare how much it changed for this usage (not a lot). I'm not sure
>> that joinpath.c is an appropriate place for it anymore, though I can't
>> see any obviously better place either. Any thoughts on that?

> I dislike the idea of leaving it in joinpath.c.  I don't even think it
> properly belongs in the path subdirectory since it no longer has
> anything to do with paths.  Also worth thinking about where we would
> put the logic I pontificated about here:
> http://archives.postgresql.org/pgsql-hackers/2009-10/msg01012.php

The only argument I can see for leaving it where it is is that it
depends on clause_sides_match_join, which we'd have to either duplicate
or global-ize in order to continue sharing that code.  However, since
join_is_removable now needs a slightly different API for that anyway
(cf changes in draft patch), it's probably better to not try to share it.
So let's put the join removal code somewhere else.  The reasonable
alternatives seem to be:

* in a new file in prep/.  Although this clearly has the flavor of
preprocessing, all the other work in prep/ is done before we get into
query_planner().  So this choice seems a bit dubious.

* directly in plan/planmain.c.  Has the advantage of being where the
caller is, so no globally visible function declaration needed.  No other
redeeming social value though.

* in plan/initsplan.c.  Somewhat reasonable, although that file is
rather large already.

* in a new file in plan/.  Not sure if it's worth this, though your
thought that we might add more logic later makes it more defensible.

Comments?

			regards, tom lane

Re: join removal

Robert Haas <robertmhaas@gmail.com> — 2010-03-28T18:06:57Z

On Sun, Mar 28, 2010 at 2:04 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Robert Haas <robertmhaas@gmail.com> writes:
>> On Sun, Mar 28, 2010 at 12:19 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>>> * I left join_is_removable where it was, mainly so that it was easy to
>>> compare how much it changed for this usage (not a lot).  I'm not sure
>>> that joinpath.c is an appropriate place for it anymore, though I can't
>>> see any obviously better place either.  Any thoughts on that?
>
>> I dislike the idea of leaving it in joinpath.c.  I don't even think it
>> properly belongs in the path subdirectory since it no longer has
>> anything to do with paths.  Also worth thinking about where we would
>> put the logic I pontificated about here:
>> http://archives.postgresql.org/pgsql-hackers/2009-10/msg01012.php
>
> The only argument I can see for leaving it where it is is that it
> depends on clause_sides_match_join, which we'd have to either duplicate
> or global-ize in order to continue sharing that code.  However, since
> join_is_removable now needs a slightly different API for that anyway
> (cf changes in draft patch), it's probably better to not try to share it.
> So let's put the join removal code somewhere else.  The reasonable
> alternatives seem to be:
>
> * in a new file in prep/.  Although this clearly has the flavor of
> preprocessing, all the other work in prep/ is done before we get into
> query_planner().  So this choice seems a bit dubious.
>
> * directly in plan/planmain.c.  Has the advantage of being where the
> caller is, so no globally visible function declaration needed.  No other
> redeeming social value though.
>
> * in plan/initsplan.c.  Somewhat reasonable, although that file is
> rather large already.
>
> * in a new file in plan/.  Not sure if it's worth this, though your
> thought that we might add more logic later makes it more defensible.

I sort of like the last of these ideas though I'm at a loss for what
to call it.  Otherwise I kind of like planmain.c.

...Robert

Re: join removal

Tom Lane <tgl@sss.pgh.pa.us> — 2010-03-28T18:10:14Z

Robert Haas <robertmhaas@gmail.com> writes:
> On Sun, Mar 28, 2010 at 2:04 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> * in a new file in plan/. Not sure if it's worth this, though your
>> thought that we might add more logic later makes it more defensible.

> I sort of like the last of these ideas though I'm at a loss for what
> to call it.  Otherwise I kind of like planmain.c.

joinremoval.c ?

			regards, tom lane

Re: join removal

Robert Haas <robertmhaas@gmail.com> — 2010-03-28T19:55:19Z

On Sun, Mar 28, 2010 at 2:10 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Robert Haas <robertmhaas@gmail.com> writes:
>> On Sun, Mar 28, 2010 at 2:04 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>>> * in a new file in plan/.  Not sure if it's worth this, though your
>>> thought that we might add more logic later makes it more defensible.
>
>> I sort of like the last of these ideas though I'm at a loss for what
>> to call it.  Otherwise I kind of like planmain.c.
>
> joinremoval.c ?

Maybe, except as I mentioned in the email linked upthread, my plan for
implementing inner join removal would also include allowing join
reordering in cases where we currently don't.  So I don't want to
sandbox it too tightly as join removal, per se, though that's
certainly what we have on the table ATM.  It's more like advanced
open-heart join-tree surgery - like prepjointree, but much later in
the process.

...Robert

Re: join removal

Tom Lane <tgl@sss.pgh.pa.us> — 2010-03-28T20:12:32Z

Robert Haas <robertmhaas@gmail.com> writes:
> On Sun, Mar 28, 2010 at 2:10 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> joinremoval.c ?

> Maybe, except as I mentioned in the email linked upthread, my plan for
> implementing inner join removal would also include allowing join
> reordering in cases where we currently don't.  So I don't want to
> sandbox it too tightly as join removal, per se, though that's
> certainly what we have on the table ATM.  It's more like advanced
> open-heart join-tree surgery - like prepjointree, but much later in
> the process.

Hm.  At this point we're not really working with a join *tree* in any
case --- the data structure we're mostly concerned with is the list of
SpecialJoinInfo structs, and what we're trying to do is weaken the
constraints described by that list.  So I'd rather stay away from "tree"
terminology.

planjoins.c would fit with other names in the plan/ directory but it
seems like a misnomer because we're not really "planning" any joins
at this stage.

adjustjoins.c?  loosenjoins.c?  weakenjoins.c?

			regards, tom lane

Re: join removal

Robert Haas <robertmhaas@gmail.com> — 2010-03-28T21:08:32Z

On Sun, Mar 28, 2010 at 4:12 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Robert Haas <robertmhaas@gmail.com> writes:
>> On Sun, Mar 28, 2010 at 2:10 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>>> joinremoval.c ?
>
>> Maybe, except as I mentioned in the email linked upthread, my plan for
>> implementing inner join removal would also include allowing join
>> reordering in cases where we currently don't.  So I don't want to
>> sandbox it too tightly as join removal, per se, though that's
>> certainly what we have on the table ATM.  It's more like advanced
>> open-heart join-tree surgery - like prepjointree, but much later in
>> the process.
>
> Hm.  At this point we're not really working with a join *tree* in any
> case --- the data structure we're mostly concerned with is the list of
> SpecialJoinInfo structs, and what we're trying to do is weaken the
> constraints described by that list.  So I'd rather stay away from "tree"
> terminology.
>
> planjoins.c would fit with other names in the plan/ directory but it
> seems like a misnomer because we're not really "planning" any joins
> at this stage.
>
> adjustjoins.c?  loosenjoins.c?  weakenjoins.c?

How about analyzejoins.c?  Loosen and weaken don't seem like quite the
right idea; adjust is a little generic and perhaps overused, but not
bad.  If you don't like analyzejoins then go with adjustjoins.

...Robert

Re: join removal

Dimitri Fontaine <dfontaine@hi-media.com> — 2010-03-29T06:54:19Z

reducejoins.c ?
flattenjoins.c ?
filterjoins.c ?

--  
dim

Le 28 mars 2010 à 22:12, Tom Lane <tgl@sss.pgh.pa.us> a écrit :

> Robert Haas <robertmhaas@gmail.com> writes:
>> On Sun, Mar 28, 2010 at 2:10 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>>> joinremoval.c ?
>
>> Maybe, except as I mentioned in the email linked upthread, my plan  
>> for
>> implementing inner join removal would also include allowing join
>> reordering in cases where we currently don't.  So I don't want to
>> sandbox it too tightly as join removal, per se, though that's
>> certainly what we have on the table ATM.  It's more like advanced
>> open-heart join-tree surgery - like prepjointree, but much later in
>> the process.
>
> Hm.  At this point we're not really working with a join *tree* in any
> case --- the data structure we're mostly concerned with is the list of
> SpecialJoinInfo structs, and what we're trying to do is weaken the
> constraints described by that list.  So I'd rather stay away from  
> "tree"
> terminology.
>
> planjoins.c would fit with other names in the plan/ directory but it
> seems like a misnomer because we're not really "planning" any joins
> at this stage.
>
> adjustjoins.c?  loosenjoins.c?  weakenjoins.c?
>
>            regards, tom lane
>
> -- 
> Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-hackers

Re: join removal

Pavel Stehule <pavel.stehule@gmail.com> — 2010-03-29T08:19:37Z

Hello

is any reason why join removal doesn't remove useless relation b?

postgres=# \d a
       Table "public.a"
 Column |  Type   | Modifiers
--------+---------+-----------
 a      | integer |
Indexes:
    "a_a_idx" UNIQUE, btree (a)

postgres=# \d b
       Table "public.b"
 Column |  Type   | Modifiers
--------+---------+-----------
 b      | integer |
Indexes:
    "b_b_idx" UNIQUE, btree (b)

postgres=# explain select  a from a left join b on true;
                            QUERY PLAN
-------------------------------------------------------------------
 Nested Loop Left Join  (cost=0.00..72074.00 rows=5760000 width=4)
   ->  Seq Scan on a  (cost=0.00..34.00 rows=2400 width=4)
   ->  Materialize  (cost=0.00..46.00 rows=2400 width=0)
         ->  Seq Scan on b  (cost=0.00..34.00 rows=2400 width=0)
(4 rows)

postgres=# explain select distinct a from a left join b on true;
                                   QUERY PLAN
---------------------------------------------------------------------------------
 Unique  (cost=0.00..86520.25 rows=2400 width=4)
   ->  Nested Loop Left Join  (cost=0.00..72120.25 rows=5760000 width=4)
         ->  Index Scan using a_a_idx on a  (cost=0.00..80.25 rows=2400 width=4)
         ->  Materialize  (cost=0.00..46.00 rows=2400 width=0)
               ->  Seq Scan on b  (cost=0.00..34.00 rows=2400 width=0)
(5 rows)

Regards
Pavel Stehule

Re: join removal

Marko Tiikkaja <marko.tiikkaja@cs.helsinki.fi> — 2010-03-29T08:25:31Z

On 2010-03-29 11:19 +0200, Pavel Stehule wrote:
> postgres=# explain select  a from a left join b on true;

This is effectively a cross join and it would give wrong answers.  Try
SELECT a FROM a LEFT JOIN b ON a.a = b.b;


Regards,
Marko Tiikkaja

Re: join removal

Pavel Stehule <pavel.stehule@gmail.com> — 2010-03-29T08:33:07Z

2010/3/29 Marko Tiikkaja <marko.tiikkaja@cs.helsinki.fi>:
> On 2010-03-29 11:19 +0200, Pavel Stehule wrote:
>> postgres=# explain select  a from a left join b on true;

you have a true.

I forgot SELECT DISTINCT

regards

Pavel
>
> This is effectively a cross join and it would give wrong answers.  Try
> SELECT a FROM a LEFT JOIN b ON a.a = b.b;
>
>
> Regards,
> Marko Tiikkaja
>