Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtp (Exim 4.80) (envelope-from ) id 1XZmUO-0001IN-L8 for pgsql-performance@arkaria.postgresql.org; Thu, 02 Oct 2014 19:56:36 +0000 Received: from localhost ([127.0.0.1] helo=postgresql.org) by malur.postgresql.org with smtp (Exim 4.80) (envelope-from ) id 1XZmUN-0005cJ-TJ for pgsql-performance@arkaria.postgresql.org; Thu, 02 Oct 2014 19:56:35 +0000 Received: from makus.postgresql.org ([2001:4800:1501:1::229]) by malur.postgresql.org with esmtps (TLS1.2:DHE_RSA_AES_256_CBC_SHA256:256) (Exim 4.80) (envelope-from ) id 1XZmUM-0005cB-Oa for pgsql-performance@postgresql.org; Thu, 02 Oct 2014 19:56:34 +0000 Received: from 01.zmailcloud.com ([192.198.85.104] helo=mx-out-1.zmailcloud.com) by makus.postgresql.org with esmtp (Exim 4.80) (envelope-from ) id 1XZmUJ-0001bR-DA for pgsql-performance@postgresql.org; Thu, 02 Oct 2014 19:56:32 +0000 Received: from smtp.01.com (smtp.01.com [10.10.0.43]) by mx-out-1.zmailcloud.com (Postfix) with ESMTP id EDF23564AE8; Thu, 2 Oct 2014 14:56:30 -0500 (CDT) Received: from localhost (localhost [127.0.0.1]) by smtp-out-1.01.com (Postfix) with ESMTP id CB721A0377; Thu, 2 Oct 2014 14:56:30 -0500 (CDT) X-Virus-Scanned: amavisd-new at smtp-out-1.01.com Received: from smtp.01.com ([127.0.0.1]) by localhost (smtp-out-1.01.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id aS9wRiK53S2B; Thu, 2 Oct 2014 14:56:30 -0500 (CDT) Received: from smtp.01.com (localhost [127.0.0.1]) by smtp-out-1.01.com (Postfix) with ESMTP id 957B7A0617; Thu, 2 Oct 2014 14:56:30 -0500 (CDT) Received: from localhost (localhost [127.0.0.1]) by smtp-out-1.01.com (Postfix) with ESMTP id 6955AA0613; Thu, 2 Oct 2014 14:56:30 -0500 (CDT) X-Virus-Scanned: amavisd-new at smtp-out-1.01.com Received: from smtp.01.com ([127.0.0.1]) by localhost (smtp-out-1.01.com [127.0.0.1]) (amavisd-new, port 10026) with ESMTP id uDbxPAyUV9eB; Thu, 2 Oct 2014 14:56:30 -0500 (CDT) Received: from [172.47.23.102] (70-36-143-82.dsl.dynamic.fusionbroadband.com [70.36.143.82]) by smtp-out-1.01.com (Postfix) with ESMTPSA id 8F768A0377; Thu, 2 Oct 2014 14:56:29 -0500 (CDT) Message-ID: <542DADEB.2080103@agliodbs.com> Date: Thu, 02 Oct 2014 12:56:27 -0700 From: Josh Berkus Organization: PostgreSQL Experts Inc. User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.5.0 MIME-Version: 1.0 To: Peter Geoghegan , Simon Riggs CC: Jeff Janes , Merlin Moncure , postgres performance list Subject: Re: Yet another abort-early plan disaster on 9.3 References: <541A2335.3060100@agliodbs.com> <5420B71C.6010208@agliodbs.com> <5429D517.3090900@agliodbs.com> <542C4E60.3030505@agliodbs.com> In-Reply-To: Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit X-Pg-Spam-Score: -1.9 (-) List-Archive: List-Help: List-ID: List-Owner: List-Post: List-Subscribe: List-Unsubscribe: X-Mailing-List: pgsql-performance Precedence: bulk Sender: pgsql-performance-owner@postgresql.org On 10/02/2014 02:30 AM, Peter Geoghegan wrote: > On Thu, Oct 2, 2014 at 1:19 AM, Simon Riggs wrote: >> Having read papers on it, I believe the problem is intractable. Coding >> is not the issue. To anyone: please prove me wrong, in detail, with >> references so it can be coded. > > I think it might be close to intractable if you're determined to use a > sampling model. HyperLogLog looks very interesting for n_distinct > estimation, though. My abbreviated key patch estimates the cardinality > of abbreviated keys (and original strings that are to be sorted) with > high precision and fixed overhead. Maybe we can figure out a way to > do opportunistic streaming of HLL. Believe it or not, the way I use > HLL for estimating cardinality is virtually free. Hashing is really > cheap when the CPU is bottlenecked on memory bandwidth. Yes, it's only intractable if you're wedded to the idea of a tiny, fixed-size sample. If we're allowed to sample, say, 1% of the table, we can get a MUCH more accurate n_distinct estimate using multiple algorithms, of which HLL is one. While n_distinct will still have some variance, it'll be over a much smaller range. The n_distinct algo we use in Postgres is specifically designed (by its author) to choose the smallest reasonable number of distinct values capable of producing the observed distribution. This made sense when we added it because we didn't have query plans where underestimating n_distinct produced a penalty. Now we do, and we ought to change algos. -- Josh Berkus PostgreSQL Experts Inc. http://pgexperts.com -- Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance