Re: Dead Space Map for vacuum

ITAGAKI Takahiro wrote:
> Hello,
>
> NTT staffs are working on TODO item:
> | Create a bitmap of pages that need vacuuming
>
> We call the bitmap "Dead Space Map" (DSM), that allows VACUUM to scan
> only pages that need vacuuming or freezing. We'd like to discuss the
> design on hackers and make agreements with community.

Great!

> We implemented the basic parts of it and measured the performance.
> As expected, VACUUM took shorter time when the fraction of updates are low.
> DSM is useful for large but not so heavily-updated databases. The overhead
> of managing DSM seemed to be negligible small in our CPU-loaded tests.
>
> There are a lot of choices in implementation. We followed the descriptions
> in TODO list and past discussions in some parts, but did not in other parts
> for some reasons. I would appreciate your comments and suggestions.

I experimented with a different DSM design last winter. I got busy with
other things and never posted it AFAIR, but the idea was to store a
bitmap in the special area on every 32k heap page. That had some advantages:

* doesn't require a new dedicated shared memory area that needs to be
allocated and tuned.
* doesn't introduce a (single) new global lwlock that might become hotspot.
* WAL logging is quite simple, since the bitmaps are on normal pages
handled by buffer manager.

I had it working enough to see that vacuum time was shortened, but I
didn't perform any further performance testing.

> | In the event of a system crash, the bitmap would probably be invalidated.
>
> We bought it for simplicity. Currently, all DSM are lost after crash.
> All tables will be untracked status. Full-scanned vacuum is needed
> after the lost of DSM.

If you flush the DSM to disk at checkpoint, it should be easy to bring
it up-to-date on WAL replay. Having to do full-scanning vacuum after
crash can be a nasty surprise.

> | One complexity is that index entries still have to be vacuumed, and doing
> | this without an index scan (by using the heap values to find the index entry)
> | might be slow and unreliable, especially for user-defined index functions.
>
> Indexes are still needed to be full-scanned at the present moment. We are
> also researching a retail index vacuum method, but it requires more works.

Yeah, that's an old story :(.

BTW: Yesterday I realized that bitmap indexes could be retail vacuumed
safely. You'll still need to visit all bitmaps to find the dead bit, but
you only need to check the bitmap page that corresponds the tid of the
dead tuple.

> | http://archives.postgresql.org/pgsql-hackers/2004-03/msg00957.php
> | Maintain 2 bits per block that tell if the block has been vaccumed of all
> | dead tuples since the last time it was dirtied, and if all its tuples are
> | completely frozen.
>
> We use 1 bit per block, so we cannot separate pages that need either
> vacuum or freeze only. The reason is that we cannot determine where to
> record before/after updated tuples. If the transaction is commited,
> before-version should be recorded into needs-vacuum bitmap and
> after-version into needs-freeze bitmap. But on rollback, it is inverted.
> We cannot judge which we should do until the end of transaction.

Yeah, that makes the DSM less useful. Are you thinking of freezing more
aggressively because of that? Or doing a full-scanning vacuum every now
and then to freeze?

> | [TODO item] Allow data to be pulled directly from indexes
> | Another idea is to maintain a bitmap of heap pages where all rows are
> | visible to all backends, and allow index lookups to reference that bitmap
> | to avoid heap lookups
>
> It is not done yet, but we can use DSM for this purpose. If the corresponding
> bit in DSM is '0', all tuples in the page are frozen and visible to all
> backends. We don't have to look up frozen pages only for visibiliby checking.

Cool.

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