Thread: Patch to support SEMI and ANTI join removal

On 08/26/2014 03:28 PM, David Rowley wrote:
> Any ideas or feedback on this would be welcome

Before someone spends time reviewing this patch, are you sure this is 
worth the effort? It seems like very narrow use case to me. I understand 
removing LEFT and INNER joins, but the case for SEMI and ANTI joins 
seems a lot thinner. Unnecessary LEFT and INNER joins can easily creep 
into a query when views are used, for example, but I can't imagine that 
happening for a SEMI or ANTI join. Maybe I'm lacking imagination. If 
someone has run into a query in the wild that would benefit from this, 
please raise your hand.

If I understood correctly, you're planning to work on INNER join removal 
too. How much of the code in this patch is also required for INNER join 
removal, and how much is specific to SEMI and ANTI joins?

Just so everyone is on the same page on what kind of queries this helps 
with, here are some examples from the added regression tests:

> -- Test join removals for semi and anti joins
> CREATE TEMP TABLE b (id INT NOT NULL PRIMARY KEY, val INT);
> CREATE TEMP TABLE a (id INT NOT NULL PRIMARY KEY, b_id INT REFERENCES b(id));
> -- should remove semi join to b
> EXPLAIN (COSTS OFF)
> SELECT id FROM a WHERE b_id IN(SELECT id FROM b);
>           QUERY PLAN
> ------------------------------
>  Seq Scan on a
>    Filter: (b_id IS NOT NULL)
> (2 rows)
>
> -- should remove semi join to b
> EXPLAIN (COSTS OFF)
> SELECT id FROM a WHERE EXISTS(SELECT 1 FROM b WHERE a.b_id = id);
>           QUERY PLAN
> ------------------------------
>  Seq Scan on a
>    Filter: (b_id IS NOT NULL)
> (2 rows)
>
> -- should remove anti join to b
> EXPLAIN (COSTS OFF)
> SELECT id FROM a WHERE NOT EXISTS(SELECT 1 FROM b WHERE a.b_id = id);
>         QUERY PLAN
> --------------------------
>  Seq Scan on a
>    Filter: (b_id IS NULL)
> (2 rows)

- Heikki

On 8/26/14, 8:40 AM, Heikki Linnakangas wrote:
> Just so everyone is on the same page on what kind of queries this helps with, here are some examples from the added
regressiontests:
 
>
>> -- Test join removals for semi and anti joins
>> CREATE TEMP TABLE b (id INT NOT NULL PRIMARY KEY, val INT);
>> CREATE TEMP TABLE a (id INT NOT NULL PRIMARY KEY, b_id INT REFERENCES b(id));
>> -- should remove semi join to b
>> EXPLAIN (COSTS OFF)
>> SELECT id FROM a WHERE b_id IN(SELECT id FROM b);
<snip>
>> SELECT id FROM a WHERE EXISTS(SELECT 1 FROM b WHERE a.b_id = id);

I also fail to see a use for examples that are that silly *unless* we're talking machine-generated SQL, but I suspect
thatnormally uses JOINS.
 

Where I would expect this to be useful is in cases where we can pre-evaluate some other condition in the subqueries to
makethe subqueries useless (ie: SELECT id FROM b WHERE 1=1), or where the condition could be passed through (ie: SELECT
idFROM b WHERE id=42). Another possibility would be if there's a condition in the subquery that could trigger
constraintelimination.
 

Those are the real world cases I'd expect to see from anything reasonably sane (an adjective that doesn't always apply
tosome of the users I have to support...) My $0.01 on the burden of carrying the "useless" tests and code around is
thatit doesn't seem like all that much overhead...
 
-- 
Jim C. Nasby, Data Architect                       jim@nasby.net
512.569.9461 (cell)                         http://jim.nasby.net

Jim Nasby <jim@nasby.net> writes:
> On 8/26/14, 8:40 AM, Heikki Linnakangas wrote:
>> Just so everyone is on the same page on what kind of queries this helps with, here are some examples from the added
regressiontests:
 
>> 
> -- Test join removals for semi and anti joins
> CREATE TEMP TABLE b (id INT NOT NULL PRIMARY KEY, val INT);
> CREATE TEMP TABLE a (id INT NOT NULL PRIMARY KEY, b_id INT REFERENCES b(id));
> -- should remove semi join to b
> EXPLAIN (COSTS OFF)
> SELECT id FROM a WHERE b_id IN(SELECT id FROM b);
> <snip>
> SELECT id FROM a WHERE EXISTS(SELECT 1 FROM b WHERE a.b_id = id);

> I also fail to see a use for examples that are that silly *unless* we're talking machine-generated SQL, but I suspect
thatnormally uses JOINS.
 

> Where I would expect this to be useful is in cases where we can pre-evaluate some other condition in the subqueries
tomake the subqueries useless (ie: SELECT id FROM b WHERE 1=1), or where the condition could be passed through (ie:
SELECTid FROM b WHERE id=42). Another possibility would be if there's a condition in the subquery that could trigger
constraintelimination.
 

