Re: Bitmap scan is undercosted?

[Tom Lane]

I wrote:
> I tried creating multiple-column statistics using the v10 facility for
> that:
> regression=# create statistics s1 on num, flag from aaa;
> CREATE STATISTICS
> regression=# analyze aaa;
> ANALYZE
> but that changed the estimate not at all, which surprised me because
> dependency statistics are supposed to fix exactly this type of problem.
> I suspect there may be something in the extended-stats code that causes it
> not to work right for boolean columns --- this wouldn't be excessively
> surprising because of the way the planner messes around with converting
> "flag = true" to just "flag" and sometimes back again.  But I've not
> looked closer yet.

After looking, I found that indeed dependency_is_compatible_clause()
rejects expressions like "flag" or "NOT flag", which it needn't since
those are fully equivalent to "flag = true" or "flag = false"
respectively.  Moreover there's nothing else in
dependencies_clauselist_selectivity that depends on the exact form of
the clause under test, only on the semantics that it's an equality
condition on some Var.  Hence I propose the attached patch, which
fixes the rowcount estimate for the example discussed in this thread:

create table aaa as select (id%100)::int num, (id%10=1)::bool flag from 
generate_series(1, 1000) id;
create index i1 on aaa  (num);
create index i2 on aaa  (flag);
create statistics s1 on num, flag from aaa;
analyze aaa;

explain analyze select count(*) from aaa where num = 1 and flag = true;

Without patch:

 Aggregate  (cost=43236.73..43236.74 rows=1 width=8) (actual time=349.365..349.3
65 rows=1 loops=1)
   ->  Bitmap Heap Scan on aaa  (cost=20086.40..43212.94 rows=9514 width=0) (act
ual time=101.308..337.985 rows=10 loops=1)
 Recheck Cond: (num = 1)
 Filter: flag
 Heap Blocks: exact=44248
 ->  BitmapAnd  (cost=20086.40..20086.40 rows=9514 width=0) (actual time
=92.214..92.214 rows=0 loops=1)
   ->  Bitmap Index Scan on i1  (cost=0.00..1776.43 rows=96000 width
=0) (actual time=17.236..17.236 rows=10 loops=1)
 Index Cond: (num = 1)
   ->  Bitmap Index Scan on i2  (cost=0.00..18304.96 rows=991003 wid
th=0) (actual time=72.168..72.168 rows=100 loops=1)
 Index Cond: (flag = true)
 Planning time: 0.254 ms
 Execution time: 350.796 ms

With patch:

 Aggregate  (cost=43496.19..43496.20 rows=1 width=8) (actual time=359.195..359.1
95 rows=1 loops=1)
   ->  Bitmap Heap Scan on aaa  (cost=20129.64..43256.19 rows=96000 width=0) (ac
tual time=99.750..347.353 rows=10 loops=1)
 Recheck Cond: (num = 1)
 Filter: flag
 Heap Blocks: exact=44248
 ->  BitmapAnd  (cost=20129.64..20129.64 rows=9514 width=0) (actual time
=90.671..90.671 rows=0 loops=1)
   ->  Bitmap Index Scan on i1  (cost=0.00..1776.43 rows=96000 width
=0) (actual time=16.946..16.946 rows=10 loops=1)
 Index Cond: (num = 1)
   ->  Bitmap Index Scan on i2  (cost=0.00..18304.96 rows=991003 wid
th=0) (actual time=70.898..70.898 rows=100 loops=1)
 Index Cond: (flag = true)
 Planning time: 0.218 ms
 Execution time: 360.608 ms

That's the right overall rowcount estimate for the scan, given the stats
it's working from.  There's apparently still something wrong with bitmap
costing, since it's still estimating this as cheaper than the single-index
case --- noting the bogus rowcount estimate for the BitmapAnd, I suspect
that bitmap costing is taking shortcuts rather than using
clauselist_selectivity to estimate the overall selectivity of the bitmap
conditions.  But whatever is causing that, it's independent of this
deficiency.

In addition to the bugfix proper, I improved some comments, got rid of
a NumRelids() test that's redundant with the preceding bms_membership()
test, and fixed dependencies_clauselist_selectivity so that
estimatedclauses actually is a pure output argument as stated by its
API contract.

regards, tom lane

diff --git a/src/backend/statistics/dependencies.c b/src/backend/statistics/dependencies.c
index 9756fb8..ae0f304 100644
*** a/src/backend/statistics/dependencies.c
--- b/src/backend/statistics/dependencies.c
*** pg_dependencies_send(PG_FUNCTION_ARGS)
*** 736,826 
   * dependency_is_compatible_clause
   *		Determines if the clause is compatible with functional dependencies
   *
