Received: from localhost (unknown [200.46.204.184]) by developer.postgresql.org (Postfix) with ESMTP id 28FAC2E00AA for ; Tue, 22 Apr 2008 09:01:28 -0300 (ADT) Received: from developer.postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.184]) (amavisd-maia, port 10024) with ESMTP id 05319-05 for ; Tue, 22 Apr 2008 09:01:16 -0300 (ADT) X-Greylist: from auto-whitelisted by SQLgrey-1.7.5 Received: from ironport2-out.teksavvy.com (ironport2-out.pppoe.ca [206.248.154.182]) by developer.postgresql.org (Postfix) with ESMTP id 39E662E0053 for ; Tue, 22 Apr 2008 09:01:22 -0300 (ADT) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AmIFAPNvDUjO+Igp/2dsb2JhbACBUqpa X-IronPort-AV: E=Sophos;i="4.25,693,1199682000"; d="scan'208";a="18861050" Received: from smtp.pppoe.ca (HELO smtp.teksavvy.com) ([65.39.196.238]) by ironport2-out.teksavvy.com with ESMTP; 22 Apr 2008 08:01:20 -0400 Received: from [206.248.136.41] ([206.248.136.41]) by smtp.teksavvy.com (Internet Mail Server v1.0) with ESMTP id CQX57720; Tue, 22 Apr 2008 08:01:20 -0400 Message-ID: <480DD390.7020405@mark.mielke.cc> Date: Tue, 22 Apr 2008 08:01:20 -0400 From: Mark Mielke User-Agent: Thunderbird 2.0.0.12 (X11/20080226) MIME-Version: 1.0 To: Matthew Wakeling CC: Pgsql performance Subject: Re: Group by more efficient than distinct? References: <87ve2f7bel.fsf@oxford.xeocode.com> <480D283E.1060602@mark.mielke.cc> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Virus-Scanned: Maia Mailguard 1.0.1 X-Archive-Number: 200804/313 X-Sequence-Number: 29806 Matthew Wakeling wrote: > On Mon, 21 Apr 2008, Mark Mielke wrote: >> This surprises me - hash values are lossy, so it must still need to >> confirm against the real list of values, which at a minimum should >> require references to the rows to check against? >> >> Is PostgreSQL doing something beyond my imagination? :-) > > Not too far beyond your imagination, I hope. > > It's simply your assumption that the hash table is lossy. Sure, hash > values are lossy, but a hash table isn't. Postgres stores in memory > not only the hash values, but the rows they refer to as well, having > checked them all on disc beforehand. That way, it doesn't need to look > up anything on disc for that branch of the join again, and it has a > rapid in-memory lookup for each row. I said hash *values* are lossy. I did not say hash table is lossy. The poster I responded to said that the memory required for a hash join was relative to the number of distinct values, not the number of rows. They gave an example of millions of rows, but only a few distinct values. Above, you agree with me that it it would include the rows (or at least references to the rows) as well. If it stores rows, or references to rows, then memory *is* relative to the number of rows, and millions of records would require millions of rows (or row references). Cheers, mark -- Mark Mielke