SEO

This is the second proposal for Dead Space Map (DSM).
Here is the previous discussion:
http://archives.postgresql.org/pgsql...2/msg01188.php

I'll post the next version of the Dead Space Map patch to -patches.
I've implemented 2bits/page bitmap and new vacuum commands.
Memory management and recovery features are not done yet.

I think it's better to get DSM and HOT together. DSM is good at complex
updated cases but not at heavily updated cases. HOT has opposite aspects,
as far as I can see. I think they can cover each other.


2bits/page bitmap
-----------------

Each heap pages have 4 states for dead space map; HIGH, LOW, UNFROZEN and
FROZEN. VACUUM uses the states to reduce the number of target pages.

- HIGH : High priority to vacuum. Maybe many dead tuples in the page.
- LOW : Low priority to vacuum Maybe few dead tuples in the page.
- UNFROZEN : No dead tuples, but some unfrozen tuples in the page.
- FROZEN : No dead nor unfrozen tuples in the page.

If we do UPDATE a tuple, the original page containing the tuple is marked
as HIGH and the new page where the updated tuple is placed is marked as LOW.
When we commit the transaction, the updated tuples needs only FREEZE.
That's why the after-page is marked as LOW. However, If we rollback, the
after-page should be vacuumed, so we should mark the page LOW, not UNFROZEN.
We don't know the transaction will commit or rollback at the UPDATE.

If we combine this with the HOT patch, pages with HOT tuples are probably
marked as UNFROZEN because we don't bother vacuuming HOT tuples. They can
be removed incrementally and doesn't require explicit vacuums.

In future work, we can do index-only-scan for tuples that is in UNFROZEN or
FROZEN pages. (currently not implemented)


VACUUM commands
---------------

VACUUM now only scans the pages that possibly have dead tuples.
VACUUM ALL, a new syntax, behaves as the same as before.

- VACUUM FULL : Not changed. scans all pages and compress them.
- VACUUM ALL : Scans all pages; Do the same behavior as previous VACUUM.
- VACUUM : Scans only HIGH pages usually, but also LOW and UNFROZEN
pages on vacuums in the cases for preventing XID wraparound.

The commitment of oldest XID for VACUUM is not changed. There should not be
tuples that XIDs are older than (Current XID - vacuum_freeze_min_age) after
VACUUM. If the VACUUM can guarantee the commitment, it scans only HIGH pages.
Otherwise, it scans HIGH, LOW and UNFROZEN pages for FREEZE.


Performance issues
------------------

* Enable/Disable DSM tracking per tables
DSM requires more or less additional works. If we know specific tables
where DSM does not work well, ex. heavily updated small tables, we can
disable DSM for it. The syntax is:
ALTER TABLE name SET (dsm=true/false);

* Dead Space State Cache
The DSM management module is guarded using one LWLock, DeadSpaceLock.
Almost all accesses to DSM requires only shared lock, but the frequency
of shared lock was very high (tied with BufMappingLock) in my research.
To avoid the lock contention, I added a cache of dead space state in
BufferDesc flags. Backends see the flags first, and avoid locking if no
need to

* Agressive freezing
We will freeze tuples in dirty pages using OldestXmin but FreezeLimit.
This is for making FROZEN pages but not UNFROZEN pages as far as possible
in order to reduce works in XID wraparound vacuums.


Memory management
-----------------

In current implementation, DSM allocates a bunch of memory at start up and
we cannot modify it in running. It's maybe enough because DSM consumes very
little memory -- 32MB memory per 1TB database.

There are 3 parameters for FSM and DSM.

- max_fsm_pages = 204800
- max_fsm_relations = 1000 (= max_dsm_relations)
- max_dsm_pages = 4096000

I'm thinking to change them into 2 new paramaters. We will allocates memory
for DSM that can hold all of estimated_database_size, and for FSM 50% or
something of the size. Is this reasonable?

- estimated_max_relations = 1000
- estimated_database_size = 4GB (= about max_fsm_pages * 8KB * 2)


Recovery
--------

I've already have a recovery extension. However, it can recover DSM
but not FSM. Do we also need to restore FSM? If we don't, unreusable
pages might be left in heaps. Of cource it could be reused if another
tuple in the page are updated, but VACUUM will not find those pages.


Comments and suggestions are really appreciated.

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


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

On Tue, Feb 27, 2007 at 12:05:57PM +0900, ITAGAKI Takahiro wrote:
> Each heap pages have 4 states for dead space map; HIGH, LOW, UNFROZEN and
> FROZEN. VACUUM uses the states to reduce the number of target pages.
>
> - HIGH : High priority to vacuum. Maybe many dead tuples in the page.
> - LOW : Low priority to vacuum Maybe few dead tuples in the page.
> - UNFROZEN : No dead tuples, but some unfrozen tuples in the page.
> - FROZEN : No dead nor unfrozen tuples in the page.
>
> If we do UPDATE a tuple, the original page containing the tuple is marked
> as HIGH and the new page where the updated tuple is placed is marked as LOW.

Don't you mean UNFROZEN?

> When we commit the transaction, the updated tuples needs only FREEZE.
> That's why the after-page is marked as LOW. However, If we rollback, the
> after-page should be vacuumed, so we should mark the page LOW, not UNFROZEN.
> We don't know the transaction will commit or rollback at the UPDATE.

What makes it more important to mark the original page as HIGH instead
of LOW, like the page with the new tuple? The description of the states
indicates that there would likely be a lot more dead tuples in a HIGH
page than in a LOW page.

Perhaps it would be better to have the bgwriter take a look at how many
dead tuples (or how much space the dead tuples account for) when it
writes a page out and adjust the DSM at that time.

> * Agressive freezing
> We will freeze tuples in dirty pages using OldestXmin but FreezeLimit.
> This is for making FROZEN pages but not UNFROZEN pages as far as possible
> in order to reduce works in XID wraparound vacuums.

Do you mean using OldestXmin instead of FreezeLimit?

Perhaps it might be better to save that optimization for later...

> In current implementation, DSM allocates a bunch of memory at start up and
> we cannot modify it in running. It's maybe enough because DSM consumes very
> little memory -- 32MB memory per 1TB database.
>
> There are 3 parameters for FSM and DSM.
>
> - max_fsm_pages = 204800
> - max_fsm_relations = 1000 (= max_dsm_relations)
> - max_dsm_pages = 4096000
>
> I'm thinking to change them into 2 new paramaters. We will allocates memory
> for DSM that can hold all of estimated_database_size, and for FSM 50% or
> something of the size. Is this reasonable?

I don't think so, at least not until we get data from the field about
what's typical. If the DSM is tracking every page in the cluster then
I'd expect the FSM to be closer to 10% or 20% of that, anyway.

> I've already have a recovery extension. However, it can recover DSM
> but not FSM. Do we also need to restore FSM? If we don't, unreusable
> pages might be left in heaps. Of cource it could be reused if another
> tuple in the page are updated, but VACUUM will not find those pages.

Yes, DSM would make FSM recovery more important, but I thought it was
recoverable now? Or is that only on a clean shutdown?

I suspect we don't need perfect recoverability... theoretically we could
just commit the FSM after vacuum frees pages and leave it at that; if we
revert to that after a crash, backends will grab pages from the FSM only
to find there's no more free space, at which point they could pull the
page from the FSM and find another one. This would lead to degraded
performance for a while after a crash, but that might be a good
trade-off.
--
Jim Nasby jim@nasby.net
EnterpriseDB http://enterprisedb.com 512.569.9461 (cell)

---------------------------(end of broadcast)---------------------------
TIP 3: Have you checked our extensive FAQ?

http://www.postgresql.org/docs/faq

"Jim C. Nasby" <jim@nasby.net> writes:
> Yes, DSM would make FSM recovery more important, but I thought it was
> recoverable now? Or is that only on a clean shutdown?

Currently we throw away FSM during any non-clean restart. This is
probably overkill but I'm quite unclear what would be a safe
alternative.

> I suspect we don't need perfect recoverability...

The main problem with the levels proposed by Takahiro-san is that any
transition from FROZEN to not-FROZEN *must* be exactly recovered,
because vacuum will never visit an allegedly frozen page at all. This
appears to require WAL-logging DSM state changes, which is a pretty
serious performance hit. I'd be happier if the DSM content could be
treated as just a hint. I think that means not trusting it for whether
a page is frozen to the extent of not needing vacuum even for
wraparound. So I'm inclined to propose that there be only two states
(hence only one DSM bit per page): page needs vacuum for space recovery,
or not. Vacuum for XID wraparound would have to hit every page
regardless.

regards, tom lane

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

On Tue, 2007-02-27 at 12:05 +0900, ITAGAKI Takahiro wrote:

> I think it's better to get DSM and HOT together. DSM is good at
> complex updated cases but not at heavily updated cases. HOT has
> opposite aspects, as far as I can see. I think they can cover each
> other.

Very much agreed.

I'll be attempting to watch for any conflicting low-level assumptions as
we progress towards deadline.

--
Simon Riggs
EnterpriseDB http://www.enterprisedb.com



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

On Tue, 2007-02-27 at 12:05 +0900, ITAGAKI Takahiro wrote:

> If we combine this with the HOT patch, pages with HOT tuples are probably
> marked as UNFROZEN because we don't bother vacuuming HOT tuples. They can
> be removed incrementally and doesn't require explicit vacuums.

Perhaps avoid DSM entries for HOT updates completely?

> VACUUM commands
> ---------------
>
> VACUUM now only scans the pages that possibly have dead tuples.
> VACUUM ALL, a new syntax, behaves as the same as before.
>
> - VACUUM FULL : Not changed. scans all pages and compress them.
> - VACUUM ALL : Scans all pages; Do the same behavior as previous VACUUM.
> - VACUUM : Scans only HIGH pages usually, but also LOW and UNFROZEN
> pages on vacuums in the cases for preventing XID wraparound.

Sounds good.

> Performance issues
> ------------------
>
> * Enable/Disable DSM tracking per tables
> DSM requires more or less additional works. If we know specific tables
> where DSM does not work well, ex. heavily updated small tables, we can
> disable DSM for it. The syntax is:
> ALTER TABLE name SET (dsm=true/false);

How about a dsm_tracking_limit GUC? (Better name please)
The number of pages in a table before we start tracking DSM entries for
it. DSM only gives worthwhile benefits for larger tables anyway, so let
the user define what large means for them.
dsm_tracking_limit = 1000 by default.

> * Dead Space State Cache
> The DSM management module is guarded using one LWLock, DeadSpaceLock.
> Almost all accesses to DSM requires only shared lock, but the frequency
> of shared lock was very high (tied with BufMappingLock) in my research.
> To avoid the lock contention, I added a cache of dead space state in
> BufferDesc flags. Backends see the flags first, and avoid locking if no
> need to

ISTM there should be a point at which DSM is so full we don't bother to
keep track any longer, so we can drop that information. For example if
user runs UPDATE without a WHERE clause, there's no point in tracking
whole relation.

> Memory management
> -----------------
>
> In current implementation, DSM allocates a bunch of memory at start up and
> we cannot modify it in running. It's maybe enough because DSM consumes very
> little memory -- 32MB memory per 1TB database.

That sounds fine.

--
Simon Riggs
EnterpriseDB http://www.enterprisedb.com



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

On Tue, 2007-02-27 at 00:55 -0500, Tom Lane wrote:
> "Jim C. Nasby" <jim@nasby.net> writes:
> > Yes, DSM would make FSM recovery more important, but I thought it was
> > recoverable now? Or is that only on a clean shutdown?
>
> Currently we throw away FSM during any non-clean restart. This is
> probably overkill but I'm quite unclear what would be a safe
> alternative.
>
> > I suspect we don't need perfect recoverability...
>
> The main problem with the levels proposed by Takahiro-san is that any
> transition from FROZEN to not-FROZEN *must* be exactly recovered,
> because vacuum will never visit an allegedly frozen page at all. This
> appears to require WAL-logging DSM state changes, which is a pretty
> serious performance hit. I'd be happier if the DSM content could be
> treated as just a hint. I think that means not trusting it for whether
> a page is frozen to the extent of not needing vacuum even for
> wraparound.

Agreed.

> So I'm inclined to propose that there be only two states
> (hence only one DSM bit per page): page needs vacuum for space recovery,
> or not. Vacuum for XID wraparound would have to hit every page
> regardless.

I'm inclined to think: this close to deadline it would be more robust to
go with the simpler option. So, agreed to the one bit per page.

We can revisit the 2 bits/page idea easily for later releases. If the
DSM is non-transactional, upgrading to a new format in the future should
be very easy.

--
Simon Riggs
EnterpriseDB http://www.enterprisedb.com



---------------------------(end of broadcast)---------------------------
TIP 4: Have you searched our list archives?

http://archives.postgresql.org

"Jim C. Nasby" <jim@nasby.net> wrote:

> > If we do UPDATE a tuple, the original page containing the tuple is marked
> > as HIGH and the new page where the updated tuple is placed is marked as LOW.
>
> Don't you mean UNFROZEN?

No, the new tuples are marked as LOW. I intend to use UNFROZEN and FROZEN
pages as "all tuples in the pages are visible to all transactions" for
index-only-scan in the future.


> What makes it more important to mark the original page as HIGH instead
> of LOW, like the page with the new tuple? The description of the states
> indicates that there would likely be a lot more dead tuples in a HIGH
> page than in a LOW page.
>
> Perhaps it would be better to have the bgwriter take a look at how many
> dead tuples (or how much space the dead tuples account for) when it
> writes a page out and adjust the DSM at that time.

Yeah, I feel it is worth optimizable, too. One question is, how we treat
dirty pages written by backends not by bgwriter? If we want to add some
works in bgwriter, do we also need to make bgwriter to write almost of
dirty pages?


> > * Agressive freezing
> > We will freeze tuples in dirty pages using OldestXmin but FreezeLimit.
>
> Do you mean using OldestXmin instead of FreezeLimit?

Yes, we will use OldestXmin as the threshold to freeze tuples in
dirty pages or pages that have some dead tuples. Or, many UNFROZEN
pages still remain after vacuum and they will cost us in the next
vacuum preventing XID wraparound.


> > I'm thinking to change them into 2 new paramaters. We will allocates memory
> > for DSM that can hold all of estimated_database_size, and for FSM 50% or
> > something of the size. Is this reasonable?
>
> I don't think so, at least not until we get data from the field about
> what's typical. If the DSM is tracking every page in the cluster then
> I'd expect the FSM to be closer to 10% or 20% of that, anyway.

I'd like to add some kind of logical flavors to max_fsm_pages
and max_dsm_pages. For DSM, max_dsm_pages should represent the
whole database size. In the other hand, what meaning does
max_fsm_pages have? (estimated_updatable_size ?)

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



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

Tom Lane <tgl@sss.pgh.pa.us> wrote:

> Vacuum for XID wraparound would have to hit every page regardless.

There is one problem at this point. If we want to guarantee that there
are no tuples that XIDs are older than pg_class.relfrozenxid, we must scan
all pages for XID wraparound for every vacuums. So I used two thresholds
for treating XIDs, that is commented as follows. Do you have better ideas
for this point?

/*
* We use vacuum_freeze_min_age to determine whether a freeze scan is
* needed, but half vacuum_freeze_min_age for the actual freeze limits
* in order to prevent XID wraparound won't occur too frequently.
*/


Also, normal vacuums uses DSM and freeze-vacuum does not, so vacuums
sometimes take longer time than usual. Doesn't the surprise bother us?

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



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

"Simon Riggs" <simon@2ndquadrant.com> wrote:

> > If we combine this with the HOT patch, pages with HOT tuples are probably
> > marked as UNFROZEN because we don't bother vacuuming HOT tuples. They can
> > be removed incrementally and doesn't require explicit vacuums.
>
> Perhaps avoid DSM entries for HOT updates completely?

Yes, if we employ 1bit/page (worth vacuum or not).
Or no if 2bits/page because HOT updates change page states to UNFROZEN.


> > * Enable/Disable DSM tracking per tables
>
> How about a dsm_tracking_limit GUC? (Better name please)
> The number of pages in a table before we start tracking DSM entries for
> it. DSM only gives worthwhile benefits for larger tables anyway, so let
> the user define what large means for them.
> dsm_tracking_limit = 1000 by default.

Sound good. How about small_table_size = 8MB for the variable?
I found that we've already have the value used for truncating
threshold for vacuum. (REL_TRUNCATE_MINIMUM = 1000 in vacuumlazy.c)
I think they have the same purpose in treating of small tables
and we can use the same variable in these places.


> > * Dead Space State Cache
>
> ISTM there should be a point at which DSM is so full we don't bother to
> keep track any longer, so we can drop that information. For example if
> user runs UPDATE without a WHERE clause, there's no point in tracking
> whole relation.

It's a bit difficult. We have to lock DSM *before* we see whether
the table is tracked or not. So we need to cache the tracked state
in the relcache entry, but it requres some works to keep coherency
between cached states and shared states.

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



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

Tom Lane wrote:
> The main problem with the levels proposed by Takahiro-san is that any
> transition from FROZEN to not-FROZEN *must* be exactly recovered,
> because vacuum will never visit an allegedly frozen page at all. This
> appears to require WAL-logging DSM state changes, which is a pretty
> serious performance hit.

I doubt it would be a big performance hit. AFAICS, all the information
needed to recover the DSM is already written to WAL, so it wouldn't need
any new WAL records.

> I'd be happier if the DSM content could be
> treated as just a hint. I think that means not trusting it for whether
> a page is frozen to the extent of not needing vacuum even for
> wraparound. So I'm inclined to propose that there be only two states
> (hence only one DSM bit per page): page needs vacuum for space recovery,
> or not. Vacuum for XID wraparound would have to hit every page
> regardless.

If we don't have a frozen state, we can't use the DSM to implement
index-only scans. Index-only scans will obviously require a lot more
work than just the DSM, but I'd like to have a solution that enables it
in the future.

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

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