More efficient RI checks - take 2

st 8. 4. 2020 v 18:36 odesílatel Antonin Houska <ah@cybertec.at> napsal:

After having reviewed [1] more than a year ago (the problem I found was
that
the transient table is not available for deferred constraints), I've tried
to
implement the same in an alternative way. The RI triggers still work as row
level triggers, but if multiple events of the same kind appear in the
queue,
they are all passed to the trigger function at once. Thus the check query
does
not have to be executed that frequently.

Some performance comparisons are below. (Besides the execution time, please
note the difference in the number of trigger function executions.) In
general,
the checks are significantly faster if there are many rows to process, and
a
bit slower when we only need to check a single row. However I'm not sure
about
the accuracy if only a single row is measured (if a single row check is
performed several times, the execution time appears to fluctuate).

It is hard task to choose good strategy for immediate constraints, but for
deferred constraints you know how much rows should be checked, and then you
can choose better strategy.

Is possible to use estimation for choosing method of RI checks?

On Wed, Apr 8, 2020 at 1:06 PM Pavel Stehule <pavel.stehule@gmail.com>
wrote:

st 8. 4. 2020 v 18:36 odesílatel Antonin Houska <ah@cybertec.at> napsal:

After having reviewed [1] more than a year ago (the problem I found was
that
the transient table is not available for deferred constraints), I've
tried to
implement the same in an alternative way. The RI triggers still work as
row
level triggers, but if multiple events of the same kind appear in the
queue,
they are all passed to the trigger function at once. Thus the check query
does
not have to be executed that frequently.

I'm excited that you picked this up!

Some performance comparisons are below. (Besides the execution time,
please
note the difference in the number of trigger function executions.) In
general,
the checks are significantly faster if there are many rows to process,
and a
bit slower when we only need to check a single row. However I'm not sure
about
the accuracy if only a single row is measured (if a single row check is
performed several times, the execution time appears to fluctuate).

These numbers are very promising, and much more in line with my initial
expectations. Obviously the impact on single-row DML is of major concern,
though.

It is hard task to choose good strategy for immediate constraints, but for

deferred constraints you know how much rows should be checked, and then you
can choose better strategy.

Is possible to use estimation for choosing method of RI checks?

In doing my initial attempt, the feedback I was getting was that the people
who truly understood the RI checks fell into the following groups:
1. people who wanted to remove the SPI calls from the triggers
2. people who wanted to completely refactor RI to not use triggers
3. people who wanted to completely refactor triggers

While #3 is clearly beyond the scope for an endeavor like this, #1 seems
like it would nearly eliminate the 1-row penalty (we'd still have the
TupleStore initi penalty, but it would just be a handy queue structure, and
maybe that cost would be offset by removing the SPI overhead), and once
that is done, we could see about step #2.

Pavel Stehule <pavel.stehule@gmail.com> wrote:

st 8. 4. 2020 v 18:36 odesílatel Antonin Houska <ah@cybertec.at> napsal:

Some performance comparisons are below. (Besides the execution time, please
note the difference in the number of trigger function executions.) In general,
the checks are significantly faster if there are many rows to process, and a
bit slower when we only need to check a single row. However I'm not sure about
the accuracy if only a single row is measured (if a single row check is
performed several times, the execution time appears to fluctuate).

It is hard task to choose good strategy for immediate constraints, but for
deferred constraints you know how much rows should be checked, and then you
can choose better strategy.

Is possible to use estimation for choosing method of RI checks?

The exact number of rows ("batch size") is always known before the query is
executed. So one problem to solve is that, when only one row is affected, we
need to convince the planner that the "transient table" really contains a
single row. Otherwise it can, for example, produce a hash join where the hash
eventually contains a single row.

--
Antonin Houska
Web: https://www.cybertec-postgresql.com

Corey Huinker <corey.huinker@gmail.com> wrote:

These numbers are very promising, and much more in line with my initial
expectations. Obviously the impact on single-row DML is of major concern,
though.

Yes, I agree.

In doing my initial attempt, the feedback I was getting was that the people
who truly understood the RI checks fell into the following groups:

1. people who wanted to remove the SPI calls from the triggers
2. people who wanted to completely refactor RI to not use triggers
3. people who wanted to completely refactor triggers

While #3 is clearly beyond the scope for an endeavor like this, #1 seems
like it would nearly eliminate the 1-row penalty (we'd still have the
TupleStore initi penalty, but it would just be a handy queue structure, and
maybe that cost would be offset by removing the SPI overhead),

