Re: [HACKERS] Hash Indexes

On Thu, Sep 22, 2016 at 3:23 AM, Tom Lane wrote: > But to kick the hash AM as such to the curb is to say > "sorry, there will never be O(1) index lookups in Postgres". Well there's plenty of halfway solutions for that. We could move hash indexes to contrib or even have them

Re: [HACKERS] Hash Indexes

On 2016-09-23 15:19:14 -0400, Robert Haas wrote: > On Wed, Sep 21, 2016 at 10:33 PM, Andres Freund wrote: > > On 2016-09-21 22:23:27 -0400, Tom Lane wrote: > >> Andres Freund writes: > >> > Sure. But that can be addressed, with a lot less effort than

Re: [HACKERS] Hash Indexes

On Wed, Sep 21, 2016 at 10:33 PM, Andres Freund wrote: > On 2016-09-21 22:23:27 -0400, Tom Lane wrote: >> Andres Freund writes: >> > Sure. But that can be addressed, with a lot less effort than fixing and >> > maintaining the hash indexes, by adding the

Re: [HACKERS] Hash Indexes

On Wed, Sep 21, 2016 at 08:44:15PM +0100, Geoff Winkless wrote: > On 21 September 2016 at 13:29, Robert Haas wrote: > > I'd be curious what benefits people expect to get. > > An edge case I came across the other day was a unique index on a large > string: postgresql popped

Re: [HACKERS] Hash Indexes

On Thu, Sep 22, 2016 at 8:03 AM, Andres Freund wrote: > On 2016-09-21 22:23:27 -0400, Tom Lane wrote: >> Andres Freund writes: >> > Sure. But that can be addressed, with a lot less effort than fixing and >> > maintaining the hash indexes, by adding the

Re: [HACKERS] Hash Indexes

On 2016-09-21 22:23:27 -0400, Tom Lane wrote: > Andres Freund writes: > > Sure. But that can be addressed, with a lot less effort than fixing and > > maintaining the hash indexes, by adding the ability to do that > > transparently using btree indexes + a recheck internally.

Re: [HACKERS] Hash Indexes

Andres Freund writes: > Sure. But that can be addressed, with a lot less effort than fixing and > maintaining the hash indexes, by adding the ability to do that > transparently using btree indexes + a recheck internally. How that > compares efficiency-wise is unclear as of

Re: [HACKERS] Hash Indexes

On 2016-09-21 19:49:15 +0300, Oskari Saarenmaa wrote: > 21.09.2016, 15:29, Robert Haas kirjoitti: > > For PostgreSQL, I expect the benefits of improving hash indexes to be > > (1) slightly better raw performance for equality comparisons and (2) > > better concurrency. > > There's a third benefit:

Re: [HACKERS] Hash Indexes

On Wed, Sep 21, 2016 at 12:44 PM, Geoff Winkless wrote: > On 21 September 2016 at 13:29, Robert Haas wrote: > > I'd be curious what benefits people expect to get. > > An edge case I came across the other day was a unique index on a large > string:

Re: [HACKERS] Hash Indexes

On 21 September 2016 at 13:29, Robert Haas wrote: > I'd be curious what benefits people expect to get. An edge case I came across the other day was a unique index on a large string: postgresql popped up and told me that I couldn't insert a value into the field because the

Re: [HACKERS] Hash Indexes

On Wed, Sep 21, 2016 at 2:11 PM, Jeff Janes wrote: > We are? I thought we were trying to preserve on-disk compatibility so that > we didn't have to rebuild the indexes. Well, that was my initial idea, but ... > Is the concern that lack of WAL logging has generated some

Re: [HACKERS] Hash Indexes

On Wed, Sep 21, 2016 at 08:29:59AM -0400, Robert Haas wrote: > Of course, if we want to implement clustered indexes, that's going to > require significant changes to the heap format ... or the ability to > support multiple heap storage formats. I'm not opposed to that, but I > think it makes

Re: [HACKERS] Hash Indexes

On Thu, Sep 15, 2016 at 7:13 AM, Robert Haas wrote: > On Thu, Sep 15, 2016 at 1:41 AM, Amit Kapila > wrote: > > I think it is possible without breaking pg_upgrade, if we match all > > items of a page at once (and save them as local copy), rather

Re: [HACKERS] Hash Indexes

21.09.2016, 15:29, Robert Haas kirjoitti: For PostgreSQL, I expect the benefits of improving hash indexes to be (1) slightly better raw performance for equality comparisons and (2) better concurrency. There's a third benefit: with large columns a hash index is a lot smaller on disk than a

Re: [HACKERS] Hash Indexes

On Tue, Sep 20, 2016 at 7:55 PM, Bruce Momjian wrote: >> If it turns out that it has little benefit, then we don't really need >> to step up our user education. People can just keep using btree like > > The big problem is people coming from other databases and assuming our >

Re: [HACKERS] Hash Indexes

On Mon, Sep 19, 2016 at 03:50:38PM -0400, Robert Haas wrote: > It will probably have some bugs, but they probably won't be worse than > the status quo: > > WARNING: hash indexes are not WAL-logged and their use is discouraged > > Personally, I think it's outright embarrassing that we've had that

Re: [HACKERS] Hash Indexes

On Thu, Sep 15, 2016 at 11:11:41AM +0530, Amit Kapila wrote: > I think it is possible without breaking pg_upgrade, if we match all > items of a page at once (and save them as local copy), rather than > matching item-by-item as we do now. We are already doing similar for > btree, refer explanation

Re: [HACKERS] Hash Indexes

On Mon, Sep 19, 2016 at 05:50:13PM +1200, Mark Kirkwood wrote: > >I'm rather unenthused about having a hash index implementation that's > >mildly better in some corner cases, but otherwise doesn't have much > >benefit. That'll mean we'll have to step up our user education a lot, > >and we'll have

Re: [HACKERS] Hash Indexes

On Fri, Sep 16, 2016 at 2:38 PM, Andres Freund wrote: >> I think that exploring it well requires good code. If the code is good, >> why not commit it? > > Because getting there requires a lot of effort, debugging it afterwards > would take effort, and maintaining it would

Re: [HACKERS] Hash Indexes

On Sun, Sep 18, 2016 at 11:44 PM, Amit Kapila wrote: > On Mon, Sep 19, 2016 at 11:20 AM, Mark Kirkwood > wrote: > > On 17/09/16 06:38, Andres Freund wrote: > > > > While I see the point of what you are saying here, I recall all previous >

Re: [HACKERS] Hash Indexes

On Mon, Sep 19, 2016 at 12:14:26PM +0530, Amit Kapila wrote: > On Mon, Sep 19, 2016 at 11:20 AM, Mark Kirkwood > wrote: > > > > > > On 17/09/16 06:38, Andres Freund wrote: > >> > >> On 2016-09-16 09:12:22 -0700, Jeff Janes wrote: > >>> > >>> On Thu, Sep 15, 2016 at

Re: [HACKERS] Hash Indexes

On Mon, Sep 19, 2016 at 11:20 AM, Mark Kirkwood wrote: > > > On 17/09/16 06:38, Andres Freund wrote: >> >> On 2016-09-16 09:12:22 -0700, Jeff Janes wrote: >>> >>> On Thu, Sep 15, 2016 at 7:23 AM, Andres Freund >>> wrote: One earlier

Re: [HACKERS] Hash Indexes

On 17/09/16 06:38, Andres Freund wrote: On 2016-09-16 09:12:22 -0700, Jeff Janes wrote: On Thu, Sep 15, 2016 at 7:23 AM, Andres Freund wrote: One earlier question about this is whether that is actually a worthwhile goal. Are the speed and space benefits big enough in

Re: [HACKERS] Hash Indexes

On 09/16/2016 03:18 AM, Amit Kapila wrote: Attached is a run with 1000 rows. I think 1000 is also less, you probably want to run it for 100,000 or more rows. I suspect that the reason why you are seeing the large difference between btree and hash index is that the range of values is narrow

Re: [HACKERS] Hash Indexes

On 2016-09-16 09:12:22 -0700, Jeff Janes wrote: > On Thu, Sep 15, 2016 at 7:23 AM, Andres Freund wrote: > > One earlier question about this is whether that is actually a worthwhile > > goal. Are the speed and space benefits big enough in the general case? > > Could those

Re: [HACKERS] Hash Indexes

On Thu, Sep 15, 2016 at 7:23 AM, Andres Freund wrote: > Hi, > > On 2016-05-10 17:39:22 +0530, Amit Kapila wrote: > > For making hash indexes usable in production systems, we need to improve > > its concurrency and make them crash-safe by WAL logging them. > > One earlier

Re: [HACKERS] Hash Indexes

On Thu, Sep 15, 2016 at 10:38 PM, Jesper Pedersen wrote: > On 09/15/2016 02:03 AM, Amit Kapila wrote: >>> >>> Same thing here - where the fields involving the hash index aren't >>> updated. >>> >> >> Do you mean that for such cases also you see 40-60% gain? >> > > No,

Re: [HACKERS] Hash Indexes

On 16/09/16 18:35, Amit Kapila wrote: On Thu, Sep 15, 2016 at 7:53 PM, Andres Freund wrote: Hi, On 2016-05-10 17:39:22 +0530, Amit Kapila wrote: For making hash indexes usable in production systems, we need to improve its concurrency and make them crash-safe by WAL

Re: [HACKERS] Hash Indexes

On Thu, Sep 15, 2016 at 7:53 PM, Andres Freund wrote: > Hi, > > On 2016-05-10 17:39:22 +0530, Amit Kapila wrote: >> For making hash indexes usable in production systems, we need to improve >> its concurrency and make them crash-safe by WAL logging them. > > One earlier

Re: [HACKERS] Hash Indexes

On Thu, Sep 15, 2016 at 7:25 PM, Robert Haas wrote: > On Thu, Sep 15, 2016 at 2:13 AM, Amit Kapila wrote: >> One other point, I would like to discuss is that currently, we have a >> concept for tracking active hash scans (hashscan.c) which I think

Re: [HACKERS] Hash Indexes

On 09/15/2016 02:03 AM, Amit Kapila wrote: Same thing here - where the fields involving the hash index aren't updated. Do you mean that for such cases also you see 40-60% gain? No, UPDATEs are around 10-20% for our cases. I have done a run to look at the concurrency / TPS aspect of the

Re: [HACKERS] Hash Indexes

Hi, On 2016-05-10 17:39:22 +0530, Amit Kapila wrote: > For making hash indexes usable in production systems, we need to improve > its concurrency and make them crash-safe by WAL logging them. One earlier question about this is whether that is actually a worthwhile goal. Are the speed and space

Re: [HACKERS] Hash Indexes

On Thu, Sep 15, 2016 at 1:41 AM, Amit Kapila wrote: > I think it is possible without breaking pg_upgrade, if we match all > items of a page at once (and save them as local copy), rather than > matching item-by-item as we do now. We are already doing similar for > btree,

Re: [HACKERS] Hash Indexes

On Thu, Sep 15, 2016 at 2:13 AM, Amit Kapila wrote: > One other point, I would like to discuss is that currently, we have a > concept for tracking active hash scans (hashscan.c) which I think is > mainly to protect splits when the backend which is trying to split has >

Re: [HACKERS] Hash Indexes

One other point, I would like to discuss is that currently, we have a concept for tracking active hash scans (hashscan.c) which I think is mainly to protect splits when the backend which is trying to split has some scan open. You can read "Other Notes" section of access/hash/README for further

Re: [HACKERS] Hash Indexes

On Thu, Sep 15, 2016 at 12:43 AM, Jesper Pedersen wrote: > Hi, > > On 09/14/2016 07:24 AM, Amit Kapila wrote: > >>> UPDATE also sees an improvement. >>> >> >> Can you explain this more? Is it more compare to HEAD or more as >> compare to Btree? Isn't this

