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 55E0ED1D2C1 for ; Mon, 19 Apr 2004 03:09:34 -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 73070-01 for ; Mon, 19 Apr 2004 03:09:33 -0300 (ADT) Received: from sss.pgh.pa.us (sss.pgh.pa.us [66.207.139.130]) by svr1.postgresql.org (Postfix) with ESMTP id 6D3FCD1D29D for ; Mon, 19 Apr 2004 03:09:32 -0300 (ADT) Received: from sss2.sss.pgh.pa.us (tgl@localhost [127.0.0.1]) by sss.pgh.pa.us (8.12.11/8.12.11) with ESMTP id i3J69Ugw016042; Mon, 19 Apr 2004 02:09:31 -0400 (EDT) To: Greg Stark Cc: Dennis Bjorklund , Bruno Wolff III , "Jim C. Nasby" , pgsql-performance@postgresql.org Subject: Re: Horribly slow hash join In-reply-to: <874qrg7cy8.fsf@stark.xeocode.com> References: <874qrg7cy8.fsf@stark.xeocode.com> Comments: In-reply-to Greg Stark message dated "19 Apr 2004 01:29:19 -0400" Date: Mon, 19 Apr 2004 02:09:30 -0400 Message-ID: <16041.1082354970@sss.pgh.pa.us> From: Tom Lane X-Virus-Scanned: by amavisd-new at postgresql.org X-Archive-Number: 200404/261 X-Sequence-Number: 6561 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. > http://burtleburtle.net/bob/hash/doobs.html > Incidentally, this text claims mod is extremely slow compared to bit > manipulations. 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. 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. Knuth's treatment of hashing has some actual math to it... regards, tom lane