Re: HOT latest patch - version 8

Hi All,

Please see version 8 of the HOT patch attached with the mail.
In the last couple of weeks, few people like Heikki, Simon, Greg,
Korry have reviewed the patch. I should especially thank Heikki
for his thorough review.

In the process we have fixed quite a few bugs and improved
few things. The attached patch is based on those changes.

I now need to again split the patch into smaller patches for
ease of review. There were some additional suggestions regarding
refactoring which I would do now. But if anybody wants to just
test the patch, please use this version.

I would summarize the changes when I split and send the smaller
patches.

Thanks,
Pavan

--
Pavan Deolasee
EnterpriseDB http://www.enterprisedb.com

Please see updated version of the patch. This includes further code
refactoring and bug fixes.

heapam code is now refactored and I have also added several comments
in that code as well as vacuum and create index related code.

In the previous version, we were not collecting aborted heap-only
tuples since they are not part of any chain. This version deals with
such tuples.

There is also some cleanup in the VACUUM FULL area. Especially
we have dealt with the redirected line pointers by pointing them to
the first non-dead tuple in the chain. Since we hold exclusive lock
on the relation, we can easily do that.

Anyways, we still need a comprehensive writeup, but if someone
wants to test things further, this patch should be used.

Thanks,
Pavan

On 6/27/07, Pavan Deolasee <pavan(dot)deolasee(at)gmail(dot)com> wrote:
>
>
> Hi All,
>
> Please see version 8 of the HOT patch attached with the mail.
> In the last couple of weeks, few people like Heikki, Simon, Greg,
> Korry have reviewed the patch. I should especially thank Heikki
> for his thorough review.
>
> In the process we have fixed quite a few bugs and improved
> few things. The attached patch is based on those changes.
>
> I now need to again split the patch into smaller patches for
> ease of review. There were some additional suggestions regarding
> refactoring which I would do now. But if anybody wants to just
> test the patch, please use this version.
>
> I would summarize the changes when I split and send the smaller
> patches.
>
> Thanks,
> Pavan
>
> --
> Pavan Deolasee
> EnterpriseDB http://www.enterprisedb.com
>

--
Pavan Deolasee
EnterpriseDB http://www.enterprisedb.com

Pavan Deolasee wrote:
> Please see updated version of the patch. This includes further code
> refactoring and bug fixes.

Thanks for the update, Pavan!

I've been looking at this patch in the last couple of weeks in detail. I
wrote a short summary of how it works (attached) to help reviewing it.
Especially the glossary is helpful, since the patch introduces a lot of
new concepts.

I have some suggestions which I'll post separately, this just describes
the status quo of the patch.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

Heikki Linnakangas wrote:
> I have some suggestions which I'll post separately,

A significant chunk of the complexity and new code in the patch comes
from pruning hot chains and reusing the space for new updates. Because
we can't reclaim dead space in the page like a VACUUM does, without
holding the vacuum lock, we have to deal with pages that contain deleted
tuples, and be able to reuse them, and keep track of the changes in
tuple length etc.

A much simpler approach would be to try to acquire the vacuum lock, and
compact the page the usual way, and fall back to a cold update if we
can't get the lock immediately.

The obvious downside of that is that if a page is continuously pinned,
we can't HOT update tuples on it. Keeping in mind that the primary use
case for HOT is largeish tables, small tables are handled pretty well by
autovacuum, chances are pretty good that you can get a vacuum lock when
you need it.

Thoughts?

I'm looking for ways to make the patch simpler and less invasive. We may
want to put back some of this stuff, or come up with a more clever
solution, in future releases, but right let's keep it simple.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

Heikki Linnakangas <heikki(at)enterprisedb(dot)com> writes:
> A much simpler approach would be to try to acquire the vacuum lock, and
> compact the page the usual way, and fall back to a cold update if we
> can't get the lock immediately.

Seems like that could work.

> I'm looking for ways to make the patch simpler and less invasive.

+1 on that, for sure.

regards, tom lane

Tom Lane wrote:
> Heikki Linnakangas <heikki(at)enterprisedb(dot)com> writes:
>> A much simpler approach would be to try to acquire the vacuum lock, and
>> compact the page the usual way, and fall back to a cold update if we
>> can't get the lock immediately.
>
> Seems like that could work.

I just realized that there's a big problem with that. The process doing
the update surely holds a pin on the buffer itself. Needs more thought..

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

Heikki Linnakangas <heikki(at)enterprisedb(dot)com> writes:
> Tom Lane wrote:
>> Heikki Linnakangas <heikki(at)enterprisedb(dot)com> writes:
>>> A much simpler approach would be to try to acquire the vacuum lock, and
>>> compact the page the usual way, and fall back to a cold update if we
>>> can't get the lock immediately.
>>
>> Seems like that could work.

> I just realized that there's a big problem with that. The process doing
> the update surely holds a pin on the buffer itself. Needs more thought..

So does VACUUM when it's trying to lock a page, no? In any case we
could surely make an extra parameter to LockBufferForCleanup if it
really needs to distinguish the cases.

regards, tom lane

Tom Lane wrote:
> Heikki Linnakangas <heikki(at)enterprisedb(dot)com> writes:
>> Tom Lane wrote:
>>> Heikki Linnakangas <heikki(at)enterprisedb(dot)com> writes:
>>>> A much simpler approach would be to try to acquire the vacuum lock, and
>>>> compact the page the usual way, and fall back to a cold update if we
>>>> can't get the lock immediately.
>>> Seems like that could work.
>
>> I just realized that there's a big problem with that. The process doing
>> the update surely holds a pin on the buffer itself. Needs more thought..
>
> So does VACUUM when it's trying to lock a page, no? In any case we
> could surely make an extra parameter to LockBufferForCleanup if it
> really needs to distinguish the cases.

The problem is that if we trigger the page cleanup from heap_update, as
I was planning to do, the executor has already pinned the page and holds
a reference to the old tuple on the page. We can't shuffle the data on
the page, because the pointer to the old tuple would become invalid.

We could do still it from somewhere else, though. For example, in
heap_fetch, the first time a page is touched. Or in bgwriter.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

Heikki,

Thanks for providing this summary. As someone unfamiliar with the
domain (both HOT development specifically and tuple management in
general), I found it easy to follow.

On Jul 13, 2007, at 8:31 , Heikki Linnakangas wrote:

> Pruning
> -------

> To reclaim the index-visible (i.e. first) tuple in a HOT chain, the
> line pointer is turned into a redirecting line pointer that points
> to the line pointer of the next tuple in the chain. To keep track
> of the space occupied by the dead tuple, so that we can reuse the
> space, a new line pointer is allocated and marked with LP_DELETE to
> point to the dead tuple. That means its tid changes, but that's ok
> since it's dead.

> Row-level fragmentation
> -----------------------

> If there's no LP_DELETEd tuples large enough to fit the new tuple
> in, the row-level fragmentation is repaired in the hope that some
> of the slots were actually big enough, but were just fragmented.
> That's done by mapping the offsets in the page, and enlarging all
> LP_DELETEd line pointers up to the beginning of the next tuple.

Would it make sense to enlarge the LP_DELETEd line pointers up to the
beginning of the next tuple at the time the tuple is marked LP_DELETE?

> Vacuum
> ------
> Vacuum prunes all HOT chains, and removes any LP_DELETEd tuples,
> making the space available for any use.

In the case of a fragmented row, am I right to assume vacuum reclaims
all space up to the next (live) tuple?

Michael Glaesemann
grzm seespotcode net

Michael Glaesemann wrote:
> On Jul 13, 2007, at 8:31 , Heikki Linnakangas wrote:
>> Row-level fragmentation
>> -----------------------
>
>> If there's no LP_DELETEd tuples large enough to fit the new tuple in,
>> the row-level fragmentation is repaired in the hope that some of the
>> slots were actually big enough, but were just fragmented. That's done
>> by mapping the offsets in the page, and enlarging all LP_DELETEd line
>> pointers up to the beginning of the next tuple.
>
> Would it make sense to enlarge the LP_DELETEd line pointers up to the
> beginning of the next tuple at the time the tuple is marked LP_DELETE?

The thing is, it's relatively expensive to figure out where the next
tuple starts. We need to scan all line pointers to do that. Though given
that pruning all tuples on a page is a relatively expensive operation
anyway, maybe it wouldn't be so bad.

>> Vacuum
>> ------
>> Vacuum prunes all HOT chains, and removes any LP_DELETEd tuples,
>> making the space available for any use.
>
> In the case of a fragmented row, am I right to assume vacuum reclaims
> all space up to the next (live) tuple?

Yes, Vacuum will 'defrag' the page.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

Pavan Deolasee wrote:
>
> Please see updated version of the patch. This includes further code
> refactoring and bug fixes.
>
> heapam code is now refactored and I have also added several comments
> in that code as well as vacuum and create index related code.
>
> In the previous version, we were not collecting aborted heap-only
> tuples since they are not part of any chain. This version deals with
> such tuples.
>
> There is also some cleanup in the VACUUM FULL area. Especially
> we have dealt with the redirected line pointers by pointing them to
> the first non-dead tuple in the chain. Since we hold exclusive lock
> on the relation, we can easily do that.
>
> Anyways, we still need a comprehensive writeup, but if someone
> wants to test things further, this patch should be used.

tried to test a bit on my Solaris 10 install(sun studio , 64bit build)
but I'm hitting the following while trying to initdb a new cluster:

program terminated by signal SEGV (no mapping at the fault address)
Current function is PageGetRedirectingOffset
1186 offsets[ItemIdGetRedirect(lp) - 1] = offnum;
(dbx) where
=>[1] PageGetRedirectingOffset(page = 0xfffffd7ffdf2bea0 "", offsets =
0xfffffd7fffdfd2fc, size = 582), line 1186 in "bufpage.c"
[2] lazy_scan_heap(onerel = 0xc7fcd8, vacrelstats = 0xcb9940, Irel =
0xcd0008, nindexes = 2), line 434 in "vacuumlazy.c"
[3] lazy_vacuum_rel(onerel = 0xc7fcd8, vacstmt = 0xc34e70, bstrategy =
0xcb76d8), line 187 in "vacuumlazy.c"
[4] vacuum_rel(relid = 2608U, vacstmt = 0xc34e70, expected_relkind =
'r'), line 1109 in "vacuum.c"
[5] vacuum(vacstmt = 0xc34e70, relids = (nil), bstrategy = 0xcb76d8,
isTopLevel = '\001'), line 424 in "vacuum.c"
[6] ProcessUtility(parsetree = 0xc34e70, queryString = 0xbcd978
"VACUUM pg_depend;\n", params = (nil), isTopLevel = '\001', dest =
0xb0f440, completionTag = 0xfffffd7fffdff5d0 ""), line 997 in "utility.c"
[7] PortalRunUtility(portal = 0xcc5328, utilityStmt = 0xc34e70,
isTopLevel = '\001', dest = 0xb0f440, completionTag = 0xfffffd7fffdff5d0
""), line 1179 in "pquery.c"
[8] PortalRunMulti(portal = 0xcc5328, isTopLevel = '\001', dest =
0xb0f440, altdest = 0xb0f440, completionTag = 0xfffffd7fffdff5d0 ""),
line 1267 in "pquery.c"
[9] PortalRun(portal = 0xcc5328, count = 9223372036854775807,
isTopLevel = '\001', dest = 0xb0f440, altdest = 0xb0f440, completionTag
= 0xfffffd7fffdff5d0 ""), line 814 in "pquery.c"
[10] exec_simple_query(query_string = 0xc34c08 "VACUUM pg_depend;\n"),
line 967 in "postgres.c"
[11] PostgresMain(argc = 8, argv = 0xb94c68, username = 0xb8dd10
"pgbuild"), line 3527 in "postgres.c"
[12] main(argc = 9, argv = 0xb94c60), line 186 in "main.c"

Stefan

Stefan Kaltenbrunner wrote:
> tried to test a bit on my Solaris 10 install(sun studio , 64bit build)
> but I'm hitting the following while trying to initdb a new cluster:

I can't reproduce this error, but I found a bug that's likely causing
it. The patch uses InvalidOffsetNumber in lp_off to mark so called
"redirect dead" line pointers, but that special case is not checked in
PageGetRedirectingOffset-function, writing to a caller-supplied array
with -1 index instead, globbering over whatever is there. Actually
storing InvalidOffsetNumber in lp_off is a bit bogus in the first place
since lp_off is unsigned, and InvalidOffsetNumber is -1, so I fixed that
as well.

Patch attached.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

Heikki Linnakangas wrote:
> Stefan Kaltenbrunner wrote:
>> tried to test a bit on my Solaris 10 install(sun studio , 64bit build)
>> but I'm hitting the following while trying to initdb a new cluster:
>
> I can't reproduce this error, but I found a bug that's likely causing
> it. The patch uses InvalidOffsetNumber in lp_off to mark so called
> "redirect dead" line pointers, but that special case is not checked in
> PageGetRedirectingOffset-function, writing to a caller-supplied array
> with -1 index instead, globbering over whatever is there. Actually
> storing InvalidOffsetNumber in lp_off is a bit bogus in the first place
> since lp_off is unsigned, and InvalidOffsetNumber is -1, so I fixed that
> as well.

this seems to fix the problem for me - a least I can now successfully
initdb a new cluster with the HOT patch applied.

Stefan

On Fri, 2007-07-13 at 16:22 +0100, Heikki Linnakangas wrote:
> Heikki Linnakangas wrote:
> > I have some suggestions which I'll post separately,

> I'm looking for ways to make the patch simpler and less invasive. We may
> want to put back some of this stuff, or come up with a more clever
> solution, in future releases, but right let's keep it simple.

I believe we're all trying to do that, but I would like to see some
analysis of which techniques are truly effective and which are not.
Simpler code may not have desirable behaviour and then the whole lot of
code is pointless. Let's make it effective by making it complex enough.
I'm not clear where the optimum lies. (c.f. Flying Buttresses).

> A significant chunk of the complexity and new code in the patch comes
> from pruning hot chains and reusing the space for new updates. Because
> we can't reclaim dead space in the page like a VACUUM does, without
> holding the vacuum lock, we have to deal with pages that contain deleted
> tuples, and be able to reuse them, and keep track of the changes in
> tuple length etc.
>
> A much simpler approach would be to try to acquire the vacuum lock, and
> compact the page the usual way, and fall back to a cold update if we
> can't get the lock immediately.
>
> The obvious downside of that is that if a page is continuously pinned,
> we can't HOT update tuples on it. Keeping in mind that the primary use
> case for HOT is largeish tables, small tables are handled pretty well by
> autovacuum, chances are pretty good that you can get a vacuum lock when
> you need it.

The main problem HOT seeks to avoid is wasted inserts into indexes, and
the subsequent VACUUMing that requires. Small tables have smaller
indexes, so that the VACUUMing is less of a problem. If we have hot
spots in larger tables, DSM would allow us to avoid the I/O on the main
table, but we would still need to scan the indexes. So HOT *can* be
better than DSM. I'm worried that requiring the vacuum lock in all cases
will mean that HOT will be ineffective where it is needed most - in the
hot spots - i.e. the blocks that contain frequently updated rows. [As an
aside, in OLTP it is frequently the index blocks that become hot spots,
so reducing index inserts because of UPDATEs will also reduce block
contention]

