Thread: Clarification about HOT

Clarification about HOT

From
"Gokulakannan Somasundaram"
Date:
I went through the README on HOT. That was really a nice and cool feature. Hats off to the person who thought about it.
Ihave a couple of doubts about it.<br /><br />a) In the README, there is a statement like this. <br clear="all"
/><pre>Inprinciple we could continue a HOT chain across<br />pages, but this would destroy the desired property of
beingable to<br />reclaim space with just page-local manipulations.  Anyway, we don't<br />want to have to chase
throughmultiple heap pages to get from an index
 
<br />entry to the desired tuple, so it seems better to create a new index<br />entry for the new tuple.<br /></pre><br
/>Iam 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
targetentry.Is this the only reason, it was left out?<br /><br /><br />-- <br />Thanks,<br />Gokul.<br />CertoSQL
Project,<br/>Allied Solution Group.<br />(<a href="http://www.alliedgroups.com">www.alliedgroups.com</a>)  

Re: Clarification about HOT

From
Martijn van Oosterhout
Date:
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@svana.org>   http://svana.org/kleptog/
> Those who make peaceful revolution impossible will make violent revolution inevitable.
>  -- John F Kennedy

Re: Clarification about HOT

From
"Gokulakannan Somasundaram"
Date:


On 11/2/07, Martijn van Oosterhout <kleptog@svana.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.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.

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)

Re: Clarification about HOT

From
Heikki Linnakangas
Date:
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


Re: Clarification about HOT

From
"Gokulakannan Somasundaram"
Date:


On 11/2/07, Heikki Linnakangas <heikki@enterprisedb.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)

Re: Clarification about HOT

From
Martijn van Oosterhout
Date:
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@svana.org>   http://svana.org/kleptog/
> Those who make peaceful revolution impossible will make violent revolution inevitable.
>  -- John F Kennedy

Re: Clarification about HOT

From
Heikki Linnakangas
Date:
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


Re: Clarification about HOT

From
Gregory Stark
Date:
"Gokulakannan Somasundaram" <gokul007@gmail.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


Fwd: Clarification about HOT

From
"Gokulakannan Somasundaram"
Date:
Forgot to include the group...



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



On 11/2/07, Gregory Stark <stark@enterprisedb.com> wrote:

"Gokulakannan Somasundaram" <gokul007@gmail.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)

Re: Fwd: Clarification about HOT

From
Heikki Linnakangas
Date:
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


Re: Fwd: Clarification about HOT

From
"Gokulakannan Somasundaram"
Date:


On 11/5/07, Heikki Linnakangas <heikki@enterprisedb.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)

Re: Fwd: Clarification about HOT

From
Heikki Linnakangas
Date:
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


Re: Fwd: Clarification about HOT

From
"Gokulakannan Somasundaram"
Date:


On 11/5/07, Heikki Linnakangas <heikki@enterprisedb.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)

Re: Fwd: Clarification about HOT

From
Heikki Linnakangas
Date:
Gokulakannan Somasundaram wrote:
> On 11/5/07, Heikki Linnakangas <heikki@enterprisedb.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


Re: Fwd: Clarification about HOT

From
"Gokulakannan Somasundaram"
Date:


> 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)

Re: Fwd: Clarification about HOT

From
Heikki Linnakangas
Date:
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


Fwd: Fwd: Clarification about HOT

From
"Gokulakannan Somasundaram"
Date:
Again Forgot to include the group...

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



On 11/5/07, Heikki Linnakangas < heikki@enterprisedb.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)

Re: Fwd: Clarification about HOT

From
Tom Lane
Date:
"Gokulakannan Somasundaram" <gokul007@gmail.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


Re: Fwd: Clarification about HOT

From
"Gokulakannan Somasundaram"
Date:
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@sss.pgh.pa.us> wrote:
"Gokulakannan Somasundaram" <gokul007@gmail.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)

Re: Fwd: Clarification about HOT

From
"Pavan Deolasee"
Date:
<br /><br /><div class="gmail_quote">On Nov 5, 2007 7:37 PM, Gokulakannan Somasundaram <<a
href="mailto:gokul007@gmail.com">gokul007@gmail.com</a>>wrote:<br /><blockquote class="gmail_quote"
style="border-left:1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"> Tom, <br />       Let
metry to understand your statement.<br /><br />What extra multi-page operations are we doing? <br />  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
asa locking overhead here? <br /><br /><br /></blockquote></div><br />Its not just about vacuuming. You need to worry
aboutlocking during the<br />HOT-fetches as well as chain pruning. There could be tricky corner cases<br />between
index/seqscans and pruning. And don't forget CREATE INDEX <br />which would become even more challenging if you have
HOTchains<br />spanning multiple pages.<br /><br />This is not to discourage you from trying to improve HOT. But
once-upon-a-time<br/>we had this multi-page HOT (it was called Heap-Overflow-Tuple) and I can <br />tell you: it was
reallycomplex.<br clear="all" /><br /><br />Thanks,<br />Pavan<br /><br />-- <br />Pavan Deolasee<br />EnterpriseDB    
<ahref="http://www.enterprisedb.com">http://www.enterprisedb.com</a> 

Re: Fwd: Clarification about HOT

From
"Gokulakannan Somasundaram"
Date:
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.deolasee@gmail.com> wrote:


On Nov 5, 2007 7:37 PM, Gokulakannan Somasundaram <gokul007@gmail.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)

Re: Fwd: Clarification about HOT

From
Tom Lane
Date:
"Gokulakannan Somasundaram" <gokul007@gmail.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


Re: Fwd: Clarification about HOT

From
"Pavan Deolasee"
Date:


On Nov 5, 2007 8:04 PM, Gokulakannan Somasundaram <gokul007@gmail.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

Re: Fwd: Clarification about HOT

From
"Gokulakannan Somasundaram"
Date:


On 11/5/07, Tom Lane <tgl@sss.pgh.pa.us> wrote:
"Gokulakannan Somasundaram" <gokul007@gmail.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)

Re: Fwd: Clarification about HOT

From
Heikki Linnakangas
Date:
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


Re: Fwd: Clarification about HOT

From
"Gokulakannan Somasundaram"
Date:


On 11/5/07, Pavan Deolasee <pavan.deolasee@gmail.com> wrote:


On Nov 5, 2007 8:04 PM, Gokulakannan Somasundaram <gokul007@gmail.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)

Re: Fwd: Clarification about HOT

From
"Gokulakannan Somasundaram"
Date:
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@enterprisedb.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)

Re: Fwd: Clarification about HOT

From
Heikki Linnakangas
Date:
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


Re: Fwd: Clarification about HOT

From
"Gokulakannan Somasundaram"
Date:


On 11/5/07, Heikki Linnakangas <heikki@enterprisedb.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)

Re: Fwd: Clarification about HOT

From
Martijn van Oosterhout
Date:
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@svana.org>   http://svana.org/kleptog/
> Those who make peaceful revolution impossible will make violent revolution inevitable.
>  -- John F Kennedy

Re: Fwd: Clarification about HOT

From
"Gokulakannan Somasundaram"
Date:


On 11/5/07, Martijn van Oosterhout <kleptog@svana.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)