pg.ddx.io pgsql-sql@postgresql.org mailing list archive
help / color / mirror / Atom feedRe: Hash Indexes. (Was: planner complaints)
2+ messages / 2 participants
[nested] [flat]
* Re: Hash Indexes. (Was: planner complaints)
@ 2000-04-03 19:36 Mark Dalphin <mdalphin@amgen.com>
0 siblings, 1 reply; 2+ messages in thread
From: Mark Dalphin @ 2000-04-03 19:36 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: pgsql-sql
Tom Lane wrote:
> > 2. I've replace btree indexes on relation
> > AND atd.ifs_data_id = def.ifs_data_id;
> > with:
> > create index itd_hash_data_id on ifs_tree_default USING HASH (ifs_data_id);
> > create index iatd_hash_data_id on ifs_account_tree_data USING HASH (ifs_data_id);
>
> Why would you do that? The hash index method doesn't have any advantage
> over btree that I can see, and it's got a lot of disadvantages.
Tom, I have heard this stated several times in this list and yet it contradicts what I
was taught in my course on databases. It was explained that using a HASH index could
be faster than a BTREE index for direct lookup of an item, however, the tradeoff was
that you couldn't do "unequal" comparisons (ie COLUMN < SomeValue). The speed gain
was because the HASH index could go directly to the page containing the data while the
btree index might need to load several pages to get to the final data, especially for
large BTREE indexes. Is this simply not true for PostgreSQL, or do you think it isn't
true in general (for most implementations of HASH and BTREE)?
Mark
--
Mark Dalphin email: mdalphin@amgen.com
Mail Stop: 29-2-A phone: +1-805-447-4951 (work)
One Amgen Center Drive +1-805-375-0680 (home)
Thousand Oaks, CA 91320 fax: +1-805-499-9955 (work)
^ permalink raw reply [nested|flat] 2+ messages in thread
* Re: Hash Indexes. (Was: planner complaints)
@ 2000-04-03 21:33 Tom Lane <tgl@sss.pgh.pa.us>
parent: Mark Dalphin <mdalphin@amgen.com>
0 siblings, 0 replies; 2+ messages in thread
From: Tom Lane @ 2000-04-03 21:33 UTC (permalink / raw)
To: Mark Dalphin <mdalphin@amgen.com>; +Cc: pgsql-sql
Mark Dalphin <mdalphin@amgen.com> writes:
> Tom Lane wrote:
>> Why would you do that? The hash index method doesn't have any advantage
>> over btree that I can see, and it's got a lot of disadvantages.
> Tom, I have heard this stated several times in this list and yet it
> contradicts what I was taught in my course on databases. It was
> explained that using a HASH index could be faster than a BTREE index
> for direct lookup of an item, however, the tradeoff was that you
> couldn't do "unequal" comparisons (ie COLUMN < SomeValue). The speed
> gain was because the HASH index could go directly to the page
> containing the data while the btree index might need to load several
> pages to get to the final data, especially for large BTREE indexes.
> Is this simply not true for PostgreSQL, or do you think it isn't true
> in general (for most implementations of HASH and BTREE)?
Hmm. I haven't actually timed hash versus btree lookups in Postgres;
it's possible that hash is faster (at least for some tables). I'm not
sure I believe that a hash "can go directly to the right page", though.
You could go directly to the right hash bucket, but how many index
entries will be in the bucket? You might still have to follow a chain
of overflow pages. As Professor Knuth remarked about hashing, when
you use it you are absolutely depending on the laws of probability:
the average case is really good, but the worst case is awful. Btrees
have more predictable performance.
When I commented that hashes have disadvantages, I was thinking of other
issues that are Postgres-specific: PG's hash indexes support fewer data
types than our btrees do, and our btrees support concurrent index updates
while hashes don't. If you use a hash index you are pretty much back
to the bad old pre-MVCC days: you can have N readers *or* one writer
at any instant. (I imagine this could be fixed if anyone cared to
invest the work.) The btree code is also a lot more heavily used by
most people, so I'd expect it to have fewer bugs.
And, as you say, btrees support order-related queries while hashes only
support equality. IMHO this alone is sufficient to justify choosing
btree, unless you are quite certain that you know all the kinds of query
that you will be throwing at the table and none of them involve
ordering.
regards, tom lane
^ permalink raw reply [nested|flat] 2+ messages in thread
end of thread, other threads:[~2000-04-03 21:33 UTC | newest]
Thread overview: 2+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2000-04-03 19:36 Re: Hash Indexes. (Was: planner complaints) Mark Dalphin <mdalphin@amgen.com>
2000-04-03 21:33 ` Tom Lane <tgl@sss.pgh.pa.us>
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox