Re: FSM search modes

Just been looking again at the way FSM works. In fsm_search_avail() we
essentially have just a single way for working out how to search the
tree.

Seems like it would be good to abstract this so that we can implement a
number of FSM search strategies

* (current) randomize - page selection encourages different backends to
access different blocks, thus reducing block contention

* cluster - page selection made based around selecting block with
freespace nearest current block and we prefer keep-in-sequence to
avoid-contention

* compact - page selection specifically attempts to find the lowest
numbered blocks, so that the table will naturally shrink over time.

These are not all mutually exclusive, suggested combinations would be

randomize, randomize | cluster, randomize | compact

So we don't give up the load spreading behaviour, we just apply the
logic at lower levels of the tree only.

VACUUM could set the FSM into FSMstrategy = compact when it notices that
most of the free blocks are at lower end of table. Or explicitly set
during VF replacement utility.

FSMstrategy = cluster would be the default if clustering is enabled on a
table.

FSMstrategy can change via ALTER TABLE ... WITH (fsm_strategy = ...)

--
Simon Riggs www.2ndQuadrant.com

Simon Riggs <simon(at)2ndQuadrant(dot)com> wrote:

> * compact - page selection specifically attempts to find the lowest
> numbered blocks, so that the table will naturally shrink over time.

We cannot shrink the table if one tuple remains at the end of table
and the tuple is always HOT-updated, because we put a new tuple into
the same page where the old tuple is placed if possible.

In addition to your intelligent FSM search modes,
do we need another algorithm to make the compaction to work better?

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

On Fri, 2009-09-18 at 10:47 +0900, Itagaki Takahiro wrote:
> Simon Riggs <simon(at)2ndQuadrant(dot)com> wrote:
>
> > * compact - page selection specifically attempts to find the lowest
> > numbered blocks, so that the table will naturally shrink over time.
>
> We cannot shrink the table if one tuple remains at the end of table
> and the tuple is always HOT-updated, because we put a new tuple into
> the same page where the old tuple is placed if possible.
>
> In addition to your intelligent FSM search modes,
> do we need another algorithm to make the compaction to work better?

Perhaps we can have an additional piece of information about a table.
Something like target_size, so that normal updaters that attempt HOT
updates on blocks greater than target_size would know to avoid that
block and to seek a new location for the row lower in the table. Perhaps
such information could be reset and then sent via invalidation
mechanisms.

I'm thinking along the lines of a "fire alarm". An occasional mechanism
by which we can inform users of the need to evacuate certain blocks.

--
Simon Riggs www.2ndQuadrant.com

On Sep 18, 2009, at 1:09 AM, Simon Riggs wrote:
> On Fri, 2009-09-18 at 10:47 +0900, Itagaki Takahiro wrote:
>> Simon Riggs <simon(at)2ndQuadrant(dot)com> wrote:
>>
>>> * compact - page selection specifically attempts to find the lowest
>>> numbered blocks, so that the table will naturally shrink over time.
>>
>> We cannot shrink the table if one tuple remains at the end of table
>> and the tuple is always HOT-updated, because we put a new tuple into
>> the same page where the old tuple is placed if possible.
>>
>> In addition to your intelligent FSM search modes,
>> do we need another algorithm to make the compaction to work better?
>
> Perhaps we can have an additional piece of information about a table.
> Something like target_size, so that normal updaters that attempt HOT
> updates on blocks greater than target_size would know to avoid that
> block and to seek a new location for the row lower in the table.
> Perhaps
> such information could be reset and then sent via invalidation
> mechanisms.
>
> I'm thinking along the lines of a "fire alarm". An occasional
> mechanism
> by which we can inform users of the need to evacuate certain blocks.

It might be better to not beat around the bush and provide a vacuum
mode that explicitly tries to free the last X percent of the table.
That's especially handy for a very large table, because you probably
don't want to be forced into scanning the whole thing in vacuum just
to free some space at the end. This mode could also be more
aggressive about trying to acquire the lock that's needed to trim the
file on disk.

