Обсуждение: Allowing join removals for more join types

David Rowley <dgrowleyml@gmail.com> writes:
> It looks like the existing join removals are done quite early in the
> planning and redundant joins are removed before any subqueries from that
> query are planned. So this innerrel->subroot->parse has not been done yet.
> It seems to be done later in query_planner() when make_one_rel() is called.

It's true that we don't plan the subquery till later, but I don't see why
that's important here.  Everything you want to know is available from the
subquery parsetree; so just look at the RTE, don't worry about how much
of the RelOptInfo has been filled in.

> The best I can come up with on how to implement this is to have 2 stages of
> join removals. Stage 1 would be the existing stage that attempts to remove
> joins from non subqueries. Stage 2 would happen just after make_one_rel()
> is called from query_planner(), this would be to attempt to remove any
> subqueries that are not need, and if it managed to remove any it would
> force a 2nd call to make_one_rel().

That sounds like a seriously bad idea.  For one thing, it blows the
opportunity to not plan the subquery in the first place.  For another,
most of these steps happen in a carefully chosen order because there
are interdependencies.  You can't just go back and re-run some earlier
processing step.  A large fraction of the complexity of analyzejoins.c
right now arises from the fact that it has to undo some earlier
processing; that would get enormously worse if you delayed it further.

BTW, just taking one step back ... this seems like a pretty specialized
requirement.  Are you sure it wouldn't be easier to fix your app to
not generate such silly queries?
        regards, tom lane

<div class="WordSection1"><p class="MsoNormal"><span
style="font-size:10.0pt;font-family:"Tahoma","sans-serif"">On</span><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"></span><span
style="font-size:10.0pt;font-family:"Tahoma","sans-serif"">19May 2014 12:15 </span>David Rowley Wrote,<span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"></span><pclass="MsoNormal"> <p
class="MsoNormal">>Ithink you are right here, it would be correct to remove that join, but I also think that the
queryin question could be quite easily be written as:<p class="MsoNormal"> <p class="MsoNormal">>select t1.a from t1
leftjoin t2 on t1.a=t2.b;<p class="MsoNormal"> <p class="MsoNormal">>Where the join WILL be removed. The distinct
clausehere technically is a no-op due to all the columns of a unique index being present in the clause. Can you think
ofa use case for this where the sub query couldn't have been written out as a direct join to the relation?<p
class="MsoNormal"> <pclass="MsoNormal">>What would be the reason to make it a sub query with the distinct? or have I
gottensomething wrong here?<p class="MsoNormal"> <p class="MsoNormal">>I'm also thinking here that if we made the
joinremoval code remove these joins, then the join removal code would end up smarter than the rest of the code as the
currentcode seems not to remove the distinct clause for single table queries where a subset of the columns of a
distinctclause match all the columns of a unique index.<p class="MsoNormal"> <p class="MsoNormal">>Can you think of
asimilar example where the subquery could not have been written as a direct join to the relation?<p
class="MsoNormal"><spanstyle="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"> </span><p
class="MsoNormal">Ithink, you are write that above given query and be written in very simple join.<p
class="MsoNormal"> <pclass="MsoNormal">But what my point is, In any case when optimizer cannot pull up the  subquery
(becauseit may have aggregate, group by, order by, limit, distinct etc.. clause),<p class="MsoNormal">That time even,
Itwill check Whether join is removable or not only when distinct or group by clause is there if it has unique index
thenit will not be check, is there no scenario where it will be useful ?<p class="MsoNormal"> <p class="MsoNormal">May
bewe can convert my above example like below  <span style="font-family:Wingdings"> à</span> in this case we have unique
indexon field a and we are limiting it by first 100 tuple (record are already order because of index)<p
class="MsoNormal"> <pclass="MsoNormal">Create table t1 (a int, b int); <p class="MsoNormal">Create table t2 (a int, b
int);<pclass="MsoNormal">Create unique index on t2(a);<p class="MsoNormal"> <p class="MsoNormal">create view v1 as<p
class="MsoNormal">selectx.a, y.b <p class="MsoNormal">from t1 x left join (select t2.a a1, b from t2  limit 100) as y
onx.a=y.a1;<p class="MsoNormal"> <p class="MsoNormal">select a from v1;  <span style="font-family:Wingdings">à</span>
forthis query I think left join can be removed, But in view since non join field(b) is also projected so this cannot be
simplifiedthere.<p class="MsoNormal"> <p class="MsoNormal">In your patch, anyway we are having check for distinct and
groupclause inside subquery, can’t we have check for unique index also ?<p class="MsoNormal"> <p
class="MsoNormal">Regards,<pclass="MsoNormal">Dilip<p class="MsoNormal"> <p class="MsoNormal"> <p
class="MsoNormal"> </div>

