[PATCH]-hash index improving

On Thu, Jul 17, 2008 at 5:26 AM, Xiao Meng <mx.cogito@gmail.com> wrote:

The patch store hash code only in the index tuple.
It based on Neil Conway's patch with an old version of PostgreSQL.
It passes the regression test but I didn't test the performance yet.
Anyone interested can make a performance test;-)
You can undefine the macro HASHVALUE_ONLY in hash.h to get the
original implementation.
It's a preliminary implementation and I'm looking for input here.
Hope to hear from you.

Tom, Simon, Heikki, Greg, we need to make sure this SoC project
succeeds and would appreciate your review and input.

Based on some of Kenneth Marshall and Tom Raney's past hash index test
cases, Xiao and I are going to work on some benchmarks for measuring
the performance-related aspects of this project.

Thanks!

--
Jonah H. Harris, Sr. Software Architect | phone: 732.331.1324
EnterpriseDB Corporation | fax: 732.331.1301
499 Thornall Street, 2nd Floor | jonah.harris@enterprisedb.com
Edison, NJ 08837 | http://www.enterprisedb.com/

Xiao Meng escribi�:

The patch store hash code only in the index tuple.
It based on Neil Conway's patch with an old version of PostgreSQL.
It passes the regression test but I didn't test the performance yet.
Anyone interested can make a performance test;-)
You can undefine the macro HASHVALUE_ONLY in hash.h to get the
original implementation.

I think having the HASHVALUE_ONLY define is not a good idea -- it just
makes the patch harder to read. I suggest just removing the old code
and putting the new code in place. (That's why we have revision
control.)

--
Alvaro Herrera http://www.CommandPrompt.com/
The PostgreSQL Company - Command Prompt, Inc.

On Thu, Jul 17, 2008 at 12:42 PM, Alvaro Herrera
<alvherre@commandprompt.com> wrote:

I think having the HASHVALUE_ONLY define is not a good idea -- it just
makes the patch harder to read. I suggest just removing the old code
and putting the new code in place. (That's why we have revision
control.)

Agreed. I'm also getting a crash on it with large data sets, so we'll
make sure to get those fixed in the next version of the patch.

-Jonah

On Thu, Jul 17, 2008 at 12:42:39PM -0400, Alvaro Herrera wrote:

Xiao Meng escribi?:

The patch store hash code only in the index tuple.
It based on Neil Conway's patch with an old version of PostgreSQL.
It passes the regression test but I didn't test the performance yet.
Anyone interested can make a performance test;-)
You can undefine the macro HASHVALUE_ONLY in hash.h to get the
original implementation.

I think having the HASHVALUE_ONLY define is not a good idea -- it just
makes the patch harder to read. I suggest just removing the old code
and putting the new code in place. (That's why we have revision
control.)

One thing it helps is building an old version and a new version
for comparative testing. Otherwise, you could end up with an apples-to-
oranges comparison. I certainly think that the final patch should not
have it, but it is useful now for testing and comparisons.

My two cents,
Ken

On Thu, Jul 17, 2008 at 1:54 PM, Kenneth Marshall <ktm@rice.edu> wrote:

I think having the HASHVALUE_ONLY define is not a good idea -- it just
makes the patch harder to read. I suggest just removing the old code
and putting the new code in place. (That's why we have revision
control.)

One thing it helps is building an old version and a new version
for comparative testing. Otherwise, you could end up with an apples-to-
oranges comparison. I certainly think that the final patch should not
have it, but it is useful now for testing and comparisons.

Yes, that's why Xiao did it that way. However, we traditionally just
submit a patch with only the changes and it's up to the person testing
to have an identical build-tree without the patch for testing.
Another reason for it is that even if you build without the define,
the patch author may have mistakenly added something outside the ifdef
which could impact testing.

I agree with Alvaro that we should submit it as a standard change patch.

