Re: Hash index todo list item - Mailing list pgsql-hackers

From Mark Mielke
Subject Re: Hash index todo list item
Date
Msg-id 46E310A1.8000008@mark.mielke.cc
Whole thread Raw
In response to Re: Hash index todo list item  (Kenneth Marshall <ktm@rice.edu>)
Responses Re: Hash index todo list item
List pgsql-hackers
Kenneth Marshall wrote:<br /><blockquote cite="mid:20070908202122.GA5679@it.is.rice.edu" type="cite"><pre
wrap="">Continuingthis train of thought.... While it would make sense for larger
 
keys to store the hash in the index, if the key is smaller, particularly
if it is of fixed size, it would make sense to store the key in the index
instead. This would have the benefit of allowing use of the hash index
in non-lossy mode albeit with a slight increase in complexity. </pre></blockquote> I suspect there is no value in
designinga hash implementation to work well for a context where a btree index would already perform equally well.<br
/><br/> If there are too few hash buckets, performance is not O(1). For a hash index to function better than btree, I
believefocus should be spent on the O(1) case, which means ensuring that enough hash buckets are used to provide
O(1).<br/><br /> All of these must match: 1) Hash value, 2) Key value, 3) Tuple visibility.<br /><br /> In the optimum
O(1)scenario, each existing key will map to a hash bucket that contains ~1 entry. For this case, there is no value to
havingthe key stored in the index row, as 3) Tuple visibility, will still require access to the table row. In this
optimumscenario, I do not believe anything of value is saved by storing the key in the index row. The loss, however, is
thatthe hash index data structures become more complex, and would likely require support for variable length data. The
resultingincrease in hash index size and code complexity would reduce performance.<br /><br /> Just an opinion.<br
/><br/> Cheers,<br /> mark<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>

pgsql-hackers by date:

Previous
From: Markus Schiltknecht
Date:
Subject: Re: WIP patch for latestCompletedXid method of computing snapshot xmax
Next
From: Josh Berkus
Date:
Subject: Re: WIP patch for latestCompletedXid method of computing snapshot xmax