pg.ddx.io  pgsql-performance@postgresql.org mailing list archive  

help / color / mirror / Atom feed
From: Josh Berkus <josh@agliodbs.com>
To: Peter Geoghegan <peter.geoghegan86@gmail.com>
To: Simon Riggs <simon@2ndquadrant.com>
Cc: Jeff Janes <jeff.janes@gmail.com>
Cc: Merlin Moncure <mmoncure@gmail.com>
Cc: postgres performance list <pgsql-performance@postgresql.org>
Subject: Re: Yet another abort-early plan disaster on 9.3
Date: Thu, 02 Oct 2014 12:56:27 -0700
Message-ID: <542DADEB.2080103@agliodbs.com> (raw)
In-Reply-To: <WM!341e0135c2f371f48830484cdb3da37506d776453b10db7a9af11d648214c4b437402f04e7ccb3d30918cbc64dfee95d!@asav-1.01.com>
References: <541A2335.3060100@agliodbs.com>
	<WM!aa8d66f3329082c248d8e57896b3051be5691fe6550231e4f7388b7a9339864c4c89748426e4ef897c484b8998b7f996!@asav-1.01.com>
	<5420B71C.6010208@agliodbs.com>
	<CA+U5nMJqYiViG8Xu=OqJo5o7NbKgrBYC=Kn6nx-4AtKXidWvtw@mail.gmail.com>
	<WM!179663f2b73bd99d77bdeeaa9c7a72aa03c039d695004807cd4a621b4ed9ff654caf2caa9f8d529ad85c07db10c93999!@asav-1.01.com>
	<5429D517.3090900@agliodbs.com>
	<CAMkU=1wCMLWZexqVUPXWFeKmPPUDMv6GEEFUVDQnb7gfW9Wamw@mail.gmail.com>
	<CA+U5nMLj0iyYpOM+uF934-joy+6S64=yR+d6cnp94ZWzk2xkug@mail.gmail.com>
	<WM!ce2c941557a0e9090a3cb66d0469128c782bb4d7b1f60d15a5c91279578d4c6fd237efa5b4660e94a0056752c695113e!@asav-2.01.com>
	<542C4E60.3030505@agliodbs.com>
	<CA+U5nMKqqPNpSr2CQ2V0=9bjWVv-OA28o3BoxYP=7YVfyswdzw@mail.gmail.com>
	<CAEYLb_UTz=dtxYOCYF_D1s7wQJfoZUrey6Fjxq08VFueXWoEKQ@mail.gmail.com>
	<WM!341e0135c2f371f48830484cdb3da37506d776453b10db7a9af11d648214c4b437402f04e7ccb3d30918cbc64dfee95d!@asav-1.01.com>
List-Unsubscribe:  <mailto:majordomo@postgresql.org?body=unsub%20pgsql-performance>

On 10/02/2014 02:30 AM, Peter Geoghegan wrote:
> On Thu, Oct 2, 2014 at 1:19 AM, Simon Riggs <simon@2ndquadrant.com> 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



view thread (60+ messages)  latest in thread

Message-ID: <542DADEB.2080103@agliodbs.com>
Permalink:  ../542DADEB.2080103@agliodbs.com/
Also on:    postgresql.org/message-id/542DADEB.2080103@agliodbs.com

 · 

reply
Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients using the --to and --cc options:
  reply via email

  To: pgsql-performance@postgresql.org
  Cc: josh@agliodbs.com, peter.geoghegan86@gmail.com, simon@2ndquadrant.com, jeff.janes@gmail.com, mmoncure@gmail.com
  Subject: Re: Yet another abort-early plan disaster on 9.3
  In-Reply-To: <542DADEB.2080103@agliodbs.com>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox