Re: vacuum, performance, and MVCC

We all know that PostgreSQL suffers performance problems when rows are
updated frequently prior to a vacuum. The most serious example can be seen
by using PostgreSQL as a session handler for a busy we site. You may have
thousands or millions of active sessions, each being updated per page hit.

Each time the record is updated, a new version is created, thus
lengthening the "correct" version search each time row is accessed, until,
of course, the next vacuum comes along and corrects the index to point to
the latest version of the record.

Is that a fair explanation?

If my assertion is fundimentally true, then PostgreSQL will always suffer
performance penalties under a heavy modification load. Of course, tables
with many inserts are not an issue, it is mainly updates. The problem is
that there are classes of problems where updates are the primary
operation.

I was thinking, just as a hypothetical, what if we reversed the problem,
and always referenced the newest version of a row and scanned backwards
across the versions to the first that has a lower transacton number?

One possible implementation: PostgreSQL could keep an indirection array of
index to table ref for use by all the indexes on a table. The various
indexes return offsets into the array, not direct table refs. Because the
table refs are separate from the index, they can be updated each time a
transaction is commited.

This way, the newest version of a row is always the first row found. Also,
on a heavily updated site, the most used rows would always be at the end
of the table, reducing amount of disk reads or cache memory required to
find the correct row version for each query.

Clinging to sanity, pgsql(at)mohawksoft(dot)com ("Mark Woodward") mumbled into her beard:
> We all know that PostgreSQL suffers performance problems when rows are
> updated frequently prior to a vacuum. The most serious example can be seen
> by using PostgreSQL as a session handler for a busy we site. You may have
> thousands or millions of active sessions, each being updated per page hit.
>
> Each time the record is updated, a new version is created, thus
> lengthening the "correct" version search each time row is accessed, until,
> of course, the next vacuum comes along and corrects the index to point to
> the latest version of the record.
>
> Is that a fair explanation?

No, it's not.

1. The index points to all the versions, until they get vacuumed out.

2. There may simultaneously be multiple "correct" versions. The
notion that there is one version that is The Correct One is wrong, and
you need to get rid of that thought.

> If my assertion is fundimentally true, then PostgreSQL will always suffer
> performance penalties under a heavy modification load. Of course, tables
> with many inserts are not an issue, it is mainly updates. The problem is
> that there are classes of problems where updates are the primary
> operation.

The trouble with your assertion is that it is true for *all* database
systems except for those whose only transaction mode is READ
UNCOMMITTED, where the only row visible is the "Latest" version.

> I was thinking, just as a hypothetical, what if we reversed the
> problem, and always referenced the newest version of a row and
> scanned backwards across the versions to the first that has a lower
> transacton number?

That would require an index on transaction number, which is an
additional data structure not in place now. That would presumably
worsen things.

> One possible implementation: PostgreSQL could keep an indirection array of
> index to table ref for use by all the indexes on a table. The various
> indexes return offsets into the array, not direct table refs. Because the
> table refs are separate from the index, they can be updated each time a
> transaction is commited.

You mean, this index would be "VACUUMed" as a part of each transaction
COMMIT? I can't see that turning out well...

> This way, the newest version of a row is always the first row
> found. Also, on a heavily updated site, the most used rows would
> always be at the end of the table, reducing amount of disk reads or
> cache memory required to find the correct row version for each
> query.

I can't see how it follows that most-used rows would migrate to the
end of the table. That would only be true in a database that is never
VACUUMed; as soon as a VACUUM is done, free space opens up in the
interior, so that new tuples may be placed in the "interior."
--
If this was helpful, <http://svcs.affero.net/rm.php?r=cbbrowne> rate me
http://linuxdatabases.info/info/lisp.html
"On a normal ascii line, the only safe condition to detect is a
'BREAK' - everything else having been assigned functions by Gnu
EMACS." -- Tarl Neustaedter

> Clinging to sanity, pgsql(at)mohawksoft(dot)com ("Mark Woodward") mumbled into
> her beard:
>> We all know that PostgreSQL suffers performance problems when rows are
>> updated frequently prior to a vacuum. The most serious example can be
>> seen
>> by using PostgreSQL as a session handler for a busy we site. You may
>> have
>> thousands or millions of active sessions, each being updated per page
>> hit.
>>
>> Each time the record is updated, a new version is created, thus
>> lengthening the "correct" version search each time row is accessed,
>> until,
>> of course, the next vacuum comes along and corrects the index to point
>> to
>> the latest version of the record.
>>
>> Is that a fair explanation?
>
> No, it's not.
>
> 1. The index points to all the versions, until they get vacuumed out.

It can't point to "all" versions, it points to the last "current" version
as updated by vacuum, or the first version of the row.

>
> 2. There may simultaneously be multiple "correct" versions. The
> notion that there is one version that is The Correct One is wrong, and
> you need to get rid of that thought.

Sorry, this is misunderstanding. By "correct version search" it was
implied "for this transaction." Later I mention finding the first row with
a transaction lower than the current.

>
>> If my assertion is fundimentally true, then PostgreSQL will always
>> suffer
>> performance penalties under a heavy modification load. Of course, tables
>> with many inserts are not an issue, it is mainly updates. The problem is
>> that there are classes of problems where updates are the primary
>> operation.
>
> The trouble with your assertion is that it is true for *all* database
> systems except for those whose only transaction mode is READ
> UNCOMMITTED, where the only row visible is the "Latest" version.

Not true. Oracle does not seem to exhibit this problem.

>
>> I was thinking, just as a hypothetical, what if we reversed the
>> problem, and always referenced the newest version of a row and
>> scanned backwards across the versions to the first that has a lower
>> transacton number?
>
> That would require an index on transaction number, which is an
> additional data structure not in place now. That would presumably
> worsen things.

All things being equal, perhaps not. It would proably be a loser if you
have a static database, but in a database that undergoes modification, it
would be the same or less work if the average row has two versions.
(assuming nothing else changes)
>
>> One possible implementation: PostgreSQL could keep an indirection array
>> of
>> index to table ref for use by all the indexes on a table. The various
>> indexes return offsets into the array, not direct table refs. Because
>> the
>> table refs are separate from the index, they can be updated each time a
>> transaction is commited.
>
> You mean, this index would be "VACUUMed" as a part of each transaction
> COMMIT? I can't see that turning out well...

No, it would not be vacuumed!!!

Right now, the indexes point to the lowest row version. When an index
returns the row ID, it is checked if there are newer versions, if so, the
newer versions are searched until the last one is found or exceeds the
current TID.

>
>> This way, the newest version of a row is always the first row
>> found. Also, on a heavily updated site, the most used rows would
>> always be at the end of the table, reducing amount of disk reads or
>> cache memory required to find the correct row version for each
>> query.
>
> I can't see how it follows that most-used rows would migrate to the
> end of the table.

Sorry, OK, as assumtion it ignores the FSM, but the idea is that there is
only one lookup.

> That would only be true in a database that is never
> VACUUMed; as soon as a VACUUM is done, free space opens up in the
> interior, so that new tuples may be placed in the "interior."

Regardless, the point is that you have to search the [N] versions of a row
to find the latest correct version of the row for your transacation. This
is done, AFAICT, from first to last version, meaning that the work
required to find a row increases with every update prior to vacuum.

PostgreSQL fails miserably as a web session handler because of this
behavior and it requires too frequent vacuums and inconsistent
performance.

OK, forget the version array, it was just an off the top idea. How about
this:

Currently a row does this:

row_TID[0] -> row_TID[1] ->row_TID[2] ./. row_TID[LAST-1] -> row_TID[LAST]

Pointing to each subsequent row. What if it did this:

row_TID[0] -> row_TID[LAST] -> row_TID[LAST-1] ./. -> row_TID[2] ->
row_TID[1]

The base tuple of a version chain gets updated to point to the latest
commited row. It should be fairly low impact on performance on a static
database, but REALLY speed up PostgreSQL on a heavily modified database
and provide more consistent performance between vacuums and require fewer
vacuums to maintain performance.

After a long battle with technology, pgsql(at)mohawksoft(dot)com ("Mark Woodward"), an earthling, wrote:
>> Clinging to sanity, pgsql(at)mohawksoft(dot)com ("Mark Woodward") mumbled into
>> her beard:
>>> We all know that PostgreSQL suffers performance problems when rows are
>>> updated frequently prior to a vacuum. The most serious example can be
>>> seen
>>> by using PostgreSQL as a session handler for a busy we site. You may
>>> have
>>> thousands or millions of active sessions, each being updated per page
>>> hit.
>>>
>>> Each time the record is updated, a new version is created, thus
>>> lengthening the "correct" version search each time row is accessed,
>>> until,
>>> of course, the next vacuum comes along and corrects the index to point
>>> to
>>> the latest version of the record.
>>>
>>> Is that a fair explanation?
>>
>> No, it's not.
>>
>> 1. The index points to all the versions, until they get vacuumed out.
>
> It can't point to "all" versions, it points to the last "current" version
> as updated by vacuum, or the first version of the row.

No, it points to *all* the versions.

Suppose I take a table with two rows:

INFO: analyzing "public.test"
INFO: "test": 1 pages, 2 rows sampled, 2 estimated total rows
VACUUM

Then, over and over, I remove and insert one entry with the same PK:

sample=# delete from test where id = 2;insert into test (id) values (2);
DELETE 1
INSERT 4842550 1
sample=# delete from test where id = 2;insert into test (id) values (2);
DELETE 1
INSERT 4842551 1
sample=# delete from test where id = 2;insert into test (id) values (2);
DELETE 1
INSERT 4842552 1
sample=# delete from test where id = 2;insert into test (id) values (2);
DELETE 1
INSERT 4842553 1
sample=# delete from test where id = 2;insert into test (id) values (2);
DELETE 1
INSERT 4842554 1
sample=# delete from test where id = 2;insert into test (id) values (2);
DELETE 1
INSERT 4842555 1
sample=# delete from test where id = 2;insert into test (id) values (2);
DELETE 1
INSERT 4842556 1
sample=# delete from test where id = 2;insert into test (id) values (2);
DELETE 1
INSERT 4842557 1
sample=# delete from test where id = 2;insert into test (id) values (2);
DELETE 1
INSERT 4842558 1
sample=# delete from test where id = 2;insert into test (id) values (2);
DELETE 1
INSERT 4842559 1

Now, I vacuum it.

sample=# vacuum verbose analyze test;
INFO: vacuuming "public.test"
INFO: index "test_id_key" now contains 2 row versions in 2 pages
DETAIL: 10 index row versions were removed.
0 index pages have been deleted, 0 are currently reusable.
CPU 0.00s/0.00u sec elapsed 0.00 sec.
INFO: "test": removed 10 row versions in 1 pages
DETAIL: CPU 0.00s/0.00u sec elapsed 0.00 sec.
INFO: "test": found 10 removable, 2 nonremovable row versions in 1 pages
DETAIL: 0 dead row versions cannot be removed yet.
There were 0 unused item pointers.
0 pages are entirely empty.
CPU 0.00s/0.00u sec elapsed 0.00 sec.
INFO: analyzing "public.test"
INFO: "test": 1 pages, 2 rows sampled, 2 estimated total rows
VACUUM

Notice that the index contained 10 versions of that one row.

It pointed to *ALL* the versions.

>> 2. There may simultaneously be multiple "correct" versions. The
>> notion that there is one version that is The Correct One is wrong, and
>> you need to get rid of that thought.
>
> Sorry, this is misunderstanding. By "correct version search" it was
> implied "for this transaction." Later I mention finding the first row with
> a transaction lower than the current.

Ah. Then you need for each transaction to spawn an index for each
table that excludes non-current values.

>>> If my assertion is fundimentally true, then PostgreSQL will always
>>> suffer performance penalties under a heavy modification load. Of
>>> course, tables with many inserts are not an issue, it is mainly
>>> updates. The problem is that there are classes of problems where
>>> updates are the primary operation.
>>
>> The trouble with your assertion is that it is true for *all* database
>> systems except for those whose only transaction mode is READ
>> UNCOMMITTED, where the only row visible is the "Latest" version.
>
> Not true. Oracle does not seem to exhibit this problem.

Oracle suffers a problem in this regard that PostgreSQL doesn't; in
Oracle, rollbacks are quite expensive, as "recovery" requires doing
extra work that PostgreSQL doesn't do.
--
output = ("cbbrowne" "@" "gmail.com")
http://cbbrowne.com/info/
Marriage means commitment. Of course, so does insanity.

Mark Woodward wrote:

> Hmm, OK, then the problem is more serious than I suspected.
> This means that every index on a row has to be updated on every
> transaction that modifies that row. Is that correct?

Add an index entry, yes.

> I am attaching some code that shows the problem with regard to
> applications such as web server session management, when run, each second
> the system can handle fewer and fewer connections. Here is a brief output:
> [...]
> There has to be a more linear way of handling this scenario.

So vacuum the table often.

--
Alvaro Herrera http://www.CommandPrompt.com/
PostgreSQL Replication, Consulting, Custom Development, 24x7 support

> After a long battle with technology, pgsql(at)mohawksoft(dot)com ("Mark
> Woodward"), an earthling, wrote:
>>> Clinging to sanity, pgsql(at)mohawksoft(dot)com ("Mark Woodward") mumbled into
>>> her beard:
[snip]
>>>
>>> 1. The index points to all the versions, until they get vacuumed out.
>>
>> It can't point to "all" versions, it points to the last "current"
>> version
>> as updated by vacuum, or the first version of the row.
>
> No, it points to *all* the versions.
>
> Suppose I take a table with two rows:
>
> INFO: analyzing "public.test"
> INFO: "test": 1 pages, 2 rows sampled, 2 estimated total rows
> VACUUM
>
> Then, over and over, I remove and insert one entry with the same PK:
>
> sample=# delete from test where id = 2;insert into test (id) values (2);
> DELETE 1

[snip]
>
> Now, I vacuum it.
>
> sample=# vacuum verbose analyze test;
> INFO: vacuuming "public.test"
> INFO: index "test_id_key" now contains 2 row versions in 2 pages
> DETAIL: 10 index row versions were removed.
> 0 index pages have been deleted, 0 are currently reusable.
> CPU 0.00s/0.00u sec elapsed 0.00 sec.
> INFO: "test": removed 10 row versions in 1 pages
> DETAIL: CPU 0.00s/0.00u sec elapsed 0.00 sec.
> INFO: "test": found 10 removable, 2 nonremovable row versions in 1 pages
> DETAIL: 0 dead row versions cannot be removed yet.
> There were 0 unused item pointers.
> 0 pages are entirely empty.
> CPU 0.00s/0.00u sec elapsed 0.00 sec.
> INFO: analyzing "public.test"
> INFO: "test": 1 pages, 2 rows sampled, 2 estimated total rows
> VACUUM
>
> Notice that the index contained 10 versions of that one row.
>
> It pointed to *ALL* the versions.

Hmm, OK, then the problem is more serious than I suspected.
This means that every index on a row has to be updated on every
transaction that modifies that row. Is that correct?

I am attaching some code that shows the problem with regard to
applications such as web server session management, when run, each second
the system can handle fewer and fewer connections. Here is a brief output:

markw(at)ent:~/pgfoo$ ./footest
1307 sessions per second, elapsed: 1
1292 sessions per second, elapsed: 2
1287 sessions per second, elapsed: 3
....
1216 sessions per second, elapsed: 25
1213 sessions per second, elapsed: 26
1208 sessions per second, elapsed: 27
....
1192 sessions per second, elapsed: 36
1184 sessions per second, elapsed: 37
1183 sessions per second, elapsed: 38
....
1164 sessions per second, elapsed: 58
1170 sessions per second, elapsed: 59
1168 sessions per second, elapsed: 60

As you can see, in about a minute at high load, this very simple table
lost about 10% of its performance, and I've seen worse based on update
frequency. Before you say this is an obscure problem, I can tell you it
isn't. I have worked with more than a few projects that had to switch away
from PostgreSQL because of this behavior.

Obviously this is not a problem with small sites, but this is a real
problem with an enterprise level web site with millions of visitors and
actions a day. Quite frankly it is a classic example of something that
does not scale. The more and more updates there are, the higher the load
becomes. You can see it on "top" as the footest program runs.

There has to be a more linear way of handling this scenario.

> > [...]
> > There has to be a more linear way of handling this scenario.
>
> So vacuum the table often.

Good advice, except if the table is huge :-)

Here we have for example some tables which are frequently updated but
contain >100 million rows. Vacuuming that takes hours. And the dead row
candidates are the ones which are updated again and again and looked up
frequently...

A good solution would be a new type of vacuum which does not need to do
a full table scan but can clean the pending dead rows without that... I
guess then I could vacuum really frequently those tables.

Cheers,
Csaba.

On 6/22/06, Alvaro Herrera <alvherre(at)commandprompt(dot)com> wrote:
> > Hmm, OK, then the problem is more serious than I suspected.
> > This means that every index on a row has to be updated on every
> > transaction that modifies that row. Is that correct?
>
> Add an index entry, yes.

Again, this is a case for update-in-place. No need to write an extra
index entry and incur the WAL associated with it. Imagine a table
with 3 indexes on it... I would estimate that we perform at least 3 to
6 times more overhead than any commercial database on such an update.

> > There has to be a more linear way of handling this scenario.
>
> So vacuum the table often.

It's easy to say VACUUM often... but I'd bet that vacuuming is going
to lessen the throughput in his tests even more; no matter how it's
tuned.

--
Jonah H. Harris, Software Architect | phone: 732.331.1300
EnterpriseDB Corporation | fax: 732.331.1301
33 Wood Ave S, 2nd Floor | jharris(at)enterprisedb(dot)com
Iselin, New Jersey 08830 | http://www.enterprisedb.com/

Am Donnerstag, 22. Juni 2006 16:09 schrieb Csaba Nagy:
> > > [...]
> > > There has to be a more linear way of handling this scenario.
> >
> > So vacuum the table often.
>
> Good advice, except if the table is huge :-)
>
> Here we have for example some tables which are frequently updated but
> contain >100 million rows. Vacuuming that takes hours. And the dead row
> candidates are the ones which are updated again and again and looked up
> frequently...
>
> A good solution would be a new type of vacuum which does not need to do
> a full table scan but can clean the pending dead rows without that... I
> guess then I could vacuum really frequently those tables.

Now that there is autovaccum, why not think of something like continous
vacuum? A background process that gets info about potential changed tuples,
and vacuums them (only those tuples), possibly with honouring I/O needs of
backgrounds (not steealing I/O from busy backends).

For sure not that easy as autovacuum. I'm pretty sure I've read something
about partial vacuum lately, is somebody working on something like this?

Regards,
Mario

Ühel kenal päeval, N, 2006-06-22 kell 09:59, kirjutas Mark Woodward:
> > After a long battle with technology, pgsql(at)mohawksoft(dot)com ("Mark
> > Woodward"), an earthling, wrote:
> >>> Clinging to sanity, pgsql(at)mohawksoft(dot)com ("Mark Woodward") mumbled into
> > It pointed to *ALL* the versions.
>
> Hmm, OK, then the problem is more serious than I suspected.
> This means that every index on a row has to be updated on every
> transaction that modifies that row. Is that correct?

Yes.

> I am attaching some code that shows the problem with regard to
> applications such as web server session management, when run, each second
> the system can handle fewer and fewer connections. Here is a brief output:
>
> markw(at)ent:~/pgfoo$ ./footest
> 1307 sessions per second, elapsed: 1
> 1292 sessions per second, elapsed: 2
> 1287 sessions per second, elapsed: 3
> ....
> 1216 sessions per second, elapsed: 25
> 1213 sessions per second, elapsed: 26
> 1208 sessions per second, elapsed: 27
> ....
> 1192 sessions per second, elapsed: 36
> 1184 sessions per second, elapsed: 37
> 1183 sessions per second, elapsed: 38
> ....
> 1164 sessions per second, elapsed: 58
> 1170 sessions per second, elapsed: 59
> 1168 sessions per second, elapsed: 60
>
> As you can see, in about a minute at high load, this very simple table
> lost about 10% of its performance, and I've seen worse based on update
> frequency. Before you say this is an obscure problem, I can tell you it
> isn't. I have worked with more than a few projects that had to switch away
> from PostgreSQL because of this behavior.

You mean systems that are designed so exactly, that they can't take 10%
performance change ?

Or just that they did not vacuum for so long, that performance was less
than needed in the end?

btw, what did they switch to ?

> Obviously this is not a problem with small sites, but this is a real
> problem with an enterprise level web site with millions of visitors and
> actions a day.

On such site you should design so that db load stays below 50% and run
vacuum "often", that may even mean that you run vacuum continuously with
no wait between runs. If you run vacuum with right settings,

> Quite frankly it is a classic example of something that
> does not scale. The more and more updates there are, the higher the load
> becomes. You can see it on "top" as the footest program runs.

Yes, you understood correctly - the more updates, the higher the load :)

--
----------------
Hannu Krosing
Database Architect
Skype Technologies OÜ
Akadeemia tee 21 F, Tallinn, 12618, Estonia

Skype me: callto:hkrosing
Get Skype for free: http://www.skype.com

Ühel kenal päeval, N, 2006-06-22 kell 10:20, kirjutas Jonah H. Harris:
> On 6/22/06, Alvaro Herrera <alvherre(at)commandprompt(dot)com> wrote:
> > > Hmm, OK, then the problem is more serious than I suspected.
> > > This means that every index on a row has to be updated on every
> > > transaction that modifies that row. Is that correct?
> >
> > Add an index entry, yes.
>
> Again, this is a case for update-in-place. No need to write an extra
> index entry and incur the WAL associated with it.

I guess that MySQL on its original storage does that, but they allow
only one concurrent update per table and no transactions.

> Imagine a table
> with 3 indexes on it... I would estimate that we perform at least 3 to
> 6 times more overhead than any commercial database on such an update.

One way to describe what "commercial databases" do to keep constant
update rates is saying that they do either vacuuming as part of
update, or they just use locks anf force some transactions to wait or
fail/retry.

Depending on exact details and optimisations done, this can be either
slower or faster than postgresql's way, but they still need to do
something to get transactional visibility rules implemented.

> > > There has to be a more linear way of handling this scenario.
> >
> > So vacuum the table often.
>
> It's easy to say VACUUM often... but I'd bet that vacuuming is going
> to lessen the throughput in his tests even more; no matter how it's
> tuned.

Running VACUUM often/continuously will likely keep his update rate
fluctuatons within a corridor of maybe 5-10%, at the cost of 1-2% extra
load. At least if vacuum is configured right and the server is not
already running at 100% IO saturation, in which case it will be worse.

The max throughput figure is not something you actually need very often
in production. What is interesting is setting up the server so that you
can service your loads comfortably. Running the server at 100% lead is
not anything you want to do on production server. There will be things
you need to do anyway and you need some headroom for that.

--
----------------
Hannu Krosing
Database Architect
Skype Technologies OÜ
Akadeemia tee 21 F, Tallinn, 12618, Estonia

Skype me: callto:hkrosing
Get Skype for free: http://www.skype.com

nagy(at)ecircle-ag(dot)com (Csaba Nagy) writes:

>> > [...]
>> > There has to be a more linear way of handling this scenario.
>>
>> So vacuum the table often.
>
> Good advice, except if the table is huge :-)

... Then the table shouldn't be designed to be huge. That represents
a design error.

> Here we have for example some tables which are frequently updated but
> contain >100 million rows. Vacuuming that takes hours. And the dead row
> candidates are the ones which are updated again and again and looked up
> frequently...

This demonstrates that "archival" material and "active" data should be
kept separately.

They have different access patterns; kludging them into the same table
turns out badly.

> A good solution would be a new type of vacuum which does not need to
> do a full table scan but can clean the pending dead rows without
> that... I guess then I could vacuum really frequently those tables.

That's yet another feature that's on the ToDo list; the "Vacuum Space
Map."

The notion is to have lists of recently modified pages, and to
restrict VACUUM to those pages. (Probably a special version of
VACUUM...)
--
output = reverse("moc.enworbbc" "@" "enworbbc")
http://www.ntlug.org/~cbbrowne/lisp.html
"As I've gained more experience with Perl it strikes me that it
resembles Lisp in many ways, albeit Lisp as channeled by an awk script
on acid." -- Tim Moore (on comp.lang.lisp)

On 6/22/06, Hannu Krosing <hannu(at)skype(dot)net> wrote:
> I guess that MySQL on its original storage does that, but they allow
> only one concurrent update per table and no transactions.

More like practically every commercial database. As ~97% of
transactions commit (yes, some can argue that number), most commercial
systems prefer optimistic storage managers; whereas PostgreSQL opts
for the ~3% of pessimistic cases.

Let's see, if I had a 97% chance of winning the lottery... I'd
probably play a lot more than if I only had a 3% chance.

> One way to describe what "commercial databases" do to keep constant
> update rates is saying that they do either vacuuming as part of
> update, or they just use locks anf force some transactions to wait or
> fail/retry.

Not exactly... there are several ways to handle UNDO without locking.
Certainly the other systems have to perform background cleanup, but
I'd hardly compare that to vacuuming.

> Depending on exact details and optimisations done, this can be either
> slower or faster than postgresql's way, but they still need to do
> something to get transactional visibility rules implemented.

No argument there... but I have yet to find proof that
straight-out-of-CVS PostgreSQL (including tuning) is faster than any
commercial system on almost any large workload. Without a doubt, our
MVCC is in most cases, much nicer than other OSS databases. However,
it hasn't yet proven itself to be better than the concepts employed by
the database vendors with billions of dollars. The reasoning behind
PostgreSQL's storage and MVCC architecture made sense for its design,
but this had nothing to do with creating a super-highly-concurrent
database.

> Running the server at 100% lead is not anything you want to
> do on production server. There will be things you need to
> do anyway and you need some headroom for that.

No argument there.

--
Jonah H. Harris, Software Architect | phone: 732.331.1300
EnterpriseDB Corporation | fax: 732.331.1301
33 Wood Ave S, 2nd Floor | jharris(at)enterprisedb(dot)com
Iselin, New Jersey 08830 | http://www.enterprisedb.com/

> Ühel kenal päeval, N, 2006-06-22 kell 09:59, kirjutas Mark Woodward:
>> > After a long battle with technology, pgsql(at)mohawksoft(dot)com ("Mark
>> > Woodward"), an earthling, wrote:
>> >>> Clinging to sanity, pgsql(at)mohawksoft(dot)com ("Mark Woodward") mumbled
>> into
>> > It pointed to *ALL* the versions.
>>
>> Hmm, OK, then the problem is more serious than I suspected.
>> This means that every index on a row has to be updated on every
>> transaction that modifies that row. Is that correct?
>
> Yes.
>
>> I am attaching some code that shows the problem with regard to
>> applications such as web server session management, when run, each
>> second
>> the system can handle fewer and fewer connections. Here is a brief
>> output:
>>
>> markw(at)ent:~/pgfoo$ ./footest
>> 1307 sessions per second, elapsed: 1
>> 1292 sessions per second, elapsed: 2
>> 1287 sessions per second, elapsed: 3
>> ....
>> 1216 sessions per second, elapsed: 25
>> 1213 sessions per second, elapsed: 26
>> 1208 sessions per second, elapsed: 27
>> ....
>> 1192 sessions per second, elapsed: 36
>> 1184 sessions per second, elapsed: 37
>> 1183 sessions per second, elapsed: 38
>> ....
>> 1164 sessions per second, elapsed: 58
>> 1170 sessions per second, elapsed: 59
>> 1168 sessions per second, elapsed: 60
>>
>> As you can see, in about a minute at high load, this very simple table
>> lost about 10% of its performance, and I've seen worse based on update
>> frequency. Before you say this is an obscure problem, I can tell you it
>> isn't. I have worked with more than a few projects that had to switch
>> away
>> from PostgreSQL because of this behavior.
>
> You mean systems that are designed so exactly, that they can't take 10%
> performance change ?

No, that's not really the point, performance degrades over time, in one
minute it degraded 10%.

The update to session ratio has a HUGE impact on PostgreSQL. If you have a
thousand active sessions, it may take a minute to degrade 10% assuming
some level of active vs operations per session per action.

If an active user causes a session update once a second, that is not too
bad, but if an active user updates a session more often, then it is worse.

Generally speaking, sessions aren't updated when they change, they are
usually updated per HTTP request. The data in a session may not change,
but the session handling code doesn't know this and simply updates anyway.

In a heavily AJAX site, you may have many smaller HTTP requests returning
items in a page. So, a single page may consist of multiple HTTP requests.
Worse yet, as a user drags an image around, there are lots of background
requests being made. Each request typically means a session lookup and a
session update. This is compounded by the number of active users. Since
the object of a site is to have many active users, this is always a
problem. It is less intrusive now that non-locking vacuum is there, but
that doesn't mean it isn't a problem.

>
> Or just that they did not vacuum for so long, that performance was less
> than needed in the end?

In an active site or application, vacuuming often enough to prevent this
often is, itself, a load on the system.

>
> btw, what did they switch to ?

One switched to oracle and one is using a session handler I wrote for PHP.
One company I did work for tried to maintain a table with a single row
that indicated state, this single row would sometimes take more than a
second to query. It was horrible. I'm not sure what they ended up using,
but I wrote a shared memory variable C function got rid of that specific
problem. They were trying to use PostgreSQL as the database to implement a
HUGE redundent networked file system. My personal opinion was that there
biggest problem was that they decided to use Java as the programming
environment, but that's another issue.

>
>> Obviously this is not a problem with small sites, but this is a real
>> problem with an enterprise level web site with millions of visitors and
>> actions a day.
>
> On such site you should design so that db load stays below 50% and run
> vacuum "often", that may even mean that you run vacuum continuously with
> no wait between runs. If you run vacuum with right settings,

Yea, but that, at least in my opinion, is a poor design.
>
>> Quite frankly it is a classic example of something that
>> does not scale. The more and more updates there are, the higher the load
>> becomes. You can see it on "top" as the footest program runs.
>
> Yes, you understood correctly - the more updates, the higher the load :)

Imagine this:

Each row in a table has a single entry that represents that row. Lets call
it the "key" entry. Whether or not the key entry maintains data is an
implementation detail.

When indexing a table, the index always points to the key entry for a row.

When a row is updated, in the spirit of MVCC, a new data row is created.
The key entry is then updated to point to the new version of the row. The
new row points to the previous version of the row, and the previous entry
continues to point to its previous entry, etc.

When a row is found by the index, the key entry is found first. Much more
often than not, the latest entry in the table for a row is the correct row
for a query.

Now this works in the simplest cases, and there are edge conditions where
index keys change, of course, but that's why its called software
development and not typing.

However, this accomplishes a few things, updates become cheaper because
indexes do not need to be updated if the keys don't change, and
performance doesn't degrade based on the number of updates a row has had.

> Ühel kenal päeval, N, 2006-06-22 kell 10:20, kirjutas Jonah H. Harris:
>> On 6/22/06, Alvaro Herrera <alvherre(at)commandprompt(dot)com> wrote:
>> > > Hmm, OK, then the problem is more serious than I suspected.
>> > > This means that every index on a row has to be updated on every
>> > > transaction that modifies that row. Is that correct?
>> >
>> > Add an index entry, yes.
>>
>> Again, this is a case for update-in-place. No need to write an extra
>> index entry and incur the WAL associated with it.
>
> I guess that MySQL on its original storage does that, but they allow
> only one concurrent update per table and no transactions.
>
>> Imagine a table
>> with 3 indexes on it... I would estimate that we perform at least 3 to
>> 6 times more overhead than any commercial database on such an update.
>
> One way to describe what "commercial databases" do to keep constant
> update rates is saying that they do either vacuuming as part of
> update, or they just use locks anf force some transactions to wait or
> fail/retry.
>
> Depending on exact details and optimisations done, this can be either
> slower or faster than postgresql's way, but they still need to do
> something to get transactional visibility rules implemented.

I think they have a different strategy. I think they maintain the notion
of "current version" of a row, and hunt for previous versions when needed,
at least that's how I suspect Oracle does it with redo logs.

>
>> > > There has to be a more linear way of handling this scenario.
>> >
>> > So vacuum the table often.
>>
>> It's easy to say VACUUM often... but I'd bet that vacuuming is going
>> to lessen the throughput in his tests even more; no matter how it's
>> tuned.
>
> Running VACUUM often/continuously will likely keep his update rate
> fluctuatons within a corridor of maybe 5-10%, at the cost of 1-2% extra
> load. At least if vacuum is configured right and the server is not
> already running at 100% IO saturation, in which case it will be worse.

Assuming the table is a reasonable size, the I/O required for vacuum
doesn't kill everything else!
>
> The max throughput figure is not something you actually need very often
> in production.

No, but you need to have some degree of certainty and predictability in
the system you are developing.

> What is interesting is setting up the server so that you
> can service your loads comfortably. Running the server at 100% lead is
> not anything you want to do on production server. There will be things
> you need to do anyway and you need some headroom for that.

Of course, you design it so peaks are easily managed, but unless you run
vacuum continuously, and that has its own set of problems, you run into
this problem, and it can get really really bad.

>
> --
> ----------------
> Hannu Krosing
> Database Architect
> Skype Technologies OÜ
> Akadeemia tee 21 F, Tallinn, 12618, Estonia
>
> Skype me: callto:hkrosing
> Get Skype for free: http://www.skype.com
>
>
>
> ---------------------------(end of broadcast)---------------------------
> TIP 4: Have you searched our list archives?
>
> http://archives.postgresql.org
>

Christopher Browne <cbbrowne(at)acm(dot)org> writes:
> After a long battle with technology, pgsql(at)mohawksoft(dot)com ("Mark Woodward"), an earthling, wrote:
>> Not true. Oracle does not seem to exhibit this problem.

> Oracle suffers a problem in this regard that PostgreSQL doesn't; in
> Oracle, rollbacks are quite expensive, as "recovery" requires doing
> extra work that PostgreSQL doesn't do.

The Oracle design has got other drawbacks: if you need to access a row
version other than than the very latest, you need to go searching in the
rollback segments for it. This is slow (no index help) and creates
significant amounts of contention (since lots of processes are competing
to touch the rollback segments). Plus there's the old bugaboo that
long-running transactions require indefinite amounts of rollback space,
and Oracle is apparently unable to enlarge that space on-the-fly.
(This last seems like a surmountable problem, but maybe there is some
non-obvious reason why it's hard.)

Basically there's no free lunch: if you want the benefits of MVCC it's
going to cost you somewhere. In the Postgres design you pay by having
to do VACUUM pretty often for heavily-updated tables. I don't think
that decision is fundamentally wrong --- the attractive thing about it
is that the overhead is pushed out of the foreground query-processing
code paths. We still have lots of work to do in making autovacuum
smarter, avoiding vacuuming parts of relations that have not changed,
and so on. But I have no desire to go over to an Oracle-style solution
instead. We can't beat them by trying to be like them, and we run no
small risk of falling foul of some of their patents if we do.

regards, tom lane

On 6/22/06, Mark Woodward wrote:
(..)
> thousand active sessions
(..)
> If an active user causes a session update once a second
(..)
> Generally speaking, sessions aren't updated when they change, they are
> usually updated per HTTP request. The data in a session may not change,
> but the session handling code doesn't know this and simply updates anyway.

So what you are saying is that you are doing hundreds of unnecessary
updates per second and as a result of those unnecessary problems you
have a performance problem. Why not attack the root of the problem and
make the session handler smarter? And if you can't do that, put some
logic in the session table that turns an update without changes into a
no-op?

Jochem

Tom Lane wrote:

> Basically there's no free lunch: if you want the benefits of MVCC it's
> going to cost you somewhere. In the Postgres design you pay by having
> to do VACUUM pretty often for heavily-updated tables. I don't think
> that decision is fundamentally wrong --- the attractive thing about it
> is that the overhead is pushed out of the foreground query-processing
> code paths. We still have lots of work to do in making autovacuum
> smarter, avoiding vacuuming parts of relations that have not changed,
> and so on. But I have no desire to go over to an Oracle-style solution
> instead. We can't beat them by trying to be like them, and we run no
> small risk of falling foul of some of their patents if we do.

The question is just if it makes sense to give people the option of
running some tables with a different approach where the drawbacks of the
current approach are significant. This would let them stick to
PostgreSQL as their one stop solution.

The MySQL storage engine plugin architecture does have some merit in
general (even if you consider the rest of the RDBMS along with the
available storage engines to be inferior). Some problems simply require
different algorithms.

regards,
Lukas

Jochem van Dieten wrote:

> make the session handler smarter? And if you can't do that, put some
> logic in the session table that turns an update without changes into a
> no-op?

err isnt that one the job of the database?

regards,
Lukas

On 6/22/06, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> The Oracle design has got other drawbacks: if you need to access a row
> version other than than the very latest, you need to go searching in the
> rollback segments for it.

There are ways to implement this functionality without implementing it
exactly as Oracle has.

> Plus there's the old bugaboo that long-running transactions
> require indefinite amounts of rollback space, and Oracle is
> apparently unable to enlarge that space on-the-fly.

This has actually gotten much better in recent versions.

> Basically there's no free lunch: if you want the benefits of MVCC it's
> going to cost you somewhere.

Surely. Our MVCC design is great for SELECT, INSERT, and for the most
part, DELETE. However, I'm confident that we can build a hybrid MVCC
model that takes some of the pain out of UPDATE without having to
overcomplicate VACUUM or violate patents.

--
Jonah H. Harris, Software Architect | phone: 732.331.1300
EnterpriseDB Corporation | fax: 732.331.1301
33 Wood Ave S, 2nd Floor | jharris(at)enterprisedb(dot)com
Iselin, New Jersey 08830 | http://www.enterprisedb.com/

On Thu, 22 Jun 2006 19:01:38 +0200
Lukas Smith <smith(at)pooteeweet(dot)org> wrote:

> Jochem van Dieten wrote:
>
> > make the session handler smarter? And if you can't do that, put some
> > logic in the session table that turns an update without changes into a
> > no-op?
>
> err isnt that one the job of the database?

Seems like a lot of work to give the database for special cases. Not
only would it have to compare all fields, it would also have to check
for the behaviour of all rules, triggers and follow chains. Doing this
for each and every update seems like a loss to me.

Some things just make more sense in the framework of the business rules.

--
D'Arcy J.M. Cain <darcy(at)druid(dot)net> | Democracy is three wolves
http://www.druid.net/darcy/ | and a sheep voting on
+1 416 425 1212 (DoD#0082) (eNTP) | what's for dinner.

> > Here we have for example some tables which are frequently updated but
> > contain >100 million rows. Vacuuming that takes hours. And the dead row
> > candidates are the ones which are updated again and again and looked up
> > frequently...
>
> This demonstrates that "archival" material and "active" data should be
> kept separately.
>
> They have different access patterns; kludging them into the same table
> turns out badly.

Rightfully it should be up to the database engine to ensure that both of
these patterns work against the same structure. Splitting up the data
for their access patterns is the job of partitions (hidden from the end
user preferably).

Same table good, same partition and possible same table space is bad.

--

> > You mean systems that are designed so exactly, that they can't take 10%
> > performance change ?
>
> No, that's not really the point, performance degrades over time, in one
> minute it degraded 10%.
>
> The update to session ratio has a HUGE impact on PostgreSQL. If you have a
> thousand active sessions, it may take a minute to degrade 10% assuming
> some level of active vs operations per session per action.

So don't do an update. Multiple updates to the same row block anyway
which is generally not something you want anyway.

If you INSERT into multiple partitions (by time -- say one per minute)
and TRUNCATE periodically (30 minute old partitions for 30 minute
expiry) it works much better. Expiring the session is quite fast as well
since they'll go away with the truncate.

Index on sessionid and time and grab the row with the most recent time.
--

On 6/22/06, Rod Taylor <pg(at)rbt(dot)ca> wrote:
> If you INSERT into multiple partitions (by time -- say one per minute)
> and TRUNCATE periodically (30 minute old partitions for 30 minute
> expiry) it works much better. Expiring the session is quite fast as well
> since they'll go away with the truncate.

Forgive me if this sounds rude because I'm not meaning it as such, but
this suggestion sounds like a MySQL-ish hack. No doubt it would work,
but should an application-writer have to incur the cost of writing
something different because the database can't handle it? I remember
having to write subselect code in PHP because MySQL couldn't do it...
not what I would call a *solution* by any mean.

--
Jonah H. Harris, Software Architect | phone: 732.331.1300
EnterpriseDB Corporation | fax: 732.331.1301
33 Wood Ave S, 2nd Floor | jharris(at)enterprisedb(dot)com
Iselin, New Jersey 08830 | http://www.enterprisedb.com/

On Thu, 2006-06-22 at 13:42 -0400, Jonah H. Harris wrote:
> On 6/22/06, Rod Taylor <pg(at)rbt(dot)ca> wrote:
> > If you INSERT into multiple partitions (by time -- say one per minute)
> > and TRUNCATE periodically (30 minute old partitions for 30 minute
> > expiry) it works much better. Expiring the session is quite fast as well
> > since they'll go away with the truncate.
>
> Forgive me if this sounds rude because I'm not meaning it as such, but
> this suggestion sounds like a MySQL-ish hack. No doubt it would work,
> but should an application-writer have to incur the cost of writing
> something different because the database can't handle it? I remember
> having to write subselect code in PHP because MySQL couldn't do it...
> not what I would call a *solution* by any mean.

Application writer doesn't need to do anything. That's what rules,
views, etc. are for.

The only snag is that PostgreSQL doesn't 'eliminate' a partition by
itself, so the truncate is a manual requirement.

--

> Christopher Browne <cbbrowne(at)acm(dot)org> writes:
>> After a long battle with technology, pgsql(at)mohawksoft(dot)com ("Mark
>> Woodward"), an earthling, wrote:
>>> Not true. Oracle does not seem to exhibit this problem.
>
>> Oracle suffers a problem in this regard that PostgreSQL doesn't; in
>> Oracle, rollbacks are quite expensive, as "recovery" requires doing
>> extra work that PostgreSQL doesn't do.
>
> The Oracle design has got other drawbacks: if you need to access a row
> version other than than the very latest, you need to go searching in the
> rollback segments for it. This is slow (no index help) and creates
> significant amounts of contention (since lots of processes are competing
> to touch the rollback segments).

But, it is all probability, in most cases, the VAST majority, older
versions aren't much needed outside the concurency of of active
transactions.

> Plus there's the old bugaboo that
> long-running transactions require indefinite amounts of rollback space,
> and Oracle is apparently unable to enlarge that space on-the-fly.
> (This last seems like a surmountable problem, but maybe there is some
> non-obvious reason why it's hard.)

Yea, Oracle has a million way to die. And when you think you know all one
million, you find one million and one.

>
> Basically there's no free lunch: if you want the benefits of MVCC it's
> going to cost you somewhere. In the Postgres design you pay by having
> to do VACUUM pretty often for heavily-updated tables. I don't think
> that decision is fundamentally wrong --- the attractive thing about it
> is that the overhead is pushed out of the foreground query-processing
> code paths.

Under certain circumstances, it is a very poor design. Think of a single
row table that keeps a scoreboard or a session table that keeps a limited
number of rows that are updated very frequently.

> We still have lots of work to do in making autovacuum
> smarter, avoiding vacuuming parts of relations that have not changed,
> and so on. But I have no desire to go over to an Oracle-style solution
> instead. We can't beat them by trying to be like them, and we run no
> small risk of falling foul of some of their patents if we do.

I proposed having a "key row entry" for each logical row. The key row
entry points to the latest version of the row. There, each row entry is a
linked list, in descending order, of previous row versions. The vast
majority of the time, the latest version will be the first version. It is
only when you have a previously started long running or concurrent
transaction will you ever look at previous versions.

I'm not saying it is an easy slam dunk, as I can think of a few
difficulties off the top of my head, but it would solve the steady
degradation of performance between vacuums and, to a possibly lesser
extent, the cost of updating a row in a heavily indexed table.

On Thu, 22 Jun 2006, Jonah H. Harris wrote:

> On 6/22/06, Rod Taylor <pg(at)rbt(dot)ca> wrote:
>> If you INSERT into multiple partitions (by time -- say one per minute)
>> and TRUNCATE periodically (30 minute old partitions for 30 minute
>> expiry) it works much better. Expiring the session is quite fast as well
>> since they'll go away with the truncate.
>
> Forgive me if this sounds rude because I'm not meaning it as such, but
> this suggestion sounds like a MySQL-ish hack. No doubt it would work,
> but should an application-writer have to incur the cost of writing
> something different because the database can't handle it? I remember
> having to write subselect code in PHP because MySQL couldn't do it...
> not what I would call a *solution* by any mean.

AFAICS, you could hide it from the application with update rules and
views.

- Heikki

Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> writes:

> The Oracle design has got other drawbacks: if you need to access a row
> version other than than the very latest, you need to go searching in the
> rollback segments for it. This is slow (no index help)

Just for the record, if i understood correctly -- this was all a bit black
magicky -- Oracle found the data in the rollback segment by storing a pointer
to it in the block header where the updated data is. Ie, it could jump
straight to the right place. Of course the record could have been updated
multiple times which would necessitate following a linked list of rollback
segment entries. And those are all random access reads though you could hope
it was mostly cached.

> and creates significant amounts of contention (since lots of processes are
> competing to touch the rollback segments). Plus there's the old bugaboo that
> long-running transactions require indefinite amounts of rollback space, and
> Oracle is apparently unable to enlarge that space on-the-fly. (This last
> seems like a surmountable problem, but maybe there is some non-obvious
> reason why it's hard.)

That was one of the biggest bugaboos with Oracle but I get the impression they
spent a lot of work improving it precisely because it was such a high profile
failure. I think it's basically impossible to get a good old 'Snapshot Too
Old' error now but I'm unclear how they achieved that. There must have been a
tradeoff somewhere.

There are other solutions too. I never used DB2 but I was led to believe they
used their transaction log to retrieve old versions of the records. Someone
else here claimed DB2 didn't implement MVCC at all so perhaps that's wrong
though.

--
greg

>> > You mean systems that are designed so exactly, that they can't take
>> 10%
>> > performance change ?
>>
>> No, that's not really the point, performance degrades over time, in one
>> minute it degraded 10%.
>>
>> The update to session ratio has a HUGE impact on PostgreSQL. If you have
>> a
>> thousand active sessions, it may take a minute to degrade 10% assuming
>> some level of active vs operations per session per action.
>
> So don't do an update. Multiple updates to the same row block anyway
> which is generally not something you want anyway.

The example is a very active web site, the flow is this:

query for session information
process HTTP request
update session information

This happens for EVERY http request. Chances are that you won't have
concurrent requests for the same row, but you may have well over 100 HTTP
server processes/threads answering queries in your web server farm.

>
> If you INSERT into multiple partitions (by time -- say one per minute)
> and TRUNCATE periodically (30 minute old partitions for 30 minute
> expiry) it works much better. Expiring the session is quite fast as well
> since they'll go away with the truncate.
>
> Index on sessionid and time and grab the row with the most recent time.

I doubt that that approach (1) answers the problem or (2) would be more
efficient.
> --
>

Greg Stark wrote:

> There are other solutions too. I never used DB2 but I was led to believe they
> used their transaction log to retrieve old versions of the records. Someone
> else here claimed DB2 didn't implement MVCC at all so perhaps that's wrong
> though.

I would be suprised giving this paper:
ftp://ftp.software.ibm.com/software/data/pubs/papers/readconsistency.pdf

Lukas Smith <smith(at)pooteeweet(dot)org> writes:
> Jochem van Dieten wrote:
>> make the session handler smarter? And if you can't do that, put some
>> logic in the session table that turns an update without changes into a
>> no-op?

> err isnt that one the job of the database?

No. That idea has been suggested and rejected before. Detecting that
an UPDATE is a no-op would require a significant number of cycles, and
in most applications, most or all of the time those cycles would be
wasted effort. If you have a need for this behavior, you can attach a
BEFORE UPDATE trigger to a table that checks for all-fields-the-same and
suppresses the update. I don't think that should be automatic though.

regards, tom lane

Greg Stark <gsstark(at)mit(dot)edu> writes:
> Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> writes:
>> The Oracle design has got other drawbacks: if you need to access a row
>> version other than than the very latest, you need to go searching in the
>> rollback segments for it. This is slow (no index help)

> Just for the record, if i understood correctly -- this was all a bit black
> magicky -- Oracle found the data in the rollback segment by storing a pointer
> to it in the block header where the updated data is. Ie, it could jump
> straight to the right place.

Yeah, you should be able to find the older version easily enough, if you
arrived at the newer version and realized you needed to visit the older
version. But this fails in scenarios where you are searching on a
column that's been updated --- the index entry for the newer version
will not lead you to visit it at all. I've not seen any documentation
about what Oracle does with cases like that.

regards, tom lane

On Thu, 2006-06-22 at 13:56 -0400, Mark Woodward wrote:
> >> > You mean systems that are designed so exactly, that they can't take
> >> 10%
> >> > performance change ?
> >>
> >> No, that's not really the point, performance degrades over time, in one
> >> minute it degraded 10%.
> >>
> >> The update to session ratio has a HUGE impact on PostgreSQL. If you have
> >> a
> >> thousand active sessions, it may take a minute to degrade 10% assuming
> >> some level of active vs operations per session per action.
> >
> > So don't do an update. Multiple updates to the same row block anyway
> > which is generally not something you want anyway.
>
> The example is a very active web site, the flow is this:
>
> query for session information
> process HTTP request
> update session information
>
> This happens for EVERY http request. Chances are that you won't have
> concurrent requests for the same row, but you may have well over 100 HTTP
> server processes/threads answering queries in your web server farm.
>
> >
> > If you INSERT into multiple partitions (by time -- say one per minute)
> > and TRUNCATE periodically (30 minute old partitions for 30 minute
> > expiry) it works much better. Expiring the session is quite fast as well
> > since they'll go away with the truncate.
> >
> > Index on sessionid and time and grab the row with the most recent time.
>
> I doubt that that approach (1) answers the problem or (2) would be more
> efficient.

Depends on what else you have going on in the background. If you can
vacuum constantly and have the garbage cleaned up, it may not be. If you
have a long running transaction (pg_dump, vacuum?, report query, ...) in
the background then it can make a pretty good difference last time I
measured.

If this is the only thing that the database has and vacuum still isn't
able to keep up, who knows you might find advantages to being able to
truncate periodically instead of a constant vacuum.

--

> As you can see, in about a minute at high load, this very simple table
> lost about 10% of its performance, and I've seen worse based on update
> frequency. Before you say this is an obscure problem, I can tell you it
> isn't. I have worked with more than a few projects that had to switch
> away
> from PostgreSQL because of this behavior.
>
> Obviously this is not a problem with small sites, but this is a real
> problem with an enterprise level web site with millions of visitors and
> actions a day. Quite frankly it is a classic example of something that
> does not scale. The more and more updates there are, the higher the load
> becomes. You can see it on "top" as the footest program runs.

I believe sessions should not be stored in a SQL database.
It makes no sense. Updates and Inserts to the database should only be
done where there is an interesting thing to record, when the user does an
action like posting to a forum, making a purchase, sending a message, etc.

I believe sessions should be stored in the memory of the application
server, as native objects of the whatever language the application is
written in. This way, sessions incur no serializing overhead and can be
quite large and complex, which allows storage of interesting things, like
the result of a complicated search query which is to be later paginated,
for instance. It really makes sense to use native language objects too, as
these have a lot more power and versatility than a database row. Think
about rights management, for instance.

When the framework used lacks this power (most do and this is sad), then
sessions incur serializing overhead ; but they should be serialized to
filesystem files, or better, to memory using memcached, for instance. It
makes no sense to pay the performance penalty of a COMMIT (disk seek delay
etc) and the database overhead for sessions, which are by nature volatile
data changing all the time.

I don't think postgres should be tweaked to allow better handling of
this. It would only make a better foot-gun.

Adding back pgsql-hackers.

Mark Woodward wrote:
> > Mark Woodward wrote:
> >
> >> Hmm, OK, then the problem is more serious than I suspected.
> >> This means that every index on a row has to be updated on every
> >> transaction that modifies that row. Is that correct?
> >
> > Add an index entry, yes.
> >
> >> I am attaching some code that shows the problem with regard to
> >> applications such as web server session management, when run, each
> >> second
> >> the system can handle fewer and fewer connections. Here is a brief
> >> output:
> >> [...]
> >> There has to be a more linear way of handling this scenario.
> >
> > So vacuum the table often.
>
> That fixes the symptom, not the problem. The problem is performance
> steadily degrades over time.

No, you got it backwards. The performance degradation is the symptom.
The problem is that there are too many dead tuples in the table. There
is one way to solve that problem -- remove them, which is done by
running vacuum.

There are some problems with vacuum itself, that I agree with. For
example it would be good if a long-running vacuum wouldn't affect a
vacuum running in another table because of the long-running transaction
effect it has. It would be good if vacuum could be run partially over a
table. It would be good if there was a way to speed up vacuum by using
a dead space map or something.

I have a pending patch which adds the possibility of "non-transactional
catalogs". Maybe that could evolve into non-transactional user tables
eventually, which would have problems of their own but maybe could be
used in certain very limited scenarios, like the sessions table.

--
Alvaro Herrera Developer, http://www.PostgreSQL.org
"Oh, great altar of passive entertainment, bestow upon me thy discordant images
at such speed as to render linear thought impossible" (Calvin a la TV)

Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> writes:

> Yeah, you should be able to find the older version easily enough, if you
> arrived at the newer version and realized you needed to visit the older
> version. But this fails in scenarios where you are searching on a
> column that's been updated --- the index entry for the newer version
> will not lead you to visit it at all. I've not seen any documentation
> about what Oracle does with cases like that.

That's a good question. I had the impression rollback was handled at a lower
level so index pages were stored in rollback segments just like table pages.
If you saw that the page of the index had been updated you went and fetched
the index page of the appropriate age from the rollback segment, giving you
pointers to the right records or at least the right places to start from.

Now that I think about it though I'm not too sure. It seems like the
performance of that would be pretty awful.

--
greg

>
>> As you can see, in about a minute at high load, this very simple table
>> lost about 10% of its performance, and I've seen worse based on update
>> frequency. Before you say this is an obscure problem, I can tell you it
>> isn't. I have worked with more than a few projects that had to switch
>> away
>> from PostgreSQL because of this behavior.
>>
>> Obviously this is not a problem with small sites, but this is a real
>> problem with an enterprise level web site with millions of visitors and
>> actions a day. Quite frankly it is a classic example of something that
>> does not scale. The more and more updates there are, the higher the load
>> becomes. You can see it on "top" as the footest program runs.
>
>
> I believe sessions should not be stored in a SQL database.
Alas, this is a long debate, and while I fundimentally agree with this
position, there is an inconvenient truth that it is often nessisary.

http://www.mohawksoft.org/?q=node/8

> It makes no sense. Updates and Inserts to the database should only be
> done where there is an interesting thing to record, when the user does an
> action like posting to a forum, making a purchase, sending a message, etc.

Again, preaching to the chior.

>
> I believe sessions should be stored in the memory of the application
> server, as native objects of the whatever language the application is
> written in. This way, sessions incur no serializing overhead and can be
> quite large and complex, which allows storage of interesting things, like
> the result of a complicated search query which is to be later paginated,
> for instance. It really makes sense to use native language objects too, as
> these have a lot more power and versatility than a database row. Think
> about rights management, for instance.

What you seem not to grasp at this point is a large web-farm, about 10 or
more servers running PHP, Java, ASP, or even perl. The database is usually
the most convenient and, aside from the particular issue we are talking
about, best suited.

>
> When the framework used lacks this power (most do and this is sad), then
> sessions incur serializing overhead ; but they should be serialized to
> filesystem files, or better, to memory using memcached, for instance.

I actually have a good number of years of experience in this topic, and
memcached or file system files are NOT the best solutions for a server
farm.

> It
> makes no sense to pay the performance penalty of a COMMIT (disk seek delay
> etc) and the database overhead for sessions, which are by nature volatile
> data changing all the time.

Very true.

>
> I don't think postgres should be tweaked to allow better handling of
> this. It would only make a better foot-gun.

I think the debate is over, it may be a bad use of a database, but there
are few alternatives, and SQL databases have become the defacto
methodology for dealing with this type of problem.

>

On Thu, Jun 22, 2006 at 07:01:38PM +0200, Lukas Smith wrote:
> Jochem van Dieten wrote:
>
> >make the session handler smarter? And if you can't do that, put
> >some logic in the session table that turns an update without
> >changes into a no-op?
>
> err isnt that one the job of the database?

By no means. Even if there were zero overhead for this, which there
couldn't be, you'd have a real problem auditing attempted actions.
This would be a very big problem when trying to track down a rogue app
and/or a denial of service attack.

Cheers,
D
--
David Fetter <david(at)fetter(dot)org> http://fetter.org/
phone: +1 415 235 3778 AIM: dfetter666
Skype: davidfetter

Remember to vote!

> What you seem not to grasp at this point is a large web-farm, about 10 or
> more servers running PHP, Java, ASP, or even perl. The database is
> usually
> the most convenient and, aside from the particular issue we are talking
> about, best suited.

The answer is sticky sessions : each user is assigned to one and only one
webserver in the cluster and his session is maintained locally, in RAM. No
locks, no need to manage distributed session...

> I actually have a good number of years of experience in this topic, and
> memcached or file system files are NOT the best solutions for a server
> farm.

If sessions are distributed, certainly, but if sessions are sticky to
their own server ?

PFC wrote:

>
>> What you seem not to grasp at this point is a large web-farm, about
>> 10 or
>> more servers running PHP, Java, ASP, or even perl. The database is
>> usually
>> the most convenient and, aside from the particular issue we are talking
>> about, best suited.
>
>
> The answer is sticky sessions : each user is assigned to one and
> only one webserver in the cluster and his session is maintained
> locally, in RAM. No locks, no need to manage distributed session...

Sticky sessions can cause enormous problems. I have just worked on a
site whose problems largely come back to having to use a load balancer
in front of an app server farm that required sticky sessions.

They are not a solution, they are a disease.

cheers

andrew

On Jun 22, 2006, at 12:56 PM, Greg Stark wrote:
> Just for the record, if i understood correctly -- this was all a
> bit black
> magicky -- Oracle found the data in the rollback segment by storing
> a pointer
> to it in the block header where the updated data is. Ie, it could jump
> straight to the right place. Of course the record could have been
> updated
> multiple times which would necessitate following a linked list of
> rollback
> segment entries. And those are all random access reads though you
> could hope
> it was mostly cached.

Correct. Mark is basically suggesting we do the same thing in the
heap so that updates that don't touch any indexed fields could just
update the indexes to point them at the new row version.

Question: do we currently create new index entries even if the index
key hasn't changed? If so, what's the purpose of storing the CTID of
the next version in the old version of the row?

> There are other solutions too. I never used DB2 but I was led to
> believe they
> used their transaction log to retrieve old versions of the records.
> Someone
> else here claimed DB2 didn't implement MVCC at all so perhaps
> that's wrong
> though.

DB2 switched to MVCC in version 8. MSSQL switched in MSSQL2005. At
this point, I don't know of any major databases that don't use some
form of MVCC (err, maybe Sybase?)
--
Jim C. Nasby, Sr. Engineering Consultant jnasby(at)pervasive(dot)com
Pervasive Software http://pervasive.com work: 512-231-6117
vcard: http://jim.nasby.net/pervasive.vcf cell: 512-569-9461

On Jun 22, 2006, at 2:00 PM, Mark Woodward wrote:

> I actually have a good number of years of experience in this topic,
> and
> memcached or file system files are NOT the best solutions for a server
> farm.

What's wrong with memcached for session data?
--
Jim C. Nasby, Sr. Engineering Consultant jnasby(at)pervasive(dot)com
Pervasive Software http://pervasive.com work: 512-231-6117
vcard: http://jim.nasby.net/pervasive.vcf cell: 512-569-9461

>
>> What you seem not to grasp at this point is a large web-farm, about 10
>> or
>> more servers running PHP, Java, ASP, or even perl. The database is
>> usually
>> the most convenient and, aside from the particular issue we are talking
>> about, best suited.
>
> The answer is sticky sessions : each user is assigned to one and only one
> webserver in the cluster and his session is maintained locally, in RAM. No
> locks, no need to manage distributed session...
>
>> I actually have a good number of years of experience in this topic, and
>> memcached or file system files are NOT the best solutions for a server
>> farm.
>
> If sessions are distributed, certainly, but if sessions are sticky to
> their own server ?

And what if a particulr server goes down? or gets too high a percentage of
the load?

On Jun 22, 2006, at 1:09 PM, Tom Lane wrote:
> Lukas Smith <smith(at)pooteeweet(dot)org> writes:
>> Jochem van Dieten wrote:
>>> make the session handler smarter? And if you can't do that, put some
>>> logic in the session table that turns an update without changes
>>> into a
>>> no-op?
>
>> err isnt that one the job of the database?
>
> No. That idea has been suggested and rejected before. Detecting that
> an UPDATE is a no-op would require a significant number of cycles, and
> in most applications, most or all of the time those cycles would be
> wasted effort. If you have a need for this behavior, you can attach a
> BEFORE UPDATE trigger to a table that checks for all-fields-the-
> same and
> suppresses the update. I don't think that should be automatic though.

What would be nice to add is the ability to perform that check more
easily. As of 8.1...

create function test() returns trigger as $$
begin
if NEW=OLD then
return null;
else
return NEW;
end if;
end;
create trigger test before update on test execute procedure test();
update test set i=i;
ERROR: operator does not exist: test = test
HINT: No operator matches the given name and argument type(s). You
may need to add explicit type casts.
CONTEXT: SQL statement "SELECT $1 = $2 "
PL/pgSQL function "test" line 2 at if
--
Jim C. Nasby, Sr. Engineering Consultant jnasby(at)pervasive(dot)com
Pervasive Software http://pervasive.com work: 512-231-6117
vcard: http://jim.nasby.net/pervasive.vcf cell: 512-569-9461

Jim Nasby <jnasby(at)pervasive(dot)com> writes:
> Question: do we currently create new index entries even if the index
> key hasn't changed?

Yes.

> If so, what's the purpose of storing the CTID of
> the next version in the old version of the row?

So that UPDATE can always find the newest version of the row,
independently of what indexes exist or how it got to the row.
You may care to re-read the second paragraph here:
http://developer.postgresql.org/docs/postgres/transaction-iso.html#XACT-READ-COMMITTED

regards, tom lane

Jim Nasby <jnasby(at)pervasive(dot)com> writes:
> What would be nice to add is the ability to perform that check more
> easily. As of 8.1...
> ...
> if NEW=OLD then
> ...
> ERROR: operator does not exist: test = test
> HINT: No operator matches the given name and argument type(s). You
> may need to add explicit type casts.

Hmm, there seems to be some asymmetry in the handling, because it works
for anonymous row constructors:

regression=# select row(a.*) = row(a.*) from int8_tbl a;
ERROR: operator does not exist: int8_tbl = int8_tbl
LINE 1: select row(a.*) = row(a.*) from int8_tbl a;
^
HINT: No operator matches the given name and argument type(s). You may need to
add explicit type casts.

regression=# select row(a.q1,a.q2) = row(a.q1,a.q2) from int8_tbl a;
?column?
----------
t
t
t
t
t
(5 rows)

Someone oughta look into that...

regards, tom lane

On Jun 22, 2006, at 9:56 PM, Christopher Kings-Lynne wrote:

>> The example is a very active web site, the flow is this:
>> query for session information
>> process HTTP request
>> update session information
>> This happens for EVERY http request. Chances are that you won't have
>> concurrent requests for the same row, but you may have well over 100
>> HTTP
>> server processes/threads answering queries in your web server farm.
>
> You're crazy :) Use memcache, not the DB :)

Still, the database is the one central location that the apaches can
connect too- postgres already has a lot of application platform
features- locking synchronization, asynchronous notifications,
arbitrary pl code.

Personally, I think that a special non-MVCC table type could be
created- the catalogs are similarly flat. What I envision is a table
type that can only be accessed "outside" transactions (like AutoCommit
mode)- this is already possible to implement in plperl for a single
session. It would be more efficient to have something like a global
temp table hanging around...

Just some random ideas...

-M

¬ ¬ ¬ ¬ ¬ ¬ ¬ ¬ ¬ ¬ ¬ ¬ ¬ ¬ ¬ ¬ ¬ ¬
AgentM
agentm(at)themactionfaction(dot)com
¬ ¬ ¬ ¬ ¬ ¬ ¬ ¬ ¬ ¬ ¬ ¬ ¬ ¬ ¬ ¬ ¬ ¬

> The example is a very active web site, the flow is this:
>
> query for session information
> process HTTP request
> update session information
>
> This happens for EVERY http request. Chances are that you won't have
> concurrent requests for the same row, but you may have well over 100 HTTP
> server processes/threads answering queries in your web server farm.

You're crazy :) Use memcache, not the DB :)

Chris

On Jun 22, 2006, at 6:56 PM, Agent M wrote:

>
> On Jun 22, 2006, at 9:56 PM, Christopher Kings-Lynne wrote:
>
>>> The example is a very active web site, the flow is this:
>>> query for session information
>>> process HTTP request
>>> update session information
>>> This happens for EVERY http request. Chances are that you won't have
>>> concurrent requests for the same row, but you may have well over
>>> 100 HTTP
>>> server processes/threads answering queries in your web server farm.
>>
>> You're crazy :) Use memcache, not the DB :)
>
> Still, the database is the one central location that the apaches
> can connect too- postgres already has a lot of application platform
> features- locking synchronization, asynchronous notifications,
> arbitrary pl code.
>
> Personally, I think that a special non-MVCC table type could be
> created- the catalogs are similarly flat. What I envision is a
> table type that can only be accessed "outside" transactions (like
> AutoCommit mode)- this is already possible to implement in plperl
> for a single session. It would be more efficient to have something
> like a global temp table hanging around...
>

Have you seen pgmemcache? It allows you to access a memcached
instance from within postgresql - which makes many of the problems
with using a separate caching / storage layer go away, or at least
get far easier to deal with.

Cheers,
Steve

On Thu, 22 Jun 2006, Agent M wrote:

>
> On Jun 22, 2006, at 9:56 PM, Christopher Kings-Lynne wrote:
>
> >> The example is a very active web site, the flow is this:
> >> query for session information
> >> process HTTP request
> >> update session information
> >> This happens for EVERY http request. Chances are that you won't have
> >> concurrent requests for the same row, but you may have well over 100
> >> HTTP
> >> server processes/threads answering queries in your web server farm.
> >
> > You're crazy :) Use memcache, not the DB :)
>
> Still, the database is the one central location that the apaches can
> connect too- postgres already has a lot of application platform
> features- locking synchronization, asynchronous notifications,
> arbitrary pl code.
>
> Personally, I think that a special non-MVCC table type could be
> created- the catalogs are similarly flat. What I envision is a table
> type that can only be accessed "outside" transactions (like AutoCommit
> mode)- this is already possible to implement in plperl for a single
> session. It would be more efficient to have something like a global
> temp table hanging around...
>
> Just some random ideas...

Unfortunately, it's not so simple.

What if a user enters a transaction block, modifies a normal table,
modifies this 'special table'... then rolls back? This is the problem
MySQL has with innodb and myisam tables.

Well... we could just document that. If only.

What happens if, as a part the update to the special table, we encounter
and error? MVCC currently guarantees that this modification will be
invisible. Without MVCC, we have no such capability.

There seems to be a bit of confusion about what MVCC is. PostgreSQL is not
the only MVCC database. InnoDB is MVCC. Oracle is MVCC. As far as I know,
PostgreSQL is the only MVCC database with a 'non-overwriting storage
manager'. The other MVCC databases maintain UNDO logs outside of the
table's data files. When an update occurs, the existing row version is
copied to te UNDO file, the new data replaces the old and a backward
pointer from the table row to the UNDO log is created. Concurrent reads
must go into the UNDO log and find the version visible to them. This
implements the principle of MVCC and uses snapshot isolation, like we do,
to isolate read/write concurrency.

Overwriting MVCC comes with its own baggage. Ask any Oracle user about
error ORA-01555[1]. There's also the added cost of managing the UNDO logs,
the cost of jumping around between files to get row versions and so on.

Also, it leads to inefficiency with variable size data types. The new
version of a row might be longer or shorter than the previous version and
this has to be causing them a headaches and performance penalties.

As for single version databases -- they have a tonne of problems
themselves. They need to maintain UNDO functionality so as to deal with
the error handling I detailed above but they also cannot implement MVCC
rules for all cases: readers to not block writes, writers do not block
readers. Instead, they implement a large lock matrix and certain types of
queries use certain types of granular locks.

Some potentially interesting reading material on these ideas:

J. Gray & A Reuter, Transaction Processing: Concepts and Techniques
US Patent Number 5,870,758 -- (one of?) Oracle's snapshot isolation patent
Tom Lane's MVCC talk:
http://www.postgresql.org/files/developer/transactions.pdf

Thanks,

Gavin

---
[1] Basically, the UNDO logs are a circular buffer and, remarkably, Oracle
doesnt seem to let the buffer expand if there is a long running
transaction. (We do this for WAL).

Basically, in this case Oracle finds itself in a compromising position
because if any more data is written to the UNDO log the query affected
will not be able to roll back and/or concurrent queries will not be able
to find the correct row version for their snapshot.

UNDO log size can be adjusted but this situation bites Oracle users
constantly.

I wrote:
> Jim Nasby <jnasby(at)pervasive(dot)com> writes:
>> What would be nice to add is the ability to perform that check more
>> easily. As of 8.1...
>> ...
>> if NEW=OLD then
>> ...
>> ERROR: operator does not exist: test = test
>> HINT: No operator matches the given name and argument type(s). You
>> may need to add explicit type casts.

> Hmm, there seems to be some asymmetry in the handling, because it works
> for anonymous row constructors:
> regression=# select row(a.q1,a.q2) = row(a.q1,a.q2) from int8_tbl a;

I poked into this a little, and it seems like the most flexible answer
might be for "foo.*" inside a ROW construct to behave the way that it
does at the top level of a SELECT list --- that is, implicitly expand to
a list of all the columns of foo. You'd have to write the mentioned
test as

if row(new.*) = row(old.*) then ...

but there is some additional flexibility because you could form rows
from combinations of things, eg

row(foo.*, bar, baz.*)

I can't find anything suggesting this syntax in the SQL99 spec, but
I don't think they expect equality to work on two unadorned table names
either.

Not sure if there are any backwards-compatibility issues. Right now the
system takes this syntax as creating a rowtype column within a rowtype,
which is possibly of some use but I kinda doubt people are doing much
with it. In any case, if you did want that behavior you could still get
it by leaving off the ".*".

Implementation would be pretty trivial, we'd just have to put logic into
transformRowExpr() comparable to what transformTargetList() does for
"foo.*" cases. With a little bit of refactoring, the code could be shared.

Comments?

regards, tom lane

The world rejoiced as tgl(at)sss(dot)pgh(dot)pa(dot)us (Tom Lane) wrote:
> Lukas Smith <smith(at)pooteeweet(dot)org> writes:
>> Jochem van Dieten wrote:
>>> make the session handler smarter? And if you can't do that, put some
>>> logic in the session table that turns an update without changes into a
>>> no-op?
>
>> err isnt that one the job of the database?
>
> No. That idea has been suggested and rejected before. Detecting
> that an UPDATE is a no-op would require a significant number of
> cycles, and in most applications, most or all of the time those
> cycles would be wasted effort. If you have a need for this
> behavior, you can attach a BEFORE UPDATE trigger to a table that
> checks for all-fields-the-same and suppresses the update. I don't
> think that should be automatic though.

If this be handled via a stored procedure, the stored proc could hide
this detail nice and completely...

select store_session(a,b,c,d,e);

store_session can be quite smart enough to not bother doing spurious
updates.
--
select 'cbbrowne' || '@' || 'linuxfinances.info';
http://linuxdatabases.info/info/x.html
Rules of the Evil Overlord #29. "I will dress in bright and cheery
colors, and so throw my enemies into confusion."
<http://www.eviloverlord.com/>

On 6/22/06, Gavin Sherry <swm(at)linuxworld(dot)com(dot)au> wrote:
> There seems to be a bit of confusion about what MVCC is.

Yes, PostgreSQL implements MVTO-style concurrency, Oracle implements
MVRC, ... Let's not go into theory here, because there's plenty of
papers and books on the subject.

> The other MVCC databases maintain UNDO logs outside of the
> table's data files.

*most* other MVCC systems act this way, but not all.

> When an update occurs, the existing row version is
> copied to te UNDO file

Not in all systems. A few now perform in-memory UNDO and only write
it to disk if and when it is required.

> Overwriting MVCC comes with its own baggage. Ask any Oracle user about
> error ORA-01555[1]. There's also the added cost of managing the UNDO logs,
> the cost of jumping around between files to get row versions and so on.

This seems to be going in the direction of our common MySQL
discussions; relying on old failures and mistakes to base our
assumptions on the current version. Please stay apprised of current
developments in other systems.

As you're probably haven't done consulting for Oracle recently, I can
tell you that the once-dreaded ORA-01555 is nearly a thing of the
past. Continuing to dispense misinformation doesn't help anyone so
let's stop trying to use Oracle's past problems (which are largely due
to improper tuning) as preferring PostgreSQL's methods over others.

> Also, it leads to inefficiency with variable size data types. The new
> version of a row might be longer or shorter than the previous version and
> this has to be causing them a headaches and performance penalties.

I've seen many MVCC implementations using update-in-place (overwriting
storage manager) with plenty of variable-length attributes; not all
have these problems.

> J. Gray & A Reuter, Transaction Processing: Concepts and Techniques

Pretty much older than dirt, discusses locking, and barely touches on
MVCC. Still has some good concepts though.

> US Patent Number 5,870,758 -- (one of?) Oracle's snapshot isolation patent

Again, not the most optimal implementation of MVCC, but does certainly
have advantages.

> Tom Lane's MVCC talk:
> http://www.postgresql.org/files/developer/transactions.pdf

Always a good read.

I suggest reading Transactional Information Systems: Theory,
Algorithms, and the Practice of Concurrency Control by Weikum and
Vossen... it's basically the new Gray and Reuter. It covers multiple
MVCC techniques as well as differences between the different UNDO/REDO
database models.

--
Jonah H. Harris, Software Architect | phone: 732.331.1300
EnterpriseDB Corporation | fax: 732.331.1301
33 Wood Ave S, 2nd Floor | jharris(at)enterprisedb(dot)com
Iselin, New Jersey 08830 | http://www.enterprisedb.com/

On Thu, 22 Jun 2006, Jonah H. Harris wrote:

> Not in all systems. A few now perform in-memory UNDO and only write
> it to disk if and when it is required.

Interesting...

>
> > Overwriting MVCC comes with its own baggage. Ask any Oracle user about
> > error ORA-01555[1]. There's also the added cost of managing the UNDO logs,
> > the cost of jumping around between files to get row versions and so on.
>
> This seems to be going in the direction of our common MySQL
> discussions; relying on old failures and mistakes to base our
> assumptions on the current version. Please stay apprised of current
> developments in other systems.

Erm. Perhaps a poor example as I was not trying to put Oracle in a poor
light. Rather, I was trying to point out that each method has its
disadvantages. If the update in place method has no detractions we
shouldn't be hanging on to our existing mechanism.

> > J. Gray & A Reuter, Transaction Processing: Concepts and Techniques
>
> Pretty much older than dirt, discusses locking, and barely touches on
> MVCC. Still has some good concepts though.

The really useful section of this book is the discussion of snapshot
isolation. That's the important thing here. Conceivably we could have a
higher performance storage system but, IMHO, it must implement snapshot
isolation.

Thanks,

Gavin

Jonah H. Harris wrote:
> On 6/22/06, Gavin Sherry <swm(at)linuxworld(dot)com(dot)au> wrote:

> >When an update occurs, the existing row version is
> >copied to te UNDO file
>
> Not in all systems. A few now perform in-memory UNDO and only write
> it to disk if and when it is required.

How does that work? If the last transaction is not finished after it
wrote the tuple when the power goes out, and the UNDO is not written to
disk either, how do you reconstruct the tuple at all?

--
Alvaro Herrera http://www.CommandPrompt.com/
The PostgreSQL Company - Command Prompt, Inc.

On Thu, 22 Jun 2006, Jim Nasby wrote:

> DB2 switched to MVCC in version 8. ...

Um, no it didn't.

- Heikki

> > Good advice, except if the table is huge :-)
>
> ... Then the table shouldn't be designed to be huge. That represents
> a design error.
[snip]
> This demonstrates that "archival" material and "active" data should be
> kept separately.
>
> They have different access patterns; kludging them into the same table
> turns out badly.

Well, then please help me find a better design cause I can't see one...
what we have here is a big "membership" table of email lists. When
there's a sendout then the memberships of the affected group are heavily
read/updated, otherwise they are idle. None of the memberships is
archive data, they are all active data... the only problem is that they
are so many. Is it so hard to believe that >100 million rows is all
active data, but only used in bursts once per week (that's an example,
some groups are more active, others less) ?

Cheers,
Csaba.

> Well, then please help me find a better design cause I can't see one...
> what we have here is a big "membership" table of email lists. When
> there's a sendout then the memberships of the affected group are heavily
> read/updated, otherwise they are idle. None of the memberships is
> archive data, they are all active data... the only problem is that they
> are so many. Is it so hard to believe that >100 million rows is all
> active data, but only used in bursts once per week (that's an example,
> some groups are more active, others less) ?

I suppose you have a table memberships (user_id, group_id) or something
like it ; it should have as few columns as possible ; then try regularly
clustering on group_id (maybe once a week) so that all the records for a
particular group are close together. Getting the members of a group to
send them an email should be faster (less random seeks).

For tables with very few small fields (like a few integers) the
26-something bytes row overhead is significant ; MySQL can be faster
because MyISAM tables have no transaction support and thus have very
little things to store besides actual row data, and the table can then fit
in RAM...

> I suppose you have a table memberships (user_id, group_id) or something
> like it ; it should have as few columns as possible ; then try regularly
> clustering on group_id (maybe once a week) so that all the records for a
> particular group are close together. Getting the members of a group to
> send them an email should be faster (less random seeks).

It is like this, and some more bookkeeping data which must be there...
we could split the table for smaller records or for updatable/stable
fields, but at the end of the day it doesn't make much sense, usually
all the data is needed and I wonder if more big/shallow tables instead
of one big/wider makes sense...

Regularly clustering is out of question as it would render the system
unusable for hours. There's no "0 activity hour" we could use for such
stuff. There's always something happening, only the overall load is
smaller at night...

Thanks,
Csaba.

>> The example is a very active web site, the flow is this:
>>
>> query for session information
>> process HTTP request
>> update session information
>>
>> This happens for EVERY http request. Chances are that you won't have
>> concurrent requests for the same row, but you may have well over 100
>> HTTP
>> server processes/threads answering queries in your web server farm.
>
> You're crazy :) Use memcache, not the DB :)
>

I actually have what I consider a better and more complete session handler
system. MCache formally MSession. (http://www.mohawksoft.org/?q=node/8) I
mean, it implements a LOT of nifty features, loadable function modules,
collision safe counters and operators, ability to save session data to
file or SQL database and at varying levels of caching, but that doesn't
mean it is used.

Technologies like memcached and my mcache are a separate data store. Your
session data is not usable anywhere but in your web system. I have gone as
far as to write a session serializer for PHP that outputs XML, a
PostgreSQL plugin that can extract data from the XML session string, and a
set of functions for interfacing mcache with PostgreSQL and I still have a
hard time convincing clients that this is the right way to go.

While we all know session data is, at best, ephemeral, people still want
some sort of persistence, thus, you need a database. For mcache I have a
couple plugins that have a wide range of opitions, from read/write at
startup and shut down, to full write through cache to a database.

In general, my clients don't want this, they want the database to store
their data. When you try to explain to them that a database may not be the
right place to store this data, they ask why, sadly they have little hope
of understanding the nuances and remain unconvinced.

> Let me ask a question, you have this hundred million row table. OK, how
> much of that table is "read/write?" Would it be posible to divide the
> table into two (or more) tables where one is basically static, only
> infrequent inserts and deletes, and the other is highly updated?

Well, all of it is read write... some of the data might be updated less
frequently, but there's no way I would know which part of the data is
that. Logically is just the same type of data... so unless I find a way
to continuously move back and forth the data between an archive table
and the live table, based on how active the groups are, I can't imagine
any other way of partitioning it. And that would also mean some quite
big load given the pretty high dynamics of the groups.

> The "big" thing in performance is the amount of disk I/O, if you have a
> smaller active table with only a single index, then you may be able to cut
> your disk I/O time really down. The smaller the row size, the more rows
> fit into a block. The fewer blocks the less dissk I/O. The less disk I/O
> the bbetter the performance.

I agree, but it is quite hard to achieve that when the data set is both
big AND the partitioning criteria is highly dynamic. Not to mention that
deleting from that table is also a PITA performance-wise, so I wonder
how well the continuous back and forth between the active and inactive
table would do.

> Also, and anyone listening correct me if I'm wrong, you NEED to vacuum
> frequently because the indexes grow and vacuuming them doesnt remove
> everything, sometimes a REINDEX or a drop/recreate is the only way to get
> performance back. So if you wait too long between vacuums, your indexes
> grow and spread across more disk blocks than they should and thus use
> more disk I/O to search and/or shared memory to cache.

This is nice in theory, but kills performance. I vacuum the big tables
only overnight, otherwise the server is sluggish.

Cheers,
Csaba.

>> I suppose you have a table memberships (user_id, group_id) or something
>> like it ; it should have as few columns as possible ; then try regularly
>> clustering on group_id (maybe once a week) so that all the records for a
>> particular group are close together. Getting the members of a group to
>> send them an email should be faster (less random seeks).
>
> It is like this, and some more bookkeeping data which must be there...
> we could split the table for smaller records or for updatable/stable
> fields, but at the end of the day it doesn't make much sense, usually
> all the data is needed and I wonder if more big/shallow tables instead
> of one big/wider makes sense...
>
> Regularly clustering is out of question as it would render the system
> unusable for hours. There's no "0 activity hour" we could use for such
> stuff. There's always something happening, only the overall load is
> smaller at night...
>

Let me ask a question, you have this hundred million row table. OK, how
much of that table is "read/write?" Would it be posible to divide the
table into two (or more) tables where one is basically static, only
infrequent inserts and deletes, and the other is highly updated?

The "big" thing in performance is the amount of disk I/O, if you have a
smaller active table with only a single index, then you may be able to cut
your disk I/O time really down. The smaller the row size, the more rows
fit into a block. The fewer blocks the less dissk I/O. The less disk I/O
the bbetter the performance.

Also, and anyone listening correct me if I'm wrong, you NEED to vacuum
frequently because the indexes grow and vacuuming them doesnt remove
everything, sometimes a REINDEX or a drop/recreate is the only way to get
performance back. So if you wait too long between vacuums, your indexes
grow and spread across more disk blocks than they should and thus use
more disk I/O to search and/or shared memory to cache.

>> Let me ask a question, you have this hundred million row table. OK, how
>> much of that table is "read/write?" Would it be posible to divide the
>> table into two (or more) tables where one is basically static, only
>> infrequent inserts and deletes, and the other is highly updated?
>
> Well, all of it is read write... some of the data might be updated less
> frequently, but there's no way I would know which part of the data is
> that. Logically is just the same type of data... so unless I find a way
> to continuously move back and forth the data between an archive table
> and the live table, based on how active the groups are, I can't imagine
> any other way of partitioning it. And that would also mean some quite
> big load given the pretty high dynamics of the groups.
>
>> The "big" thing in performance is the amount of disk I/O, if you have a
>> smaller active table with only a single index, then you may be able to
>> cut
>> your disk I/O time really down. The smaller the row size, the more rows
>> fit into a block. The fewer blocks the less dissk I/O. The less disk I/O
>> the bbetter the performance.
>
> I agree, but it is quite hard to achieve that when the data set is both
> big AND the partitioning criteria is highly dynamic. Not to mention that
> deleting from that table is also a PITA performance-wise, so I wonder
> how well the continuous back and forth between the active and inactive
> table would do.
>
>> Also, and anyone listening correct me if I'm wrong, you NEED to vacuum
>> frequently because the indexes grow and vacuuming them doesnt remove
>> everything, sometimes a REINDEX or a drop/recreate is the only way to
>> get
>> performance back. So if you wait too long between vacuums, your indexes
>> grow and spread across more disk blocks than they should and thus use
>> more disk I/O to search and/or shared memory to cache.
>
> This is nice in theory, but kills performance. I vacuum the big tables
> only overnight, otherwise the server is sluggish.

Well, the only thing left is to cluster the database. There are a couple
ways to do this, one switch to a platform that supports clustering or
create an API to wrap multiple databases. If your queries are simple and
limited, you could create an HTTP/XML service that wraps a number of
postgresql databases, issues a query across all databases, merges multiple
query sets, and returns one homoginous stream.

Inserts would be handled by hash to machine weighted by number of records
on each machine.

Updates and deletes would have two keys, machine and ID.

It sounds like you have a "big" problem and you need a "big" solution.

> Well, the only thing left is to cluster the database. There are a couple
> ways to do this, one switch to a platform that supports clustering or
> create an API to wrap multiple databases. If your queries are simple and
> limited, you could create an HTTP/XML service that wraps a number of
> postgresql databases, issues a query across all databases, merges multiple
> query sets, and returns one homoginous stream.
>
Our queries are not simple nor limited :-)

We have a big variety of users, with a big variety of needs and talented
user story writers who have imaginative minds... so the same code must
work in quite a few ways, and some of the resulting queries are
dynamically created. It's a tough job to optimize all the queries we
have.

> Inserts would be handled by hash to machine weighted by number of records
> on each machine.
>
> Updates and deletes would have two keys, machine and ID.
>
Such a setup might work for us but I fear it would be a major PITA to
make it reliable and to maintain it. It's not like I can say "let's
allot a month of work for trying out a clustering solution, but I'm not
sure if it will work fine at the end". We still have enough features to
develop, the DB is something to solve part of the problem, not to keep
us busy... the Oracle systems were there first, the application works
more or less fine on them (with occasional need to optimize here and
there). Supporting Postgres was a side-project to see if it works, and
it works decently, so we deployed some systems on it. Both of the DBs
have their quirks, and I can voice here the ones I don't like in
Postgres... and then some developer might do something about it or not,
and I find that OK. If my mind wouldn't refuse so categorically to learn
C style programming (tried that and gave up), I would probably scratch
my itches. I did it for smaller scaled ones, like truncating
timestamp(0) instead of rounding so that it is consistent with what
Oracle does, but that was just a one file modification... I simply don't
find it fun to browse C code, compared to how easy is to understand Java
code which I work with here. So unless somebody ports Postgres to Java,
I'll further need to voice my itches here in the hope that they'll be
solved by others... sorry for the long rant.

> It sounds like you have a "big" problem and you need a "big" solution.

Well, Postgres does a decent job as it is. The problem is under peek
load, sometimes it gets bogged down and the usual things like vacuum
will not help immediately. I think a few more features like the dead
space map for quick vacuum and even something like the original post's
proposition would make postgres fly under heavy load too...

Cheers,
Csaba.

Ühel kenal päeval, N, 2006-06-22 kell 12:41, kirjutas Mark Woodward:

> > Depending on exact details and optimisations done, this can be either
> > slower or faster than postgresql's way, but they still need to do
> > something to get transactional visibility rules implemented.
>
> I think they have a different strategy. I think they maintain the notion
> of "current version" of a row, and hunt for previous versions when needed,
> at least that's how I suspect Oracle does it with redo logs.

Not "current" but "last" :)

And one side effect of redo logs is that it is practically impossible to
do large deletes on production databases. So you design around that,
like you have to design around limitations of MVCC.

> >> > > There has to be a more linear way of handling this scenario.
> >> >
> >> > So vacuum the table often.
> >>
> >> It's easy to say VACUUM often... but I'd bet that vacuuming is going
> >> to lessen the throughput in his tests even more; no matter how it's
> >> tuned.
> >
> > Running VACUUM often/continuously will likely keep his update rate
> > fluctuatons within a corridor of maybe 5-10%, at the cost of 1-2% extra
> > load. At least if vacuum is configured right and the server is not
> > already running at 100% IO saturation, in which case it will be worse.
>
> Assuming the table is a reasonable size, the I/O required for vacuum
> doesn't kill everything else!

I have solved the problem of unneccessary IO by keeping active and
finished rows in separate tables, with the finish() function moving the
row between tables.

In case of the number of actively modified rows being in only tens or
low hundreds of thousands of rows, (i.e. the modified set fits in
memory) the continuous vacuum process shows up as just another backend,
not really taking order of magnitude more resources. It mainly generates
WAL traffic, as modified pages are already in memory/cache and are
mostly synced by background writer and/or checkpoint.

Of course you have to adjust vacuum_cost_* variables so as to not
saturate IO.

> > The max throughput figure is not something you actually need very often
> > in production.
>
> No, but you need to have some degree of certainty and predictability in
> the system you are developing.

Yup. You have to design it so it has.

> > What is interesting is setting up the server so that you
> > can service your loads comfortably. Running the server at 100% lead is
> > not anything you want to do on production server. There will be things
> > you need to do anyway and you need some headroom for that.
>
> Of course, you design it so peaks are easily managed, but unless you run
> vacuum continuously, and that has its own set of problems, you run into
> this problem, and it can get really really bad.

Usually it gets really bad if you *don't* run vacuum continuously, maybe
hopeing to do it in slower times at night. For high-update db you have
to run it continuously, maybe having some 5-15 sec pauses between runs.

--
----------------
Hannu Krosing
Database Architect
Skype Technologies OÜ
Akadeemia tee 21 F, Tallinn, 12618, Estonia

Skype me: callto:hkrosing
Get Skype for free: http://www.skype.com

On Fri, Jun 23, 2006 at 03:30:45PM +0200, Csaba Nagy wrote:
> > It sounds like you have a "big" problem and you need a "big" solution.
>
> Well, Postgres does a decent job as it is. The problem is under peek
> load, sometimes it gets bogged down and the usual things like vacuum
> will not help immediately. I think a few more features like the dead
> space map for quick vacuum and even something like the original post's
> proposition would make postgres fly under heavy load too...

I know there have a been a number of suggestions in the past to deal
with this thing. Some I don't remember being mentioned in this thread
are:

- Once a tuple has been determined to be invisible to everyone,
truncate it to just the header. This would probably work wonders for
frequently updated wide tables. However, this required keeping track of
the oldest active xact, I'm not sure how that works at the moment.

- Have the bgwriter do cleanup work before writing out a block. It
could probably do the truncation bit above, but totally removing old
tuples requires cleaning out the indexes too, which AIUI is the hard
part of vacuuming.

One totally whacked out idea I just thought of: Instead of just
truncating tuples when they're invisible, mark them "dying" and make
the data section store an array of CTIDs pointing to the index tuples
pointing to it. Lookups that find the tuple via an index could store
the CTID of the index tuple before continuing. If the bgwriter sees it
has a full set, it can efficiently remove the tuple straight away.

There are ofcourse drawbacks to this approach, you'd probably need
something like the half-dirty pages to avoid a large increase in write
load. If it's even beneficial at all given concurrency issues.

Still, VACUUM has gotten faster in CVS so the issues are slowly being
addressed...

Have a nice day,
--
Martijn van Oosterhout <kleptog(at)svana(dot)org> http://svana.org/kleptog/
> From each according to his ability. To each according to his ability to litigate.

On 6/22/06, Alvaro Herrera <alvherre(at)commandprompt(dot)com> wrote:
> > Not in all systems. A few now perform in-memory UNDO and only write
> > it to disk if and when it is required.
>
> How does that work? If the last transaction is not finished after it
> wrote the tuple when the power goes out, and the UNDO is not written to
> disk either, how do you reconstruct the tuple at all?

It still follows normal transaction semantics... on commit, the REDO
record is written to disk. If the block was not written to disk and
the database crashes, the on-disk representation of the block remained
unchanged and recovery would pick up the REDO record from the log and
reapply it.

However, say someone updates a record which moves the old tuple value
to an in-memory UNDO location and changes the in-memory block
representation... if a checkpoint occurs before the user commits, the
block must be written to disk in changed form which means that the
UNDO record must also be written to the log (before the block is
written to disk). In the event of a crash, recovery would see that
the transaction never committed and would apply the UNDO to the block.

--
Jonah H. Harris, Software Architect | phone: 732.331.1300
EnterpriseDB Corporation | fax: 732.331.1301
33 Wood Ave S, 2nd Floor | jharris(at)enterprisedb(dot)com
Iselin, New Jersey 08830 | http://www.enterprisedb.com/

Mark Woodward wrote:

> > In case of the number of actively modified rows being in only tens or
> > low hundreds of thousands of rows, (i.e. the modified set fits in
> > memory) the continuous vacuum process shows up as just another backend,
> > not really taking order of magnitude more resources. It mainly generates
> > WAL traffic, as modified pages are already in memory/cache and are
> > mostly synced by background writer and/or checkpoint.
> >
> > Of course you have to adjust vacuum_cost_* variables so as to not
> > saturate IO.
>
> These sort of solutions, IMHO, don't show how good PostgreSQL is, but show
> where it is very lacking.

We all know Postgres is lacking; some of us try to improve it (some with
more success than others). People who know the current limitations but
like the capabilities, try to find workarounds to the problems. What
surprises me is that, if you have such a low opinion of Postgres, you
still use it.

--
Alvaro Herrera http://www.CommandPrompt.com/
The PostgreSQL Company - Command Prompt, Inc.

On Fri, June 23, 2006 9:56 am, Martijn van Oosterhout wrote:
> On Fri, Jun 23, 2006 at 03:30:45PM +0200, Csaba Nagy wrote:
>
>>> It sounds like you have a "big" problem and you need a "big"
>>> solution.
>>
>> Well, Postgres does a decent job as it is. The problem is under peek
>> load, sometimes it gets bogged down and the usual things like vacuum will
>> not help immediately. I think a few more features like the dead space
>> map for quick vacuum and even something like the original post's
>> proposition would make postgres fly under heavy load too...
>
> I know there have a been a number of suggestions in the past to deal
> with this thing. Some I don't remember being mentioned in this thread are:
>
>
> - Once a tuple has been determined to be invisible to everyone,
> truncate it to just the header. This would probably work wonders for
> frequently updated wide tables. However, this required keeping track of
> the oldest active xact, I'm not sure how that works at the moment.
>
> - Have the bgwriter do cleanup work before writing out a block. It
> could probably do the truncation bit above, but totally removing old tuples
> requires cleaning out the indexes too, which AIUI is the hard part of
> vacuuming.
>
> One totally whacked out idea I just thought of: Instead of just
> truncating tuples when they're invisible, mark them "dying" and make the
> data section store an array of CTIDs pointing to the index tuples pointing
> to it. Lookups that find the tuple via an index could store the CTID of
> the index tuple before continuing. If the bgwriter sees it has a full set,
> it can efficiently remove the tuple straight away.
>
> There are ofcourse drawbacks to this approach, you'd probably need
> something like the half-dirty pages to avoid a large increase in write
> load. If it's even beneficial at all given concurrency issues.

A lot of these recommendations sound like garbage collection ideas found
in modern programming languages. Perhaps it would be worth considering
allowing sessions to keep track of which pages they alter and spawn a
separate process per connection to sweep up slowly along the way.

Also, it's nice that vacuum now has slow-down settings, but why isn't
there a option to autovacuum during periods of idleness and pause when
busy?

-M

> Ühel kenal päeval, N, 2006-06-22 kell 12:41, kirjutas Mark Woodward:
>
>> > Depending on exact details and optimisations done, this can be either
>> > slower or faster than postgresql's way, but they still need to do
>> > something to get transactional visibility rules implemented.
>>
>> I think they have a different strategy. I think they maintain the notion
>> of "current version" of a row, and hunt for previous versions when
>> needed,
>> at least that's how I suspect Oracle does it with redo logs.
>
> Not "current" but "last" :)

True
>
> And one side effect of redo logs is that it is practically impossible to
> do large deletes on production databases. So you design around that,
> like you have to design around limitations of MVCC.

Think that's bad, try doing an update in PostgreSQL on a table with 20
million rows and a few indexes. I had to write a script to chunk up the
block update into segments and vacuum between each.

>
>> >> > > There has to be a more linear way of handling this scenario.
>> >> >
>> >> > So vacuum the table often.
>> >>
>> >> It's easy to say VACUUM often... but I'd bet that vacuuming is going
>> >> to lessen the throughput in his tests even more; no matter how it's
>> >> tuned.
>> >
>> > Running VACUUM often/continuously will likely keep his update rate
>> > fluctuatons within a corridor of maybe 5-10%, at the cost of 1-2%
>> extra
>> > load. At least if vacuum is configured right and the server is not
>> > already running at 100% IO saturation, in which case it will be worse.
>>
>> Assuming the table is a reasonable size, the I/O required for vacuum
>> doesn't kill everything else!
>
> I have solved the problem of unneccessary IO by keeping active and
> finished rows in separate tables, with the finish() function moving the
> row between tables.

Sorry, an RDBMS is a "relational database management system," if you are
doing the "database management," it isn't a very good RDBMS.

>
> In case of the number of actively modified rows being in only tens or
> low hundreds of thousands of rows, (i.e. the modified set fits in
> memory) the continuous vacuum process shows up as just another backend,
> not really taking order of magnitude more resources. It mainly generates
> WAL traffic, as modified pages are already in memory/cache and are
> mostly synced by background writer and/or checkpoint.
>
> Of course you have to adjust vacuum_cost_* variables so as to not
> saturate IO.

These sort of solutions, IMHO, don't show how good PostgreSQL is, but show
where it is very lacking.

>
>> > The max throughput figure is not something you actually need very
>> often
>> > in production.
>>
>> No, but you need to have some degree of certainty and predictability in
>> the system you are developing.
>
> Yup. You have to design it so it has.

I was refereing to the system as a whole and the individual components.
PostgreSQL's performance under some pathalogical condictions is not very
predictable or reliable.

>
>> > What is interesting is setting up the server so that you
>> > can service your loads comfortably. Running the server at 100% lead is
>> > not anything you want to do on production server. There will be things
>> > you need to do anyway and you need some headroom for that.
>>
>> Of course, you design it so peaks are easily managed, but unless you run
>> vacuum continuously, and that has its own set of problems, you run into
>> this problem, and it can get really really bad.
>
> Usually it gets really bad if you *don't* run vacuum continuously, maybe
> hopeing to do it in slower times at night. For high-update db you have
> to run it continuously, maybe having some 5-15 sec pauses between runs.

And how much I/O does this take?

> > These sort of solutions, IMHO, don't show how good PostgreSQL is, but show
> > where it is very lacking.
>
> We all know Postgres is lacking; some of us try to improve it (some with
> more success than others). People who know the current limitations but
> like the capabilities, try to find workarounds to the problems. What
> surprises me is that, if you have such a low opinion of Postgres, you
> still use it.

Alvaro, I understand your reaction, you're on the developer side... but
please try to understand us mortals who can't write good C code too:
some of us like what postgres already offers, but we would also like to
not need those workarounds. And the only thing we can do is make big
noise so somebody from the other side (sour side) will notice it and at
one point do something about it... the noise here by no means means we
have a low opinion about postgres. On the contrary, we appreciate enough
postgres and it's developers to ask for what we would like to see, and
we are sure there are some gifted developers out there who can program
those features we scream about...

Cheers,
Csaba.

Ühel kenal päeval, N, 2006-06-22 kell 13:49, kirjutas Mark Woodward:
> > Christopher Browne <cbbrowne(at)acm(dot)org> writes:

> > Basically there's no free lunch: if you want the benefits of MVCC it's
> > going to cost you somewhere. In the Postgres design you pay by having
> > to do VACUUM pretty often for heavily-updated tables. I don't think
> > that decision is fundamentally wrong --- the attractive thing about it
> > is that the overhead is pushed out of the foreground query-processing
> > code paths.
>
> Under certain circumstances, it is a very poor design. Think of a single
> row table that keeps a scoreboard or a session table that keeps a limited
> number of rows that are updated very frequently.

A single row table that every session updates is a really bad design on
any database, as it is a sure point of lock contention and thus removes
any possibility of concurrency.

But except for locking problems, it will perform really well when you
vacuum often enough :)

> > We still have lots of work to do in making autovacuum
> > smarter, avoiding vacuuming parts of relations that have not changed,
> > and so on. But I have no desire to go over to an Oracle-style solution
> > instead. We can't beat them by trying to be like them, and we run no
> > small risk of falling foul of some of their patents if we do.
>
> I proposed having a "key row entry" for each logical row. The key row
> entry points to the latest version of the row. There, each row entry is a
> linked list, in descending order, of previous row versions.

Do I understand right, that you are proposing a redesign of how indexing
works, by updating indexes in-place.

How would older rows be found then by transactions needing to see
them ?

Do you suggest reverting to seqscan when we see _any_ newer
transactions ?

Or if you want to have index pointing to "latest" row with each value in
indexed field, how would you find the last time this value was used ?

Don't tell me that you plan to trace the full update-chain on each
update.

Or would this new indexing mechanism be used only for non-changing key
fields ? How would you check for that ?

> The vast majority of the time, the latest version will be the first version.

Not in a web scenario. In my experience more complicated web-pages tend
to produce lots of concurrent accesses.

> It is
> only when you have a previously started long running or concurrent
> transaction will you ever look at previous versions.
>
> I'm not saying it is an easy slam dunk, as I can think of a few
> difficulties off the top of my head, but it would solve the steady
> degradation of performance between vacuums and, to a possibly lesser
> extent, the cost of updating a row in a heavily indexed table.