Re: [HACKERS] Hash Indexes

On Thu, Sep 15, 2016 at 4:44 AM, Jeff Janes wrote: > On Tue, May 10, 2016 at 5:09 AM, Amit Kapila > wrote: >> >> >> >> Although, I don't think it is a very good idea to take any performance >> data with WIP patch, still I couldn't resist myself from

Re: [HACKERS] Hash Indexes

On Thu, Sep 15, 2016 at 4:04 AM, Jeff Janes wrote: > On Tue, Sep 13, 2016 at 9:31 AM, Jeff Janes wrote: >> >> === >> >> +Vacuum acquires cleanup lock on bucket to remove the dead tuples and or >> tuples >> +that are moved due to split. The need

Re: [HACKERS] Hash Indexes

On Tue, May 10, 2016 at 5:09 AM, Amit Kapila wrote: > > > Although, I don't think it is a very good idea to take any performance > data with WIP patch, still I couldn't resist myself from doing so and below > are the performance numbers. To get the performance data, I

Re: [HACKERS] Hash Indexes

On Tue, Sep 13, 2016 at 9:31 AM, Jeff Janes wrote: > === > > +Vacuum acquires cleanup lock on bucket to remove the dead tuples and or > tuples > +that are moved due to split. The need for cleanup lock to remove dead > tuples > +is to ensure that scans' returns

Re: [HACKERS] Hash Indexes

Hi, On 09/14/2016 07:24 AM, Amit Kapila wrote: On Wed, Sep 14, 2016 at 12:29 AM, Jesper Pedersen wrote: On 09/13/2016 07:26 AM, Amit Kapila wrote: Attached, new version of patch which contains the fix for problem reported on write-ahead-log of hash index thread

Re: [HACKERS] Hash Indexes

On Wed, Sep 14, 2016 at 12:29 AM, Jesper Pedersen wrote: > On 09/13/2016 07:26 AM, Amit Kapila wrote: >> >> Attached, new version of patch which contains the fix for problem >> reported on write-ahead-log of hash index thread [1]. >> > > I have been testing patch in

Re: [HACKERS] Hash Indexes

On Tue, Sep 13, 2016 at 5:46 PM, Robert Haas wrote: > On Thu, Sep 8, 2016 at 12:32 AM, Amit Kapila wrote: >> Hmm. I think page or block is a concept of database systems and >> buckets is a general concept used in hashing technology. I think the

Re: [HACKERS] Hash Indexes

On 09/13/2016 07:26 AM, Amit Kapila wrote: Attached, new version of patch which contains the fix for problem reported on write-ahead-log of hash index thread [1]. I have been testing patch in various scenarios, and it has a positive performance impact in some cases. This is especially seen

Re: [HACKERS] Hash Indexes

On Wed, Sep 7, 2016 at 9:32 PM, Amit Kapila wrote: > On Wed, Sep 7, 2016 at 11:49 PM, Jeff Janes wrote: > > On Thu, Sep 1, 2016 at 8:55 PM, Amit Kapila > wrote: > >> > >> > >> I have fixed all other issues you have raised.

Re: [HACKERS] Hash Indexes

On Thu, Sep 8, 2016 at 12:32 AM, Amit Kapila wrote: > Hmm. I think page or block is a concept of database systems and > buckets is a general concept used in hashing technology. I think the > difference is that there are primary buckets and overflow buckets. I > have

Re: [HACKERS] Hash Indexes

On 09/12/2016 10:42 PM, Amit Kapila wrote: The following script hangs on idx_val creation - just with v5, WAL patch not applied. Are you sure it is actually hanging? I see 100% cpu for a few minutes but the index eventually completes ok for me (v5 patch applied to today's master). It

Re: [HACKERS] Hash Indexes

Attached, new version of patch which contains the fix for problem reported on write-ahead-log of hash index thread [1]. [1] - https://www.postgresql.org/message-id/CAA4eK1JuKt%3D-%3DY0FheiFL-i8Z5_5660%3D3n8JUA8s3zG53t_ArQ%40mail.gmail.com -- With Regards, Amit Kapila. EnterpriseDB:

Re: [HACKERS] Hash Indexes

On Tue, Sep 13, 2016 at 3:58 AM, Mark Kirkwood wrote: > On 13/09/16 01:20, Jesper Pedersen wrote: >> >> On 09/01/2016 11:55 PM, Amit Kapila wrote: >>> >>> I have fixed all other issues you have raised. Updated patch is >>> attached with this mail. >>> >> >> The

Re: [HACKERS] Hash Indexes

On 13/09/16 01:20, Jesper Pedersen wrote: On 09/01/2016 11:55 PM, Amit Kapila wrote: I have fixed all other issues you have raised. Updated patch is attached with this mail. The following script hangs on idx_val creation - just with v5, WAL patch not applied. Are you sure it is actually

Re: [HACKERS] Hash Indexes

On 09/01/2016 11:55 PM, Amit Kapila wrote: I have fixed all other issues you have raised. Updated patch is attached with this mail. The following script hangs on idx_val creation - just with v5, WAL patch not applied. Best regards, Jesper zero.sql Description: application/sql --

Re: [HACKERS] Hash Indexes

On Wed, Sep 7, 2016 at 11:49 PM, Jeff Janes wrote: > On Thu, Sep 1, 2016 at 8:55 PM, Amit Kapila wrote: >> >> >> I have fixed all other issues you have raised. Updated patch is >> attached with this mail. > > > I am finding the comments

Re: [HACKERS] Hash Indexes

On Thu, Sep 1, 2016 at 8:55 PM, Amit Kapila wrote: > > I have fixed all other issues you have raised. Updated patch is > attached with this mail. > I am finding the comments (particularly README) quite hard to follow. There are many references to an "overflow bucket",

Re: [HACKERS] Hash Indexes

On Thu, Sep 1, 2016 at 11:33 PM, Jesper Pedersen wrote: > On 08/05/2016 07:36 AM, Amit Kapila wrote: > > Needs a rebase. > Done. > > + if (blkno == P_NEW) > + elog(ERROR, "hash AM does not use P_NEW"); > > Left over ? > No. We need this check

Re: [HACKERS] Hash Indexes

On 08/05/2016 07:36 AM, Amit Kapila wrote: On Thu, Aug 4, 2016 at 8:02 PM, Mithun Cy wrote: I did some basic testing of same. In that I found one issue with cursor. Thanks for the testing. The reason for failure was that the patch didn't take into account the

Re: [HACKERS] Hash Indexes

On Thu, Aug 4, 2016 at 8:02 PM, Mithun Cy wrote: > I did some basic testing of same. In that I found one issue with cursor. > Thanks for the testing. The reason for failure was that the patch didn't take into account the fact that for scrolling cursors, scan can

Re: [HACKERS] Hash Indexes

I did some basic testing of same. In that I found one issue with cursor. +BEGIN; +SET enable_seqscan = OFF; +SET enable_bitmapscan = OFF; +CREATE FUNCTION declares_cursor(int) + RETURNS void + AS 'DECLARE c CURSOR FOR SELECT * from con_hash_index_table WHERE keycol = $1;' +LANGUAGE SQL; +

Re: [HACKERS] Hash indexes and effective_cache_size in CREATE INDEX documentation

On Sun, Jul 31, 2016 at 10:05 AM, Tom Lane wrote: > After looking at that a bit, I'm strongly tempted to just take out > the last two sentences of the para, reducing it to the advice concerning > maintenance_work_mem. That seems sufficient to describe the current > behavior,

Re: [HACKERS] Hash indexes and effective_cache_size in CREATE INDEX documentation

I wrote: > Peter Geoghegan writes: >> The CREATE INDEX documentation states: >> "For hash indexes, the value of effective_cache_size is also relevant >> to index creation time: PostgreSQL will use one of two different hash >> index creation methods depending on whether the

Re: [HACKERS] Hash indexes and effective_cache_size in CREATE INDEX documentation

Peter Geoghegan writes: > The CREATE INDEX documentation states: > "For hash indexes, the value of effective_cache_size is also relevant > to index creation time: PostgreSQL will use one of two different hash > index creation methods depending on whether the estimated index size

Re: [HACKERS] Hash Indexes

On Wed, Jun 22, 2016 at 8:48 PM, Robert Haas wrote: > On Wed, Jun 22, 2016 at 5:14 AM, Amit Kapila wrote: >> We can do it in the way as you are suggesting, but there is another thing >> which we need to consider here. As of now, the patch tries to

Re: [HACKERS] Hash Indexes

On Wed, Jun 22, 2016 at 8:44 PM, Robert Haas wrote: > On Wed, Jun 22, 2016 at 5:10 AM, Amit Kapila wrote: >>> > Insertion will happen by scanning the appropriate bucket and needs to >>> > retain pin on primary bucket to ensure that concurrent split

Re: [HACKERS] Hash Indexes

On Fri, Jun 24, 2016 at 2:38 PM, Mithun Cy wrote: > On Thu, Jun 16, 2016 at 12:58 PM, Amit Kapila > wrote: > > I have a question regarding code changes in _hash_first. > > +/* > + * Conditionally get the lock on primary bucket

Re: [HACKERS] Hash Indexes

On Thu, Jun 16, 2016 at 12:58 PM, Amit Kapila wrote: I have a question regarding code changes in *_hash_first*. +/* + * Conditionally get the lock on primary bucket page for search while +* holding lock on meta page. If we have to wait, then

Re: [HACKERS] Hash Indexes

On Thu, Jun 23, 2016 at 10:56 PM, Robert Haas wrote: > On Wed, Jun 22, 2016 at 10:13 PM, Amit Kapila wrote: >>> A scan that has seen the flag won't look at the >>> tuple in any case. >> >> Why so? Assume that scan started on new bucket where >>

Re: [HACKERS] Hash Indexes

On Wed, Jun 22, 2016 at 10:13 PM, Amit Kapila wrote: >> A scan that has seen the flag won't look at the >> tuple in any case. > > Why so? Assume that scan started on new bucket where > split-in-progress flag was set, now it will not look at tuples that > are marked as

Re: [HACKERS] Hash Indexes

On Wed, Jun 22, 2016 at 8:48 PM, Robert Haas wrote: > On Wed, Jun 22, 2016 at 5:14 AM, Amit Kapila wrote: >> We can do it in the way as you are suggesting, but there is another thing >> which we need to consider here. As of now, the patch tries to

Re: [HACKERS] Hash Indexes

On Wed, Jun 22, 2016 at 8:44 PM, Robert Haas wrote: > On Wed, Jun 22, 2016 at 5:10 AM, Amit Kapila wrote: >>> >>> I think this is basically correct, although I don't find it to be as >>> clear as I think it could be. It seems very clear that any

Re: [HACKERS] Hash Indexes

On Wed, Jun 22, 2016 at 5:14 AM, Amit Kapila wrote: > We can do it in the way as you are suggesting, but there is another thing > which we need to consider here. As of now, the patch tries to finish the > split if it finds split-in-progress flag in either old or new

Re: [HACKERS] Hash Indexes

On Wed, Jun 22, 2016 at 5:10 AM, Amit Kapila wrote: >> > Insertion will happen by scanning the appropriate bucket and needs to >> > retain pin on primary bucket to ensure that concurrent split doesn't >> > happen, >> > otherwise split might leave this tuple unaccounted.

Re: [HACKERS] Hash Indexes

On Tue, Jun 21, 2016 at 9:33 PM, Robert Haas wrote: > > On Thu, Jun 16, 2016 at 3:28 AM, Amit Kapila wrote: > >> Incomplete splits can be completed either by vacuum or insert as both > >> needs exclusive lock on bucket. If vacuum finds

Re: [HACKERS] Hash Indexes

On Tue, Jun 21, 2016 at 9:26 PM, Robert Haas wrote: > > On Tue, May 10, 2016 at 8:09 AM, Amit Kapila wrote: > > > Once the split operation has set the split-in-progress flag, it will begin scanning bucket (N+1)/2. Every time it finds a tuple that

Re: [HACKERS] Hash Indexes

On Thu, Jun 16, 2016 at 3:28 AM, Amit Kapila wrote: >> Incomplete splits can be completed either by vacuum or insert as both >> needs exclusive lock on bucket. If vacuum finds split-in-progress flag on a >> bucket then it will complete the split operation, vacuum won't

Re: [HACKERS] Hash Indexes

On Tue, May 10, 2016 at 8:09 AM, Amit Kapila wrote: > > For making hash indexes usable in production systems, we need to improve its > concurrency and make them crash-safe by WAL logging them. The first problem > I would like to tackle is improve the concurrency of

Re: [HACKERS] Hash Indexes

On Tue, May 10, 2016 at 5:39 PM, Amit Kapila wrote: > > > Incomplete Splits > -- > Incomplete splits can be completed either by vacuum or insert as both > needs exclusive lock on bucket. If vacuum finds split-in-progress flag on > a bucket then it

Re: [HACKERS] hash indexes and HS was:(Re: [HACKERS] testing hot standby)

On Tue, 2010-04-13 at 10:41 -0500, Jaime Casanova wrote: On Mon, Apr 12, 2010 at 1:23 AM, Jaime Casanova jcasa...@systemguards.com.ec wrote: another point, what happened with this: http://archives.postgresql.org/message-id/1229549172.4793.105.ca...@ebony.2ndquadrant? Obviously we still

Re: [HACKERS] Hash indexes (was: On-disk bitmap index patch)

On Tue, Aug 01, 2006 at 02:26:18PM -0700, [EMAIL PROTECTED] wrote: Kenneth Marshall wrote: On Fri, Jul 28, 2006 at 12:14:49PM -0500, Jim C. Nasby wrote: On Thu, Jul 27, 2006 at 01:46:01PM -0400, Alvaro Herrera wrote: Jim Nasby wrote: On Jul 25, 2006, at 3:31 PM, Tom Lane wrote:

Re: [HACKERS] Hash indexes (was: On-disk bitmap index patch)

Kenneth Marshall wrote: On Fri, Jul 28, 2006 at 12:14:49PM -0500, Jim C. Nasby wrote: On Thu, Jul 27, 2006 at 01:46:01PM -0400, Alvaro Herrera wrote: Jim Nasby wrote: On Jul 25, 2006, at 3:31 PM, Tom Lane wrote: Hannu Krosing [EMAIL PROTECTED] writes: What would be the

Re: [HACKERS] Hash indexes (was: On-disk bitmap index patch)

Tom Lane [EMAIL PROTECTED] writes: I think the problem may well be that we use hash buckets that are too large (ie, whole pages). After we fetch the page, we have to grovel through every tuple on it to find the one(s) that really match the query, whereas btree has a much more intelligent

Re: [HACKERS] Hash indexes

Gregory Stark wrote: Tom Lane [EMAIL PROTECTED] writes: I think the problem may well be that we use hash buckets that are too large (ie, whole pages). After we fetch the page, we have to grovel through every tuple on it to find the one(s) that really match the query, whereas btree has a

Re: [HACKERS] Hash indexes (was: On-disk bitmap index patch)

Jim, On 7/28/06 12:27 PM, Jim C. Nasby [EMAIL PROTECTED] wrote: In that case, perhaps this is something Greenplum might be interested in, since it might fit nicely between bitmap and btree indexes. I'm certainly following the thread. We have talked about hash and btree organized tables both

Re: [HACKERS] Hash indexes (was: On-disk bitmap index patch)

On Tue, 2006-08-01 at 07:55 -0700, Luke Lonergan wrote: WRT hashing - we use FNV hash which is a very nice, very fast modern hash algorithm. We would contribute that if we worked on this. We currently use Bob Jenkins' hash function[1], which is apparently faster than FNV on most architectures

Re: [HACKERS] Hash indexes

On Tue, Aug 01, 2006 at 10:54:10AM -0400, Andrew Dunstan wrote: This is now sounding like a lot of low hanging fruit ... highly performant hash indexed tables could possibly be a very big win. So does someone want to 'take up the cause' for them? -- Jim C. Nasby, Sr. Engineering Consultant

Re: [HACKERS] Hash indexes

Ühel kenal päeval, T, 2006-08-01 kell 10:54, kirjutas Andrew Dunstan: Gregory Stark wrote: I looked a while back and was suspicious about the actual hash functions too. It seemed like a lot of them were vastly suboptimal. That would mean we're often dealing with mostly empty and

Re: [HACKERS] Hash indexes

Hannu Krosing [EMAIL PROTECTED] writes: Ühel kenal päeval, T, 2006-08-01 kell 10:54, kirjutas Andrew Dunstan: Gregory Stark wrote: I looked a while back and was suspicious about the actual hash functions too. It seemed like a lot of them were vastly suboptimal. That would mean

Re: [HACKERS] Hash indexes

Momjian; Jie Zhang; Gavin Sherry; pgsql-hackers@postgresql.org Subject: Re: [HACKERS] Hash indexes Hannu Krosing [EMAIL PROTECTED] writes: Ühel kenal päeval, T, 2006-08-01 kell 10:54, kirjutas Andrew Dunstan: Gregory Stark wrote: I looked a while back and was suspicious about

Re: [HACKERS] Hash indexes (was: On-disk bitmap index patch)

On Fri, Jul 28, 2006 at 12:14:49PM -0500, Jim C. Nasby wrote: On Thu, Jul 27, 2006 at 01:46:01PM -0400, Alvaro Herrera wrote: Jim Nasby wrote: On Jul 25, 2006, at 3:31 PM, Tom Lane wrote: Hannu Krosing [EMAIL PROTECTED] writes: What would be the use-case for hash indexes ? And what

Re: [HACKERS] Hash indexes (was: On-disk bitmap index patch)

On Thu, Jul 27, 2006 at 01:46:01PM -0400, Alvaro Herrera wrote: Jim Nasby wrote: On Jul 25, 2006, at 3:31 PM, Tom Lane wrote: Hannu Krosing [EMAIL PROTECTED] writes: What would be the use-case for hash indexes ? And what should be done to make them faster than btree ? If we knew,

Re: [HACKERS] Hash indexes (was: On-disk bitmap index patch)

Jim C. Nasby wrote: What I'm getting at is that I've never seen any explanation for the theoretical use cases where a hash index would outperform a btree. If we knew what kind of problems hash indexes were supposed to solve, we could try and interest people who are solving those kinds of

Re: [HACKERS] Hash indexes (was: On-disk bitmap index patch)

Alvaro Herrera [EMAIL PROTECTED] writes: The btree index needs to descend potentially many pages before getting to the leaf page, where the actual index is stored. The hash index can get at the leaf node in --supposedly-- one fetch. Btree is O(logN) to get a single key, while hash is O(1).

Re: [HACKERS] Hash indexes (was: On-disk bitmap index patch)

On Fri, Jul 28, 2006 at 03:14:33PM -0400, Alvaro Herrera wrote: Jim C. Nasby wrote: What I'm getting at is that I've never seen any explanation for the theoretical use cases where a hash index would outperform a btree. If we knew what kind of problems hash indexes were supposed to solve,

Re: [HACKERS] Hash indexes (was: On-disk bitmap index patch)

Jim Nasby wrote: On Jul 25, 2006, at 3:31 PM, Tom Lane wrote: Hannu Krosing [EMAIL PROTECTED] writes: What would be the use-case for hash indexes ? And what should be done to make them faster than btree ? If we knew, we'd do it ;-) But no one's put enough effort into it to find out.

<    1   2