X-Original-To: pgsql-performance-postgresql.org@localhost.postgresql.org Received: from localhost (unknown [200.46.204.2]) by svr1.postgresql.org (Postfix) with ESMTP id 461CAD1D08C for ; Mon, 19 Apr 2004 09:12:54 -0300 (ADT) Received: from svr1.postgresql.org ([200.46.204.71]) by localhost (neptune.hub.org [200.46.204.2]) (amavisd-new, port 10024) with ESMTP id 82621-08 for ; Mon, 19 Apr 2004 09:12:55 -0300 (ADT) Received: from smtp.istop.com (dci.doncaster.on.ca [66.11.168.194]) by svr1.postgresql.org (Postfix) with ESMTP id B0E71D1C9E1 for ; Mon, 19 Apr 2004 09:12:51 -0300 (ADT) Received: from stark.xeocode.com (gsstark.mtl.istop.com [66.11.160.162]) by smtp.istop.com (Postfix) with ESMTP id 081CB17C4D1; Mon, 19 Apr 2004 08:12:55 -0400 (EDT) Received: from localhost ([127.0.0.1] helo=stark.xeocode.com) by stark.xeocode.com with smtp (Exim 3.36 #1 (Debian)) id 1BFXdu-00034x-00; Mon, 19 Apr 2004 08:12:54 -0400 To: Tom Lane Cc: Greg Stark , Dennis Bjorklund , Bruno Wolff III , "Jim C. Nasby" , pgsql-performance@postgresql.org Subject: Re: Horribly slow hash join References: <874qrg7cy8.fsf@stark.xeocode.com> <16041.1082354970@sss.pgh.pa.us> In-Reply-To: <16041.1082354970@sss.pgh.pa.us> From: Greg Stark Organization: The Emacs Conspiracy; member since 1992 Date: 19 Apr 2004 08:12:54 -0400 Message-ID: <87vfjw5fp5.fsf@stark.xeocode.com> Lines: 27 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 postgresql.org X-Archive-Number: 200404/266 X-Sequence-Number: 6566 Tom Lane writes: > Greg Stark writes: > > If the hash tables were made a power of two then it would be possible to mix > > the bits of the 32 bit value and just mask off the unneeded bits. I've found > > one page via google that mentions mixing bits in a hash function, but I would > > look for a more serious treatment somewhere. > Modding by a *non* power of 2 (esp. a prime) mixes the bits quite well, > and is likely faster than any multiple-instruction way to do the same. Well a) any number that has any factors of two fails to mix in some bits. That's a lot more common than non powers of two. b) The postgres code makes no attempt to make the number of buckets a prime and c) Even if the number of buckets were prime then it seems it would still be too easy to find real-world data where all the data have that prime as a factor. As it is they only need to have common factors to lose. > The quoted article seems to be by someone who has spent a lot of time > counting assembly cycles and none at all reading the last thirty years > worth of CS literature. Yes, well I did note that. -- greg