Unless I'm misunderstanding something, pretty much *any* WHERE restriction
in the subquery would defeat this optimization, since it would no longer
be certain that there was a match to an arbitrary outer-query row.  So
it seems unlikely to me that this would fire in enough real-world cases
to be worth including.  I am definitely not a fan of carrying around
deadwood in the planner.

If the majority of the added code is code that will be needed for
less-bogus optimizations, it might be all right; but I'd kind of want to
see the less-bogus optimizations working first.
        regards, tom lane

On Thu, Sep 11, 2014 at 7:14 AM, David Rowley <dgrowleyml@gmail.com> wrote:
> Here's a quick demo, of the patch at work:
>
> test=# create table c (id int primary key);
> CREATE TABLE
> test=# create table b (id int primary key, c_id int not null references
> c(id));
> CREATE TABLE
> test=# create table a (id int primary key, b_id int not null references
> b(id));
> CREATE TABLE
> test=#
> test=# explain select a.* from a inner join b on a.b_id = b.id inner join c
> on b.c_id = c.id;
>                      QUERY PLAN
> -----------------------------------------------------
>  Seq Scan on a  (cost=0.00..31.40 rows=2140 width=8)
>  Planning time: 1.061 ms
> (2 rows)

That is just awesome.  You are my new hero.

> 1. I don't think that I'm currently handling removing eclass members
> properly. So far the code just removes the Vars that belong to the relation
> being removed. I likely should also be doing bms_del_member(ec->ec_relids,
> relid); on the eclass, but perhaps I should just be marking the whole class
> as "ec_broken = true" and adding another eclass all everything that the
> broken one has minus the parts from the removed relation?

I haven't read the patch, but I think the question is why this needs
to be different than what we do for left join removal.

> Assume there's a foreign key a (x) reference b(x)
>
> SELECT a.* FROM a INNER JOIN b ON a.x = b.x WHERE b.x = 1
>
> relation b should be removable because an eclass will contain {a.x, b.x} and
> therefore s baserestrictinfo for a.x = 1 should also exist on relation a.
> Therefore removing relation b should produce equivalent results, i.e
> everything that gets filtered out on relation b will also be filtered out on
> relation a anyway.
>
> I think the patch without this is still worth it, but if someone feels
> strongly about it I'll take a bash at supporting it.

That'd be nice to fix, but IMHO not essential.

> 3. Currently the inner join support does not allow removals using foreign
> keys which contain duplicate columns on the referencing side. e.g (a,a)
> references (x,y), this is basically because of the point I made in item 2.
> In this case a baserestrictinfo would exist on the referenced relation to
> say WHERE x = y.

I think it's fine to not bother with this case.  Who cares?

> 4. The patch currently only allows removals for eclass join types. If the
> rel has any joininfo items, then the join removal is disallowed. From what I
> can see equality type inner join conditions get described in eclasses, and
> only non-equality join conditions make it into the joininfo list, and since
> foreign keys only support equality operators, then I thought this was a
> valid restriction, however, if someone can show me a flaw in my assumption
> then I may need to improve this.

Seems OK.

> 5. I've added a flag to pg_class called relhasfkey. Currently this gets set
> to true when a foreign key is added, though I've added nothing to set it
> back to false again. I notice that relhasindex gets set back to false during
> vacuum, if vacuum happens to find there to not be any indexes on the rel. I
> didn't put my logic here as I wasn't too sure if scanning pg_constraint
> during a vacuum seemed very correct, so I just left out the "setting it to
> false" logic based on the the fact that I noticed that relhaspkey gets away
> with quite lazy setting back to false logic (only when there's no indexes of
> any kind left on the relation at all).

The alternative to resetting the flag somehow is not having it in the
first place.  Would that be terribly expensive?

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

Robert Haas <robertmhaas@gmail.com> writes:
> On Thu, Sep 11, 2014 at 7:14 AM, David Rowley <dgrowleyml@gmail.com> wrote:
>> 5. I've added a flag to pg_class called relhasfkey. Currently this gets set
>> to true when a foreign key is added, though I've added nothing to set it
>> back to false again. I notice that relhasindex gets set back to false during
>> vacuum, if vacuum happens to find there to not be any indexes on the rel. I
>> didn't put my logic here as I wasn't too sure if scanning pg_constraint
>> during a vacuum seemed very correct, so I just left out the "setting it to
>> false" logic based on the the fact that I noticed that relhaspkey gets away
>> with quite lazy setting back to false logic (only when there's no indexes of
>> any kind left on the relation at all).

> The alternative to resetting the flag somehow is not having it in the
> first place.  Would that be terribly expensive?

The behavior of relhaspkey is a legacy thing that we've tolerated only
because nothing whatsoever in the backend depends on it at all.  I'm not
eager to add more equally-ill-defined pg_class columns.
        regards, tom lane

David Rowley <dgrowleyml@gmail.com> writes:
> On Fri, Sep 12, 2014 at 3:35 AM, Robert Haas <robertmhaas@gmail.com> wrote:
>> I haven't read the patch, but I think the question is why this needs
>> to be different than what we do for left join removal.