--
Jonah H. Harris, Sr. Software Architect | phone: 732.331.1324
EnterpriseDB Corporation | fax: 732.331.1301
499 Thornall Street, 2nd Floor | jonah.harris@enterprisedb.com
Edison, NJ 08837 | http://www.enterprisedb.com/

On Thu, Jul 17, 2008 at 02:00:07PM -0400, Jonah H. Harris wrote:

On Thu, Jul 17, 2008 at 1:54 PM, Kenneth Marshall <ktm@rice.edu> wrote:

I think having the HASHVALUE_ONLY define is not a good idea -- it just
makes the patch harder to read. I suggest just removing the old code
and putting the new code in place. (That's why we have revision
control.)

One thing it helps is building an old version and a new version
for comparative testing. Otherwise, you could end up with an apples-to-
oranges comparison. I certainly think that the final patch should not
have it, but it is useful now for testing and comparisons.

Yes, that's why Xiao did it that way. However, we traditionally just
submit a patch with only the changes and it's up to the person testing
to have an identical build-tree without the patch for testing.
Another reason for it is that even if you build without the define,
the patch author may have mistakenly added something outside the ifdef
which could impact testing.

I agree with Alvaro that we should submit it as a standard change patch.

Okay, that makes sense.

Ken

Kenneth Marshall escribi�:

On Thu, Jul 17, 2008 at 12:42:39PM -0400, Alvaro Herrera wrote:

I think having the HASHVALUE_ONLY define is not a good idea -- it just
makes the patch harder to read. I suggest just removing the old code
and putting the new code in place. (That's why we have revision
control.)

One thing it helps is building an old version and a new version
for comparative testing. Otherwise, you could end up with an apples-to-
oranges comparison. I certainly think that the final patch should not
have it, but it is useful now for testing and comparisons.

For this purpose I think it would be easier to have a separate tree with
the patch, and one without it.

--
Alvaro Herrera http://www.CommandPrompt.com/
PostgreSQL Replication, Consulting, Custom Development, 24x7 support

On Thu, Jul 17, 2008 at 5:26 AM, Xiao Meng <mx.cogito@gmail.com> wrote:

The patch store hash code only in the index tuple.
It based on Neil Conway's patch with an old version of PostgreSQL.
It passes the regression test but I didn't test the performance yet.
Anyone interested can make a performance test;-)
You can undefine the macro HASHVALUE_ONLY in hash.h to get the
original implementation.
It's a preliminary implementation and I'm looking for input here.
Hope to hear from you.

I've spent some time today performing tests similar to those mentioned
here (http://archives.postgresql.org/pgsql-hackers/2007-09/msg00208.php)

Using a word list of 2650024 unique words (maximum length is 118
bytes), build times are still high, but I'm not really seeing any
performance improvements over b-tree. I haven't profiled it yet, but
my test is as follows:

- Created the dict table
- Loaded the dict table
- Counted the records in the dict table
- Created the index
- Shutdown the database
- Randomly selected 200 entries from the word list and built a file
full of (SELECT * FROM dict WHERE word = '<word>') queries using them.
- Cleared out the kernel cache
- Started the database
- Ran the query file

The result of this is between 5-10ms improvement in the overall
execution time of all 200 queries. The time-per-query is practically
unnoticeable. As this is in the range of noise, methinks there's a
larger problem with hash indexes. I haven't looked heavily into their
implementation, but do you any of you know of any major design flaws?

--
Jonah H. Harris, Sr. Software Architect | phone: 732.331.1324
EnterpriseDB Corporation | fax: 732.331.1301
499 Thornall Street, 2nd Floor | jonah.harris@enterprisedb.com
Edison, NJ 08837 | http://www.enterprisedb.com/

On Thu, Jul 17, 2008 at 04:24:28PM -0400, Jonah H. Harris wrote:

On Thu, Jul 17, 2008 at 5:26 AM, Xiao Meng <mx.cogito@gmail.com> wrote:

The patch store hash code only in the index tuple.
It based on Neil Conway's patch with an old version of PostgreSQL.
It passes the regression test but I didn't test the performance yet.
Anyone interested can make a performance test;-)
You can undefine the macro HASHVALUE_ONLY in hash.h to get the
original implementation.
It's a preliminary implementation and I'm looking for input here.
Hope to hear from you.

I've spent some time today performing tests similar to those mentioned
here (http://archives.postgresql.org/pgsql-hackers/2007-09/msg00208.php)

Using a word list of 2650024 unique words (maximum length is 118
bytes), build times are still high, but I'm not really seeing any
performance improvements over b-tree. I haven't profiled it yet, but
my test is as follows:

- Created the dict table
- Loaded the dict table
- Counted the records in the dict table
- Created the index
- Shutdown the database
- Randomly selected 200 entries from the word list and built a file
full of (SELECT * FROM dict WHERE word = '<word>') queries using them.
- Cleared out the kernel cache
- Started the database
- Ran the query file

The result of this is between 5-10ms improvement in the overall
execution time of all 200 queries. The time-per-query is practically
unnoticeable. As this is in the range of noise, methinks there's a
larger problem with hash indexes. I haven't looked heavily into their
implementation, but do you any of you know of any major design flaws?

Jonah,

Thank you for running these tests. I was trying to reproduce my initial
tests on the original system to make it more apples to apples, but the
latest release needs more resources semaphore-wise than the 8.2 and
to fix it on Solaris 8 I will need a reboot. Would you mind posting
the timings for the hash_only index versus the hash_value versus the
btree index for the same test. Also, what is the on-disk size of all
three indexes? This will allow us to figure out the bucket/page load
or fill-factor for each scenario.

The basic implementation looked reasonable. I will take a look at
the patch this evening.

Regards,
Ken

On Thu, 2008-07-17 at 16:24 -0400, Jonah H. Harris wrote:

I'm not really seeing any performance improvements over b-tree.

I'd like to see a theoretical analysis on the benefit case before we
spend too many teraflops on investigation.

In which cases do we expect that hash indexes will beat btrees?

--
Simon Riggs www.2ndQuadrant.com
PostgreSQL Training, Services and Support

-----Original Message-----

From: pgsql-hackers-owner@postgresql.org

[mailto:pgsql-hackers-owner@postgresql.org] On Behalf Of Simon Riggs

Sent: Thursday, July 17, 2008 4:10 PM

To: Jonah H. Harris

Cc: Xiao Meng; pgsql-hackers@postgresql.org; Kenneth Marshall

Subject: Re: [HACKERS] [PATCH]-hash index improving

On Thu, 2008-07-17 at 16:24 -0400, Jonah H. Harris wrote:

I'm not really seeing any performance improvements over b-tree.

I'd like to see a theoretical analysis on the benefit case before we

spend too many teraflops on investigation.

In which cases do we expect that hash indexes will beat btrees?

Large table unique index equality search should be very fast with hashed
index (and the only place where any advantage will be seen). Hashed
indexes are useless for any search besides equality and gain more and
more when the levels of the b-tree index increase.

Here is a hash index lookup that is frightfully fast:
http://www.corpit.ru/mjt/tinycdb.html

It's a constant database, but the file format might be worth
examination. Here is a quickie definition of the CDB format:
http://cr.yp.to/cdb/cdb.txt

I think that the problem with hashed indexes tends to be the blocking of
index pages on disk. For instance, the FastDB/GigaBase author was able
to make FastDB memory based hash indexes that are faster than the memory
based b-tree versions, but not for the disk based GigaBase database.
The only way to get better performance from hash based indexes is to
read fewer index pages than if a tree-based index were used. So I think
that the scheme used to create the index pages is the focus to make them
worthwhile.

On Thu, Jul 17, 2008 at 02:11:20PM -0400, Alvaro Herrera wrote:

Kenneth Marshall escribi�:

On Thu, Jul 17, 2008 at 12:42:39PM -0400, Alvaro Herrera wrote:

I think having the HASHVALUE_ONLY define is not a good idea --
it just makes the patch harder to read. I suggest just removing
the old code and putting the new code in place. (That's why we
have revision control.)

One thing it helps is building an old version and a new version
for comparative testing. Otherwise, you could end up with an
apples-to- oranges comparison. I certainly think that the final
patch should not have it, but it is useful now for testing and
comparisons.

For this purpose I think it would be easier to have a separate tree
with the patch, and one without it.

Here's one tree. Anyone can get an initial copy as follows:

git clone http://git.postgresql.org/git/~davidfetter/hash/.git

Xiao Meng, if you let me know where your git repo is, say by cloning
onto a machine I can see from the internet and applying your patches
to it, I can pull and let others see it :)

Yes, I know it's a little cumbersome, but we'll get something slicker
as we figure out what "slicker" really should mean.

Cheers,
David.
--
David Fetter <david@fetter.org> http://fetter.org/
Phone: +1 415 235 3778 AIM: dfetter666 Yahoo!: dfetter
Skype: davidfetter XMPP: david.fetter@gmail.com

Remember to vote!
Consider donating to Postgres: http://www.postgresql.org/about/donate

On Thu, Jul 17, 2008 at 7:37 PM, Dann Corbit <DCorbit@connx.com> wrote:

In which cases do we expect that hash indexes will beat btrees?

Large table unique index equality search should be very fast with hashed
index (and the only place where any advantage will be seen).

Yes, this is the exact use-case. Likewise, Dan has provided a good
description regarding the primary implementation goals of a disk-based
hash table.

--
Jonah H. Harris, Sr. Software Architect | phone: 732.331.1324
EnterpriseDB Corporation | fax: 732.331.1301
499 Thornall Street, 2nd Floor | jonah.harris@enterprisedb.com
Edison, NJ 08837 | http://www.enterprisedb.com/

Alvaro Herrera <alvherre@commandprompt.com> writes:

Xiao Meng escribi�:

You can undefine the macro HASHVALUE_ONLY in hash.h to get the
original implementation.

I think having the HASHVALUE_ONLY define is not a good idea -- it just
makes the patch harder to read.

While we are griping about readability: failure to update the comments
to match the code is NOT, NOT, NOT acceptable. I had barely started
to read the patch before encountering this insult to the reader:

     /* Hash indexes are never lossy (at the moment anyway) */
-    scan->xs_recheck = false;
+#ifdef HASHVALUE_ONLY
+    scan->xs_recheck = true;
+#else
+    scan->xs_recheck = false;
+#endif

The fact that the patch doesn't touch backend/access/hash/README is
already grounds for rejection, but can't you be bothered to fix a
comment that is literally one line away from where you are making
it wrong?

regards, tom lane

On Fri, Jul 18, 2008 at 1:00 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

While we are griping about readability: failure to update the comments
to match the code is NOT, NOT, NOT acceptable. I had barely started
to read the patch before encountering this insult to the reader:
...

As this is Xiao's first patch to the community, I'd appreciate it if
you guys would chill a little. I'm fully aware of what needs to be
done with it clean-up wise, but given that we're under some time
constraints, I asked that he submit his preliminary patch for those
who wanted to preview/test it.

Again, this patch is nowhere near acceptance quality, nor was it
intended to be. I'll make sure he gets the next one cleaned up prior
to submitting it.

The real question now has been listed above; why are hash index
queries, including this patch, no better than b-tree even for straight
equality comparisons? Because hash is lossy, we could easily be
performing multiple I/Os for recheck, and that may be causing some of
the performance problems. I haven't checked I/O for that yet, but was
wondering if you (Tom) knew of any major design/implementation
deficiency we should be taking into consideration regarding PG's hash
index implementation?

--
Jonah H. Harris, Sr. Software Architect | phone: 732.331.1324
EnterpriseDB Corporation | fax: 732.331.1301
499 Thornall Street, 2nd Floor | jonah.harris@enterprisedb.com
Edison, NJ 08837 | http://www.enterprisedb.com/

"Jonah H. Harris" <jonah.harris@gmail.com> writes:

The real question now has been listed above; why are hash index
queries, including this patch, no better than b-tree even for straight
equality comparisons?

Well, the theoretical advantage is that a hash probe is O(1) while a
btree probe is O(log N) (ignoring a lot of possible nonoptimalities
on each side of course). So you'd need a test case large enough for
log N to be noticeably more than 1, which I think means in practice that
the upper levels of the btree don't fit in memory. So small test cases
aren't going to show any improvement.

I think the historical problem with our hash implementation has been
that it was terribly space-inefficient, because of the fixed (and large)
bucket size. A dense btree index can probably beat a sparse hash up to
exceedingly large values of N. It's not clear to me how much the patch
at hand does to fix that.

The patch might introduce a new problem, which is extra heap visits
caused by the lossiness of the hash value. Again, that doesn't hurt
much ideally, but maybe you chanced to use a test case where it does
hurt. It would be worth sticking in a bit of debug instrumentation to
see whether the number of failed heap visits is significant.

In any case, the reported test seems to be dealing with index sizes in
the tens-of-megabytes range, and it doesn't surprise me a whole lot that
an O(log N) penalty isn't showing up there. Try a test case where the
index size is significantly larger than your RAM.

regards, tom lane

On Thu, 2008-07-17 at 16:37 -0700, Dann Corbit wrote:

Large table unique index equality search should be very fast with hashed
index (and the only place where any advantage will be seen). Hashed
indexes are useless for any search besides equality and gain more and
more when the levels of the b-tree index increase.

I think a comparison with a btree using a functional index should be
shown.

The only way to get better performance from hash based indexes is to
read fewer index pages than if a tree-based index were used. So I think
that the scheme used to create the index pages is the focus to make them
worthwhile.

Agreed. Some math on that, plus a clear focus on making this faster than
a btree is critical to this project.

--
Simon Riggs www.2ndQuadrant.com
PostgreSQL Training, Services and Support

"Simon Riggs" <simon@2ndquadrant.com> writes:

On Thu, 2008-07-17 at 16:37 -0700, Dann Corbit wrote:

Large table unique index equality search should be very fast with hashed
index (and the only place where any advantage will be seen). Hashed
indexes are useless for any search besides equality and gain more and
more when the levels of the b-tree index increase.

I think a comparison with a btree using a functional index should be
shown.

To do that you'll have to think about the use cases you think hash should win
on.

For cpu-bound databases with small indexes there might be a win if you can
avoid the binary search of all the elements on a page. (Have we modified btree
to do that or does it still scan sequentially on the leaf pages?)

For i/o-bound databases with very large indexes there should be an opportunity
where btree lookups are O(logn) and hash lookups can in theory be O(1).

However to get O(1) hash lookups need to do extra work at insert time. If they
don't expand the hash as necessary then they end up just being a linear
speedup to whatever lookup algorithm is used to scan the buckets. That isn't
going to win over btree which is already doing a binary search.

The extra work on insert time is O(nlogn) amortized, but I'm not sure
good amortized performance is good enough for Postgres. Users are unhappy when
they're average performance is good but 1/1000 inserts thrashes their i/o
rewriting the whole index...

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com
Ask me about EnterpriseDB's 24x7 Postgres support!

On Fri, 2008-07-18 at 11:07 +0100, Gregory Stark wrote:

"Simon Riggs" <simon@2ndquadrant.com> writes:

hash lookups can in theory be O(1).

I'm not sure whether that applies here? I'm interested in how *this*
patch will work, not in more generic algorithm theory.

To patch authors: Can we please see a table showing expected number of
logical I/Os (i,e, block accesses) for btrees and hash indexes

e.g. for 100-byte rows...

rows btree hash
---- ----- ----
10^2
10^3
10^4
10^5
10^6
10^7
10^8

--
Simon Riggs www.2ndQuadrant.com
PostgreSQL Training, Services and Support