VACUUMing often also solves the problem of "steady degradation of
performance between vacuums" :)

No need to be afraid of vacuum. Vacuum is your friend! Just learn to use
it right.

--
----------------
Hannu Krosing
Database Architect
Skype Technologies OÜ
Akadeemia tee 21 F, Tallinn, 12618, Estonia

Skype me: callto:hkrosing
Get Skype for free: http://www.skype.com

> Mark Woodward wrote:
>
>> > In case of the number of actively modified rows being in only tens or
>> > low hundreds of thousands of rows, (i.e. the modified set fits in
>> > memory) the continuous vacuum process shows up as just another
>> backend,
>> > not really taking order of magnitude more resources. It mainly
>> generates
>> > WAL traffic, as modified pages are already in memory/cache and are
>> > mostly synced by background writer and/or checkpoint.
>> >
>> > Of course you have to adjust vacuum_cost_* variables so as to not
>> > saturate IO.
>>
>> These sort of solutions, IMHO, don't show how good PostgreSQL is, but
>> show
>> where it is very lacking.
>
> We all know Postgres is lacking; some of us try to improve it (some with
> more success than others). People who know the current limitations but
> like the capabilities, try to find workarounds to the problems. What
> surprises me is that, if you have such a low opinion of Postgres, you
> still use it.