Our main test case for OLTP is DBT-2 which follows TPC-C in being
perfectly scalable with no hot spots in the heap and limited hot spots
in the indexes. As such it's a poor test of real world applications,
where Benfold's Law holds true. Requiring the vacuum lock in all cases
would allow good benchmark performance but would probably fail in the
real world at providing good long term performance.

I'm interested in some numbers that show which we need. I'm thinking of
some pg_stats output that shows how many vac locks were taken and how
many prunes were made. Something general that allows some beta testers
to provide feedback on the efficacy of the patch.

That leads to the suggestion that we should make the HOT pruning logic
into an add-on patch, commit it, but evaluate its performance during
beta. If we have no clear evidence of additional benefit, we remove it
again.

I'm not in favour of background retail vacuuming by the bgwriter. The
timeliness of that is (similarly) in question and I think bgwriter has
enough work to do already.

[Just as a note to all performance testers: HOT is designed to show
long-term steady performance. Short performance tests frequently show no
benefit if sufficient RAM is available to avoid the table bloat and we
avoid hitting the point where autovacuums kick in. I know Heikki knows
this, just not sure we actually said it.]

--
Simon Riggs
EnterpriseDB http://www.enterprisedb.com

On Sun, 15 Jul 2007, Simon Riggs wrote:

> Our main test case for OLTP is DBT-2 which follows TPC-C in being
> perfectly scalable with no hot spots in the heap and limited hot spots
> in the indexes. As such it's a poor test of real world applications,
> where Benfold's Law holds true.

I assume this is a typo on Benford's Law:
http://en.wikipedia.org/wiki/Benford's_law which notes there are far more
ones in real-world data sets.

If there were a Benfold's Law, it would surely involve the number 5
instead.

--
* Greg Smith gsmith(at)gregsmith(dot)com http://www.gregsmith.com Baltimore, MD

> I'm looking for ways to make the patch simpler and less invasive.

Any objections to changing the name of "RedirectDead"? A RedirectDead
ItemId is not really redirected, it's just a stub representing a dead
tuple (the space for that tuple has been reused but an index entry may
still point to the ItemId).

How about "stub" or "tombstone"?

-- Korry

--
Korry Douglas korryd(at)enterprisedb(dot)com
EnterpriseDB http://www.enterprisedb.com

korryd(at)enterprisedb(dot)com wrote:
> Any objections to changing the name of "RedirectDead"? A RedirectDead
> ItemId is not really redirected, it's just a stub representing a dead
> tuple (the space for that tuple has been reused but an index entry may
> still point to the ItemId).
>
> How about "stub" or "tombstone"?

Sounds good to me. "Stub" is a bit generic, I'd go for "tombstone".

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

On 7/15/07, Heikki Linnakangas <heikki(at)enterprisedb(dot)com> wrote:
>
>
> Actually
> storing InvalidOffsetNumber in lp_off is a bit bogus in the first place
> since lp_off is unsigned, and InvalidOffsetNumber is -1, so I fixed that
> as well.
>
>

I see InvalidOffsetNumber as 0 in off.h:26

#define InvalidOffsetNumber ((OffsetNumber) 0)

So I think we should be OK to use that to indicate redirect-dead
pointers.

Thanks,
Pavan

--
Pavan Deolasee
EnterpriseDB http://www.enterprisedb.com

"Heikki Linnakangas" <heikki(at)enterprisedb(dot)com> writes:

> CREATE INDEX
> CREATE INDEX CONCURRENTLY
> -------------------------
> I'm not very familiar with how these, so I'll just shut up..

Here is an addendum for how HOT handles CREATE INDEX and CREATE INDEX
CONCURRENTLY.