Thread

1. Re: HASH: Out of overflow pages. Out of luck

   Hannu Krosing <hannu@tm.ee> — 2002-08-05T00:49:21Z

   On Mon, 2002-08-05 at 07:26, Gene Selkov, Jr. wrote:
   > Hi Everybody!
   > 
   > I'm sorry I dropped out for so long -- was switching jobs and was on
   > the verge of deportation for a while. Still not entirely back to
   > normal, but can raise my head and look around.
   > 
   > The first thing I discovered in the current version (7.2.1) -- as well
   > as in 7.1.3 -- seems to be an old problem with the hash am. It's
   > clustering too much. 
   
   ...
   
   > The quality of the hash function can be a factor here, but probably
   > not the major one. I was able to jack my limit up to over 3.7M rows by
   > reversing the order of bytes in hashvarlena() -- I made the pointer go
   > down instead of up. That spread the hash values more sparsely, but it
   > failed with the same message when I fed it with more than 4M rows.
   > 
   > I saw Tom answer a similar question a year ago, by saying that the
   > hash access method is poorly supported and that there is no advantage
   > to using it. I am not sure about the former, but the latter is not
   > entirely true: we saw at least 20% gain in performance when we
   > switched from btree to hash, and my boss considers 20% a big enough
   > improvement. Besides, he knows the database theory and he is a
   > long-time BerkelyDB user,
   
   As BerkelyDB came into being by splitting index methods out of an early
   version of Postgres, it should still have some similar structure left,
   so one possibility is to check what they are doing to not be that bad.
   
   Have you tried to index your dataset into a BerkelyDB database ?
   
   > and in his world, hash is greatly superior
   > to btree, so he is wondering why are the postgres implementations so
   > close. Besides, it's a tough challenge to explain it to a Libertarian
   > that he'd better not do something.
   
   -------------
   Hannu
   
   
   

2. HASH: Out of overflow pages. Out of luck

   Gene Selkov Jr. <selkovjr@xnet.com> — 2002-08-05T02:26:16Z

   Hi Everybody!
   
   I'm sorry I dropped out for so long -- was switching jobs and was on
   the verge of deportation for a while. Still not entirely back to
   normal, but can raise my head and look around.
   
   The first thing I discovered in the current version (7.2.1) -- as well
   as in 7.1.3 -- seems to be an old problem with the hash am. It's
   clustering too much. 
   
   The data I'm trying to index is of the type text, so it uses hashvarlena(). The values
   are something like this:
   
   REC00014
   REC00015
   ....
   REC02463
   RBS00001
   RBS00002
   ....
   RBS11021
   ....
   
   It's like several very long sequences with multiple gaps. 
   
   With the existing hashvarlena(), I can index about 2M rows, but not
   much more -- it comes back with the message about the overflow pages.
   
   hashvarlena() responds to this input in a piecewise linear fashion. That is,
   the succession 'REC00010' .. 'REC00019' results in a linear order
   1346868191 .. 1346868200. The next ten hash values will also be sequential, 
   but in a different range. 
   
   The quality of the hash function can be a factor here, but probably
   not the major one. I was able to jack my limit up to over 3.7M rows by
   reversing the order of bytes in hashvarlena() -- I made the pointer go
   down instead of up. That spread the hash values more sparsely, but it
   failed with the same message when I fed it with more than 4M rows.
   
   I saw Tom answer a similar question a year ago, by saying that the
   hash access method is poorly supported and that there is no advantage
   to using it. I am not sure about the former, but the latter is not
   entirely true: we saw at least 20% gain in performance when we
   switched from btree to hash, and my boss considers 20% a big enough
   improvement. Besides, he knows the database theory and he is a
   long-time BerkelyDB user, and in his world, hash is greatly superior
   to btree, so he is wondering why are the postgres implementations so
   close. Besides, it's a tough challenge to explain it to a Libertarian
   that he'd better not do something.
   
   I guess we can make such people happy by either fixing hash, or by
   making btree very much worse -- whichever is easier :)
   
   Seriously, though, if anybody wants to look at the problem, I saved
   the set of keys that caused it as
   
   http://home.xnet.com/~selkovjr/tmp/prot.gz
   
   Also, I heard that other database systems have special access methods
   for sequences, that address this issue, and I heard as well that
   without an option to use an arbitrary hash function instead of a
   single built-in, such problems are bound to happen with particular
   data sets. How true is that? If a better access method exists, what is
   it?
   
   Thank you,
   
   Gene
   
   
   
   

3. Re: HASH: Out of overflow pages. Out of luck

   Christopher Kings-Lynne <chriskl@familyhealth.com.au> — 2002-08-05T02:36:57Z

   > I saw Tom answer a similar question a year ago, by saying that the
   > hash access method is poorly supported and that there is no advantage
   > to using it. I am not sure about the former, but the latter is not
   > entirely true: we saw at least 20% gain in performance when we
   > switched from btree to hash, and my boss considers 20% a big enough
   > improvement. Besides, he knows the database theory and he is a
   > long-time BerkelyDB user, and in his world, hash is greatly superior
   > to btree, so he is wondering why are the postgres implementations so
   > close. Besides, it's a tough challenge to explain it to a Libertarian
   > that he'd better not do something.
   >
   > I guess we can make such people happy by either fixing hash, or by
   > making btree very much worse -- whichever is easier :)
   
   Cool.  I'm sure that making btree much worse is definitely within my
   ability - I'll submit a patch shortly with new pg_bench results.
   
   Chris
   
   
   

4. Re: HASH: Out of overflow pages. Out of luck

   Tom Lane <tgl@sss.pgh.pa.us> — 2002-08-05T03:13:14Z

   "Gene Selkov, Jr." <selkovjr@xnet.com> writes:
   > I saw Tom answer a similar question a year ago, by saying that the
   > hash access method is poorly supported and that there is no advantage
   > to using it. I am not sure about the former, but the latter is not
   > entirely true: we saw at least 20% gain in performance when we
   > switched from btree to hash, and my boss considers 20% a big enough
   > improvement. Besides, he knows the database theory and he is a
   > long-time BerkelyDB user, and in his world, hash is greatly superior
   > to btree, so he is wondering why are the postgres implementations so
   > close. Besides, it's a tough challenge to explain it to a Libertarian
   > that he'd better not do something.
   
   Hey, if he wants to fix the hash code, more power to him ;-).  Patches
   will be gladly accepted.
   
   The real problem with the PG hash index code is that approximately zero
   effort has been put into it since the code left Berkeley, while quite
   a lot of work has been put into the btree code.  Thus, for most purposes
   the btree index type leaves hash in the dust, no matter what theoretical
   concerns may say.
   
   If you or he would like to expend the effort to bring hash indexing up
   to speed, I'll surely not stand in your way.  But be advised that
   there's a lot of work to be done there (concurrency issues and WAL
   support being at the top of my list) ... are you sure you believe that
   hash is worth the effort?
   
   			regards, tom lane
   
   

5. Re: HASH: Out of overflow pages. Out of luck

   Gene Selkov Jr. <selkovjr@xnet.com> — 2002-08-07T05:41:04Z

   > From: Hannu Krosing <hannu@tm.ee>
   > 
   > As BerkelyDB came into being by splitting index methods out of an early
   > version of Postgres, it should still have some similar structure left,
   > so one possibility is to check what they are doing to not be that bad.
   > 
   > Have you tried to index your dataset into a BerkelyDB database ?
   
   Yes, it works fine with BerkelyDB. I looked at both codes and I was
   stupefied with their complexity. Even if there is a similar structure,
   it must be very well disguised. Some of the data structures resemble
   each other's counterparts; the only piece that is exactly the same
   as one of the five BerkelyDB's hash functions. 
   
   The only useful experiment that I feel I am capable of making is
   trying their __ham_hash5() function, with they claim is generally
   better than the other four, for most purposes. But they warn in their
   comments that there is no such thing as "a hash function" -- there
   must be one for each purpose.
   
   So another experiment I might try is writing an adapter for a
   user-supplied hash -- that might help in figuring out the role of the
   hash function in bin overflows. That should be easy enough to do, but
   fixing or re-writing the access method itself -- I'm sorry: the level 
   of complexity scares me. Appears like a couple man-months 
   (those Mythical Man-Months :).
   
   --Gene
   
   

6. Re: HASH: Out of overflow pages. Out of luck

   Neil Conway <nconway@klamath.dyndns.org> — 2002-08-07T14:46:58Z

   On Wed, Aug 07, 2002 at 12:41:04AM -0500, selkovjr@xnet.com wrote:
   > Some of the data structures resemble each other's counterparts;
   > the only piece that is exactly the same as one of the five
   > BerkelyDB's hash functions. 
   
   FYI, the development version of PostgreSQL uses a completely
   different (and higher quality) hash function.
   
   > The only useful experiment that I feel I am capable of making is
   > trying their __ham_hash5() function, with they claim is generally
   > better than the other four, for most purposes.
   
   I'm skeptical that changing the hash function would make a significant
   difference to the usability of hash indexes. At the very least, the
   reproducible deadlocks under concurrent access need to be fixed, as well
   as a host of other issues.
   
   Cheers,
   
   Neil
   
   -- 
   Neil Conway <neilconway@rogers.com>
   PGP Key ID: DB3C29FC