Re: Index only scan sometimes switches to sequential scan for small amount of rows

From: Tomas Vondra <tomas(dot)vondra(at)2ndquadrant(dot)com>
To: Jeff Janes <jeff(dot)janes(at)gmail(dot)com>
Cc: "pgsql-performance(at)postgresql(dot)org" <pgsql-performance(at)postgresql(dot)org>
Subject: Re: Index only scan sometimes switches to sequential scan for small amount of rows
Date: 2015-03-26 22:19:07
Message-ID: 551485DB.8060901@2ndquadrant.com
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-performance

On 26.3.2015 17:35, Jeff Janes wrote:
> On Thu, Mar 26, 2015 at 5:44 AM, Tomas Vondra
> <tomas(dot)vondra(at)2ndquadrant(dot)com <mailto:tomas(dot)vondra(at)2ndquadrant(dot)com>> wrote:
>
>> That might work IMO, but maybe we should increase the coefficient a
>> bit (say, from 1.25 to 2), not to produce needlessly long MCV
>> lists.
>
> That wouldn't work here, because at the point of decision the value
> present 99 times contributes half the average, so the average is 50,
> and of course it can't possibly be twice of that.

Oh, right. How could I miss that? ;-)

> I have a patch, but is there a way to determine how it affects a
> wide variety of situations? I guess run `make installcheck`, then
> analyze, then dump pg_stats, with the patch and without the patch,
> and then compare the dumpsj?

I doubt there's such way. I'd argue that if you can show this always
generates longer MCV lists, we can assume the stats are probably more
accurate, and thus the plans should be better.

Of course, there's always the possibility that the plan was good by
luck, and improving the estimates will result in a worse plan. But I
don't think we can really fix that :-(

>>> It is also grossly inconsistent with the other behavior. If they
>>> are "29900; 98; 2" then all three go into the MCV.
>>
>> Isn't the mincount still 12500? How could all three get into the
>> MCV?
>
> If all observed values are observed at least twice, it takes a
> different path through the code. It just keeps them all in the MCV
> list. That is what is causing the instability for the OP. If the 3rd
> most common is seen twice, then all three are kept. If it is seen
> once, then only the most common is kept. See if statements at 2494
> and 2585
>
> else if (toowide_cnt == 0 && nmultiple == ndistinct)
>
> if (track_cnt == ndistinct ....

Aha, I think I see it now. I've been concentrating on this code:

avgcount = (double) samplerows / ndistinct;
/* set minimum threshold count to store a value */
mincount = avgcount * 1.25;
if (mincount < 2)
mincount = 2;

but this is actually too late, because first we do this:

else if (toowide_cnt == 0 && nmultiple == ndistinct)
{
stats->stadistinct = ndistinct;
}

and that only happens if each item is observed at least 2x in the sample
(and the actual Haas and Stokes estimator it not used).

And then we do this:

if (track_cnt == ndistinct && toowide_cnt == 0 &&
stats->stadistinct > 0 && track_cnt <= num_mcv)
{
num_mcv = track_cnt;
}

so that we track everything.

If at least one value is seen only 1x, it works differently, and we use
the code with (1.25*avgcount) threshold.

I wonder where the 1.25x threshold comes from - whether it's something
we came up with, or if it comes from some paper. I guess the former.

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

In response to

Browse pgsql-performance by date

  From Date Subject
Next Message Tom Lane 2015-03-28 17:14:04 Re: views much slower in 9.3 than 8.4
Previous Message Jeff Janes 2015-03-26 16:35:57 Re: Index only scan sometimes switches to sequential scan for small amount of rows