Re: Including Snapshot Info with Indexes

Hi Heikki,
I am always slightly late in understanding things. Let me try
to understand the use of DSM. It is a bitmap index on whether all the tuples
in a particular block is visible to all the backends, whether a particular
block contains tuples which are invisible to everyone. But i think this will
get subjected to the same limitations of Bitmap index. Even Oracle suggests
the use of Bitmap index for only data warehousing tables, where the Bitmap
indexes will be dropped and recreated after every bulk load. This is not a
viable alternative for OLTP transactions. But i think i am late in the game
as i haven't participated in those discussions
One Bitmap index block usually maps to lot of blocks in the heap.
So locking of one page to update the DSM for update/delete/insert would hit
the concurrency. But again all these are my observation w.r.t oracle bitmap
indexes. May be i am missing something in DSM.
I couldn't get that piece of discussion in the archive, which
discusses the design of Retail Vacuum. So please advise me again here.
Let's take up Retail Vacuuming again. The User defined function
which would return different values at different time can be classified as
non-deterministic functions. We can say that this index cannot be created
on a non-deterministic function. This is the way it is implemented in
Oracle. What they have done is they have classified certain built-in
operators and functions as deterministic. Similarly they have classified a
few as non-deterministic operators and functions. Can we follow a similar
approach?

Thanks,
Gokul.

On 10/8/07, Heikki Linnakangas <heikki(at)enterprisedb(dot)com> wrote:
>
> Gokulakannan Somasundaram wrote:
> > On 10/8/07, Heikki Linnakangas <heikki(at)enterprisedb(dot)com> wrote:
> >> IMO, the most promising approach to achieving index-only-scans at the
> >> moment is the Dead Space Map, as discussed in the 8.3 dev cycle.
> >
> > Index only scans means that in order to get certain results, we may not
> > goto the table at all. For example, if you have an index on columns a
> and b,
> > and if there is a query like "select b from table where a between a1 and
> > a2", then the explain plan need not goto the table. I can't understand
> how
> > dead space map will provide such a functionality.
>
> Please read the discussions in the archives. The dead space map holds
> visibility information in a condensed form. For index-only-scans, we
> need to know if all tuples on page are are visible to us. If the dead
> space map is designed with index-only-scans in mind, we can store a bit
> there indicating "all tuples on this page are visible to everyone".
> Pages that have that bit set don't need to be visited to check visibility.
>
> What information exactly is going to be stored in the dead space map is
> still debated. For vacuuming, we need to know which pages contain dead
> tuples that are worth vacuuming, which isn't the same thing as "all
> tuples are visible to everyone", but it's quite close.
>
> Heap pages that do have dead or recently modified rows do need to be
> visited, so the executor needs to always be prepared to check visibility
> from the heap. However, on a table that's not very frequently updated,
> most bits will be set and the effect will be the same as genuine
> index-only-scans. On a table that is frequently updated, you would
> suffer a big hit in update performance with the "duplicate visibility
> information in all indexes" scheme as well, as the updates would need to
> update the indexes as well, so the performance characteristics are
> roughly the same.
>
> > That's true. But i am not asking to replace the current index
> > implementation, but to provide an extra option while indexing. Say if a
> > particular database setup doesn't do much deletes and updates(imagine
> tables
> > with partitioning, where the partitions/tables are dropped instead of
> > deletes. They can have an option to "create index .. with snapshot"
>
> A nice property of utilizing the dead space map for index-only-scans is
> that it doesn't require any action from the DBA. It will "just work". It
> also adapts well to tables that have parts that are frequently updated,
> and other parts that are not. The frequently updated parts will behave
> like what we have now, index-only-scans are not possible because, but
> deletes/updates are cheap. But the less frequently updated parts will
> eventually have the bits set in the map, and we can do index-only-scans
> for those parts.
>
> > Imagine the Index Vacuum also will do lesser Random I/Os
>
> Index vacuum doesn't do random I/Os as it is.
>
> > Also, the full visibility information would need 12 bytes of space per
> >> tuple. An index tuple on an int4 key currently takes 12 bytes, so that
> >> would double the index size. Storage size has a big impact on
> >> performance. More bytes means more I/O, less data fits in cache, and
> >> more WAL traffic.
> >
> > I am thinking of certain optimizations here. we have a bit unused in
> > indextuple structure. If a particular tuple is not deleted, then we can
> > signify that using that bit and save 6 bytes of saving the xmax and
> cmax. We
> > are trading of this space efficiency in place of Random I/Os, which is
> not a
> > bad trade-off , i suppose. Again this is going to optional for the user.
> If
> > users have an option to create Bitmap index/ Binary index, why can't
> they
> > have this option as well?
>
> Because we have to maintain it? :)
>
> Speaking of bitmap indexes, that would be nice to have. It looks like
> Gavin dropped the ball on the patch, so if you want to continue that
> work, that would be great.
>
> > There's non-trivial implementation issues involved as well. You'd need a
> >> way to reliably find all the index pointers for a given heap tuple
> >> (search the archives for "retail vacuum" for the issues involved in
> >> that. Broken user defined functions are a problem for example). And
> >> you'd need to keep them all locked at the same time to modify them all
> >> atomically, which is prone to deadlocks.
> >
> > I think Vacuum need not goto the table, as the visibility information is
> > present in the index itself.
>
> Vacuum isn't the problem here. The problem is: given heap tuple X, how
> do you find the the corresponding index tuples? The obvious solution is
> to calculate the index keys from the heap tuple, and use them to look
> up. But what if you have an expression index on a user-defined function,
> and that user-defined function is broken so that it returns a different
> value than when the index tuple was inserted? You won't find the index
> tuples in that case, so you won't be able to update the visibility
> information. Granted, you've got a broken user-defined-function in that
> case, and you're going to get bogus query results anyway. But not
> finding the index tuple when needed would lead to more serious
> corruption. This is the same problem many proposed retail vacuum schemes
> have stumbled into, which is why I suggested searching for that.
>
> --
> Heikki Linnakangas
> EnterpriseDB http://www.enterprisedb.com
>