> I discovered over here ->
> http://www.postgresql.org/message-id/CAApHDvo5wCRk7uHBuMHJaDpbW-b_oGKQOuisCZzHC25=H3__fA@mail.gmail.com
> during the early days of the semi and anti join removal code that the
> planner was trying to generate paths to the dead rel. I managed to track
> the problem down to eclass members still existing for the dead rel. I guess
> we must not have eclass members for outer rels? or we'd likely have seen
> some troubles with left join removals already.

Mere existence of an eclass entry ought not cause paths to get built.
It'd be worth looking a bit harder into what's happening there.
        regards, tom lane

On 09/16/2014 01:20 PM, David Rowley wrote:
> +    /*
> +     * We mustn't allow any joins to be removed if there are any pending
> +     * foreign key triggers in the queue. This could happen if we are planning
> +     * a query that has been executed from within a volatile function and the
> +     * query which called this volatile function has made some changes to a
> +     * table referenced by a foreign key. The reason for this is that any
> +     * updates to a table which is referenced by a foreign key constraint will
> +     * only have the referencing tables updated after the command is complete,
> +     * so there is a window of time where records may violate the foreign key
> +     * constraint.
> +     *
> +     * Currently this code is quite naive, as we won't even attempt to remove
> +     * the join if there are *any* pending foreign key triggers, on any
> +     * relation. It may be worthwhile to improve this to check if there's any
> +     * pending triggers for the referencing relation in the join.
> +     */
> +    if (!AfterTriggerQueueIsEmpty())
> +        return false;

Hmm. This code runs when the query is planned. There is no guarantee 
that there won't be after triggers pending when the query is later 
*executed*.

- Heikki

On 2014-09-28 17:32:21 +1300, David Rowley wrote:
> My understanding of foreign keys is that any pending foreign key triggers
> will be executed just before the query completes, so we should only ever
> encounter pending foreign key triggers during planning when we're planning
> a query that's being executed from somewhere like a volatile function or
> trigger function, if the outer query has updated or deleted some records
> which are referenced by a foreign key.

Note that foreign key checks also can be deferred. So the window for
these cases is actually larger.

> So I think with the check for pending triggers at planning time this is
> safe at least for queries being planned right before they're executed, but
> you've caused me to realise that I'll probably need to do some more work on
> this for when it comes to PREPARE'd queries, as it looks like if we
> executed a prepared query from inside a volatile function or trigger
> function that was called from a DELETE or UPDATE statement that caused
> foreign key triggers to be queued, and we'd happened to have removed some
> INNER JOINs when we originally planned that prepare statement, then that
> would be wrong.

I'm wondering whether this wouldn't actually be better handled by some
sort of 'one time filter' capability for joins. When noticing during
planning that one side of the join is nullable attach a check to the
join node. Then, whenever that check returns true, skip checking one
side of the join and return rows without looking at that side.

That capability might also be interesting for more efficient planning of
left joins that partially have a constant join expression.

Greetings,

Andres Freund

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

David Rowley <dgrowleyml@gmail.com> writes:
> Please correct anything that sounds wrong here, but my understanding is
> that we'll always plan a query right before we execute it, with the
> exception of PREPARE statements where PostgreSQL will cache the query plan
> when the prepare statement is first executed.

If this optimization only works in that scenario, it's dead in the water,
because that assumption is unsupportable.  The planner does not in general
use the same query snapshot as the executor, so even in an immediate-
execution workflow there could have been data changes (caused by other
transactions) between planning and execution.

Why do you need such an assumption?
        regards, tom lane

On 2014-09-28 10:41:56 -0400, Tom Lane wrote:
> David Rowley <dgrowleyml@gmail.com> writes:
> > Please correct anything that sounds wrong here, but my understanding is
> > that we'll always plan a query right before we execute it, with the
> > exception of PREPARE statements where PostgreSQL will cache the query plan
> > when the prepare statement is first executed.
> 
> If this optimization only works in that scenario, it's dead in the water,
> because that assumption is unsupportable.  The planner does not in general
> use the same query snapshot as the executor, so even in an immediate-
> execution workflow there could have been data changes (caused by other
> transactions) between planning and execution.

I don't think the effects of other queries are the problem here. The
effect of other backend's deferred FK checks shouldn't matter for other
backends for normal query purposes. It's the planning backend that might
have deferred checks and thus temporarily violated foreign keys.

Greetings,

Andres Freund

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

On 2014-09-29 22:42:57 +1300, David Rowley wrote:
> On Mon, Sep 29, 2014 at 2:41 AM, Andres Freund <andres@2ndquadrant.com>
> wrote:
> 
> > On 2014-09-28 17:32:21 +1300, David Rowley wrote:
> > > My understanding of foreign keys is that any pending foreign key triggers
> > > will be executed just before the query completes, so we should only ever
> > > encounter pending foreign key triggers during planning when we're
> > planning
> > > a query that's being executed from somewhere like a volatile function or
> > > trigger function, if the outer query has updated or deleted some records
> > > which are referenced by a foreign key.
> >
> > Note that foreign key checks also can be deferred. So the window for
> > these cases is actually larger.
> >
> >
> Thanks Andres, I know you had said this before but I had previously failed
> to realise exactly what you meant. I thought you were talking about
> defining a foreign key to reference a column that has a deferrable unique
> index. I now realise you were talking about making the foreign key itself
> as deferrable.

