Thread: 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. 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>)
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
On 11/2/07, Martijn van Oosterhout <kleptog@svana.org> 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.
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.
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)
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@enterprisedb.com > 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?
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@svana.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@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
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>
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)
---------- 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:
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.
"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.
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@enterprisedb.com> 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. 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.
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@enterprisedb.com> wrote:
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.
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.
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@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
> 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@gmail.com >
Date: Nov 5, 2007 5:09 PM
Subject: Re: [HACKERS] Fwd: Clarification about HOT
To: Heikki Linnakangas <heikki@enterprisedb.com>
--
Thanks,
Gokul.
CertoSQL Project,
Allied Solution Group.
( www.alliedgroups.com)
--
Thanks,
Gokul.
CertoSQL Project,
Allied Solution Group.
(www.alliedgroups.com)
---------- 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:
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.
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
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@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
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.
--
Thanks,
Gokul.
CertoSQL Project,
Allied Solution Group.
(www.alliedgroups.com)
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)
<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>
Thanks for the feedback. Let me try to put what is there in my mind for this. Please clarify whether my assumptions are valid
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)
On 11/5/07, Pavan Deolasee <pavan.deolasee@gmail.com> wrote:
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.
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
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.
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.
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)
"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
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
On 11/5/07, Tom Lane <tgl@sss.pgh.pa.us> wrote:
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.
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 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??
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.
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.
"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)
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.deolasee@gmail.com> wrote:
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?
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)
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.
--
Thanks,
Gokul.
CertoSQL Project,
Allied Solution Group.
(www.alliedgroups.com)
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)
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@enterprisedb.com> wrote:
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.
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@svana.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@svana.org> wrote:
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.
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)