I am thinking that maintaining fragmented free space within a heap page
might be a good idea. It would help us to reuse the free space ASAP without
waiting for a vacuum run on the page. This in turn will lead to lesser heap
bloats and also increase the probability of placing updated tuple in the
same heap page as the original one.

So during a sequential or index scan, if a tuple is found to be dead, the
corresponding line pointer is marked "unused" and the space is returned to a
free list. This free list is maintained within the page. A linked-list can
be used for this purpose and the special area of the heap-page can be used
to track the fragment list. We can maintain some additional information
about the fragmented space such as, total_free_space, max_fragment_size,
num_of_fragments etc in the special area.

During UPDATEs, if we find that there is no free space in the block, the
fragment list is searched (either first-fit or best-fit), the required space
is consumed and the remaining space is returned to the free list.

We might not be able to reuse the line pointers because indexes may have
references to it. All such line pointers will be freed when the page is
vacuumed during the regular vacuum.

Thanks,
Pavan

EnterpriseDB http://www.enterprisedb.com

On Tue, Jan 23, 2007 at 01:48:08PM +0530, Pavan Deolasee wrote:
> I am thinking that maintaining fragmented free space within a heap page
> might be a good idea. It would help us to reuse the free space ASAP without
> waiting for a vacuum run on the page. This in turn will lead to lesser heap
> bloats and also increase the probability of placing updated tuple in the
> same heap page as the original one.

<snip>

Nice idea but:

> We might not be able to reuse the line pointers because indexes may have
> references to it. All such line pointers will be freed when the page is
> vacuumed during the regular vacuum.

The overwhelming vast majoirty of tuples are going to be in one or more
indexes. Which means nearly all tuples are going to fall into this
category. So where's the benefit?

Have a nice day,
--
Martijn van Oosterhout <kleptog@svana.org> http://svana.org/kleptog/
> From each according to his ability. To each according to his ability to litigate.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFFtcvuIB7bNG8LQkwRAsDLAJ4sPvR9jbe02jlNNN2zqH bovZGnDgCeMYHU
weocjbIYcVic+o3bx4TbJF8=
=2uHt
-----END PGP SIGNATURE-----

On 1/23/07, Martijn van Oosterhout <kleptog@svana.org> wrote:
>
> On Tue, Jan 23, 2007 at 01:48:08PM +0530, Pavan Deolasee wrote:
>
> > We might not be able to reuse the line pointers because indexes may have
> > references to it. All such line pointers will be freed when the page is
> > vacuumed during the regular vacuum.
>
> The overwhelming vast majoirty of tuples are going to be in one or more
> indexes. Which means nearly all tuples are going to fall into this
> category. So where's the benefit?


The line pointers can not reused, but the space consumed by the tuple can
be.
So the benefit is in utilizing that space for newer tuples and thus reduce
the
bloat.

One assumption I am making here is that its sufficient to mark the line
pointer
"unused" (reset LP_USED flag) even though there is an index entry pointing
to
the tuple. During index scan, we anyways check for ItemIdIsUsed() before
proceeding further. I know it might break the ctid chain, but does that
really
matter ? I don't see any reason why somebody would need to follow ctid chain
past a dead tuple.

Thanks,
Pavan

EnterpriseDB http://www.enterprisedb.com

"Pavan Deolasee" <pavan.deolasee@gmail.com> wrote:

> > The overwhelming vast majoirty of tuples are going to be in one or more
> > indexes. Which means nearly all tuples are going to fall into this
> > category. So where's the benefit?
>
> The line pointers can not reused, but the space consumed by the tuple can be.
> So the benefit is in utilizing that space for newer tuples and thus reduce the
> bloat.

I think your idea is same as the following TODO Item, that I suggested before.

* Consider shrinking expired tuples to just their headers.
http://archives.postgresql.org/pgsql...3/msg00142.php
http://archives.postgresql.org/pgsql...3/msg00166.php


> One assumption I am making here is that its sufficient to mark the line pointer
> "unused" (reset LP_USED flag) even though there is an index entry pointing to
> the tuple. During index scan, we anyways check for ItemIdIsUsed() before
> proceeding further. I know it might break the ctid chain, but does that really
> matter ? I don't see any reason why somebody would need to follow ctid chain
> past a dead tuple.

Keeping only line pointers itself is not a problem, but it might lead
bloating of line pointers. If a particular tuple in a page is replaced
repeatedly, the line pointers area bloats up to 1/4 of the page.
We need to work around the problem.

Regards,
---
ITAGAKI Takahiro
NTT Open Source Software Center