!  * Only OpExprs with two arguments using an equality operator are supported.
!  * When returning True attnum is set to the attribute number of the Var within
!  * the supported clause.
!  *
!  * Currently we only support Var = Const, or Const = Var. It may be possible
!  * to expand on this later.
   */
  static bool
  dependency_is_compatible_clause(Node *clause, Index relid, AttrNumber *attnum)
  {
  	RestrictInfo *rinfo = (RestrictInfo *) clause;
  
  	if (!IsA(rinfo, RestrictInfo))
  		return false;
  
! 	/* Pseudoconstants are not really 

Re: Bitmap scan is undercosted? - boolean correlation

[Jeff Janes]

On Dec 3, 2017 15:31, "Tom Lane"  wrote:

Jeff Janes  writes:
> On Sat, Dec 2, 2017 at 8:04 PM, Justin Pryzby 
wrote:
>> It thinks there's somewhat-high correlation since it gets a list of x
>> and y values (integer positions by logical and physical sort order) and
>> 90% of the x list (logical value) are the same value ('t'), and the
>> CTIDs are in order on the new index, so 90% of the values are 100%
>> correlated.

> But there is no index involved (except in the case of the functional
> index).  The correlation of table columns to physical order of the table
> doesn't depend on the existence of an index, or the physical order within
> an index.

> But I do see that ties within the logical order of the column values are
> broken to agree with the physical order.  That is wrong, right?  Is there
> any argument that this is desirable?

Uh ... what do you propose doing instead?  We'd have to do something with
ties, and it's not so obvious this way is wrong.


Let them be tied.  If there are 10 distinct values, number the values 0 to
9, and all rows of a given distinct values get the same number for the
logical order axis.

Calling the correlation 0.8 when it is really 0.0 seems obviously wrong to
me.  Although if we switched btree to store duplicate values with tid as a
tie breaker, then maybe it wouldn't be as obviously wrong.

Cheers,

Jeff

Re: Bitmap scan is undercosted? - boolean correlation

[Tom Lane]

Jeff Janes  writes:
> On Sat, Dec 2, 2017 at 8:04 PM, Justin Pryzby  wrote:
>> It thinks there's somewhat-high correlation since it gets a list of x
>> and y values (integer positions by logical and physical sort order) and
>> 90% of the x list (logical value) are the same value ('t'), and the
>> CTIDs are in order on the new index, so 90% of the values are 100%
>> correlated.

> But there is no index involved (except in the case of the functional
> index).  The correlation of table columns to physical order of the table
> doesn't depend on the existence of an index, or the physical order within
> an index.

> But I do see that ties within the logical order of the column values are
> broken to agree with the physical order.  That is wrong, right?  Is there
> any argument that this is desirable?

Uh ... what do you propose doing instead?  We'd have to do something with
ties, and it's not so obvious this way is wrong.

regards, tom lane

Re: Bitmap scan is undercosted? - boolean correlation

[Jeff Janes]

On Sat, Dec 2, 2017 at 8:04 PM, Justin Pryzby  wrote:

> On Sat, Dec 02, 2017 at 05:27:51PM -0800, Jeff Janes wrote:
> > I think the non-extended stats code also has trouble with booleans.
> > pg_stats gives me a correlation  of 0.8 or higher for the flag column.
>
> It's not due to the boolean though; you see the same thing if you do:
> CREATE INDEX aaa_f ON aaa((flag::text));
> ANALYZE aaa;
> correlation | 0.81193
>
> or:
> ALTER TABLE aaa ADD flag2 int; UPDATE aaa SET flag2= flag::int
> correlation | 0.81193
>
> I think it's caused by having so few (2) values to correlate.
>
> most_common_vals   | {f,t}
> most_common_freqs  | {0.9014,0.0986}
> correlation| 0.822792
>
> It thinks there's somewhat-high correlation since it gets a list of x and y
> values (integer positions by logical and physical sort order) and 90% of
> the x
> list (logical value) are the same value ('t'), and the CTIDs are in order
> on
> the new index, so 90% of the values are 100% correlated.
>

But there is no index involved (except in the case of the functional
index).  The correlation of table columns to physical order of the table
doesn't depend on the existence of an index, or the physical order within
an index.

But I do see that ties within the logical order of the column values are
broken to agree with the physical order.  That is wrong, right?  Is there
any argument that this is desirable?

It looks like it could be fixed with a few extra double calcs per distinct
value.  Considering we already sorted the sample values using SQL-callable
collation dependent comparators, I doubt a few C-level double calcs is
going to be meaningful.

Cheers,

Jeff

Re: Bitmap scan is undercosted?

[Vitaliy Garnashevich]

On 03/12/2017 03:27, Jeff Janes wrote:
Due to that, when I disable bitmapscans and seqscans, I start getting 
slow index scans on the wrong index, i2 rather than i1.  I don't know 
why he doesn't see that in his example.
When I increase effective_cache_size to 1024MB, I start getting the plan 
with the slower index i2, too.


*Bitmap Heap Scan* on public.aaa  (cost=12600.90..*23688**.70* rows=9488 
width=5) (actual time=107.529..*115.902* rows=9976 loops=1)
  ->  BitmapAnd  (cost=12600.90..12600.90 rows=9488 width=0) (actual 
time=105.133..105.133 rows=0 loops=1)
    ->  Bitmap Index Scan on i1  (cost=0.00..1116.43 rows=96000 
width=0) (actual time=16.313..16.313 rows=100508 loops=1)
    ->  Bitmap Index Scan on i2  (cost=0.00..11479.47 rows=988338 
width=0) (actual time=77.950..77.950 rows=1000200 loops=1)


*Index Scan* using i2 on public.aaa  (cost=0.44..*48227.31* rows=9488 
width=5) (actual time=0.020..*285.695* rows=9976 loops=1)


*Seq Scan* on public.aaa  (cost=0.00..*169248.54* rows=9488 width=5) 
(actual time=0.024..*966.469* rows=9976 loops=1)


This way the estimates and the actual time get more sense. But then 
there's the question - maybe it's i1 runs too fast, and is estimated 
incorrectly? Why that happens?


Here are the complete plans with the two different kinds of index scans 
once again:


Index Scan using i1 on public.aaa  (cost=0.44..66621.56 rows=10340 
width=5) (actual time=0.027..47.075 rows=9944 loops=1)

  Output: num, flag
  Index Cond: (aaa.num = 1)
  Filter: aaa.flag
  Rows Removed by Filter: 89687
  Buffers: shared hit=39949
Planning time: 0.104 ms
Execution time: 47.351 ms

Index Scan using i2 on public.aaa  (cost=0.44..48227.31 rows=9488 
width=5) (actual time=0.020..285.695 rows=9976 loops=1)

  Output: num, flag
  Index Cond: (aaa.flag = true)
  Filter: (aaa.flag AND (aaa.num = 1))
  Rows Removed by Filter: 990224
  Buffers: shared hit=46984
Planning time: 0.098 ms
Execution time: 286.081 ms


// The test DB was populated with: create table aaa as select 
floor(random()*100)::int num, (random()*10 < 1)::bool flag from 
generate_series(1, 1000) id;


Regards,
Vitaliy

Re: Bitmap scan is undercosted?

[Vitaliy Garnashevich]

On 02/12/2017 23:17, Jeff Janes wrote:
Right, so there is a cpu costing problem (which could only be fixed by 
hacking postgresql and recompiling it), but it is much smaller of a 
problem than the IO cost not being accurate due to the high hit rate. 
Fixing the CPU costing problem is unlikely to make a difference to 
your real query.  If you set the page costs to zero, what happens to 
your real query?
I can't reproduce the exact issue on the real database any more. The 
query started to use the slow bitmap scan recently, and had been doing 
so for some time lately, but now it's switched back to use the index 
scan. The table involved in the query gets modified a lot. It has 
hundreds of millions of rows. Lots of new rows are appended to it every 
day, the oldest rows are sometimes removed. The table is analyzed at 
least daily. It's possible that statistics was updated and that caused 
the query to run differently. But I still would like to understand why 
that issue happened, and how to properly fix it, in case the issue returns.


But I doubt that the settings seq_page_cost = random_page_cost =
0.0 should actually be used.


Why not?  If your production server really has everything in memory 
during normal operation, that is the correct course of action.  If you 
ever restart the server, then you could have some unpleasant time 
getting it back up to speed again, but pg_prewarm could help with that.
In the real database, not everything is in memory. There are 200GB+ of 
RAM, but DB is 500GB+. The table involved in the query itself is 60GB+ 
of data and 100GB+ of indexes. I'm running the test case in a way where 
all reads are done from RAM, only to make it easier to reproduce and to 
avoid unrelated effects.


As far as know, costs in Postgres were designed to be relative to 
seq_page_cost, which for that reason is usually defined as 1.0. Even if 
everything would be in RAM, accesses to the pages would still not have 
zero cost. Setting 0.0 just seems too extreme, as all other non-zero 
costs would become infinitely bigger.
If you really want to target the plan with the BitmapAnd, you should 
increase cpu_index_tuple_cost and/or cpu_operator_cost but not 
increase cpu_tuple_cost.  That is because the  unselective bitmap 
index scan does not incur any cpu_tuple_cost, but does incur 
index_tuple and operator costs.  Unfortunately all other index scans 
in the system will also be skewed by such a change if you make the 
change system-wide.
Exactly. I'd like to understand why the worse plan is being chosen, and 
1) if it's fixable by tuning costs, to figure out the right settings 
which could be used in production, 2) if there is a bug in Postgres 
optimizer, then to bring some attention to it, so that it's eventually 
fixed in one of future releases, 3) if Postgres is supposed to work this 
way, then at least I (and people who ever read this thread) would 
understand it better.


Regards,
Vitaliy