David Rowley <dgrowleyml@gmail.com> writes:
> I'm also now wondering if I need to do some extra tests in the existing
> code to ensure that the subquery would have had no side affects.

You should probably at least refuse the optimization if the subquery's
tlist contains volatile functions.

Functions that return sets might be problematic too [ experiments... ]
Yeah, they are.  This behavior is actually a bit odd:

regression=# select q1 from int8_tbl;       q1        
------------------             123             123456789012345678945678901234567894567890123456789
(5 rows)

regression=# select q1 from int8_tbl group by 1;       q1        
------------------4567890123456789             123
(2 rows)

regression=# select q1,unnest(array[1,2]) as u from int8_tbl;       q1        | u 
------------------+---             123 | 1             123 | 2             123 | 1             123 | 24567890123456789
|14567890123456789 | 24567890123456789 | 14567890123456789 | 24567890123456789 | 14567890123456789 | 2
 
(10 rows)

regression=# select q1,unnest(array[1,2]) as u from int8_tbl group by 1;       q1        | u 
------------------+---4567890123456789 | 14567890123456789 | 2             123 | 1             123 | 2
(4 rows)

EXPLAIN shows that the reason the last case behaves like that is that
the SRF is expanded *after* the grouping step.  I'm not entirely sure if
that's a bug --- given the lack of complaints, perhaps not.  But it shows
you can't apply this optimization without changing the existing behavior.

I doubt you should drop a subquery containing FOR UPDATE, either.
That's a side effect, just as much as a volatile function would be.
        regards, tom lane

<div class="WordSection1"><p class="MsoNormal"><span
style="font-size:10.0pt;font-family:"Tahoma","sans-serif"">On</span><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"></span><span
style="font-size:10.0pt;font-family:"Tahoma","sans-serif"">23May 2014 12:43 David Rowley Wrote,</span><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"></span><pclass="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"> </span><pclass="MsoNormal">>I'm hitting a
bitof a roadblock on point 1. Here's a snipped from my latest attempt:<p class="MsoNormal"> <p
class="MsoNormal">>                     if (bms_membership(innerrel->relids) == BMS_SINGLETON)<p
class="MsoNormal">>                     {<p class="MsoNormal">>                                  int
subqueryrelid= bms_singleton_member(innerrel->relids);<p class="MsoNormal">>                                 
RelOptInfo*subqueryrel = find_base_rel(innerrel->subroot, subqueryrelid);<p
class="MsoNormal">>                     <p class="MsoNormal">>                                  if
(relation_has_unique_index_for(root,subqueryrel, clause_list, NIL, NIL))<p
class="MsoNormal">>                                             return true;<p
class="MsoNormal">>                     }<p class="MsoNormal"> <p class="MsoNormal">>But it seems that
innerrel->subrootis still NULL at this stage of planning and from what I can tell does not exist anywhere else yet
andis not generated until make_one_rel() is called from query_planner()<p class="MsoNormal"> <p
class="MsoNormal">>AmI missing something major here,or does this sound about right?<p class="MsoNormal"> <p
class="MsoNormal">It’strue that, till this point of time we haven’t prepared the base relation list for the subquery,
andthat will be done from make_one_rel while generating the SUBQURY path list.<p class="MsoNormal"> <p
class="MsoNormal">Ican think of one solution but I think it will be messy…<p class="MsoNormal"> <p class="MsoNormal">We
getthe base relation info directly from subquery <p class="MsoNormal">Like currently in your patch (shown in below
snippet)we are getting the distinct and groupby clause from sub Query,  similarly we can get base relation info from 
(Query->jointree)<pclass="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"> </span><pclass="MsoNormal">            if
(innerrel->rtekind== RTE_SUBQUERY)<p class="MsoNormal">            {<p class="MsoNormal">                       
Query*query = root->simple_rte_array[innerrelid]->subquery;<p class="MsoNormal"> <p
class="MsoNormal">                       if (sortclause_is_unique_on_restrictinfo(query, clause_list,
query->groupClause)||<p class="MsoNormal">                                   
sortclause_is_unique_on_restrictinfo(query,clause_list, query->distinctClause))<p
class="MsoNormal">                                   return true;<p class="MsoNormal">            }<p
class="MsoNormal"><spanstyle="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"> </span><p
class="MsoNormal"><spanstyle="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"> </span><p
class="MsoNormal">Regards,<pclass="MsoNormal">Dilip</div> 

David Rowley <dgrowleyml@gmail.com> writes:
> I've just had a bit of a look at implementing checks allowing subqueries
> with unique indexes on the join cols being removed,

I'm a bit confused by this statement of the problem.  I thought the idea
was to recognize that subqueries with DISTINCT or GROUP BY clauses produce
known-unique output column(s), which permits join removal in the same way
that unique indexes on a base table allow us to deduce that certain
columns are known-unique and hence can offer no more than one match for
a join.  That makes it primarily a syntactic check, which you can perform
despite the fact that the subquery hasn't been planned yet (since the
parser has done sufficient analysis to determine the semantics of
DISTINCT/GROUP BY).

