Re: Hash index todo list item

Kenneth Marshall wrote:
> On Thu, Sep 06, 2007 at 11:56:25PM -0700, Neil Conway wrote:
>
>> You might find this patch useful:
>>
>> http://archives.postgresql.org/pgsql-patches/2005-05/msg00164.php
>> ...
>>
>> Unfortunately, the patch doesn't apply cleanly to HEAD, but I can merge
>> it up to HEAD if you'd like.
>>
> This is a great starting point. I would appreciate it if you have the
> time and could make it apply cleanly to HEAD. I remember when you first
> posted it but had forgotten, probably because of the lack-luster results.
> Just a quick glance at the patch and from what I can tell, tagging the
> index as lossy causes a lot more work to be done than should be needed
> in theory. Currently the index-scan machinery will recheck the value
> against the original value for lossy indexes. However, given that we
> are using a good hash function with a low chance of collision, if we
> mark the unique items in the index then they do not actually have to
> be rechecked during the scan. Do you have any suggestions for implementing
> that optimization or is there any option to tell the scan machinery to
> only re-check a certain list of tuples? Thank you again for pointing
> this patch out and please let me know when you have a version against
> HEAD.
>
What do you mean by "mark the unique items in the index then they do not
actually have to be rechecked during the scan." Even if there is a
unique hash value mapping to a unique key, there is no guarantee that a
new value won't result in that same hash value. Such is the nature of
hashes. A hash key map does not mean a value match. The value must be
checked. The opposite, however, may be true. If the hash key is not
found, then we know the row for the value does not exist.

Have you measured the performance of re-checking? I have always assumed
the performance of re-checking was near free when compared to the cost
of looking up the tuples in the table to determine whether or not they
are "live". This is why I have not been upset that bitmap index scans
often re-check.

Cheers,
mark

--
Mark Mielke <mark(at)mielke(dot)cc>