Hash index todo list item

Kenneth Marshall <ktm@rice.edu> writes:

... This is the rough plan. Does anyone see anything critical that
is missing at this point?

Sounds pretty good. Let me brain-dump one item on you: one thing that
hash currently has over btree is the ability to handle index items up
to a full page. Now, if you go with a scheme that only stores hash
codes and not the underlying data, you can not only handle that but
improve on it; but if you reduce the bucket size and don't remove the
data, it'd be a step backward. The idea I had about dealing with that
was to only reduce the size of primary buckets --- if it's necessary to
add overflow space to a bucket, the overflow units are still full pages.
So an index tuple up to a page in size can always be accommodated by
adding an overflow page to the bucket.

Just a thought, but AFAIR it's not in the archives anywhere.

regards, tom lane

On Sun, 2007-09-02 at 13:04 -0500, Kenneth Marshall wrote:

Dear PostgreSQL Hackers:

After following the hackers mailing list for quite a while,
I am going to start investigating what will need to be done
to improve hash index performance. Below are the pieces of
this project that I am currently considering:

1. Characterize the current hash index implementation against
the BTree index, with a focus on space utilization and
lookup performance against a collection of test data. This
will give a baseline performance test to evaluate the impact
of changes. I initially do not plan to bench the hash creation
process since my initial focus will be on lookup performance.

2. Evaluate the performance of different hash index implementations
and/or changes to the current implementation. My current plan is
to keep the implementation as simple as possible and still provide
the desired performance. Several hash index suggestions deal with
changing the layout of the keys on a page to improve lookup
performance, including reducing the bucket size to a fraction of
a page or only storing the hash value on the page, instead of
the index value itself. My goal in this phase is to produce one
or more versions with better performance than the current BTree.

3. Look at build time and concurrency issues with the addition of
some additional tests to the test bed. (1)

4. Repeat as needed.

This is the rough plan. Does anyone see anything critical that
is missing at this point? Please send me any suggestions for test
data and various performance test ideas, since I will be working
on that first.

Sounds good.

I'd be particularly interested in large indexes, say ~ 0.5 - 2GB. There
are likely to be various effects apparent as the indexes grow. It would
be too easy to do all the tests with smaller indexes and miss things.

Other factors are:
- volatility
- concurrency

My general experience is that hash-based indexes are better when the
range of inputs is relatively well-known, allowing a fast lookup. If
that is the only benefit of hash indexes, a flexible hashing scheme may
simply weaken the benefit-case for using them. If that's true, should
the index build process examine the key values in the data to determine
the best parameters to use? Kind of ANALYZE before build.

My current feeling is that they ought to be very good at handling
read-mostly situations such as privilege checking or UPDATE-intensive
situations such as Customer-Current-Credit tracking, when the number of
customers is large.

It might also be worth looking at lossy hash indexes, i.e. the index
stores only the block numbers. That would need to be part of the
discussion around how lossy we will allow indexes to be.

We currently have two kinds of full text index with different
concurrency use cases, so it should be acceptable to have hash indexes
have a clear benefit in one use case but a clear loss in another.

--
Simon Riggs
2ndQuadrant http://www.2ndQuadrant.com

On Sun, Sep 02, 2007 at 10:41:22PM -0400, Tom Lane wrote:

Kenneth Marshall <ktm@rice.edu> writes:

... This is the rough plan. Does anyone see anything critical that
is missing at this point?

Sounds pretty good. Let me brain-dump one item on you: one thing that
hash currently has over btree is the ability to handle index items up
to a full page. Now, if you go with a scheme that only stores hash
codes and not the underlying data, you can not only handle that but
improve on it; but if you reduce the bucket size and don't remove the
data, it'd be a step backward. The idea I had about dealing with that
was to only reduce the size of primary buckets --- if it's necessary to
add overflow space to a bucket, the overflow units are still full pages.
So an index tuple up to a page in size can always be accommodated by
adding an overflow page to the bucket.

Just a thought, but AFAIR it's not in the archives anywhere.

regards, tom lane

Tom,

Thank you for the input. I agree that keeping the ability to accomodate
an index tuple up to a page is size worth keeping. I think that your
goal in reducing the bucket size is to improve the packing efficiency
of the index. Since the on disk page size remains the same, it may be
possible to use a different structure overlayed on the current bucket
size and still improve the packing efficiency of the index. After some
more mulling, here are some further thoughts on the improved hash table
implementation:

- Hash lookup is O(1) while btree is O(logN). Is there a value
in optimizing the NOT case, i.e. the entry is not in the table?

- Space versus performance trade-off. This may tie into cache
efficiency and use of L2/L3, shared buffers, main memory.
Denser layouts with a higher load facter may be a bit slower
in lookups but play much nicer in a multi-user system. Look
at the possibility of a lossy mapping?

- Build time versus update time. How does concurrency enter into
the picture regarding simultaneous updates, inserts, deletes,
and lookups?

- Could a hybrid structure with some type of prefix compression
give a more efficient layout and possibly improve performance?

- Index larger fields. Btree is limited to blocksize/3, the
current hash implementation can go up to a full block.

- What about multi-column indexes? The current implementation
only supports 1 column.

More ideas are welcome and I will add them to the list for
investigation.

Regards,
Ken

On Mon, Sep 03, 2007 at 10:33:54AM +0100, Simon Riggs wrote:

This is the rough plan. Does anyone see anything critical that
is missing at this point? Please send me any suggestions for test
data and various performance test ideas, since I will be working
on that first.

Sounds good.

I'd be particularly interested in large indexes, say ~ 0.5 - 2GB. There
are likely to be various effects apparent as the indexes grow. It would
be too easy to do all the tests with smaller indexes and miss things.

Other factors are:
- volatility
- concurrency

My general experience is that hash-based indexes are better when the
range of inputs is relatively well-known, allowing a fast lookup. If
that is the only benefit of hash indexes, a flexible hashing scheme may
simply weaken the benefit-case for using them. If that's true, should
the index build process examine the key values in the data to determine
the best parameters to use? Kind of ANALYZE before build.

My current feeling is that they ought to be very good at handling
read-mostly situations such as privilege checking or UPDATE-intensive
situations such as Customer-Current-Credit tracking, when the number of
customers is large.

It might also be worth looking at lossy hash indexes, i.e. the index
stores only the block numbers. That would need to be part of the
discussion around how lossy we will allow indexes to be.

We currently have two kinds of full text index with different
concurrency use cases, so it should be acceptable to have hash indexes
have a clear benefit in one use case but a clear loss in another.

--
Simon Riggs
2ndQuadrant http://www.2ndQuadrant.com

Simon,

Thank you for your input. I would like to include some tests with large
indexes too. Do you have any ideas for a test corpus or should we try
and generate the test data programatically? Many people in the literature
of text retrieval use the TREC* data for at least some of their runs. I
am going to check at work to see if the campus has access to the data,
otherwise I will do some web crawling to generate some sample data. I
have just posted a reply to Tom Lane with some further ideas for consideration
in the new hash index support. Like you, I suspect that volatile data that
results in many index changes may not work well with hash indexes, in general.
PostgreSQL has the additional burden of needing to access both the index and
the data heap. Obviously, the less I/O that is needed the better the
performance is likely to be. The new HOT functionality plus clustering the
table data on the hash index would effectively organize the table into the
"hash buckets" which could help with reducing both the churn in the index
as well as in the tables.

Regards,
Ken

"Kenneth Marshall" <ktm@rice.edu> writes:

On Sun, Sep 02, 2007 at 10:41:22PM -0400, Tom Lane wrote:

Kenneth Marshall <ktm@rice.edu> writes:

... This is the rough plan. Does anyone see anything critical that
is missing at this point?

Sounds pretty good. Let me brain-dump one item on you: one thing that
hash currently has over btree is the ability to handle index items up
to a full page. Now, if you go with a scheme that only stores hash
codes and not the underlying data, you can not only handle that but
improve on it;

I think that would be a big selling point for hash indexes. It would let you
index even toasted data which are larger than a page. I'm not sure whether you
can make it work for unique indexes though. But for non-unique indexes I think
it would be a solid win and mean you cover a set of use cases quite distinct
from btree indexes.

- Hash lookup is O(1) while btree is O(logN).

That's not really true. There's a tradeoff between insertion time and lookup
time. In order to get O(1) lookups you need to work pretty hard to maintain
the hash table including spending a lot of time reorganizing it when you grow
it. If you don't want to spend the time on inserts then you end up with
buckets and the hash table is basically just a linear speedup to whatever
algorithm you use to scan the buckets.

- What about multi-column indexes? The current implementation
only supports 1 column.

That seems kind of weird. It seems obvious that you mix the three hashes
together which reduces it to the solved problem.

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com

Gregory Stark <stark@enterprisedb.com> writes:

"Kenneth Marshall" <ktm@rice.edu> writes:

- What about multi-column indexes? The current implementation
only supports 1 column.

That seems kind of weird. It seems obvious that you mix the three hashes
together which reduces it to the solved problem.

No, because part of the deal is that you can do lookups using only the
leading index columns. At least, all the existing multicolumn index
types can do that.

regards, tom lane

On 9/3/07, Gregory Stark <stark@enterprisedb.com> wrote:

"Kenneth Marshall" <ktm@rice.edu> writes:

On Sun, Sep 02, 2007 at 10:41:22PM -0400, Tom Lane wrote:

Kenneth Marshall <ktm@rice.edu> writes:

... This is the rough plan. Does anyone see anything critical that
is missing at this point?

Sounds pretty good. Let me brain-dump one item on you: one thing that
hash currently has over btree is the ability to handle index items up
to a full page. Now, if you go with a scheme that only stores hash
codes and not the underlying data, you can not only handle that but
improve on it;

I think that would be a big selling point for hash indexes. It would let you
index even toasted data which are larger than a page. I'm not sure whether you
can make it work for unique indexes though. But for non-unique indexes I think
it would be a solid win and mean you cover a set of use cases quite distinct
from btree indexes.

- Hash lookup is O(1) while btree is O(logN).

That's not really true. There's a tradeoff between insertion time and lookup
time. In order to get O(1) lookups you need to work pretty hard to maintain
the hash table including spending a lot of time reorganizing it when you grow
it. If you don't want to spend the time on inserts then you end up with
buckets and the hash table is basically just a linear speedup to whatever
algorithm you use to scan the buckets.

These facts notwithstanding, average insert performance remains O(1)
if you grow the hash exponentially every time it needs to be grown.
Suppose, for example, that you use a power of 2 arrangement. Then the
worst case scenario, right after a split, is that all of your keys had
to be inserted, all had to be moved once, half had to be moved twice,
a quarter 3 times, etc. So the ratio of moves to keys is 1 + 1/2 +
1/4 + ... which is a well-known geometric series converging on 2.

True, when you cross the threshold a lot of work needs to be done.
Life would be simpler if you could just put up a lock while you split
the hash. You can't do that for a busy transactional database though.
But if you want to be clever about it, you build into your hash
implementation the intelligence to be able to have 1 or 2 hash
locations to search. When they are both present, all inserts go into
one of them, all deletes and updates are performed against both. Then
you're able to have a background job reorganize your hash while the
database continues to use it.

- What about multi-column indexes? The current implementation
only supports 1 column.

That seems kind of weird. It seems obvious that you mix the three hashes
together which reduces it to the solved problem.

That raises a very random thought. One of the nicer features of
Oracle is the ability to have function-based indexes. So you could
index, say, trim(lower(person.name)). There are a *lot* of practical
situations where that comes in handy. The best workaround that I can
think of for not having that is to have a column defined to hold the
result of the function, maintain that column with a trigger, then
index that column. Which works, but is inelegant. (It also requires
storing completely redundant data.)

Is there any prospect of postgres aquiring that functionality?

Ben

On Mon, Sep 03, 2007 at 05:20:34PM -0700, Ben Tilly wrote:

That raises a very random thought. One of the nicer features of
Oracle is the ability to have function-based indexes. So you could
index, say, trim(lower(person.name)). There are a *lot* of practical
situations where that comes in handy. The best workaround that I can
think of for not having that is to have a column defined to hold the
result of the function, maintain that column with a trigger, then
index that column. Which works, but is inelegant. (It also requires
storing completely redundant data.)

Is there any prospect of postgres aquiring that functionality?

Ben

I believe that PostgreSQL already supports functional indexes. In fact,
one suggestion to address the egregiously poor performance of the current
hash index was to replace it with a functional index.

Regards,
Ken

"Ben Tilly" <btilly@gmail.com> writes:

That raises a very random thought. One of the nicer features of
Oracle is the ability to have function-based indexes. So you could
index, say, trim(lower(person.name)).

Is there any prospect of postgres aquiring that functionality?

Uh, no, since it's already there; has been since Berkeley days ...

regards, tom lane

On 9/3/07, Tom Lane <tgl@sss.pgh.pa.us> wrote:

"Ben Tilly" <btilly@gmail.com> writes:

That raises a very random thought. One of the nicer features of
Oracle is the ability to have function-based indexes. So you could
index, say, trim(lower(person.name)).

Is there any prospect of postgres aquiring that functionality?

Uh, no, since it's already there; has been since Berkeley days ...

Nice!

I know of at least one DBA who is moving from Oracle to postgres who
will be *very* happy to hear that.

Ben

On Sun, Sep 02, 2007 at 01:04:04PM -0500, Kenneth Marshall wrote:

Dear PostgreSQL Hackers:

After following the hackers mailing list for quite a while,
I am going to start investigating what will need to be done
to improve hash index performance. Below are the pieces of
this project that I am currently considering:

1. Characterize the current hash index implementation against
the BTree index, with a focus on space utilization and
lookup performance against a collection of test data. This
will give a baseline performance test to evaluate the impact
of changes. I initially do not plan to bench the hash creation
process since my initial focus will be on lookup performance.

Here are very basic results for a table with 1.6m entries:

postgres=# CREATE TABLE dict (word varchar(100));
CREATE TABLE

postgres=# COPY dict FROM '/tmp/words';
COPY 1648379
postgres=# select count(*) from dict;
count
---------
1648379
(1 row)

Time: 11187.418 ms
postgres=# select count(*) from dict;
count
---------
1648379
(1 row)

Time: 6040.912 ms
postgres=# CREATE INDEX wordhash ON dict USING hash (word);
CREATE INDEX
Time: 11108707.160 ms

postgres=# select * from dict where word = 'avatar';
word
--------
avatar
(1 row)

Time: 79.823 ms
postgres=# select * from dict where word = 'zebra';
word
-------
zebra
(1 row)

Time: 9.864 ms
postgres=# select * from dict where word = 'turkey';
word
--------
turkey
(1 row)

Time: 18.418 ms
Time: 1.045 ms
Time: 1.257 ms
Time: 1.080 ms

postgres=# CREATE INDEX wordbtree ON dict USING btree (word);
CREATE INDEX

Time: 25438.884 ms

postgres=# select * from dict where word = 'avatar';
word
--------
avatar
(1 row)

Time: 13.400 ms
postgres=# select * from dict where word = 'zebra';
word
-------
zebra
(1 row)

Time: 1.173 ms
postgres=# select * from dict where word = 'turkey';
word
--------
turkey
(1 row)

Time: 1.186 ms
Time: 1.103 ms
Time: 1.099 ms
Time: 1.108 ms

------------------------------
Size of table = 87556096

Size of hash index = 268451840
Size of btree index = 53510144

From my very small sample on an unloaded machine, a hash index lookup
took the least amount of time. It had a much larger initial time which
could be attributable to cache population effects. The size is 5X that
of the Btree index. I will continue to improve the test suite as more
granularity is needed. If anyone has a good data generator, please let
me know. Otherwise I will just roll my own.

Regards,
Ken

Ühel kenal päeval, E, 2007-09-03 kell 19:55, kirjutas Tom Lane:

Gregory Stark <stark@enterprisedb.com> writes:

"Kenneth Marshall" <ktm@rice.edu> writes:

- What about multi-column indexes? The current implementation
only supports 1 column.

That seems kind of weird. It seems obvious that you mix the three hashes
together which reduces it to the solved problem.

No, because part of the deal is that you can do lookups using only the
leading index columns. At least, all the existing multicolumn index
types can do that.

One approahc is not to mix hashes, but to partition the hash, so that
each column gets its N bits in the hash.

If you do it smartly you can use any column for index lookups, not just
the leading one.

Hannu Krosing <hannu@skype.net> writes:

Ühel kenal päeval, E, 2007-09-03 kell 19:55, kirjutas Tom Lane:

No, because part of the deal is that you can do lookups using only the
leading index columns. At least, all the existing multicolumn index
types can do that.

One approahc is not to mix hashes, but to partition the hash, so that
each column gets its N bits in the hash.

How does that help? You still need all the keys to find out which
bucket to look in.

regards, tom lane

Ühel kenal päeval, N, 2007-09-06 kell 09:38, kirjutas Tom Lane:

Hannu Krosing <hannu@skype.net> writes:

Ühel kenal päeval, E, 2007-09-03 kell 19:55, kirjutas Tom Lane:

No, because part of the deal is that you can do lookups using only the
leading index columns. At least, all the existing multicolumn index
types can do that.

One approahc is not to mix hashes, but to partition the hash, so that
each column gets its N bits in the hash.

How does that help? You still need all the keys to find out which
bucket to look in.

no. you need to look at only the buckets where that part of hash matches