Drilling down into the subquery is a whole different matter.  For one
thing, there's no point in targeting cases in which the subquery would be
eligible to be flattened into the parent query, and your proposed list of
restrictions seems to eliminate most cases in which it couldn't be
flattened.  For another, you don't have access to any planning results for
the subquery yet, which is the immediate problem you're complaining of.
Duplicating the work of looking up a relation's indexes seems like a
pretty high price to pay for whatever improvement you might get here.
        regards, tom lane

David Rowley <dgrowleyml@gmail.com> writes:
> I agree that there are not many cases left to remove the join that remain
> after is_simple_subquery() has decided not to pullup the subquery. Some of
> the perhaps more common cases would be having windowing functions in the
> subquery as this is what you need to do if you want to include the results
> of a windowing function from within the where clause. Another case, though
> I can't imagine it would be common, is ORDER BY in the subquery... But for
> that one I can't quite understand why is_simple_subquery() stops that being
> flattened in the first place.

The problem there is that (in general) pushing qual conditions to below a
window function will change the window function's results.  If we flatten
such a subquery then the outer query's quals can get evaluated before
the window function, so that's no good.  Another issue is that flattening
might cause the window function call to get copied to places in the outer
query where it can't legally go, such as the WHERE clause.
        regards, tom lane

David Rowley <dgrowleyml@gmail.com> writes:
> I'm not quite there with inner joins yet. I'm still getting my head around
> just where the join quals are actually stored.

TBH I think that trying to do anything at all for inner joins is probably
a bad idea.  The cases where the optimization could succeed are so narrow
that it's unlikely to be worth adding cycles to every query to check.

The planning cost of all this is likely to be a concern anyway; but
if you can show that you don't add anything unless there are some outer
joins in the query, you can at least overcome objections about possibly
adding significant overhead to trivial queries.
        regards, tom lane

* Tom Lane (tgl@sss.pgh.pa.us) wrote:
> David Rowley <dgrowleyml@gmail.com> writes:
> > I'm not quite there with inner joins yet. I'm still getting my head around
> > just where the join quals are actually stored.
>
> TBH I think that trying to do anything at all for inner joins is probably
> a bad idea.  The cases where the optimization could succeed are so narrow
> that it's unlikely to be worth adding cycles to every query to check.

I agree that we don't want to add too many cycles to trivial queries but
I don't think it's at all fair to say that FK-check joins are a narrow
use-case and avoiding that join could be a very nice win.

> The planning cost of all this is likely to be a concern anyway; but
> if you can show that you don't add anything unless there are some outer
> joins in the query, you can at least overcome objections about possibly
> adding significant overhead to trivial queries.

I'm not quite buying this.  We're already beyond really trivial queries
since we're talking about joins and then considering how expensive joins
can be, putting in a bit of effort to eliminate one would be time well
worth spending, imv.

In any case, I'd certainly suggest David continue to develop this and
then we can look at measuring the cost on cases where it was time wasted
and on cases where it helps.  We may also be able to come up with ways
to short-circuit the test and thereby minimize the cost in cases where
it won't help.
Thanks,
    Stephen

Stephen Frost <sfrost@snowman.net> writes:
> * Tom Lane (tgl@sss.pgh.pa.us) wrote:
>> TBH I think that trying to do anything at all for inner joins is probably
>> a bad idea.  The cases where the optimization could succeed are so narrow
>> that it's unlikely to be worth adding cycles to every query to check.

> I agree that we don't want to add too many cycles to trivial queries but
> I don't think it's at all fair to say that FK-check joins are a narrow
> use-case and avoiding that join could be a very nice win.

[ thinks for a bit... ]  OK, I'd been thinking that to avoid a join the
otherwise-unreferenced table would have to have a join column that is both
unique and the referencing side of an FK to the other table's join column.
But after consuming more caffeine I see I got that backwards and it would
need to be the *referenced* side of the FK, which is indeed a whole lot
more plausible case.
        regards, tom lane

On Wed, May 28, 2014 at 08:39:32PM +1200, David Rowley wrote:
> The attached patch allows join removals for both sub queries with left
> joins and also semi joins where a foreign key can prove the existence of
> the record.

When a snapshot can see modifications that queued referential integrity
triggers for some FK constraint, that constraint is not guaranteed to hold
within the snapshot until those triggers have fired.  For example, a query
running within a VOLATILE function f() in a statement like "UPDATE t SET c =
f(c)" may read data that contradicts FK constraints involving table "t".
Deferred UNIQUE constraints, which we also do not yet use for deductions in
the planner, have the same problem; see commit 0f39d50.  This project will
need a design accounting for that hazard.

