Re: [HACKERS] join removal
2010/3/29 Marko Tiikkaja : > 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 > -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] join removal
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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] join removal
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=576 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=576 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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] join removal
reducejoins.c ? flattenjoins.c ? filterjoins.c ? -- dim Le 28 mars 2010 à 22:12, Tom Lane a écrit : Robert Haas writes: On Sun, Mar 28, 2010 at 2:10 PM, Tom Lane 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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] join removal
On Sun, Mar 28, 2010 at 4:12 PM, Tom Lane wrote: > Robert Haas writes: >> On Sun, Mar 28, 2010 at 2:10 PM, Tom Lane 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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] join removal
Robert Haas writes: > On Sun, Mar 28, 2010 at 2:10 PM, Tom Lane 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: [HACKERS] join removal
On Sun, Mar 28, 2010 at 2:10 PM, Tom Lane wrote: > Robert Haas writes: >> On Sun, Mar 28, 2010 at 2:04 PM, Tom Lane 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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] join removal
Robert Haas writes: > On Sun, Mar 28, 2010 at 2:04 PM, Tom Lane 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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] join removal
On Sun, Mar 28, 2010 at 2:04 PM, Tom Lane wrote: > Robert Haas writes: >> On Sun, Mar 28, 2010 at 12:19 AM, Tom Lane 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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] join removal
Robert Haas writes: > On Sun, Mar 28, 2010 at 12:19 AM, Tom Lane 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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] join removal
I wrote:
> Robert Haas 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
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] join removal
Simon Riggs 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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] join removal
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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] join removal
Robert Haas 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
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] join removal
On Sun, Mar 28, 2010 at 12:19 AM, Tom Lane wrote:
> Robert Haas writes:
>> On Sat, Mar 27, 2010 at 4:11 PM, Tom Lane 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
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] join removal
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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] join removal
Robert Haas writes:
> On Sat, Mar 27, 2010 at 4:11 PM, Tom Lane 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 - 1.131
--- src/backend/optimizer/path/joinpath.c 28 Mar 2010 03:50:58 -
***
*** 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))
- {
- gene
Re: [HACKERS] join removal
On Sat, Mar 27, 2010 at 4:11 PM, Tom Lane 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
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] join removal
Robert Haas writes: > On Sat, Mar 27, 2010 at 10:50 AM, Tom Lane 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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] join removal
On Sat, Mar 27, 2010 at 10:50 AM, Tom Lane wrote: > Robert Haas 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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] join removal
Robert Haas 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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] join removal
On Fri, Mar 26, 2010 at 6:10 PM, Tom Lane 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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] join removal
Robert Haas writes: > On Sun, Jul 19, 2009 at 10:56 PM, Tom Lane 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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] join removal
On Sun, Jul 19, 2009 at 10:56 PM, Tom Lane 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
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] join removal
On Sun, Aug 16, 2009 at 5:31 PM, Robert Haas 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
*** a/src/backend/optimizer/path/costsize.c
--- b/src/backend/optimizer/path/costsize.c
***
*** 109,114 bool enable_hashagg = true;
--- 109,115
bool enable_nestloop = true;
bool enable_mergejoin = true;
bool enable_hashjoin = true;
+ bool enable_joinremoval = true;
typedef struct
{
*** a/src/backend/optimizer/path/joinpath.c
--- b/src/backend/optimizer/path/joinpath.c
***
*** 16,26
--- 16,39
#include
+ #include "optimizer/clauses.h"
#include "optimizer/cost.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
+ typedef struct path_operator_clause {
+ List *mergeclause_list;
+ List *hashclause_list;
+ List *joinremovalclause_list;
+ List *joinremovalvarattno_list;
+ } path_operator_clause;
+
+ static bool join_is_removable(RelOptInfo *joinrel,
+ RelOptInfo *outerrel,
+ RelOptInfo *innerrel,
+ path_operator_clause *poc,
+ JoinType jointype);
static void sort_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel,
RelOptInfo *outerrel, RelOptInfo *innerrel,
List *restrictlist, List *mergeclause_list,
***
*** 31,47 static void match_unsorted_outer(PlannerInfo *root, RelOptInfo *joinrel,
JoinType jointype, SpecialJoinInfo *sjinfo);
static void hash_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel,
RelOptInfo *outerrel, RelOptInfo *innerrel,
! List *restrictlist,
JoinType jointype, SpecialJoinInfo *sjinfo);
static Path *best_appendrel_indexscan(PlannerInfo *root, RelOptInfo *rel,
RelOptInfo *outer_rel, JoinType jointype);
! static List *select_mergejoin_clauses(PlannerInfo *root,
! RelOptInfo *joinrel,
! RelOptInfo *outerrel,
! RelOptInfo *innerrel,
! List *restrictlist,
! JoinType jointype);
!
/*
* add_paths_to_joinrel
--- 44,61
JoinType jointype, SpecialJoinInfo *sjinfo);
static void hash_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel,
RelOptInfo *outerrel, RelOptInfo *innerrel,
! List *restrictlist, List *hashclauses,
JoinType jointype, SpecialJoinInfo *sjinfo);
static Path *best_appendrel_indexscan(PlannerInfo *root, RelOptInfo *rel,
RelOptInfo *outer_rel, JoinType jointype);
! static bool rel_attrs_needed_above_join(RelOptInfo *rel, RelOptInfo *joinrel);
! static void select_operator_clauses(PlannerInfo *root,
! RelOptInfo *joinrel,
! RelOptInfo *outerrel,
! RelOptInfo *innerrel,
! List *restrictlist,
! JoinType jointype,
! path_operator_clause *poc);
/*
* add_paths_to_joinrel
***
*** 75,135 add_paths_to_joinrel(PlannerInfo *root,
SpecialJoinInfo *sjinfo,
List *restrictlist)
{
! List *mergeclause_list = NIL;
/*
! * 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.
*/
! if (enable_mergejoin || jointype == JOIN_FULL)
! mergeclause_list = select_mergejoin_clauses(root,
! joinrel,
! outerrel,
! innerrel,
! restrictlist,
! jointype);
/*
! * 1. Consider mergejoin paths where both relations must be explicitly
* sorted.
*/
sort_inner_and_outer(root, joinrel, outerrel, innerrel,
! restrictlist, mergeclause_list, jointype, sjinfo);
/*
! * 2. Consider paths where the outer relation need not be explicitly
* sorted. This include
Re: [HACKERS] join removal
On Sun, Aug 9, 2009 at 12:19 PM, Tom Lane wrote: > Robert Haas 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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] join removal
> 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 cardinalityFuncs.c Description: cardinalityFuncs.c -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] join removal
On Sun, Aug 9, 2009 at 5:19 PM, Tom Lane 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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] join removal
Robert Haas 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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] join removal
On Sun, Jul 19, 2009 at 10:56 PM, Tom Lane 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, ))
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
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] join removal
On Fri, Jul 24, 2009 at 7:53 AM, Alex Brasetvik 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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] join removal
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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] join removal
Robert Haas writes: > On Sun, Jul 19, 2009 at 10:56 PM, Tom Lane 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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] join removal
On Sun, Jul 19, 2009 at 10:56 PM, Tom Lane wrote:
> Robert Haas writes:
>> On Thu, Jul 16, 2009 at 9:02 PM, Greg Stark 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
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] join removal
Robert Haas writes: > On Thu, Jul 16, 2009 at 9:02 PM, Greg Stark 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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] join removal
On Thu, Jul 16, 2009 at 9:02 PM, Greg Stark 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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] join removal
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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Join Removal/ Vertical Partitioning
Simon Riggs wrote: > > On Thu, 2008-06-26 at 13:42 -0400, Tom Lane wrote: > > Simon Riggs <[EMAIL PROTECTED]> writes: > > > We can check for removal of a rel by... > > OT comment: I just found a blog about Oracle's optimizermagic, which is > quite interesting. I notice there is a blog there about join removal, > posted about 12 hours later than my original post. Seems to validate the > theory anyway. Our posts have a wider audience than may be apparent :-) Yes, I think more people admire the work we do than we expect. -- Bruce Momjian <[EMAIL PROTECTED]>http://momjian.us EnterpriseDB http://enterprisedb.com + If your life is a hard drive, Christ can be your backup. + -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Join Removal/ Vertical Partitioning
On Thu, 2008-08-14 at 09:27 -0400, Robert Haas wrote: > I'm guessing it's this... looks pretty interesting even if not. > > http://optimizermagic.blogspot.com/2008/06/why-are-some-of-tables-in-my-query.html Yes, thanks for copying it in. -- Simon Riggs www.2ndQuadrant.com PostgreSQL Training, Services and Support -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Join Removal/ Vertical Partitioning
I'm guessing it's this... looks pretty interesting even if not. http://optimizermagic.blogspot.com/2008/06/why-are-some-of-tables-in-my-query.html ...Robert -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Join Removal/ Vertical Partitioning
"Simon Riggs" <[EMAIL PROTECTED]> writes: > On Thu, 2008-06-26 at 13:42 -0400, Tom Lane wrote: >> Simon Riggs <[EMAIL PROTECTED]> writes: >> > We can check for removal of a rel by... > > OT comment: I just found a blog about Oracle's optimizermagic, which is > quite interesting. I notice there is a blog there about join removal, > posted about 12 hours later than my original post. Seems to validate the > theory anyway. Our posts have a wider audience than may be apparent :-) Well turnabout's fair play... what's the URL? -- Gregory Stark EnterpriseDB http://www.enterprisedb.com Get trained by Bruce Momjian - ask me about EnterpriseDB's PostgreSQL training! -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Join Removal/ Vertical Partitioning
On Thu, 2008-06-26 at 13:42 -0400, Tom Lane wrote: > Simon Riggs <[EMAIL PROTECTED]> writes: > > We can check for removal of a rel by... OT comment: I just found a blog about Oracle's optimizermagic, which is quite interesting. I notice there is a blog there about join removal, posted about 12 hours later than my original post. Seems to validate the theory anyway. Our posts have a wider audience than may be apparent :-) -- Simon Riggs www.2ndQuadrant.com PostgreSQL Training, Services and Support -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Join Removal/ Vertical Partitioning
On Fri, 2008-06-27 at 17:50 -0400, Tom Lane wrote: > Simon Riggs <[EMAIL PROTECTED]> writes: > > On Thu, 2008-06-26 at 13:42 -0400, Tom Lane wrote: > >> It might be possible to treat "ignore the RHS" as a join strategy and > >> try to apply it while forming join relations, which would be late enough > >> to have all the needed info available. > > > Oh, actually have a join node that is a no-op, with a path cost of zero? > > Not even that: just return the best path(s) for the LHS as the paths for > the joinrel. Much neater. Cool. -- Simon Riggs www.2ndQuadrant.com PostgreSQL Training, Services and Support -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Join Removal/ Vertical Partitioning
Simon Riggs <[EMAIL PROTECTED]> writes: > On Thu, 2008-06-26 at 13:42 -0400, Tom Lane wrote: >> It might be possible to treat "ignore the RHS" as a join strategy and >> try to apply it while forming join relations, which would be late enough >> to have all the needed info available. > Oh, actually have a join node that is a no-op, with a path cost of zero? Not even that: just return the best path(s) for the LHS as the paths for the joinrel. 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: [HACKERS] Join Removal/ Vertical Partitioning
On Thu, 2008-06-26 at 13:42 -0400, Tom Lane wrote: > Simon Riggs <[EMAIL PROTECTED]> writes: > > We can check for removal of a rel by > > > 1. inspecting the target list for the query to see if there are rels > > that do not provide any attributes. (We might also use equivalence > > classes to recode the targetlist to minimise the numbers of tables > > touched, but I think that might be overkill). > > More to the point, it would be wrong. Equivalence classes do not imply > that two values considered equivalent are equal for all purposes, and > since we don't know what the client is going to do with the returned > data, we can't substitute some other value for the one requested. > > > So some thoughts on where to attempt this would be very useful. > > The hard part of this is figuring out where to do the work. As you say, > doing it during prepjointree seems the nicest from an abstract code > structure point of view, but it requires a lot of information that is > not derived until later. > It might be possible to treat "ignore the RHS" as a join strategy and > try to apply it while forming join relations, which would be late enough > to have all the needed info available. Oh, actually have a join node that is a no-op, with a path cost of zero? So we end up with an EXPLAIN like this: QUERY PLAN --- Join Removed (cost=0.00..8.27 rows=1 width=4) -> Index Scan using class_pkey on class c (cost=0.00..8.27 rows=1 width=8) Index Cond: (pk = 6) -> No Operation on subclass sc (cost=0.00..0.00 rows=0 width=0) (4 rows) That really does help, I think. The code allows us to say a join is impossible, but not very easily to say a join doesn't exist. I'll try it this way first. Maybe we'll see other ways as we go. -- Simon Riggs www.2ndQuadrant.com PostgreSQL Training, Services and Support -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Join Removal/ Vertical Partitioning
Simon Riggs <[EMAIL PROTECTED]> writes: > We can check for removal of a rel by > 1. inspecting the target list for the query to see if there are rels > that do not provide any attributes. (We might also use equivalence > classes to recode the targetlist to minimise the numbers of tables > touched, but I think that might be overkill). More to the point, it would be wrong. Equivalence classes do not imply that two values considered equivalent are equal for all purposes, and since we don't know what the client is going to do with the returned data, we can't substitute some other value for the one requested. > So some thoughts on where to attempt this would be very useful. The hard part of this is figuring out where to do the work. As you say, doing it during prepjointree seems the nicest from an abstract code structure point of view, but it requires a lot of information that is not derived until later. It might be possible to treat "ignore the RHS" as a join strategy and try to apply it while forming join relations, which would be late enough to have all the needed info available. 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