---------------------------(end of broadcast)---------------------------
TIP 2: Don't 'kill -9' the postmaster

Pavan Deolasee wrote:
> One assumption I am making here is that its sufficient to mark the line
> pointer
> "unused" (reset LP_USED flag) even though there is an index entry pointing
> to
> the tuple. During index scan, we anyways check for ItemIdIsUsed() before
> proceeding further. I know it might break the ctid chain, but does that
> really
> matter ? I don't see any reason why somebody would need to follow ctid
> chain
> past a dead tuple.

You can't clear the LP_USED flag, but you could use the LP_DELETE flag
that's currently not used in heap pages.

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

---------------------------(end of broadcast)---------------------------
TIP 5: don't forget to increase your free space map settings

Pavan Deolasee wrote:
> I am thinking that maintaining fragmented free space within a heap page
> might be a good idea. It would help us to reuse the free space ASAP without
> waiting for a vacuum run on the page. This in turn will lead to lesser heap
> bloats and also increase the probability of placing updated tuple in the
> same heap page as the original one.

Agreed.

> So during a sequential or index scan, if a tuple is found to be dead, the
> corresponding line pointer is marked "unused" and the space is returned
> to a
> free list. This free list is maintained within the page. A linked-list can
> be used for this purpose and the special area of the heap-page can be used
> to track the fragment list. We can maintain some additional information
> about the fragmented space such as, total_free_space, max_fragment_size,
> num_of_fragments etc in the special area.

Maintaining a list like that seems like a lot of hassle to me. Instead,
you could just scan the line pointers looking for a dead tuple of the
right size. We already have to scan the line pointers when inserting to
find a free line pointer.

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

---------------------------(end of broadcast)---------------------------
TIP 1: if posting/reading through Usenet, please send an appropriate
subscribe-nomail command to majordomo@postgresql.org so that your
message can get through to the mailing list cleanly

ITAGAKI Takahiro wrote:
> "Pavan Deolasee" <pavan.deolasee@gmail.com> wrote:
>
>>> The overwhelming vast majoirty of tuples are going to be in one or more
>>> indexes. Which means nearly all tuples are going to fall into this
>>> category. So where's the benefit?
>> The line pointers can not reused, but the space consumed by the tuple can be.
>> So the benefit is in utilizing that space for newer tuples and thus reduce the
>> bloat.
>
> I think your idea is same as the following TODO Item, that I suggested before.
>
> * Consider shrinking expired tuples to just their headers.
> http://archives.postgresql.org/pgsql...3/msg00142.php
> http://archives.postgresql.org/pgsql...3/msg00166.php

Yeah, same idea. You suggested in that thread that we should keep the
headers because of line pointer bloat, but I don't see how that's
better. You're still going to get some line pointer bloat, but not able
to reclaim as much free space.

In that thread, Tom mentioned that we may need to keep the header
because the dead tuple might be part of an update chain. Reading back
the discussion on the vacuum bug, I can't see how removing the header
would be a problem, but maybe I'm missing something.

>> One assumption I am making here is that its sufficient to mark the line pointer
>> "unused" (reset LP_USED flag) even though there is an index entry pointing to
>> the tuple. During index scan, we anyways check for ItemIdIsUsed() before
>> proceeding further. I know it might break the ctid chain, but does that really
>> matter ? I don't see any reason why somebody would need to follow ctid chain
>> past a dead tuple.
>
> Keeping only line pointers itself is not a problem, but it might lead
> bloating of line pointers. If a particular tuple in a page is replaced
> repeatedly, the line pointers area bloats up to 1/4 of the page.

Where does the 1/4 figure come from?

> We need to work around the problem.

If a row is updated many times until vacuum comes along, what currently
happens is that we end up with a bunch of pages full of dead tuples.
With the truncation scheme, we could fit way more dead tuples on each
page, reducing the need to vacuum. If a row is for example 40 bytes
long, including header (a quite narrow one), you could fit 10 line
pointers to the space of one row, which means that you could ideally
multiply your vacuum interval by a factor of 10x. That's a huge benefit,
though indexes would still bloat unless selects marking index pointers
as dead keep the bloat in control.

The problem is that if a tuple is updated say hundreds of times before
vacuum, but then it's not updated anymore, you'll have a page full of
useless line pointers that are not reclaimed. Clearly we should start
reclaiming line pointers, but we can only do that for unused line
pointers after the last used one.

Would it be enough cap the number of dead line pointers with a simple
rule like "max 20% of line pointers can be dead"? I'd be happy with that.

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

---------------------------(end of broadcast)---------------------------
TIP 6: explain analyze is your friend

On 1/23/07, Heikki Linnakangas <heikki@enterprisedb.com> wrote:
>
> ITAGAKI Takahiro wrote:
>
> > Keeping only line pointers itself is not a problem, but it might lead
> > bloating of line pointers. If a particular tuple in a page is replaced
> > repeatedly, the line pointers area bloats up to 1/4 of the page.
>
> Where does the 1/4 figure come from?
>
> > We need to work around the problem.
>
> If a row is updated many times until vacuum comes along, what currently
> happens is that we end up with a bunch of pages full of dead tuples.
> With the truncation scheme, we could fit way more dead tuples on each
> page, reducing the need to vacuum. If a row is for example 40 bytes
> long, including header (a quite narrow one), you could fit 10 line
> pointers to the space of one row, which means that you could ideally
> multiply your vacuum interval by a factor of 10x. That's a huge benefit,
> though indexes would still bloat unless selects marking index pointers
> as dead keep the bloat in control.
>
> The problem is that if a tuple is updated say hundreds of times before
> vacuum, but then it's not updated anymore, you'll have a page full of
> useless line pointers that are not reclaimed. Clearly we should start
> reclaiming line pointers, but we can only do that for unused line
> pointers after the last used one.
>
>
I thought that we can not reclaim the line pointers unless we remove the
corresponding index entries as well. Isn't that the case ? If so, how would
we reclaim the line pointers after the last used one ?

Thanks,
Pavan

EnterpriseDB http://www.enterprisedb.com

On 1/23/07, Heikki Linnakangas <heikki@enterprisedb.com> wrote:
>
> Pavan Deolasee wrote:
>
> > So during a sequential or index scan, if a tuple is found to be dead,
> the
> > corresponding line pointer is marked "unused" and the space is returned
> > to a
> > free list. This free list is maintained within the page. A linked-list
> can
> > be used for this purpose and the special area of the heap-page can be
> used
> > to track the fragment list. We can maintain some additional information
> > about the fragmented space such as, total_free_space, max_fragment_size,
> > num_of_fragments etc in the special area.
>
> Maintaining a list like that seems like a lot of hassle to me. Instead,
> you could just scan the line pointers looking for a dead tuple of the
> right size. We already have to scan the line pointers when inserting to
> find a free line pointer.


That's a good suggestion. Just to avoid useless scans when there is no
fragment which can accommodate the new tuple, we may have some book keeping
information in the special area though.

Thanks,
Pavan

EnterpriseDB http://www.enterprisedb.com

Heikki Linnakangas <heikki@enterprisedb.com> wrote:

> > * Consider shrinking expired tuples to just their headers.
>
> Yeah, same idea. You suggested in that thread that we should keep the
> headers because of line pointer bloat, but I don't see how that's
> better. You're still going to get some line pointer bloat, but not able
> to reclaim as much free space.

That is not an essential solution, as you are aware. I think it will be
better to combine tuple shrinking and other restrictions of LP area.

> > Keeping only line pointers itself is not a problem, but it might lead
> > bloating of line pointers. If a particular tuple in a page is replaced
> > repeatedly, the line pointers area bloats up to 1/4 of the page.
>
> Where does the 1/4 figure come from?

BLCKSZ is typically 8192 bytes and sizeof(ItemPointerData) is 4 bytes.
1/4 comes from 8192 / 4 = 2048. If we allow zero-size tuples, the line
pointers area can bloat up to the ratio. We have tuples no less than
32 bytes-size, so the area is restricted 256 bytes now.


> The problem is that if a tuple is updated say hundreds of times before
> vacuum, but then it's not updated anymore, you'll have a page full of
> useless line pointers that are not reclaimed. Clearly we should start
> reclaiming line pointers, but we can only do that for unused line
> pointers after the last used one.

We can recycle unused line pointers, but we cannot shrink the area unless
the tail end of line pointers are removed. i.e, unusable free space will
remains at the middle of LP area.

[used lp][***unusable free space***][used lp] [free space] [heap tuples]

> Would it be enough cap the number of dead line pointers with a simple
> rule like "max 20% of line pointers can be dead"? I'd be happy with that.

Yeah, I think it is enough, too. It might be a signal of vacuum.

Regards,
---
ITAGAKI Takahiro
NTT Open Source Software Center



---------------------------(end of broadcast)---------------------------
TIP 7: You can help support the PostgreSQL project by donating at

http://www.postgresql.org/about/donate