Re: HOT patch - version 14

Hi All,

Please see the version 14 of HOT patch attached. I have also
attached a differential patch from the last version posted. This
now includes support for partial and expression indexes. As per
the discussion, we collect all the index columns appearing in
the partial index predicates and/or expression index expressions.
If any of these columns are being updated, the update does not
qualify for HOT update.

I also took this opportunity to remove the modularity invasion caused
by heap_check_idxupdate() since it was using resultRelInfo. We now
build the list of attributes that must be checked to satisfy HOT update.
This list includes all the index columns, columns in the partial index
predicates and expression index expressions and is built in the
executor.

heap_check_idxupdate() is renamed to HeapSatisfiesHOTUpdate()

The patch also includes a bug fix in the CREATE INDEX code path.
There was a race between CREATE INDEX and concurrent chain pruning
operation. Since CREATE INDEX works on SnapshotAny, a tuple returned
by heap-scan may get pruned (and marked ~LP_USED) before it can
be inspected later. So we must check for LP_USED after reaquiring
the buffer lock.

Thanks,
Pavan

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

Pavan Deolasee wrote:
> Please see the version 14 of HOT patch attached. I have also
> attached a differential patch from the last version posted. This
> now includes support for partial and expression indexes. As per
> the discussion, we collect all the index columns appearing in
> the partial index predicates and/or expression index expressions.
> If any of these columns are being updated, the update does not
> qualify for HOT update.

I see that you have a separate bitmapset to keep track of indexes on
system attributes. But having an index on a system attribute doesn't
make any sense, does it?

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

Heikki Linnakangas <heikki(at)enterprisedb(dot)com> writes:
> I see that you have a separate bitmapset to keep track of indexes on
> system attributes. But having an index on a system attribute doesn't
> make any sense, does it?

Counterexample: OID.

regards, tom lane

On 8/20/07, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>
> Heikki Linnakangas <heikki(at)enterprisedb(dot)com> writes:
> > I see that you have a separate bitmapset to keep track of indexes on
> > system attributes. But having an index on a system attribute doesn't
> > make any sense, does it?
>
> Counterexample: OID.
>
>
>
Right. Further, we allow creating indexes on system attributes. So we
must support those.

Thanks,
Pavan

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

"Pavan Deolasee" <pavan(dot)deolasee(at)gmail(dot)com> writes:
> Please see the version 14 of HOT patch attached.

I expected to find either a large new README, or some pretty substantial
additions to existing README files, to document how this all works.
The comments included do not represent nearly enough documentation.

One thing I was unable to discern from the comments is how CREATE INDEX
can work at all. A new index might mean that tuples that could formerly
legally be part of the same hot-chain no longer can. I can't find any
code here that looks like it's addressing that. I also don't think I
believe the reasoning for not indexing DELETE_IN_PROGRESS hot-updated
tuples: what if the index completion commits, but the concurrent delete
rolls back? Then you've got a valid tuple that's not in the index.

> I also took this opportunity to remove the modularity invasion caused
> by heap_check_idxupdate() since it was using resultRelInfo. We now
> build the list of attributes that must be checked to satisfy HOT update.
> This list includes all the index columns, columns in the partial index
> predicates and expression index expressions and is built in the
> executor.

The executor is the wrong place for that: I'm not sure why you think
that making heapam depend on the executor is a modularity improvement.
Furthermore this approach requires recalculating the list during
each query, which is wasteful when it could only change during schema
updates. I'd suggest making the relcache responsible for computing and
saving this data, along the same lines as RelationGetIndexList().
(That also means that heapam can get the data from the relcache, saving
a lot of API-bloating from passing around Attrids explicitly.)
Also, rather than inventing Attrids, I'd suggest just using one
Bitmapset with the convention that its contents are offset by
FirstLowInvalidHeapAttributeNumber.

The redefinition of the value of MaxHeapTuplesPerPage seems pretty
ugly and unprincipled. I think it'd be better to leave it as-is,
and just enforce that we don't allow more than that many line pointers
on a heap page (as indeed you have to do anyway, so it's not clear
what the change is buying).

Is it really necessary to add hot_update to xl_heap_update? Seems the
information should be available from the tuple header fields.

Have you demonstrated that the "prune_hard" logic is worth its weight?
Considering that many of us want to drop VACUUM FULL, adding more
complexity to it doesn't seem like a profitable use of time.

Is it really safe, or productive, to run heap_page_prune when the buffer
is not locked for cleanup (ie, there are other people with pins on it)?
Even if it's safe, ISTM what you're mostly accomplishing there is to
expend a lot of cycles while holding exclusive lock on the page, when
there is good reason to think that you're blocking other people who are
interested in using the page. Eliminating the separation between that
and cleanup would also allow eliminating the separate "PD_FRAGMENTED"
page state.

PlanSetValidForThisTransaction is completely bogus --- it's not
re-entrant, and it needs to be. I think you need some state in
PlannerGlobal instead.

rd_avgfsm seems fairly bogus ... when does it get updated?

regards, tom lane

On 8/30/07, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>
> "Pavan Deolasee" <pavan(dot)deolasee(at)gmail(dot)com> writes:
> > Please see the version 14 of HOT patch attached.
>
> I expected to find either a large new README, or some pretty substantial
> additions to existing README files, to document how this all works.
> The comments included do not represent nearly enough documentation.

I shall take that up. There are couple of documents posted by Heikki and
Greg,
apart from several email threads and original design doc by Simon. I shall
consolidate everything in a single README.

One thing I was unable to discern from the comments is how CREATE INDEX
> can work at all. A new index might mean that tuples that could formerly
> legally be part of the same hot-chain no longer can. I can't find any
> code here that looks like it's addressing that.

You are right - a new index might mean that an existing HOT chain
is broken as far as the new index is concerned. The way we address
that is by indexing the root tuple of the chain, but the index key is
extracted from the last tuple in the chain. The index is marked "unusable"
for all those existing transactions which can potentially see any
intermediate
tuples in the chain.

Please see this document written by Greg Stark. He has nicely summarized
how CREATE INDEX and CREATE INDEX CONCURRENTLY works with HOT.

http://archives.postgresql.org/pgsql-patches/2007-07/msg00360.php

I also don't think I
> believe the reasoning for not indexing DELETE_IN_PROGRESS hot-updated
> tuples: what if the index completion commits, but the concurrent delete
> rolls back? Then you've got a valid tuple that's not in the index.

Since CREATE INDEX works with ShareLock on the relation, we can
safely assume that we can't find any DELETE_IN_PROGRESS tuples except
those deleted by our own transaction. The only exception is system relation,
but we don't do HOT updates on system relation. Given that, it seems OK
to me to ignore these tuples because if the transaction aborts,
CREATE INDEX is aborted as well. Am I overlooking something here ?
There is a comment to this regard in the current code as well.

> I also took this opportunity to remove the modularity invasion caused
> > by heap_check_idxupdate() since it was using resultRelInfo. We now
> > build the list of attributes that must be checked to satisfy HOT update.
> > This list includes all the index columns, columns in the partial index
> > predicates and expression index expressions and is built in the
> > executor.
>
> The executor is the wrong place for that: I'm not sure why you think
> that making heapam depend on the executor is a modularity improvement.

Earlier (in the previous version of HOT patch) we were passing ResultRelInfo
to heap_update, which was more ugly. The comment is in that context :-)

Furthermore this approach requires recalculating the list during
> each query, which is wasteful when it could only change during schema
> updates. I'd suggest making the relcache responsible for computing and
> saving this data, along the same lines as RelationGetIndexList().
> (That also means that heapam can get the data from the relcache, saving
> a lot of API-bloating from passing around Attrids explicitly.)
> Also, rather than inventing Attrids, I'd suggest just using one
> Bitmapset with the convention that its contents are offset by
> FirstLowInvalidHeapAttributeNumber.

I liked all these suggestions. I know I thought about computing
the attribute list in relcache, but probably avoided to keep things simple.
I shall make these changes.

The redefinition of the value of MaxHeapTuplesPerPage seems pretty
> ugly and unprincipled. I think it'd be better to leave it as-is,
> and just enforce that we don't allow more than that many line pointers
> on a heap page (as indeed you have to do anyway, so it's not clear
> what the change is buying).

The only reason to redefine MaxHeapTuplesPerPage to higher side is
because HOT allows us to accommodate more tuples per page because
of redirect-dead line pointers. For a table with sufficiently large tuples,
the original bound would work well, but for very small tuples - we might
hit the line pointer limit even if there is free space available in the
page. Doubling the value is chosen as a balance between heap page
utilization, line pointer bloating and overhead for bitmap scans. But
I agree that the factor choice is rather arbitrary.

> Is it really necessary to add hot_update to xl_heap_update? Seems the
> information should be available from the tuple header fields.

I think its not necessary. The reason I did that way because the new block
might be backed up in the WAL record and hence we might have recorded
the new tuple infomasks. But we can surely handle that corner case. I shall
fix this.

Have you demonstrated that the "prune_hard" logic is worth its weight?
> Considering that many of us want to drop VACUUM FULL, adding more
> complexity to it doesn't seem like a profitable use of time.

The prune_hard code is lot more simple in this version (it was horrible
before Heikki and I reworked the pruning logic). We just follow the HOT
chain to the last definitely DEAD tuple and remove all tuples preceding
that. This simplifies the second phase of VACUUM FULL since
we don't need to handle any broken HOT chains because of intermediate
DEAD tuples. Also, prune_hard allows us to cleanup the redirected
line pointers.

Another reason for doing this is to avoid any significant changes to
VACUUM FULL code since the code itself is complex and we might
just drop this in future. But until that time, we need to make sure that
HOT works fine with VACUUM FULL.

Is it really safe, or productive, to run heap_page_prune when the buffer
> is not locked for cleanup (ie, there are other people with pins on it)?

It looks safe to me. We don't move tuples around during chain pruning.
We only fix the HOT chains by removing intermediate DEAD tuples.
Other places where we follow HOT chains, we do so while holding
at-least SHARE lock on the buffer. So there are no race conditions here.

A place where this bite me is that the heap-scan with SnapshotAny
may return a tuple which gets pruned (and marked ~LP_USED)
before the caller can see it. Fortunately there are only limited users
of SnapshotAny. We make sure that IndexBuildHeapScan confirms that
the ItemIdIsValid() after acquiring lock on the buffer. Cluster works with
exclusive lock on the relation and hence there is no concurrent pruning
possible.

Even if it's safe, ISTM what you're mostly accomplishing there is to
> expend a lot of cycles while holding exclusive lock on the page, when
> there is good reason to think that you're blocking other people who are
> interested in using the page. Eliminating the separation between that
> and cleanup would also allow eliminating the separate "PD_FRAGMENTED"
> page state.

The reason we did it that way because repairing fragmentation seems
much more costly that pruning. Please note that we prune a single
chain during index fetch. Its only for heap-scans (and VACUUM) that
we try to prune all chains in the page. So unless we are doing heap-scan,
I am not sure if we are spending too much time holding the exclusive
lock. I agree we don't have any specific numbers to prove that though.

Another reasoning behind separating these two steps is: pruning
requires exclusive lock whereas repairing fragmentation requires
cleanup lock. Also we want to prune the chains aggressively
because the visible tuple is most likely at the end of the chain. Longer
the chain, greater the cost to fetch the tuple.

PlanSetValidForThisTransaction is completely bogus --- it's not
> re-entrant, and it needs to be. I think you need some state in
> PlannerGlobal instead.

I was not happy with this - frankly I don't understand the planning code
much. Thanks for pointing me to the appropriate code. I shall try fix this,
unless you would like to do it yourself.

rd_avgfsm seems fairly bogus ... when does it get updated?

Yeah, its not the best solution. What I wanted to do is delay repairing
page fragmentation as far as possible. But I noticed that fsmrel->avgRequest
(rd_avgfsm is initialized to it) starts with a small value (I guess 256).
For a table with large tuples, we may not repair fragmentation at all, thus
causing unnecessary COLD updates.

rd_avgfsm is updated when the relcache is rebuilt. Since we don't
send out any relcache invalidation when fsmrel->avgRequest changes,
rd_avgfsm may never get updated in a session.

Should we just revert to checking if the free space is less than a certain
percentage of BLCKSZ and trigger defragmentation ? Or may be do a
combination of both ?

Thanks,
Pavan

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

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

> "Pavan Deolasee" <pavan(dot)deolasee(at)gmail(dot)com> writes:
>> Please see the version 14 of HOT patch attached.
>
> I expected to find either a large new README, or some pretty substantial
> additions to existing README files, to document how this all works.
> The comments included do not represent nearly enough documentation.

The Heikki and I posted a two-part README of sorts:

http://archives.postgresql.org/pgsql-patches/2007-07/msg00142.php
http://archives.postgresql.org/pgsql-patches/2007-07/msg00360.php

> One thing I was unable to discern from the comments is how CREATE INDEX
> can work at all. A new index might mean that tuples that could formerly
> legally be part of the same hot-chain no longer can. I can't find any
> code here that looks like it's addressing that.

This is one of the weirdest things in HOT and one of the hardest problems it
faced. The best solution proposed was to index the head of the HOT chain and
just ban older transactions which might be able to see the older versions fro
using the index.

That's the purpose of the indcreatexid column. It's set in
index_set_createxid() and checked in get_relation_info().

> I also don't think I believe the reasoning for not indexing
> DELETE_IN_PROGRESS hot-updated tuples: what if the index completion commits,
> but the concurrent delete rolls back? Then you've got a valid tuple that's
> not in the index.

You're talking about the concurrent index build case? Wouldn't the second pass
pick up that tuple? I have to look back at it to see for sure.

> The redefinition of the value of MaxHeapTuplesPerPage seems pretty
> ugly and unprincipled. I think it'd be better to leave it as-is,
> and just enforce that we don't allow more than that many line pointers
> on a heap page (as indeed you have to do anyway, so it's not clear
> what the change is buying).

Note that in a heavily updated table basically every tuple will have two line
pointers, the head which just redirects to another line pointer, and the line
pointer for the actual tuple. It's hard to get rid of the actual head line
pointer without declaring that the tid might sometimes not change after an
update.

Not sure what this translates to for MaxHeapTuplesPerPage though.

The rest I know less about and will leave to Pavan and Heikki (or anyone else
who was following those details more closely).

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com

"Gregory Stark" <stark(at)enterprisedb(dot)com> writes:

> "Tom Lane" <tgl(at)sss(dot)pgh(dot)pa(dot)us> writes:
>
>> "Pavan Deolasee" <pavan(dot)deolasee(at)gmail(dot)com> writes:
>>> Please see the version 14 of HOT patch attached.
>>
>> I expected to find either a large new README, or some pretty substantial
>> additions to existing README files, to document how this all works.
>> The comments included do not represent nearly enough documentation.
>
> The Heikki and I posted a two-part README of sorts:

Er, editing error there. Has a ring to it though.

> http://archives.postgresql.org/pgsql-patches/2007-07/msg00142.php
> http://archives.postgresql.org/pgsql-patches/2007-07/msg00360.php
...
>> I also don't think I believe the reasoning for not indexing
>> DELETE_IN_PROGRESS hot-updated tuples: what if the index completion commits,
>> but the concurrent delete rolls back? Then you've got a valid tuple that's
>> not in the index.
>
> You're talking about the concurrent index build case? Wouldn't the second pass
> pick up that tuple? I have to look back at it to see for sure.

Sorry, that's misguided. The concurrent index build uses snapshots now so it
can't see DELETE_IN_PROGRESS. And the non-concurrent index build has an lock
so it ought to be back to the way it was before I messed with it where there
was an assert against finding *_IN_PROGRESS (except as Pavan points out in the
same transaction).

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com

"Pavan Deolasee" <pavan(dot)deolasee(at)gmail(dot)com> writes:
> You are right - a new index might mean that an existing HOT chain
> is broken as far as the new index is concerned. The way we address
> that is by indexing the root tuple of the chain, but the index key is
> extracted from the last tuple in the chain. The index is marked "unusable"
> for all those existing transactions which can potentially see any
> intermediate tuples in the chain.

I don't think that works --- what if the last tuple in the chain isn't
committed good yet? If its inserter ultimately rolls back, you've
indexed the wrong value.

> Please see this document written by Greg Stark. He has nicely summarized
> how CREATE INDEX and CREATE INDEX CONCURRENTLY works with HOT.
> http://archives.postgresql.org/pgsql-patches/2007-07/msg00360.php

Isn't the extra machination for C.I.C. just useless complication?
What's the point of avoiding creation of new broken HOT chains when
you still have to deal with existing ones?

>> I also don't think I
>> believe the reasoning for not indexing DELETE_IN_PROGRESS hot-updated
>> tuples: what if the index completion commits, but the concurrent delete
>> rolls back? Then you've got a valid tuple that's not in the index.

> Since CREATE INDEX works with ShareLock on the relation, we can
> safely assume that we can't find any DELETE_IN_PROGRESS tuples except
> those deleted by our own transaction. The only exception is system relation,
> but we don't do HOT updates on system relation.

That chain of reasoning is way too shaky for me. Essentially what
you're saying is you'll promise not to corrupt non-system indexes.
Nor am I really thrilled about having to disable HOT for system
catalogs.

> The only reason to redefine MaxHeapTuplesPerPage to higher side is
> because HOT allows us to accommodate more tuples per page because
> of redirect-dead line pointers.

No, it doesn't allow more tuples per page. It might mean there can be
more line pointers than that on a page, but not more actual tuples.
The question is whether there is any real use in allowing more line
pointers than that --- the limit is already unrealistically high,
since it assumes no data content in any of the tuples. If there is a
rationale for it then you should invent a different constant
MaxLinePointersPerPage or some such, but I really think there's no
point.

> Doubling the value is chosen as a balance between heap page
> utilization, line pointer bloating and overhead for bitmap scans.

I'd say it allows a ridiculous amount of line pointer bloat.

>> Even if it's safe, ISTM what you're mostly accomplishing there is to
>> expend a lot of cycles while holding exclusive lock on the page, when
>> there is good reason to think that you're blocking other people who are
>> interested in using the page. Eliminating the separation between that
>> and cleanup would also allow eliminating the separate "PD_FRAGMENTED"
>> page state.

> The reason we did it that way because repairing fragmentation seems
> much more costly that pruning. Please note that we prune a single
> chain during index fetch. Its only for heap-scans (and VACUUM) that
> we try to prune all chains in the page. So unless we are doing heap-scan,
> I am not sure if we are spending too much time holding the exclusive
> lock. I agree we don't have any specific numbers to prove that though.

If you don't have numbers proving that this extra complication has a
benefit, I'd vote for simplifying it. The SnapshotAny case is going to
bite other people besides you in future.

> Another reasoning behind separating these two steps is: pruning
> requires exclusive lock whereas repairing fragmentation requires
> cleanup lock.

This is nonsense. Those are the same lock. If you have the former and
not the latter, it just means that you *know* there is contention for
the page. It seems to me that performing optional maintenance work in
such a situation is completely wrong.

regards, tom lane

On 8/30/07, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>
> "Pavan Deolasee" <pavan(dot)deolasee(at)gmail(dot)com> writes:
> > You are right - a new index might mean that an existing HOT chain
> > is broken as far as the new index is concerned. The way we address
> > that is by indexing the root tuple of the chain, but the index key is
> > extracted from the last tuple in the chain. The index is marked
> "unusable"
> > for all those existing transactions which can potentially see any
> > intermediate tuples in the chain.
>
> I don't think that works --- what if the last tuple in the chain isn't
> committed good yet? If its inserter ultimately rolls back, you've
> indexed the wrong value.

I am confused. How could we get ShareLock on the relation while
there is some open transaction which has inserted a tuple in the
table ? (Of course, I am not considering the system tables here)
If the transaction which inserted the last tuple in the chain is already
aborted, we are not indexing that tuple (even if that tuple is at the
end). We would rather index the last committed-good tuple in the
chain. Running the tuples with HeapTupleSatisfiesVacuum guarantees
that. Isn't it ?

> Please see this document written by Greg Stark. He has nicely summarized
> > how CREATE INDEX and CREATE INDEX CONCURRENTLY works with HOT.
> > http://archives.postgresql.org/pgsql-patches/2007-07/msg00360.php
>
> Isn't the extra machination for C.I.C. just useless complication?
> What's the point of avoiding creation of new broken HOT chains when
> you still have to deal with existing ones?

IMHO the extra step in C.I.C simplifies the index build. The
transaction-waits
takes care of the existing broken chains and the early catalog entry for
the index helps us avoid creating new broken chains. I am not against
doing it a different way, but this is the best solution we could come up
when we worked on CIC.

>> I also don't think I
> >> believe the reasoning for not indexing DELETE_IN_PROGRESS hot-updated
> >> tuples: what if the index completion commits, but the concurrent delete
> >> rolls back? Then you've got a valid tuple that's not in the index.
>
> > Since CREATE INDEX works with ShareLock on the relation, we can
> > safely assume that we can't find any DELETE_IN_PROGRESS tuples except
> > those deleted by our own transaction. The only exception is system
> relation,
> > but we don't do HOT updates on system relation.
>
> That chain of reasoning is way too shaky for me. Essentially what
> you're saying is you'll promise not to corrupt non-system indexes.
> Nor am I really thrilled about having to disable HOT for system
> catalogs.

I am not against supporting HOT for system catalogs. But IMHO
its not a strict requirements because system catalogs are small, less
frequently updated and HOT adds little value to them. If we don't have
a generic solution which works for system and non-system tables,
thats the best we can get. We can start with non-system
tables and expand its scope later.

> The only reason to redefine MaxHeapTuplesPerPage to higher side is
> > because HOT allows us to accommodate more tuples per page because
> > of redirect-dead line pointers.
>
> No, it doesn't allow more tuples per page. It might mean there can be
> more line pointers than that on a page, but not more actual tuples.
> The question is whether there is any real use in allowing more line
> pointers than that --- the limit is already unrealistically high,
> since it assumes no data content in any of the tuples. If there is a
> rationale for it then you should invent a different constant
> MaxLinePointersPerPage or some such, but I really think there's no
> point.

I agree. I think the current limit on MaxHeapTuplesPerPage is sufficiently
large. May be we can keep it the same and tune it later if we have numbers
to prove its worthiness.

> Doubling the value is chosen as a balance between heap page
> > utilization, line pointer bloating and overhead for bitmap scans.
>
> I'd say it allows a ridiculous amount of line pointer bloat.

OK. Lets keep MaxHeapTuplesPerPage unchanged.

>> Even if it's safe, ISTM what you're mostly accomplishing there is to
> >> expend a lot of cycles while holding exclusive lock on the page, when
> >> there is good reason to think that you're blocking other people who are
> >> interested in using the page. Eliminating the separation between that
> >> and cleanup would also allow eliminating the separate "PD_FRAGMENTED"
> >> page state.
>
> > The reason we did it that way because repairing fragmentation seems
> > much more costly that pruning. Please note that we prune a single
> > chain during index fetch. Its only for heap-scans (and VACUUM) that
> > we try to prune all chains in the page. So unless we are doing
> heap-scan,
> > I am not sure if we are spending too much time holding the exclusive
> > lock. I agree we don't have any specific numbers to prove that though.
>
> If you don't have numbers proving that this extra complication has a
> benefit, I'd vote for simplifying it. The SnapshotAny case is going to
> bite other people besides you in future.

OK. So if I get you correctly, you are suggesting to acquire cleanup lock.
If we don't get that, we don't to any maintenance work. Otherwise, we prune
and repair fragmentation in one go.

A related question is: should we always prune all chains in the
page ? I guess if we are going to repair fragmentation, it would make
more sense to do that.

> Another reasoning behind separating these two steps is: pruning
> > requires exclusive lock whereas repairing fragmentation requires
> > cleanup lock.
>
> This is nonsense. Those are the same lock. If you have the former and
> not the latter, it just means that you *know* there is contention for
> the page. It seems to me that performing optional maintenance work in
> such a situation is completely wrong.
>
>
Oh yes, they are the same lock. The difference is the chances of getting
one is more than the other. But I agree with your argument about the
contention
and maintenance work. I think we can do what you are suggesting and
then fine tune it.

Thanks,
Pavan

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

"Pavan Deolasee" <pavan(dot)deolasee(at)gmail(dot)com> writes:
> On 8/30/07, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>> I don't think that works --- what if the last tuple in the chain isn't
>> committed good yet? If its inserter ultimately rolls back, you've
>> indexed the wrong value.

> I am confused. How could we get ShareLock on the relation while
> there is some open transaction which has inserted a tuple in the
> table ? (Of course, I am not considering the system tables here)

Not if someone else releases lock before committing. Which I remind you
is a programming technique we use quite a lot with respect to the system
catalogs. I'm not prepared to guarantee that there is no code path in
core (much less in contrib or third-party addons) that doesn't do it on
a user table; even less that no such path will ever appear in future.
As things stand it's a pretty harmless error --- the worst consequence
I know of is that a VACUUM FULL starting right then might bleat and
refuse to do shrinking. What you propose is to turn the case into a
cause of silent index corruption.

A more robust solution would be to wait out the source transaction if
CREATE INDEX comes across an INSERT_IN_PROGRESS or DELETE_IN_PROGRESS
HOT tuple. Or you could throw an error, since it's not really likely to
happen (except maybe in a system catalog REINDEX operation). But the
way the patch approaches this at the moment is far too fragile IMHO.

