Thread: join removal
Apologies for submitting new patches while we're still in the midst of CommitFest:November, but I think I've more or less come to the end of the reviewing that I can usefully do for 8.4 (or at least, I haven't had any requests lately, feel free...) and I don't want to wait forever to start thinking about 8.5. This patch is based on Simon Riggs' earlier work on join removal, although I don't believe I've actually used any of his code. Tom Lane's review comments on Simon's code were invaluable in getting this to work. I also understand that Simon plans to do more work in this area, so if this ends up getting sucked into his work or visca versa (or this ends up getting superseded altogether), that is fine. http://archives.postgresql.org/pgsql-patches/2008-08/msg00035.php http://archives.postgresql.org/pgsql-patches/2008-09/msg00024.php The theoretical underpinning of this patch is as follows: Joins can affect the result of a query in one of two ways: either they change the set of rows returned (by either increasing it or decreasing it), or they provide attributes. To remove a join, we need to prove that neither of these things is possible. It's pretty easy to test that the join isn't providing any attributes above the level of the join, and you'll see that rel_attrs_needed_above_join() handles that here. Verifying that the number of rows returned isn't changed by the join is harder. For the sake of simplicity, this patch only attempts to handle LEFT JOINs. Specifically, it attempts to prove that the results of scanning the outer side of the joinrel will be identical to the results of performing a merge-join, up to sorting. Nothing that happens on the inner side of the join can reduce the number of output rows (except via a WHERE-clause qual that will fail the rel_attrs_needed_above_join test anyway), so the only thing we need to worry about is the possibility that the join might increase the output row count. To do that, we need to know that there will be a sufficiently strong unique-ness property on the rows emitted by the inner side of the join. I believe that there are two main cases in which we could potentially prove this: the inner side of the join is an index scan (without resort) on a unique index, or the inner side of the join is a subselect with a group by clause over the join columns. For now, I'm only attempting to handle the first case, though it might be nice to eventually handle the other as well. Simon's original patch starts by checking whether the RelOptInfo for the relation to be dropped is a base relation, but that approach seems somewhat limiting, because we certainly want to be able to remove multiple joins in succession. Setting the paths for the joinrel {B C} to the paths for B doesn't help us when we try to form {A B C}, because now the join of {A} to {B C} is not a join against a base rel and join removal fails. The other problem is that at that level we don't really understand what's up with the join clauses: is the join operator even an equality operator? There is finally the problem that while we can get at the relevant IndexOptInfo structures and figure out which combinations of attributes have unique indices, I can't figure out any sane way to relate those attribute numbers back to the join clauses. So I've taken the alternative approach of working on the level of paths. sort_outer_and_inner(), before forming a join path, checks whether there happens to be a unique index with the same pathkeys as the inner side of the path. If so, and if no attributes are needed from the inner side of the join, the it pulls up all the paths from the outerrel into the joinrel and exits (really, it should skip the rest of add_paths_to_joinrel() as well, but it didn't seem worth refactoring that without some validation of the basic approach). This approach is limiting because sort_outer_and_inner() doesn't try every possible combination of pathkeys that might be helpful to us, but it seems likely to be adequate here for the same reasons that sort_outer_and_inner() gets away with it generally: the list of mergeclauses tends to be real short. (I think that if we were trying to optimize away an INNER join, this approach would be inadequate, because any non-merge-joinable join clauses could change the number of output rows. Here that can't happen: the most they can do is force the inner side to NULL, but if the inner side isn't being used that doesn't matter anyway. Of course, for INNER JOINs, we'd also need to worry about the merge-joinable clauses themselves stripping rows from the output due to a failure to match; we'd need to check for foreign key constraints.) I have a feeling there are probably lingering bugs in here, but it passes regression tests and some sample queries I tried still return the correct answers even after nuking one or more joins. Any comments appreciated, ...Robert
Attachment
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
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
Scanusing 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
Attachment
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
Attachment
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
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
Index: src/backend/optimizer/path/joinpath.c
===================================================================
RCS file: /cvsroot/pgsql/src/backend/optimizer/path/joinpath.c,v
retrieving revision 1.131
diff -c -r1.131 joinpath.c
*** src/backend/optimizer/path/joinpath.c 22 Mar 2010 13:57:15 -0000 1.131
--- src/backend/optimizer/path/joinpath.c 28 Mar 2010 03:50:58 -0000
***************
*** 22,32 ****
#include "optimizer/paths.h"
- static bool join_is_removable(PlannerInfo *root, RelOptInfo *joinrel,
- RelOptInfo *outerrel, RelOptInfo *innerrel,
- List *restrictlist, JoinType jointype);
- static void generate_outer_only(PlannerInfo *root, RelOptInfo *joinrel,
- RelOptInfo *outerrel);
static void sort_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel,
RelOptInfo *outerrel, RelOptInfo *innerrel,
List *restrictlist, List *mergeclause_list,
--- 22,27 ----
***************
*** 84,109 ****
List *mergeclause_list = NIL;
/*
- * 0. Consider join removal. This is always the most efficient strategy,
- * so if it works, there's no need to consider anything further.
- */
- if (join_is_removable(root, joinrel, outerrel, innerrel,
- restrictlist, jointype))
- {
- generate_outer_only(root, joinrel, outerrel);
- return;
- }
-
- /*
* Find potential mergejoin clauses. We can skip this if we are not
* interested in doing a mergejoin. However, mergejoin is currently our
* only way of implementing full outer joins, so override mergejoin
* disable if it's a full join.
- *
- * Note: do this after join_is_removable(), because this sets the
- * outer_is_left flags in the mergejoin clauses, while join_is_removable
- * uses those flags for its own purposes. Currently, they set the flags
- * the same way anyway, but let's avoid unnecessary entanglement.
*/
if (enable_mergejoin || jointype == JOIN_FULL)
mergeclause_list = select_mergejoin_clauses(root,
--- 79,88 ----
***************
*** 165,182 ****
* we set the transient flag outer_is_left to identify which side is which.
*/
static inline bool
! clause_sides_match_join(RestrictInfo *rinfo, RelOptInfo *outerrel,
! RelOptInfo *innerrel)
{
! if (bms_is_subset(rinfo->left_relids, outerrel->relids) &&
! bms_is_subset(rinfo->right_relids, innerrel->relids))
{
/* lefthand side is outer */
rinfo->outer_is_left = true;
return true;
}
! else if (bms_is_subset(rinfo->left_relids, innerrel->relids) &&
! bms_is_subset(rinfo->right_relids, outerrel->relids))
{
/* righthand side is outer */
rinfo->outer_is_left = false;
--- 144,161 ----
* we set the transient flag outer_is_left to identify which side is which.
*/
static inline bool
! clause_sides_match_join(RestrictInfo *rinfo, Relids outerrelids,
! Relids innerrelids)
{
! if (bms_is_subset(rinfo->left_relids, outerrelids) &&
! bms_is_subset(rinfo->right_relids, innerrelids))
{
/* lefthand side is outer */
rinfo->outer_is_left = true;
return true;
}
! else if (bms_is_subset(rinfo->left_relids, innerrelids) &&
! bms_is_subset(rinfo->right_relids, outerrelids))
{
/* righthand side is outer */
rinfo->outer_is_left = false;
***************
*** 187,193 ****
/*
* join_is_removable
! * Determine whether we need not perform the join at all, because
* it will just duplicate its left input.
*
* This is true for a left join for which the join condition cannot match
--- 166,172 ----
/*
* join_is_removable
! * Determine whether we need not perform a special join at all, because
* it will just duplicate its left input.
*
* This is true for a left join for which the join condition cannot match
***************
*** 195,213 ****
* cases, but we don't have the infrastructure to prove them.) We also
* have to check that the inner side doesn't generate any variables needed
* above the join.
- *
- * Note: there is no need to consider the symmetrical case of duplicating the
- * right input, because add_paths_to_joinrel() will be called with each rel
- * on the outer side.
*/
! static bool
! join_is_removable(PlannerInfo *root,
! RelOptInfo *joinrel,
! RelOptInfo *outerrel,
! RelOptInfo *innerrel,
! List *restrictlist,
! JoinType jointype)
{
List *clause_list = NIL;
ListCell *l;
int attroff;
--- 174,186 ----
* cases, but we don't have the infrastructure to prove them.) We also
* have to check that the inner side doesn't generate any variables needed
* above the join.
*/
! bool
! join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo)
{
+ int innerrelid;
+ RelOptInfo *innerrel;
+ Relids joinrelids;
List *clause_list = NIL;
ListCell *l;
int attroff;
***************
*** 220,227 ****
* now we just make sure there are indexes of some sort or other. If none
* of them are unique, join removal will still fail, just slightly later.
*/
! if (jointype != JOIN_LEFT ||
! innerrel->reloptkind == RELOPT_JOINREL ||
innerrel->rtekind != RTE_RELATION ||
innerrel->indexlist == NIL)
return false;
--- 193,207 ----
* now we just make sure there are indexes of some sort or other. If none
* of them are unique, join removal will still fail, just slightly later.
*/
! if (sjinfo->jointype != JOIN_LEFT ||
! sjinfo->delay_upper_joins ||
! bms_membership(sjinfo->min_righthand) != BMS_SINGLETON)
! return false;
!
! innerrelid = bms_singleton_member(sjinfo->min_righthand);
! innerrel = find_base_rel(root, innerrelid);
!
! if (innerrel->reloptkind != RELOPT_BASEREL ||
innerrel->rtekind != RTE_RELATION ||
innerrel->indexlist == NIL)
return false;
***************
*** 239,249 ****
* theory that the system attributes are somewhat less likely to be wanted
* and should be tested last.
*/
for (attroff = innerrel->max_attr - innerrel->min_attr;
attroff >= 0;
attroff--)
{
! if (!bms_is_subset(innerrel->attr_needed[attroff], joinrel->relids))
return false;
}
--- 219,231 ----
* theory that the system attributes are somewhat less likely to be wanted
* and should be tested last.
*/
+ joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
+
for (attroff = innerrel->max_attr - innerrel->min_attr;
attroff >= 0;
attroff--)
{
! if (!bms_is_subset(innerrel->attr_needed[attroff], joinrelids))
return false;
}
***************
*** 256,262 ****
PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
if (bms_is_subset(phinfo->ph_eval_at, innerrel->relids) &&
! !bms_is_subset(phinfo->ph_needed, joinrel->relids))
return false;
}
--- 238,244 ----
PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
if (bms_is_subset(phinfo->ph_eval_at, innerrel->relids) &&
! !bms_is_subset(phinfo->ph_needed, joinrelids))
return false;
}
***************
*** 267,282 ****
* it's what we want. The mergejoinability test also eliminates clauses
* containing volatile functions, which we couldn't depend on.
*/
! foreach(l, restrictlist)
{
RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
/*
* If we find a pushed-down clause, it must have come from above the
* outer join and it must contain references to the inner rel. (If it
* had only outer-rel variables, it'd have been pushed down into the
* outer rel.) Therefore, we can conclude that join removal is unsafe
* without any examination of the clause contents.
*/
if (restrictinfo->is_pushed_down)
return false;
--- 249,270 ----
* it's what we want. The mergejoinability test also eliminates clauses
* containing volatile functions, which we couldn't depend on.
*/
! foreach(l, innerrel->joininfo)
{
RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
+ /* Ignore clauses not pertinent to this join */
+ if (!bms_is_subset(restrictinfo->required_relids, joinrelids))
+ continue;
+
/*
* If we find a pushed-down clause, it must have come from above the
* outer join and it must contain references to the inner rel. (If it
* had only outer-rel variables, it'd have been pushed down into the
* outer rel.) Therefore, we can conclude that join removal is unsafe
* without any examination of the clause contents.
+ *
+ * XXX still appropriate?
*/
if (restrictinfo->is_pushed_down)
return false;
***************
*** 289,295 ****
/*
* Check if clause has the form "outer op inner" or "inner op outer".
*/
! if (!clause_sides_match_join(restrictinfo, outerrel, innerrel))
continue; /* no good for these input relations */
/* OK, add to list */
--- 277,284 ----
/*
* Check if clause has the form "outer op inner" or "inner op outer".
*/
! if (!clause_sides_match_join(restrictinfo, sjinfo->min_lefthand,
! innerrel->relids))
continue; /* no good for these input relations */
/* OK, add to list */
***************
*** 1031,1037 ****
/*
* Check if clause has the form "outer op inner" or "inner op outer".
*/
! if (!clause_sides_match_join(restrictinfo, outerrel, innerrel))
continue; /* no good for these input relations */
hashclauses = lappend(hashclauses, restrictinfo);
--- 1020,1027 ----
/*
* Check if clause has the form "outer op inner" or "inner op outer".
*/
! if (!clause_sides_match_join(restrictinfo, outerrel->relids,
! innerrel->relids))
continue; /* no good for these input relations */
hashclauses = lappend(hashclauses, restrictinfo);
***************
*** 1216,1222 ****
/*
* Check if clause has the form "outer op inner" or "inner op outer".
*/
! if (!clause_sides_match_join(restrictinfo, outerrel, innerrel))
{
have_nonmergeable_joinclause = true;
continue; /* no good for these input relations */
--- 1206,1213 ----
/*
* Check if clause has the form "outer op inner" or "inner op outer".
*/
! if (!clause_sides_match_join(restrictinfo, outerrel->relids,
! innerrel->relids))
{
have_nonmergeable_joinclause = true;
continue; /* no good for these input relations */
Index: src/backend/optimizer/plan/planmain.c
===================================================================
RCS file: /cvsroot/pgsql/src/backend/optimizer/plan/planmain.c,v
retrieving revision 1.117
diff -c -r1.117 planmain.c
*** src/backend/optimizer/plan/planmain.c 2 Jan 2010 16:57:47 -0000 1.117
--- src/backend/optimizer/plan/planmain.c 28 Mar 2010 03:50:58 -0000
***************
*** 29,34 ****
--- 29,37 ----
#include "utils/selfuncs.h"
+ static List *remove_useless_joins(PlannerInfo *root, List *joinlist);
+
+
/*
* query_planner
* Generate a path (that is, a simplified plan) for a basic query,
***************
*** 249,254 ****
--- 252,264 ----
fix_placeholder_eval_levels(root);
/*
+ * Remove any useless outer joins. Ideally this would be done during
+ * jointree preprocessing, but the necessary information isn't available
+ * until now.
+ */
+ joinlist = remove_useless_joins(root, joinlist);
+
+ /*
* Ready to do the primary planning.
*/
final_rel = make_one_rel(root, joinlist);
***************
*** 404,406 ****
--- 414,579 ----
*cheapest_path = cheapestpath;
*sorted_path = sortedpath;
}
+
+ extern bool
+ join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo);
+ static void
+ remove_rel_from_query(PlannerInfo *root, int relid);
+ static List *
+ remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved);
+
+ static List *
+ remove_useless_joins(PlannerInfo *root, List *joinlist)
+ {
+ ListCell *lc;
+
+ restart:
+ foreach(lc, root->join_info_list)
+ {
+ SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
+ int innerrelid;
+ int nremoved;
+
+ if (!join_is_removable(root, sjinfo))
+ continue;
+
+ /*
+ * Currently, join_is_removable can only succeed when the sjinfo's
+ * righthand is a single baserel. Remove that rel from the joinlist.
+ */
+ innerrelid = bms_singleton_member(sjinfo->min_righthand);
+
+ remove_rel_from_query(root, innerrelid);
+
+ nremoved = 0;
+ joinlist = remove_rel_from_joinlist(joinlist, innerrelid, &nremoved);
+ if (nremoved != 1)
+ elog(ERROR, "failed to find relation %d in joinlist", innerrelid);
+
+ /*
+ * We can delete this SpecialJoinInfo too, since it's no longer of
+ * interest.
+ */
+ root->join_info_list = list_delete_ptr(root->join_info_list, sjinfo);
+
+ /*
+ * Restart the scan. This is necessary to ensure we find all removable
+ * joins independently of ordering of the join_info_list (note that
+ * removal of attr_needed bits may make a join appear removable that
+ * did not before). Also, since we just deleted the current list
+ * cell, we'd have to have some hack to continue the list search
+ * anyway.
+ */
+ goto restart;
+ }
+
+ return joinlist;
+ }
+
+ /*
+ * Remove the target relid from the planner's data structures.
+ *
+ * We are not terribly thorough here. We must make sure that the rel is
+ * no longer visible as a baserel, and that attributes of other baserels
+ * are no longer marked as being needed at joins involving this rel.
+ * We don't have to bother removing join quals involving the rel from the
+ * joininfo lists; they'll just get ignored since we will never form a
+ * join relation that appears to match them.
+ */
+ static void
+ remove_rel_from_query(PlannerInfo *root, int relid)
+ {
+ RelOptInfo *rel = find_base_rel(root, relid);
+ Index rti;
+ ListCell *l;
+
+ /*
+ * Mark the rel as an "other" rel instead of a "base" rel, since it
+ * is no longer part of the join tree. (Could we remove it from
+ * the baserel array altogether? Or use a dedicated reloptkind?)
+ */
+ rel->reloptkind = RELOPT_OTHER_MEMBER_REL;
+
+ /*
+ * Remove references to the rel from other baserels' attr_needed arrays.
+ */
+ for (rti = 1; rti < root->simple_rel_array_size; rti++)
+ {
+ RelOptInfo *otherrel = root->simple_rel_array[rti];
+ int attroff;
+
+ /* there may be empty slots corresponding to non-baserel RTEs */
+ if (otherrel == NULL)
+ continue;
+
+ Assert(otherrel->relid == rti); /* sanity check on array */
+
+ for (attroff = otherrel->max_attr - otherrel->min_attr;
+ attroff >= 0;
+ attroff--)
+ {
+ otherrel->attr_needed[attroff] =
+ bms_del_member(otherrel->attr_needed[attroff], relid);
+ }
+ }
+
+ /*
+ * Likewise remove references from PlaceHolderVar data structures.
+ */
+ foreach(l, root->placeholder_list)
+ {
+ PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
+
+ phinfo->ph_eval_at = bms_del_member(phinfo->ph_eval_at, relid);
+ phinfo->ph_needed = bms_del_member(phinfo->ph_needed, relid);
+ }
+ }
+
+ /*
+ * Remove any occurrences of the target relid from a joinlist structure.
+ *
+ * It's easiest to build a whole new list structure, so we handle it that
+ * way. Efficiency is not a big deal here.
+ *
+ * *nremoved is incremented by the number of occurrences removed (there
+ * should be exactly one, but the caller checks that).
+ */
+ static List *
+ remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved)
+ {
+ List *result = NIL;
+ ListCell *jl;
+
+ foreach(jl, joinlist)
+ {
+ Node *jlnode = (Node *) lfirst(jl);
+
+ if (IsA(jlnode, RangeTblRef))
+ {
+ int varno = ((RangeTblRef *) jlnode)->rtindex;
+
+ if (varno == relid)
+ (*nremoved)++;
+ else
+ result = lappend(result, jlnode);
+ }
+ else if (IsA(jlnode, List))
+ {
+ /* Recurse to handle subproblem */
+ List *sublist;
+
+ sublist = remove_rel_from_joinlist((List *) jlnode,
+ relid, nremoved);
+ /* Avoid including empty sub-lists in the result */
+ if (sublist)
+ result = lappend(result, sublist);
+ }
+ else
+ {
+ elog(ERROR, "unrecognized joinlist node type: %d",
+ (int) nodeTag(jlnode));
+ }
+ }
+
+ return result;
+ }
Index: src/test/regress/expected/join.out
===================================================================
RCS file: /cvsroot/pgsql/src/test/regress/expected/join.out,v
retrieving revision 1.44
diff -c -r1.44 join.out
*** src/test/regress/expected/join.out 22 Mar 2010 13:57:16 -0000 1.44
--- src/test/regress/expected/join.out 28 Mar 2010 03:50:59 -0000
***************
*** 2494,2499 ****
--- 2494,2531 ----
--
-- test join removal
--
+ begin;
+ CREATE TEMP TABLE a (id int PRIMARY KEY, b_id int);
+ NOTICE: CREATE TABLE / PRIMARY KEY will create implicit index "a_pkey" for table "a"
+ CREATE TEMP TABLE b (id int PRIMARY KEY, c_id int);
+ NOTICE: CREATE TABLE / PRIMARY KEY will create implicit index "b_pkey" for table "b"
+ CREATE TEMP TABLE c (id int PRIMARY KEY);
+ NOTICE: CREATE TABLE / PRIMARY KEY will create implicit index "c_pkey" for table "c"
+ INSERT INTO a VALUES (0, 0), (1, NULL);
+ INSERT INTO b VALUES (0, 0), (1, NULL);
+ INSERT INTO c VALUES (0), (1);
+ -- all three cases should be optimizable into a simple seqscan
+ explain (costs off) SELECT a.* FROM a LEFT JOIN b ON a.b_id = b.id;
+ QUERY PLAN
+ ---------------
+ Seq Scan on a
+ (1 row)
+
+ explain (costs off) SELECT b.* FROM b LEFT JOIN c ON b.c_id = c.id;
+ QUERY PLAN
+ ---------------
+ Seq Scan on b
+ (1 row)
+
+ explain (costs off)
+ SELECT a.* FROM a LEFT JOIN (b left join c on b.c_id = c.id)
+ ON (a.b_id = b.id);
+ QUERY PLAN
+ ---------------
+ Seq Scan on a
+ (1 row)
+
+ rollback;
create temp table parent (k int primary key, pd int);
NOTICE: CREATE TABLE / PRIMARY KEY will create implicit index "parent_pkey" for table "parent"
create temp table child (k int unique, cd int);
***************
*** 2540,2542 ****
--- 2572,2595 ----
-> Seq Scan on child c
(5 rows)
+ -- bug 5255: this is not optimizable by join removal
+ begin;
+ CREATE TEMP TABLE a (id int PRIMARY KEY);
+ NOTICE: CREATE TABLE / PRIMARY KEY will create implicit index "a_pkey" for table "a"
+ CREATE TEMP TABLE b (id int PRIMARY KEY, a_id int);
+ NOTICE: CREATE TABLE / PRIMARY KEY will create implicit index "b_pkey" for table "b"
+ INSERT INTO a VALUES (0), (1);
+ INSERT INTO b VALUES (0, 0), (1, NULL);
+ SELECT * FROM b LEFT JOIN a ON (b.a_id = a.id) WHERE (a.id IS NULL OR a.id > 0);
+ id | a_id | id
+ ----+------+----
+ 1 | |
+ (1 row)
+
+ SELECT b.* FROM b LEFT JOIN a ON (b.a_id = a.id) WHERE (a.id IS NULL OR a.id > 0);
+ id | a_id
+ ----+------
+ 1 |
+ (1 row)
+
+ rollback;
Index: src/test/regress/sql/join.sql
===================================================================
RCS file: /cvsroot/pgsql/src/test/regress/sql/join.sql,v
retrieving revision 1.33
diff -c -r1.33 join.sql
*** src/test/regress/sql/join.sql 22 Mar 2010 13:57:16 -0000 1.33
--- src/test/regress/sql/join.sql 28 Mar 2010 03:50:59 -0000
***************
*** 572,577 ****
--- 572,595 ----
-- test join removal
--
+ begin;
+
+ CREATE TEMP TABLE a (id int PRIMARY KEY, b_id int);
+ CREATE TEMP TABLE b (id int PRIMARY KEY, c_id int);
+ CREATE TEMP TABLE c (id int PRIMARY KEY);
+ INSERT INTO a VALUES (0, 0), (1, NULL);
+ INSERT INTO b VALUES (0, 0), (1, NULL);
+ INSERT INTO c VALUES (0), (1);
+
+ -- all three cases should be optimizable into a simple seqscan
+ explain (costs off) SELECT a.* FROM a LEFT JOIN b ON a.b_id = b.id;
+ explain (costs off) SELECT b.* FROM b LEFT JOIN c ON b.c_id = c.id;
+ explain (costs off)
+ SELECT a.* FROM a LEFT JOIN (b left join c on b.c_id = c.id)
+ ON (a.b_id = b.id);
+
+ rollback;
+
create temp table parent (k int primary key, pd int);
create temp table child (k int unique, cd int);
insert into parent values (1, 10), (2, 20), (3, 30);
***************
*** 590,592 ****
--- 608,623 ----
select p.*, linked from parent p
left join (select c.*, true as linked from child c) as ss
on (p.k = ss.k);
+
+ -- bug 5255: this is not optimizable by join removal
+ begin;
+
+ CREATE TEMP TABLE a (id int PRIMARY KEY);
+ CREATE TEMP TABLE b (id int PRIMARY KEY, a_id int);
+ INSERT INTO a VALUES (0), (1);
+ INSERT INTO b VALUES (0, 0), (1, NULL);
+
+ SELECT * FROM b LEFT JOIN a ON (b.a_id = a.id) WHERE (a.id IS NULL OR a.id > 0);
+ SELECT b.* FROM b LEFT JOIN a ON (b.a_id = a.id) WHERE (a.id IS NULL OR a.id > 0);
+
+ rollback;
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
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
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
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
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
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
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
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
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
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
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
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
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
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=5760000width=4) -> Seq Scan on a (cost=0.00..34.00 rows=2400 width=4) -> Materialize (cost=0.00..46.00 rows=2400width=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 Scanon b (cost=0.00..34.00 rows=2400 width=0) (5 rows) Regards Pavel Stehule
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
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 >