Patch: Write Amplification Reduction Method (WARM)

On Wed, Aug 31, 2016 at 1:45 PM, Pavan Deolasee <pavan.deolasee@gmail.com>
wrote:

We discussed a few ideas to address the "Duplicate Scan" problem. For
example, we can teach Index AMs to discard any duplicate (key, CTID) insert
requests. Or we could guarantee uniqueness by either only allowing updates
in one lexical order. While the former is a more complete solution to avoid
duplicate entries, searching through large number of keys for non-unique
indexes could be a drag on performance. The latter approach may not be
sufficient for many workloads. Also tracking increment/decrement for many
indexes will be non-trivial.

There is another problem with allowing many index entries pointing to the
same WARM chain. It will be non-trivial to know how many index entries are
currently pointing to the WARM chain and index/heap vacuum will throw up
more challenges.

Instead, what I would like to propose and the patch currently implements
is to restrict WARM update to once per chain. So the first non-HOT update
to a tuple or a HOT chain can be a WARM update. The chain can further be
HOT updated any number of times. But it can no further be WARM updated.
This might look too restrictive, but it can still bring down the number of
regular updates by almost 50%. Further, if we devise a strategy to convert
a WARM chain back to HOT chain, it can again be WARM updated. (This part is
currently not implemented). A good side effect of this simple strategy is
that we know there can maximum two index entries pointing to any given WARM
chain.

We should probably think about coordinating with my btree patch.

From the description above, the strategy is quite readily "upgradable" to
one in which the indexam discards duplicate (key,ctid) pairs and that would
remove the limitation of only one WARM update... right?

On Wed, Aug 31, 2016 at 10:38 PM, Claudio Freire <klaussfreire@gmail.com>
wrote:

On Wed, Aug 31, 2016 at 1:45 PM, Pavan Deolasee <pavan.deolasee@gmail.com>
wrote:

We discussed a few ideas to address the "Duplicate Scan" problem. For
example, we can teach Index AMs to discard any duplicate (key, CTID) insert
requests. Or we could guarantee uniqueness by either only allowing updates
in one lexical order. While the former is a more complete solution to avoid
duplicate entries, searching through large number of keys for non-unique
indexes could be a drag on performance. The latter approach may not be
sufficient for many workloads. Also tracking increment/decrement for many
indexes will be non-trivial.

There is another problem with allowing many index entries pointing to the
same WARM chain. It will be non-trivial to know how many index entries are
currently pointing to the WARM chain and index/heap vacuum will throw up
more challenges.

Instead, what I would like to propose and the patch currently implements
is to restrict WARM update to once per chain. So the first non-HOT update
to a tuple or a HOT chain can be a WARM update. The chain can further be
HOT updated any number of times. But it can no further be WARM updated.
This might look too restrictive, but it can still bring down the number of
regular updates by almost 50%. Further, if we devise a strategy to convert
a WARM chain back to HOT chain, it can again be WARM updated. (This part is
currently not implemented). A good side effect of this simple strategy is
that we know there can maximum two index entries pointing to any given WARM
chain.

We should probably think about coordinating with my btree patch.

From the description above, the strategy is quite readily "upgradable" to
one in which the indexam discards duplicate (key,ctid) pairs and that would
remove the limitation of only one WARM update... right?

Yes, we should be able to add further optimisations on lines you're working
on, but what I like about the current approach is that a) it reduces
complexity of the patch and b) having thought about cleaning up WARM
chains, limiting number of index entries per root chain to a small number
will simplify that aspect too.

Thanks,
Pavan

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

On Wed, Aug 31, 2016 at 10:15 PM, Pavan Deolasee <pavan.deolasee@gmail.com>
wrote:

Hi All,

As previously discussed [1], WARM is a technique to reduce write
amplification when an indexed column of a table is updated. HOT fails to
handle such updates and ends up inserting a new index entry in all indexes
of the table, irrespective of whether the index key has changed or not for
a specific index. The problem was highlighted by Uber's blog post [2], but
it was a well known problem and affects many workloads.

I realised that the patches were bit-rotten because of 8e1e3f958fb. Rebased
patches on the current master are attached. I also took this opportunity to
correct some white space errors and improve formatting of the README.

Thanks,
Pavan

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

On Wed, Aug 31, 2016 at 10:15:33PM +0530, Pavan Deolasee wrote:

Instead, what I would like to propose and the patch currently implements is to
restrict WARM update to once per chain. So the first non-HOT update to a tuple
or a HOT chain can be a WARM update. The chain can further be HOT updated any
number of times. But it can no further be WARM updated. This might look too
restrictive, but it can still bring down the number of regular updates by
almost 50%. Further, if we devise a strategy to convert a WARM chain back to
HOT chain, it can again be WARM updated. (This part is currently not
implemented). A good side effect of this simple strategy is that we know there
can maximum two index entries pointing to any given WARM chain.

I like the simplified approach, as long as it doesn't block further
improvements.

Headline TPS numbers:

Master:

transaction type: update.sql
scaling factor: 700
query mode: simple
number of clients: 16
number of threads: 8
duration: 57600 s
number of transactions actually processed: 65552986
latency average: 14.059 ms
tps = 1138.072117 (including connections establishing)
tps = 1138.072156 (excluding connections establishing)

WARM:

transaction type: update.sql
scaling factor: 700
query mode: simple
number of clients: 16
number of threads: 8
duration: 57600 s
number of transactions actually processed: 116168454
latency average: 7.933 ms
tps = 2016.812924 (including connections establishing)
tps = 2016.812997 (excluding connections establishing)

These are very impressive results.

Converting WARM chains back to HOT chains (VACUUM ?)
---------------------------------------------------------------------------------

The current implementation of WARM allows only one WARM update per chain. This
simplifies the design and addresses certain issues around duplicate scans. But
this also implies that the benefit of WARM will be no more than 50%, which is
still significant, but if we could return WARM chains back to normal status, we
could do far more WARM updates.

A distinct property of a WARM chain is that at least one index has more than
one live index entries pointing to the root of the chain. In other words, if we
can remove duplicate entry from every index or conclusively prove that there
are no duplicate index entries for the root line pointer, the chain can again
be marked as HOT.

I had not thought of how to convert from WARM to HOT yet.

Here is one idea, but more thoughts/suggestions are most welcome.�

A WARM chain has two parts, separated by the tuple that caused WARM update. All
tuples in each part has matching index keys, but certain index keys may not
match between these two parts. Lets say we mark heap tuples in each part with a
special Red-Blue flag. The same flag is replicated in the index tuples. For
example, when new rows are inserted in a table, they are marked with Blue flag
and the index entries associated with those rows are also marked with Blue
flag. When a row is WARM updated, the new version is marked with Red flag and
the new index entry created by the update is also marked with Red flag.

Heap chain: lp �[1] [2] [3] [4]
� [aaaa, 1111]B -> [aaaa, 1111]B -> [bbbb, 1111]R -> [bbbb, 1111]R

Index1: (aaaa)B points to 1 (satisfies only tuples marked with B)
(bbbb)R points to 1 (satisfies only tuples marked with R)

Index2: (1111)B points to 1 (satisfies both B and R tuples)

It's clear that for indexes with Red and Blue pointers, a heap tuple with Blue
flag will be reachable from Blue pointer and that with Red flag will be
reachable from Red pointer. But for indexes which did not create a new entry,
both Blue and Red tuples will be reachable from Blue pointer (there is no Red
pointer in such indexes). So, as a side note, matching Red and Blue flags is
not enough from index scan perspective.

During first heap scan of VACUUM, we look for tuples with HEAP_WARM_TUPLE set.
If all live tuples in the chain are either marked with Blue flag or Red flag
(but no mix of Red and Blue), then the chain is a candidate for HOT conversion.

Uh, if the chain is all blue, then there is are WARM entries so it
already a HOT chain, so there is nothing to do, right?

We remember the root line pointer and Red-Blue flag of the WARM chain in a
separate array.

If we have a Red WARM chain, then our goal is to remove Blue pointers and vice
versa. But there is a catch. For Index2 above, there is only Blue pointer
and that must not be removed. IOW we should remove Blue pointer iff a Red
pointer exists. Since index vacuum may visit Red and Blue pointers in any
order, I think we will need another index pass to remove dead
index pointers. So in the first index pass we check which WARM candidates have
2 index pointers. In the second pass, we remove the dead pointer and reset Red
flag is the surviving index pointer is Red.

Why not just remember the tid of chains converted from WARM to HOT, then
use "amrecheck" on an index entry matching that tid to see if the index
matches one of the entries in the chain. (It will match all of them or
none of them, because they are all red.) I don't see a point in
coloring the index entries as reds as later you would have to convert to
blue in the WARM-to-HOT conversion, and a vacuum crash could lead to
inconsistencies. Consider that you can just call "amrecheck" on the few
chains that have converted from WARM to HOT. I believe this is more
crash-safe too. However, if you have converted WARM to HOT in the heap,
but crash durin the index entry removal, you could potentially have
duplicates in the index later, which is bad.

--
Bruce Momjian <bruce@momjian.us> http://momjian.us
EnterpriseDB http://enterprisedb.com

+ As you are, so once was I. As I am, so you will be. +
+                     Ancient Roman grave inscription +

--
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 31, 2016 at 04:03:29PM -0400, Bruce Momjian wrote:

Why not just remember the tid of chains converted from WARM to HOT, then
use "amrecheck" on an index entry matching that tid to see if the index
matches one of the entries in the chain. (It will match all of them or
none of them, because they are all red.) I don't see a point in
coloring the index entries as reds as later you would have to convert to
blue in the WARM-to-HOT conversion, and a vacuum crash could lead to
inconsistencies. Consider that you can just call "amrecheck" on the few
chains that have converted from WARM to HOT. I believe this is more
crash-safe too. However, if you have converted WARM to HOT in the heap,
but crash during the index entry removal, you could potentially have
duplicates in the index later, which is bad.

I think Pavan had the "crash durin the index entry removal" fixed via:

During the second heap scan, we fix WARM chain by clearing HEAP_WARM_TUPLE flag
and also reset Red flag to Blue.

so the marking from WARM to HOT only happens after the index has been cleaned.

--
Bruce Momjian <bruce@momjian.us> http://momjian.us
EnterpriseDB http://enterprisedb.com

+ As you are, so once was I. As I am, so you will be. +
+                     Ancient Roman grave inscription +

--
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, Sep 1, 2016 at 1:33 AM, Bruce Momjian <bruce@momjian.us> wrote:

On Wed, Aug 31, 2016 at 10:15:33PM +0530, Pavan Deolasee wrote:

Instead, what I would like to propose and the patch currently implements

is to

restrict WARM update to once per chain. So the first non-HOT update to a

tuple

or a HOT chain can be a WARM update. The chain can further be HOT

updated any

number of times. But it can no further be WARM updated. This might look

too

restrictive, but it can still bring down the number of regular updates by
almost 50%. Further, if we devise a strategy to convert a WARM chain

back to

HOT chain, it can again be WARM updated. (This part is currently not
implemented). A good side effect of this simple strategy is that we know

there

can maximum two index entries pointing to any given WARM chain.

I like the simplified approach, as long as it doesn't block further
improvements.

Yes, the proposed approach is simple yet does not stop us from improving
things further. Moreover it has shown good performance characteristics and
I believe it's a good first step.

Master:
tps = 1138.072117 (including connections establishing)

WARM:
tps = 2016.812924 (including connections establishing)

These are very impressive results.

Thanks. What's also interesting and something that headline numbers don't
show is that WARM TPS is as much as 3 times of master TPS when the
percentage of WARM updates is very high. Notice the spike in TPS in the
comparison graph.

Results with non-default heap fill factor are even better. In both cases,
the improvement in TPS stays constant over long periods.

During first heap scan of VACUUM, we look for tuples with

HEAP_WARM_TUPLE set.

If all live tuples in the chain are either marked with Blue flag or Red

flag

(but no mix of Red and Blue), then the chain is a candidate for HOT

conversion.

Uh, if the chain is all blue, then there is are WARM entries so it
already a HOT chain, so there is nothing to do, right?

For aborted WARM updates, the heap chain may be all blue, but there may
still be a red index pointer which must be cleared before we allow further
WARM updates to the chain.

We remember the root line pointer and Red-Blue flag of the WARM chain in

a

separate array.

If we have a Red WARM chain, then our goal is to remove Blue pointers

and vice

versa. But there is a catch. For Index2 above, there is only Blue pointer
and that must not be removed. IOW we should remove Blue pointer iff a Red
pointer exists. Since index vacuum may visit Red and Blue pointers in any
order, I think we will need another index pass to remove dead
index pointers. So in the first index pass we check which WARM

candidates have

2 index pointers. In the second pass, we remove the dead pointer and

reset Red

flag is the surviving index pointer is Red.

Why not just remember the tid of chains converted from WARM to HOT, then
use "amrecheck" on an index entry matching that tid to see if the index
matches one of the entries in the chain.

That will require random access to heap during index vacuum phase,
something I would like to avoid. But we can have that as a fall back
solution for handling aborted vacuums.

(It will match all of them or
none of them, because they are all red.) I don't see a point in
coloring the index entries as reds as later you would have to convert to
blue in the WARM-to-HOT conversion, and a vacuum crash could lead to
inconsistencies.

Yes, that's a concern since the conversion of red to blue will also need to
WAL logged to ensure that a crash doesn't leave us in inconsistent state. I
still think that this will be an overall improvement as compared to
allowing one WARM update per chain.

Consider that you can just call "amrecheck" on the few
chains that have converted from WARM to HOT. I believe this is more
crash-safe too. However, if you have converted WARM to HOT in the heap,
but crash durin the index entry removal, you could potentially have
duplicates in the index later, which is bad.

As you probably already noted, we clear heap flags only after all indexes
are cleared of duplicate entries and hence a crash in between should not
cause any correctness issue. As long as heap tuples are marked as warm,
amrecheck will ensure that only valid tuples are returned to the caller.

Thanks,
Pavan

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

On Thu, Sep 1, 2016 at 02:37:40PM +0530, Pavan Deolasee wrote:

I like the simplified approach, as long as it doesn't block further
improvements.

Yes, the proposed approach is simple yet does not stop us from improving things
further. Moreover it has shown good performance characteristics and I believe
it's a good first step.

Agreed. This is BIG. Do you think it can be done for PG 10?

Thanks. What's also interesting and something that headline numbers don't show
is that WARM TPS is as much as 3 times of master TPS when the percentage of
WARM updates is very high. Notice the spike in TPS in the comparison graph.

Results with non-default heap fill factor are even better. In both cases, the
improvement in TPS stays constant over long periods.�

Yes, I expect the benefits of this to show up in better long-term
performance.

During first heap scan of VACUUM, we look for tuples with HEAP_WARM_TUPLE

set.

If all live tuples in the chain are either marked with Blue flag or Red