That said, *any* step that improves dealing with table bloat is
extremely welcome, as right now you're basically stuck rebuilding the
table.
--
Decibel!, aka Jim C. Nasby, Database Architect decibel(at)decibel(dot)org
Give your computer some brain candy! www.distributed.net Team #1828

On Thu, 2009-09-17 at 16:26 +0100, Simon Riggs wrote:
> Just been looking again at the way FSM works. In fsm_search_avail() we
> essentially have just a single way for working out how to search the
> tree.
>
> Seems like it would be good to abstract this so that we can implement a
> number of FSM search strategies
>
> * (current) randomize - page selection encourages different backends to
> access different blocks, thus reducing block contention
>
> * cluster - page selection made based around selecting block with
> freespace nearest current block and we prefer keep-in-sequence to
> avoid-contention

Is the information about "current block" available to FSM search API, or
do we need to change the API for that ?

> * compact - page selection specifically attempts to find the lowest
> numbered blocks, so that the table will naturally shrink over time.
>
> These are not all mutually exclusive, suggested combinations would be
>
> randomize, randomize | cluster, randomize | compact
>
> So we don't give up the load spreading behaviour, we just apply the
> logic at lower levels of the tree only.
>
> VACUUM could set the FSM into FSMstrategy = compact when it notices that
> most of the free blocks are at lower end of table. Or explicitly set
> during VF replacement utility.
>
> FSMstrategy = cluster would be the default if clustering is enabled on a
> table.
>
> FSMstrategy can change via ALTER TABLE ... WITH (fsm_strategy = ...)
>
> --
> Simon Riggs www.2ndQuadrant.com
>

--
Hannu Krosing http://www.2ndQuadrant.com
PostgreSQL Scalability and Availability
Services, Consulting and Training

On Fri, 2009-09-18 at 15:43 +0300, Hannu Krosing wrote:
> >
> > * cluster - page selection made based around selecting block with
> > freespace nearest current block and we prefer keep-in-sequence to
> > avoid-contention
>
> Is the information about "current block" available to FSM search API, or
> do we need to change the API for that ?

Need to change the API, but its a small code impact.

--
Simon Riggs www.2ndQuadrant.com

decibel <decibel(at)decibel(dot)org> wrote:

> *any* step that improves dealing with table bloat is extremely
> welcome, as right now you're basically stuck rebuilding the table.

+1

Although, possibly more irritating than actually rebuilding it is
evaluating borderline bloat situations to determine if they will "work
themselves out" over time or whether you need to bite the bullet to do
aggressive maintenance. Having some way for routine vacuums (or any
other routine process, currently available or that could be scheduled)
to "nibble away" at moderate bloat without significant performance or
usability impact would make life easier for at least *some* DBAs.

-Kevin

On Sep 30, 2009, at 5:13 PM, Kevin Grittner wrote:
> decibel <decibel(at)decibel(dot)org> wrote:
>
>> *any* step that improves dealing with table bloat is extremely
>> welcome, as right now you're basically stuck rebuilding the table.
>
> +1
>
> Although, possibly more irritating than actually rebuilding it is
> evaluating borderline bloat situations to determine if they will "work
> themselves out" over time or whether you need to bite the bullet to do
> aggressive maintenance. Having some way for routine vacuums (or any
> other routine process, currently available or that could be scheduled)
> to "nibble away" at moderate bloat without significant performance or
> usability impact would make life easier for at least *some* DBAs.

Kevin, do you have tools that allow you to clear out the end of a
table? That part is at least mostly possible from userland (get list
of ctids from end of table, update those records to move them, rinse,
repeat) but even if you do all that there's no guarantee that a
vacuum will get the exclusive lock it needs to truncate the table.

So while something that makes it easier to clean out the end of a
table would be good, I think the critical need is a way to make
vacuum more aggressive about obtaining the exclusive lock.
--
Decibel!, aka Jim C. Nasby, Database Architect decibel(at)decibel(dot)org
Give your computer some brain candy! www.distributed.net Team #1828

decibel wrote:

> So while something that makes it easier to clean out the end of a
> table would be good, I think the critical need is a way to make
> vacuum more aggressive about obtaining the exclusive lock.