Oh. Don't remember doing that ;)

> I've made a change to the patch locally to ignore foreign
> keys that are marked as deferrable.

I have serious doubts about the general usefulness if this is onlyu
going to be useable in a very restricted set of circumstances (only one
time plans, no deferrable keys). I think it'd be awesome to have the
capability, but I don't think it's ok to restrict it that much.

To me that means you can't make the decision at plan time, but need to
move it to execution time. It really doesn't sound that hard to short
circuit the semi joins whenever, at execution time, there's no entries
in the deferred trigger queue. It's a bit annoying to have to add code
to all of nestloop/hashjoin/mergejoin to not check the outer tuple if
there's no such entry. But I don't think it'll be too bad. That'd mean
it can be used in prepared statements.

What I think would be a bit finnicky is the costing...

Greetings,

Andres Freund

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

Andres Freund <andres@2ndquadrant.com> writes:
> On 2014-09-28 10:41:56 -0400, Tom Lane wrote:
>> If this optimization only works in that scenario, it's dead in the water,
>> because that assumption is unsupportable.  The planner does not in general
>> use the same query snapshot as the executor, so even in an immediate-
>> execution workflow there could have been data changes (caused by other
>> transactions) between planning and execution.

> I don't think the effects of other queries are the problem here. The
> effect of other backend's deferred FK checks shouldn't matter for other
> backends for normal query purposes. It's the planning backend that might
> have deferred checks and thus temporarily violated foreign keys.

I see.  So why aren't we simply ignoring deferrable FKs when making the
optimization?  That pushes it back from depending on execution-time state
(unsafe) to depending on table DDL (safe).
        regards, tom lane

On 2014-09-29 10:12:25 -0400, Tom Lane wrote:
> Andres Freund <andres@2ndquadrant.com> writes:
> > On 2014-09-28 10:41:56 -0400, Tom Lane wrote:
> >> If this optimization only works in that scenario, it's dead in the water,
> >> because that assumption is unsupportable.  The planner does not in general
> >> use the same query snapshot as the executor, so even in an immediate-
> >> execution workflow there could have been data changes (caused by other
> >> transactions) between planning and execution.
> 
> > I don't think the effects of other queries are the problem here. The
> > effect of other backend's deferred FK checks shouldn't matter for other
> > backends for normal query purposes. It's the planning backend that might
> > have deferred checks and thus temporarily violated foreign keys.
> 
> I see.  So why aren't we simply ignoring deferrable FKs when making the
> optimization?  That pushes it back from depending on execution-time state
> (unsafe) to depending on table DDL (safe).

IIRC there's some scenarios where violated FKs are visible to client
code for nondeferrable ones as well. Consider e.g. cascading foreign
keys + triggers. Or, somewhat insane, operators used in fkey triggers
that execute queries themselves.

Greetings,

Andres Freund

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

Andres Freund <andres@2ndquadrant.com> writes:
> On 2014-09-29 10:12:25 -0400, Tom Lane wrote:
>> I see.  So why aren't we simply ignoring deferrable FKs when making the
>> optimization?  That pushes it back from depending on execution-time state
>> (unsafe) to depending on table DDL (safe).

> IIRC there's some scenarios where violated FKs are visible to client
> code for nondeferrable ones as well. Consider e.g. cascading foreign
> keys + triggers. Or, somewhat insane, operators used in fkey triggers
> that execute queries themselves.

Yeah, I had just thought of the query-in-function-called-from-violating-
query case myself.  I plead insufficient caffeine :-(.  I'd been making
a mental analogy to non-deferred uniqueness constraints, but actually
what we will optimize outer joins on is "immediate" unique indexes,
wherein there's no delay at all before the constraint is checked.
Too bad there's no equivalent in foreign key land.

These are certainly corner cases, but it doesn't seem up to project
quality standards to just ignore them.  So I'm thinking you're right
that a run-time short-circuit would be the only way to deal with the
case safely.

On the whole I'm feeling that the scope of applicability of this
optimization is going to be too narrow to justify the maintenance
effort and extra planning/runtime overhead.
        regards, tom lane

On 2014-09-30 23:25:45 +1300, David Rowley wrote:
> On Tue, Sep 30, 2014 at 12:42 AM, Andres Freund <andres@2ndquadrant.com>
> wrote:
> 
> > On 2014-09-29 22:42:57 +1300, David Rowley wrote:
> >
> > > I've made a change to the patch locally to ignore foreign
> > > keys that are marked as deferrable.
> >
> > I have serious doubts about the general usefulness if this is onlyu
> > going to be useable in a very restricted set of circumstances (only one
> > time plans, no deferrable keys). I think it'd be awesome to have the
> > capability, but I don't think it's ok to restrict it that much.
> >
> >
> I had a look to see what Oracle does in this situation and I was quite
> shocked to see that they're blatantly just ignoring the fact that the
> foreign key is being deferred. I tested by deferring the foreign key in a
> transaction then updating the referenced record and I see that Oracle just
> return the wrong results as they're just blindly removing the join. So it
> appears that they've not solved this one very well.

Ick. I'm pretty strongly against going that way.

> > To me that means you can't make the decision at plan time, but need to
> > move it to execution time. It really doesn't sound that hard to short
> > circuit the semi joins whenever, at execution time, there's no entries
> > in the deferred trigger queue. It's a bit annoying to have to add code
> > to all of nestloop/hashjoin/mergejoin to not check the outer tuple if
> > there's no such entry. But I don't think it'll be too bad. That'd mean
> > it can be used in prepared statements.
> >
> >
> I'm starting to think about how this might be done, but I'm a bit confused
> and I don't know if it's something you've overlooked or something I've
> misunderstood.
> 
> I've not quite gotten my head around how we might stop the unneeded
> relation from being the primary path to join the other inner relations,
> i.e. what would stop the planner making a plan that hashed all the other
> relations and planned to perform a sequence scan on the relation that we
> have no need to scan (because the foreign key tells us the join is
> pointless). If we were not use use that relation then we'd just have a
> bunch of hash tables with no path to join them up. If we did anything to
> force the planner into creating a plan that would suit skipping relations,
> then we could possibly be throwing away the optimal plan..... Right?

I'm not 100% sure I understand your problem description, but let me
describe how I think this would work. During planning, you'd emit the
exactly same plan as you'd today, with two exceptions:
a) When costing a node where one side of a join is very likely to be  removable, you'd cost it nearly as if there
wasn'ta join.
 
b) The planner would attach some sort of 'one time join qual' to the  'likely removable' join nodes. If, during
executorinit, that qual  returns false, simply don't perform the join. Just check the inner  relation, but entirely
skipthe outer relation.
 

With regard to your comment hash tables that aren't joined up: Currently
hash tables aren't built if they're not used. I.e. it's not
ExecInitHash() that does the hashing, but they're generally only built
when needed. E.g. nodeHashJoin.c:ExecHashJoin() only calls
MultiExecProcNode() when in the HJ_BUILD_HASHTABLE state - which it only
initially and sometimes after rescans is.

Does that clear things up or have I completely missed your angle?

Greetings,

Andres Freund

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

On 2014-10-01 01:03:35 +1300, David Rowley wrote:
> On Wed, Oct 1, 2014 at 12:01 AM, Andres Freund <andres@2ndquadrant.com>
> wrote:
> 
> > On 2014-09-30 23:25:45 +1300, David Rowley wrote:
> > >
> > > I've not quite gotten my head around how we might stop the unneeded
> > > relation from being the primary path to join the other inner relations,
> > > i.e. what would stop the planner making a plan that hashed all the other
> > > relations and planned to perform a sequence scan on the relation that we
> > > have no need to scan (because the foreign key tells us the join is
> > > pointless). If we were not use use that relation then we'd just have a
> > > bunch of hash tables with no path to join them up. If we did anything to
> > > force the planner into creating a plan that would suit skipping
> > relations,
> > > then we could possibly be throwing away the optimal plan..... Right?
> >
> > I'm not 100% sure I understand your problem description, but let me
> > describe how I think this would work. During planning, you'd emit the
> > exactly same plan as you'd today, with two exceptions:
> > a) When costing a node where one side of a join is very likely to be
> >    removable, you'd cost it nearly as if there wasn't a join.
> >
> 
> Ok given the tables:
> create table t1 (x int primary key);
> create table t2 (y int primary key);
> 
> suppose the planner came up with something like:
> 
> test=# explain (costs off) select t2.* from t1 inner join t2 on t1.x=t2.y;
>          QUERY PLAN
> ----------------------------
>  Hash Join
>    Hash Cond: (t1.x = t2.y)
>    ->  Seq Scan on t1
>    ->  Hash
>          ->  Seq Scan on t2
> 
> If we had a foreign key...
> 
> alter table t2 add constraint t2_y_fkey foreign key (y) references t1 (x);
> 
> ...the join to t1 could possibly be "ignored" by the executor... but
> there's a problem as the plan states we're going to seqscan then hash that
> relation, then seqscan t1 with a hash lookup on each of t1's rows. In this
> case how would the executor skip the scan on t1? I can see how this might
> work if it was t2 that we were removing, as we'd just skip the hash lookup
> part in the hash join node.

Hm, right. But that doesn't seem like a fatal problem to me. The planner
knows about t1/t2 and Seq(t1), Seq(t2), not just Hash(Seq(t2)). So it
can tell the HashJoin node that when the 'shortcut' qualifier is true,
it should source everything from Seq(t2). Since the sequence scan
doesn't care about the node ontop that doesn't seem to be overly
dramatic?
Obviously reality makes this a bit more complicated...

Greetings,

Andres Freund

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

