X-Original-To: pgsql-general-postgresql.org@localhost.postgresql.org Received: from localhost (unknown [200.46.204.144]) by svr1.postgresql.org (Postfix) with ESMTP id 41A7353D7D for ; Tue, 10 May 2005 22:51:55 -0300 (ADT) Received: from svr1.postgresql.org ([200.46.204.71]) by localhost (av.hub.org [200.46.204.144]) (amavisd-new, port 10024) with ESMTP id 08895-03 for ; Wed, 11 May 2005 01:51:50 +0000 (GMT) Received: from candle.pha.pa.us (candle.pha.pa.us [64.139.89.126]) by svr1.postgresql.org (Postfix) with ESMTP id C362D53CFF for ; Tue, 10 May 2005 22:51:48 -0300 (ADT) Received: (from pgman@localhost) by candle.pha.pa.us (8.11.6/8.11.6) id j4B1pnt16211; Tue, 10 May 2005 21:51:49 -0400 (EDT) From: Bruce Momjian Message-Id: <200505110151.j4B1pnt16211@candle.pha.pa.us> Subject: Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL In-Reply-To: <1115770466.42814e62cb0e1@webmail.telus.net> To: Mischa Sandberg Date: Tue, 10 May 2005 21:51:49 -0400 (EDT) Cc: pgsql-general@postgresql.org X-Mailer: ELM [version 2.4ME+ PL121 (25)] MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset=US-ASCII X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, hits=0.01 tagged_above=0 required=5 tests=AWL X-Spam-Level: X-Archive-Number: 200505/529 X-Sequence-Number: 77877 Is there a TODO anywhere in this discussion? If so, please let me know. --------------------------------------------------------------------------- Mischa Sandberg wrote: > Quoting Mark Lewis : > > > 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