I wonder if we should have a different mode of operation that only
attempted the truncate (say VACUUM TRUNCATE), optionally being
non-conditional about obtaining the required lock. That said, I wonder
even more whether any such hacks are still needed after the visilibity
map that changed the landscape for vacuum so dramatically.

--
Alvaro Herrera http://www.CommandPrompt.com/
The PostgreSQL Company - Command Prompt, Inc.

Alvaro Herrera <alvherre(at)commandprompt(dot)com> writes:
> I wonder if we should have a different mode of operation that only
> attempted the truncate (say VACUUM TRUNCATE), optionally being
> non-conditional about obtaining the required lock. That said, I wonder
> even more whether any such hacks are still needed after the visilibity
> map that changed the landscape for vacuum so dramatically.

Yeah. The one thing in this thread that seemed like a good idea to me
was to bias the FSM code a little bit towards returning space near the
start of the relation, rather than its current behavior of treating all
the free space equally. The current arrangement pretty much guarantees
that you'll never recover from a bloating episode without taking special
manual action. (This is not new to 8.4, the previous FSM code behaved
the same.)

The analogy in the back of my mind is the btree code that decides
whether to split the current page or move to the next page when it has a
full page and a new key that could go to either page. We found out that
randomizing that choice made a *huge* improvement in the average
behavior, even with the probabilities set up as 99-to-1. I'm thinking
that just a small chance of resetting the search to the start of the
relation might do the trick for FSM.

regards, tom lane

On Thu, 2009-10-01 at 12:05 -0400, Tom Lane wrote:
> Alvaro Herrera <alvherre(at)commandprompt(dot)com> writes:
> > I wonder if we should have a different mode of operation that only
> > attempted the truncate (say VACUUM TRUNCATE), optionally being
> > non-conditional about obtaining the required lock. That said, I wonder
> > even more whether any such hacks are still needed after the visilibity
> > map that changed the landscape for vacuum so dramatically.
>
> Yeah. The one thing in this thread that seemed like a good idea to me
> was to bias the FSM code a little bit towards returning space near the
> start of the relation, rather than its current behavior of treating all
> the free space equally. The current arrangement pretty much guarantees
> that you'll never recover from a bloating episode without taking special
> manual action. (This is not new to 8.4, the previous FSM code behaved
> the same.)
>
> The analogy in the back of my mind is the btree code that decides
> whether to split the current page or move to the next page when it has a
> full page and a new key that could go to either page. We found out that
> randomizing that choice made a *huge* improvement in the average
> behavior, even with the probabilities set up as 99-to-1. I'm thinking
> that just a small chance of resetting the search to the start of the
> relation might do the trick for FSM.

No real need to be random is there? In the bloated space scenario,
VACUUM will be triggered but will be unable to remove the empty blocks.
So in that case VACUUM can hint the FSM to perform "start from beginning
of relation" behaviour. When a searcher does that and can't usefully
find space quickly, then we can reset the hint back to normal. So it's
an automated mode change in both directions.

I think we can use the N-to-1 idea to define what we mean by "quickly",
but that should be in proportion to exactly how many free blocks there
were in table, not a fixed N. It would be a shame to make this work
poorly for very large tables.

It would be more useful to think of this as "look for huge chunks of
space and fill them" rather than "start at beginning", since space won't
always be right at start.

--
Simon Riggs www.2ndQuadrant.com

Simon Riggs <simon(at)2ndQuadrant(dot)com> writes:
> No real need to be random is there? In the bloated space scenario,
> VACUUM will be triggered but will be unable to remove the empty blocks.
> So in that case VACUUM can hint the FSM to perform "start from beginning
> of relation" behaviour.

No, that's an entirely unrelated issue. My point is that there won't
*be* any empty end blocks unless we discourage FSM from handing out
those pages as insertion targets.

regards, tom lane

Simon Riggs <simon(at)2ndQuadrant(dot)com> wrote:

> It would be more useful to think of this as "look for huge chunks of
> space and fill them" rather than "start at beginning", since space
> won't always be right at start.

