Patch to support SEMI and ANTI join removal

On Tue, Aug 5, 2014 at 10:35 PM, David Rowley <dgrowleyml@gmail.com> wrote:

The patch (attached) is also now able to detect when a NOT EXISTS clause
cannot produce any records at all.

I've attached an updated version of the patch which fixes up some
incorrect logic in the foreign key matching code, plus various comment
improvements.

Regards

David Rowley

On Sun, Aug 10, 2014 at 11:48 PM, David Rowley <dgrowleyml@gmail.com> wrote:

I've attached an updated version of the patch which fixes up some
incorrect logic in the foreign key matching code, plus various comment
improvements.

I've made a few updated to the patch to simplify some logic in the code
which analyses the join condition. The result is slightly faster code for
detecting either successful or unsuccessful join removal.

I've also been doing a little benchmarking of the overhead that this adds
to planning time for a handful of different queries.
With the queries I tested the overhead was between ~20 and ~423 nanoseconds
per SEMI or ANTI join, the 20 was for the earliest fast path out on an
unsuccessful removal and the 423 was for a successful removal. (tests done
on a 4 year old intel i5 laptop). This accounted for between 0.01% and 0.2%
of planning time for the tested queries. I was quite happy with this, but I
did manage to knock it down a little more with the
bms_get_singleton_v1.patch, which I've attached. This reduces the range to
between ~15 and ~409 nanoseconds, but probably this is going into micro
benchmark territory... so perhaps not worth the extra code...

With the benchmarks I just put semiorantijoin_is_removable() in a tight 1
million iteration loop and grabbed the total planning time for that, I then
compared this to an unpatched master's planning time after dividing the
time reported for the 1 million removals version by 1 million.

I didn't really find a good way to measure the extra overhead in actually
loading the foreign key constraints in get_relation_info()

Regards

David Rowley

On Tue, Aug 5, 2014 at 10:35 PM, David Rowley <dgrowleyml@gmail.com> wrote:

Currently most of my changes are in analyzejoin.c, but I did also have to
make changes to load the foreign key constraints so that they were
available to the planner. One thing that is currently lacking, which would
likely be needed, before the finished patch is ready, would be a
"relhasfkeys" column in pg_class. Such a column would mean that it would be
possible to skip scanning pg_constraint for foreign keys when there's none
to find. I'll delay implementing that until I get a bit more feedback to
weather this patch would be a welcome addition to the existing join removal
code or not.

I've modified this patch to include a new "relhasfkey" column in pg_class,
and then only attempt to load the foreign keys in get_relation_info() if
the pg_class flag is true.

Currently what I'm not quite sure on is the best place to be clearing this
flag. I see that relhaspkey is cleared during vacuum, but only if there's
no indexes at all on the relation. It seems that it will remain set to
"true" after vacuum, if the primary key is dropped and there's still other
indexes on the relation. My guess here is that this is done so that
pg_constraint does not have to be checked to see if a PK exists, which is
why I'm not sure if this would be the correct place for me to do the same
in order to determine if there's any FKs on the relation. Though I can't
quite think where else I might clear this flag.

Any ideas or feedback on this would be welcome

Regards

David Rowley

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

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Wed, Aug 27, 2014 at 1:40 AM, Heikki Linnakangas <hlinnakangas@vmware.com

wrote:

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.

I agree that the use case for removals of SEMI and ANTI join are a lot
thinner than LEFT and INNER joins. My longer term goal here is to add join
removal support for INNER joins. In order to do this I need the foreign key
infrastructure which is included in this patch. I held back from just going
ahead and writing the INNER JOIN removal patch as I didn't want to waste
the extra effort in doing that if someone was to find a show stopper
problem with using foreign keys the way I am with this patch. I was kind of
hoping someone would be able to look at this patch a bit more and confirm
to me that it's safe to do this or not before I go ahead and write the
inner join version.

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?

Apart from the extra lines of code in remove_useless_joins(), there's 3
functions added here which won't be needed at all for INNER
JOINs; semiorantijoin_is_removable(), convert_semijoin_to_isnotnull_quals()
and convert_antijoin_to_isnull_quals(). Not including the regression tests,
this is 396 lines with comments and 220 lines without. All of these
functions are static and in analyzejoin.c.

The benchmarks I posted a few weeks back show that the overhead of
performing the semi/anti join removal checks is quite low. I measured an
extra 400 or so nanoseconds for a successful removal on my i5 laptop. Or
just 15 nanoseconds on the earliest fast path for a non-removal. This
accounted for between 0.008% and 0.2% of planning time for the queries I
tested.

Regards

David Rowley

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 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);

<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 that normally 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 make the subqueries useless (ie: SELECT id FROM b WHERE 1=1), or where the condition could be passed through (ie: SELECT id FROM b WHERE id=42). Another possibility would be if there's a condition in the subquery that could trigger constraint elimination.

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

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

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 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);
<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 that normally 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 make the subqueries useless (ie: SELECT id FROM b WHERE 1=1), or where the condition could be passed through (ie: SELECT id FROM b WHERE id=42). Another possibility would be if there's a condition in the subquery that could trigger constraint elimination.

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

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Thu, Aug 28, 2014 at 6:23 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

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.

That seems fair. Likely there'd be not a great deal of value to semi and
anti joins removal alone. I was more just trying to spread weight of an
inner join removal patch...

So In response to this, I've gone off and written an inner join removal
support patch (attached), which turned out to be a bit less complex than I
thought.

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)

Perhaps not a greatly useful example, but if you can imagine the joins are
hidden in a view and the user is just requesting a small subset of columns,
then it does seem quite powerful.

There's currently a few things with the patch that I'll list below, which
may raise a few questions:

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?

2. Currently the inner join removal is dis-allowed if the (would be)
removal relation has *any* baserestrictinfo items. The reason for this is
that we must ensure that the inner join gives us exactly 1 row match on the
join condition, but a baserestrictinfo can void the proof that a foreign
key would give us that a matching row does exist. However there is an
exception to this that could allow that restriction to be relaxed. That is
if the qual in baserestrictinfo use vars that are in an eclass, where the
same eclass also has ec members vars that belong to the rel that we're
using the foreign key for to prove the relation not needed.... umm.. that's
probably better described by example:

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.

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'd have to remove the restriction described in item 2 and
do a small change to the code that extracts the join condition from the
eclass for this to work. But it's likely a corner case that's not worth too
much trouble to support. I think probably if I saw an FK like that in the
field, I'd probably scratch my head for a while, while trying to
understanding why they bothered.

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.

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 only think else I can think of is perhaps optimising a little. I was
thinking likely most queries wont benefit from this too much, so I was
thinking of adding some logic to skip all join removals by pulling out the
varnos from the target list entries and skipping even attempting to perform
a join removal for a relation that has its varno in the targetlist of the
query. Though perhaps a few benchmarks will determine if this is worth it
or not.

Comments are welcome. -- I'm really hoping this patch generates a bit more
interest than the SEMI/ANTI join removal one!

Regards

David Rowley

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

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

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

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Fri, Sep 12, 2014 at 3:35 AM, Robert Haas <robertmhaas@gmail.com> wrote:

On Thu, Sep 11, 2014 at 7:14 AM, David Rowley <dgrowleyml@gmail.com>
wrote:

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.

I discovered over here ->
/messages/by-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.

In the meantime I'll fix up the inner join removal code to properly delete
the ec_relids member for the dead rel. I guess probably the restrict info
should come out too.

I know it's late in the commitfest, but since there was next to no interest
in semi and anti join removals, can I rename the patch in the commitfest
app to be "Inner join removals"? It's either that or I'd mark that patch as
rejected and submit this one in October.

Regards

David Rowley

On Fri, Sep 12, 2014 at 3:47 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

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?

I'd imagine not really expensive. I guess I just thought that it would be a
good idea to save from having to bother looking in pg_constraint for
foreign keys when none exist. The scan uses pg_constraint_conrelid_index so
only would ever see the constraints for the rel being cached/loaded.

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.

I guess it's certainly not required. It would be easier to add it later if
we decided it was a good idea, rather than having to keep it forever and a
day if it's next to useless.

I'll remove it from the patch.

Regards

David Rowley

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 ->
/messages/by-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

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Sat, Sep 13, 2014 at 1:38 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

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

/messages/by-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.

It took me a bit of time to create this problem again as I didn't record
the actual query where I hit the assert failure the first time. Though, now
I have managed to recreate the problem again by removing the code that I
had added which removes eclass members for dead rels.

