Re: Including Snapshot Info with Indexes

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