Either I misunderstand you or I disagree. If there's a huge chunk of
space near the end, and many many smaller spaces spread throughout,
what I'd like is for rows to be placed in those small ones. This
would minimize the number of pages to read for queries, and would
present some possibility that the rows past the huge chunk might
eventually be deleted or non-HOT updated, allowing the bloat to
eventually be cleaned up with minimal pain.

-Kevin

On Thu, 2009-10-01 at 11:32 -0500, Kevin Grittner wrote:

> Either I misunderstand you or I disagree.

That does seem to be a common stance, though I will read on. :-)

--
Simon Riggs www.2ndQuadrant.com

On Thu, 2009-10-01 at 11:32 -0500, Kevin Grittner wrote:
> If there's a huge chunk of
> space near the end, and many many smaller spaces spread throughout,
> what I'd like is for rows to be placed in those small ones. This
> would minimize the number of pages to read for queries, and would
> present some possibility that the rows past the huge chunk might
> eventually be deleted or non-HOT updated, allowing the bloat to
> eventually be cleaned up with minimal pain.

Yes, as Tom points out, this must be done with bias away from the very
end of the table.

I meant that we should start from the beginning of large spaces and that
we shouldn't assume that all space worth filling is at start of
relation.

--
Simon Riggs www.2ndQuadrant.com

Simon Riggs <simon(at)2ndQuadrant(dot)com> writes:
> Yes, as Tom points out, this must be done with bias away from the very
> end of the table.

> I meant that we should start from the beginning of large spaces and that
> we shouldn't assume that all space worth filling is at start of
> relation.

Right. One of the goals that FSM is trying to meet is ensuring that
different backends aren't trying to insert into the same page
concurrently, so as to reduce page-level contention. So for example
it'd be a bad idea to adopt the really-dumb strategy of searching from
the start of the table for each request --- it'd funnel all the backends
to the same target page. What we want is a behavior that is randomized
but tends to prefer pages towards the start rather than hitting all free
pages equally. The btree precedent makes me suspect that quite a weak
preference would be sufficient. So for example we might try resetting
the search to the start of the relation with probability 0.01.

regards, tom lane

Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Simon Riggs <simon(at)2ndQuadrant(dot)com> writes:
>> Yes, as Tom points out, this must be done with bias away from the
>> very end of the table.
>
>> I meant that we should start from the beginning of large spaces and
>> that we shouldn't assume that all space worth filling is at start
>> of relation.

OK, so I did misunderstand you; we agree after all. :-)

> So for example we might try resetting the search to the start of the
> relation with probability 0.01.

If I understand the heuristic you propose, and my math skill haven't
eroded too badly from lack of use, every 229 spots considered would
cause a 90% chance of reset. That means that the odds of getting past
50,000 spots (the number of pages with available free space at which I
generally start to get worried) without resetting is about 1 in 10^218
-- which is a risk I'm willing to accept. ;-)

-Kevin

"Kevin Grittner" <Kevin(dot)Grittner(at)wicourts(dot)gov> writes:
> Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>> So for example we might try resetting the search to the start of the
>> relation with probability 0.01.

> If I understand the heuristic you propose, and my math skill haven't
> eroded too badly from lack of use, every 229 spots considered would
> cause a 90% chance of reset.

Sorry, I wasn't clear. What I was thinking of was that we'd consider
resetting the search position once, upon entry to fsm_search, and then
search normally thereafter. Some experimentation would be needed to
choose the right probability of course. A number like 0.01 might seem
too small to affect the behavior at all, but that's what we thought
about the btree case too. A very light thumb upon the scales may be
sufficient.

regards, tom lane

Kevin Grittner wrote:
> Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>> Simon Riggs <simon(at)2ndQuadrant(dot)com> writes:
>>> Yes, as Tom points out, this must be done with bias away from the
>>> very end of the table.
>>> I meant that we should start from the beginning of large spaces and
>>> that we shouldn't assume that all space worth filling is at start
>>> of relation.
>
> OK, so I did misunderstand you; we agree after all. :-)
>
>> So for example we might try resetting the search to the start of the
>> relation with probability 0.01.
>
> If I understand the heuristic you propose, and my math skill haven't
> eroded too badly from lack of use, every 229 spots considered would
> cause a 90% chance of reset. That means that the odds of getting past
> 50,000 spots (the number of pages with available free space at which I
> generally start to get worried) without resetting is about 1 in 10^218
> -- which is a risk I'm willing to accept. ;-)

The FSM currently uses a clock sweep kind of algorithm to hand out
pages, and the clock hand is reset to 0 at every vacuum. The purpose of
resetting the clock hand is precisely to bias towards lower-numbered
pages, to allow truncation later on.

That's a bit of an over-simplification, though, there's actually a
separate "clock hand" on each FSM page (next_slot pointer).

We probably could do with more bias. For example, we still prefer pages
close to the page we last inserted to, by searching for free space in
the same FSM page first, before starting the search from the top of the
tree. And of course, each backend tries first to insert to the last page
it inserted to before even consulting the FSM. A mode to disable those
behaviors might indeed be useful, along with the random reset.

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

Heikki Linnakangas <heikki(dot)linnakangas(at)enterprisedb(dot)com> wrote:
> Kevin Grittner wrote:
>> Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

>>> So for example we might try resetting the search to the start of
the
>>> relation with probability 0.01.
>>
>> If I understand the heuristic you propose, and my math skill
>> haven't eroded too badly from lack of use, every 229 spots
>> considered would cause a 90% chance of reset. That means that the
>> odds of getting past 50,000 spots (the number of pages with
>> available free space at which I generally start to get worried)
>> without resetting is about 1 in 10^218 -- which is a risk I'm
>> willing to accept. ;-)
>
> The FSM currently uses a clock sweep kind of algorithm to hand out
> pages, and the clock hand is reset to 0 at every vacuum. The purpose
> of resetting the clock hand is precisely to bias towards
> lower-numbered pages, to allow truncation later on.
>
> That's a bit of an over-simplification, though, there's actually a
> separate "clock hand" on each FSM page (next_slot pointer).
>
> We probably could do with more bias. For example, we still prefer
> pages close to the page we last inserted to, by searching for free
> space in the same FSM page first, before starting the search from
> the top of the tree. And of course, each backend tries first to
> insert to the last page it inserted to before even consulting the
> FSM. A mode to disable those behaviors might indeed be useful, along
> with the random reset.

That flushes out the descriptions given by Tom, but doesn't really
make me think I misunderstood the heuristic or miscalculated the odds
of getting far from the start with a 1% probability of a reset on each
advance of the sweep. (Of course, it's possible I'm being dense and
taking statements to mean what I expect, despite evidence to the
contrary.)

The way I figure it, if there is a 0.01 chance to reset the sweep,
then there's a 0.99 percent chance to continue the sweep from the last
position. 0.99^229 is about 0.1, which means there is a 10% chance
not to have reset after that many attempts to advance. Every 229
attempts after that multiplies by 0.1, too. So, after 229*6 attempts
(for example) the odds of not having reset are about one in a million.

Am I saying something stupid here? (I used to be good at these sorts
of calculations....)

-Kevin

"Kevin Grittner" <Kevin(dot)Grittner(at)wicourts(dot)gov> wrote:

> 0.99 percent chance to continue the sweep

Make that a 99% chance, or a 0.99 chance (in case the typo was not
apparent).

> Am I saying something stupid here?

Well, besides that line?

-Kevin

On Thu, Oct 1, 2009 at 3:23 PM, Heikki Linnakangas
<heikki(dot)linnakangas(at)enterprisedb(dot)com> wrote:
> We probably could do with more bias. For example, we still prefer pages
> close to the page we last inserted to, by searching for free space in
> the same FSM page first, before starting the search from the top of the
> tree. And of course, each backend tries first to insert to the last page
> it inserted to before even consulting the FSM. A mode to disable those
> behaviors might indeed be useful, along with the random reset.

The elephant in the room here is that if the relation is a million
pages of which 1-100,000 and 1,000,000 are in use, no amount of bias
is going to help us truncate the relation unless every tuple on page
1,000,000 gets updated or deleted. If the user doesn't have any
interest in doing anything to those tuples, nothing will ever happen.

