Re: Hash index todo list item

Kenneth Marshall wrote: <blockquote cite="mid:20070907132928.GC19403@it.is.rice.edu" type="cite"><pre wrap="">On Thu,
Sep06, 2007 at 11:56:25PM -0700, Neil Conway wrote: </pre><blockquote type="cite"><pre wrap="">You might find this
patchuseful:
 
   <a class="moz-txt-link-freetext"
href="http://archives.postgresql.org/pgsql-patches/2005-05/msg00164.php">http://archives.postgresql.org/pgsql-patches/2005-05/msg00164.php</a>
...

Unfortunately, the patch doesn't apply cleanly to HEAD, but I can merge
it up to HEAD if you'd like.   </pre></blockquote><pre wrap="">This is a great starting point. I would appreciate it if
youhave 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. </pre></blockquote> What do you mean by "mark the unique items in the index then they do not actually have to be
recheckedduring the scan." Even if there is a unique hash value mapping to a unique key, there is no guarantee that a
newvalue 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
forthe value does not exist.<br /><br /> Have you measured the performance of re-checking? I have always assumed the
performanceof re-checking was near free when compared to the cost of looking up the tuples in the table to determine
whetheror not they are "live". This is why I have not been upset that bitmap index scans often re-check.<br /><br />
Cheers,<br/> mark<br /><br /><pre class="moz-signature" cols="72">-- 
 
Mark Mielke <a class="moz-txt-link-rfc2396E" href="mailto:mark@mielke.cc"><mark@mielke.cc></a>
</pre>