On Mon, Oct 6, 2014 at 5:57 AM, David Rowley <dgrowleyml@gmail.com> wrote:
>> Hm, right. But that doesn't seem like a fatal problem to me. The planner
>> knows about t1/t2 and Seq(t1), Seq(t2), not just Hash(Seq(t2)). So it
>> can tell the HashJoin node that when the 'shortcut' qualifier is true,
>> it should source everything from Seq(t2). Since the sequence scan
>> doesn't care about the node ontop that doesn't seem to be overly
>> dramatic?
>> Obviously reality makes this a bit more complicated...
>>
> Ok, after a bit of study on the hash join code I can see what you mean, it
> shouldn't really matter.
> I've started working on this now and I've made some changes in
> analyzejoins.c so that instead of removing joins, it just marks the
> RangeTblEntry, setting a new flag named skipJoinPossible to true. (I'll
> think of a better name later)
>
> I'm starting off with hash joins and I'm hacking a bit at ExecInitHashJoin.
> I want to add 2 bool flags to HashJoinState, outerIsRequired and
> innerIsRequired. I think if both of these flags are set then we can just
> abort the join altogether. Though in order to set these flags I need to
> identify which relations are for the outer and which are for the inner side
> of the join. I've got the logic for that only partially worked out. My
> understanding of it so far is that I just need to look at the
> hjstate->js.ps.lefttree and righttree. Inner being right, and outer being
> left. I'm a little stuck on more complex cases where the scan is nested
> deeper in the tree and I'm not quite sure on the logic I should be using to
> navigate to it.
>
> Take the following plan: (which I've amended to mark the left and right
> nodes)
>
> explain select t1.* from t1 inner join t2 on t1.t2_id= t2.id inner join t3
> on t2.t3_id=t3.id;
>                                QUERY PLAN
> ------------------------------------------------------------------------
>  Hash Join  (cost=122.15..212.40 rows=2140 width=8)
>    Hash Cond: (t2.t3_id = t3.id)
>    ->  Hash Join  (cost=58.15..118.98 rows=2140 width=12) (left node)
>          Hash Cond: (t1.t2_id = t2.id)
>          ->  Seq Scan on t1  (cost=0.00..31.40 rows=2140 width=8) (left
> node)
>          ->  Hash  (cost=31.40..31.40 rows=2140 width=8) (right node)
>                ->  Seq Scan on t2  (cost=0.00..31.40 rows=2140 width=8)
> (left node)
>    ->  Hash  (cost=34.00..34.00 rows=2400 width=4) (right node)
>          ->  Seq Scan on t3  (cost=0.00..34.00 rows=2400 width=4) (left
> node)
>
> The schema is set up in such a way that the joins to t2 and t3 can be...
> "skipped", and my new code in analyzejoin.c marks the RangeTblEntry records
> for this relation to reflect that.
>
> During ExecInitHashJoin for the join between t2 and t3, if I want to find t2
> in the tree, I'd need to do hjstate->js.ps.lefttree->righttree->lefttree...
> (which I know just from looking at the explain output) I just can't work out
> the logic behind where the scan node will actually be. At first I had
> thought something like, loop down the lefttree path until I reach a deadend,
> and that's the outer scan node, but in this case there's a right turn in
> there too, so that won't work. If I keep going down the left path I'd end up
> at t1, which is completely wrong.
>
> Can anyone shed any light on how I might determine where the scan rel is in
> the tree? I need to find it so I can check if the RangeTblEntry is marked as
> skip-able.

I think you're probably going to need logic that knows about
particular node types and does the right thing for each one.  I think
- but maybe I'm misunderstanding - what you're looking for is a
function of the form Oid ScansOnePlainTableWithoutQuals().  The
algorithm could be something like:

switch (node type)
{   case T_SeqScanState:       if (no quals)           return the_appropriate_oid;       return false;   case
T_HashJoin:      decide whether we can ignore one side of the join       fish out the node from the other side of the
join(including
 
reaching through the Hash node if necessary)       return ScansOnePlainTableWithoutQuals(the node we fished out);
...otherspecific cases...   default:       return false;
 
}

This seems messy, though.  Can't the deferred trigger queue become
non-empty at pretty much any point in time?  At exactly what point are
we making this decision, and how do we know the correct answer can't
change after that point?

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

On 2014-10-06 10:46:09 -0400, Robert Haas wrote:
> This seems messy, though.  Can't the deferred trigger queue become
> non-empty at pretty much any point in time?  At exactly what point are
> we making this decision, and how do we know the correct answer can't
> change after that point?

What we've been talking about is doing this during executor startup. And
at that point we really don't care about new entries in the queue during
query execution - we can't see them anyway.

Greetings,

Andres Freund

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

On Mon, Oct 6, 2014 at 10:59 AM, Andres Freund <andres@2ndquadrant.com> wrote:
> On 2014-10-06 10:46:09 -0400, Robert Haas wrote:
>> This seems messy, though.  Can't the deferred trigger queue become
>> non-empty at pretty much any point in time?  At exactly what point are
>> we making this decision, and how do we know the correct answer can't
>> change after that point?
>
> What we've been talking about is doing this during executor startup. And
> at that point we really don't care about new entries in the queue during
> query execution - we can't see them anyway.

Ah, OK.

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

On 2014-10-09 00:21:44 +1300, David Rowley wrote:
> Ok, so I've been hacking away at this for a couple of evenings and I think
> I have a working prototype finally!