And this is likely to come up a lot, because many tables have a core
of data that is rarely or never updated. For example, imagine that
90% of pages contain data that is updated regularly and 10% of pages
contain data that is rarely or never updated. If these are
distributed uniformly, we figure to hit one of the latter type within
10 pages or so, and then we're stymied.

...Robert

"Kevin Grittner" <Kevin(dot)Grittner(at)wicourts(dot)gov> writes:
> The way I figure it, if there is a 0.01 chance to reset the sweep,
> then there's a 0.99 percent chance to continue the sweep from the last
> position. 0.99^229 is about 0.1, which means there is a 10% chance
> not to have reset after that many attempts to advance.

Right, so the odds would be that a backend will confine its insertion
attempts to the first 229 pages containing a usable amount of free
space. As long as the number of backends concurrently inserting
into the relation is well under 229, this seems perfectly fine.
(Hm, so we might want to make the probability depend on
max_connections?)

A possible downside of keeping things compact this way is that you'd
probably get a longer average search distance because of all the early
pages tending to remain full. Maybe what we want is some bias against
inserting in the last half or quarter of the table, or some such rule,
rather than necessarily heading for the start of the relation.

regards, tom lane

Robert Haas <robertmhaas(at)gmail(dot)com> writes:
> The elephant in the room here is that if the relation is a million
> pages of which 1-100,000 and 1,000,000 are in use, no amount of bias
> is going to help us truncate the relation unless every tuple on page
> 1,000,000 gets updated or deleted.

Well, there is no way to move a tuple across pages in a user-invisible,
non-blocking fashion, so our ability to do something automatic about the
above scenario is limited. The discussion at the moment is about ways
of reducing the probability of getting into that situation in the first
place. That doesn't preclude also providing some more-invasive tools
that people can use when they do get into that situation; but let's
not let I-want-a-magic-pony syndrome prevent us from doing anything
at all.

regards, tom lane

On Thu, Oct 1, 2009 at 4:47 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> A possible downside of keeping things compact this way is that you'd
> probably get a longer average search distance because of all the early
> pages tending to remain full.  Maybe what we want is some bias against
> inserting in the last half or quarter of the table, or some such rule,
> rather than necessarily heading for the start of the relation.

Yeah, that seems better. Avoiding the last quarter seems like it
would likely be sufficient.

If it's not too hard, it might make sense to only apply this bias when
we know that the table is already somewhat bloated.

...Robert

On Thu, Oct 1, 2009 at 5:08 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Robert Haas <robertmhaas(at)gmail(dot)com> writes:
>> The elephant in the room here is that if the relation is a million
>> pages of which 1-100,000 and 1,000,000 are in use, no amount of bias
>> is going to help us truncate the relation unless every tuple on page
>> 1,000,000 gets updated or deleted.
>
> Well, there is no way to move a tuple across pages in a user-invisible,
> non-blocking fashion, so our ability to do something automatic about the
> above scenario is limited.  The discussion at the moment is about ways
> of reducing the probability of getting into that situation in the first
> place.  That doesn't preclude also providing some more-invasive tools
> that people can use when they do get into that situation; but let's
> not let I-want-a-magic-pony syndrome prevent us from doing anything
> at all.

That's fair enough, but it's our usual practice to consider, before
implementing a feature or code change, what fraction of the people it
will actually help and by how much. If there's a way that we can
improve the behavior of the system in this area, I am all in favor of
it, but I have pretty modest expectations for how much real-world
benefit will ensue. I suspect that it's pretty common for large
tables to contain a core of infrequently-updated records, and even a
very light smattering of those, distributed randomly, will be enough
to stop table shrinkage before it can get very far.

...Robert

Robert Haas <robertmhaas(at)gmail(dot)com> wrote:

> The elephant in the room here is that if the relation is a million
> pages of which 1-100,000 and 1,000,000 are in use, no amount of bias
> is going to help us truncate the relation unless every tuple on page
> 1,000,000 gets updated or deleted.

Perhaps bias, combined with a client utility to force non-HOT updates
of some rows at the end of the table would provide the desired
behavior. (It'd be nice if that could be built in to vacuum, but if
it's not feasible, a separate utility is workable.) Off the top of my
head, I might set up a routine crontab job for most databases to do
that to the lesser of 1% of the rows or a number of rows which matches
how far the pages with free space exceed 10% of total pages. That
seems like it should contain things for most circumstances without
getting too extreme. One could always run the utility manually to
correct more extreme bloat.

Some sort of delay (similar to what vacuum can do) to prevent tanking
performance would be good. We wouldn't care about the occasional
update conflict -- we expect that using a relational database means
dealing with serialization failures. We'd be more than happy to
accept a few of these in exchange for keeping performance optimal. If
your software is designed to reschedule transactions which are rolled
back for serialization failures, they are just another performance
cost, so it's pretty easy to balance one cost against another.

-Kevin

Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> writes:
> That doesn't preclude also providing some more-invasive tools
> that people can use when they do get into that situation;

About this side of things, what about having any query which asks for
system columns (any of them) take a specific (new) exclusive row level
lock. The tuple moving utility would try to take the same lock before
moving any tuple, thus allowing those who need it to continue relying on
the ctid / xmin queries trick.

If that idea has any chance to fly, the tuple moving facility could even
be integrated into autovacuum for actively self-healing PostgreSQL.

Regards,
--
dim

Hoping this won't be some more hand waving.

Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> (Hm, so we might want to make the probability depend on
> max_connections?)

Without doing rigorous math on it, I'd guess that to prevent
contention among n connections you'd want the probably of resetting
the sweep to be about 1 / (n * 2). That would mean you'd advance to
the nth page about 60.6% of the time without resetting the sweep. For
less contention, 1 / (n * 4) would let you get to the nth page about
77.9% of the time.

> Maybe what we want is some bias against inserting in the last half
> or quarter of the table, or some such rule, rather than necessarily
> heading for the start of the relation.

I think it would make sense to just start using this once you get into
the last half or quarter of the free pages. If you go with the last
quarter, then you might want to use a higher probability than I
suggested above, although that would tend to leave you with contention
when all the free space was in the last quarter. I'd be inclined to
use something like the above probability and start using it at 50%.

-Kevin

"Kevin Grittner" <Kevin(dot)Grittner(at)wicourts(dot)gov> wrote:

> I think it would make sense to just start using this once you get
> into the last half or quarter of the free pages. If you go with the
> last quarter, then you might want to use a higher probability than I
> suggested above, although that would tend to leave you with
> contention when all the free space was in the last quarter. I'd be
> inclined to use something like the above probability and start using
> it at 50%.

Fuzzy thinking there -- if it's the last quarter of the *free* pages,
the suggested probabilities should be fine. (Somehow I got to
thinking, for a moment, that it would be the last quarter of the
relation's overall pages....)

-Kevin

"Kevin Grittner" <Kevin(dot)Grittner(at)wicourts(dot)gov> writes:
> Fuzzy thinking there -- if it's the last quarter of the *free* pages,
> the suggested probabilities should be fine. (Somehow I got to
> thinking, for a moment, that it would be the last quarter of the
> relation's overall pages....)

It's going to be the latter --- we do not know, and are *not* going to
invest the cycles to find out, how many pages have a useful amount of
free space. Even finding out the relation physical length might be
more cycles than we want to spend here ...

regards, tom lane

On Thu, 2009-10-01 at 17:08 -0400, Tom Lane wrote:
> The discussion at the moment is about ways
> of reducing the probability of getting into that situation in the
> first place.

Definitely.

> That doesn't preclude also providing some more-invasive tools that
> people can use when they do get into that situation

Yes, this is a separate thread specifically so we can get both; the
VACUUM FULL replacement discussion had/was progressing well so ought not
need to bring it up again here.

--
Simon Riggs www.2ndQuadrant.com

Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> "Kevin Grittner" <Kevin(dot)Grittner(at)wicourts(dot)gov> writes:
>> [pages with free space or total pages in relation?]
>
> It's going to be the latter --- we do not know, and are *not* going
> to invest the cycles to find out, how many pages have a useful
> amount of free space. Even finding out the relation physical length
> might be more cycles than we want to spend here ...

OK, after mulling this over for a while, I suspect we'd do pretty well
with starting to consider resetting the sweep after hitting 50% of the
last known relation size (or whatever best approximation is available
at low cost), and using a reset probability of 1 / (max_connections *
4). That gives about a 77.8% chance of getting to at least
max_connections before resetting the sweep. Since it leaves about an
8.2% chance of getting to at least ten times max_connections pages
before resetting the sweep, I'm inclined to think we'd want to start
that at 50% of the relation rather than waiting until we get to the
last quarter. As one more data point to consider, if someone has 2000
connections configured (which I've seen mentioned in many posts), you
would get to 50,000 pages past the point where you start using this
technique one time out of 500.

-Kevin

On Oct 1, 2009, at 4:18 PM, Robert Haas wrote:

> On Thu, Oct 1, 2009 at 5:08 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>> Robert Haas <robertmhaas(at)gmail(dot)com> writes:
>>> The elephant in the room here is that if the relation is a million
>>> pages of which 1-100,000 and 1,000,000 are in use, no amount of bias
>>> is going to help us truncate the relation unless every tuple on page
>>> 1,000,000 gets updated or deleted.
>>
>> Well, there is no way to move a tuple across pages in a user-
>> invisible,
>> non-blocking fashion, so our ability to do something automatic
>> about the
>> above scenario is limited. The discussion at the moment is about
>> ways
>> of reducing the probability of getting into that situation in the
>> first
>> place. That doesn't preclude also providing some more-invasive tools
>> that people can use when they do get into that situation; but let's
>> not let I-want-a-magic-pony syndrome prevent us from doing anything
>> at all.
>
> That's fair enough, but it's our usual practice to consider, before
> implementing a feature or code change, what fraction of the people it
> will actually help and by how much. If there's a way that we can
> improve the behavior of the system in this area, I am all in favor of
> it, but I have pretty modest expectations for how much real-world
> benefit will ensue. I suspect that it's pretty common for large

Speaking of helping other cases...

Something else that's been talked about is biasing FSM searches in
order to try and keep a table clustered. If it doesn't add a lot of
overhead, it would be nice to keep that in mind. I don't know where
something like randomly reseting the search would go in the code, but
I suspect it wouldn't be very expandable in the future.

But like Tom said, the top goal here is to help deal with bloat, not
other fanciness.
--
Decibel!, aka Jim C. Nasby, Database Architect decibel(at)decibel(dot)org
Give your computer some brain candy! www.distributed.net Team #1828

Kevin Grittner wrote:
> Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>
> > (Hm, so we might want to make the probability depend on
> > max_connections?)
>
> Without doing rigorous math on it, I'd guess that to prevent
> contention among n connections you'd want the probably of resetting
> the sweep to be about 1 / (n * 2). That would mean you'd advance to
> the nth page about 60.6% of the time without resetting the sweep. For
> less contention, 1 / (n * 4) would let you get to the nth page about
> 77.9% of the time.
>
> > Maybe what we want is some bias against inserting in the last half
> > or quarter of the table, or some such rule, rather than necessarily
> > heading for the start of the relation.
>
> I think it would make sense to just start using this once you get into
> the last half or quarter of the free pages. If you go with the last
> quarter, then you might want to use a higher probability than I
> suggested above, although that would tend to leave you with contention
> when all the free space was in the last quarter. I'd be inclined to
> use something like the above probability and start using it at 50%.

Two things that might not have been mentioned: First, only reset if you
are given a page in the last 1/4 of the table; that way, if there is no
free space in the last 1/4 of the table, you will not be resetting. A
second idea is to heavily bias against using the last table page with
data in it; that should help bias toward empty pages on the end of the
table.

--
Bruce Momjian <bruce(at)momjian(dot)us> http://momjian.us
EnterpriseDB http://enterprisedb.com

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