If we approach it this way, we might also be able to jettison some of
the other complexity such as idxcreatexid.

>> Isn't the extra machination for C.I.C. just useless complication?
>> What's the point of avoiding creation of new broken HOT chains when
>> you still have to deal with existing ones?

> IMHO the extra step in C.I.C simplifies the index build.

If you make the change suggested above, I think you don't need to do
things differently in C.I.C.

>>> I also don't think I
>>> believe the reasoning for not indexing DELETE_IN_PROGRESS hot-updated
>>> tuples: what if the index completion commits, but the concurrent delete
>>> rolls back? Then you've got a valid tuple that's not in the index.
>>
>> Since CREATE INDEX works with ShareLock on the relation, we can
>> safely assume that we can't find any DELETE_IN_PROGRESS tuples except
>> those deleted by our own transaction. The only exception is system
>> relation, but we don't do HOT updates on system relation.

Same issue as above: this makes correctness utterly dependent on nobody
releasing locks early.

> OK. So if I get you correctly, you are suggesting to acquire cleanup lock.
> If we don't get that, we don't to any maintenance work. Otherwise, we prune
> and repair fragmentation in one go.

Yeah, that's what I'm thinking; then there's no need to track a separate
page state where we've pruned but not defragmented.

regards, tom lane

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

>>> Isn't the extra machination for C.I.C. just useless complication?
>>> What's the point of avoiding creation of new broken HOT chains when
>>> you still have to deal with existing ones?
>
>> IMHO the extra step in C.I.C simplifies the index build.
>
> If you make the change suggested above, I think you don't need to do
> things differently in C.I.C.

It seems to me if you wait out transactions as you come across them you could
end up waiting a whole lot longer than the way it works now where it waits
them all out at the end of the first pass.

>> OK. So if I get you correctly, you are suggesting to acquire cleanup lock.
>> If we don't get that, we don't to any maintenance work. Otherwise, we prune
>> and repair fragmentation in one go.
>
> Yeah, that's what I'm thinking; then there's no need to track a separate
> page state where we've pruned but not defragmented.

Note that you still need to do it in two steps, you just get to postpone the
pruning work to the same point in time as the defragmenting. You can never
"acquire" the cleanup lock when it comes time to insert a new update version
since the executor still holds references to the original tuple.

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com

Gregory Stark <stark(at)enterprisedb(dot)com> writes:
>> If you make the change suggested above, I think you don't need to do
>> things differently in C.I.C.

> It seems to me if you wait out transactions as you come across them you could
> end up waiting a whole lot longer than the way it works now where it waits
> them all out at the end of the first pass.

I think you might have misread that --- I intended to say that C.I.C
could still work the way it does today, not that it would be exactly
like regular CREATE INDEX. The wait-out business should only be needed
for a regular CREATE INDEX, and in that case there's no cumulative
waiting effect because no new conflicting transactions are coming in.
C.I.C. should be able to fix things up in its second pass instead of
waiting during the first one.

regards, tom lane

Tom Lane escribió:
> "Pavan Deolasee" <pavan(dot)deolasee(at)gmail(dot)com> writes:
> > On 8/30/07, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> >> I don't think that works --- what if the last tuple in the chain isn't
> >> committed good yet? If its inserter ultimately rolls back, you've
> >> indexed the wrong value.
>
> > I am confused. How could we get ShareLock on the relation while
> > there is some open transaction which has inserted a tuple in the
> > table ? (Of course, I am not considering the system tables here)
>
> Not if someone else releases lock before committing.

FWIW, a red flag raised for me here, though maybe it is irrelevant or
unimportant. Currently, VACUUM acquires an exclusive lock for
truncating the table. The lock is kept till commit. However I am
proposing that it be released before commit.

Now, VACUUM never inserts rows. But I don't claim I understand what's
going on here.

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

Alvaro Herrera <alvherre(at)commandprompt(dot)com> writes:
> Tom Lane escribi:
>> Not if someone else releases lock before committing.

> FWIW, a red flag raised for me here, though maybe it is irrelevant or
> unimportant. Currently, VACUUM acquires an exclusive lock for
> truncating the table. The lock is kept till commit. However I am
> proposing that it be released before commit.

I think that's all right, because it's dealing with a different set of
concerns. AFAICS the only issue for truncation is to prevent physical
access to the blocks in question until we can get rid of them. Once
they're gone, if there wasn't an active seqscan (with an
already-established notion of the max block number to scan to), there
would be no reason for anyone to try to touch them.

regards, tom lane

On 8/31/07, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>
> "Pavan Deolasee" <pavan(dot)deolasee(at)gmail(dot)com> writes:
>
> Not if someone else releases lock before committing. Which I remind you
> is a programming technique we use quite a lot with respect to the system
> catalogs. I'm not prepared to guarantee that there is no code path in
> core (much less in contrib or third-party addons) that doesn't do it on
> a user table; even less that no such path will ever appear in future.
> As things stand it's a pretty harmless error --- the worst consequence
> I know of is that a VACUUM FULL starting right then might bleat and
> refuse to do shrinking. What you propose is to turn the case into a
> cause of silent index corruption.
>
> A more robust solution would be to wait out the source transaction if
> CREATE INDEX comes across an INSERT_IN_PROGRESS or DELETE_IN_PROGRESS
> HOT tuple. Or you could throw an error, since it's not really likely to
> happen (except maybe in a system catalog REINDEX operation). But the
> way the patch approaches this at the moment is far too fragile IMHO.

OK. I looked at the code again. In CVS HEAD we assume that we
should never see an DELETE_IN_PROGRESS/INSERT_IN_PROGRESS
unless its deleted/inserted by our own transaction or we are indexing a
system table. Except for these cases, we throw an error.

With HOT, we keep it the same i.e. if we see a
DELETE_IN_PROGRESS/INSERT_IN_PROGRESS tuple, we throw an error,
unless its deleted/inserted by us or this is a system table..
What we change is if we find a DELETE_IN_PROGRESS tuple deleted
by our own transaction and its HOT-updated, we skip that tuple. This is
fine because if the CREATE INDEX commits the DELETE is also committed
and the tuple is not visible (I am still assuming the indcreatxid mechanism
is in place)

So if we don't do HOT update on system tables, the current algorithm
should work fine because we should never find a HOT updated tuple
in the system table and the error-out mechanism should ensure
that we don't corrupt user tables.

So I guess what you are suggesting is to turn on HOT on system tables
and then wait-out any DELETING/INSETING transaction if we find such
a tuple during CREATE INDEX. I think this would work and since we are
talking about system tables, the wait-out business won't be harmful - I
remember there were objections when I suggested this as a general solution.

If we approach it this way, we might also be able to jettison some of
> the other complexity such as idxcreatexid.

I doubt, unless we replace it with something better. I think indcreatexid
serves
another purpose. While building an index, we skip any RECENTLY_DEAD
HOT-updated tuples. This is required to handle the existing HOT chains
which are broken with respect to the new index. Essentially what it means
is we don't want to index anything other than the last committed good tuple
in the HOT chain. So when we skip any intermediate RECENTLY_DEAD tuples,
which are potentially visible to the existing running transactions, we want
those transactions NOT to use this new index.

> > IMHO the extra step in C.I.C simplifies the index build.
>
> If you make the change suggested above, I think you don't need to do
> things differently in C.I.C.

I am not sure if I follow you correctly here. The issue with CIC is that
it works with a snapshot. So during initial index build, we might index
a tuple which is in the middle of a broken HOT chain. In the second phase,
we just don't need to index the tuple at the head of the chain, but also
remove the previously inserted tuple, otherwise there would be two
references from the index to the same root heap tuple.

The additional step which does two things:

1) Create catalog entry - stops any new broken HOT chains being created
2) Wait-out existing transactions - makes sure that when the index is built,
we only index the last committed good tuple in the chain.

> >>
> >> Since CREATE INDEX works with ShareLock on the relation, we can
> >> safely assume that we can't find any DELETE_IN_PROGRESS tuples except
> >> those deleted by our own transaction. The only exception is system
> >> relation, but we don't do HOT updates on system relation.
>
> Same issue as above: this makes correctness utterly dependent on nobody
> releasing locks early.

As I said above, we in fact throw an error for user tables. But if we want
to support HOT updates on system tables, we may need to do the
wait-out business. In fact, now that I think about it there is no other
fundamental reason to not support HOT on system tables. So we
can very well do what you are suggesting.

> OK. So if I get you correctly, you are suggesting to acquire cleanup
> lock.
> > If we don't get that, we don't to any maintenance work. Otherwise, we
> prune
> > and repair fragmentation in one go.
>
> Yeah, that's what I'm thinking; then there's no need to track a separate
> page state where we've pruned but not defragmented.
>
>

I agree. Lets keep it simple and we can always improve it later. The
only thing that worries me how to balance between repair fragmentation
(which is costly operation since it involves several memmoves) and chain
pruning. It might be alright to delay repair operation, but if we end up
with long
chains, fetches might suffer.

Thanks,
Pavan

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

On 8/31/07, Pavan Deolasee <pavan(dot)deolasee(at)gmail(dot)com> wrote:
>
>
>
> In fact, now that I think about it there is no other
> fundamental reason to not support HOT on system tables. So we
> can very well do what you are suggesting.
>
>

On second thought, I wonder if there is really much to gain by
supporting HOT on system tables and whether it would justify all
the complexity. Initially I thought about CatalogUpdateIndexes to
which we need to teach HOT. Later I also got worried about
building the HOT attribute lists for system tables and handling
all the corner cases for bootstrapping and catalog REINDEX.
It might turn out to be straight forward, but I am not able to
establish that with my limited knowledge in the area.

I would still vote for disabling HOT on catalogs unless you see
strong value in it.

Thanks,
Pavan

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

On Fri, Aug 31, 2007 at 12:53:51PM +0530, Pavan Deolasee wrote:
> On 8/31/07, Pavan Deolasee <pavan(dot)deolasee(at)gmail(dot)com> wrote:
> >
> >
> >
> > In fact, now that I think about it there is no other
> > fundamental reason to not support HOT on system tables. So we
> > can very well do what you are suggesting.
> >
> >
>
> On second thought, I wonder if there is really much to gain by
> supporting HOT on system tables and whether it would justify all
> the complexity. Initially I thought about CatalogUpdateIndexes to
> which we need to teach HOT. Later I also got worried about
> building the HOT attribute lists for system tables and handling
> all the corner cases for bootstrapping and catalog REINDEX.
> It might turn out to be straight forward, but I am not able to
> establish that with my limited knowledge in the area.
>
> I would still vote for disabling HOT on catalogs unless you see
> strong value in it.

What about ANALYZE? Doesn't that do a lot of updates?

BTW, I'm 100% in favor of pushing system catalog HOT until later; it's
be silly to risk not getting hot in 8.3 because of catalog HOT.
--
Decibel!, aka Jim Nasby decibel(at)decibel(dot)org
EnterpriseDB http://enterprisedb.com 512.569.9461 (cell)

Decibel! <decibel(at)decibel(dot)org> writes:
> BTW, I'm 100% in favor of pushing system catalog HOT until later; it's
> be silly to risk not getting hot in 8.3 because of catalog HOT.

I see this the other way around: if it doesn't work on system catalogs,
it probably doesn't work, period. I'm not in favor of treating the
catalogs differently.

regards, tom lane

On 9/1/07, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>
>
> I see this the other way around: if it doesn't work on system catalogs,
> it probably doesn't work, period. I'm not in favor of treating the
> catalogs differently.
>
>
Now that I hear you, I know what to do next :-)

I don't think there is any fundamental problem with system catalogs,
its only the additional complexity that I was worried about. Anyways,
I will rework things as per your suggestion. And I take your point that
making it work on all tables will give us more confidence on the code.

Thanks,
Pavan

P.S. Next week is bad for me :-( I am on vacation on Thursday/Friday
and for remaining days, I may not be able to spend extra cycles,
apart from regular working hours.

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

Tom Lane wrote:
> "Pavan Deolasee" <pavan(dot)deolasee(at)gmail(dot)com> writes:
>> Please see the version 14 of HOT patch attached.
>
> I expected to find either a large new README, or some pretty substantial
> additions to existing README files, to document how this all works.

Here's an updated version of the README I posted earlier. It now
reflects the changes to how pruning works.

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

Heikki Linnakangas wrote:
> Tom Lane wrote:
> > "Pavan Deolasee" <pavan(dot)deolasee(at)gmail(dot)com> writes:
> >> Please see the version 14 of HOT patch attached.
> >
> > I expected to find either a large new README, or some pretty substantial
> > additions to existing README files, to document how this all works.
>
> Here's an updated version of the README I posted earlier. It now
> reflects the changes to how pruning works.

I have taken this, and Pavan's documentation about CREATE INDEX, and
worked up an updated README. Comments? Corrections?

I plan to put this in src/backend/access/heap/README.HOT.

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

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

"Bruce Momjian" <bruce(at)momjian(dot)us> writes:

> Heikki Linnakangas wrote:
>
>> Here's an updated version of the README I posted earlier. It now
>> reflects the changes to how pruning works.
>
> I have taken this, and Pavan's documentation about CREATE INDEX, and
> worked up an updated README. Comments? Corrections?

You should also take the appendix to Heikki's README about CREATE INDEX that I
wrote.

>
> I plan to put this in src/backend/access/heap/README.HOT.

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com

Bruce Momjian wrote:
> Heikki Linnakangas wrote:
>> Tom Lane wrote:
>>> "Pavan Deolasee" <pavan(dot)deolasee(at)gmail(dot)com> writes:
>>>> Please see the version 14 of HOT patch attached.
>>> I expected to find either a large new README, or some pretty substantial
>>> additions to existing README files, to document how this all works.
>> Here's an updated version of the README I posted earlier. It now
>> reflects the changes to how pruning works.
>
> I have taken this, and Pavan's documentation about CREATE INDEX, and
> worked up an updated README. Comments? Corrections?

Thanks, that's much better.

I made some corrections, patch attached. I clarified the terminology a
bit: "row", "row version" and "tuple" were mixed in some places. "Tuple"
and "row version" are synonyms in my mind, so they can be used
interchangeably, but "row" is not. Row is a higher level concept and
refers to what a user sees when he does a "SELECT * FROM foo". There can
be multiple row versions, or tuples, behind a single row.

I also changed "ctid" to "line pointer" in most places. ctid is a field
on a tuple, I don't think we use that term to refer to line pointers
anywhere.

> I plan to put this in src/backend/access/heap/README.HOT.

Sounds good. I didn't look at the create index stuff.

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

"Bruce Momjian" <bruce(at)momjian(dot)us> writes:

> I have taken this, and Pavan's documentation about CREATE INDEX, and
> worked up an updated README. Comments? Corrections?

Oh, you I think the CREATE INDEX documentation you refer to was actually the
one I suggested.

A few tweaks:

> (If we find any HOT-updated tuples with RECENTLY_DEAD or
> DELETE_IN_PROGRESS we ignore it assuming that we will also come across
> the _end_ of the update chain and index that instead.)

There's more to this. We build a mapping telling us the Root tuple for each
tuple in the page. Then when we scan tuples looking for the Head of each HOT
chain (ie, a tuple that wasn't HOT updated) and index the corresponding Root
from the map using the key value from the Head tuple.

We treat DELETE_IN_PROGRESS the same way we treat RECENTLY_DEAD (and
INSERT_IN_PROGRESS the same as LIVE) because we assume it's been deleted (or
inserted) by our own transaction. So while it's not actually committed yet we
can assume it is since if its transaction aborts the index creation itself
will be aborted. Other transactions cannot be deleting or inserting tuples
without having committed or aborted already because we have a lock on the
table and the other transactions normally keep their locks until they exit.

NOTE: This is something likely to change. Current discussions are leading
towards handling DELETE_IN_PROGRESS and INSERT_IN_PROGRESS from other
transactions. We would do this by waiting until the transactions owning those
tuples exit. This would allow us to index tables being used by transactions
which release their locks early to work. In particular this happens for system
tables.

> The tricky case arises with queries executed in the same transaction as
> CREATE INDEX. In the case of a new table created within the same
> transaction (such as with pg_dump), the index will be usable because
> there will never be any HOT update chains so the indcreatexid will never
> be set.

This is unclear and perhaps misleading. I think it needs to be more like "In
the case of a new table in which rows were inserted but none updated (such as
with pg_dump) the index will be usable because ..."

> Also in the case of a read-committed transaction new queries will be able to
> use the index. A serializable transaction building an index on an existing
> table with HOT updates cannot not use the index.

I don't think this is clear and I'm not sure it's right.

Currently the transaction that actually did the CREATE INDEX has to follow the
same rules as other transactions. This means if there were any visible hot
updated tuples and the index is therefore marked with our xid in indcreatexid
we will *not* be able to use it in the same transaction as our xid is never in
our serializable snapshot. This is true even if we're not in serializable mode
as we cannot know what earlier snapshots are still in use and may be used with
the new plan.

NOTE: This again is something likely to change. In many cases it ought to be
possible to have the transaction use the index it just built even if there
were visible HOT updated tuples in it.

In particular in READ COMMITTED transactions which have no outstanding
commands using early snapshots then subsequent planning ought to be able to
use the index. Even if outstanding commands are using old snapshots if we can
be sure they can't use the new plan then it would still be safe to use the
index in the new plan. Also in SERIALIZABLE mode those same statements hold
for temporary tables.

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com

On 9/4/07, Gregory Stark <stark(at)enterprisedb(dot)com> wrote:

>
>
> NOTE: This is something likely to change. Current discussions are leading
> towards handling DELETE_IN_PROGRESS and INSERT_IN_PROGRESS from other
> transactions. We would do this by waiting until the transactions owning
> those
> tuples exit. This would allow us to index tables being used by
> transactions
> which release their locks early to work. In particular this happens for
> system
> tables.

The latest patch (v15) posted does this for system tables. We still
error-out for non-system tables, just the way we do today.

> The tricky case arises with queries executed in the same transaction as
> > CREATE INDEX. In the case of a new table created within the same
> > transaction (such as with pg_dump), the index will be usable because
> > there will never be any HOT update chains so the indcreatexid will never
> > be set.
>
> This is unclear and perhaps misleading. I think it needs to be more like
> "In
> the case of a new table in which rows were inserted but none updated (such
> as
> with pg_dump) the index will be usable because ..."

Right.

> Also in the case of a read-committed transaction new queries will be able
> to
> > use the index. A serializable transaction building an index on an
> existing
> > table with HOT updates cannot not use the index.
>
> I don't think this is clear and I'm not sure it's right.
>
> Currently the transaction that actually did the CREATE INDEX has to follow
> the
> same rules as other transactions. This means if there were any visible hot
> updated tuples and the index is therefore marked with our xid in
> indcreatexid
> we will *not* be able to use it in the same transaction as our xid is
> never in
> our serializable snapshot. This is true even if we're not in serializable
> mode
> as we cannot know what earlier snapshots are still in use and may be used
> with
> the new plan.
>
> NOTE: This again is something likely to change. In many cases it ought to
> be
> possible to have the transaction use the index it just built even if there
> were visible HOT updated tuples in it.
>
>
It would be great if I can achieve that. But we haven't been able to
find a solution that would work in all cases and yet not too complicated.
My guess is any such solution will involve breaking the existing
HOT chains.

Right now we support one of the most common use case where
a table is created, loaded with data and one or more indexes are
created - all in the same transaction. In this case, the index will
be usable in the same transaction. And may be we should be
able do something better for READ COMMITTED transactions.

Thanks,
Pavan

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

On 9/4/07, Bruce Momjian <bruce(at)momjian(dot)us> wrote:
>
>
> I have taken this, and Pavan's documentation about CREATE INDEX, and
> worked up an updated README. Comments? Corrections?

Thanks Bruce, Heikki, Greg for helping me with the documentation.

> The requirements for doing a HOT update is that none of the indexed
> columns are changed. That is checked at execution time, comparing the
> binary representation of the old and new values.

It would be worth mentioning that columns appearing in predicates
of partial indexes and expressions of expression indexes are also
checked. If any of these columns are changed, HOT update is not done.

>
> When the last live tuple in an update chain becomes dead (after a DELETE
> or a cold update), the redirecting line pointer is marked as redirected
> dead. That allows us to immediately reuse the heap space (but not the
> line pointer itself).

A lazy vacuum is required to reclaim redirect-dead line pointers.

To limit the damage in the worst case, and to
> keep numerous arrays as well as the bitmaps in bitmap scans reasonably
> sized, the maximum number of line pointers (MaxHeapTuplesPerPage) is
> arbitrarily capped at twice its previous maximum.

With the latest patch, we have reverted it back to the original value.

VACUUM FULL
> -----------

It might be worth mentioning that vacuum full also removes
redirected line pointers by making them directly point to
the first tuple in the HOT chain. We can do so, because vacuum
full works with an exclusive lock on the relation.

VACUUM
> ------
>
> There is little change to regular vacuum. It removes dead HOT tuples,
> like pruning does, and cleans up any redirected dead line pointers.

One change that is worth mentioning is that with HOT it needs vacuum
strength
lock in the first phase (currently it works with SHARE lock if no tuples
need
freezing or EXCLUSIVE lock otherwise). We can improve it a bit by first
checking if there is really a need for pruning and then only go for cleanup
lock. But thats probably not worth the efforts (atleast for large tables
where
we should usually get cleanup lock rather easily).

Statistics
> ----------
>
> XXX: How do HOT-updates affect statistics? How often do we need to run
> autovacuum?

As the latest patch stands, we track dead-space in the relation and trigger
autovacuuum based on the percentage of dead space in the table. We
don't have any mechanism to account for index bloat yet. Autoanalyze
does not change.

Thanks,
Pavan

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

Gregory Stark wrote:
>
> "Bruce Momjian" <bruce(at)momjian(dot)us> writes:
>
> > I have taken this, and Pavan's documentation about CREATE INDEX, and
> > worked up an updated README. Comments? Corrections?
>
> Oh, you I think the CREATE INDEX documentation you refer to was actually the
> one I suggested.

Sorry, I see now it was you who wrote that section, not Pavan.

> A few tweaks:
>
> > (If we find any HOT-updated tuples with RECENTLY_DEAD or
> > DELETE_IN_PROGRESS we ignore it assuming that we will also come across
> > the _end_ of the update chain and index that instead.)
>
> There's more to this. We build a mapping telling us the Root tuple for each
> tuple in the page. Then when we scan tuples looking for the Head of each HOT
> chain (ie, a tuple that wasn't HOT updated) and index the corresponding Root
> from the map using the key value from the Head tuple.
>
> We treat DELETE_IN_PROGRESS the same way we treat RECENTLY_DEAD (and
> INSERT_IN_PROGRESS the same as LIVE) because we assume it's been deleted (or
> inserted) by our own transaction. So while it's not actually committed yet we
> can assume it is since if its transaction aborts the index creation itself
> will be aborted. Other transactions cannot be deleting or inserting tuples
> without having committed or aborted already because we have a lock on the
> table and the other transactions normally keep their locks until they exit.

Updated text:

Because we have a lock on the table, any RECENTLY_DEAD,
DELETE_IN_PROGRESS, and INSERT_IN_PROGRESS tuples belong to our own
transction. Therefore we can consider them committed since if the
CREATE INDEX commits, they will be committed, and if it aborts the index
is discarded.

> NOTE: This is something likely to change. Current discussions are leading
> towards handling DELETE_IN_PROGRESS and INSERT_IN_PROGRESS from other
> transactions. We would do this by waiting until the transactions owning those
> tuples exit. This would allow us to index tables being used by transactions
> which release their locks early to work. In particular this happens for system
> tables.

OK, we will just have to update the README then.

> > The tricky case arises with queries executed in the same transaction as
> > CREATE INDEX. In the case of a new table created within the same
> > transaction (such as with pg_dump), the index will be usable because
> > there will never be any HOT update chains so the indcreatexid will never
> > be set.
>
> This is unclear and perhaps misleading. I think it needs to be more like "In
> the case of a new table in which rows were inserted but none updated (such as
> with pg_dump) the index will be usable because ..."

Done.

> > Also in the case of a read-committed transaction new queries will be able to
> > use the index. A serializable transaction building an index on an existing
> > table with HOT updates cannot not use the index.
>
> I don't think this is clear and I'm not sure it's right.
>
> Currently the transaction that actually did the CREATE INDEX has to follow the
> same rules as other transactions. This means if there were any visible hot
> updated tuples and the index is therefore marked with our xid in indcreatexid
> we will *not* be able to use it in the same transaction as our xid is never in
> our serializable snapshot. This is true even if we're not in serializable mode
> as we cannot know what earlier snapshots are still in use and may be used with
> the new plan.

Updated paragraph:

The CREATE INDEX transaction cannot not use the index if HOT rows exist
in the table. Fortunately, many CREATE INDEX transactions use new
tables in which rows are inserted but not updated (such as with
pg_dump). Such tables have no HOT rows so the index will be usable
because indcreatexid will never be set.

> NOTE: This again is something likely to change. In many cases it ought to be
> possible to have the transaction use the index it just built even if there
> were visible HOT updated tuples in it.
>
> In particular in READ COMMITTED transactions which have no outstanding
> commands using early snapshots then subsequent planning ought to be able to
> use the index. Even if outstanding commands are using old snapshots if we can
> be sure they can't use the new plan then it would still be safe to use the
> index in the new plan. Also in SERIALIZABLE mode those same statements hold
> for temporary tables.

OK, we can update the README at that point.

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

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

Pavan Deolasee wrote:
> It would be worth mentioning that columns appearing in predicates
> of partial indexes and expressions of expression indexes are also
> checked. If any of these columns are changed, HOT update is not done.

Added now:

Tuples are checked against expression and
partial indexes to be sure no referenced columns change.

Something about those was in the original version but not the new one I
used.

> > When the last live tuple in an update chain becomes dead (after a DELETE
> > or a cold update), the redirecting line pointer is marked as redirected
> > dead. That allows us to immediately reuse the heap space (but not the
> > line pointer itself).
>
>
>
> A lazy vacuum is required to reclaim redirect-dead line pointers.

Updated:

When the last live tuple in an update chain becomes dead (after a DELETE
or a cold update), the redirecting line pointer is marked as redirected
dead. That allows us to immediately reuse the heap space, while VACUUM
can reclaim the line pointer space.

> To limit the damage in the worst case, and to
> > keep numerous arrays as well as the bitmaps in bitmap scans reasonably
> > sized, the maximum number of line pointers (MaxHeapTuplesPerPage) is
> > arbitrarily capped at twice its previous maximum.
>
>
>
> With the latest patch, we have reverted it back to the original value.

Updated:

We have effectively implemented the "truncate dead tuples to just line
pointer" idea that has been proposed and rejected before because of fear
of line pointer bloat. To limit the damage in the worst case, and to
keep numerous arrays as well as the bitmaps in bitmap scans reasonably
sized, the maximum number of line pointers (MaxHeapTuplesPerPage) is
arbitrarily capped.

> VACUUM FULL
> > -----------
>
>
>
> It might be worth mentioning that vacuum full also removes
> redirected line pointers by making them directly point to
> the first tuple in the HOT chain. We can do so, because vacuum
> full works with an exclusive lock on the relation.

Updated:

To make vacuum full work, any DEAD tuples in the middle of an update
chain need to be removed (see comments at the top of
heap_prune_hotchain_hard() for details). Vacuum full performs a more
aggressive pruning that not only removes dead tuples at the beginning of
an update chain, but scans the whole chain and removes any intermediate
dead tuples as well. It also removes redirected line pointers by making
them directly point to the first tuple in the HOT chain. This is
possible because vacuum full works with an exclusive lock on the
relation.

> VACUUM
> > ------
> >
> > There is little change to regular vacuum. It removes dead HOT tuples,
> > like pruning does, and cleans up any redirected dead line pointers.
>
>
>
> One change that is worth mentioning is that with HOT it needs vacuum
> strength
> lock in the first phase (currently it works with SHARE lock if no tuples
> need
> freezing or EXCLUSIVE lock otherwise). We can improve it a bit by first
> checking if there is really a need for pruning and then only go for cleanup
> lock. But thats probably not worth the efforts (atleast for large tables
> where
> we should usually get cleanup lock rather easily).
>
>
>
> Statistics
> > ----------
> >
> > XXX: How do HOT-updates affect statistics? How often do we need to run
> > autovacuum?
>
>
>
> As the latest patch stands, we track dead-space in the relation and trigger
> autovacuuum based on the percentage of dead space in the table. We
> don't have any mechanism to account for index bloat yet. Autoanalyze
> does not change.

OK.

Current README.HOT version:

ftp://momjian.us/pub/postgresql/mypatches/README.HOT

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

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

"Pavan Deolasee" <pavan(dot)deolasee(at)gmail(dot)com> writes:

> It would be worth mentioning that columns appearing in predicates
> of partial indexes and expressions of expression indexes are also
> checked. If any of these columns are changed, HOT update is not done.

In discussion a question arose. I don't think we currently compare these
columns before when we're building an index and find a visible hot update. We
just set hot_visible even if the chain might still be a valid hot chain for
the new index right? Should we consider checking the columns in that case too?
Or would it be too much extra overhead?

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com

Bruce Momjian <bruce(at)momjian(dot)us> writes:
> Current README.HOT version:
> ftp://momjian.us/pub/postgresql/mypatches/README.HOT

I've done some further editorializing and wordsmithing on this,
and marked with XXX some areas that seem like they're still red flags
(or at least inadequately described).

regards, tom lane

On 9/12/07, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>
> Bruce Momjian <bruce(at)momjian(dot)us> writes:
> > Current README.HOT version:
> > ftp://momjian.us/pub/postgresql/mypatches/README.HOT
>
> I've done some further editorializing and wordsmithing on this,
> and marked with XXX some areas that seem like they're still red flags
> (or at least inadequately described).

Thanks a lot.

> CREATE INDEX CONCURRENTLY
> -------------------------
>
> In the concurrent case we take a different approach. We create the
> pg_index entry immediately, before we scan the table. The pg_index entry
> is marked as "not ready for inserts". Then we commit and wait for any
> transactions which have the table open to finish. This ensures that no
> *new* HOT updates will change the key value for our new index, because all
> transactions will see the existence of the index and will respect its
> constraint on which updates can be HOT.
>
> After waiting for transactions which had the table open, we build the
> index with a snapshot. Because we waited for anyone who existed before
> the index was created, any tuples seen in the snapshot will have only
> valid forward-growing HOT chains. (They might still have older HOT
> updates behind them which are broken.) As above, we point the index
> pointer at the root of the HOT-update chain but we use the key from the
> end of the chain.
>
> We mark the index open for inserts (but still not ready for reads) then
> we again wait for transactions which have the table open. Then we take
> a second reference snapshot and validate the index. This searches for
> tuples missing from the index --- but it again has to look up the root
> of the HOT chains and search for those tuples in the index.
>
> Then we wait until every transaction that could have a snapshot older than
> the second reference snapshot is finished. This ensures that nobody is
> alive any longer who could possibly see any of the older tuples in a
> broken HOT chain. (This condition is actually stronger than what is
> needed to protect the broken HOT chains --- the problem we are dealing
> with is tuples inserted after we took our first reference snapshot.
> Those will be part of valid HOT-chains, but might not be in the index.)
>
> XXX the above being the case, why should we bother with all this extra
> mechanism? Seems we could dispense with "not ready for inserts".
>
>

The "not ready for inserts" logic is necessary because we have separated
the steps of creating the catalog entry for the new index and actual
bottom-up
building of the index into separate transactions. My worry was once the
catalog
entry is committed, an index insert won't work with the concurrent index
build.

I guess I also need to explain why we need to separate the catalog entry
creation and index building activities into separate transactions. The
primary
purpose is to handle existing broken HOT chains and avoid any new
broken chains being created while we are building the index.

Without this additional step, while we are building the index in the first
phase
using a snapshot, its possible that a broken HOT chain may get created
forwarding to the tuple that we index. For example:

A table with two columns a and b. Say, we already have an index on 'a'
and creating a new index on 'b'. Say, there is a tuple (0, 1): (1, 11) in
the table where (0, 1) in the line pointer of the tuple.
This is the visible tuple when we took snapshot in the first phase and so
we shall index this tuple with key 11 and TID (0, 1). But before the first
phase
finishes, the tuple is updated to (0, 2): (1, 22). This would be a HOT
update
resulting in a broken chain. The root line pointer for the new tuple is
still (0, 1).
CIC now waits for the updating transaction,
takes a fresh snapshot and starts the second phase. In the second phase,
it must index the new tuple (1, 22) using the key 22 and TID (0, 1) because
thats the root line pointer for the chain. Now there is already an index
entry
in the new index with key 11 and TID (0, 1). Inserting another index entry
with
a different key and the same TID would certainly corrupt the index.

We solve this issue by first creating a catalog entry for the new index and
committing the transaction. We then wait
out for any conflicting transactions before taking snapshot for building the
index in the first phase. This arrangement guarantees that the snapshot
used in the first phase would always satisfy tuples at the head of the
existing HOT chains. At the same time, no new broken HOT chains are
created while we are building the index because the new index
(even though not yet ready) is consulted for all subsequent UPDATEs.

Hope this helps.

Thanks,
Pavan

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

On 9/12/07, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>
>
>
> VACUUM
> ------
>
> There is little change to regular vacuum. It removes dead HOT tuples,
> like pruning does, and cleans up any redirected dead line pointers.
>
> In lazy vacuum, we must not freeze a tuple that is in the middle of an
> update chain. That can happen when a tuple has xmin > xmax; it is the
> same scenario that requires "hard pruning" in VACUUM FULL. Freezing such
> tuples will break the check that xmin and xmax matches when following
> the chain. It is not a problem without HOT, because the preceding tuple
> in the chain must be dead as well so no one will try to follow the
> chain, but with HOT the preceding tuple would be DEAD_CHAIN, and someone
> might still need to follow the chain to find the live tuple. We avoid
> that by just not freezing such tuples. They can be frozen eventually,
> when the xmax of the preceding tuple is < OldestXmin as well.
>
> XXX doesn't the above completely break the anti-wraparound guarantees?
> And why couldn't we avoid the problem by pruning the previous tuple,
> which is surely dead?
>
>

We preserve anti-wraparound guarantees by not letting the relfrozenxid
advance past the minimum of cut-off xid and xmin/xmax of not-yet-frozen
tuples. Given that this is required to address corner case of DEAD tuple
following a RD tuple, the final relfrozenxid would be very close to the
cut-off xid. Isn't it ?

We could have actually pruned the preceding RD tuples (as we do in
vacuum full), but we were worried about missing some corner case
where someone may still want to follow the chain from the RD tuple.
We don't have any such concern with vacuum full because we run
with exclusive lock on the table. But if we agree that there is no
problem with pruning RD tuple preceding a DEAD tuple, we can
actually prune that tuple as well.

Thanks,
Pavan

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

On 9/12/07, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>
>
> VACUUM FULL
> -----------
>
> To make vacuum full work, any DEAD tuples in the middle of an update
> chain need to be removed (see comments at the top of
> heap_prune_hotchain_hard() for details). Vacuum full performs a more
> aggressive pruning that not only removes dead tuples at the beginning of
> an update chain, but scans the whole chain and removes any intermediate
> dead tuples as well. It also removes redirected line pointers by making
> them directly point to the first tuple in the HOT chain. This causes
> a user-visible change in the tuple's CTID, but since VACUUM FULL has
> always moved tuple CTIDs, that should not break anything.
>
> XXX any extra complexity here needs justification --- a lot of it.

We hard prune the chains and also clear up redirect line pointers
because doing so is safe within VACUUM FULL and it reduces addition
complexity in the actual VACUUM FULL work.

When we move tuples and tuple chains, we don't try to preserve
their HOT properties. So when tuples in a HOT chain are moved,
we reset their HEAP_ONLY_TUPLE and HEAP_HOT_UPDATED flags
and each tuple has its own index entry. This requires us to some
more book keeping work in terms on number of indexed tuples expected
etc because they are checked at the end of the index scan.

Statistics
> ----------
>
> XXX: How do HOT-updates affect statistics? How often do we need to run
> autovacuum and autoanalyze?
>
>
>
Auotovacuum needs to be run much less frequently with HOT. This is because
defragmentation reclaims dead space in a page, thus reducing total dead
space in a table. Right now we don't update FSM information about the page
after defragmenting it, so a UPDATE on a different page can still cause
relation extension even though there is free space in some other page.
The rational for not updating FSM is to let subsequent UPDATEs on the page
to use the freed up space. But one can argue that we should let the free
space to be used for other UPDATEs/INSERTs after leaving fillfactor worth
of space.

Another significant change regarding autovacuum is that we now track
the total dead space in the table instead of number of dead tuples. This
seems like a better approach because it takes into account varying tuple
sizes
into account. The tracked dead space is increased whenever we update/delete
a tuple (or insert is aborted) and reduced when a page is defragmented.
autovacuum_vacuum_scale_factor considers the percentage of dead space
to the size of the relation whereas autovacuum_vacuum_threshold
considers the absolute amount of dead space in terms of blocks.

Every UPDATE (HOT or COLD) contributes to the autoanalyze stats and
defragmentation/pruning has no effect on autoanalyze. IOW autoanalyze
would work just the way it does today. One change that is worh mentioning
and discussing is that we don't follow HOT chains while fetching tuples
during
autoanalyze and autoanalyze would consider all such tuples as DEAD.
In the worst case when all the tuples in the table are reachable via
redirected line pointers, this would confuse autoanalyze since it would
consider all tuples in the table as DEAD.

I think we should change this to follow HOT chain in analyze. Since we
fetch using SnapshotNow, if there is a live tuple at the end of the
chain, analyze would use that. Otherwise the tuple is considered as
DEAD.

Thanks,
Pavan

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

"Pavan Deolasee" <pavan(dot)deolasee(at)gmail(dot)com> writes:
> On 9/12/07, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>> XXX the above being the case, why should we bother with all this extra
>> mechanism? Seems we could dispense with "not ready for inserts".

> Without this additional step, while we are building the index in the first
> phase
> using a snapshot, its possible that a broken HOT chain may get created
> forwarding to the tuple that we index. For example:

> A table with two columns a and b. Say, we already have an index on 'a'
> and creating a new index on 'b'. Say, there is a tuple (0, 1): (1, 11) in
> the table where (0, 1) in the line pointer of the tuple.
> This is the visible tuple when we took snapshot in the first phase and so
> we shall index this tuple with key 11 and TID (0, 1). But before the first
> phase
> finishes, the tuple is updated to (0, 2): (1, 22). This would be a HOT
> update
> resulting in a broken chain. The root line pointer for the new tuple is
> still (0, 1).

Got it. I'll put something about this into the README.

regards, tom lane

"Pavan Deolasee" <pavan(dot)deolasee(at)gmail(dot)com> writes:
> On 9/12/07, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>> XXX doesn't the above completely break the anti-wraparound guarantees?
>> And why couldn't we avoid the problem by pruning the previous tuple,
>> which is surely dead?

> We preserve anti-wraparound guarantees by not letting the relfrozenxid
> advance past the minimum of cut-off xid and xmin/xmax of not-yet-frozen
> tuples. Given that this is required to address corner case of DEAD tuple
> following a RD tuple, the final relfrozenxid would be very close to the
> cut-off xid. Isn't it ?
> We could have actually pruned the preceding RD tuples (as we do in
> vacuum full), but we were worried about missing some corner case
> where someone may still want to follow the chain from the RD tuple.

This seems all wrong to me. We'd only be considering freezing a tuple
whose xmin precedes the global xmin. If it has a predecessor, that
predecessor has xmax equal to this one's xmin, therefore also preceding
global xmin, therefore it would be seen as DEAD not RECENTLY_DEAD.
So we should never need to freeze a tuple that isn't the start of its
HOT chain.

Also, if you find a DEAD tuple after a RECENTLY_DEAD one, you can
certainly prune both, because what this tells you is that both tuples
are in fact dead to all observers.

regards, tom lane

On 9/12/07, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>
>
>
> This seems all wrong to me. We'd only be considering freezing a tuple
> whose xmin precedes the global xmin. If it has a predecessor, that
> predecessor has xmax equal to this one's xmin, therefore also preceding
> global xmin, therefore it would be seen as DEAD not RECENTLY_DEAD.
> So we should never need to freeze a tuple that isn't the start of its
> HOT chain.

hm.. What you are saying is right. I fail to recollect any other scenario
that
had forced me to think freezing is a problem with HOT.

Also, if you find a DEAD tuple after a RECENTLY_DEAD one, you can
> certainly prune both, because what this tells you is that both tuples
> are in fact dead to all observers.
>
>
I agree. I ran a long test with this change and there doesn't seem to be
any issue. So lets prune everything including the latest DEAD tuple. That
would let us take out the changes related to freezing. I also think that
should let us remove the DEAD_CHAIN concept, but let me check.

Thanks,
Pavan

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

On 9/12/07, Pavan Deolasee <pavan(dot)deolasee(at)gmail(dot)com> wrote:
>
>
> One change that is worh mentioning
> and discussing is that we don't follow HOT chains while fetching tuples
> during
> autoanalyze and autoanalyze would consider all such tuples as DEAD.
> In the worst case when all the tuples in the table are reachable via
> redirected line pointers, this would confuse autoanalyze since it would
> consider all tuples in the table as DEAD.

This is all crap. I was under the impression that heap_release_fetch()
would never fetch a HOT tuple directly, but thats not true. analyze fetches
all tuples in the chosen block, so it would ultimately fetch the visible
tuple.
A tuple is counted DEAD only if its t_data is set to non-NULL. For
redirected
line pointer heap_release_fetch() will set t_data to NULL and hence these
line pointers are (rightly) not counted as DEAD. This is the right thing to
do
because lazy vacuum can not remove redirected line pointers.

I think we should change this to follow HOT chain in analyze.
>
>
>
We need not follow the chain, but we should check for redirect-dead line
pointers and count them as dead rows.

Thanks,
Pavan

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