say you allocate bits 4-7 for column 2 and then need to look up column 2
value with hash 3 . here you need to look at only buckets N*16 + 3, that
is, you need to examine only each 16th bucket

---------
Hannu

Hannu Krosing wrote:

One approahc is not to mix hashes, but to partition the hash, so that
each column gets its N bits in the hash.

How does that help? You still need all the keys to find out which
bucket to look in.

no. you need to look at only the buckets where that part of hash matches

say you allocate bits 4-7 for column 2 and then need to look up column 2
value with hash 3 . here you need to look at only buckets N*16 + 3, that
is, you need to examine only each 16th bucket

I don't like the truncating hash suggestion because it limits the
ability of a hash code to uniquely identify a key.

If a user requires the ability to search on both (column1) and (column1,
column2), they can create two hash indexes and the planner can decide
which to use.
Or, they can use a btree. I think hash has a subset of uses where it
would be a significant gain, and focus should be spent on this subset.

Cheers,
mark

--
Mark Mielke <mark@mielke.cc>

On Sep 6, 2007, at 10:53 , Mark Mielke wrote:

I don't like the truncating hash suggestion because it limits the
ability of a hash code to uniquely identify a key.

AIUI, a hash can't be used as a unique identifier: it always needs to
be rechecked due to the chance of collisions. There might be other
issues with truncation, but preventing hashes from being unique isn't
one of them.

Michael Glaesemann
grzm seespotcode net

On Thu, Sep 06, 2007 at 11:53:45AM -0400, Mark Mielke wrote:

Hannu Krosing wrote:

One approahc is not to mix hashes, but to partition the hash, so that
each column gets its N bits in the hash.

How does that help? You still need all the keys to find out which
bucket to look in.

no. you need to look at only the buckets where that part of hash matches

say you allocate bits 4-7 for column 2 and then need to look up column 2
value with hash 3 . here you need to look at only buckets N*16 + 3, that
is, you need to examine only each 16th bucket

I don't like the truncating hash suggestion because it limits the ability
of a hash code to uniquely identify a key.

If a user requires the ability to search on both (column1) and (column1,
column2), they can create two hash indexes and the planner can decide which
to use.
Or, they can use a btree. I think hash has a subset of uses where it would
be a significant gain, and focus should be spent on this subset.

Cheers,
mark

I agree that we should focus primarily on the subset of uses for hash
indexes where there would be a significant gain. I do think that being
able to use a single O(1) hash lookup against all the values specified
in a pseudo-multi-column index could be very beneficial in reducing
access time and I/O.

Since we already have to check the actual tuple values for any index
lookup in postgresql, we could only store the full hash value and the
corresponding TIDs in the bucket. Then when we lookup an item by
calculating its hash, if the exact hash is not present in the bucket,
then we know that the item is not in the index. If the value exists,
then we would check the heap tuples before returning the results. Thus
a negative lookup only needs to check the index and if the hash function
is "good" there will be optimally only 1 possibly valid heap tuple if
there is a match. One very big win for this change is to allow a much
smaller index size (hash value + relevant TIDs) and the large column
values are only stored in the actual data tuples.

Regards,
Ken

Michael Glaesemann wrote:

On Sep 6, 2007, at 10:53 , Mark Mielke wrote:

I don't like the truncating hash suggestion because it limits the
ability of a hash code to uniquely identify a key.

AIUI, a hash can't be used as a unique identifier: it always needs to
be rechecked due to the chance of collisions. There might be other
issues with truncation, but preventing hashes from being unique isn't
one of them.

Of course - that's why I used the word "limit".

Hash works best, when the key is unique, however. A 32-bit hash will be
many powers of 2 more unique than a 8-bit hash.

Cheers,
mark

--
Mark Mielke <mark@mielke.cc>

On Thu, Sep 06, 2007 at 01:08:59PM -0500, Kenneth Marshall wrote:

Since we already have to check the actual tuple values for any index
lookup in postgresql, we could only store the full hash value and the
corresponding TIDs in the bucket. Then when we lookup an item by
calculating its hash, if the exact hash is not present in the bucket,
then we know that the item is not in the index.

Sounds like you'd be returning a bitmap for use with a bitmap scan.
That's a different take on other suggestions I've heard and would allow
a hash index to have an almost unlimited key size yet flexible
matching... (combined with other index, or even just the same index).

Neat.

Have a nice day,
Martijn van Oosterhout <kleptog@svana.org> http://svana.org/kleptog/