Thread: Make the qual cost on index Filter slightly higher than qual cost onindex Cond.

On Tue, May 26, 2020 at 1:52 PM Andy Fan <zhihui.fan1213@gmail.com> wrote:
>
>
> Consider the below example:
>
> create table j1(i int, im5 int,  im100 int, im1000 int);
> insert into j1 select i, i%5, i%100, i%1000 from generate_series(1, 10000000)i;
> create index j1_i_im5 on j1(i, im5);
> create index j1_i_im100 on j1(i, im100);
> analyze j1;
> explain select * from j1 where i = 100 and im5 = 5;
>
> We may get the plan like this:
>
> demo=# explain select  * from  j1 where i = 100 and im5 = 1;
>                               QUERY PLAN
> ----------------------------------------------------------------------
>  Index Scan using j1_i_im100 on j1  (cost=0.43..8.46 rows=1 width=16)
>    Index Cond: (i = 100)
>    Filter: (im5 = 1)
> (3 rows)
>
> At this case, optimizer can estimate there are only 1 row to return, so both
> indexes have same cost, which one will be choose is un-controlable. This is
> fine for above query based on the estimation is accurate. However estimation
> can't be always accurate in real life. Some inaccurate estimation can cause an
> wrong index choose. As an experience, j1_i_im5 index should always be choose
> for above query.

I think we need a better example where choosing an index makes a difference.

An index can be chosen just because it's path was created before some
other more appropriate index but the cost difference was within fuzzy
limit. Purely based on the order in which index paths are created.

>
> This one line change is the best method I can think.
>
> -       cpu_per_tuple = cpu_tuple_cost + qpqual_cost.per_tuple;
> +      cpu_per_tuple = cpu_tuple_cost + (qpqual_cost.per_tuple * 1.001);
>
> We make the qual cost on index filter is slightly higher than qual cost in Index
> Cond. This will also good for QUAL (i=x AND m=y AND n=z). Index are (i, m,
> other_col1) and (i, other_col1, other_col2).  But this change also
> changed the relation between the qual cost on index scan and qual cost on seq
> scan. However I think that impact is so tiny that I think we can ignore that (we
> can choose a better factor between 1 and 1.001).
>
> Even the root cause of this issue comes from an inaccurate estimation. but I
> don't think that is an issue easy/possible to fix, however I'm open for
> suggestion on that as well.
>
> Any suggestions?
>
> --
> Best Regards
> Andy Fan



-- 
Best Wishes,
Ashutosh Bapat

On Wed, May 27, 2020 at 09:58:04PM +0800, Andy Fan wrote:
>On Wed, May 27, 2020 at 8:01 PM Ashutosh Bapat <
>ashutosh.bapat@2ndquadrant.com> wrote:
>
>>
>>
>> On Wed, 27 May 2020 at 04:43, Andy Fan <zhihui.fan1213@gmail.com> wrote:
>>
>>> You can use the attached sql to reproduce this issue, but I'm not sure
>>> you can
>>> get the above result at the first time that is because when optimizer
>>> think the
>>> 2 index scan have the same cost, it will choose the first one it found,
>>> the order
>>> depends on RelationGetIndexList.  If so,  you may try drop and create
>>> j1_i_im5 index.
>>>
>>> The sense behind this patch is we still use the cost based optimizer,
>>> just when we
>>> we find out the 2 index scans have the same cost,  we prefer to use the
>>> index which
>>> have more qual filter on Index Cond.  This is implemented by adjust the
>>> qual cost
>>> on index filter slightly higher.
>>>
>>
>> Thanks for the example and the explanation.
>>
>> The execution time difference in your example is pretty high to account
>> for executing the filter on so many rows. My guess is this has to do with
>> the heap access. For applying the filter the entire row needs to be fetched
>> from the heap. So we should investigate this case from that angle. Another
>> guess I have is the statistics is not correct and hence the cost is wrong.
>>
>>
>I believe this is a statistics issue and then the cost is wrong.

I think you're both right. Most of the time probably comes from the
heap accesses, but the dabatabase has no chance to account for that
as there was no analyze after inseting the data causing that. So it's
very difficult to account for this when computing the cost.

