Re: Fwd: Clarification about HOT

I went through the README on HOT. That was really a nice and cool feature.
Hats off to the person who thought about it. I have a couple of doubts about
it.

a) In the README, there is a statement like this.

In principle we could continue a HOT chain across
pages, but this would destroy the desired property of being able to
reclaim space with just page-local manipulations. Anyway, we don't
want to have to chase through multiple heap pages to get from an index
entry to the desired tuple, so it seems better to create a new index
entry for the new tuple.

I am especially interested in the case of continuing the HOT chain across
pages. When we are actually reclaiming space, we should check the snapshot
and reclaim it. If it is HOT updated, we will leave the top most tuple and
take the rest. So then the top most tuple will remain always and any index
scan now has to make read two heap pages to reach the target entry.Is this
the only reason, it was left out?

--
Thanks,
Gokul.
CertoSQL Project,
Allied Solution Group.
(www.alliedgroups.com)

On Fri, Nov 02, 2007 at 06:12:37PM +0530, Gokulakannan Somasundaram wrote:
> I am especially interested in the case of continuing the HOT chain across
> pages. When we are actually reclaiming space, we should check the snapshot
> and reclaim it. If it is HOT updated, we will leave the top most tuple and
> take the rest. So then the top most tuple will remain always and any index
> scan now has to make read two heap pages to reach the target entry.Is this
> the only reason, it was left out?

It's not that simple. At any point in time there may be dozens of
active snapshots, each of which might see a different tuple in the
chain. So to clear any tuple you have to wait until all active
snapshots are gone. You will almost never be able to reduce the chain
to just one.

As for your original question and jumping across pages, why stop at
one. Why not chain HOT tuples down 100 pages? Because then it gets very
expensive. Not to mention the locking considerations. Better keep it
simple.

Have a nice day,
--
Martijn van Oosterhout <kleptog(at)svana(dot)org> http://svana.org/kleptog/
> Those who make peaceful revolution impossible will make violent revolution inevitable.
> -- John F Kennedy

On 11/2/07, Martijn van Oosterhout <kleptog(at)svana(dot)org> wrote:
>
> On Fri, Nov 02, 2007 at 06:12:37PM +0530, Gokulakannan Somasundaram wrote:
> > I am especially interested in the case of continuing the HOT chain
> across
> > pages. When we are actually reclaiming space, we should check the
> snapshot
> > and reclaim it. If it is HOT updated, we will leave the top most tuple
> and
> > take the rest. So then the top most tuple will remain always and any
> index
> > scan now has to make read two heap pages to reach the target entry.Isthis
> > the only reason, it was left out?
>
> It's not that simple. At any point in time there may be dozens of
> active snapshots, each of which might see a different tuple in the
> chain. So to clear any tuple you have to wait until all active
> snapshots are gone. You will almost never be able to reduce the chain
> to just one.

I understand that if you have to Vacuum a tuple, it has to satisfy the
necessary snapshot requirements. i will never be able to reduce the chain to
just one, because the there is always a indirection at the top of HOT. I
understood this.

My question was is it the only reason for the decision to stop HOT across
pages.

As for your original question and jumping across pages, why stop at
> one. Why not chain HOT tuples down 100 pages? Because then it gets very
> expensive. Not to mention the locking considerations. Better keep it
> simple.

If you have to jump 100 pages, then you have 100 versions of the same tuple,
which are not to be Vacuumed. That's a heavily updated tuple indeed. Then
you will have 100 index tuples and you will anyway visit all those versions
in a normal index scan. The question is whether you want to visit it through
the HOT chain/ through the index entries. If you visit it through HOT chain,
indexes can be in reduced size.

--
Thanks,
Gokul.
CertoSQL Project,
Allied Solution Group.
(www.alliedgroups.com)

Gokulakannan Somasundaram wrote:
> I understand that if you have to Vacuum a tuple, it has to satisfy the
> necessary snapshot requirements. i will never be able to reduce the chain to
> just one, because the there is always a indirection at the top of HOT. I
> understood this.
>
> My question was is it the only reason for the decision to stop HOT across
> pages.

Another reason is that it avoids the whole problem of updating multiple
pages atomically, without deadlocks.

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

On 11/2/07, Heikki Linnakangas <heikki(at)enterprisedb(dot)com> wrote:
>
> Gokulakannan Somasundaram wrote:
> > I understand that if you have to Vacuum a tuple, it has to satisfy the
> > necessary snapshot requirements. i will never be able to reduce the
> chain to
> > just one, because the there is always a indirection at the top of HOT. I
>
> > understood this.
> >
> > My question was is it the only reason for the decision to stop HOT
> across
> > pages.
>
> Another reason is that it avoids the whole problem of updating multiple
> pages atomically, without deadlocks.

Thanks Heikki. I am still not getting what you said. In the case of HOT,
you need to update the top pointer to point to some other tuple in some
other page. That's one update. what's the other one?

say currently the top of heap chain points to (2,3) . Imagine we are making
the HOT chain through the pages. there might be a situation it should start
pointing to (4,5) after the tuple at (2,3) gets ready to be Vacuumed. We
should just lock the page where the top of HOT chain resides and update it
to point to (4,5). What else we should do atomically?

