From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
To: Dilip Kumar <dilipbalaut@gmail.com>
Cc: Amit Langote <Langote_Amit_f8@lab.ntt.co.jp>
Cc: Dean Rasheed <dean.a.rasheed@gmail.com>
Cc: Heikki Linnakangas <hlinnaka@iki.fi>
Cc: Michael Paquier <michael.paquier@gmail.com>
Cc: Robert Haas <robertmhaas@gmail.com>
Cc: Tatsuo Ishii <ishii@postgresql.org>
Cc: David Steele <david@pgmasters.net>
Cc: Tom Lane <tgl@sss.pgh.pa.us>
Cc: Álvaro Herrera <alvherre@2ndquadrant.com>
Cc: Petr Jelinek <petr@2ndquadrant.com>
Cc: Jeff Janes <jeff.janes@gmail.com>
Cc: pgsql-hackers@postgresql.org <pgsql-hackers@postgresql.org>
Subject: Re: multivariate statistics (v19)
Date: Mon, 30 Jan 2017 20:33:26 +0100
Message-ID: <026e37cf-319a-fa6f-79c2-d5a2fc98b1b6@2ndquadrant.com> (raw)
In-Reply-To: <CAFiTN-sdJmUYiARd0qBQKBXqs73096qD0Hd1QrNs=JQ3F_0QGQ@mail.gmail.com>
References: <5d1d62a6-6228-188c-e079-c1be59942168@2ndquadrant.com>
<0ce73e37-7be4-8d9f-1ec4-46b0ca1d90c6@2ndquadrant.com>
<1c7e4e63-769b-f8ce-f245-85ef4f59fcba@iki.fi>
<CAEZATCV5ZPqvsbJJ77jr4R9beqd=xwVUnMwBkMeCw5zDdrqRNw@mail.gmail.com>
<9f7d5c73-71d6-fbe0-c190-b321db46f88c@iki.fi>
<CAEZATCWKEm1VhLdWFF5SPk7yVW0ZzH4MQFTxgDswopOwmVY+cw@mail.gmail.com>
<277d9678-7a35-a746-0eb5-41d4bcd4ef55@2ndquadrant.com>
<61e71067-9461-d785-b4a6-6e8a08996d5f@2ndquadrant.com>
<8508ad05-54b9-f402-e736-e992ea014a32@lab.ntt.co.jp>
<72eeb3d5-c406-93b0-8ff8-11b31789f683@2ndquadrant.com>
<CAFiTN-scNndU0BiYUqyM2qvyuNLjWJvJ1=9gdA9SXwvKsw0ELQ@mail.gmail.com>
<7c4b2088-5cbd-dfec-0b98-16e5a7db5308@2ndquadrant.com>
<696aa95c-2411-9b2b-f36e-65b66bf47c88@2ndquadrant.com>
<CAFiTN-vjNHSEWn9M5RqZQV7KWoFT97W=Nc14YikgUxbw2qcxDg@mail.gmail.com>
<6f7ff2aa-b2b8-dbde-b39b-a9099f615466@2ndquadrant.com>
<CAFiTN-sdJmUYiARd0qBQKBXqs73096qD0Hd1QrNs=JQ3F_0QGQ@mail.gmail.com>
List-Unsubscribe: <mailto:majordomo@postgresql.org?body=unsub%20pgsql-hackers>
On 01/26/2017 10:43 AM, Dilip Kumar wrote:
>
> histograms
> --------------
> + if (matches[i] == MVSTATS_MATCH_FULL)
> + s += mvhist->buckets[i]->ntuples;
> + else if (matches[i] == MVSTATS_MATCH_PARTIAL)
> + s += 0.5 * mvhist->buckets[i]->ntuples;
>
> Isn't it will be better that take some percentage of the bucket based
> on the number of distinct element for partial matching buckets.
>
I don't think so, for the same reason why ineq_histogram_selectivity()
in selfuncs.c uses
binfrac = 0.5;
for partial bucket matches - it provides minimum average error. Even if
we knew the number of distinct items in the bucket, we have no idea what
the distribution within the bucket looks like. Maybe 99% of the bucket
are covered by a single distinct value, maybe all the items are squashed
on one side of the bucket, etc.
Moreover we don't really know the number of distinct values in the
bucket - we only know the number of distinct items in the sample, and
only while building the histogram. I don't think it makes much sense to
estimate the number of distinct items in a bucket, because the buckets
contain only very few rows so the estimates would be wildly inaccurate.
>
> +static int
> +update_match_bitmap_histogram(PlannerInfo *root, List *clauses,
> + int2vector *stakeys,
> + MVSerializedHistogram mvhist,
> + int nmatches, char *matches,
> + bool is_or)
> +{
> + int i;
>
> For each clause we are processing all the buckets, can't we use some
> data structure which can make multi-dimensions information searching
> faster.
>
No, we're not processing all buckets for each clause. We're' only
processing buckets that were not "ruled out" by preceding clauses.
That's the whole point of the bitmap.
For example for condition (a=1) AND (b=2), the code will first evaluate
(a=1) on all buckets, and then (b=2) but only on buckets where (a=1) was
evaluated as true. Similarly for OR clauses.
>
> Something like HTree, RTree, Maybe storing histogram in these formats
> will be difficult?
>
Maybe, but I don't want to do that in the first version. I'm not opposed
to doing that in the future, if we find out the v1 histograms are not
efficient (I don't think we will, based on tests I did while working on
the patch). Support for other histogram implementations is pretty much
why there is 'type' field in the struct.
For now I think we should stick with the simple implementation.
regards
--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
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-hackers@postgresql.org
Cc: tomas.vondra@2ndquadrant.com, dilipbalaut@gmail.com, Langote_Amit_f8@lab.ntt.co.jp, dean.a.rasheed@gmail.com, hlinnaka@iki.fi, michael.paquier@gmail.com, robertmhaas@gmail.com, ishii@postgresql.org, david@pgmasters.net, tgl@sss.pgh.pa.us, alvherre@2ndquadrant.com, petr@2ndquadrant.com, jeff.janes@gmail.com
Subject: Re: multivariate statistics (v19)
In-Reply-To: <026e37cf-319a-fa6f-79c2-d5a2fc98b1b6@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