Cool!

> So it seems it's not quite as efficient as join removal at planning time,
> but still a big win when it's possible to perform the join skipping.

Have you checked where the overhead is? Is it really just the additional
node that the tuples are passed through?

Have you measured the overhead of the plan/execution time checks over
master?

> One thing that we've lost out of this execution time join removal checks
> method is the ability to still remove joins where the join column is
> NULLable. The previous patch added IS NOT NULL to ensure the query was
> equivalent when a join was removed, of course this meant that any
> subsequent joins may later not have been removed due to the IS NOT NULL
> quals existing (which could restrict the rows and remove the ability that
> the foreign key could guarantee the existence of exactly 1 row matching the
> join condition). I've not yet come up with a nice way to reimplement these
> null checks at execution time, so I've thought that perhaps I won't bother,
> at least not for this patch. I'd just disable join skipping at planning
> time if any of the join columns can have NULLs.

Sounds fair enough for the first round.

Greetings,

Andres Freund

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

On 15 October 2014 11:03, David Rowley <dgrowleyml@gmail.com> wrote:

> The explain analyze from the above query looks like:
> test=# explain (analyze, costs off, timing off) select count(*) from t1
> inner join t2 on t1.t2_id=t2.id;
>                             QUERY PLAN
> ------------------------------------------------------------------
>  Aggregate (actual rows=1 loops=1)
>    ->  Nested Loop (actual rows=1000000 loops=1)
>          ->  Seq Scan on t1 (actual rows=1000000 loops=1)
>          ->  Index Only Scan using t2_pkey on t2 (never executed)
>                Index Cond: (id = t1.t2_id)
>                Heap Fetches: 0
>  Execution time: 124.990 ms
> (7 rows)
>
> As you can see the scan on t2 never occurred.

Very good, happy to see this happening (yay FKs!) and with
PostgreSQL-style rigour.

I've reviewed the patch from cold and I have a few comments.

The plan you end up with here works quite differently from left outer
join removal, where the join is simply absent. That inconsistency
causes most of the other problems I see.

I propose that we keep track of whether there are any potentially
skippable joins at the top of the plan. When we begin execution we do
a single if test to see if there is run-time work to do. If we pass
the run-time tests we then descend the tree and prune the plan to
completely remove unnecessary nodes. We end with an EXPLAIN and
EXPLAIN ANALYZE that looks like this

>                             QUERY PLAN
> ------------------------------------------------------------------
>  Aggregate (actual rows=1 loops=1)
>          ->  Seq Scan on t1 (actual rows=1000000 loops=1)

Doing that removes all the overheads and complexity; it also matches
how join removal currently works.

The alternative is accepting some pretty horrible additional code in
most join types, plus a small regression on nested loop joins which I
would have to call out as regrettably unacceptable. (Horrible in this
sense that we don't want that code, not that David's code is poor).

The tests on the patch are pretty poor. If we should use EXPLAINs to
show a join removal that works and a join removal that fails. With a
few of the main permutations.

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

On 2/13/15 8:52 AM, Michael Paquier wrote:
> On Sun, Nov 23, 2014 at 8:23 PM, David Rowley <dgrowleyml@gmail.com> wrote:
>> As the patch stands there's still a couple of FIXMEs in there, so there's
>> still a bit of work to do yet.
>> Comments are welcome
>>
>
> Hm, if there is still work to do, we may as well mark this patch as
> rejected as-is, also because it stands in this state for a couple of months.

I didn't bring this up before, but I'm pretty sure this patch should be 
marked "returned with feedback".  From what I've understood, "rejected" 
means "we don't want this thing, not in this form or any other".  That 
doesn't seem to be the case for this patch, nor for a few others marked 
"rejected" in the currently in-progress commit fest.



.m

<div dir="ltr"><br /><div class="gmail_extra"><br /><div class="gmail_quote">On Fri, Feb 13, 2015 at 4:57 PM, Marko
Tiikkaja<span dir="ltr"><<a href="mailto:marko@joh.to" target="_blank">marko@joh.to</a>></span> wrote:<br
/><blockquoteclass="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex"><divclass=""><div class="h5">On 2/13/15 8:52 AM, Michael Paquier wrote:<br
/><blockquoteclass="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex">On Sun, Nov 23, 2014 at 8:23 PM, David Rowley <<a
href="mailto:dgrowleyml@gmail.com"target="_blank">dgrowleyml@gmail.com</a>> wrote:<br /><blockquote
class="gmail_quote"style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> As the
patchstands there's still a couple of FIXMEs in there, so there's<br /> still a bit of work to do yet.<br /> Comments
arewelcome<br /><br /></blockquote><br /> Hm, if there is still work to do, we may as well mark this patch as<br />
rejectedas-is, also because it stands in this state for a couple of months.<br /></blockquote><br /></div></div> I
didn'tbring this up before, but I'm pretty sure this patch should be marked "returned with feedback".  From what I've
understood,"rejected" means "we don't want this thing, not in this form or any other".  That doesn't seem to be the
casefor this patch, nor for a few others marked "rejected" in the currently in-progress commit fest.<span
class=""><fontcolor="#888888"><br /></font></span></blockquote></div><br /></div><div class="gmail_extra">In the new CF
app,marking a patch as "returned this feedback" adds it automatically to the next commit fest. And note that it is
actuallywhat I did for now to move on to the next CF in the doubt:<br /><a
href="https://commitfest.postgresql.org/3/27/">https://commitfest.postgresql.org/3/27/</a><br/></div><div
class="gmail_extra">Butif nothing is done, we should as well mark it as "rejected". Not based on the fact that it is
rejectedbased on its content, but to not bloat the CF app with entries that have no activity for months.<br clear="all"
/></div><divclass="gmail_extra">-- <br /><div class="gmail_signature">Michael<br /></div></div></div> 