--
Thanks,
Gokul.
CertoSQL Project,
Allied Solution Group.
(www.alliedgroups.com)

On Fri, Nov 02, 2007 at 10:27:27PM +0530, Gokulakannan Somasundaram wrote:
> say currently the top of heap chain points to (2,3) . Imagine we are making
> the HOT chain through the pages. there might be a situation it should start
> pointing to (4,5) after the tuple at (2,3) gets ready to be Vacuumed. We
> should just lock the page where the top of HOT chain resides and update it
> to point to (4,5). What else we should do atomically?

You have to lock (4,5) also to make sure it's still there after you
update. Maybe just at that moment another vacuum saw that (4,5) can
also be cleaned, you have to lock all the pages to make sure the change
is atomic...

As soon as you have to lock more than one page, deadlocks become a
problem.

Have a nice day,
--
Martijn van Oosterhout <kleptog(at)svana(dot)org> http://svana.org/kleptog/
> Those who make peaceful revolution impossible will make violent revolution inevitable.
> -- John F Kennedy

Gokulakannan Somasundaram wrote:
> Thanks Heikki. I am still not getting what you said. In the case of HOT,
> you need to update the top pointer to point to some other tuple in some
> other page. That's one update. what's the other one?
>
> say currently the top of heap chain points to (2,3) . Imagine we are making
> the HOT chain through the pages. there might be a situation it should start
> pointing to (4,5) after the tuple at (2,3) gets ready to be Vacuumed. We
> should just lock the page where the top of HOT chain resides and update it
> to point to (4,5). What else we should do atomically?

Imagine one more update, and we end up with a HOT chain like this:

(2,3) -> (4,5) -> (6,7)

Where (2,3) is a redirecting line pointer, (4,5) is a tuple that can be
vacuumed, and (6,7) is the a live tuple. When vacuuming (4,5), the
redirecting line pointer (2,3) needs to be updated at the same time.

The chain could be even longer, requiring either locking and modifying
even more pages atomically, or doing the pruning in steps which leads to
more WAL traffic among other things.

It could be done, we already have to deal with locking two pages
simultaneously in heap_update, but it's pretty darn complex.

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

"Gokulakannan Somasundaram" <gokul007(at)gmail(dot)com> writes:

>> Another reason is that it avoids the whole problem of updating multiple
>> pages atomically, without deadlocks.
>
>
> Thanks Heikki. I am still not getting what you said. In the case of HOT,
> you need to update the top pointer to point to some other tuple in some
> other page. That's one update. what's the other one?

There are several problems, two that come to mind are:

1) How do you make the dead top pointer redirect to the first live pointer in
the chain? Currently we store the item number of the first live tuple in the
line pointer. You would have to keep the tuple around, though you could
truncate it to just the tuple header.

2) When vacuuming how do you find the head of the chain when you're looking at
a dead tuple? There's no space in the tuple header to store the head of the
chain. Besides you want to vacuum scanning sequentially, not randomly.

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com
Ask me about EnterpriseDB's On-Demand Production Tuning

Forgot to include the group...

---------- Forwarded message ----------
From: Gokulakannan Somasundaram <gokul007(at)gmail(dot)com>
Date: Nov 5, 2007 3:04 PM
Subject: Re: Clarification about HOT
To: Gregory Stark <stark(at)enterprisedb(dot)com>

On 11/2/07, Gregory Stark <stark(at)enterprisedb(dot)com> wrote:
>
>
> "Gokulakannan Somasundaram" <gokul007(at)gmail(dot)com> writes:
>
> >> Another reason is that it avoids the whole problem of updating multiple
> >> pages atomically, without deadlocks.
> >
> >
> > Thanks Heikki. I am still not getting what you said. In the case of
> HOT,
> > you need to update the top pointer to point to some other tuple in some
> > other page. That's one update. what's the other one?
>
> There are several problems, two that come to mind are:
>
> 1) How do you make the dead top pointer redirect to the first live pointer
> in
> the chain? Currently we store the item number of the first live tuple in
> the
> line pointer. You would have to keep the tuple around, though you could
> truncate it to just the tuple header.
>
> 2) When vacuuming how do you find the head of the chain when you're
> looking at
> a dead tuple? There's no space in the tuple header to store the head of
> the
> chain. Besides you want to vacuum scanning sequentially, not randomly.

Thanks for all the inputs. My question would be if we decide to update the
top of the HOT chain in the Index itself. Right now we are carrying a list
of tuple-ids to be vacuumed, when we vacuum the index. Say we carry another
list (or through some better mechanism), which would carry the corresponding
live HOT tuple to be pointed. In other words we would try to make the index
point to the top of the HOT chain during Vacuum.

Am i making some mistake?

--
Thanks,
Gokul.
CertoSQL Project,
Allied Solution Group.
(www.alliedgroups.com)

--
Thanks,
Gokul.
CertoSQL Project,
Allied Solution Group.
(www.alliedgroups.com)

Gokulakannan Somasundaram wrote:
> Thanks for all the inputs. My question would be if we decide to update the
> top of the HOT chain in the Index itself. Right now we are carrying a list
> of tuple-ids to be vacuumed, when we vacuum the index. Say we carry another
> list (or through some better mechanism), which would carry the corresponding
> live HOT tuple to be pointed. In other words we would try to make the index
> point to the top of the HOT chain during Vacuum.

Yeah, we could do that. It was discussed in Spring, along with many
other alternatives. Search the archives for "pointer swinging".

Basically, we decided we can live without it for now. It would've
required quite a bit of changes, for not that much gain. We might still
want it in the future if there's demand for it. If you really need to
recover those 4 bytes per HOT chain, you can use VACUUM FULL, though it
does take an exclusive lock on the table.

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

On 11/5/07, Heikki Linnakangas <heikki(at)enterprisedb(dot)com> wrote:
>
> Gokulakannan Somasundaram wrote:
> > Thanks for all the inputs. My question would be if we decide to update
> the
> > top of the HOT chain in the Index itself. Right now we are carrying a
> list
> > of tuple-ids to be vacuumed, when we vacuum the index. Say we carry
> another
> > list (or through some better mechanism), which would carry the
> corresponding
> > live HOT tuple to be pointed. In other words we would try to make the
> index
> > point to the top of the HOT chain during Vacuum.
>
> Yeah, we could do that. It was discussed in Spring, along with many
> other alternatives. Search the archives for "pointer swinging".
>
> Basically, we decided we can live without it for now. It would've
> required quite a bit of changes, for not that much gain. We might still
> want it in the future if there's demand for it. If you really need to
> recover those 4 bytes per HOT chain, you can use VACUUM FULL, though it
> does take an exclusive lock on the table.

I think pointer swinging is still about maintaining the HOT chain within a
page. Actually i am thinking about continuing the HOT chain across pages.
The advantages are obvious

a) Indexes need not get updated unless their values are updated, even if the
inserts go into new pages
b) Much smaller Index Footprint.

May be i am missing something in the big picture. Please clarify me on that.

--
Thanks,
Gokul.
CertoSQL Project,
Allied Solution Group.
(www.alliedgroups.com)

Gokulakannan Somasundaram wrote:
> I think pointer swinging is still about maintaining the HOT chain within a
> page. Actually i am thinking about continuing the HOT chain across pages.

AFAICS, pointer-swinging would be exactly the same on cross-page HOT
chains as same-page chains.

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

On 11/5/07, Heikki Linnakangas <heikki(at)enterprisedb(dot)com> wrote:
>
> Gokulakannan Somasundaram wrote:
> > I think pointer swinging is still about maintaining the HOT chain within
> a
> > page. Actually i am thinking about continuing the HOT chain across
> pages.
>
> AFAICS, pointer-swinging would be exactly the same on cross-page HOT
> chains as same-page chains.

When i read pointer-swinging, it talks a lot about in-page updates, pointing
to the latest tuple instead of oldest tuple and circular pointers etc.
Maybe, if i am missing the post, which you are referring to, please correct
me on the steps i am talking about.

This scheme, if implemented would avoid the use of HOT stub and avoids the
need to go to index, even if some other indexes are getting updated/ even if
the updated new tuple goes into a new page

a) Whenever we update, we will update only those indexes whose attributes
are updated. So the index will point to the top of the HOT chain.
b) Whenever we Vacuum the index, we take a list of tids and check whether
there are any index tuples pointing to it. If the Vacuumed tuple is a start
of the HOT chain, then we will carry the next in-line HOT tuple when we goto
Vacuum the index. If the next in-line also satisfies the Vacuum, it will
carry with it the next in-line HOT tuple-id.

In this way, we will make sure the Index points to a live tuple after the
Vacuum.

This will remove the in-page pruning exercises, but as i said already the
cost of updates will go down a lot with normal indexes.

Can you please tell, what are the disadvantages of the above mentioned
approach?

--
Thanks,
Gokul.
CertoSQL Project,
Allied Solution Group.
(www.alliedgroups.com)

Gokulakannan Somasundaram wrote:
> On 11/5/07, Heikki Linnakangas <heikki(at)enterprisedb(dot)com> wrote:
>> AFAICS, pointer-swinging would be exactly the same on cross-page HOT
>> chains as same-page chains.
>
> When i read pointer-swinging, it talks a lot about in-page updates, pointing
> to the latest tuple instead of oldest tuple and circular pointers etc.
> Maybe, if i am missing the post, which you are referring to, please correct
> me on the steps i am talking about.

It talks about in-page updates etc, because we are only doing HOT
updates within page. The pointer-swinging would still work across page
boundaries, AFAICS.

> This scheme, if implemented would avoid the use of HOT stub and avoids the
> need to go to index, even if some other indexes are getting updated/ even if
> the updated new tuple goes into a new page

You'd still have the HOT stubs until the next VACUUM.

> a) Whenever we update, we will update only those indexes whose attributes
> are updated. So the index will point to the top of the HOT chain.

I don't see how pointer-swinging would solve the problem with updating
just some indexes. On vacuum, you'd have to know which indexes were
updated, and remove the old pointers in the ones that were updated, and
pointer-swing others. You could store that information in the heap
tuple, but that means more bloat in the heap, and more complexity.

We did talk about that back in spring as well, but all the suggestions
were quite complex. Besides, as soon as you insert at least one new
index pointer, you no longer can remove the dead HOT updated tuple
without scanning at least that one index.

> b) Whenever we Vacuum the index, we take a list of tids and check whether
> there are any index tuples pointing to it. If the Vacuumed tuple is a start
> of the HOT chain, then we will carry the next in-line HOT tuple when we goto
> Vacuum the index. If the next in-line also satisfies the Vacuum, it will
> carry with it the next in-line HOT tuple-id.

Sorry, I didn't understand that. But the way you described it earlier,
it's exactly the same thing as the pointer-swinging we talked about in
spring. Is it the same or not?

> This will remove the in-page pruning exercises, but as i said already the
> cost of updates will go down a lot with normal indexes.

We don't want to get rid of the in-page pruning. It allows us to reclaim
dead space without having to VACUUM. That's a major point of HOT.

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

>
> > b) Whenever we Vacuum the index, we take a list of tids and check
> whether
> > there are any index tuples pointing to it. If the Vacuumed tuple is a
> start
> > of the HOT chain, then we will carry the next in-line HOT tuple when we
> goto
> > Vacuum the index. If the next in-line also satisfies the Vacuum, it will
> > carry with it the next in-line HOT tuple-id.
>
> Sorry, I didn't understand that. But the way you described it earlier,
> it's exactly the same thing as the pointer-swinging we talked about in
> spring. Is it the same or not?

The onle extra overhead is that we will need more memory during Vacuum. We
are currently calling the tid_reaped function / lazy_tid_reaped function. It
does a binary search to check whether the tid pointed by the index, is
present in its array/list. If it is present, it means that it is ready for
Vacuum. For HOT tuples, this list will carry a replacement tid(the next
in-line HOT Tuple). So instead of removing the index tuples, we will update
the tid part of the index tuples. So there is no HOT stub here. The index
will try to point to the live HOT tuple (it would also be the head of the
chain).

Say index was previously pointing to (3,4). After (3,4) gets ready to
Vacuum, it will send a replacement tid, the one in its t_data. say (5,6).

So once the Vacuum identifies the correct Index Tuple, it will update the
tid portion of index tuple to (5,6). Please advise me on whether i am
missing something / not clear in the explanation.

I think i am very poor in understanding things at the first time and also
very poor in putting across my point the very first time. Please bear with
that :)

> This will remove the in-page pruning exercises, but as i said already the
> > cost of updates will go down a lot with normal indexes.
>
> We don't want to get rid of the in-page pruning. It allows us to reclaim
> dead space without having to VACUUM. That's a major point of HOT.

But we are going to get the index sizes very small and also we are going to
reduce the cost of updates. Isn't that sufficient enough reason for us?

--
Thanks,
Gokul.
CertoSQL Project,
Allied Solution Group.
(www.alliedgroups.com)

Gokulakannan Somasundaram wrote:
>>> b) Whenever we Vacuum the index, we take a list of tids and check
>> whether
>>> there are any index tuples pointing to it. If the Vacuumed tuple is a
>> start
>>> of the HOT chain, then we will carry the next in-line HOT tuple when we
>> goto
>>> Vacuum the index. If the next in-line also satisfies the Vacuum, it will
>>> carry with it the next in-line HOT tuple-id.
>> Sorry, I didn't understand that. But the way you described it earlier,
>> it's exactly the same thing as the pointer-swinging we talked about in
>> spring. Is it the same or not?
>
> The onle extra overhead is that we will need more memory during Vacuum. We
> are currently calling the tid_reaped function / lazy_tid_reaped function. It
> does a binary search to check whether the tid pointed by the index, is
> present in its array/list. If it is present, it means that it is ready for
> Vacuum. For HOT tuples, this list will carry a replacement tid(the next
> in-line HOT Tuple). So instead of removing the index tuples, we will update
> the tid part of the index tuples. So there is no HOT stub here. The index
> will try to point to the live HOT tuple (it would also be the head of the
> chain).
>
> Say index was previously pointing to (3,4). After (3,4) gets ready to
> Vacuum, it will send a replacement tid, the one in its t_data. say (5,6).
>
> So once the Vacuum identifies the correct Index Tuple, it will update the
> tid portion of index tuple to (5,6). Please advise me on whether i am
> missing something / not clear in the explanation.

To answer the question I asked you, based on the above, this really is
exactly the same pointer-swinging we talked about in spring.

>> This will remove the in-page pruning exercises, but as i said already the
>>> cost of updates will go down a lot with normal indexes.
>> We don't want to get rid of the in-page pruning. It allows us to reclaim
>> dead space without having to VACUUM. That's a major point of HOT.
>
> But we are going to get the index sizes very small and also we are going to
> reduce the cost of updates. Isn't that sufficient enough reason for us?

No.

You haven't actually explained why you'd have to "remove the in-page
pruning exercises". I suspect that's not true.

Not that any of this really matters, until you address the arguments
against doing HOT updates across pages in the first place.

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

Again Forgot to include the group...

---------- Forwarded message ----------
From: Gokulakannan Somasundaram <gokul007(at)gmail(dot)com>
Date: Nov 5, 2007 5:09 PM
Subject: Re: [HACKERS] Fwd: Clarification about HOT
To: Heikki Linnakangas <heikki(at)enterprisedb(dot)com>

On 11/5/07, Heikki Linnakangas <heikki(at)enterprisedb(dot)com> wrote:
>
> Gokulakannan Somasundaram wrote:
> >>> b) Whenever we Vacuum the index, we take a list of tids and check
> >> whether
> >>> there are any index tuples pointing to it. If the Vacuumed tuple is a
> >> start
> >>> of the HOT chain, then we will carry the next in-line HOT tuple when
> we
> >> goto
> >>> Vacuum the index. If the next in-line also satisfies the Vacuum, it
> will
> >>> carry with it the next in-line HOT tuple-id.
> >> Sorry, I didn't understand that. But the way you described it earlier,
> >> it's exactly the same thing as the pointer-swinging we talked about in
> >> spring. Is it the same or not?
> >
> > The onle extra overhead is that we will need more memory during Vacuum.
> We
> > are currently calling the tid_reaped function / lazy_tid_reaped
> function. It
> > does a binary search to check whether the tid pointed by the index, is
> > present in its array/list. If it is present, it means that it is ready
> for
> > Vacuum. For HOT tuples, this list will carry a replacement tid(the next
> > in-line HOT Tuple). So instead of removing the index tuples, we will
> update
> > the tid part of the index tuples. So there is no HOT stub here. The
> index
> > will try to point to the live HOT tuple (it would also be the head of
> the
> > chain).
> >
> > Say index was previously pointing to (3,4). After (3,4) gets ready to
> > Vacuum, it will send a replacement tid, the one in its t_data. say
> (5,6).
> >
> > So once the Vacuum identifies the correct Index Tuple, it will update
> the
> > tid portion of index tuple to (5,6). Please advise me on whether i am
> > missing something / not clear in the explanation.
>
> To answer the question I asked you, based on the above, this really is
> exactly the same pointer-swinging we talked about in spring.
>
> >> This will remove the in-page pruning exercises, but as i said already
> the
> >>> cost of updates will go down a lot with normal indexes.
> >> We don't want to get rid of the in-page pruning. It allows us to
> reclaim
> >> dead space without having to VACUUM. That's a major point of HOT.
> >
> > But we are going to get the index sizes very small and also we are going
> to
> > reduce the cost of updates. Isn't that sufficient enough reason for us?
>
> No.
>
> You haven't actually explained why you'd have to "remove the in-page
> pruning exercises". I suspect that's not true.

OK. If HOT updates are going to be across pages, we may not know whether we
need to do Pruning, because we don't know whether it is a in-page HOT/
out-of page HOT. May be we can allocate some extra bits for that. I am not
favouring it. That's an option to be tried out.

Not that any of this really matters, until you address the arguments
> against doing HOT updates across pages in the first place.

Yes, but those arguments were centered around the current implementation,
where we have a HOT stub, which will point us to the latest live HOT Tuple.
the two problems which were put forth in this thread are
a) updating two pages concurrently and
Soln: We are just following the current Vacuum process. We are updating the
index tuple tid, instead of reclaiming its space with a Super Exclusive
lock. We will vacuum the heap tuple as usual.

b) we won't know the HOT chain stub tid, when we encounter a HOT dead tuple
Soln: Whenever we find a HOT dead tuple, during vacuum, we will add it to
the list(tid_reaped uses) with the next-in-line HOT Tuple. So when we vacuum
the index, it would be taken care of

i am actually expecting some issues, as this is not a proposal and just a
discussion

--
Thanks,
Gokul.
CertoSQL Project,
Allied Solution Group.
( www.alliedgroups.com)

--
Thanks,
Gokul.
CertoSQL Project,
Allied Solution Group.
(www.alliedgroups.com)

"Gokulakannan Somasundaram" <gokul007(at)gmail(dot)com> writes:
> May be i am missing something in the big picture. Please clarify me on that.

Locking. Your proposal involves lots of multi-page operations, which
are best avoided.

Moreover, you have offered no data to suggest that there would be any
real gain from all this extra complexity.

regards, tom lane

Tom,
Let me try to understand your statement.

What extra multi-page operations are we doing?
Currently, during Vacuum, we goto the Index and mark it as dead and
reclaim the space. For doing this, we are acquiring a Super-Exclusive lock.
After this implementation, we would update the index tuple instead of
marking it for cleanup. What can be foreseen as a locking overhead here?

Actually i don't know what should be the best practice. Should i start a
discussion, take inputs from everyone and start a implementation? (Or)
Should i finish the task, get the performance figures and then come to the
forum?
I realize, that i am doing something wrong here.

HOT in its present implementation has some complexities associated, as it is
dealt as a special case. I saw that you have also made that comment in your
review. The only place where HOT is innovative is in its underlying
assumption
- Since we are not storing the snapshot info into the index, it need not get
updated, if the index info is not changing.

Currently we have implemented in a very limited sense- works only when you
do in-page updates, works only when no index get updated.
It would relish its completeness, if it works across pages and works
treating each index as a seperate entity and makes decisions on updating it
on a index-by-index basis.

By doing this, we will have a rich indexing infrastructure, where thin
indexes are suitable for heavily updated tables and thick indexes would be
suitable for heavily selected tables.

I definitely need guidance from you, before going into its implementation.
So please don't consider this as a proposal. With your experience, try to
gauge the usefulness of this feature. Some small tricks from you to make it
even more effective, would also be very useful.

Thanks,
Gokul.

On 11/5/07, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>
> "Gokulakannan Somasundaram" <gokul007(at)gmail(dot)com> writes:
> > May be i am missing something in the big picture. Please clarify me on
> that.
>
> Locking. Your proposal involves lots of multi-page operations, which
> are best avoided.
>
> Moreover, you have offered no data to suggest that there would be any
> real gain from all this extra complexity.
>
> regards, tom lane
>

--
Thanks,
Gokul.
CertoSQL Project,
Allied Solution Group.
(www.alliedgroups.com)

On Nov 5, 2007 7:37 PM, Gokulakannan Somasundaram <gokul007(at)gmail(dot)com>
wrote:

> Tom,
> Let me try to understand your statement.
>
> What extra multi-page operations are we doing?
> Currently, during Vacuum, we goto the Index and mark it as dead and
> reclaim the space. For doing this, we are acquiring a Super-Exclusive lock.
> After this implementation, we would update the index tuple instead of
> marking it for cleanup. What can be foreseen as a locking overhead here?
>
>
>
Its not just about vacuuming. You need to worry about locking during the
HOT-fetches as well as chain pruning. There could be tricky corner cases
between index/seq scans and pruning. And don't forget CREATE INDEX
which would become even more challenging if you have HOT chains
spanning multiple pages.

This is not to discourage you from trying to improve HOT. But
once-upon-a-time
we had this multi-page HOT (it was called Heap-Overflow-Tuple) and I can
tell you: it was really complex.

Thanks,
Pavan

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

Thanks for the feedback. Let me try to put what is there in my mind for
this. Please clarify whether my assumptions are valid

On 11/5/07, Pavan Deolasee <pavan(dot)deolasee(at)gmail(dot)com> wrote:
>
>
>
> On Nov 5, 2007 7:37 PM, Gokulakannan Somasundaram <gokul007(at)gmail(dot)com>
> wrote:
>
> > Tom,
> > Let me try to understand your statement.
> >
> > What extra multi-page operations are we doing?
> > Currently, during Vacuum, we goto the Index and mark it as dead and
> > reclaim the space. For doing this, we are acquiring a Super-Exclusive lock.
> > After this implementation, we would update the index tuple instead of
> > marking it for cleanup. What can be foreseen as a locking overhead here?
> >
> >
> >
> Its not just about vacuuming. You need to worry about locking during the
> HOT-fetches as well as chain pruning.

During HOT fetches, the normal case is that we will take the tuple-id from
the index, goto the top of HOT chain, descend from there, until we reach the
right tuple. So this would involve BUFFER_SHARE locks which should not be of
any concern. There may not be anything called chain-pruning. Instead the
tuples, which are to be vacuumed, will get vacuumed, after redirecting their
index tuple peers, during the Vacuum process.

There could be tricky corner cases
> between index/seq scans and pruning.

In seq-scans, i think we need not worry about the HOT implementation. we
need to take each tuple, check for the visibility criteria and take the
appropriate step. During clean-up, we will be taking the super exclusive
lock here. In Index scans, we will change the index-entry, only after
obtaining the Super-Exclusive locks - so no pins - so no index scans are
going on during this time

And don't forget CREATE INDEX
> which would become even more challenging if you have HOT chains
> spanning multiple pages.

Create index has to do seq scan. so it will consider only tuples which are
live at the time of creation of index. It won't worry about the HOT chains.

This is not to discourage you from trying to improve HOT. But
> once-upon-a-time
> we had this multi-page HOT (it was called Heap-Overflow-Tuple) and I can
> tell you: it was really complex.

Thanks a lot for the encouraging words. I would definitely refer to the
Heap Overflow Tuple and check, whether there are any problems that are going
to recur in this.

In the mean-while, if you can think of a specific case, in which this design
would fail, please notify me.

--
Thanks,
Gokul.
CertoSQL Project,
Allied Solution Group.
(www.alliedgroups.com)

"Gokulakannan Somasundaram" <gokul007(at)gmail(dot)com> writes:
> Currently, during Vacuum, we goto the Index and mark it as dead and
> reclaim the space. For doing this, we are acquiring a Super-Exclusive lock.
> After this implementation, we would update the index tuple instead of
> marking it for cleanup. What can be foreseen as a locking overhead here?

There are three operations involved: marking the child tuple not-HOT,
updating the index entry(s), and removing the parent tuple. I doubt you
can do them safely as independent atomic operations; I think you'll need
to have more than one page locked at a time. The locking problem also
applies to trying to collapse out a dead HOT tuple that's in the middle
of the chain: if it's the end of a cross-page link then you need two
pages super-exclusive-locked in order to do that.

There's also the little problem that a redirect line pointer doesn't
have room for a cross-page link, and the big problem that having to
chase across multiple pages for an index lookup would almost certainly
negate any performance gains you might get. (In particular it'd
completely destroy locality of access for bitmap indexscans...)

regards, tom lane

On Nov 5, 2007 8:04 PM, Gokulakannan Somasundaram <gokul007(at)gmail(dot)com>
wrote:

>
>
> There may not be anything called chain-pruning. Instead the tuples, which
> are to be vacuumed, will get vacuumed, after redirecting their index tuple
> peers, during the Vacuum process.
>
>

This won't help us check the heap bloat. Though containing index bloat is
important,
most of the performance benefits of HOT comes from doing page level retail
vacuuming.
This not only reduces the heap bloat but also results in less frequent
vacuuming
of the table.

Thanks,
Pavan

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

On 11/5/07, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>
> "Gokulakannan Somasundaram" <gokul007(at)gmail(dot)com> writes:
> > Currently, during Vacuum, we goto the Index and mark it as dead and
> > reclaim the space. For doing this, we are acquiring a Super-Exclusive
> lock.
> > After this implementation, we would update the index tuple instead of
> > marking it for cleanup. What can be foreseen as a locking overhead here?
>
> There are three operations involved: marking the child tuple not-HOT,
> updating the index entry(s), and removing the parent tuple. I doubt you
> can do them safely as independent atomic operations; I think you'll need
> to have more than one page locked at a time.

I think, in my suggestion, there are only two steps, redirect the index
tuple tid to point to a new tuple and mark the parent heap tuple vacuumed.
This is no different from the existing Vacuum process, except that we are
updating the index tuple, instead of marking it for Vacuum . I think you are
thinking about the current implementation. We need not mark any tuple as HOT
in the proposed one. Instead our code will work under the assumption that
normal indexes won't get updated, unless the indexing info changes. i don't
foresee a requirement for HOT classification. Please explain me, if it is
required in any case.

The locking problem also
> applies to trying to collapse out a dead HOT tuple that's in the middle
> of the chain:

Currently, we are maintaining a list/array in the tid_reaped or
lazy_tid_Reaped function. So this will contain all the tids that can be
Vacuumed. In our case,as already explained, all the heap tuples, which are
updated, will contain an extra tid, which is taken from it t_ctid stored in
t_data. So after we update the tid in the index-tuple, we can call
tid_reaped again to check whether the replaced tid has to get replaced / can
be Vacuumed

if it's the end of a cross-page link then you need two
> pages super-exclusive-locked in order to do that.

If the chain ends, the heap tuple would have got marked deleted. it won't
point to any tuple in the t_data and would have got marked HEAP_XMAX_VALID.
So it is the same case as Vacuuming a normal tuple. Have i correctly
answered your question??

There's also the little problem that a redirect line pointer doesn't
> have room for a cross-page link,

i don't know, what is a re-direct line pointer. The tid part of index tuple
can be made to point to any place. So i don't understand what you mean over
here.

and the big problem that having to
> chase across multiple pages for an index lookup would almost certainly
> negate any performance gains you might get. (In particular it'd
> completely destroy locality of access for bitmap indexscans...)

Yes, i think bitmap index scans will get affected, but only for the select
on heavily updated tuples. That's the cost we need to pay for extracting the
performance out of updates. As i already said the normal index would be the
index for heavily updated tables and thick index would be the index for
tables with heavy selects.

We can also look at optimizing the index tuple structure to reduce its
footprint.

Please get back, if i am not clear in any.
--
Thanks,
Gokul.
CertoSQL Project,
Allied Solution Group.
(www.alliedgroups.com)

Gokulakannan Somasundaram wrote:
>> There's also the little problem that a redirect line pointer doesn't
>> have room for a cross-page link,
>
> i don't know, what is a re-direct line pointer.

Then you clearly don't understand at all how HOT works. Please go read
src/backend/access/heap/README.HOT.

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

On 11/5/07, Pavan Deolasee <pavan(dot)deolasee(at)gmail(dot)com> wrote:
>
>
>
> On Nov 5, 2007 8:04 PM, Gokulakannan Somasundaram <gokul007(at)gmail(dot)com>
> wrote:
>
> >
> >
> > There may not be anything called chain-pruning. Instead the tuples,
> > which are to be vacuumed, will get vacuumed, after redirecting their index
> > tuple peers, during the Vacuum process.
> >
> >
>
> This won't help us check the heap bloat. Though containing index bloat is
> important,
> most of the performance benefits of HOT comes from doing page level retail
> vacuuming.
> This not only reduces the heap bloat but also results in less frequent
> vacuuming
> of the table.

Can you please explain this in more detail?
If the HOT chain doesn't break and completely gets into a single page, the
Vacuum daemon need not intervene with the HOT tuples for space reclamation.
But ultimately the space would get reclaimed even with the normal
Vacuum(without HOT Pruning). Isn't it? Then how do we say that without HOT
Pruning, we will have Heap Bloat?

--
Thanks,
Gokul.
CertoSQL Project,
Allied Solution Group.
(www.alliedgroups.com)

Thanks Heikki. To clarify, there won't be any redirect-line pointers in this
implementation. That space is saved. We will have the index tuple point to
the latest live tuple in the update chain. So no need for redirect-line
pointers.

Thanks,
Gokul.

On 11/5/07, Heikki Linnakangas <heikki(at)enterprisedb(dot)com> wrote:
>
> Gokulakannan Somasundaram wrote:
> >> There's also the little problem that a redirect line pointer doesn't
> >> have room for a cross-page link,
> >
> > i don't know, what is a re-direct line pointer.
>
> Then you clearly don't understand at all how HOT works. Please go read
> src/backend/access/heap/README.HOT.
>
> --
> Heikki Linnakangas
> EnterpriseDB http://www.enterprisedb.com
>

--
Thanks,
Gokul.
CertoSQL Project,
Allied Solution Group.
(www.alliedgroups.com)

Gokulakannan Somasundaram wrote:
> Thanks Heikki. To clarify, there won't be any redirect-line pointers in this
> implementation. That space is saved. We will have the index tuple point to
> the latest live tuple in the update chain. So no need for redirect-line
> pointers.

The redirected line pointers are there for a reason. The reason is to be
able to retail vacuum (= prune) a page without having to do a regular
vacuum, scanning all indexes.

If you lose that ability, the idea is dead in the water.

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

On 11/5/07, Heikki Linnakangas <heikki(at)enterprisedb(dot)com> wrote:
>
> Gokulakannan Somasundaram wrote:
> > Thanks Heikki. To clarify, there won't be any redirect-line pointers in
> this
> > implementation. That space is saved. We will have the index tuple point
> to
> > the latest live tuple in the update chain. So no need for redirect-line
> > pointers.
>
> The redirected line pointers are there for a reason. The reason is to be
> able to retail vacuum (= prune) a page without having to do a regular
> vacuum, scanning all indexes.
>
> If you lose that ability, the idea is dead in the water.
>
> --

Since we are going to have the index point to the top of the chain and
sliding the chain happens concurrently with index and heap, there is no need
for redirected line pointers. But i doubt whether we can retail Vacuum a
page since there is just one HOT chain in the page. We can retail Vacuum
only the HOT chain and for the rest of the tuples, which are not HOT
updated, we need to consult with the indexes. Any other tuple in that page
has to go through the normal Vacuum process. Is my understanding correct
here? If so, we don't retail vacuum a page. We just try to shorten the HOT
chain at the expense of some space overhead. If this is going to give so
much benefit, then may be the design can be made slightly flexible in order
to accomodate it.
Say, if we have a table with 4 indexes and updates occur in such intervals,
we may not be able to find space in the same page for the update. Currently
we are incurring the overhead of updating all the indexes in this scenario.
Even if one of the index is updated, we will be incurring the same overhead
again in the current scenario.
In the proposed scenario, we will not have all those overheads. if we feel
that this overhead is required for achieving a pruning of HOT chain, then i
think we should let drop this idea.

Thanks,
Gokul.

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

--
Thanks,
Gokul.
CertoSQL Project,
Allied Solution Group.
(www.alliedgroups.com)

On Mon, Nov 05, 2007 at 09:32:08PM +0530, Gokulakannan Somasundaram wrote:
> Say, if we have a table with 4 indexes and updates occur in such intervals,
> we may not be able to find space in the same page for the update. Currently
> we are incurring the overhead of updating all the indexes in this scenario.
> Even if one of the index is updated, we will be incurring the same overhead
> again in the current scenario.

Ok, I've been following this tangentially, but here is one thing I
really don't understand: Sure, you might save this cost during update,
but you do incur this cost while updating the head of the chain. There
is no link from the chain to the index tuple, so the work to find the
current index tuple is nearly the same as the cost to create a new one.

It seems to me that updating and pruning the head will happen about
equally often, so I'm not sure you're saving anything here. Or am I
missing something?

Have a nice day,
--
Martijn van Oosterhout <kleptog(at)svana(dot)org> http://svana.org/kleptog/
> Those who make peaceful revolution impossible will make violent revolution inevitable.
> -- John F Kennedy

On 11/5/07, Martijn van Oosterhout <kleptog(at)svana(dot)org> wrote:
>
> On Mon, Nov 05, 2007 at 09:32:08PM +0530, Gokulakannan Somasundaram wrote:
> > Say, if we have a table with 4 indexes and updates occur in such
> intervals,
> > we may not be able to find space in the same page for the update.
> Currently
> > we are incurring the overhead of updating all the indexes in this
> scenario.
> > Even if one of the index is updated, we will be incurring the same
> overhead
> > again in the current scenario.
>
> Ok, I've been following this tangentially, but here is one thing I
> really don't understand: Sure, you might save this cost during update,
> but you do incur this cost while updating the head of the chain. There
> is no link from the chain to the index tuple, so the work to find the
> current index tuple is nearly the same as the cost to create a new one.
>
> It seems to me that updating and pruning the head will happen about
> equally often, so I'm not sure you're saving anything here. Or am I
> missing something?

Whatever you just said will happen during the index Vacuum. Instead of
marking a particular tuple as Dead/ ready to be Vacuumed, we will update its
tid to point to the tuple which is next to the head of the chain. This won't
incur extra overhead, except that during the Vacuum process we will carry
the tid of the tuple, which is next to the head of the chain(a memory
overhead).

Hope , i was clear. Please get back, in case you haven't understood.

--
Thanks,
Gokul.
CertoSQL Project,
Allied Solution Group.
(www.alliedgroups.com)