Using the attached patch, the failing test case is:

create table b (id int primary key);
create table a (id int primary key, b_id int references b);
create index on a (b_id); -- add index to create alternative path

explain select a.* from a inner join b on b.id=a.b_id;

What seems to be happening is that generate_implied_equalities_for_column
generates a RestrictInfo for the dead rel due to the eclass member still
existing. This new rinfo gets matched to the index
by match_clauses_to_index()

The code then later fails in get_loop_count:

TRAP: FailedAssertion("!(outer_rel->rows > 0)", File:
"src\backend\optimizer\path\indxpath.c", Line: 1861)

The call stack looks like:

postgres.exe!get_loop_count(PlannerInfo * root, Bitmapset * outer_relids)

Line 1861 C
postgres.exe!build_index_paths(PlannerInfo * root, RelOptInfo * rel,
IndexOptInfo * index, IndexClauseSet * clauses, char useful_predicate,
SaOpControl saop_control, ScanTypeControl scantype) Line 938 C
postgres.exe!get_index_paths(PlannerInfo * root, RelOptInfo * rel,
IndexOptInfo * index, IndexClauseSet * clauses, List * * bitindexpaths)
Line 745 C
postgres.exe!get_join_index_paths(PlannerInfo * root, RelOptInfo * rel,
IndexOptInfo * index, IndexClauseSet * rclauseset, IndexClauseSet *
jclauseset, IndexClauseSet * eclauseset, List * * bitindexpaths, Bitmapset
* relids, List * * considered_relids) Line 672 C
postgres.exe!consider_index_join_outer_rels(PlannerInfo * root,
RelOptInfo * rel, IndexOptInfo * index, IndexClauseSet * rclauseset,
IndexClauseSet * jclauseset, IndexClauseSet * eclauseset, List * *
bitindexpaths, List * indexjoinclauses, int considered_clauses, List * *
considered_relids) Line 585 C
postgres.exe!consider_index_join_clauses(PlannerInfo * root, RelOptInfo *
rel, IndexOptInfo * index, IndexClauseSet * rclauseset, IndexClauseSet *
jclauseset, IndexClauseSet * eclauseset, List * * bitindexpaths) Line 485 C
postgres.exe!create_index_paths(PlannerInfo * root, RelOptInfo * rel)
Line 308 C
postgres.exe!set_plain_rel_pathlist(PlannerInfo * root, RelOptInfo * rel,
RangeTblEntry * rte) Line 403 C
postgres.exe!set_rel_pathlist(PlannerInfo * root, RelOptInfo * rel,
unsigned int rti, RangeTblEntry * rte) Line 337 C
postgres.exe!set_base_rel_pathlists(PlannerInfo * root) Line 223 C
postgres.exe!make_one_rel(PlannerInfo * root, List * joinlist) Line 157 C
postgres.exe!query_planner(PlannerInfo * root, List * tlist, void
(PlannerInfo *, void *) * qp_callback, void * qp_extra) Line 236 C
postgres.exe!grouping_planner(PlannerInfo * root, double tuple_fraction)
Line 1289 C
postgres.exe!subquery_planner(PlannerGlobal * glob, Query * parse,
PlannerInfo * parent_root, char hasRecursion, double tuple_fraction,
PlannerInfo * * subroot) Line 573 C
postgres.exe!standard_planner(Query * parse, int cursorOptions,
ParamListInfoData * boundParams) Line 211 C
postgres.exe!planner(Query * parse, int cursorOptions, ParamListInfoData
* boundParams) Line 139 C
postgres.exe!pg_plan_query(Query * querytree, int cursorOptions,
ParamListInfoData * boundParams) Line 750 C
postgres.exe!ExplainOneQuery(Query * query, IntoClause * into,
ExplainState * es, const char * queryString, ParamListInfoData * params)
Line 330 C
postgres.exe!ExplainQuery(ExplainStmt * stmt, const char * queryString,
ParamListInfoData * params, _DestReceiver * dest) Line 231 C
postgres.exe!standard_ProcessUtility(Node * parsetree, const char *
queryString, ProcessUtilityContext context, ParamListInfoData * params,
_DestReceiver * dest, char * completionTag) Line 647 C
postgres.exe!ProcessUtility(Node * parsetree, const char * queryString,
ProcessUtilityContext context, ParamListInfoData * params, _DestReceiver *
dest, char * completionTag) Line 314 C
postgres.exe!PortalRunUtility(PortalData * portal, Node * utilityStmt,
char isTopLevel, _DestReceiver * dest, char * completionTag) Line 1195 C
postgres.exe!FillPortalStore(PortalData * portal, char isTopLevel) Line
1063 C
postgres.exe!PortalRun(PortalData * portal, long count, char isTopLevel,
_DestReceiver * dest, _DestReceiver * altdest, char * completionTag) Line
790 C
postgres.exe!exec_simple_query(const char * query_string) Line 1052 C
postgres.exe!PostgresMain(int argc, char * * argv, const char * dbname,
const char * username) Line 4012 C
postgres.exe!BackendRun(Port * port) Line 4113 C
postgres.exe!SubPostmasterMain(int argc, char * * argv) Line 4618 C
postgres.exe!main(int argc, char * * argv) Line 207 C