As a point of procedure, I recommend separating the semijoin support into its
own patch.  Your patch is already not small; delaying non-essential parts will
make the essential parts more accessible to reviewers.

Thanks,
nm

-- 
Noah Misch
EnterpriseDB                                 http://www.enterprisedb.com

David Rowley <dgrowleyml@gmail.com> writes:
> On Wed, Jun 4, 2014 at 11:50 AM, Noah Misch <noah@leadboat.com> wrote:
>> When a snapshot can see modifications that queued referential integrity
>> triggers for some FK constraint, that constraint is not guaranteed to hold
>> within the snapshot until those triggers have fired.

> I remember reading about some concerns with that here:
> http://www.postgresql.org/message-id/51E2D505.5010705@2ndQuadrant.com
> But I didn't quite understand the situation where the triggers are delayed.
> I just imagined that the triggers would have fired by the time the command
> had completed. If that's not the case, when do the triggers fire? on
> commit? Right now I've no idea how to check for this in order to disable
> the join removal.

I'm afraid that this point destroys your entire project :-( ... even
without deferred constraints, there's no good way to be sure that you're
not planning a query that will be run inside some function that can see
the results of partially-completed updates.  The equivalent problem for
unique indexes is tolerable because the default choice is immediate
uniqueness enforcement, but there's no similar behavior for FKs.

It's possible that we could apply the optimization only to queries that
have been issued directly by a client, but that seems rather ugly and
surprise-filled.
        regards, tom lane

On Wed, Jun 04, 2014 at 10:14:42AM -0400, Tom Lane wrote:
> David Rowley <dgrowleyml@gmail.com> writes:
> > On Wed, Jun 4, 2014 at 11:50 AM, Noah Misch <noah@leadboat.com> wrote:
> >> When a snapshot can see modifications that queued referential integrity
> >> triggers for some FK constraint, that constraint is not guaranteed to hold
> >> within the snapshot until those triggers have fired.
> 
> > I remember reading about some concerns with that here:
> > http://www.postgresql.org/message-id/51E2D505.5010705@2ndQuadrant.com
> > But I didn't quite understand the situation where the triggers are delayed.
> > I just imagined that the triggers would have fired by the time the command
> > had completed. If that's not the case, when do the triggers fire? on

Normally, they fire in AfterTriggerEndQuery(), which falls at the end of a
command.  The trouble arises there when commands nest.  (If the constraint is
deferred, they fire just before COMMIT.)

> > commit? Right now I've no idea how to check for this in order to disable
> > the join removal.
> 
> I'm afraid that this point destroys your entire project :-( ... even
> without deferred constraints, there's no good way to be sure that you're
> not planning a query that will be run inside some function that can see
> the results of partially-completed updates.  The equivalent problem for
> unique indexes is tolerable because the default choice is immediate
> uniqueness enforcement, but there's no similar behavior for FKs.

Let's not give up just yet.  There's considerable middle ground between
ignoring the hazard and ignoring all FK constraints in the planner, ...

> It's possible that we could apply the optimization only to queries that
> have been issued directly by a client, but that seems rather ugly and
> surprise-filled.

... such as this idea.  It's a good start to a fairly-hard problem.  FKs are
also always valid when afterTriggers->query_depth == -1, such as when all
ongoing queries qualified for EXEC_FLAG_SKIP_TRIGGERS.  What else?  We could
teach trigger.c to efficiently report whether a given table has a queued RI
trigger.  Having done that, when plancache.c is building a custom plan, the
planner could ignore FKs with pending RI checks and use the rest.  At that
point, the surprises will be reasonably-isolated.

-- 
Noah Misch
EnterpriseDB                                 http://www.enterprisedb.com

On 2014-06-04 20:04:07 -0400, Noah Misch wrote:
> On Wed, Jun 04, 2014 at 10:14:42AM -0400, Tom Lane wrote:
> > It's possible that we could apply the optimization only to queries that
> > have been issued directly by a client, but that seems rather ugly and
> > surprise-filled.
> 
> ... such as this idea.  It's a good start to a fairly-hard problem.  FKs are
> also always valid when afterTriggers->query_depth == -1, such as when all
> ongoing queries qualified for EXEC_FLAG_SKIP_TRIGGERS.  What else?  We could
> teach trigger.c to efficiently report whether a given table has a queued RI
> trigger.  Having done that, when plancache.c is building a custom plan, the
> planner could ignore FKs with pending RI checks and use the rest.  At that
> point, the surprises will be reasonably-isolated.

A bit more crazy, but how about trying trying to plan joins with a added
one-time qual that checks the size of the deferred trigger queue? Then
we wouldn't even need special case plans.

Greetings,

Andres Freund

-- Andres Freund                       http://www.2ndQuadrant.com/PostgreSQL Development, 24x7 Support, Training &
Services