Actually I love PostgreSQL, I've been using it for about 10 years on a lot
of projects. There are some serious issues with it, however, and it is
important to expose them, discuss them, and resolve them. Work arounds are
great, but in the end, they are work arounds.

On Fri, Jun 23, 2006 at 10:24:06AM -0400, Alvaro Herrera wrote:
> Mark Woodward wrote:
> > > In case of the number of actively modified rows being in only tens or
> > > low hundreds of thousands of rows, (i.e. the modified set fits in
> > > memory) the continuous vacuum process shows up as just another backend,
> > > not really taking order of magnitude more resources. It mainly generates
> > > WAL traffic, as modified pages are already in memory/cache and are
> > > mostly synced by background writer and/or checkpoint.
> > > Of course you have to adjust vacuum_cost_* variables so as to not
> > > saturate IO.
> > These sort of solutions, IMHO, don't show how good PostgreSQL is, but show
> > where it is very lacking.
> We all know Postgres is lacking; some of us try to improve it (some with
> more success than others). People who know the current limitations but
> like the capabilities, try to find workarounds to the problems. What
> surprises me is that, if you have such a low opinion of Postgres, you
> still use it.

If everybody had good opinions, where would the development come from?

It's the parts that suck that need fixing the most... :-)

Cheers,
mark

--
mark(at)mielke(dot)cc / markm(at)ncf(dot)ca / markm(at)nortel(dot)com __________________________
. . _ ._ . . .__ . . ._. .__ . . . .__ | Neighbourhood Coder
|\/| |_| |_| |/ |_ |\/| | |_ | |/ |_ |
| | | | | \ | \ |__ . | | .|. |__ |__ | \ |__ | Ottawa, Ontario, Canada

One ring to rule them all, one ring to find them, one ring to bring them all
and in the darkness bind them...

http://mark.mielke.cc/

Ühel kenal päeval, R, 2006-06-23 kell 10:30, kirjutas Mark Woodward:

> >> > What is interesting is setting up the server so that you
> >> > can service your loads comfortably. Running the server at 100% lead is
> >> > not anything you want to do on production server. There will be things
> >> > you need to do anyway and you need some headroom for that.
> >>
> >> Of course, you design it so peaks are easily managed, but unless you run
> >> vacuum continuously, and that has its own set of problems, you run into
> >> this problem, and it can get really really bad.
> >
> > Usually it gets really bad if you *don't* run vacuum continuously, maybe
> > hopeing to do it in slower times at night. For high-update db you have
> > to run it continuously, maybe having some 5-15 sec pauses between runs.
>
> And how much I/O does this take?

Surprisingly its mostly WAL traffic, the heap/index pages themselves are
often not yet synced to disk by time of vacuum, so no additional traffic
there. If you had made 5 updates per page and then vacuum it, then you
make effectively 1 extra WAL write meaning 20% increase in WAL traffic.

--
----------------
Hannu Krosing
Database Architect
Skype Technologies OÜ
Akadeemia tee 21 F, Tallinn, 12618, Estonia

Skype me: callto:hkrosing
Get Skype for free: http://www.skype.com

> > > Usually it gets really bad if you *don't* run vacuum continuously, maybe
> > > hopeing to do it in slower times at night. For high-update db you have
> > > to run it continuously, maybe having some 5-15 sec pauses between runs.
> >
> > And how much I/O does this take?
>
> Surprisingly its mostly WAL traffic, the heap/index pages themselves are
> often not yet synced to disk by time of vacuum, so no additional traffic
> there. If you had made 5 updates per page and then vacuum it, then you
> make effectively 1 extra WAL write meaning 20% increase in WAL traffic.

Is this also holding about read traffic ? I thought vacuum will make a
full table scan... for big tables a full table scan is always badly
influencing the performance of the box. If the full table scan would be
avoided, then I wouldn't mind running vacuum in a loop...

In fact I think that it would make sense to replace the whole current
vacuum stuff with a background thread which does that continuously using
a dead space map. That could be a heap sorted by tuple deletion time,
and always cleaned up up to the oldest running transaction's start
time... there would be no need for any other autovacuum then.

Cheers,
Csaba.

Ühel kenal päeval, R, 2006-06-23 kell 18:05, kirjutas Csaba Nagy:
> > > > Usually it gets really bad if you *don't* run vacuum continuously, maybe
> > > > hopeing to do it in slower times at night. For high-update db you have
> > > > to run it continuously, maybe having some 5-15 sec pauses between runs.
> > >
> > > And how much I/O does this take?
> >
> > Surprisingly its mostly WAL traffic, the heap/index pages themselves are
> > often not yet synced to disk by time of vacuum, so no additional traffic
> > there. If you had made 5 updates per page and then vacuum it, then you
> > make effectively 1 extra WAL write meaning 20% increase in WAL traffic.
>
> Is this also holding about read traffic ? I thought vacuum will make a
> full table scan... for big tables a full table scan is always badly
> influencing the performance of the box. If the full table scan would be
> avoided, then I wouldn't mind running vacuum in a loop...

I was referring to a design that keeps frequently updated tuples in a
separate table.

> In fact I think that it would make sense to replace the whole current
> vacuum stuff with a background thread which does that continuously using
> a dead space map. That could be a heap sorted by tuple deletion time,
> and always cleaned up up to the oldest running transaction's start
> time... there would be no need for any other autovacuum then.

This has been on todo list for some time already.

>
--
----------------
Hannu Krosing
Database Architect
Skype Technologies OÜ
Akadeemia tee 21 F, Tallinn, 12618, Estonia

Skype me: callto:hkrosing
Get Skype for free: http://www.skype.com

Csaba Nagy <nagy(at)ecircle-ag(dot)com> writes:
>> Surprisingly its mostly WAL traffic, the heap/index pages themselves are
>> often not yet synced to disk by time of vacuum, so no additional traffic
>> there. If you had made 5 updates per page and then vacuum it, then you
>> make effectively 1 extra WAL write meaning 20% increase in WAL traffic.

> Is this also holding about read traffic ? I thought vacuum will make a
> full table scan... for big tables a full table scan is always badly
> influencing the performance of the box. If the full table scan would be
> avoided, then I wouldn't mind running vacuum in a loop...

If you're doing heavy updates of a big table then it's likely to end up
visiting most of the table anyway, no? There is talk of keeping a map
of dirty pages, but I think it'd be a win for infrequently-updated
tables, not ones that need constant vacuuming.

I think a lot of our problems in this area could be solved with fairly
straightforward tuning efforts on the existing autovacuum
infrastructure. In particular, someone should be looking into
recommendable default vacuum-cost-delay settings so that a background
vacuum doesn't affect performance too much. Another problem with the
current autovac infrastructure is that it doesn't respond very well to
the case where there are individual tables that need constant attention
as well as many that don't. If you have N databases then you can visit
a particular table at most once every N*autovacuum_naptime seconds, and
*every* table in the entire cluster gets reconsidered at that same rate.
I'm not sure if we need the ability to have multiple autovac daemons
running at the same time, but we definitely could use something with a
more flexible table-visiting pattern. Perhaps it would be enough to
look through the per-table stats for each database before selecting the
database to autovacuum in each cycle, instead of going by "least
recently autovacuumed".

Bottom line: there's still lots of low-hanging fruit. Why are people
feeling that we need to abandon or massively complicate our basic
architecture to make progress?

regards, tom lane

On Fri, Jun 23, 2006 at 02:30:29PM -0400, Mark Woodward wrote:
> >
> > Bottom line: there's still lots of low-hanging fruit. Why are
> > people feeling that we need to abandon or massively complicate our
> > basic architecture to make progress?
> >
> > regards, tom lane
>
> I, for one, see a particularly nasty unscalable behavior in the
> implementation of MVCC with regards to updates.

You're not answering the question Tom asked. Why not?

> For each update to a row additional work needs to be done to access
> that row. Surely a better strategy can be done, especially
> considering that the problem being solved is a brief one.
>
> The only reason why you need previous versions of a row is for
> transactions that started before or during the transaction that
> seeks to modify a row. After which time, the previous versions
> continue to affect performance and take up space even though they
> are of no value. (Caveats for rollback, etc. but the point is still
> valid).

I wouldn't be so quick to dismiss those as parenthetical "caveats."

> This is a very pessimistic behavior and penalizes the more common
> and optimistic operations. Now, if a tool were to be created that
> could roll back an entire database to some arbitrary transaction ID
> between vacuums, then I can see the usefulnes of the older versions.

There was one called time travel. Somebody might put it back in some
day :)

> I still think an in-place indirection to the current row could fix
> the problem and speed up the database, there are some sticky
> situations that need to be considered, but it shouldn't break much.

We're eagerly awaiting your patch.

Cheers,
D
--
David Fetter <david(at)fetter(dot)org> http://fetter.org/
phone: +1 415 235 3778 AIM: dfetter666
Skype: davidfetter

Remember to vote!

On 6/23/06, Mark Woodward <pgsql(at)mohawksoft(dot)com> wrote:
> I, for one, see a particularly nasty unscalable behavior in the
> implementation of MVCC with regards to updates.

I think this is a fairly common acceptance. The overhead required to
perform an UPDATE in PostgreSQL is pretty heavy. Actually, it's not
really PostgreSQL's implementation, but anything that employs basic
multi-version timestamp ordering (MVTO) style MVCC. Basically,
MVTO-style systems require additional work to be done in an UPDATE so
that queries can find the most current row more quickly.

> This is a very pessimistic behavior

Yes, and that's basically the point of MVTO in general. The nice
thing about MVTO-style MVCC is that it isn't super complicated. No
big UNDO strategy is needed because the old versions are always there
and just have to satisfy a snapshot.

> I still think an in-place indirection to the current row could fix the
> problem and speed up the database, there are some sticky situations that
> need to be considered, but it shouldn't break much.

I agree, but should make clear that moving to an in-place update isn't
a quick-fix; it will require a good amount of design and planning.

What I find in these discussions is that we always talk about over
complicating vacuum in order to fix the poor behavior in MVCC. Fixing
autovacuum does not eliminate the overhead required to add index
entries and everything associated with performing an UPDATE... it's
just cleaning up the mess after the fact. As I see it, fixing the
root problem by moving to update-in-place may add a little more
complication to the core, but will eliminate a lot of the headaches we
have in overhead, performance, and manageability.

--
Jonah H. Harris, Software Architect | phone: 732.331.1300
EnterpriseDB Corporation | fax: 732.331.1301
33 Wood Ave S, 2nd Floor | jharris(at)enterprisedb(dot)com
Iselin, New Jersey 08830 | http://www.enterprisedb.com/

>
> Bottom line: there's still lots of low-hanging fruit. Why are people
> feeling that we need to abandon or massively complicate our basic
> architecture to make progress?
>
> regards, tom lane

I, for one, see a particularly nasty unscalable behavior in the
implementation of MVCC with regards to updates.

For each update to a row additional work needs to be done to access that
row. Surely a better strategy can be done, especially considering that the
problem being solved is a brief one.

The only reason why you need previous versions of a row is for
transactions that started before or during the transaction that seeks to
modify a row. After which time, the previous versions continue to affect
performance and take up space even though they are of no value.
(Caveats for rollback, etc. but the point is still valid).

This is a very pessimistic behavior and penalizes the more common and
optimistic operations. Now, if a tool were to be created that could roll
back an entire database to some arbitrary transaction ID between vacuums,
then I can see the usefulnes of the older versions.

I still think an in-place indirection to the current row could fix the
problem and speed up the database, there are some sticky situations that
need to be considered, but it shouldn't break much.

On 6/23/06, Mark Woodward wrote:
>
> For each update to a row additional work needs to be done to access that
> row. Surely a better strategy can be done, especially considering that the
> problem being solved is a brief one.
>
> The only reason why you need previous versions of a row is for
> transactions that started before or during the transaction that seeks to
> modify a row. After which time, the previous versions continue to affect
> performance and take up space even though they are of no value.
> (Caveats for rollback, etc. but the point is still valid).
>
> This is a very pessimistic behavior and penalizes the more common and
> optimistic operations.

Are you sure about that? ISTM that for the most common cases the TID
returned by an indexscan is the one of the last version and only if
that vbersion is too new a second TID is tried etc.

Jochem

Tom Lane wrote:
> If you're doing heavy updates of a big table then it's likely to end up
> visiting most of the table anyway, no? There is talk of keeping a map
> of dirty pages, but I think it'd be a win for infrequently-updated
> tables, not ones that need constant vacuuming.
>
> I think a lot of our problems in this area could be solved with fairly
> straightforward tuning efforts on the existing autovacuum
> infrastructure. In particular, someone should be looking into
> recommendable default vacuum-cost-delay settings so that a background
> vacuum doesn't affect performance too much. Another problem with the
> current autovac infrastructure is that it doesn't respond very well to
> the case where there are individual tables that need constant attention
> as well as many that don't. If you have N databases then you can visit
> a particular table at most once every N*autovacuum_naptime seconds, and
> *every* table in the entire cluster gets reconsidered at that same rate.
> I'm not sure if we need the ability to have multiple autovac daemons
> running at the same time, but we definitely could use something with a
> more flexible table-visiting pattern. Perhaps it would be enough to
> look through the per-table stats for each database before selecting the
> database to autovacuum in each cycle, instead of going by "least
> recently autovacuumed".
>
> Bottom line: there's still lots of low-hanging fruit. Why are people
> feeling that we need to abandon or massively complicate our basic
> architecture to make progress?

I think at some point we have to admit that _polling_ the tables, which
is what autovacuum does, just isn't going to work well, no matter how
much it is tweeked, and another approach should be considered for
certain workload cases.

At some point, the autovacuum approach starts to look like a car with
fifty bumper stickers. The first few were fine, but at some point, the
tweeks (bumper stickers) start to overwhelm the car, and it is time to
look for a new car.

I think particularly for the UPDATE with no index key changes, a new
approach must be considred.

--
Bruce Momjian bruce(at)momjian(dot)us
EnterpriseDB http://www.enterprisedb.com

+ If your life is a hard drive, Christ can be your backup. +

* Gavin Sherry:

> Tom Lane's MVCC talk:
> http://www.postgresql.org/files/developer/transactions.pdf

Is this still up-to-date with regard to to partial page writes?
I hope that has been fixed (like the fsync issue).

Bruce Momjian <bruce(at)momjian(dot)us> writes:
> I think at some point we have to admit that _polling_ the tables, which
> is what autovacuum does, just isn't going to work well, no matter how
> much it is tweeked, and another approach should be considered for
> certain workload cases.

Autovacuum polls in its current, first-generation implementation;
what I said upthread was it needs to be smarter than that. I am not
sure how you get from that to the conclusion that the very next step
is to abandon the vacuuming approach altogether.

What I see in this discussion is a huge amount of "the grass must be
greener on the other side" syndrome, and hardly any recognition that
every technique has its downsides and complications. Furthermore,
I do not believe that this project has the ability to support multiple
fundamental storage models, as a number of people seem to be blithely
suggesting. We're having a hard enough time debugging and optimizing
*one* storage model. I think the correct path forward is to stick with
the same basic storage model and vacuuming concept, and address the
known performance issues with better-optimized vacuuming. No, it will
never be perfect for every scenario, but we can certainly make it much
better than it is now, without risking killing the project by
introducing undebuggable, unmaintainable complexity.

regards, tom lane

Tom Lane wrote:
> Bruce Momjian <bruce(at)momjian(dot)us> writes:
> > I think at some point we have to admit that _polling_ the tables, which
> > is what autovacuum does, just isn't going to work well, no matter how
> > much it is tweeked, and another approach should be considered for
> > certain workload cases.
>
> Autovacuum polls in its current, first-generation implementation;
> what I said upthread was it needs to be smarter than that. I am not
> sure how you get from that to the conclusion that the very next step
> is to abandon the vacuuming approach altogether.

I am not ready to abandon autovacuum, but as I stated later the UPDATE
with no key change case is common enought that it could be handled
better without involving autovacuum and its limitations.

As I remember, most databases have problem with DELETE/INSERT cycles,
but we seem to be hit by UPDATE performance more than most, and more
than is wise.

> What I see in this discussion is a huge amount of "the grass must be
> greener on the other side" syndrome, and hardly any recognition that
> every technique has its downsides and complications. Furthermore,
> I do not believe that this project has the ability to support multiple
> fundamental storage models, as a number of people seem to be blithely
> suggesting. We're having a hard enough time debugging and optimizing
> *one* storage model. I think the correct path forward is to stick with
> the same basic storage model and vacuuming concept, and address the
> known performance issues with better-optimized vacuuming. No, it will
> never be perfect for every scenario, but we can certainly make it much
> better than it is now, without risking killing the project by
> introducing undebuggable, unmaintainable complexity.

Well, are you suggesting we just stop improving the database? I am sure
not. But, your suggestion is that we can't do better without incurring
more complexity (true), and that complexity will not be worth it. I
don't agree with that until I see some proposals, and shutting down
discussion because they will add complexity or are fruitless seems
unwise.

--
Bruce Momjian bruce(at)momjian(dot)us
EnterpriseDB http://www.enterprisedb.com

+ If your life is a hard drive, Christ can be your backup. +

> On 6/23/06, Mark Woodward <pgsql(at)mohawksoft(dot)com> wrote:
>> I, for one, see a particularly nasty unscalable behavior in the
>> implementation of MVCC with regards to updates.
>
> I think this is a fairly common acceptance. The overhead required to
> perform an UPDATE in PostgreSQL is pretty heavy. Actually, it's not
> really PostgreSQL's implementation, but anything that employs basic
> multi-version timestamp ordering (MVTO) style MVCC. Basically,
> MVTO-style systems require additional work to be done in an UPDATE so
> that queries can find the most current row more quickly.
>
>> This is a very pessimistic behavior
>
> Yes, and that's basically the point of MVTO in general. The nice
> thing about MVTO-style MVCC is that it isn't super complicated. No
> big UNDO strategy is needed because the old versions are always there
> and just have to satisfy a snapshot.
>
>> I still think an in-place indirection to the current row could fix the
>> problem and speed up the database, there are some sticky situations that
>> need to be considered, but it shouldn't break much.
>
> I agree, but should make clear that moving to an in-place update isn't
> a quick-fix; it will require a good amount of design and planning.

This is NOT an "in-place" update. The whole MVCC strategy of keeping old
versions around doesn't change. The only thing that does change is one
level of indirection. Rather than keep references to all versions of all
rows in indexes, keep only a reference to the first or "key" row of each
row, and have the first version of a row form the head of a linked list to
subsequent versions of each row. The list will be in decending order.

In the vast majority of cases, the overhead of this action will be
trivial. In an unmodified row, you're there. In a modified row, you have
one extra lookup. In extream cases, you may have to go back a few
versions, but I don't see that as a common behavior.

On a heavily updated row, you are never more than one jump away, the
indexes shouldn't grow overly much.

>
> What I find in these discussions is that we always talk about over
> complicating vacuum in order to fix the poor behavior in MVCC. Fixing
> autovacuum does not eliminate the overhead required to add index
> entries and everything associated with performing an UPDATE... it's
> just cleaning up the mess after the fact. As I see it, fixing the
> root problem by moving to update-in-place may add a little more
> complication to the core, but will eliminate a lot of the headaches we
> have in overhead, performance, and manageability.

Vacuum is a tool for removing old versions. I think there is an overly
eager tendency to have it fix other problems.

On 6/23/06, Mark Woodward <pgsql(at)mohawksoft(dot)com> wrote:
> Rather than keep references to all versions of all
> rows in indexes, keep only a reference to the first or "key" row of each
> row, and have the first version of a row form the head of a linked list to
> subsequent versions of each row. The list will be in decending order.

By all means, please go ahead and try it because it's not quite that
easy. You're going to run into serious locking and contention issues
this way. In the end, it's not much better than running a sequential
scan to query a row that's been updated several thousand times on a
table that hasn't been vacuumed... follow that pointer :)

--
Jonah H. Harris, Software Architect | phone: 732.331.1300
EnterpriseDB Corporation | fax: 732.331.1301
33 Wood Ave S, 2nd Floor | jharris(at)enterprisedb(dot)com
Iselin, New Jersey 08830 | http://www.enterprisedb.com/

> Tom Lane wrote:
>> If you're doing heavy updates of a big table then it's likely to end up
>> visiting most of the table anyway, no? There is talk of keeping a map
>> of dirty pages, but I think it'd be a win for infrequently-updated
>> tables, not ones that need constant vacuuming.
>>
>> I think a lot of our problems in this area could be solved with fairly
>> straightforward tuning efforts on the existing autovacuum
>> infrastructure. In particular, someone should be looking into
>> recommendable default vacuum-cost-delay settings so that a background
>> vacuum doesn't affect performance too much. Another problem with the
>> current autovac infrastructure is that it doesn't respond very well to
>> the case where there are individual tables that need constant attention
>> as well as many that don't. If you have N databases then you can visit
>> a particular table at most once every N*autovacuum_naptime seconds, and
>> *every* table in the entire cluster gets reconsidered at that same rate.
>> I'm not sure if we need the ability to have multiple autovac daemons
>> running at the same time, but we definitely could use something with a
>> more flexible table-visiting pattern. Perhaps it would be enough to
>> look through the per-table stats for each database before selecting the
>> database to autovacuum in each cycle, instead of going by "least
>> recently autovacuumed".
>>
>> Bottom line: there's still lots of low-hanging fruit. Why are people
>> feeling that we need to abandon or massively complicate our basic
>> architecture to make progress?
>
> I think at some point we have to admit that _polling_ the tables, which
> is what autovacuum does, just isn't going to work well, no matter how
> much it is tweeked, and another approach should be considered for
> certain workload cases.

Thank you, that is *eactly* the anaology I have been unable to formulate.
It was on my mind but I could not put my finger on it.

Vacuum is findimentally inefficient as it does not know what has changed
and must go through an entirety to find the specific each time. Going
through the whole table each time is messed up and wasteful.

>
> At some point, the autovacuum approach starts to look like a car with
> fifty bumper stickers. The first few were fine, but at some point, the
> tweeks (bumper stickers) start to overwhelm the car, and it is time to
> look for a new car.
>
> I think particularly for the UPDATE with no index key changes, a new
> approach must be considred.
>

I have been ranting about a first row strategy, one where the first
version of a row is the top of a linked list of versions.

(1) The indexes point to the first "key" row.
(2) When a row is updated, it is found in the various indexes, if the key
row currenlty exists in the index, no changes to the index are made. If it
is not found, the old version of the row is orphaned and behaves as
PostgreSQL always behaves.
(3) If the row is not orphaned, its "last version" reference is updated.

For the most part, this should only affect updates where the index entries
don't change. If the index value is always change, PostgreSQL will behave
as it currently does. If the index values do not change, updates will be
faster to do and won't impact queries.

On 6/23/06, Mark Woodward <pgsql(at)mohawksoft(dot)com> wrote:
> Vacuum is findimentally inefficient

The theory of database cleanup (VACUUM) is good, but has nothing to do
with the overhead we currently encounter in performing an update.

> I have been ranting about a first row strategy, one where the first
> version of a row is the top of a linked list of versions.

> (1) The indexes point to the first "key" row.

I'm with ya.

> (2) When a row is updated, [...] If it is not found [in the index], the
> old version of the row is orphaned and behaves as PostgreSQL
> always behaves.

aka current bad update behavior.

> (3) If the row is not orphaned, its "last version" reference is updated.

The *last version* reference? Where is this, another entry on the
tuple header (extra size overhead on every tuple) or updating the
index (additional locking+WAL)? Following something like the ctid?
How is that really any different than performing a sequential scan
from the index as a starting point? That could still encounter
multiple physical I/Os to get to the current row and is potentially
very slow. Sure, we can add extra free space to each block to limit
tuple version migration across blocks... combined with constant
vacuuming and FSM updates we'd get some great performance.

Of course, we could just avoid the overcomplication and locking issues
of having to tune block-level freespace, vacuum, and tweaking FSM for
each type of application, but where's the fun in that? (yes, that was
a badly placed sarchastic joke)

> For the most part, this should only affect updates where the index entries
> don't change. If the index value is always change, PostgreSQL will behave
> as it currently does. If the index values do not change, updates will be
> faster to do and won't impact queries.

I like the idea of a new strategy when index entries do not change.
But, like Tom said, there is no free lunch; in your example you're
moving the high cost of an UPDATE to even more costly SELECTs.

This is something that requires a good amount of planning and design,
and I'm really glad to see some ideas being thrown into this
discussion.

--
Jonah H. Harris, Software Architect | phone: 732.331.1300
EnterpriseDB Corporation | fax: 732.331.1301
33 Wood Ave S, 2nd Floor | jharris(at)enterprisedb(dot)com
Iselin, New Jersey 08830 | http://www.enterprisedb.com/

Tom Lane wrote:
> Bruce Momjian <bruce(at)momjian(dot)us> writes:
>> I think at some point we have to admit that _polling_ the tables, which
>> is what autovacuum does, just isn't going to work well, no matter how
>> much it is tweeked, and another approach should be considered for
>> certain workload cases.
>
> Autovacuum polls in its current, first-generation implementation;
> what I said upthread was it needs to be smarter than that. I am not
> sure how you get from that to the conclusion that the very next step
> is to abandon the vacuuming approach altogether.

yeah autovacuum still can be improved quite a lot, but as always this
can be done on a step by step base.

>
> What I see in this discussion is a huge amount of "the grass must be
> greener on the other side" syndrome, and hardly any recognition that
> every technique has its downsides and complications. Furthermore,
> I do not believe that this project has the ability to support multiple
> fundamental storage models, as a number of people seem to be blithely
> suggesting. We're having a hard enough time debugging and optimizing
> *one* storage model. I think the correct path forward is to stick with
> the same basic storage model and vacuuming concept, and address the
> known performance issues with better-optimized vacuuming. No, it will
> never be perfect for every scenario, but we can certainly make it much
> better than it is now, without risking killing the project by
> introducing undebuggable, unmaintainable complexity.

While I'm not an expert on MVCC - it certainly seems that sticking to
the current storage model and continuing to improve on it (especially
wrt vacuum performance) gradually over time (as it has happened for the
last years) is a much better and safer approach than trying to do
something revolutionary which in theory might (or might not) be better
than the current approach for this or that workload.

PostgreSQL got a _LOT_ faster for each of the last releases and by my
testing -HEAD is already significantly(20-30%) faster for some of our
apps than 8.1 and all that was achieved without radically redesigning a
proven (reliability wise) storage engine.
Maybe and only maybe one day(or when somebody comes up with a usable
patch - as always) we will at the point where we really need to think
about doing that but for now there seems to be still a lot of low
hanging fruit left to improve for month and years to come.

Stefan

On 6/23/06, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> What I see in this discussion is a huge amount of "the grass must be
> greener on the other side" syndrome, and hardly any recognition that
> every technique has its downsides and complications.

I'm being totally objective. I don't think we should abandon
PostgreSQL's overall design at all, because we do perform INSERTs and
DELETEs much better than most systems. However, I've looked at many
systems and how they implement UPDATE so that it is a scalable
operation. Sure, there are costs and benefits to each implementation,
but I think we have some pretty brilliant people in this community and
can come up with an elegant design for scalable UPDATEs.

> Furthermore, I do not believe that this project has the ability to
> support multiple fundamental storage models, as a number of
> people seem to be blithely suggesting.

The fundamental storage model was not designed to be scalable. Many
improvements have been done to get it where it is today. The
improvements are certainly good but the model itself it isn't perfect
and sometimes things need to be redesigned a bit every now and again.
To be clear though, I'm in no way suggesting that we trash and rewrite
PostgreSQL's storage architecture.

> we can certainly make it much
> better than it is now, without risking killing the project by
> introducing undebuggable, unmaintainable complexity.

I'm not saying we rewrite the entire system in C++ (as Firebird
did)... that was a risky and possibly project-killing move. I see us
changing the way a single operation works through community-oriented
planning and design. This approach seems to have worked for years...
and includes the MVCC implementation itself.

--
Jonah H. Harris, Software Architect | phone: 732.331.1300
EnterpriseDB Corporation | fax: 732.331.1301
33 Wood Ave S, 2nd Floor | jharris(at)enterprisedb(dot)com
Iselin, New Jersey 08830 | http://www.enterprisedb.com/

Jonah H. Harris wrote:
> On 6/23/06, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> > What I see in this discussion is a huge amount of "the grass must be
> > greener on the other side" syndrome, and hardly any recognition that
> > every technique has its downsides and complications.
>
> I'm being totally objective. I don't think we should abandon
> PostgreSQL's overall design at all, because we do perform INSERTs and
> DELETEs much better than most systems. However, I've looked at many
> systems and how they implement UPDATE so that it is a scalable
> operation. Sure, there are costs and benefits to each implementation,
> but I think we have some pretty brilliant people in this community and
> can come up with an elegant design for scalable UPDATEs.

I think the UPDATE case is similar to the bitmap index scan or perhaps
bitmap indexes on disk --- there are cases we know can not be handled
well by our existing code, so we have added (or might add) these
features to try to address those difficult cases.

--
Bruce Momjian bruce(at)momjian(dot)us
EnterpriseDB http://www.enterprisedb.com

+ If your life is a hard drive, Christ can be your backup. +

Just out of curiosity Mark, didn't you write your session daemon so
that you don't have to put sessions in postgres anymore? Or are you
just giving that as an example of a very wide, very heavily updated
table? My session tables have been an extreme case of this problem,
but no other table that I have is so adversely affected by this
behavior. My decision was not to pull postgres out entirely, just
using other session handlers.

Rick

On Jun 22, 2006, at 7:59 AM, Mark Woodward wrote:

>> After a long battle with technology, pgsql(at)mohawksoft(dot)com ("Mark
>> Woodward"), an earthling, wrote:
>>>> Clinging to sanity, pgsql(at)mohawksoft(dot)com ("Mark Woodward")
>>>> mumbled into
>>>> her beard:
> [snip]
>>>>
>>>> 1. The index points to all the versions, until they get
>>>> vacuumed out.
>>>
>>> It can't point to "all" versions, it points to the last "current"
>>> version
>>> as updated by vacuum, or the first version of the row.
>>
>> No, it points to *all* the versions.
>>
>> Suppose I take a table with two rows:
>>
>> INFO: analyzing "public.test"
>> INFO: "test": 1 pages, 2 rows sampled, 2 estimated total rows
>> VACUUM
>>
>> Then, over and over, I remove and insert one entry with the same PK:
>>
>> sample=# delete from test where id = 2;insert into test (id)
>> values (2);
>> DELETE 1
>
> [snip]
>>
>> Now, I vacuum it.
>>
>> sample=# vacuum verbose analyze test;
>> INFO: vacuuming "public.test"
>> INFO: index "test_id_key" now contains 2 row versions in 2 pages
>> DETAIL: 10 index row versions were removed.
>> 0 index pages have been deleted, 0 are currently reusable.
>> CPU 0.00s/0.00u sec elapsed 0.00 sec.
>> INFO: "test": removed 10 row versions in 1 pages
>> DETAIL: CPU 0.00s/0.00u sec elapsed 0.00 sec.
>> INFO: "test": found 10 removable, 2 nonremovable row versions in
>> 1 pages
>> DETAIL: 0 dead row versions cannot be removed yet.
>> There were 0 unused item pointers.
>> 0 pages are entirely empty.
>> CPU 0.00s/0.00u sec elapsed 0.00 sec.
>> INFO: analyzing "public.test"
>> INFO: "test": 1 pages, 2 rows sampled, 2 estimated total rows
>> VACUUM
>>
>> Notice that the index contained 10 versions of that one row.
>>
>> It pointed to *ALL* the versions.
>
> Hmm, OK, then the problem is more serious than I suspected.
> This means that every index on a row has to be updated on every
> transaction that modifies that row. Is that correct?
>
> I am attaching some code that shows the problem with regard to
> applications such as web server session management, when run, each
> second
> the system can handle fewer and fewer connections. Here is a brief
> output:
>
> markw(at)ent:~/pgfoo$ ./footest
> 1307 sessions per second, elapsed: 1
> 1292 sessions per second, elapsed: 2
> 1287 sessions per second, elapsed: 3
> ....
> 1216 sessions per second, elapsed: 25
> 1213 sessions per second, elapsed: 26
> 1208 sessions per second, elapsed: 27
> ....
> 1192 sessions per second, elapsed: 36
> 1184 sessions per second, elapsed: 37
> 1183 sessions per second, elapsed: 38
> ....
> 1164 sessions per second, elapsed: 58
> 1170 sessions per second, elapsed: 59
> 1168 sessions per second, elapsed: 60
>
> As you can see, in about a minute at high load, this very simple table
> lost about 10% of its performance, and I've seen worse based on update
> frequency. Before you say this is an obscure problem, I can tell
> you it
> isn't. I have worked with more than a few projects that had to
> switch away
> from PostgreSQL because of this behavior.
>
> Obviously this is not a problem with small sites, but this is a real
> problem with an enterprise level web site with millions of visitors
> and
> actions a day. Quite frankly it is a classic example of something that
> does not scale. The more and more updates there are, the higher the
> load
> becomes. You can see it on "top" as the footest program runs.
>
> There has to be a more linear way of handling this scenario.
> <footest.c>
>
> ---------------------------(end of
> broadcast)---------------------------
> TIP 6: explain analyze is your friend

On Jun 22, 2006, at 10:33 AM, Mark Woodward wrote:

>> Ühel kenal päeval, N, 2006-06-22 kell 09:59, kirjutas Mark
>> Woodward:
>>>> After a long battle with technology, pgsql(at)mohawksoft(dot)com ("Mark
>>>> Woodward"), an earthling, wrote:
>>>>>> Clinging to sanity, pgsql(at)mohawksoft(dot)com ("Mark Woodward")
>>>>>> mumbled
>>> into
>>>> It pointed to *ALL* the versions.
>>>
>>> Hmm, OK, then the problem is more serious than I suspected.
>>> This means that every index on a row has to be updated on every
>>> transaction that modifies that row. Is that correct?
>>
>> Yes.
>>
>>> I am attaching some code that shows the problem with regard to
>>> applications such as web server session management, when run, each
>>> second
>>> the system can handle fewer and fewer connections. Here is a brief
>>> output:
>>>
>>> markw(at)ent:~/pgfoo$ ./footest
>>> 1307 sessions per second, elapsed: 1
>>> 1292 sessions per second, elapsed: 2
>>> 1287 sessions per second, elapsed: 3
>>> ....
>>> 1216 sessions per second, elapsed: 25
>>> 1213 sessions per second, elapsed: 26
>>> 1208 sessions per second, elapsed: 27
>>> ....
>>> 1192 sessions per second, elapsed: 36
>>> 1184 sessions per second, elapsed: 37
>>> 1183 sessions per second, elapsed: 38
>>> ....
>>> 1164 sessions per second, elapsed: 58
>>> 1170 sessions per second, elapsed: 59
>>> 1168 sessions per second, elapsed: 60
>>>
>>> As you can see, in about a minute at high load, this very simple
>>> table
>>> lost about 10% of its performance, and I've seen worse based on
>>> update
>>> frequency. Before you say this is an obscure problem, I can tell
>>> you it
>>> isn't. I have worked with more than a few projects that had to
>>> switch
>>> away
>>> from PostgreSQL because of this behavior.
>>
>> You mean systems that are designed so exactly, that they can't
>> take 10%
>> performance change ?
>
> No, that's not really the point, performance degrades over time, in
> one
> minute it degraded 10%.
>
> The update to session ratio has a HUGE impact on PostgreSQL. If you
> have a
> thousand active sessions, it may take a minute to degrade 10% assuming
> some level of active vs operations per session per action.

How big are your session? Running with about 1000 sessions, running
vacuum on just the session table is so fast it is barely noticeable.
Vacuuming my session table every 5 minutes keeps them very, very
small and easy to vacuum and performance degradation is not an
issue. I could probably do it every minute if I had to and it would
be fine. But my sessions are only about 5k on average.

What is a bigger concern for me is the massive amount of writes to
the disk that happen in postgres to make sure the data is safe. It's
just a waste of disk bandwidth for data for data that is transient
anyway.

To me postgres (and rdbms's in general) are just not good for
handling session data for web apps. Once again isn't that why you
wrote mcache?

>
> If an active user causes a session update once a second, that is
> not too
> bad, but if an active user updates a session more often, then it is
> worse.
>
> Generally speaking, sessions aren't updated when they change, they are
> usually updated per HTTP request. The data in a session may not
> change,
> but the session handling code doesn't know this and simply updates
> anyway.

This problem is more or less specific to php no? Because it reads
the whole session on session open and writes the whole thing on
close. Because of this I am looking into smarter ways of handling
sessions than this. Because yes, the session data RARELY changes. I
am looking into ways of only doing updates when the data changes. In
fact for a very similar problem, where I had tons of tiny requests
coming in that would NEVER alter the sessions I skipped session_start
and used my own session_touch function to update the timestamp on the
session because that's all I needed to do. It saved TONS of wasted
overhead.

I don't mean to get off topic but it seems like these sorts of
problems are better solved outside of postgres. I think your session
daemon is in fact the right approach here. If you have other tables
with similar problems that is one thing but if it is just php session
tables then I think we need to look for a better use case to look
into this.

>
> In a heavily AJAX site, you may have many smaller HTTP requests
> returning
> items in a page. So, a single page may consist of multiple HTTP
> requests.
> Worse yet, as a user drags an image around, there are lots of
> background
> requests being made. Each request typically means a session lookup
> and a
> session update. This is compounded by the number of active users.
> Since
> the object of a site is to have many active users, this is always a
> problem. It is less intrusive now that non-locking vacuum is there,
> but
> that doesn't mean it isn't a problem.

Once again I think to run an "Enterprise" app (and by that I mean it
scales well) you need "Enterprise" class session management. The php
model is not good for this and using postgres is not good for this.
It's just not the right tool for this job in my opinion. I would
think you could gain WAY more by using a more intelligent session
handling model then you could ever eek out of postgres for this problem.

>
>>
>> Or just that they did not vacuum for so long, that performance was
>> less
>> than needed in the end?
>
> In an active site or application, vacuuming often enough to prevent
> this
> often is, itself, a load on the system.

Once again this is just anecdotal evidence but for me that load is
virtually unnoticeable it is so small. The key here is that session
tables are SMALL. That is less than a few thousand rows. Maybe you
are storing a lot more data in there than I am but for me a vacuum
every 5 minutes solves the problem performance degradation. It is
still too much disk bandwidth though so I am just going to stop
storing sessions in postgres.

>
>>
>> btw, what did they switch to ?
>
> One switched to oracle and one is using a session handler I wrote
> for PHP.

Just switching the session handler sounds like a pretty good
solutions to this problem to me.

just my $0.02

Rick

On Jun 22, 2006, at 2:36 PM, Mark Woodward wrote:

>>
>>> What you seem not to grasp at this point is a large web-farm,
>>> about 10
>>> or
>>> more servers running PHP, Java, ASP, or even perl. The database is
>>> usually
>>> the most convenient and, aside from the particular issue we are
>>> talking
>>> about, best suited.
>>
>> The answer is sticky sessions : each user is assigned to one and
>> only one
>> webserver in the cluster and his session is maintained locally, in
>> RAM. No
>> locks, no need to manage distributed session...
>>
>>> I actually have a good number of years of experience in this
>>> topic, and
>>> memcached or file system files are NOT the best solutions for a
>>> server
>>> farm.
>>
>> If sessions are distributed, certainly, but if sessions are
>> sticky to
>> their own server ?
>
> And what if a particulr server goes down? or gets too high a
> percentage of
> the load?

Yes, I don't think that sticky sessions are the answer. But phps
session handling behavior could be greatly improved on.

On Fri, Jun 23, 2006 at 03:08:34PM -0400, Bruce Momjian wrote:
> Tom Lane wrote:
> > ...
> > suggesting. We're having a hard enough time debugging and optimizing
> > *one* storage model. I think the correct path forward is to stick with
> > the same basic storage model and vacuuming concept, and address the
> > known performance issues with better-optimized vacuuming. No, it will
> > never be perfect for every scenario, but we can certainly make it much
> > better than it is now, without risking killing the project by
> > introducing undebuggable, unmaintainable complexity.
> Well, are you suggesting we just stop improving the database? I am sure
> not. But, your suggestion is that we can't do better without incurring
> more complexity (true), and that complexity will not be worth it. I
> don't agree with that until I see some proposals, and shutting down
> discussion because they will add complexity or are fruitless seems
> unwise.

It sounds like everybody agrees that things need to be fixed, and genuinely
motivated people are trying to offer what they have to the table.

Tom already has enough on his plate, as do most others here - so unless
a competent champion can take up the challenge, discussion is all we have.

I'm not liking the "we should do it this way," "no, we should do it that."
My read of the situation is that both may be useful, and that both should
be pursued. But one set of people can't pursue both.

Is any who is able, able to take up this challenge? Perhaps more than one,
from both major directions? (vacuum on one side, and improved storage on
the other) Somebody with the time and skill, who can work through the
design discussions on one of the aspects?

I want to contribute soon, and this is the sort of thing that interests me -
but I still don't have time yet, and there would be no guarantee that I
succeeded. Somebody else? :-)

Cheers,
mark

--
mark(at)mielke(dot)cc / markm(at)ncf(dot)ca / markm(at)nortel(dot)com __________________________
. . _ ._ . . .__ . . ._. .__ . . . .__ | Neighbourhood Coder
|\/| |_| |_| |/ |_ |\/| | |_ | |/ |_ |
| | | | | \ | \ |__ . | | .|. |__ |__ | \ |__ | Ottawa, Ontario, Canada

One ring to rule them all, one ring to find them, one ring to bring them all
and in the darkness bind them...

http://mark.mielke.cc/

> Just out of curiosity Mark, didn't you write your session daemon so
> that you don't have to put sessions in postgres anymore?

The original project started as a shared key/value system for a beowulf
cluster in the late 90s, but got reworked to be a session handler for PHP
when I worked with Stig, MSession.

> Or are you
> just giving that as an example of a very wide, very heavily updated
> table? My session tables have been an extreme case of this problem,
> but no other table that I have is so adversely affected by this
> behavior. My decision was not to pull postgres out entirely, just
> using other session handlers.

I have been working as a consultant since 2001, and prior to that, as CTO
at at a dot.com startup. MSession (the previous name) was used to
circumvent shortcomings in PostgreSQL, specificially the problem we are
talking about.

As a consultant, I have to convince the customer that "all is well." My
MCache system does not guarentee that no session data lost, nor does
memcached or other non-ACID system.

The technical arguments we can make, no matter how correct, leave us on
the defensive when asked "What if the server crashes, do you lose data?"
of course the answer is "yes." Then we get drawn into a conversation about
transient and unimportant data vs persistent and valuable data. At which
point you've lost the customer. A solid SQL database is the defacto
standard, perhaps not the best choice, but unavoidable.

The update behavior of PostgreSQL is probably the *last* serious issue.
Debate all you want, vacuum mitigates the problem to varying levels,
fixing the problem will be a huge win. If the update behavior gets fixed,
I can't think of a single issue with postgresql that would be a show
stopper.

>
> Rick
>
> On Jun 22, 2006, at 7:59 AM, Mark Woodward wrote:
>
>>> After a long battle with technology, pgsql(at)mohawksoft(dot)com ("Mark
>>> Woodward"), an earthling, wrote:
>>>>> Clinging to sanity, pgsql(at)mohawksoft(dot)com ("Mark Woodward")
>>>>> mumbled into
>>>>> her beard:
>> [snip]
>>>>>
>>>>> 1. The index points to all the versions, until they get
>>>>> vacuumed out.
>>>>
>>>> It can't point to "all" versions, it points to the last "current"
>>>> version
>>>> as updated by vacuum, or the first version of the row.
>>>
>>> No, it points to *all* the versions.
>>>
>>> Suppose I take a table with two rows:
>>>
>>> INFO: analyzing "public.test"
>>> INFO: "test": 1 pages, 2 rows sampled, 2 estimated total rows
>>> VACUUM
>>>
>>> Then, over and over, I remove and insert one entry with the same PK:
>>>
>>> sample=# delete from test where id = 2;insert into test (id)
>>> values (2);
>>> DELETE 1
>>
>> [snip]
>>>
>>> Now, I vacuum it.
>>>
>>> sample=# vacuum verbose analyze test;
>>> INFO: vacuuming "public.test"
>>> INFO: index "test_id_key" now contains 2 row versions in 2 pages
>>> DETAIL: 10 index row versions were removed.
>>> 0 index pages have been deleted, 0 are currently reusable.
>>> CPU 0.00s/0.00u sec elapsed 0.00 sec.
>>> INFO: "test": removed 10 row versions in 1 pages
>>> DETAIL: CPU 0.00s/0.00u sec elapsed 0.00 sec.
>>> INFO: "test": found 10 removable, 2 nonremovable row versions in
>>> 1 pages
>>> DETAIL: 0 dead row versions cannot be removed yet.
>>> There were 0 unused item pointers.
>>> 0 pages are entirely empty.
>>> CPU 0.00s/0.00u sec elapsed 0.00 sec.
>>> INFO: analyzing "public.test"
>>> INFO: "test": 1 pages, 2 rows sampled, 2 estimated total rows
>>> VACUUM
>>>
>>> Notice that the index contained 10 versions of that one row.
>>>
>>> It pointed to *ALL* the versions.
>>
>> Hmm, OK, then the problem is more serious than I suspected.
>> This means that every index on a row has to be updated on every
>> transaction that modifies that row. Is that correct?
>>
>> I am attaching some code that shows the problem with regard to
>> applications such as web server session management, when run, each
>> second
>> the system can handle fewer and fewer connections. Here is a brief
>> output:
>>
>> markw(at)ent:~/pgfoo$ ./footest
>> 1307 sessions per second, elapsed: 1
>> 1292 sessions per second, elapsed: 2
>> 1287 sessions per second, elapsed: 3
>> ....
>> 1216 sessions per second, elapsed: 25
>> 1213 sessions per second, elapsed: 26
>> 1208 sessions per second, elapsed: 27
>> ....
>> 1192 sessions per second, elapsed: 36
>> 1184 sessions per second, elapsed: 37
>> 1183 sessions per second, elapsed: 38
>> ....
>> 1164 sessions per second, elapsed: 58
>> 1170 sessions per second, elapsed: 59
>> 1168 sessions per second, elapsed: 60
>>
>> As you can see, in about a minute at high load, this very simple table
>> lost about 10% of its performance, and I've seen worse based on update
>> frequency. Before you say this is an obscure problem, I can tell
>> you it
>> isn't. I have worked with more than a few projects that had to
>> switch away
>> from PostgreSQL because of this behavior.
>>
>> Obviously this is not a problem with small sites, but this is a real
>> problem with an enterprise level web site with millions of visitors
>> and
>> actions a day. Quite frankly it is a classic example of something that
>> does not scale. The more and more updates there are, the higher the
>> load
>> becomes. You can see it on "top" as the footest program runs.
>>
>> There has to be a more linear way of handling this scenario.
>> <footest.c>
>>
>> ---------------------------(end of
>> broadcast)---------------------------
>> TIP 6: explain analyze is your friend
>

On 6/23/2006 3:10 PM, Mark Woodward wrote:

> This is NOT an "in-place" update. The whole MVCC strategy of keeping old
> versions around doesn't change. The only thing that does change is one
> level of indirection. Rather than keep references to all versions of all
> rows in indexes, keep only a reference to the first or "key" row of each
> row, and have the first version of a row form the head of a linked list to
> subsequent versions of each row. The list will be in decending order.

Where exactly do you intend to keep all those links (for a table with N
indexes)?

Jan

--
#======================================================================#
# It's easier to get forgiveness for being wrong than for being right. #
# Let's break this rule - forgive me. #
#================================================== JanWieck(at)Yahoo(dot)com #

On 6/23/2006 9:56 PM, mark(at)mark(dot)mielke(dot)cc wrote:

> On Fri, Jun 23, 2006 at 03:08:34PM -0400, Bruce Momjian wrote:
>> Tom Lane wrote:
>> > ...
>> > suggesting. We're having a hard enough time debugging and optimizing
>> > *one* storage model. I think the correct path forward is to stick with
>> > the same basic storage model and vacuuming concept, and address the
>> > known performance issues with better-optimized vacuuming. No, it will
>> > never be perfect for every scenario, but we can certainly make it much
>> > better than it is now, without risking killing the project by
>> > introducing undebuggable, unmaintainable complexity.
>> Well, are you suggesting we just stop improving the database? I am sure
>> not. But, your suggestion is that we can't do better without incurring
>> more complexity (true), and that complexity will not be worth it. I
>> don't agree with that until I see some proposals, and shutting down
>> discussion because they will add complexity or are fruitless seems
>> unwise.
>
> It sounds like everybody agrees that things need to be fixed, and genuinely
> motivated people are trying to offer what they have to the table.

One singe core team member responds vaguely in a way, you feel being
supportive of your case, and you conclude that "everybody agrees"?
Sorry, x'use me?

There are a couple of side effects on this "update in place" issue that
aren't even mentioned yet. Nobody with any significant in depth
knowledge of the Postgres non-overwriting storage engine concept seems
to suggest any move towards a storage system, that does updates in place
that require "undo" operations in case of a process/system failure.
You're ready to "fix" all those places to support the undo you need? You
must have a big table.

Jan

>
> Tom already has enough on his plate, as do most others here - so unless
> a competent champion can take up the challenge, discussion is all we have.
>
> I'm not liking the "we should do it this way," "no, we should do it that."
> My read of the situation is that both may be useful, and that both should
> be pursued. But one set of people can't pursue both.
>
> Is any who is able, able to take up this challenge? Perhaps more than one,
> from both major directions? (vacuum on one side, and improved storage on
> the other) Somebody with the time and skill, who can work through the
> design discussions on one of the aspects?
>
> I want to contribute soon, and this is the sort of thing that interests me -
> but I still don't have time yet, and there would be no guarantee that I
> succeeded. Somebody else? :-)
>
> Cheers,
> mark
>

--
#======================================================================#
# It's easier to get forgiveness for being wrong than for being right. #
# Let's break this rule - forgive me. #
#================================================== JanWieck(at)Yahoo(dot)com #

On Sat, Jun 24, 2006 at 03:29:47AM -0400, Jan Wieck wrote:
> >It sounds like everybody agrees that things need to be fixed, and genuinely
> >motivated people are trying to offer what they have to the table.
> One singe core team member responds vaguely in a way, you feel being
> supportive of your case, and you conclude that "everybody agrees"?
> Sorry, x'use me?

> There are a couple of side effects on this "update in place" issue that
> aren't even mentioned yet. Nobody with any significant in depth
> knowledge of the Postgres non-overwriting storage engine concept seems
> to suggest any move towards a storage system, that does updates in place
> that require "undo" operations in case of a process/system failure.
> You're ready to "fix" all those places to support the undo you need? You
> must have a big table.

Jan: Who on the list has claimed that nothing is broken and nothing needs
to be improved? Are you making this claim?

Shutting down ideas is not constructive. Encouraging those with ideas to
step up and do more than talk could be.

Cheers,
mark

--
mark(at)mielke(dot)cc / markm(at)ncf(dot)ca / markm(at)nortel(dot)com __________________________
. . _ ._ . . .__ . . ._. .__ . . . .__ | Neighbourhood Coder
|\/| |_| |_| |/ |_ |\/| | |_ | |/ |_ |
| | | | | \ | \ |__ . | | .|. |__ |__ | \ |__ | Ottawa, Ontario, Canada

One ring to rule them all, one ring to find them, one ring to bring them all
and in the darkness bind them...

http://mark.mielke.cc/

On Fri, 23 Jun 2006, Jonah H. Harris wrote:

> On 6/23/06, Mark Woodward <pgsql(at)mohawksoft(dot)com> wrote:
>> Rather than keep references to all versions of all
>> rows in indexes, keep only a reference to the first or "key" row of each
>> row, and have the first version of a row form the head of a linked list to
>> subsequent versions of each row. The list will be in decending order.
>
> By all means, please go ahead and try it because it's not quite that
> easy. You're going to run into serious locking and contention issues
> this way. In the end, it's not much better than running a sequential
> scan to query a row that's been updated several thousand times on a
> table that hasn't been vacuumed... follow that pointer :)

Can you elaborate what kind of locking and contention issues you're
thinking of?

You could update the index tuple to point to a newer version of the row,
when an index scan determines that the heap tuple it points to is not
visible to anyone. We already check that to update the XMAX_COMMITTED hint
bit. Updating the index tuple comes with a cost, of course, but
alleviates the "follow that pointer" issue.

The biggest challenge that I see is that an index scan would somehow
need to know when to follow the t_ctid chain and when not. If you follow
the pointer and there's another index tuple for the row, the scan could
see the same tuple twice. Some kind of bookkeeping would be needed to
solve that.

Also, vacuuming would become a bit more complex, since it would need to
update the index tuples to point to newer row versions instead of just
removing them.

All in all, I think this solution to the "an update needs to update all
indexes, even when none of the indexed columns changed" issue requires
less changes than implementing Oracle style rollback segments and/or an
undo log.

- Heikki

> On 6/23/2006 3:10 PM, Mark Woodward wrote:
>
>> This is NOT an "in-place" update. The whole MVCC strategy of keeping old
>> versions around doesn't change. The only thing that does change is one
>> level of indirection. Rather than keep references to all versions of all
>> rows in indexes, keep only a reference to the first or "key" row of each
>> row, and have the first version of a row form the head of a linked list
>> to
>> subsequent versions of each row. The list will be in decending order.
>
> Where exactly do you intend to keep all those links (for a table with N
> indexes)?
>

I'm probably mistaken, but aren't there already forward references in
tuples to later versions? If so, I'm only sugesting reversing the order
and referencing the latest version.

On Sat, Jun 24, 2006 at 08:14:10AM -0400, Mark Woodward wrote:
> > On 6/23/2006 3:10 PM, Mark Woodward wrote:
> >
> >> This is NOT an "in-place" update. The whole MVCC strategy of keeping old
> >> versions around doesn't change. The only thing that does change is one
> >> level of indirection. Rather than keep references to all versions of all
> >> rows in indexes, keep only a reference to the first or "key" row of each
> >> row, and have the first version of a row form the head of a linked list
> >> to
> >> subsequent versions of each row. The list will be in decending order.
> >
> > Where exactly do you intend to keep all those links (for a table with N
> > indexes)?
> >
>
> I'm probably mistaken, but aren't there already forward references in
> tuples to later versions? If so, I'm only sugesting reversing the order
> and referencing the latest version.

You can't do that. The links exist so that in READ COMMITTED mode you
can always find the newest version. You would need to add additional
links to go backwards.

Have a nice day,
--
Martijn van Oosterhout <kleptog(at)svana(dot)org> http://svana.org/kleptog/
> From each according to his ability. To each according to his ability to litigate.

On Fri, Jun 23, 2006 at 03:10:39PM -0400, Mark Woodward wrote:
> This is NOT an "in-place" update. The whole MVCC strategy of keeping old
> versions around doesn't change. The only thing that does change is one
> level of indirection. Rather than keep references to all versions of all
> rows in indexes, keep only a reference to the first or "key" row of each
> row, and have the first version of a row form the head of a linked list to
> subsequent versions of each row. The list will be in decending order.

I thought of another issue with this. If you move away from storing
each row in the indexes, you can pretty much forget bitmap index scans.
They pretty much rely on every row being represented, not just a
subset. Until you go to the heap you don't know if a tuple will match,
which is precisely what the bitmap scan is trying to avoid. You could
follow the links, but that destroys the nice sequential access
properties.

> In the vast majority of cases, the overhead of this action will be
> trivial. In an unmodified row, you're there. In a modified row, you have
> one extra lookup. In extream cases, you may have to go back a few
> versions, but I don't see that as a common behavior.

I wonder if looking at old versions is really all that uncommon. A
large reporting query which runs for hours will probably be looking at
a lot of old versions. These are the queries that will be hit the
hardest.

If you're trying to avoid index bloat, I wonder if it wouldn't be
better to tackle this from the other end. In indexes, allow a row to
carry multiple CTIDs. That way a new version only requires adding six
more bytes, rather than a whole new tuple.

Have a nice day,
--
Martijn van Oosterhout <kleptog(at)svana(dot)org> http://svana.org/kleptog/
> From each according to his ability. To each according to his ability to litigate.

On Sat, 24 Jun 2006, Mark Woodward wrote:

> I'm probably mistaken, but aren't there already forward references in
> tuples to later versions? If so, I'm only sugesting reversing the order
> and referencing the latest version.

I thought I understood your idea, but now you lost me again. I thought
what you want is that the older heap tuple has a pointer to the
newer one. Which it already has, it's called t_ctid.

Can you try to explain more carefully how the whole thing would work?
What would an index tuple point to? What pointers would a heap tuple
have? What would an index scan do to find the row version it's interested
in? What exactly would an update do?

- Heikki

On 6/24/06, Mark Woodward <pgsql(at)mohawksoft(dot)com> wrote:
> Currently it looks like this:
>
> ver001->ver002->ver003->...-verN
>
> That's what t_ctid does now, right? Well, that's sort of stupid. Why not
> have it do this:
>
> ver001->verN->...->ver003->ver002->|

Heh, because that's crazy. The first time you insert a key into the
index it will point to v1 of a tuple... say after 5 updates you have
v2,v3,v4,v5... your c_tid pointer chain looks like v1
(original)->v2->v3->v4-v5 (newest). However, your whole idea is based
on not having to do another index insert for unchanged keys, so the
index still points to v1... which means you have to follow the c_tid
chain to get to the newest version just like a sequential scan. I
don't see how you think you can reverse pointer it.

> This will speed up almost *all* queries when there are more than two
> version of rows.

Nope.

> When you vacuum, simply make the latest version (verN) the key row (ver001).

How are you going to do this without a ton of locking... remember, the
index is pointing to v1 with a tid... so you'll have to physically
move the newest version v5 to v1's tid from wherever it was... like a
vacuum full on steroids. Unless of course, you rebuild the index...
but that's not a solution either.

--
Jonah H. Harris, Software Architect | phone: 732.331.1300
EnterpriseDB Corporation | fax: 732.331.1301
33 Wood Ave S, 2nd Floor | jharris(at)enterprisedb(dot)com
Iselin, New Jersey 08830 | http://www.enterprisedb.com/

On 6/24/06, Jonah H. Harris <jonah(dot)harris(at)gmail(dot)com> wrote:

Grr... need coffee... s/c_tid/ctid/g

--
Jonah H. Harris, Software Architect | phone: 732.331.1300
EnterpriseDB Corporation | fax: 732.331.1301
33 Wood Ave S, 2nd Floor | jharris(at)enterprisedb(dot)com
Iselin, New Jersey 08830 | http://www.enterprisedb.com/

> On Sat, 24 Jun 2006, Mark Woodward wrote:
>
>> I'm probably mistaken, but aren't there already forward references in
>> tuples to later versions? If so, I'm only sugesting reversing the order
>> and referencing the latest version.
>
> I thought I understood your idea, but now you lost me again. I thought
> what you want is that the older heap tuple has a pointer to the
> newer one. Which it already has, it's called t_ctid.

Perfect!
>
> Can you try to explain more carefully how the whole thing would work?
> What would an index tuple point to? What pointers would a heap tuple
> have? What would an index scan do to find the row version it's interested
> in? What exactly would an update do?

Since we already allocate space for some notion of linked list, then all
I'm suggesting is we reverse the order, sort of. Currently it looks like
this: