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 7EA0F53833; Tue, 10 May 2005 18:36:07 -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 69912-10; Tue, 10 May 2005 21:35:57 +0000 (GMT) Received: from priv-edtnes46.telusplanet.net (defout.telus.net [199.185.220.240]) by svr1.postgresql.org (Postfix) with ESMTP id ECA6653C91; Tue, 10 May 2005 18:35:56 -0300 (ADT) Received: from localhost ([199.185.220.240]) by priv-edtnes46.telusplanet.net (InterMail vM.6.01.04.04 201-2131-118-104-20050224) with ESMTP id <20050510213558.XRVH7617.priv-edtnes46.telusplanet.net@localhost>; Tue, 10 May 2005 15:35:58 -0600 Received: from 209.17.183.249 ( [209.17.183.249]) as user a3a18850@204.209.205.53 by webmail.telus.net with HTTP; Tue, 10 May 2005 14:35:57 -0700 Message-ID: <1115760957.4281293e0155b@webmail.telus.net> Date: Tue, 10 May 2005 14:35:58 -0700 From: Mischa Sandberg To: "Jim C. Nasby" Cc: Neil Conway , Christopher Petrilli , Ying Lu , pgsql-general@postgresql.org, pgsql-performance@postgresql.org Subject: Re: [PERFORM] "Hash index" vs. "b-tree index" (PostgreSQL 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> In-Reply-To: <20050510153245.GA31103@decibel.org> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit User-Agent: Internet Messaging Program (IMP) 3.1-cvs X-Originating-IP: 209.17.183.249 X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, hits=1.062 tagged_above=0 required=5 tests=AWL, DNS_FROM_RFC_POST, FORGED_RCVD_HELO X-Spam-Level: * X-Archive-Number: 200505/514 X-Sequence-Number: 77862 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.