On Thu, Jun 05, 2014 at 02:12:33AM +0200, Andres Freund wrote:
> On 2014-06-04 20:04:07 -0400, Noah Misch wrote:
> > On Wed, Jun 04, 2014 at 10:14:42AM -0400, Tom Lane wrote:
> > > It's possible that we could apply the optimization only to queries that
> > > have been issued directly by a client, but that seems rather ugly and
> > > surprise-filled.
> > 
> > ... such as this idea.  It's a good start to a fairly-hard problem.  FKs are
> > also always valid when afterTriggers->query_depth == -1, such as when all
> > ongoing queries qualified for EXEC_FLAG_SKIP_TRIGGERS.  What else?  We could
> > teach trigger.c to efficiently report whether a given table has a queued RI
> > trigger.  Having done that, when plancache.c is building a custom plan, the
> > planner could ignore FKs with pending RI checks and use the rest.  At that
> > point, the surprises will be reasonably-isolated.
> 
> A bit more crazy, but how about trying trying to plan joins with a added
> one-time qual that checks the size of the deferred trigger queue? Then
> we wouldn't even need special case plans.

That, too, sounds promising to investigate.

-- 
Noah Misch
EnterpriseDB                                 http://www.enterprisedb.com

Noah Misch <noah@leadboat.com> writes:
> On Thu, Jun 05, 2014 at 02:12:33AM +0200, Andres Freund wrote:
>> A bit more crazy, but how about trying trying to plan joins with a added
>> one-time qual that checks the size of the deferred trigger queue? Then
>> we wouldn't even need special case plans.

> That, too, sounds promising to investigate.

Not terribly.  You can't actually do join removal in such a case, so it's
not clear to me that there's much win to be had.  The planner would be at
a loss as to what cost to assign such a construct, either.

Moreover, what happens if the trigger queue gets some entries after the
query starts?
        regards, tom lane

On Thu, Jun 05, 2014 at 07:44:31PM -0400, Tom Lane wrote:
> Noah Misch <noah@leadboat.com> writes:
> > On Thu, Jun 05, 2014 at 02:12:33AM +0200, Andres Freund wrote:
> >> A bit more crazy, but how about trying trying to plan joins with a added
> >> one-time qual that checks the size of the deferred trigger queue? Then
> >> we wouldn't even need special case plans.
> 
> > That, too, sounds promising to investigate.
> 
> Not terribly.  You can't actually do join removal in such a case, so it's
> not clear to me that there's much win to be had.  The planner would be at
> a loss as to what cost to assign such a construct, either.

Yes, those are noteworthy points against it.

> Moreover, what happens if the trigger queue gets some entries after the
> query starts?

Normally, the query's snapshot will hide modifications that prompted those
entries.  Searching for exceptions to that rule should be part of this
development effort.

A related special case came to mind: queries running in the WHEN condition of
an AFTER ROW trigger.  If the trigger in question precedes the RI triggers,
the queue will not yet evidence the triggering modification.  Nonetheless,
queries in the WHEN clause will see that modification.

-- 
Noah Misch
EnterpriseDB                                 http://www.enterprisedb.com

On Mon, Jun 2, 2014 at 11:42 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Stephen Frost <sfrost@snowman.net> writes:
>> * Tom Lane (tgl@sss.pgh.pa.us) wrote:
>>> TBH I think that trying to do anything at all for inner joins is probably
>>> a bad idea.  The cases where the optimization could succeed are so narrow
>>> that it's unlikely to be worth adding cycles to every query to check.
>
>> I agree that we don't want to add too many cycles to trivial queries but
>> I don't think it's at all fair to say that FK-check joins are a narrow
>> use-case and avoiding that join could be a very nice win.
>
> [ thinks for a bit... ]  OK, I'd been thinking that to avoid a join the
> otherwise-unreferenced table would have to have a join column that is both
> unique and the referencing side of an FK to the other table's join column.
> But after consuming more caffeine I see I got that backwards and it would
> need to be the *referenced* side of the FK, which is indeed a whole lot
> more plausible case.

Back when I did web development, this came up for me all the time.
I'd create a fact table with lots of id columns referencing dimension
tables, and then make a view over it that joined to all of those
tables so that it was easy, when reporting, to select whatever bits of
information were needed.  But the problem was that if the report
didn't need all the columns, it still had to pay the cost of computing
them, which eventually got to be problematic.  That was what inspired
me to develop the patch for LEFT JOIN removal, but to really solve the
problems I had back then, removing INNER joins as well would have been
essential.  So, while I do agree that we have to keep the planning
cost under control, I'm quite positive about the general concept.  I
think a lot of users will benefit.

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

On 17 June 2014 11:04, David Rowley <dgrowleyml@gmail.com> wrote:
> On Wed, Jun 4, 2014 at 12:50 AM, Noah Misch <noah@leadboat.com> wrote:
>>
>> As a point of procedure, I recommend separating the semijoin support into
>> its
>> own patch.  Your patch is already not small; delaying non-essential parts
>> will
>> make the essential parts more accessible to reviewers.
>>
>
> In the attached patch I've removed all the SEMI and ANTI join removal code
> and left only support for LEFT JOIN removal of sub-queries that can be
> proved to be unique on the join condition by looking at the GROUP BY and
> DISTINCT clause.

Good advice, we can come back for the others later.


> Example:
>
> SELECT t1.* FROM t1 LEFT OUTER JOIN (SELECT value,COUNT(*) FROM t2 GROUP BY
> value) t2 ON t1.id = t2.value;

Looks good on initial look.

This gets optimized...

EXPLAIN (COSTS OFF)
SELECT a.id FROM a
LEFT JOIN (SELECT b.id,1 as dummy FROM b INNER JOIN c ON b.id = c.id
GROUP BY b.id) b ON a.id = b.id AND b.dummy = 1;

does it work with transitive closure like this..

EXPLAIN (COSTS OFF)
SELECT a.id FROM a
LEFT JOIN (SELECT b.id,1 as dummy FROM b INNER JOIN c ON b.id = c.id
GROUP BY c.id) b ON a.id = b.id AND b.dummy = 1;

i.e. c.id is not in the join, but we know from subselect that c.id =
b.id and b.id is in the join

-- Simon Riggs                   http://www.2ndQuadrant.com/PostgreSQL Development, 24x7 Support, Training & Services

On 22 June 2014 12:51, Simon Riggs <simon@2ndquadrant.com> wrote:

> Looks good on initial look.

Tests 2 and 3 seem to test the same thing.

There are no tests which have multiple column clauselist/sortlists,
nor tests for cases where the clauselist is a superset of the
sortlist.

Test comments should refer to "join removal" rather than
"optimization" because we may forget which optimization they are there
to test.

It's not clear to me where you get the term "sortclause" from. This is
either the groupclause or distinctclause, but in the test cases you
provide this shows this has nothing at all to do with sorting since
there is neither an order by or a sorted aggregate anywhere near those
queries. Can we think of a better name that won't confuse us in the
future?

The comment "Since a constant only has 1 value the existence of one here will
+ * not cause any duplication of the results. We'll simply ignore it!"
would be better as "We can ignore constants since they have only one
value and don't affect uniqueness of results".

The comment "XXX is this comment still true??" can be removed since
its just a discussion point.

The comment beginning "Currently, we only know how to remove left..."
has rewritten a whole block of text just to add a few words in the
middle. We should rewrite the comment so it changes as few lines as
possible. Especially when that comment is going to be changed again
with your later patches. Better to have it provide a bullet point list
of things we know how to remove, so we can just add to it later.

Still looks good, other than the above.

-- Simon Riggs                   http://www.2ndQuadrant.com/PostgreSQL Development, 24x7 Support, Training & Services

On 23 June 2014 12:06, David Rowley <dgrowley@gmail.com> wrote:

>> It's not clear to me where you get the term "sortclause" from. This is
>> either the groupclause or distinctclause, but in the test cases you
>> provide this shows this has nothing at all to do with sorting since
>> there is neither an order by or a sorted aggregate anywhere near those
>> queries. Can we think of a better name that won't confuse us in the
>> future?
>>
>
> I probably got the word "sort" from the function targetIsInSortList, which
> expects a list of SortGroupClause. I've renamed the function to
> sortlist_is_unique_on_restrictinfo() and renamed the sortclause parameter to
> sortlist. Hopefully will reduce confusion about it being an ORDER BY clause
> a bit more. I think sortgroupclauselist might be just a bit too long. What
> do you think?

OK, perhaps I should be clearer. The word "sort" here seems completely
misplaced and we should be using a more accurately descriptive term.
It's slightly more than editing to rename things like that, so I'd
prefer you cam up with a better name.

Did you comment on the transitive closure question? Should we add a
test for that, whether or not it works yet?

Other than that it looks pretty good to commit, so I'll wait a week
for other objections then commit.

-- Simon Riggs                   http://www.2ndQuadrant.com/PostgreSQL Development, 24x7 Support, Training & Services

Simon Riggs <simon@2ndQuadrant.com> writes:
> Other than that it looks pretty good to commit, so I'll wait a week
> for other objections then commit.

I'd like to review this before it goes in.  I've been waiting for it to
get marked "ready for committer" though.
        regards, tom lane

On 24 June 2014 23:48, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Simon Riggs <simon@2ndQuadrant.com> writes:
>> Other than that it looks pretty good to commit, so I'll wait a week
>> for other objections then commit.
>
> I'd like to review this before it goes in.  I've been waiting for it to
> get marked "ready for committer" though.