I can imagine removal of the SPI from the current implementation (and
constructing the plans "manually"), but note that the queries I use in my
patch are no longer that trivial. So the SPI makes sense to me because it
ensures regular query planning.

As for the tuplestore, I'm not sure the startup cost is a problem: if you're
concerned about the 1-row case, the row should usually be stored in memory.

and once that is done, we could see about step #2.

As I said during my review of your patch last year, I think the RI semantics
has too much in common with that of triggers. I'd need more info to imagine
such a change.

--
Antonin Houska
Web: https://www.cybertec-postgresql.com

I can imagine removal of the SPI from the current implementation (and
constructing the plans "manually"), but note that the queries I use in my
patch are no longer that trivial. So the SPI makes sense to me because it
ensures regular query planning.

As an intermediate step, in the case where we have one row, it should be
simple enough to extract that row manually, and do an SPI call with fixed
values rather than the join to the ephemeral table, yes?

As for the tuplestore, I'm not sure the startup cost is a problem: if
you're
concerned about the 1-row case, the row should usually be stored in memory.

and once that is done, we could see about step #2.

As I said during my review of your patch last year, I think the RI
semantics
has too much in common with that of triggers. I'd need more info to imagine
such a change.

As a general outline, I think that DML would iterate over the 2 sets of
potentially relevant RI definitions rather than iterating over the
triggers.

The similarities between RI and general triggers are obvious, which
explains why they went that route initially, but they're also a crutch, but
since all RI operations boil down to either an iteration over a tuplestore
to do lookups in an index (when checking for referenced rows), or a hash
join of the transient data against the un-indexed table when checking for
referencing rows, and people who know this stuff far better than me seem to
think that SPI overhead is best avoided when possible. I'm looking forward
to having more time to spend on this.

On 2020-Apr-20, Corey Huinker wrote:

I can imagine removal of the SPI from the current implementation (and
constructing the plans "manually"), but note that the queries I use in my
patch are no longer that trivial. So the SPI makes sense to me because it
ensures regular query planning.

As an intermediate step, in the case where we have one row, it should be
simple enough to extract that row manually, and do an SPI call with fixed
values rather than the join to the ephemeral table, yes?

I do wonder if the RI stuff would actually end up being faster without
SPI. If not, we'd only end up writing more code to do the same thing.
Now that tables can be partitioned, it is much more of a pain than when
only regular tables could be supported. Obviously without SPI you
wouldn't *have* to go through the planner, which might be a win in
itself if the execution tree to use were always perfectly clear ... but
now that the queries get more complex per partitioning and this
optimization, is it?

You could remove the crosscheck_snapshot feature from SPI, I suppose,
but that's not that much code.

--
�lvaro Herrera https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Alvaro Herrera <alvherre@2ndquadrant.com> writes:

I do wonder if the RI stuff would actually end up being faster without
SPI. If not, we'd only end up writing more code to do the same thing.
Now that tables can be partitioned, it is much more of a pain than when
only regular tables could be supported. Obviously without SPI you
wouldn't *have* to go through the planner, which might be a win in
itself if the execution tree to use were always perfectly clear ... but
now that the queries get more complex per partitioning and this
optimization, is it?

AFAIK, we do not have any code besides the planner that is capable of
building a plan tree at all, and I'd be pretty hesitant to try to create
such; those things are complicated.

It'd likely only make sense to bypass the planner if the required work
is predictable enough that you don't need a plan tree at all, but can
just hard-wire what has to be done. That seems a bit unlikely in the
presence of partitioning.

Instead of a plan tree, you could build a parse tree to pass through the
planner, rather than building a SQL statement string that has to be
parsed. The code jumps through enough hoops to make sure the string will
be parsed "just so" that this might net out to about an equal amount of
code in ri_triggers.c, and it'd save a nontrivial amount of parsing work.
But you'd have to abandon SPI, probably, or at least it's not clear how
much that'd be doing for you anymore.

regards, tom lane

Hi,

On 2020-04-21 11:34:54 -0400, Alvaro Herrera wrote:

On 2020-Apr-20, Corey Huinker wrote:

I can imagine removal of the SPI from the current implementation (and
constructing the plans "manually"), but note that the queries I use in my
patch are no longer that trivial. So the SPI makes sense to me because it
ensures regular query planning.

As an intermediate step, in the case where we have one row, it should be
simple enough to extract that row manually, and do an SPI call with fixed
values rather than the join to the ephemeral table, yes?

I do wonder if the RI stuff would actually end up being faster without
SPI.

I would suspect so. How much is another question.

I assume that with constructing plans "manually" you don't mean to
create a plan tree, but to invoke parser/planner directly? I think
that'd likely be better than going through SPI, and there's precedent
too.

But honestly, my gut feeling is that for a lot of cases it'd be best
just bypass parser, planner *and* executor. And just do manual
systable_beginscan() style checks. For most cases we exactly know what
plan shape we expect, and going through the overhead of creating a query
string, parsing, planning, caching the previous steps, and creating an
executor tree for every check is a lot. Even just the amount of memory
for caching the plans can be substantial.

Side note: I for one would appreciate a setting that just made all RI
actions requiring a seqscan error out...

If not, we'd only end up writing more code to do the same thing. Now
that tables can be partitioned, it is much more of a pain than when
only regular tables could be supported. Obviously without SPI you
wouldn't *have* to go through the planner, which might be a win in
itself if the execution tree to use were always perfectly clear
... but now that the queries get more complex per partitioning and
this optimization, is it?

I think it's actually a good case where we will commonly be able to do
*better* than generic planning. The infrastructure for efficient
partition pruning exists (for COPY etc) - but isn't easily applicable to
generic plans.

Greetings,

Andres Freund

Hi,

On 2020-04-21 16:14:53 -0400, Tom Lane wrote:

AFAIK, we do not have any code besides the planner that is capable of
building a plan tree at all, and I'd be pretty hesitant to try to create
such; those things are complicated.

I suspect what was meant was not to create the plan tree directly, but
to bypass SPI when creating the plan / executing the query.

IMO SPI for most uses in core PG really adds more complication and
overhead than warranted. The whole concept of having a global tuptable,
a stack and xact.c integration to repair that design defficiency... The
hiding of what happens behind a pretty random set of different
abstractions. That all makes it appear as if SPI did something super
complicated, but it really doesn't. It just is a bad and
over-complicated abstraction layer.

Greetings,

Andres Freund

On 2020-Apr-22, Andres Freund wrote:

I assume that with constructing plans "manually" you don't mean to
create a plan tree, but to invoke parser/planner directly? I think
that'd likely be better than going through SPI, and there's precedent
too.

Well, I was actually thinking in building ready-made execution trees,
bypassing the planner altogether. But apparently no one thinks that
this is a good idea, and we don't have any code that does that already,
so maybe it's not a great idea.

However:

But honestly, my gut feeling is that for a lot of cases it'd be best
just bypass parser, planner *and* executor. And just do manual
systable_beginscan() style checks. For most cases we exactly know what
plan shape we expect, and going through the overhead of creating a query
string, parsing, planning, caching the previous steps, and creating an
executor tree for every check is a lot. Even just the amount of memory
for caching the plans can be substantial.

Avoiding the executor altogether scares me, but I can't say exactly why.
Foe example, you couldn't use foreign tables at either side of the FK --
but we don't allow FKs on those tables and we'd have to use some
specific executor node for such a thing anyway. So this not a real
argument against going that route.

Side note: I for one would appreciate a setting that just made all RI
actions requiring a seqscan error out...

Hmm, interesting thought. I guess there are actual cases where it's
not strictly necessary, for example where the referencing table is
really tiny -- not the *referenced* table, note, since you need the
UNIQUE index on that side in any case. I suppose that's not a really
interesting case. I don't think this is implementable when going
through SPI.

I think it's actually a good case where we will commonly be able to do
*better* than generic planning. The infrastructure for efficient
partition pruning exists (for COPY etc) - but isn't easily applicable to
generic plans.

True.

--
�lvaro Herrera https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

On Wed, Apr 22, 2020 at 1:18 PM Alvaro Herrera <alvherre@2ndquadrant.com> wrote:

Well, I was actually thinking in building ready-made execution trees,
bypassing the planner altogether. But apparently no one thinks that
this is a good idea, and we don't have any code that does that already,
so maybe it's not a great idea.

If it's any consolation, I had the same idea very recently while
chatting with Amit Langote. Maybe it's a bad idea, but you're not the
only one who had it. :-)

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

Hi,

On 2020-04-22 13:18:06 -0400, Alvaro Herrera wrote:

But honestly, my gut feeling is that for a lot of cases it'd be best
just bypass parser, planner *and* executor. And just do manual
systable_beginscan() style checks. For most cases we exactly know what
plan shape we expect, and going through the overhead of creating a query
string, parsing, planning, caching the previous steps, and creating an
executor tree for every check is a lot. Even just the amount of memory
for caching the plans can be substantial.

Avoiding the executor altogether scares me, but I can't say exactly why.
Foe example, you couldn't use foreign tables at either side of the FK --
but we don't allow FKs on those tables and we'd have to use some
specific executor node for such a thing anyway. So this not a real
argument against going that route.

I think it'd also not that hard to call a specific routine for doing
fkey checks on the remote side. Probably easier to handle things that
way than through "generic" FDW code.

Side note: I for one would appreciate a setting that just made all RI
actions requiring a seqscan error out...

Hmm, interesting thought. I guess there are actual cases where it's
not strictly necessary, for example where the referencing table is
really tiny -- not the *referenced* table, note, since you need the
UNIQUE index on that side in any case. I suppose that's not a really
interesting case.

Yea, the index is pretty much free there. Except I guess for the case of
a tiny table thats super heavily updated.

I don't think this is implementable when going through SPI.

It'd probably be not too hard to approximate by just erroring out when
there's no index on the relevant column, before even doing the planning.

Greetings,

Andres Freund

Hi,

On 2020-04-22 13:46:22 -0400, Robert Haas wrote:

On Wed, Apr 22, 2020 at 1:18 PM Alvaro Herrera <alvherre@2ndquadrant.com> wrote:

Well, I was actually thinking in building ready-made execution trees,
bypassing the planner altogether. But apparently no one thinks that
this is a good idea, and we don't have any code that does that already,
so maybe it's not a great idea.

I was commenting on what I understood Corey to say, but was fairly
unclear about it. But I'm also far from sure that I understood Corey
correctly...

If it's any consolation, I had the same idea very recently while
chatting with Amit Langote. Maybe it's a bad idea, but you're not the
only one who had it. :-)

That seems extremely hard, given our current infrastructure. I think
there's actually a good case to be made for the idea in the abstract,
but ... The amount of logic the ExecInit* routines have is substantial,
the state they set up ss complicates. A lot of nodes have state that is
private to their .c files. All executor nodes reference the
corresponding Plan nodes, so you also need to mock up those.

Greetings,

Andres Freund

Hi,

On 2020-04-08 13:55:55 -0400, Corey Huinker wrote:

In doing my initial attempt, the feedback I was getting was that the people
who truly understood the RI checks fell into the following groups:
1. people who wanted to remove the SPI calls from the triggers
2. people who wanted to completely refactor RI to not use triggers
3. people who wanted to completely refactor triggers

FWIW, for me these three are largely independent avenues:

WRT 1: There's a lot of benefit in reducing the per-call overhead of
RI. Not going through SPI is one way to do that. Even if RI were not to
use triggers, we'd still want to reduce the per-statement costs.

WRT 2: Not using the generic per-row trigger framework for RI has significant
benefits too - checking multiple rows at once, deduplicating repeated
checks, reducing the per-row storage overhead ...

WRT 3: Fairly obviously improving the generic trigger code (more
efficient fetching of tuple versions, spilling etc) would have benefits
entirely independent of other RI improvements.

Greetings,

Andres Freund

On Wed, Apr 22, 2020 at 2:36 PM Andres Freund <andres@anarazel.de> wrote:

Hi,

On 2020-04-22 13:46:22 -0400, Robert Haas wrote:

On Wed, Apr 22, 2020 at 1:18 PM Alvaro Herrera <alvherre@2ndquadrant.com>

wrote:

Well, I was actually thinking in building ready-made execution trees,
bypassing the planner altogether. But apparently no one thinks that
this is a good idea, and we don't have any code that does that already,
so maybe it's not a great idea.

I was commenting on what I understood Corey to say, but was fairly
unclear about it. But I'm also far from sure that I understood Corey
correctly...

I was unclear because, even after my failed foray into statement level
triggers for RI checks, I'm still pretty inexperienced in this area.

I'm just happy that it's being discussed.

On Wed, Apr 22, 2020 at 2:36 PM Andres Freund <andres@anarazel.de> wrote:

If it's any consolation, I had the same idea very recently while
chatting with Amit Langote. Maybe it's a bad idea, but you're not the
only one who had it. :-)

That seems extremely hard, given our current infrastructure. I think
there's actually a good case to be made for the idea in the abstract,
but ... The amount of logic the ExecInit* routines have is substantial,
the state they set up ss complicates. A lot of nodes have state that is
private to their .c files. All executor nodes reference the
corresponding Plan nodes, so you also need to mock up those.

Right -- the idea I was talking about was to create a Plan tree
without using the main planner. So it wouldn't bother costing an index
scan on each index, and a sequential scan, on the target table - it
would just make an index scan plan, or maybe an index path that it
would then convert to an index plan. Or something like that.

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

Robert Haas <robertmhaas@gmail.com> writes:

Right -- the idea I was talking about was to create a Plan tree
without using the main planner. So it wouldn't bother costing an index
scan on each index, and a sequential scan, on the target table - it
would just make an index scan plan, or maybe an index path that it
would then convert to an index plan. Or something like that.

Consing up a Path tree and then letting create_plan() make it into
an executable plan might not be a terrible idea. There's a whole
boatload of finicky details that you could avoid that way, like
everything in setrefs.c.

But it's not entirely clear to me that we know the best plan for a
statement-level RI action with sufficient certainty to go that way.
Is it really the case that the plan would not vary based on how
many tuples there are to check, for example? If we *do* know
exactly what should happen, I'd tend to lean towards Andres'
idea that we shouldn't be using the executor at all, but just
hard-wiring stuff at the level of "do these table scans".

Also, it's definitely not the case that create_plan() has an API
that's so clean that you would be able to use it without major
hassles. You'd still have to generate a pile of lookalike planner
data structures, and make sure that expression subtrees have been
fed through eval_const_expressions(), etc etc.

On the whole I still think that generating a Query tree and then
letting the planner do its thing might be the best approach.

regards, tom lane

On Wed, Apr 22, 2020 at 6:40 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:

But it's not entirely clear to me that we know the best plan for a
statement-level RI action with sufficient certainty to go that way.
Is it really the case that the plan would not vary based on how
many tuples there are to check, for example? If we *do* know
exactly what should happen, I'd tend to lean towards Andres'
idea that we shouldn't be using the executor at all, but just
hard-wiring stuff at the level of "do these table scans".

Well, I guess I'd naively think we want an index scan on a plain
table. It is barely possible that in some corner case a sequential
scan would be faster, but could it be enough faster to save the cost
of planning? I doubt it, but I just work here.

On a partitioning hierarchy we want to figure out which partition is
relevant for the value we're trying to find, and then scan that one.

I'm not sure there are any other cases. We have to have a UNIQUE
constraint or we can't be referencing this target table. So it can't
be a plain inheritance hierarchy, nor (I think) a foreign table.

Also, it's definitely not the case that create_plan() has an API
that's so clean that you would be able to use it without major
hassles. You'd still have to generate a pile of lookalike planner
data structures, and make sure that expression subtrees have been
fed through eval_const_expressions(), etc etc.

Yeah, that's annoying.

On the whole I still think that generating a Query tree and then
letting the planner do its thing might be the best approach.

Maybe, but it seems awfully heavy-weight. Once you go into the planner
it's pretty hard to avoid considering indexes we don't care about,
bitmap scans we don't care about, a sequential scan we don't care
about, etc. You'd certainly save something just from avoiding
parsing, but planning's pretty expensive too.

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

Tom Lane <tgl@sss.pgh.pa.us> wrote:

Robert Haas <robertmhaas@gmail.com> writes:

Right -- the idea I was talking about was to create a Plan tree
without using the main planner. So it wouldn't bother costing an index
scan on each index, and a sequential scan, on the target table - it
would just make an index scan plan, or maybe an index path that it
would then convert to an index plan. Or something like that.

Consing up a Path tree and then letting create_plan() make it into
an executable plan might not be a terrible idea. There's a whole
boatload of finicky details that you could avoid that way, like
everything in setrefs.c.

But it's not entirely clear to me that we know the best plan for a
statement-level RI action with sufficient certainty to go that way.
Is it really the case that the plan would not vary based on how
many tuples there are to check, for example?

I'm concerned about that too. With my patch the checks become a bit slower if
only a single row is processed. The problem seems to be that the planner is
not entirely convinced about that the number of input rows, so it can still
build a plan that expects many rows. For example (as I mentioned elsewhere in
the thread), a hash join where the hash table only contains one tuple. Or
similarly a sort node for a single input tuple.

--
Antonin Houska
Web: https://www.cybertec-postgresql.com