Message-ID: <559C76D4.2030805@2ndquadrant.com>
Date: Wed, 08 Jul 2015 03:03:16 +0200
From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
User-Agent: Mozilla/5.0 (X11; Linux x86_64;
 rv:31.0) Gecko/20100101 Thunderbird/31.7.0
MIME-Version: 1.0
To: Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp>
CC: pgsql-hackers@postgresql.org, jeff.janes@gmail.com,
 sfrost@snowman.net
Subject: Re: multivariate statistics / patch v7
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>
In-Reply-To: <559C2BD7.6040508@2ndquadrant.com>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
Precedence: bulk
Sender: pgsql-hackers-owner@postgresql.org

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