SEO

Martijn van Oosterhout wrote:
-- Start of PGP signed section.
> On Mon, Jun 26, 2006 at 07:17:31AM -0400, Bruce Momjian wrote:
> > Correct! We use the same pointers used by normal UPDATEs, except we set
> > a bit on the old tuple indicating it is a single-index tuple, and we
> > don't create index entries for the new tuple. Index scan routines will
> > need to be taught about the new chains, but because only one tuple in
> > the chain is visible to a single backend, the callers should not need to
> > be modified.
>
> I suppose we would also change the index_getmulti() function to return
> a set of ctids plus flags so the caller knows to follow the chains,
> right? And for bitmap index scans you would only remember the page in
> the case of such a tuple, since you can't be sure the exact ctid you've
> got is the one you want.
>
> Seems doable.

Yes, it just is an issue of where you want to add the complexity ---
scan entire page when no free space, or only an UPDATE.

--
Bruce Momjian bruce@momjian.us
EnterpriseDB http://www.enterprisedb.com

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

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

Bruce Momjian wrote:
> Martijn van Oosterhout wrote:
> -- Start of PGP signed section.
> > On Mon, Jun 26, 2006 at 07:17:31AM -0400, Bruce Momjian wrote:
> > > Correct! We use the same pointers used by normal UPDATEs, except we set
> > > a bit on the old tuple indicating it is a single-index tuple, and we
> > > don't create index entries for the new tuple. Index scan routines will
> > > need to be taught about the new chains, but because only one tuple in
> > > the chain is visible to a single backend, the callers should not need to
> > > be modified.
> >
> > I suppose we would also change the index_getmulti() function to return
> > a set of ctids plus flags so the caller knows to follow the chains,
> > right? And for bitmap index scans you would only remember the page in
> > the case of such a tuple, since you can't be sure the exact ctid you've
> > got is the one you want.
> >
> > Seems doable.
>
> Yes, it just is an issue of where you want to add the complexity ---
> scan entire page when no free space, or only an UPDATE.

Oh, and because you want to do this when doing an update via sequential
scan as well as an index scan, I am thinking you might need to do the
per-page method because you might not have even seen the head of the
chain yet. With an index scan, finding the head is easy, but for a
sequential scan, it seems more difficult, and we don't have any free
space in the tail of the chain to maintain a pointer to the head.

--
Bruce Momjian bruce@momjian.us
EnterpriseDB http://www.enterprisedb.com

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

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

Bruce Momjian wrote:
> Bruce Momjian wrote:
> > Martijn van Oosterhout wrote:
> > -- Start of PGP signed section.
> > > On Mon, Jun 26, 2006 at 07:17:31AM -0400, Bruce Momjian wrote:
> > > > Correct! We use the same pointers used by normal UPDATEs, except we set
> > > > a bit on the old tuple indicating it is a single-index tuple, and we
> > > > don't create index entries for the new tuple. Index scan routines will
> > > > need to be taught about the new chains, but because only one tuple in
> > > > the chain is visible to a single backend, the callers should not need to
> > > > be modified.
> > >
> > > I suppose we would also change the index_getmulti() function to return
> > > a set of ctids plus flags so the caller knows to follow the chains,
> > > right? And for bitmap index scans you would only remember the page in
> > > the case of such a tuple, since you can't be sure the exact ctid you've
> > > got is the one you want.
> > >
> > > Seems doable.
> >
> > Yes, it just is an issue of where you want to add the complexity ---
> > scan entire page when no free space, or only an UPDATE.
>
> Oh, and because you want to do this when doing an update via sequential
> scan as well as an index scan, I am thinking you might need to do the
> per-page method because you might not have even seen the head of the
> chain yet. With an index scan, finding the head is easy, but for a
> sequential scan, it seems more difficult, and we don't have any free
> space in the tail of the chain to maintain a pointer to the head.

Thinking some more, there will need to be a bit to uniquely identify the
head of a CITC. With that, you could just scan the page tuples looking
for CITC heads, and checking those to see if they are not visible, and
re-using them, rather than doing a full page reorganization where all
free spaces is collected in the middle of the page. That should limit
the overhead of reuse.

--
Bruce Momjian bruce@momjian.us
EnterpriseDB http://www.enterprisedb.com

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

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

There were some talks lately about compression.
With a bit of lateral thinking I guess this can be used to contain the
bloat induced by updates.
Of course this is just my hypothesis.

Compression in indexes :

Instead of storing (value, tuple identifier) keys in the indexes, store
(value, [tuple identifier list]) ; ie. all tuples which have the same
indexed value are referenced by the same index tuple, instead of having
one index tuple per actual tuple.
The length of the list would of course be limited to the space actually
available on an index page ; if many rows have the same indexed value,
several index tuples would be generated so that index tuples fit on index
pages.
This would make the index smaller (more likely to fit in RAM) at the cost
of a little CPU overhead for index modifications, but would make the index
scans actually use less CPU (no need to compare the indexed value on each
table tuple).

Compression in data pages :

The article that circulated on the list suggested several types of
compression, offset, dictionary, etc. The point is that several row
versions on the same page can be compressed well because these versions
probably have similar column values.

Just a thought...

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

PFC wrote:
>
> There were some talks lately about compression.
> With a bit of lateral thinking I guess this can be used to contain the
> bloat induced by updates.
> Of course this is just my hypothesis.
>
> Compression in indexes :
>
> Instead of storing (value, tuple identifier) keys in the indexes, store
> (value, [tuple identifier list]) ; ie. all tuples which have the same
> indexed value are referenced by the same index tuple, instead of having
> one index tuple per actual tuple.
> The length of the list would of course be limited to the space actually
> available on an index page ; if many rows have the same indexed value,
> several index tuples would be generated so that index tuples fit on index
> pages.
> This would make the index smaller (more likely to fit in RAM) at the cost
> of a little CPU overhead for index modifications, but would make the index
> scans actually use less CPU (no need to compare the indexed value on each
> table tuple).

What about increasing the size of an existing index entry? Can that be
done easily when a new row is added?

> Compression in data pages :
>
> The article that circulated on the list suggested several types of
> compression, offset, dictionary, etc. The point is that several row
> versions on the same page can be compressed well because these versions
> probably have similar column values.
>
> Just a thought...

I would be worried about the overhead of doing that on compression and
decompression.

--
Bruce Momjian bruce@momjian.us
EnterpriseDB http://www.enterprisedb.com

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

---------------------------(end of broadcast)---------------------------
TIP 9: In versions below 8.0, the planner will ignore your desire to
choose an index scan if your joining column's datatypes do not
match

> What about increasing the size of an existing index entry? Can that be
> done easily when a new row is added?

I'd say it looks pretty much like inserting a new index tuple...
Say "value" is the indexed column.

Find first page in the index featuring "value".
1 If there is space on the page,
add the tuple id to the list of the corresponding index entry (just like
creating a new index tuple, but uses less space).
else
look at next page.
If next page has an index tuple with the same indexed value,
goto 1
else
insert new page and create an index tuple on it

> I would be worried about the overhead of doing that on compression and
> decompression.

The compression methods mentioned in the article which was passed on the
list seemed pretty fast. From IO-limited, the test database became
CPU-limited (and a lot faster).


---------------------------(end of broadcast)---------------------------
TIP 9: In versions below 8.0, the planner will ignore your desire to
choose an index scan if your joining column's datatypes do not
match

> > head of the chain yet. With an index scan, finding the head is
easy,
> > but for a sequential scan, it seems more difficult, and we don't
have
> > any free space in the tail of the chain to maintain a pointer to the
head.
>
> Thinking some more, there will need to be a bit to uniquely
> identify the head of a CITC.

I don't think so. It would probably be sufficient to impose an order on
the CITC.
e.g. the oldest tuple version in the CITC is the head.
(An idea just in case we can't spare a bit :-)

Andreas

---------------------------(end of broadcast)---------------------------
TIP 9: In versions below 8.0, the planner will ignore your desire to
choose an index scan if your joining column's datatypes do not
match

Zeugswetter Andreas DCP SD wrote:
>
> > > head of the chain yet. With an index scan, finding the head is
> easy,
> > > but for a sequential scan, it seems more difficult, and we don't
> have
> > > any free space in the tail of the chain to maintain a pointer to the
> head.
> >
> > Thinking some more, there will need to be a bit to uniquely
> > identify the head of a CITC.
>
> I don't think so. It would probably be sufficient to impose an order on
> the CITC.
> e.g. the oldest tuple version in the CITC is the head.
> (An idea just in case we can't spare a bit :-)

Well, if we need to scan the page quickly, having the bit, or a bit
combination that can only be the head, is helpful. What we usually do
is to combine a SITC bit with another bit that would never be set for
SITC, and that is the head, and you use macros to properly do tests. We
do this already in a number of cases.

--
Bruce Momjian bruce@momjian.us
EnterpriseDB http://www.enterprisedb.com

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

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