So my solution to this was just to add the code that strips out the eclass
members that belong to the newly dead rel in join removal.
The only other solution I can think of would be to add a bitmap set of dead
rels onto the PlannerInfo struct or perhaps just generate one and passing
that in prohibited_rels in generate_implied_equalities_for_column (). I
don't really care for this solution very much as it seems better to make
the join removal code pay for this extra processing rather than (probably)
most queries.

Of course this is my problem as I'm unable to create the same situation
with the existing left join removals. The point here is more to justify why
I added code to strip eclass members of dead rels.

Any thoughts? Or arguments against me keeping the code that strips out the
eclass members of dead rels?

Regards

David Rowley

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

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Fri, Sep 26, 2014 at 12:36 AM, Heikki Linnakangas <
hlinnakangas@vmware.com> wrote:

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;

Hi Heikki,

Thanks for having a look at the patch.

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

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. So I think you may have a
point here regarding PREPARE'd statements, but I think that it is isolated
to those.

I think in all other cases we'll plan right before we execute. So if we
happen to be planning an UPDATE statement which has a sub-query that
perform some INNER JOINs, I think we're safe to remove INNER JOINs when
possible, as the UPDATE statement won't get visibility of its own changes.

We can see that here:

create table updatetest (id int primary key, value int, value2 int);

create or replace function getvalue2(p_id int) returns int
as $$select value2 from updatetest where id = p_id$$
language sql volatile;

insert into updatetest values(0,0,0);
insert into updatetest values(1,10,10);
insert into updatetest values(2,20,20);
insert into updatetest values(3,30,30);

update updatetest set value = COALESCE((select value from updatetest u2
where updatetest.id - 1 = u2.id) + 1,0);

update updatetest set value2 = COALESCE(getvalue2(id - 1) + 1,0);

select * from updatetest;
id | value | value2
----+-------+--------
0 | 0 | 0
1 | 1 | 1
2 | 11 | 2
3 | 21 | 3

The value column appears to have been set based on the value that was
previously in the value column, and has not come from the newly set value.
The behaviour is different for the value2 column as the value for this has
been fetched from another query, which *does* see the newly updated value
stored in the value2 column.

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.

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.

The only thing that comes to mind to fix that right now is to tag something
maybe in PlannerInfo to say if we've removed any INNER JOINs in planning,
then when we execute a prepared statement we could void the cached plan we
see that some INNER JOINs were removed, but only do this if the foreign key
trigger queue has pending triggers. (which will hopefully not be very
often).

Another thing that comes to mind which may be similar is how we handle
something like:

PREPARE a AS SELECT * from tbl WHERE name LIKE $1;

Where, if $1 is 'foo' or 'foo%' we might want to use an index scan, but if
$1 was '%foo' then we'd probably not.
I've not yet looked into great detail of what happens here, but from some
quick simple tests it seems to replan each time!? But perhaps that'd due to
the parameter, where with my other tests the PREPARE statement had no
parameters.

There was some other discussion relating to some of this over here->
/messages/by-id/20140603235053.GA351732@tornado.leadboat.com

Regards

David Rowley

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

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

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

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

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. I've made a change to the patch locally to ignore foreign
keys that are marked as deferrable.

Regards

David Rowley