I'll leave it for you then once I'm happy.

-- Simon Riggs                   http://www.2ndQuadrant.com/PostgreSQL Development, 24x7 Support, Training & Services

On 26 June 2014 10:01, David Rowley <dgrowleyml@gmail.com> wrote:

>> Did you comment on the transitive closure question? Should we add a
>> test for that, whether or not it works yet?
>>
>
> In my previous email.
>
> I could change the the following to use c.id in the targetlist and group by
> clause, but I'm not really sure it's testing anything new or different.
>
> EXPLAIN (COSTS OFF)
> SELECT a.id FROM a
> LEFT JOIN (SELECT b.id,1 as dummy FROM b INNER JOIN c ON b.id = c.id GROUP
> BY b.id) b ON a.id = b.id AND b.dummy = 1;

OK, agreed, no need to include.

-- Simon Riggs                   http://www.2ndQuadrant.com/PostgreSQL Development, 24x7 Support, Training & Services

David Rowley <dgrowleyml@gmail.com> writes:
> Attached is a delta patch between version 1.2 and 1.3, and also a
> completely updated patch.

Just to note that I've started looking at this, and I've detected a rather
significant omission: there's no check that the join operator has anything
to do with the subquery's grouping operator.  I think we need to verify
that they are members of the same opclass, as
relation_has_unique_index_for does.
        regards, tom lane

David Rowley <dgrowley@gmail.com> writes:
> On 6 July 2014 03:20, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> Just to note that I've started looking at this, and I've detected a rather
>> significant omission: there's no check that the join operator has anything
>> to do with the subquery's grouping operator.

> hmm, good point. If I understand this correctly we can just ensure that the
> same operator is used for both the grouping and the join condition.

Well, that's sort of the zero-order solution, but it doesn't work if the
join operators are cross-type.

I poked around to see if we didn't have some code already for that, and
soon found that not only do we have such code (equality_ops_are_compatible)
but actually almost this entire patch duplicates logic that already exists
in optimizer/util/pathnode.c, to wit create_unique_path's subroutines
query_is_distinct_for et al.  So I'm thinking what this needs to turn into
is an exercise in refactoring to allow that logic to be used for both
purposes.

I notice that create_unique_path is not paying attention to the question
of whether the subselect's tlist contains SRFs or volatile functions.
It's possible that that's a pre-existing bug.
        regards, tom lane

David Rowley <dgrowleyml@gmail.com> writes:
> On Mon, Jul 7, 2014 at 4:15 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> I poked around to see if we didn't have some code already for that, and
>> soon found that not only do we have such code (equality_ops_are_compatible)
>> but actually almost this entire patch duplicates logic that already exists
>> in optimizer/util/pathnode.c, to wit create_unique_path's subroutines
>> query_is_distinct_for et al.  So I'm thinking what this needs to turn into
>> is an exercise in refactoring to allow that logic to be used for both
>> purposes.

> Well, it seems that might just reduce the patch size a little!
> I currently have this half hacked up to use query_is_distinct_for, but I
> see there's no code that allows Const's to exist in the join condition. I
> had allowed for this in groupinglist_is_unique_on_restrictinfo() and I
> tested it worked in a regression test (which now fails). I think to fix
> this, all it would take would be to modify query_is_distinct_for to take a
> list of Node's rather than a list of column numbers then just add some
> logic that skips if it's a Const and checks it as it does now if it's a Var
> Would you see a change of this kind a valid refactor for this patch?

I'm a bit skeptical as to whether testing for that case is actually worth
any extra complexity.  Do you have a compelling use-case?  But anyway,
if we do want to allow it, why does it take any more than adding a check
for Consts to the loops in query_is_distinct_for?  It's the targetlist
entries where we'd want to allow Consts, not the join conditions.
        regards, tom lane

David Rowley <dgrowleyml@gmail.com> writes:
> On Tue, Jul 8, 2014 at 4:28 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> I'm a bit skeptical as to whether testing for that case is actually worth
>> any extra complexity.  Do you have a compelling use-case?  But anyway,
>> if we do want to allow it, why does it take any more than adding a check
>> for Consts to the loops in query_is_distinct_for?  It's the targetlist
>> entries where we'd want to allow Consts, not the join conditions.

> I don't really have a compelling use-case, but you're right, it's just a
> Const check in query_is_distinct_for(), it seems simple enough so I've
> included that in my refactor of the patch to use query_is_distinct_for().
> This allows the regression tests all to pass again.

Meh.  "I wrote a regression test that expects it" is a pretty poor
rationale for adding logic.  If you can't point to a real-world case
where this is important, I'm inclined to take it out.

If we were actually serious about exploiting such cases, looking for
bare Consts would be a poor implementation anyhow, not least because
const-folding has not yet been applied to the sub-select.  I think we'd
want to do it for any pseudoconstant expression (no Vars, no volatile
functions); which is a substantially more expensive test.

