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

help / color / mirror / Atom feed
From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
To: Greg Stark <stark@mit.edu>
Cc: PostgreSQL-development <pgsql-hackers@postgresql.org>
Subject: Re: PATCH: adaptive ndistinct estimator v4
Date: Sun, 05 Apr 2015 01:57:46 +0200
Message-ID: <55207A7A.1050802@2ndquadrant.com> (raw)
In-Reply-To: <CAM-w4HPta0Jhcv2q5vhwGJ6oL_=Fe1rz9NEkn-3+2W0+UzWR2g@mail.gmail.com>
References: <541A2335.3060100@agliodbs.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>
	<CAM-w4HNfZymQmTu3+TxQQD-e6_410-sDnZBaW8neurmTFh4GbA@mail.gmail.com>
	<f4c06746b31e468f9550fb9924798da3.squirrel@2.emaily.eu>
	<54381D20.9010501@fuzzy.cz>
	<CAMkU=1yoiQt6+_XMACL=PTv-aHwc1E0BgiHGhKW3HL+ByN6zpw@mail.gmail.com>
	<5472416C.3080506@fuzzy.cz>
	<5483B346.6000203@fuzzy.cz>
	<551AEF45.7010700@2ndquadrant.com>
	<CAM-w4HPta0Jhcv2q5vhwGJ6oL_=Fe1rz9NEkn-3+2W0+UzWR2g@mail.gmail.com>
List-Unsubscribe: <mailto:majordomo@postgresql.org?body=unsub%20pgsql-hackers>

Hi,

On 04/03/15 15:46, Greg Stark wrote:
>  > The simple workaround for this was adding a fallback to GEE when f[1]
> or f[2] is 0. GEE is another estimator described in the paper, behaving
> much better in those cases.
>
> For completeness, what's the downside in just always using GEE?

That's a good question.

GEE is the estimator with minimal average error, as defined in Theorem 1 
in that paper. The exact formulation of the theorem is a bit complex, 
but it essentially says that knowing just the sizes of the data set and 
sample, there's an accuracy limit.

Or put another way, it's possible to construct the data set so that the 
estimator gives you estimates with error exceeding some limit (with a 
certain probability).

Knowledge of how much the data set is skewed gives us opportunity to 
improve the estimates by choosing an estimator performing better with 
such data sets. The problem is we don't know the skew - we can only 
estimate it from the sample, which is what the hybrid estimators do.

The AE estimator (presented in the paper and implemented in the patch) 
is an example of such hybrid estimators, but based on my experiments it 
does not work terribly well with one particular type of skew that I'd 
expect to be relatively common (few very common values, many very rare 
values).

Luckily, GEE performs pretty well in this case, but we can use the AE 
otherwise (ISTM it gives really good estimates).

But of course - there'll always be data sets that are poorly estimated 
(pretty much as Theorem 1 in the paper says). I'd be nice to do more 
testing on real-world data sets, to see if this performs better or worse 
than our current estimator.

regards
Tomas


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers



view thread (17+ messages)  latest in thread

Message-ID: <55207A7A.1050802@2ndquadrant.com>
Permalink:  ../55207A7A.1050802@2ndquadrant.com/
Also on:    postgresql.org/message-id/55207A7A.1050802@2ndquadrant.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: tomas.vondra@2ndquadrant.com, stark@mit.edu, pgsql-hackers@postgresql.org
  Subject: Re: PATCH: adaptive ndistinct estimator v4
  In-Reply-To: <55207A7A.1050802@2ndquadrant.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