pg.ddx.io  pgsql-performance@postgresql.org mailing list archive  
help / color / mirror / Atom feed
From: Bruce Momjian <pgman@candle.pha.pa.us>
To: Mischa Sandberg <mischa.sandberg@telus.net>
Cc: pgsql-general@postgresql.org
Subject: Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL
Date: Tue, 10 May 2005 21:51:49 -0400 (EDT)
Message-ID: <200505110151.j4B1pnt16211@candle.pha.pa.us> (raw)
In-Reply-To: <1115770466.42814e62cb0e1@webmail.telus.net>


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

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

Mischa Sandberg wrote:
> 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                        |  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



view thread (36+ messages)  latest in thread

Message-ID: <200505110151.j4B1pnt16211@candle.pha.pa.us>
Permalink:  ../200505110151.j4B1pnt16211@candle.pha.pa.us/
Also on:    postgresql.org/message-id/200505110151.j4B1pnt16211@candle.pha.pa.us

 · 

reply

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients using the --to and --cc options:
  reply via email

  To: pgsql-performance@postgresql.org
  Cc: pgman@candle.pha.pa.us, mischa.sandberg@telus.net, pgsql-general@postgresql.org
  Subject: Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL
  In-Reply-To: <200505110151.j4B1pnt16211@candle.pha.pa.us>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

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