flag

(but no mix of Red and Blue), then the chain is a candidate for HOT

conversion.

Uh, if the chain is all blue, then there is are WARM entries so it
already a HOT chain, so there is nothing to do, right?

For aborted WARM updates, the heap chain may be all blue, but there may still
be a red index pointer which must be cleared before we allow further WARM
updates to the chain.

Ah, understood now. Thanks.

Why not just remember the tid of chains converted from WARM to HOT, then
use "amrecheck" on an index entry matching that tid to see if the index
matches one of the entries in the chain.�

That will require random access to heap during index vacuum phase, something I
would like to avoid. But we can have that as a fall back solution for handling
aborted vacuums.�

Yes, that is true. So the challenge is figuring how which of the index
entries pointing to the same tid is valid, and coloring helps with that?

(It will match all of them or
none of them, because they are all red.)� I don't see a point in
coloring the index entries as reds as later you would have to convert to
blue in the WARM-to-HOT conversion, and a vacuum crash could lead to
inconsistencies.�

Yes, that's a concern since the conversion of red to blue will also need to WAL
logged to ensure that a crash doesn't leave us in inconsistent state. I still
think that this will be an overall improvement as compared to allowing one WARM
update per chain.

OK. I will think some more on this to see if I can come with another
approach.

�

Consider that you can just call "amrecheck" on the few
chains that have converted from WARM to HOT.� I believe this is more
crash-safe too.� However, if you have converted WARM to HOT in the heap,
but crash durin the index entry removal, you could potentially have
duplicates in the index later, which is bad.

As you probably already noted, we clear heap flags only after all indexes are
cleared of duplicate entries and hence a crash in between should not cause any
correctness issue. As long as heap tuples are marked as warm, amrecheck will
ensure that only valid tuples are returned to the caller.

OK, got it.

--
Bruce Momjian <bruce@momjian.us> http://momjian.us
EnterpriseDB http://enterprisedb.com

+ As you are, so once was I. As I am, so you will be. +
+                     Ancient Roman grave inscription +

--
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, Sep 1, 2016 at 9:44 PM, Bruce Momjian <bruce@momjian.us> wrote:

On Thu, Sep 1, 2016 at 02:37:40PM +0530, Pavan Deolasee wrote:

I like the simplified approach, as long as it doesn't block further
improvements.

Yes, the proposed approach is simple yet does not stop us from improving

things

further. Moreover it has shown good performance characteristics and I

believe

it's a good first step.

Agreed. This is BIG. Do you think it can be done for PG 10?

I definitely think so. The patches as submitted are fully functional and
sufficient. Of course, there are XXX and TODOs that I hope to sort out
during the review process. There are also further tests needed to ensure
that the feature does not cause significant regression in the worst cases.
Again something I'm willing to do once I get some feedback on the broader
design and test cases. What I am looking at this stage is to know if I've
missed something important in terms of design or if there is some show
stopper that I overlooked.

Latest patches rebased with current master are attached. I also added a few
more comments to the code. I forgot to give a brief about the patches, so
including that as well.

0001_track_root_lp_v4.patch: This patch uses a free t_infomask2 bit to
track latest tuple in an update chain. The t_ctid.ip_posid is used to track
the root line pointer of the update chain. We do this only in the latest
tuple in the chain because most often that tuple will be updated and we
need to quickly find the root only during update.

0002_warm_updates_v4.patch: This patch implements the core of WARM logic.
During WARM update, we only insert new entries in the indexes whose key has
changed. But instead of indexing the real TID of the new tuple, we index
the root line pointer and then use additional recheck logic to ensure only
correct tuples are returned from such potentially broken HOT chains. Each
index AM must implement a amrecheck method to support WARM. The patch
currently implements this for hash and btree indexes.

Thanks,
Pavan

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

On Mon, Sep 5, 2016 at 1:53 PM, Pavan Deolasee <pavan.deolasee@gmail.com> wrote:

0001_track_root_lp_v4.patch: This patch uses a free t_infomask2 bit to track
latest tuple in an update chain. The t_ctid.ip_posid is used to track the
root line pointer of the update chain. We do this only in the latest tuple
in the chain because most often that tuple will be updated and we need to
quickly find the root only during update.

0002_warm_updates_v4.patch: This patch implements the core of WARM logic.
During WARM update, we only insert new entries in the indexes whose key has
changed. But instead of indexing the real TID of the new tuple, we index the
root line pointer and then use additional recheck logic to ensure only
correct tuples are returned from such potentially broken HOT chains. Each
index AM must implement a amrecheck method to support WARM. The patch
currently implements this for hash and btree indexes.

Moved to next CF, I was surprised to see that it is not *that* large:
43 files changed, 1539 insertions(+), 199 deletions(-)
--
Michael

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

On 09/05/2016 06:53 AM, Pavan Deolasee wrote:

On Thu, Sep 1, 2016 at 9:44 PM, Bruce Momjian <bruce@momjian.us
<mailto:bruce@momjian.us>> wrote:

On Thu, Sep 1, 2016 at 02:37:40PM +0530, Pavan Deolasee wrote:

I like the simplified approach, as long as it doesn't block further
improvements.

Yes, the proposed approach is simple yet does not stop us from improving things
further. Moreover it has shown good performance characteristics and I believe
it's a good first step.

Agreed. This is BIG. Do you think it can be done for PG 10?

I definitely think so. The patches as submitted are fully functional and
sufficient. Of course, there are XXX and TODOs that I hope to sort out
during the review process. There are also further tests needed to ensure
that the feature does not cause significant regression in the worst
cases. Again something I'm willing to do once I get some feedback on the
broader design and test cases. What I am looking at this stage is to
know if I've missed something important in terms of design or if there
is some show stopper that I overlooked.

Latest patches rebased with current master are attached. I also added a
few more comments to the code. I forgot to give a brief about the
patches, so including that as well.

0001_track_root_lp_v4.patch: This patch uses a free t_infomask2 bit to
track latest tuple in an update chain. The t_ctid.ip_posid is used to
track the root line pointer of the update chain. We do this only in the
latest tuple in the chain because most often that tuple will be updated
and we need to quickly find the root only during update.

0002_warm_updates_v4.patch: This patch implements the core of WARM
logic. During WARM update, we only insert new entries in the indexes
whose key has changed. But instead of indexing the real TID of the new
tuple, we index the root line pointer and then use additional recheck
logic to ensure only correct tuples are returned from such potentially
broken HOT chains. Each index AM must implement a amrecheck method to
support WARM. The patch currently implements this for hash and btree
indexes.

Hi,

I've been looking at the patch over the past few days, running a bunch
of benchmarks etc. I can confirm the significant speedup, often by more
than 75% (depending on number of indexes, whether the data set fits into
RAM, etc.). Similarly for the amount of WAL generated, although that's a
bit more difficult to evaluate due to full_page_writes.

I'm not going to send detailed results, as that probably does not make
much sense at this stage of the development - I can repeat the tests
once the open questions get resolved.

There's a lot of useful and important feedback in the thread(s) so far,
particularly the descriptions of various failure cases. I think it'd be
very useful to collect those examples and turn them into regression
tests - that's something the patch should include anyway.

I don't really have much comments regarding the code, but during the
testing I noticed a bit strange behavior when updating statistics.
Consider a table like this:

create table t (a int, b int, c int) with (fillfactor = 10);
insert into t select i, i from generate_series(1,1000) s(i);
create index on t(a);
create index on t(b);

and update:

update t set a = a+1, b=b+1;

which has to update all indexes on the table, but:

select n_tup_upd, n_tup_hot_upd from pg_stat_user_tables

n_tup_upd | n_tup_hot_upd
-----------+---------------
1000 | 1000

So it's still counted as "WARM" - does it make sense? I mean, we're
creating a WARM chain on the page, yet we have to add pointers into all
indexes (so not really saving anything). Doesn't this waste the one WARM
update per HOT chain without actually getting anything in return?

The way this is piggy-backed on the current HOT statistics seems a bit
strange for another reason, although WARM is a relaxed version of HOT.
Until now, HOT was "all or nothing" - we've either added index entries
to all indexes or none of them. So the n_tup_hot_upd was fine.

But WARM changes that - it allows adding index entries only to a subset
of indexes, which means the "per row" n_tup_hot_upd counter is not
sufficient. When you have a table with 10 indexes, and the counter
increases by 1, does that mean the update added index tuple to 1 index
or 9 of them?

So I think we'll need two counters to track WARM - number of index
tuples we've added, and number of index tuples we've skipped. So
something like blks_hit and blks_read. I'm not sure whether we should
replace the n_tup_hot_upd entirely, or keep it for backwards
compatibility (and to track perfectly HOT updates).

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, 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

On Wed, Oct 5, 2016 at 1:43 PM, Tomas Vondra <tomas.vondra@2ndquadrant.com>
wrote:

I've been looking at the patch over the past few days, running a bunch of
benchmarks etc.

Thanks for doing that.

I can confirm the significant speedup, often by more than 75% (depending
on number of indexes, whether the data set fits into RAM, etc.). Similarly
for the amount of WAL generated, although that's a bit more difficult to
evaluate due to full_page_writes.

I'm not going to send detailed results, as that probably does not make
much sense at this stage of the development - I can repeat the tests once
the open questions get resolved.

Sure. Anything that stands out? Any regression that you see? I'm not sure
if your benchmarks exercise the paths which might show overheads without
any tangible benefits. For example, I wonder if a test with many indexes
where most of them get updated and then querying the table via those
updated indexes could be one such test case.

There's a lot of useful and important feedback in the thread(s) so far,
particularly the descriptions of various failure cases. I think it'd be
very useful to collect those examples and turn them into regression tests -
that's something the patch should include anyway.

Sure. I added only a handful test cases which I knew regression isn't
covering. But I'll write more of them. One good thing is that the code gets
heavily exercised even during regression. I caught and fixed multiple bugs
running regression. I'm not saying that's enough, but it certainly gives
some confidence.

