PostgreSQL Discussion - Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL

Author

Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL

Mischa Sandberg

2005-05-10, 8:24 pm

Quoting Mark Lewis <mark.lewis@mir3.com>:

> If the original paper was published in 1984, then it's been more than
> 20 years. Any potential patents would already have expired, no?

Don't know, but the idea is pervasive among different vendors ...
perhaps that's a clue.

And having now read beyond the start of ExecHashJoin(), I can see that
PG does indeed implement Grace hash; and the implementation is nice and
clean.

If there were room for improvement, (and I didn't see it in the source)
it would be the logic to:

- swap inner and outer inputs (batches) when the original inner turned
out to be too large for memory, and the corresponding outer did not. If
you implement that anyway (complicates the loops) then it's no trouble
to just hash the smaller of the two, every time; saves some CPU.

- recursively partition batches where both inner and outer input batch
ends up being too large for memory, too; or where the required number of
batch output buffers alone is too large for working RAM. This is only
for REALLY big inputs.

Note that you don't need a bad hash function to get skewed batch sizes;
you only need a skew distribution of the values being hashed.

---------------------------(end of broadcast)---------------------------
TIP 3: if posting/reading through Usenet, please send an appropriate
subscribe-nomail command to majordomo@postgresql
.org so that your
message can get through to the mailing list cleanly

Bruce Momjian

2005-05-11, 3:23 am

Is there a TODO anywhere in this discussion? If so, please let me know.

---------------------------------------------------------------------------

Mischa Sandberg wrote:
> Quoting Mark Lewis <mark.lewis@mir3.com>:
>
>
> Don't know, but the idea is pervasive among different vendors ...
> perhaps that's a clue.
>
> And having now read beyond the start of ExecHashJoin(), I can see that
> PG does indeed implement Grace hash; and the implementation is nice and
> clean.
>
> If there were room for improvement, (and I didn't see it in the source)
> it would be the logic to:
>
> - swap inner and outer inputs (batches) when the original inner turned
> out to be too large for memory, and the corresponding outer did not. If
> you implement that anyway (complicates the loops) then it's no trouble
> to just hash the smaller of the two, every time; saves some CPU.
>
> - recursively partition batches where both inner and outer input batch
> ends up being too large for memory, too; or where the required number of
> batch output buffers alone is too large for working RAM. This is only
> for REALLY big inputs.
>
> Note that you don't need a bad hash function to get skewed batch sizes;
> you only need a skew distribution of the values being hashed.
>
>
>
> ---------------------------(end of broadcast)---------------------------
> TIP 3: if posting/reading through Usenet, please send an appropriate
> subscribe-nomail command to majordomo@postgresql
.org so that your
> message can get through to the mailing list cleanly
>

--
Bruce Momjian | http://candle.pha.pa.us
pgman@candle.pha.pa.us | (610) 359-1001
+ If your life is a hard drive, | 13 Roberts Road
+ Christ can be your backup. | Newtown Square, Pennsylvania 19073

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

Mischa Sandberg

2005-05-11, 3:23 am

Quoting Bruce Momjian <pgman@candle.pha.pa.us>:

>
> Is there a TODO anywhere in this discussion? If so, please let me
> know.
>

Umm... I don't think so. I'm not clear on what TODO means yet. 'Up for
consideration'? If a "TODO" means committing to do, I would prefer to
follow up on a remote-schema (federated server) project first.
....
[color=darkred]
> source)
> turned
> not. If
> trouble
> batch
> number of
> only
> sizes;

---------------------------(end of broadcast)---------------------------
TIP 2: you can get off all lists at once with the unregister command
(send "unregister YourEmailAddressHere
" to majordomo@postgresql
.org)

Bruce Momjian

2005-05-11, 3:23 am

Mischa Sandberg wrote:
> Quoting Bruce Momjian <pgman@candle.pha.pa.us>:
>
>
> Umm... I don't think so. I'm not clear on what TODO means yet. 'Up for
> consideration'? If a "TODO" means committing to do, I would prefer to
> follow up on a remote-schema (federated server) project first.

TODO means it is a change that most people think would be a good idea.
It is not a committment from anyone to actually do it.

--
Bruce Momjian | http://candle.pha.pa.us
pgman@candle.pha.pa.us | (610) 359-1001
+ If your life is a hard drive, | 13 Roberts Road
+ Christ can be your backup. | Newtown Square, Pennsylvania 19073

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

Mischa Sandberg

2005-05-11, 3:23 am

Quoting Bruce Momjian <pgman@candle.pha.pa.us>:

> Mischa Sandberg wrote:
> me
> for
> to
>
> TODO means it is a change that most people think would be a good
> idea.
> It is not a committment from anyone to actually do it.

I think there has not been enough commentary from "most people".

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

Neil Conway

2005-05-11, 3:23 am

Bruce Momjian wrote:
> Is there a TODO anywhere in this discussion? If so, please let me know.

There are a couple:

- consider changing hash indexes to keep the entries in a hash bucket
sorted, to allow a binary search rather than a linear scan

- consider changing hash indexes to store each key's hash value in
addition to or instead of the key value.

You should probably include a pointer to this discussion as well.

(I'd like to take a look at implementing these if I get a chance.)

-Neil

---------------------------(end of broadcast)---------------------------
TIP 8: explain analyze is your friend

Bruce Momjian

2005-05-27, 8:23 pm

Added to TODO:

* Consider sorting hash buckets so entries can be found using a binary
search, rather than a linear scan
* In hash indexes, consider storing the hash value with or instead
of the key itself

---------------------------------------------------------------------------

Neil Conway wrote:
> Bruce Momjian wrote:
>
> There are a couple:
>
> - consider changing hash indexes to keep the entries in a hash bucket
> sorted, to allow a binary search rather than a linear scan
>
> - consider changing hash indexes to store each key's hash value in
> addition to or instead of the key value.
>
> You should probably include a pointer to this discussion as well.
>
> (I'd like to take a look at implementing these if I get a chance.)
>
> -Neil
>

--
Bruce Momjian | http://candle.pha.pa.us
pgman@candle.pha.pa.us | (610) 359-1001
+ If your life is a hard drive, | 13 Roberts Road
+ Christ can be your backup. | Newtown Square, Pennsylvania 19073

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

Sponsored Links