Re: FSM search modes

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