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 C3AAD533C1; Tue, 10 May 2005 19:47:10 -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 81137-07; Tue, 10 May 2005 22:47:09 +0000 (GMT) Received: from mir3-fs.mir3.com (unknown [216.74.11.46]) by svr1.postgresql.org (Postfix) with ESMTP id 4FAD653E55; Tue, 10 May 2005 19:47:08 -0300 (ADT) Received: from amateljan.mirlogic.com ([172.16.2.68]) by mir3-fs.mir3.com with Microsoft SMTPSVC(5.0.2195.5329); Tue, 10 May 2005 15:48:26 -0700 Subject: Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL From: Mark Lewis To: Mischa Sandberg Cc: pgsql-general@postgresql.org, pgsql-performance@postgresql.org In-Reply-To: <1115760957.4281293e0155b@webmail.telus.net> References: <427F6853.90308@cs.concordia.ca> <427F757A.8000407@samurai.com> <59d991c405050908271b55e673@mail.gmail.com> <427F8321.5030702@samurai.com> <20050509163423.GH35026@decibel.org> <427F9211.2090008@samurai.com> <20050509165133.GJ35026@decibel.org> <427FFCD3.1010803@samurai.com> <20050510153245.GA31103@decibel.org> <1115760957.4281293e0155b@webmail.telus.net> Content-Type: text/plain Organization: MIR3, Inc. Message-Id: <1115765164.13684.25.camel@amateljan.mirlogic.com> Mime-Version: 1.0 X-Mailer: Ximian Evolution 1.4.4 (1.4.4-3) Date: Tue, 10 May 2005 15:46:04 -0700 Content-Transfer-Encoding: 7bit X-OriginalArrivalTime: 10 May 2005 22:48:26.0899 (UTC) FILETIME=[60F2C630:01C555B2] X-Virus-Scanned: by amavisd-new at hub.org X-Archive-Number: 200505/518 X-Sequence-Number: 77866 If the original paper was published in 1984, then it's been more than 20 years. Any potential patents would already have expired, no? -- Mark Lewis On Tue, 2005-05-10 at 14:35, Mischa Sandberg wrote: > Quoting "Jim C. Nasby" : > > > Well, in a hash-join right now you normally end up feeding at least > > one > > side of the join with a seqscan. Wouldn't it speed things up > > considerably if you could look up hashes in the hash index instead? > > You might want to google on "grace hash" and "hybrid hash". > > The PG hash join is the simplest possible: build a hash table in memory, > and match an input stream against it. > > *Hybrid hash* is where you spill the hash to disk in a well-designed > way. Instead of thinking of it as building a hash table in memory, think > of it as partitioning one input; if some or all of it fits in memory, > all the better. The boundary condition is the same. > > The real wizard of hybrid hash has to be Goetz Graefe, who sadly has now > joined the MS Borg. He demonstrated that for entire-table joins, hybrid > hash completely dominates sort-merge. MSSQL now uses what he developed > as an academic, but I don't know what the patent state is. > > "Grace hash" is the original implementation of hybrid hash: > Kitsuregawa, M., Tanaka, H., and Moto-oka, T. (1984). > Architecture and Performance of Relational Algebra Machine Grace. > > > > ---------------------------(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