From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
To: Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp>
Cc: pgsql-hackers@postgresql.org
Cc: jeff.janes@gmail.com
Cc: sfrost@snowman.net
Subject: Re: multivariate statistics / patch v7
Date: Wed, 08 Jul 2015 03:03:16 +0200
Message-ID: <559C76D4.2030805@2ndquadrant.com> (raw)
In-Reply-To: <559C2BD7.6040508@2ndquadrant.com>
References: <55638982.40904@2ndquadrant.com>
<20150703.143034.132752108.horiguchi.kyotaro@lab.ntt.co.jp>
<55982ED6.7000807@2ndquadrant.com>
<20150707.150554.43512301.horiguchi.kyotaro@lab.ntt.co.jp>
<559C2BD7.6040508@2ndquadrant.com>
List-Unsubscribe: <mailto:majordomo@postgresql.org?body=unsub%20pgsql-hackers>
Hello Horiguchi-san!
On 07/07/2015 09:43 PM, Tomas Vondra wrote:
> -- histograms
> ALTER TABLE t ADD STATISTICS (histogram) on (a,b,c);
> ANALYZE t;
>
> EXPLAIN ANALYZE select * from t where a < 0.3 and b < 0.3 and c < 0.3;
> Seq Scan on t (cost=0.00..23870.00 rows=267033 width=24)
> (actual time=0.021..330.487 rows=273897 loops=1)
>
> EXPLAIN ANALYZE select * from t where a < 0.3 and b < 0.3 or c > 0.3;
> Seq Scan on t (cost=0.00..23870.00 rows=14317 width=24)
> (actual time=0.027..906.321 rows=966870 loops=1)
>
> EXPLAIN ANALYZE select * from t where a < 0.3 and b < 0.3 or c > 0.9;
> Seq Scan on t (cost=0.00..23870.00 rows=20367 width=24)
> (actual time=0.028..452.494 rows=393528 loops=1)
>
> This seems wrong, because the estimate for the OR queries should not be
> lower than the estimate for the first query (with just AND), and it
> should not increase when increasing the boundary. I'd bet this is a bug
> in how the inequalities are handled with histograms, or how the AND/OR
> clauses are combined. I'll look into that.
FWIW this was a stupid bug in update_match_bitmap_histogram(), which
initially handled only AND clauses, and thus assumed the "match" of a
bucket can only decrease. But for OR clauses this is exactly the
opposite (we assume no buckets match and add buckets matching at least
one of the clauses).
With this fixed, the estimates look like this:
EXPLAIN ANALYZE select * from t where a < 0.3 and b < 0.3 and c < 0.3;
Seq Scan on t (cost=0.00..23870.00 rows=267033 width=24)
(actual time=0.102..321.524 rows=273897 loops=1)
EXPLAIN ANALYZE select * from t where a < 0.3 and b < 0.3 or c < 0.3;
Seq Scan on t (cost=0.00..23870.00 rows=319400 width=24)
(actual time=0.103..386.089 rows=317533 loops=1)
EXPLAIN ANALYZE select * from t where a < 0.3 and b < 0.3 or c > 0.3;
Seq Scan on t (cost=0.00..23870.00 rows=956833 width=24)
(actual time=0.133..908.455 rows=966870 loops=1)
EXPLAIN ANALYZE select * from t where a < 0.3 and b < 0.3 or c > 0.9;
Seq Scan on t (cost=0.00..23870.00 rows=393633 width=24)
(actual time=0.105..440.607 rows=393528 loops=1)
IMHO pretty accurate estimates - no issue with OR clauses.
I've pushed this to github [1] but I need to do some additional fixes. I
also had to remove some optimizations while fixing this, and will have
to reimplement those.
That's not to say that the handling of OR-clauses is perfectly correct.
After looking at clauselist_selectivity_or(), I believe it's a bit
broken and will need a bunch of fixes, as explained in the FIXMEs I
pushed to github.
[1] https://github.com/tvondra/postgres/tree/mvstats
kind 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, horiguchi.kyotaro@lab.ntt.co.jp, jeff.janes@gmail.com, sfrost@snowman.net
Subject: Re: multivariate statistics / patch v7
In-Reply-To: <559C76D4.2030805@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