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 C1BD154034; Tue, 10 May 2005 03:12:35 -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 74263-08; Tue, 10 May 2005 06:12:27 +0000 (GMT) Received: from stark.xeocode.com (stark.xeocode.com [216.58.44.227]) by svr1.postgresql.org (Postfix) with ESMTP id C47875403C; Tue, 10 May 2005 03:12:26 -0300 (ADT) Received: from localhost ([127.0.0.1] helo=stark.xeocode.com) by stark.xeocode.com with smtp (Exim 3.36 #1 (Debian)) id 1DVNyc-00073p-00; Tue, 10 May 2005 02:12:18 -0400 To: Tom Lane Cc: Neil Conway , "Jim C. Nasby" , 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> <4407.1115698257@sss.pgh.pa.us> <428037A2.4060304@samurai.com> <6686.1115700888@sss.pgh.pa.us> In-Reply-To: <6686.1115700888@sss.pgh.pa.us> From: Greg Stark Organization: The Emacs Conspiracy; member since 1992 Date: 10 May 2005 02:12:17 -0400 Message-ID: <878y2nsj7i.fsf@stark.xeocode.com> Lines: 22 User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.3 MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, hits=0.006 tagged_above=0 required=5 tests=AWL X-Spam-Level: X-Archive-Number: 200505/453 X-Sequence-Number: 77801 Tom Lane writes: > However: what about storing the things in hashcode order? Ordering uint32s > doesn't seem like any big conceptual problem. > > I think that efficient implementation of this would require explicitly > storing the hash code for each index entry, which we don't do now, but > it seems justifiable on multiple grounds --- besides this point, the > search could avoid doing the data-type-specific comparison if the hash > code isn't equal. It seems that means doubling the size of the hash index. That's a pretty big i/o to cpu tradeoff. What if the hash index stored *only* the hash code? That could be useful for indexing large datatypes that would otherwise create large indexes. A good hash function should have a pretty low collision rate anyways so the occasional extra i/o should more than be outweighed by the decrease in i/o needed to use the index. -- greg