SEO

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.

Regards,
Ken Marshall

---------------------------(end of broadcast)---------------------------
TIP 5: don't forget to increase your free space map settings

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

---------------------------(end of broadcast)---------------------------
TIP 5: don't forget to increase your free space map settings

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


---------------------------(end of broadcast)---------------------------
TIP 2: Don't 'kill -9' the postmaster

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

---------------------------(end of broadcast)---------------------------
TIP 7: You can help support the PostgreSQL project by donating at

http://www.postgresql.org/about/donate

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

---------------------------(end of broadcast)---------------------------
TIP 7: You can help support the PostgreSQL project by donating at

http://www.postgresql.org/about/donate

"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

---------------------------(end of broadcast)---------------------------
TIP 5: don't forget to increase your free space map settings

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

---------------------------(end of broadcast)---------------------------
TIP 9: In versions below 8.0, the planner will ignore your desire to
choose an index scan if your joining column's datatypes do not
match

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

---------------------------(end of broadcast)---------------------------
TIP 5: don't forget to increase your free space map settings

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

---------------------------(end of broadcast)---------------------------
TIP 5: don't forget to increase your free space map settings

"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

---------------------------(end of broadcast)---------------------------
TIP 4: Have you searched our list archives?

http://archives.postgresql.org