On 2015-02-13 17:06:14 +0900, Michael Paquier wrote:
> On Fri, Feb 13, 2015 at 4:57 PM, Marko Tiikkaja <marko@joh.to> wrote:
> 
> > On 2/13/15 8:52 AM, Michael Paquier wrote:
> >
> >> On Sun, Nov 23, 2014 at 8:23 PM, David Rowley <dgrowleyml@gmail.com>
> >> wrote:
> >>
> >>> As the patch stands there's still a couple of FIXMEs in there, so there's
> >>> still a bit of work to do yet.
> >>> Comments are welcome
> >>>
> >>>
> >> Hm, if there is still work to do, we may as well mark this patch as
> >> rejected as-is, also because it stands in this state for a couple of
> >> months.
> >>
> >
> > I didn't bring this up before, but I'm pretty sure this patch should be
> > marked "returned with feedback".  From what I've understood, "rejected"
> > means "we don't want this thing, not in this form or any other".  That
> > doesn't seem to be the case for this patch, nor for a few others marked
> > "rejected" in the currently in-progress commit fest.
> >
> 
> In the new CF app, marking a patch as "returned this feedback" adds it
> automatically to the next commit fest. And note that it is actually what I
> did for now to move on to the next CF in the doubt:
> https://commitfest.postgresql.org/3/27/
> But if nothing is done, we should as well mark it as "rejected". Not based
> on the fact that it is rejected based on its content, but to not bloat the
> CF app with entries that have no activity for months.

Then the CF app needs to be fixed. Marking patches as rejected on these
grounds is a bad idea.

Greetings,

Andres Freund

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

<div dir="ltr"><br /><div class="gmail_extra"><br /><div class="gmail_quote">On Fri, Feb 13, 2015 at 5:12 PM, Andres
Freund<span dir="ltr"><<a href="mailto:andres@2ndquadrant.com" target="_blank">andres@2ndquadrant.com</a>></span>
wrote:<br/><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div
class="HOEnZb"><divclass="h5">On 2015-02-13 17:06:14 +0900, Michael Paquier wrote:<br /> > On Fri, Feb 13, 2015 at
4:57PM, Marko Tiikkaja <<a href="mailto:marko@joh.to">marko@joh.to</a>> wrote:<br /> ><br /> > > On
2/13/158:52 AM, Michael Paquier wrote:<br /> > ><br /> > >> On Sun, Nov 23, 2014 at 8:23 PM, David
Rowley<<a href="mailto:dgrowleyml@gmail.com">dgrowleyml@gmail.com</a>><br /> > >> wrote:<br /> >
>><br/> > >>> As the patch stands there's still a couple of FIXMEs in there, so there's<br /> >
>>>still a bit of work to do yet.<br /> > >>> Comments are welcome<br /> > >>><br />
>>>><br /> > >> Hm, if there is still work to do, we may as well mark this patch as<br /> >
>>rejected as-is, also because it stands in this state for a couple of<br /> > >> months.<br /> >
>><br/> > ><br /> > > I didn't bring this up before, but I'm pretty sure this patch should be<br />
>> marked "returned with feedback".  From what I've understood, "rejected"<br /> > > means "we don't want
thisthing, not in this form or any other".  That<br /> > > doesn't seem to be the case for this patch, nor for a
fewothers marked<br /> > > "rejected" in the currently in-progress commit fest.<br /> > ><br /> ><br />
>In the new CF app, marking a patch as "returned this feedback" adds it<br /> > automatically to the next commit
fest.And note that it is actually what I<br /> > did for now to move on to the next CF in the doubt:<br /> > <a
href="https://commitfest.postgresql.org/3/27/"target="_blank">https://commitfest.postgresql.org/3/27/</a><br /> >
Butif nothing is done, we should as well mark it as "rejected". Not based<br /> > on the fact that it is rejected
basedon its content, but to not bloat the<br /> > CF app with entries that have no activity for months.<br /><br
/></div></div>Thenthe CF app needs to be fixed. Marking patches as rejected on these<br /> grounds is a bad idea.<br
/></blockquote></div><br/></div><div class="gmail_extra">Yup, definitely the term is incorrect. We need "Returned with
feedbackbut please do not add it to the next CF dear CF app".<br />-- <br /><div class="gmail_signature">Michael<br
/></div></div></div>

There does not seem to be a delete button, so marking as "rejected" due to this now being a duplicate entry for this
patch.