Re: Free Space Map thoughts

I found a nice paper describing a few free space management algorithms:

M. L. McAuliffe, M. J. Carey and M. H. Solomon, Towards Effective and
Efficient Free Space Management, Proceedings of the ACM SIGMOD, Jun.
1996, pages 389--400. http://citeseer.ist.psu.edu/mcauliffe96towards.html

The basic data structure used by all of the discussed algorithms is
essentially a bitmap, with a few bits per each heap page, indicating the
amount of free space on each page. Just like Tom suggested
(http://archives.postgresql.org/pgsql-hackers/2007-11/msg00204.php). The
paper calls this the Free Space Inventory Page, or FSIP.

The problem is efficiently finding a page with X bytes from the FSIP.
The algorithms surveyed in that paper aim to solve that problem, and
they're all pretty simple. The general trick is to cache some of the
information in the FSIP, so that you don't always have to linearly scan it.

Another nice property of the FSIP is that you can quickly get a summary
of the distribution of the free space, and sum of free space and
utilization %.

I still feel the FSM should be in a file of it's own, rather than
distributed on every nth heap page. It makes scanning it quicker,
because it's sequential rather than random access, we're going to need a
solution for indexes as well, and using the special area of heap pages
would make the locking quite tricky.

I think we can, however, mix the visibility map with the FSM. The
visibility map would be spread over many more pages that way, which
might affect scan performance. But it'd also ease the potential lock
contention of updates, and you could then update the FSM and the
visibility map in one operation.

Just thinking ahead...

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

On Thu, 2007-11-08 at 15:24 +0000, Heikki Linnakangas wrote:
> I still feel the FSM should be in a file of it's own, rather than
> distributed on every nth heap page. It makes scanning it quicker,
> because it's sequential rather than random access, we're going to need
> a
> solution for indexes as well, and using the special area of heap
> pages
> would make the locking quite tricky.

I'd like to see the analysis on each side of that decision, so we can
decide openly.

The pages might well be in cache, so the file location might well be
irrelevant from an I/O perspective. Maybe. The nth page solution allows
the FSM block to be easily located without any FSM index, so might well
be faster. Separate files mean more space and more fsyncs too. But even
so, I'm not sure either way.

Presumably we would not store an FSM for small tables? On the basis that
the purpose of the FSM is to save on pointless I/O there must be a size
of table below which an FSM is just overhead.

--
Simon Riggs
2ndQuadrant http://www.2ndQuadrant.com

"Simon Riggs" <simon(at)2ndquadrant(dot)com> writes:

> The pages might well be in cache, so the file location might well be
> irrelevant from an I/O perspective. Maybe. The nth page solution allows
> the FSM block to be easily located without any FSM index, so might well
> be faster. Separate files mean more space and more fsyncs too. But even
> so, I'm not sure either way.

I don't follow any of the logical leaps in this paragraph.
[We talked about this...]

Why would having the FSM info be physically addressed into every nth page of
the heap allow FSM blocks to be more easily found than having them be
physically addressed in a separate file? Why would separate files mean more
space or more fsyncs?

> Presumably we would not store an FSM for small tables? On the basis that
> the purpose of the FSM is to save on pointless I/O there must be a size
> of table below which an FSM is just overhead.

That's one of the advantages of using separate files. It would be easy to have
or not have a whole file. It would be pretty hard to know whether the bits
spread on every nth page are missing and hard to add them later if the table
grows and they're needed.

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com
Ask me about EnterpriseDB's PostGIS support!

Simon Riggs wrote:

> Presumably we would not store an FSM for small tables? On the basis that
> the purpose of the FSM is to save on pointless I/O there must be a size
> of table below which an FSM is just overhead.

Hmm, do you mean that we would open and verify every page of a small
relation until we find one with free space? That doesn't sound very
good.

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

On Thu, 2007-11-08 at 23:04 +0000, Gregory Stark wrote:
> "Simon Riggs" <simon(at)2ndquadrant(dot)com> writes:
>
> > The pages might well be in cache, so the file location might well be
> > irrelevant from an I/O perspective. Maybe. The nth page solution allows
> > the FSM block to be easily located without any FSM index, so might well
> > be faster. Separate files mean more space and more fsyncs too. But even
> > so, I'm not sure either way.
>
> I don't follow any of the logical leaps in this paragraph.

I asked Heikki to explain why he felt the design should go a certain
way, which he didn't do. That's the logical leap I'm worried about.

I repeat: I'm not sure either way.

--
Simon Riggs
2ndQuadrant http://www.2ndQuadrant.com

Alvaro Herrera wrote:
> Simon Riggs wrote:
>> Presumably we would not store an FSM for small tables? On the basis that
>> the purpose of the FSM is to save on pointless I/O there must be a size
>> of table below which an FSM is just overhead.
>
> Hmm, do you mean that we would open and verify every page of a small
> relation until we find one with free space? That doesn't sound very
> good.

There is a threshold somewhere. If the heap consists of just one page,
clearly the FSM doesn't give any benefit. If it's two pages, it's
probably still faster to just check the two pages. Somewhere after that
the FSM starts to pay off.

Whether the overhead is big enough that we care to optimize by not
having the FSM for tiny tables, I don't know. Probably not. If the FSM
is stored in the heap file, it's tricky to add the FSM after the fact.
If it's a separate file, creating the FSM requires catalog changes.

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

On Thu, 2007-11-08 at 21:50 -0300, Alvaro Herrera wrote:
> Simon Riggs wrote:
>
> > Presumably we would not store an FSM for small tables? On the basis that
> > the purpose of the FSM is to save on pointless I/O there must be a size
> > of table below which an FSM is just overhead.
>
> Hmm, do you mean that we would open and verify every page of a small
> relation until we find one with free space? That doesn't sound very
> good.

I was trying to guess at Heikki's reason for saying the FSM should be in
a separate file. If we have one extra file per table that seems like a
huge number of additional files, with space and fsync implications.
Let's wait and see what Heikki's answer is.

--
Simon Riggs
2ndQuadrant http://www.2ndQuadrant.com

Simon Riggs wrote:
> On Thu, 2007-11-08 at 23:04 +0000, Gregory Stark wrote:
>> "Simon Riggs" <simon(at)2ndquadrant(dot)com> writes:
>>
>>> The pages might well be in cache, so the file location might well be
>>> irrelevant from an I/O perspective. Maybe. The nth page solution allows
>>> the FSM block to be easily located without any FSM index, so might well
>>> be faster. Separate files mean more space and more fsyncs too. But even
>>> so, I'm not sure either way.
>> I don't follow any of the logical leaps in this paragraph.
>
> I asked Heikki to explain why he felt the design should go a certain
> way, which he didn't do. That's the logical leap I'm worried about.

Well, it's just intuition at this point.

Some points I did already mention:
- The locking is harder. At least the visibility map will require
holding a lock on the heap page and the visibility map page at the same
time.
- We need a solution for the indexes as well. A separate file would fit
nicely for them, though the contents would be different because for
indexes we only care if a page is unused or not.
- Using a separate file, the FSM pages will be closer together, which is
good if you need to scan them.

On the other hand:
- Using more files requires more file handles
- Using every nth heap page requires no changes to catalog or buffer manager

Either way, you don't need any FSM index to locate a page.

I did consider other data structures as well, like a B-tree, keyed by
block number. Or a heap, with page with most free space at the top. But
a big problem with them is that as they are more complex, you need more
care to make them crash-safe. And you might even need some kind of free
space management for the FSM itself.

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

Simon Riggs wrote:
> On Thu, 2007-11-08 at 21:50 -0300, Alvaro Herrera wrote:
>> Simon Riggs wrote:
>>
>>> Presumably we would not store an FSM for small tables? On the basis that
>>> the purpose of the FSM is to save on pointless I/O there must be a size
>>> of table below which an FSM is just overhead.
>> Hmm, do you mean that we would open and verify every page of a small
>> relation until we find one with free space? That doesn't sound very
>> good.
>
> I was trying to guess at Heikki's reason for saying the FSM should be in
> a separate file. If we have one extra file per table that seems like a
> huge number of additional files, with space and fsync implications.

You need the same amount of space either way. Well, I guess additional
files consume some space in the filesystem directory structures. I doubt
that matters.

You do need more fsyncs, and more overhead when creating/dropping
relations, to create/unlink the FSM files. I don't know how significant
that is.

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

On Fri, 2007-11-09 at 09:39 +0000, Heikki Linnakangas wrote:
> Simon Riggs wrote:
> > On Thu, 2007-11-08 at 23:04 +0000, Gregory Stark wrote:
> >> "Simon Riggs" <simon(at)2ndquadrant(dot)com> writes:
> >>
> >>> The pages might well be in cache, so the file location might well be
> >>> irrelevant from an I/O perspective. Maybe. The nth page solution allows
> >>> the FSM block to be easily located without any FSM index, so might well
> >>> be faster. Separate files mean more space and more fsyncs too. But even
> >>> so, I'm not sure either way.
> >> I don't follow any of the logical leaps in this paragraph.
> >
> > I asked Heikki to explain why he felt the design should go a certain
> > way, which he didn't do. That's the logical leap I'm worried about.
>
> Well, it's just intuition at this point.

And yours is usually very good, I would be the first to applaud.

--
Simon Riggs
2ndQuadrant http://www.2ndQuadrant.com

On Fri, 2007-11-09 at 09:23 +0000, Heikki Linnakangas wrote:
> Alvaro Herrera wrote:
> > Simon Riggs wrote:
> >> Presumably we would not store an FSM for small tables? On the basis that
> >> the purpose of the FSM is to save on pointless I/O there must be a size
> >> of table below which an FSM is just overhead.
> >
> > Hmm, do you mean that we would open and verify every page of a small
> > relation until we find one with free space? That doesn't sound very
> > good.
>
> There is a threshold somewhere. If the heap consists of just one page,
> clearly the FSM doesn't give any benefit. If it's two pages, it's
> probably still faster to just check the two pages. Somewhere after that
> the FSM starts to pay off.

I think that might be set higher than two blocks. Smaller tables tend to
have lower insert rates. If we don't have an FSM for a table we can then
just pick a random block and then seqscan to locate a block. That would
allow heavily hit small tables to avoid much of the contention.

> Whether the overhead is big enough that we care to optimize by not
> having the FSM for tiny tables, I don't know. Probably not. If the FSM
> is stored in the heap file, it's tricky to add the FSM after the fact.

Could we make a specific block number the FSM block. Say block 13, plus
other periodically throughout the table, according to how many data
blocks an FSM block serves? That way a table smaller than that doesn't
have an FSM block, plus we can just insert the FSM block naturally as
part of the insert process without filesystem operations, catalog
changes etc.. SeqScans can just step over that block.

Binary upgrades would be somewhat harder, but not that much.

If we have a separate file for each FSM then we are going to use up
considerably more shared memory for the FSM than we do now, since each
block would be 8k. Plus all the filesystem ops.

Anyway, I'm just asking for an analysis either way. I wouldn't call the
FSM-in-the-heap idea truly wonderful and it definitely isn't my idea, so
not wedded to it.

--
Simon Riggs
2ndQuadrant http://www.2ndQuadrant.com

Heikki Linnakangas wrote:

> - We need a solution for the indexes as well. A separate file would fit
> nicely for them, though the contents would be different because for indexes
> we only care if a page is unused or not.

FWIW I think it's worth considering that we may be interested in keeping
closer track of free space in index pages, so that we can eventually
implement some heuristic for when to merge partially-empty pages.

--
Alvaro Herrera http://www.amazon.com/gp/registry/CTMLCN8V17R4

Heikki Linnakangas wrote:
> Alvaro Herrera wrote:
>> Simon Riggs wrote:
>>> Presumably we would not store an FSM for small tables? On the basis that
>>> the purpose of the FSM is to save on pointless I/O there must be a size
>>> of table below which an FSM is just overhead.
>> Hmm, do you mean that we would open and verify every page of a small
>> relation until we find one with free space? That doesn't sound very
>> good.
>
> There is a threshold somewhere. If the heap consists of just one page,
> clearly the FSM doesn't give any benefit. If it's two pages, it's probably
> still faster to just check the two pages. Somewhere after that the FSM
> starts to pay off.

Right. If you have a 1-page table, and put the first FSM page in page
0, the table is now two pages, so there is a 50% wastage. But if the
table grows you cannot move all the tuples from page 0 to create the FSM
there. On the other hand, all tables are 1 page long at a certain
point.

One idea is to have the first FSM page be movable, and create it by
extending the table when as soon as it's first "needed" (this would be
the first vacuum that needs to record free space on the table). The
page number used is recorded in the relcache entry (and pg_class).
Further FSM pages use a fixed position. If the table grows beyond the
first fixed position before creating the first FSM page, reserve that
one for the first FSM page and record that.

However I agree this starts to get a little too complex, and the idea of
storing it in a separate file is suddenly attractive.

> Whether the overhead is big enough that we care to optimize by not having
> the FSM for tiny tables, I don't know. Probably not. If the FSM is stored
> in the heap file, it's tricky to add the FSM after the fact. If it's a
> separate file, creating the FSM requires catalog changes.

Creating the FSM is a one-time operation, so I wouldn't be very worried
about performance considerations.

--
Alvaro Herrera http://www.CommandPrompt.com/
PostgreSQL Replication, Consulting, Custom Development, 24x7 support

Alvaro Herrera wrote:
> One idea is to have the first FSM page be movable, and create it by
> extending the table when as soon as it's first "needed" (this would be
> the first vacuum that needs to record free space on the table). The
> page number used is recorded in the relcache entry (and pg_class).
> Further FSM pages use a fixed position. If the table grows beyond the
> first fixed position before creating the first FSM page, reserve that
> one for the first FSM page and record that.

It wouldn't need to be movable. We could just allocate the first FSM
page when the table grows bigger than say 10 pages. The first FSM page
would always be at block 11, and it could store the free space
information for pages 0-10 as well.

I'm not particularly worried about the bloat on small tables, though. If
a table that used to take 8k bytes now takes 16k, who cares. You
wouldn't need to load the FSM pages to shared buffers unless the FSM is
actually used.

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

On Fri, 2007-11-09 at 13:27 +0000, Heikki Linnakangas wrote:
> Alvaro Herrera wrote:
> > One idea is to have the first FSM page be movable, and create it by
> > extending the table when as soon as it's first "needed" (this would be
> > the first vacuum that needs to record free space on the table). The
> > page number used is recorded in the relcache entry (and pg_class).
> > Further FSM pages use a fixed position. If the table grows beyond the
> > first fixed position before creating the first FSM page, reserve that
> > one for the first FSM page and record that.
>
> It wouldn't need to be movable. We could just allocate the first FSM
> page when the table grows bigger than say 10 pages. The first FSM page
> would always be at block 11, and it could store the free space
> information for pages 0-10 as well.
>
> I'm not particularly worried about the bloat on small tables, though. If
> a table that used to take 8k bytes now takes 16k, who cares. You
> wouldn't need to load the FSM pages to shared buffers unless the FSM is
> actually used.

I'm more worried about the shared memory space we would waste if we have
FSM blocks for very small tables.

Now we use very few bytes per block, which is memory efficient for lots
of small tables and bad with lots of large tables. Putting the FSM in
blocks might change that the other way around.

--
Simon Riggs
2ndQuadrant http://www.2ndQuadrant.com

Just a small thought. If the file decision is preferred, then it might
be worth considering to create a file per tablespace.

Thanks,
Gokul.

On Nov 9, 2007 7:15 PM, Simon Riggs <simon(at)2ndquadrant(dot)com> wrote:
> On Fri, 2007-11-09 at 13:27 +0000, Heikki Linnakangas wrote:
> > Alvaro Herrera wrote:
> > > One idea is to have the first FSM page be movable, and create it by
> > > extending the table when as soon as it's first "needed" (this would be
> > > the first vacuum that needs to record free space on the table). The
> > > page number used is recorded in the relcache entry (and pg_class).
> > > Further FSM pages use a fixed position. If the table grows beyond the
> > > first fixed position before creating the first FSM page, reserve that
> > > one for the first FSM page and record that.
> >
> > It wouldn't need to be movable. We could just allocate the first FSM
> > page when the table grows bigger than say 10 pages. The first FSM page
> > would always be at block 11, and it could store the free space
> > information for pages 0-10 as well.
> >
> > I'm not particularly worried about the bloat on small tables, though. If
> > a table that used to take 8k bytes now takes 16k, who cares. You
> > wouldn't need to load the FSM pages to shared buffers unless the FSM is
> > actually used.
>
> I'm more worried about the shared memory space we would waste if we have
> FSM blocks for very small tables.
>
> Now we use very few bytes per block, which is memory efficient for lots
> of small tables and bad with lots of large tables. Putting the FSM in
> blocks might change that the other way around.
>
> --
> Simon Riggs
> 2ndQuadrant http://www.2ndQuadrant.com
>
>
> ---------------------------(end of broadcast)---------------------------
>
> TIP 1: if posting/reading through Usenet, please send an appropriate
> subscribe-nomail command to majordomo(at)postgresql(dot)org so that your
> message can get through to the mailing list cleanly
>