> 1. The fast path code that exited in join_is_removable() for subquery's
> when the subquery had no group or distinct clause is now gone. I wasn't too
> sure that I wanted to assume too much about what query_is_distinct_for may
> do in the future and I thought if I included some logic in
> join_is_removable() to fast path, that one day it may fast path wrongly.

Or put a quick-check subroutine next to query_is_distinct_for().  The code
we're skipping here is not so cheap that I want to blow off skipping it.
On review it looks like analyzejoins.c would possibly benefit from an
earlier fast-path check as well.

> 2. The patch I submitted here
> http://www.postgresql.org/message-id/CAApHDvrfVkH0P3FAooGcckBy7feCJ9QFanKLkX7MWsBcxY2Vcg@mail.gmail.com
> if that gets accepted then it makes the check for set returning functions
> in join_is_removable void.

Right (and done, if you didn't notice already).

TBH I find the checks for FOR UPDATE and volatile functions to be
questionable as well.  We have never considered those things to prevent
pushdown of quals into a subquery (cf subquery_is_pushdown_safe).  I think
what we're talking about here is pretty much equivalent to pushing an
always-false qual into the subquery; if people haven't complained about
that, why should they complain about this?  Or to put it in slightly more
principled terms, we've attempted to prevent subquery optimization from
causing volatile expressions to be evaluated *more* times than the naive
reading of the query would suggest, but we have generally not felt that
we needed to prevent them from happening *fewer* times.
        regards, tom lane

David Rowley <dgrowley@gmail.com> writes:
> On 9 July 2014 09:27, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> On review it looks like analyzejoins.c would possibly benefit from an
>> earlier fast-path check as well.

> Do you mean for non-subqueries? There already is a check to see if the
> relation has no indexes.

Oh, sorry, that was a typo: I meant to write pathnode.c.  Specifically,
we could skip the translate_sub_tlist step.  Admittedly that's not
hugely expensive, but as long as we have the infrastructure for a quick
check it might be worth doing.


>> TBH I find the checks for FOR UPDATE and volatile functions to be
>> questionable as well.

> Well, that's a real tough one for me as I only added that based on what you
> told me here:
>> I doubt you should drop a subquery containing FOR UPDATE, either.
>> That's a side effect, just as much as a volatile function would be.

Hah ;-).  But the analogy to qual pushdown hadn't occurred to me at the
time.

> As far as I know the FOR UPDATE check is pretty much void as of now anyway,
> since the current state of query_is_distinct_for() demands that there's
> either a DISTINCT, GROUP BY or just a plain old aggregate without any
> grouping, which will just return a single row, neither of these will allow
> FOR UPDATE anyway.

True.

> So the effort here should be probably be more focused on if we should allow
> the join removal when the subquery contains volatile functions. We should
> probably think fairly hard on this now as I'm still planning on working on
> INNER JOIN removals at some point and I'm thinking we should likely be
> consistent between the 2 types of join for when it comes to FOR UPDATE and
> volatile functions, and I'm thinking right now that for INNER JOINs that,
> since they're INNER that we could remove either side of the join. In that
> case maybe it would be harder for the user to understand why their volatile
> function didn't get executed.

Color me dubious.  In exactly what circumstances would it be valid to
suppress an inner join involving a sub-select?
        regards, tom lane

David Rowley <dgrowleyml@gmail.com> writes:
> I've attached an updated patch which puts in some fast path code for
> subquery type joins. I'm really not too sure on a good name for this
> function. I've ended up with query_supports_distinctness() which I'm not
> that keen on, but I didn't manage to come up with anything better.

I've committed this with some mostly but not entirely cosmetic changes.
Notably, I felt that pathnode.c was a pretty questionable place to be
exporting distinctness-proof logic from, and after some reflection decided
to move those functions to analyzejoins.c; that's certainly a better place
for them than pathnode.c, and I don't see any superior third alternative.
        regards, tom lane

David Rowley <dgrowleyml@gmail.com> writes:
> On Wed, Jul 16, 2014 at 1:17 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> Notably, I felt that pathnode.c was a pretty questionable place to be
>> exporting distinctness-proof logic from, and after some reflection decided
>> to move those functions to analyzejoins.c; that's certainly a better place
>> for them than pathnode.c, and I don't see any superior third alternative.

> That seems like a good change. Also makes be wonder a bit
> why clause_sides_match_join is duplicated in joinpath.c and analyzejoins.c,
> is this just so that it can be inlined?

Hm ... probably just didn't seem worth the trouble to try to share the
code.  It's not really something that either module should be exporting.
I guess some case could be made for exporting it from util/restrictinfo.c,
but it'd still seem like a bit of a wart.
        regards, tom lane