>More characters of this issue are:  1).  If a data is out of range in
>the old statistics, optimizer will given an 1 row assumption.  2).
>based on the 1 row assumption,  for query "col1=out_of_range_val AND
>col2 = any_value"   Index (col1, col2) and (col1, col3) will have
>exactly same cost for current cost model. 3).  If the statistics was
>wrong, (col1, col3) maybe a very bad plan as shown above, but index
>(col1, col2) should  always better/no worse than (col1, col3) in any
>case.  4). To expand the rule, for query "col1 = out_of_range_val AND
>col2 = any_value AND col3 = any_val", index are (col1, col2, col_m) and
>(col1, col_m, col_n),  the former index will aways has better/no worse
>than the later one.  5). an statistics issue like this is not
>uncommon, for example an log based application, creation_date is very
>easy to out of range in statistics.
>

Right. There are many ways to cause issues like this.

>so we need to optimize the cost model for such case, the method is the
>patch I mentioned above.

Making the planner more robust w.r.t. to estimation errors is nice, but
I wouldn't go as far saying we should optimize for such cases. The stats
can be arbitrarily off, so should we expect the error to be 10%, 100% or
1000000%? We'd probably end up with plans that handle worst cases well,
but the average performance would end up being way worse :-(

Anyway, I kinda doubt making the conditions 1.001 more expensive is a
way to make the planning more robust. I'm pretty sure we could construct
examples in the opposite direction, in which case this change make it
more likely we use the wrong index.


regards

-- 
Tomas Vondra                  http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Tomas Vondra <tomas.vondra@2ndquadrant.com> writes:
> On Wed, May 27, 2020 at 09:58:04PM +0800, Andy Fan wrote:
>> so we need to optimize the cost model for such case, the method is the
>> patch I mentioned above.

> Making the planner more robust w.r.t. to estimation errors is nice, but
> I wouldn't go as far saying we should optimize for such cases.

Yeah, it's a serious mistake to try to "optimize" for cases where we have
no data or wrong data.  By definition, we don't know what we're doing,
so who's to say whether we've made it better or worse?  And the possible
side effects on cases where we do have good data are not to be ignored.

> Anyway, I kinda doubt making the conditions 1.001 more expensive is a
> way to make the planning more robust. I'm pretty sure we could construct
> examples in the opposite direction, in which case this change make it
> more likely we use the wrong index.

The other serious error we could be making here is to change things on
the basis of just a few examples.  You really need a pretty wide range
of test cases to be sure that you're not making things worse, any time
you're twiddling basic parameters like these.

            regards, tom lane

On Fri, May 29, 2020 at 6:40 AM Andy Fan <zhihui.fan1213@gmail.com> wrote:
>
>
>>
>> >so we need to optimize the cost model for such case, the method is the
>> >patch I mentioned above.
>>
>> Making the planner more robust w.r.t. to estimation errors is nice, but
>> I wouldn't go as far saying we should optimize for such cases. The stats
>> can be arbitrarily off, so should we expect the error to be 10%, 100% or
>> 1000000%?
>
>
> I don't think my patch relay on anything like that.   My patch doesn't fix the
> statistics issue,  just adding the extra cost on qual cost on Index Filter part.
> Assume the query pattern are where col1= X and col2 = Y. The impacts are :
> 1).  Make the cost of (col1, other_column) is higher than (col1, col2)
> 2). The relationship between seqscan and index scan on index (col1, other_column)
> is changed, (this is something I don't want).  However my cost difference between
> index scan & seq scan usually very huge, so the change above should has
> nearly no impact on that choice.   3). Make the cost higher index scan for
> Index (col1) only.  Overall I think nothing will make thing worse.

When the statistics is almost correct (or better than what you have in
your example), the index which does not cover all the columns in all
the conditions will be expensive anyways because of extra cost to
access heap for the extra rows not filtered by that index. An index
covering all the conditions would have its scan cost cheaper since
there will be fewer rows and hence fewer heap page accesses because of
more filtering. So I don't think we need any change in the current
costing model.

>
>>
>> We'd probably end up with plans that handle worst cases well,
>> but the average performance would end up being way worse :-(
>>
>
> That's possible,  that's why I hope to get some feedback on that.  Actually I
> can't think out such case.   can you have anything like that in mind?
>
> ----
> I'm feeling that (qpqual_cost.per_tuple * 1.001) is not good enough since user
> may have some where expensive_func(col1) = X.   we may change it
> cpu_tuple_cost + qpqual_cost.per_tuple  + (0.0001) * list_lenght(qpquals).
>
> --
> Best Regards
> Andy Fan



-- 
Best Wishes,
Ashutosh Bapat