and update:

update t set a = a+1, b=b+1;

which has to update all indexes on the table, but:

select n_tup_upd, n_tup_hot_upd from pg_stat_user_tables

n_tup_upd | n_tup_hot_upd
-----------+---------------
1000 | 1000

So it's still counted as "WARM" - does it make sense?

No, it does not. The code currently just marks any update as a WARM update
if the table supports it and there is enough free space in the page. And
yes, you're right. It's worth fixing that because of one-WARM update per
chain limitation. Will fix.

The way this is piggy-backed on the current HOT statistics seems a bit
strange for another reason,

Agree. We could add a similar n_tup_warm_upd counter.

But WARM changes that - it allows adding index entries only to a subset of
indexes, which means the "per row" n_tup_hot_upd counter is not sufficient.
When you have a table with 10 indexes, and the counter increases by 1, does
that mean the update added index tuple to 1 index or 9 of them?

How about having counters similar to n_tup_ins/n_tup_del for indexes as
well? Today it does not make sense because every index gets the same number
of inserts, but WARM will change that.

For example, we could have idx_tup_insert and idx_tup_delete that shows up
in pg_stat_user_indexes. I don't know if idx_tup_delete adds any value, but
one can then look at idx_tup_insert for various indexes to get a sense
which indexes receives more inserts than others. The indexes which receive
more inserts are the ones being frequently updated as compared to other
indexes.

This also relates to vacuuming strategies. Today HOT updates do not count
for triggering vacuum (or to be more precise, HOT pruned tuples are
discounted while counting dead tuples). WARM tuples get the same treatment
as far as pruning is concerned, but since they cause fresh index inserts, I
wonder if we need some mechanism to cleanup the dead line pointers and dead
index entries. This will become more important if we do something to
convert WARM chains into HOT chains, something that only VACUUM can do in
the design I've proposed so far.

Thanks,
Pavan

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

On 10/06/2016 07:36 AM, Pavan Deolasee wrote:

On Wed, Oct 5, 2016 at 1:43 PM, Tomas Vondra
<tomas.vondra@2ndquadrant.com <mailto:tomas.vondra@2ndquadrant.com>> wrote:

...

I can confirm the significant speedup, often by more than 75%
(depending on number of indexes, whether the data set fits into RAM,
etc.). Similarly for the amount of WAL generated, although that's a
bit more difficult to evaluate due to full_page_writes.

I'm not going to send detailed results, as that probably does not
make much sense at this stage of the development - I can repeat the
tests once the open questions get resolved.

Sure. Anything that stands out? Any regression that you see? I'm not
sure if your benchmarks exercise the paths which might show overheads
without any tangible benefits. For example, I wonder if a test with many
indexes where most of them get updated and then querying the table via
those updated indexes could be one such test case.

No, nothing that would stand out. Let me explain what benchmark(s) I've
done. I've made some minor mistakes when running the benchmarks, so I
plan to rerun them and post the results after that. So let's take the
data with a grain of salt.

My goal was to compare current non-HOT behavior (updating all indexes)
with the WARM (updating only indexes on modified columns), and I've
taken two approaches:

1) fixed number of indexes, update variable number of columns

Create a table with 8 secondary indexes and then run a bunch of
benchmarks updating increasing number of columns. So the first run did

UPDATE t SET c1 = c1+1 WHERE id = :id;

while the second did

UPDATE t SET c1 = c1+1, c2 = c2+1 WHERE id = :id;

and so on, up to updating all the columns in the last run. I've used
multiple scripts to update all the columns / indexes uniformly
(essentially using multiple "-f" flags with pgbench). The runs were
fairly long (2h, enough to get stable behavior).

For a small data set (fits into RAM), the results look like this:

master patched diff
1 5994 8490 +42%
2 4347 7903 +81%
3 4340 7400 +70%
4 4324 6929 +60%
5 4256 6495 +52%
6 4253 5059 +19%
7 4235 4534 +7%
8 4194 4237 +1%

and the amount of WAL generated (after correction for tps difference)
looks like this (numbers are MBs)

master patched diff
1 27257 18508 -32%
2 21753 14599 -33%
3 21912 15864 -28%
4 22021 17135 -22%
5 21819 18258 -16%
6 21929 20659 -6%
7 21994 22234 +1%
8 21851 23267 +6%

So this is quite significant difference. I'm pretty sure the minor WAL
increase for the last two runs is due to full page writes (which also
affects the preceding runs, making the WAL reduction smaller than the
tps increase).

I do have results for larger data sets (>RAM), the results are very
similar although the speedup seems a bit smaller. But I need to rerun those.

2) single-row update, adding indexes between runs

This is kinda the opposite of the previous approach, i.e. transactions
always update a single column (multiple scripts to update the columns
uniformly), but there are new indexes added between runs. The results
(for a large data set, exceeding RAM) look like this:

master patched diff
0 954 1404 +47%
1 701 1045 +49%
2 484 816 +70%
3 346 683 +97%
4 248 608 +145%
5 190 525 +176%
6 152 397 +161%
7 123 315 +156%
8 123 270 +119%

So this looks really interesting.

There's a lot of useful and important feedback in the thread(s) so
far, particularly the descriptions of various failure cases. I think
it'd be very useful to collect those examples and turn them into
regression tests - that's something the patch should include anyway.

Sure. I added only a handful test cases which I knew regression isn't
covering. But I'll write more of them. One good thing is that the code
gets heavily exercised even during regression. I caught and fixed
multiple bugs running regression. I'm not saying that's enough, but it
certainly gives some confidence.

I don't see any changes to src/test in the patch, so I'm not sure what
you mean when you say you added a handful of test cases?

and update:

update t set a = a+1, b=b+1;

which has to update all indexes on the table, but:

select n_tup_upd, n_tup_hot_upd from pg_stat_user_tables

n_tup_upd | n_tup_hot_upd
-----------+---------------
1000 | 1000

So it's still counted as "WARM" - does it make sense?

No, it does not. The code currently just marks any update as a WARM
update if the table supports it and there is enough free space in the
page. And yes, you're right. It's worth fixing that because of one-WARM
update per chain limitation. Will fix.

Hmmm, so this makes monitoring of %WARM during benchmarks less reliable
than I hoped for :-(

The way this is piggy-backed on the current HOT statistics seems a
bit strange for another reason,

Agree. We could add a similar n_tup_warm_upd counter.

Yes, although HOT is a special case of WARM. But it probably makes sense
to differentiate them, I guess.

But WARM changes that - it allows adding index entries only to a
subset of indexes, which means the "per row" n_tup_hot_upd counter
is not sufficient. When you have a table with 10 indexes, and the
counter increases by 1, does that mean the update added index tuple
to 1 index or 9 of them?

How about having counters similar to n_tup_ins/n_tup_del for indexes
as well? Today it does not make sense because every index gets the
same number of inserts, but WARM will change that.

For example, we could have idx_tup_insert and idx_tup_delete that shows
up in pg_stat_user_indexes. I don't know if idx_tup_delete adds any
value, but one can then look at idx_tup_insert for various indexes to
get a sense which indexes receives more inserts than others. The indexes
which receive more inserts are the ones being frequently updated as
compared to other indexes.

Hmmm, I'm not sure that'll work. I mean, those metrics would be useful
(although I can't think of a use case for idx_tup_delete), but I'm not
sure it's a enough to measure WARM. We need to compute

index_tuples_inserted / index_tuples_total

where (index_tuples_total - index_tuples_inserted) is the number of
index tuples we've been able to skip thanks to WARM. So we'd also need
to track the number of index tuples that we skipped for the index, and
I'm not sure that's a good idea.

Also, we really don't care about inserted tuples - what matters for WARM
are updates, so idx_tup_insert is either useless (because it also
includes non-UPDATE entries) or the naming is misleading.

This also relates to vacuuming strategies. Today HOT updates do not
count for triggering vacuum (or to be more precise, HOT pruned tuples
are discounted while counting dead tuples). WARM tuples get the same
treatment as far as pruning is concerned, but since they cause fresh
index inserts, I wonder if we need some mechanism to cleanup the dead
line pointers and dead index entries. This will become more important if
we do something to convert WARM chains into HOT chains, something that
only VACUUM can do in the design I've proposed so far.

True.

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, 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

Thanks for the patch. This shows a very good performance improvement.

I started reviewing the patch, during this process and I ran the regression
test on the WARM patch. I observed a failure in create_index test.
This may be a bug in code or expected that needs to be corrected.

Regards,
Hari Babu
Fujitsu Australia

On Tue, Nov 8, 2016 at 9:13 AM, Haribabu Kommi <kommi.haribabu@gmail.com>
wrote:

Thanks for the patch. This shows a very good performance improvement.

Thank you. Can you please share the benchmark you ran, results and
observations?

I started reviewing the patch, during this process and I ran the regression
test on the WARM patch. I observed a failure in create_index test.
This may be a bug in code or expected that needs to be corrected.

Can you please share the diff? I ran regression after applying patch on the
current master and did not find any change? Does it happen consistently?

I'm also attaching fresh set of patches. The first patch hasn't changed at
all (though I changed the name to v5 to keep it consistent with the other
patch). The second patch has the following changes:

1. WARM updates are now tracked separately. We still don't count number of
index inserts separately as suggested by Tomas.
2. We don't do a WARM update if all columns referenced by all indexes have
changed. Ideally, we should check if all indexes will require an update and
avoid WARM. So there is still some room for improvement here
3. I added a very minimal regression test case. But really, it just
contains one test case which I specifically wanted to test.

So not a whole lot of changes since the last version. I'm still waiting for
some serious review of the design/code before I spend a lot more time on
the patch. I hope the patch receives some attention in this CF.

Thanks,
Pavan

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

On Sat, Nov 12, 2016 at 10:12 PM, Pavan Deolasee <pavan.deolasee@gmail.com>
wrote:

On Tue, Nov 8, 2016 at 9:13 AM, Haribabu Kommi <kommi.haribabu@gmail.com>
wrote:

Thanks for the patch. This shows a very good performance improvement.

Thank you. Can you please share the benchmark you ran, results and
observations?

I just ran a performance test on my laptop with minimal configuration, it
didn't show much
improvement, currently I don't have access to a big machine to test the
performance.

I started reviewing the patch, during this process and I ran the regression

test on the WARM patch. I observed a failure in create_index test.
This may be a bug in code or expected that needs to be corrected.

Can you please share the diff? I ran regression after applying patch on
the current master and did not find any change? Does it happen consistently?

Yes, it is happening consistently. I ran the make installcheck. Attached
the regression.diffs file with the failed test.
I applied the previous warm patch on this commit -
e3e66d8a9813d22c2aa027d8f373a96d4d4c1b15

Regards,
Hari Babu
Fujitsu Australia

On Tue, Nov 15, 2016 at 5:58 PM, Haribabu Kommi <kommi.haribabu@gmail.com>
wrote:

On Sat, Nov 12, 2016 at 10:12 PM, Pavan Deolasee <pavan.deolasee@gmail.com

wrote:

On Tue, Nov 8, 2016 at 9:13 AM, Haribabu Kommi <kommi.haribabu@gmail.com>
wrote:

Thanks for the patch. This shows a very good performance improvement.

Thank you. Can you please share the benchmark you ran, results and
observations?

I just ran a performance test on my laptop with minimal configuration, it
didn't show much
improvement, currently I don't have access to a big machine to test the
performance.

I started reviewing the patch, during this process and I ran the

regression
test on the WARM patch. I observed a failure in create_index test.
This may be a bug in code or expected that needs to be corrected.

Can you please share the diff? I ran regression after applying patch on
the current master and did not find any change? Does it happen consistently?

Yes, it is happening consistently. I ran the make installcheck. Attached
the regression.diffs file with the failed test.
I applied the previous warm patch on this commit
- e3e66d8a9813d22c2aa027d8f373a96d4d4c1b15

Are you able to reproduce the issue?

Currently the patch is moved to next CF with "needs review" state.

Regards,
Hari Babu
Fujitsu Australia

On Fri, Dec 2, 2016 at 8:34 AM, Haribabu Kommi <kommi.haribabu@gmail.com>
wrote:

On Tue, Nov 15, 2016 at 5:58 PM, Haribabu Kommi <kommi.haribabu@gmail.com>
wrote:

Yes, it is happening consistently. I ran the make installcheck. Attached
the regression.diffs file with the failed test.
I applied the previous warm patch on this commit
- e3e66d8a9813d22c2aa027d8f373a96d4d4c1b15

Are you able to reproduce the issue?

Apologies for the delay. I could reproduce this on a different environment.
It was a case of uninitialised variable and hence the inconsistent results.

I've updated the patches after fixing the issue. Multiple rounds of
regression passes for me without any issue. Please let me know if it works
for you.

Currently the patch is moved to next CF with "needs review" state.

Thanks,
Pavan

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

I noticed that this patch changes HeapSatisfiesHOTAndKeyUpdate() by
adding one more set of attributes to check, and one more output boolean
flag. My patch to add indirect indexes also modifies that routine to
add the same set of things. I think after committing both these
patches, the API is going to be fairly ridiculous. I propose to use a
different approach.

With your WARM and my indirect indexes, plus the additions for for-key
locks, plus identity columns, there is no longer a real expectation that
we can exit early from the function. In your patch, as well as mine,
there is a semblance of optimization that tries to avoid computing the
updated_attrs output bitmapset if the pointer is not passed in, but it's
effectively pointless because the only interesting use case is from
ExecUpdate() which always activates the feature. Can we just agree to
drop that?

If we do drop that, then the function can become much simpler: compare
all columns in new vs. old, return output bitmapset of changed columns.
Then "satisfies_hot" and all the other boolean output flags can be
computed simply in the caller by doing bms_overlap().

Thoughts?

--
�lvaro Herrera https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, 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

Alvaro Herrera wrote:

With your WARM and my indirect indexes, plus the additions for for-key
locks, plus identity columns, there is no longer a real expectation that
we can exit early from the function. In your patch, as well as mine,
there is a semblance of optimization that tries to avoid computing the
updated_attrs output bitmapset if the pointer is not passed in, but it's
effectively pointless because the only interesting use case is from
ExecUpdate() which always activates the feature. Can we just agree to
drop that?

I think the only case that gets worse is the path that does
simple_heap_update, which is used for DDL. I would be very surprised if
a change there is noticeable, when compared to the rest of the stuff
that goes on for DDL commands.

Now, after saying that, I think that a table with a very large number of
columns is going to be affected by this. But we don't really need to
compute the output bits for every single column -- we only care about
those that are covered by some index. So we should pass an input
bitmapset comprising all such columns, and the output bitmapset only
considers those columns, and ignores columns not indexed. My patch for
indirect indexes already does something similar (though it passes a
bitmapset of columns indexed by indirect indexes only, so it needs a
tweak there.)

--
�lvaro Herrera https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, 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