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

help / color / mirror / Atom feed
From: Tomas Vondra <tv@fuzzy.cz>
To: pgsql-performance@postgresql.org
Subject: Re: Yet another abort-early plan disaster on 9.3
Date: Sat, 04 Oct 2014 01:41:50 +0200
Message-ID: <542F343E.40906@fuzzy.cz> (raw)
In-Reply-To: <CAEYLb_UYNyG0g+2Q52GLFc9tTz+XTqEnPh5eETLcV9Z+z7sTGg@mail.gmail.com>
References: <541A2335.3060100@agliodbs.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>
	<542DADEB.2080103@agliodbs.com>
	<CAEYLb_UYNyG0g+2Q52GLFc9tTz+XTqEnPh5eETLcV9Z+z7sTGg@mail.gmail.com>
List-Unsubscribe:  <mailto:majordomo@postgresql.org?body=unsub%20pgsql-performance>

On 3.10.2014 02:54, Peter Geoghegan wrote:
> On Thu, Oct 2, 2014 at 12:56 PM, Josh Berkus <josh@agliodbs.com> wrote:
>> 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.
> 
> I think that HyperLogLog, as a streaming algorithm, will always 
> require that the entire set be streamed. This doesn't need to be a
> big deal - in the case of my abbreviated key patch, it appears to 
> basically be free because of the fact that we were streaming 
> everything anyway. It's a very cool algorithm, with fixed overhead
> and constant memory usage. It makes very useful guarantees around 
> accuracy.

I think you're mixing two things here - estimating the number of
distinct values in a sample (which can be done very efficiently using
HLL) and estimating the number of distinct values in the whole table.
For that HLL is not usable, unless you process all the data.

Sadly HLL is rather incompatible with the usual estimators, because the
ones I'm aware of need to know the number of occurences for the distinct
values etc.

But couldn't we just piggyback this on autovacuum? One of the nice HLL
features is that it's additive - you can build "partial counters" for
ranges of blocks (say, a few MBs per range), and then merge them when
needed. By keeping the parts it's possible to rebuild it separately.

But maybe this idea is way too crazy ...

regards
Tomas


-- 
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: <542F343E.40906@fuzzy.cz>
Permalink:  ../542F343E.40906@fuzzy.cz/
Also on:    postgresql.org/message-id/542F343E.40906@fuzzy.cz

 · 

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: tv@fuzzy.cz
  Subject: Re: Yet another abort-early plan disaster on 9.3
  In-Reply-To: <542F343E.40906@fuzzy.cz>

* 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