Обсуждение: Weird indices

Hi,

I try to optimize our databases and I find a query that's not very
optimal :

sitefr=# explain select nomsession from session where nomsession='xxx';
NOTICE:  QUERY PLAN:

Seq Scan on session  (cost=0.00..16275.95 rows=10113 width=12)

EXPLAIN


Phew! I think there's an index missing but...

sitefr=# \d session
                             Table "session"
 Attribute  |   Type    |                    Modifier
------------+-----------+-------------------------------------------------
 idsession  | integer   | not null default nextval('seq_idsession'::text)
 nomsession | text      |
 idmembre   | text      |
 referer    | text      |
 ip         | text      |
 datelog    | timestamp |
Indices: ix_session_idmembre,
         ix_session_nomsession,
         session_idsession_key


So I look at the index itself :

sitefr=# \d ix_session_nomsession
Index "ix_session_nomsession"
 Attribute  | Type
------------+------
 nomsession | text
btree


Did I miss something or 'text' attributes (fields) can't be indexed ?
That sounds crazy ! (I vacuum analyzed many times)

Just in case 'nomsession' would not be as dispersed as I would
think...

sitefr=# select count(nomsession) from session;
 count
--------
 510069
(1 row)

sitefr=# select count(distinct nomsession) from session;
 count
--------
 401094
(1 row)

Anyone has an idea ?

Thanks !

--
Jean-Christophe Boggio
cat@thefreecat.org
Independant Consultant and Developer
Delphi, Linux, Perl, PostgreSQL

Do you have a value that is not null that is very common?
It's estimating that there will be 10113 rows that match
nomsession='xxx' which makes a seq scan a much less bad plan.

On Sat, 17 Feb 2001, Jean-Christophe Boggio wrote:

>
> Hi,
>
> I try to optimize our databases and I find a query that's not very
> optimal :
>
> sitefr=# explain select nomsession from session where nomsession='xxx';
> NOTICE:  QUERY PLAN:
>
> Seq Scan on session  (cost=0.00..16275.95 rows=10113 width=12)
>
> EXPLAIN
>
>
> Phew! I think there's an index missing but...
>
> sitefr=# \d session
>                              Table "session"
>  Attribute  |   Type    |                    Modifier
> ------------+-----------+-------------------------------------------------
>  idsession  | integer   | not null default nextval('seq_idsession'::text)
>  nomsession | text      |
>  idmembre   | text      |
>  referer    | text      |
>  ip         | text      |
>  datelog    | timestamp |
> Indices: ix_session_idmembre,
>          ix_session_nomsession,
>          session_idsession_key
>
>
> So I look at the index itself :
>
> sitefr=# \d ix_session_nomsession
> Index "ix_session_nomsession"
>  Attribute  | Type
> ------------+------
>  nomsession | text
> btree
>
>
> Did I miss something or 'text' attributes (fields) can't be indexed ?
> That sounds crazy ! (I vacuum analyzed many times)
>
> Just in case 'nomsession' would not be as dispersed as I would
> think...
>
> sitefr=# select count(nomsession) from session;
>  count
> --------
>  510069
> (1 row)
>
> sitefr=# select count(distinct nomsession) from session;
>  count
> --------
>  401094
> (1 row)

Stephan,

Ref : Saturday, February 17, 2001 1:50:32 AM


SS> Do you have a value that is not null that is very common?
SS> It's estimating that there will be 10113 rows that match
SS> nomsession='xxx' which makes a seq scan a much less bad plan.

At first, I thought that couldn't be the case but we happen to have
100000 records where nomsession=''

Just updated them so that their value is null and everything runs
fine. Thanks for your help !

--
Jean-Christophe Boggio
cat@thefreecat.org
Independant Consultant and Developer
Delphi, Linux, Perl, PostgreSQL

Stephan Szabo wrote:
>
> Do you have a value that is not null that is very common?
> It's estimating that there will be 10113 rows that match
> nomsession='xxx' which makes a seq scan a much less bad plan.
>
Err, why?  There is an index, isn't there?  Shouldn't the index allow
postgres to quickly find the %2 of rows that would match?


> On Sat, 17 Feb 2001, Jean-Christophe Boggio wrote:
>
> >
> > Hi,
> >
> > I try to optimize our databases and I find a query that's not very
> > optimal :
> >
> > sitefr=# explain select nomsession from session where nomsession='xxx';
> > NOTICE:  QUERY PLAN:
> >
> > Seq Scan on session  (cost=0.00..16275.95 rows=10113 width=12)
> >
> > EXPLAIN
> >
> >
> > Phew! I think there's an index missing but...
> >
> > sitefr=# \d session
> >                              Table "session"
> >  Attribute  |   Type    |                    Modifier
> > ------------+-----------+-------------------------------------------------
> >  idsession  | integer   | not null default nextval('seq_idsession'::text)
> >  nomsession | text      |
> >  idmembre   | text      |
> >  referer    | text      |
> >  ip         | text      |
> >  datelog    | timestamp |
> > Indices: ix_session_idmembre,
> >          ix_session_nomsession,
> >          session_idsession_key
> >
> >
> > So I look at the index itself :
> >
> > sitefr=# \d ix_session_nomsession
> > Index "ix_session_nomsession"
> >  Attribute  | Type
> > ------------+------
> >  nomsession | text
> > btree
> >
> >
> > Did I miss something or 'text' attributes (fields) can't be indexed ?
> > That sounds crazy ! (I vacuum analyzed many times)
> >
> > Just in case 'nomsession' would not be as dispersed as I would
> > think...
> >
> > sitefr=# select count(nomsession) from session;
> >  count
> > --------
> >  510069
> > (1 row)
> >
> > sitefr=# select count(distinct nomsession) from session;
> >  count
> > --------
> >  401094
> > (1 row)

--
Joseph Shraibman
jks@selectacast.net
Increase signal to noise ratio.  http://www.targabot.com

On Mon, 19 Feb 2001, Joseph Shraibman wrote:

> Stephan Szabo wrote:
> >
> > Do you have a value that is not null that is very common?
> > It's estimating that there will be 10113 rows that match
> > nomsession='xxx' which makes a seq scan a much less bad plan.
> >
> Err, why?  There is an index, isn't there?  Shouldn't the index allow
> postgres to quickly find the %2 of rows that would match?

Right now it has to go to the heap file to find out whether or not
a row is currently visible to the transaction which means potentially
alot of seeks and reads from the heap file which can be more expensive
than just sequentially reading from the heap file depending on a bunch
of things such as how wide the rows are (if there are 100 rows per
block in the heap file and 500000 rows, you need to do 5000 reads.
If you are looking for 10000 rows in that file, you're likely (always?)
going to end up doing 10000 heap file reads plus the reads on the
index file.)

Joseph Shraibman <jks@selectacast.net> writes:
> Stephan Szabo wrote:
>> Do you have a value that is not null that is very common?
>> It's estimating that there will be 10113 rows that match
>> nomsession='xxx' which makes a seq scan a much less bad plan.
>>
> Err, why?  There is an index, isn't there?  Shouldn't the index allow
> postgres to quickly find the %2 of rows that would match?

Define "quickly".

> sitefr=# explain select nomsession from session where nomsession='xxx';
> NOTICE:  QUERY PLAN:
>
> Seq Scan on session  (cost=0.00..16275.95 rows=10113 width=12)

We have here an estimate that 10113 rows will be matched (out of the
510069 in the table).  The table contains something on the order of
16000 pages (guesstimate from the seqscan cost estimate).  The planner
is assuming that the 10113 rows are randomly scattered in the table,
and therefore that the executor will have to fetch the majority of the
pages in the table.  Under these circumstances a seqscan is cheaper
than an indexscan, because it works with the Unix kernel's preference
for sequential reads (to say nothing of the disk drive's ;-)), instead
of fighting that optimization.  Random fetches are more than twice as
expensive as sequential fetches.

Of course, if the 10113-match estimate is wildly off (as it was in this
case), then the wrong plan may be chosen.  But it IS NOT CORRECT to
suppose that indexscans always beat seqscans.  The planner's job would
be a lot easier if that were true.

            regards, tom lane

Tom Lane wrote:
>
> Joseph Shraibman <jks@selectacast.net> writes:
> > Stephan Szabo wrote:
> >> Do you have a value that is not null that is very common?
> >> It's estimating that there will be 10113 rows that match
> >> nomsession='xxx' which makes a seq scan a much less bad plan.
> >>
> > Err, why?  There is an index, isn't there?  Shouldn't the index allow
> > postgres to quickly find the %2 of rows that would match?
>
> Define "quickly".
>
> > sitefr=# explain select nomsession from session where nomsession='xxx';
> > NOTICE:  QUERY PLAN:
> >
> > Seq Scan on session  (cost=0.00..16275.95 rows=10113 width=12)
>
> We have here an estimate that 10113 rows will be matched (out of the
> 510069 in the table).  The table contains something on the order of
> 16000 pages (guesstimate from the seqscan cost estimate).  The planner
> is assuming that the 10113 rows are randomly scattered in the table,
> and therefore that the executor will have to fetch the majority of the
> pages in the table.  Under these circumstances a seqscan is cheaper
> than an indexscan, because it works with the Unix kernel's preference
> for sequential reads (to say nothing of the disk drive's ;-)), instead
> of fighting that optimization.  Random fetches are more than twice as
> expensive as sequential fetches.
>
> Of course, if the 10113-match estimate is wildly off (as it was in this
> case), then the wrong plan may be chosen.  But it IS NOT CORRECT to
> suppose that indexscans always beat seqscans.  The planner's job would
> be a lot easier if that were true.
>
>                         regards, tom lane

Can't postgres do the index lookup first and find out there are only a
few tuples that might match?

--
Joseph Shraibman
jks@selectacast.net
Increase signal to noise ratio.  http://www.targabot.com

Joseph Shraibman wrote:
>

> Can't postgres do the index lookup first and find out there are only a
> few tuples that might match?
>

Actually it looks like postgres is doing this:

o=# explain select * from usertable where p = 33;
NOTICE:  QUERY PLAN:

Seq Scan on usertable  (cost=0.00..30.54 rows=502 width=72)

EXPLAIN
o=# explain select * from usertable where p = 1;
NOTICE:  QUERY PLAN:

Index Scan using usertable_p_key on usertable  (cost=0.00..25.68 rows=50
width=72)

EXPLAIN
o=# explain select count(*) from usertable where p = 1;
NOTICE:  QUERY PLAN:

Aggregate  (cost=25.81..25.81 rows=1 width=4)
  ->  Index Scan using usertable_p_key on usertable  (cost=0.00..25.68
rows=50 width=4)

EXPLAIN
o=# explain select count(*) from usertable where p = 33;
NOTICE:  QUERY PLAN:

Aggregate  (cost=31.79..31.79 rows=1 width=4)
  ->  Seq Scan on usertable  (cost=0.00..30.54 rows=502 width=4)

o=# select count(*) from usertable where p in(1,33) group by p;
 count
-------
    16
   502
(2 rows)

This raises some other questions.  Why can't postgres get the count(*)
from the index?  Why doesn't it predict the correct number of rows in
the planner? (25 estimated vs 16 actual).


--
Joseph Shraibman
jks@selectacast.net
Increase signal to noise ratio.  http://www.targabot.com

On Mon, 19 Feb 2001, Joseph Shraibman wrote:

> > Of course, if the 10113-match estimate is wildly off (as it was in this
> > case), then the wrong plan may be chosen.  But it IS NOT CORRECT to
> > suppose that indexscans always beat seqscans.  The planner's job would
> > be a lot easier if that were true.
>
> Can't postgres do the index lookup first and find out there are only a
> few tuples that might match?

Well, theoretically the estimate is supposed to match reality.  There are
still some cases where there isn't enough information kept to allow that
to be true (the case where there is a single very common non-NULL value is
one such case).

Joseph Shraibman <jks@selectacast.net> writes:
> This raises some other questions.  Why can't postgres get the count(*)
> from the index?  Why doesn't it predict the correct number of rows in
> the planner? (25 estimated vs 16 actual).

The name of the game here is to make a plan *without* actually going
out and expending large amounts of time to find out the true state of
affairs; by the time you know for sure, you've already done the query.
We have to do a certain amount of guessing, otherwise the planner will
be a net drag on performance.  Accordingly, the estimates will never be
perfectly accurate.

            regards, tom lane

On Mon, 19 Feb 2001, Joseph Shraibman wrote:

> Joseph Shraibman wrote:
> >
>
> > Can't postgres do the index lookup first and find out there are only a
> > few tuples that might match?
> >
>

> o=# select count(*) from usertable where p in(1,33) group by p;
>  count
> -------
>     16
>    502
> (2 rows)
>

> This raises some other questions.  Why can't postgres get the count(*)
> from the index?  Why doesn't it predict the correct number of rows in
> the planner? (25 estimated vs 16 actual).

First question: Mostly the same reason.  Not all of the index entries
are necessarily real active rows that you can see, so you would still
have to hit the heap file to get that data, so I'd guess you're already
hitting the entire heap file.

[Tom answered the second]

Tom Lane wrote:
>
> Joseph Shraibman <jks@selectacast.net> writes:
> > This raises some other questions.  Why can't postgres get the count(*)
> > from the index?  Why doesn't it predict the correct number of rows in
> > the planner? (25 estimated vs 16 actual).
>
> The name of the game here is to make a plan *without* actually going
> out and expending large amounts of time to find out the true state of
> affairs; by the time you know for sure, you've already done the query.

Well I'd hope that extracting the count from the index should be very
low cost.  That is what indecies are for.

> We have to do a certain amount of guessing, otherwise the planner will
> be a net drag on performance.  Accordingly, the estimates will never be
> perfectly accurate.

But certain things could be done.  Like planning for the case of there
being a single not null value, and updating the indecies not to point at
expired rows.  Isn't the point of a vacuum to get rid of old rows?  Then
why doesn't it update the index as well?

I mean the explain shows that getting the count(*) from the field that
is indexed has to do a seq scan, presumably to determine if the rows are
in fact valid.  That is ridiculous.


--
Joseph Shraibman
jks@selectacast.net
Increase signal to noise ratio.  http://www.targabot.com

Stephan Szabo wrote:
>
> On Mon, 19 Feb 2001, Joseph Shraibman wrote:
>
> > > Of course, if the 10113-match estimate is wildly off (as it was in this
> > > case), then the wrong plan may be chosen.  But it IS NOT CORRECT to
> > > suppose that indexscans always beat seqscans.  The planner's job would
> > > be a lot easier if that were true.
> >
> > Can't postgres do the index lookup first and find out there are only a
> > few tuples that might match?
>
> Well, theoretically the estimate is supposed to match reality.  There are
> still some cases where there isn't enough information kept to allow that
> to be true (the case where there is a single very common non-NULL value is
> one such case).

But the index should give the upper bounds of the query and show that
this that this query is not going to return 10113 rows.  It appeared to
work like this in my query.  I don't really know what his database is
like or how many times it was updated since he last vacuumed, but it
seems that postgres should have been able to tell that query would have
returned much less than 10113 entries.

--
Joseph Shraibman
jks@selectacast.net
Increase signal to noise ratio.  http://www.targabot.com

On Mon, 19 Feb 2001, Joseph Shraibman wrote:

> Stephan Szabo wrote:
> >
> > On Mon, 19 Feb 2001, Joseph Shraibman wrote:
> >
> > > > Of course, if the 10113-match estimate is wildly off (as it was in this
> > > > case), then the wrong plan may be chosen.  But it IS NOT CORRECT to
> > > > suppose that indexscans always beat seqscans.  The planner's job would
> > > > be a lot easier if that were true.
> > >
> > > Can't postgres do the index lookup first and find out there are only a
> > > few tuples that might match?
> >
> > Well, theoretically the estimate is supposed to match reality.  There are
> > still some cases where there isn't enough information kept to allow that
> > to be true (the case where there is a single very common non-NULL value is
> > one such case).
>
> But the index should give the upper bounds of the query and show that
> this that this query is not going to return 10113 rows.  It appeared to
> work like this in my query.  I don't really know what his database is
> like or how many times it was updated since he last vacuumed, but it
> seems that postgres should have been able to tell that query would have
> returned much less than 10113 entries.

The problem is that the stats that are kept are woefully inadequate for
these cases.  The problem is basically that IIRC it's taking the
most common value's # of appearances and using a fraction of that
as the estimate for any other value.  This is not a really meaningful
estimate of the number of rows to return and there's been talk of how
to add more detailed statistics to make this number more meaningful.
And btree indexes really aren't all that good for getting the exact
number of entries - you'd be better off keeping that number somewhere
else, but MVCC would probably make that difficult, since I'd guess
that the different versions of rows would each have index entries
and not all of them apply to your transaction - which is why I think
it goes to the heap to test for visibility.

Stephan Szabo wrote:
>
> On Mon, 19 Feb 2001, Joseph Shraibman wrote:
>
> > Stephan Szabo wrote:
> > >
> > > On Mon, 19 Feb 2001, Joseph Shraibman wrote:
> > >
> > > > > Of course, if the 10113-match estimate is wildly off (as it was in this
> > > > > case), then the wrong plan may be chosen.  But it IS NOT CORRECT to
> > > > > suppose that indexscans always beat seqscans.  The planner's job would
> > > > > be a lot easier if that were true.
> > > >
> > > > Can't postgres do the index lookup first and find out there are only a
> > > > few tuples that might match?
> > >
> > > Well, theoretically the estimate is supposed to match reality.  There are
> > > still some cases where there isn't enough information kept to allow that
> > > to be true (the case where there is a single very common non-NULL value is
> > > one such case).
> >
> > But the index should give the upper bounds of the query and show that
> > this that this query is not going to return 10113 rows.  It appeared to
> > work like this in my query.  I don't really know what his database is
> > like or how many times it was updated since he last vacuumed, but it
> > seems that postgres should have been able to tell that query would have
> > returned much less than 10113 entries.
>
> The problem is that the stats that are kept are woefully inadequate for
> these cases.  The problem is basically that IIRC it's taking the
> most common value's # of appearances and using a fraction of that
> as the estimate for any other value.  This is not a really meaningful
> estimate of the number of rows to return and there's been talk of how
> to add more detailed statistics to make this number more meaningful.
> And btree indexes really aren't all that good for getting the exact
> number of entries - you'd be better off keeping that number somewhere
> else, but MVCC would probably make that difficult, since I'd guess
> that the different versions of rows would each have index entries
> and not all of them apply to your transaction - which is why I think
> it goes to the heap to test for visibility.

You didn't address my point.  The point was that an explain shows that
it is using the index to get an upper bounds, so why isn't it using
that?

--
Joseph Shraibman
jks@selectacast.net
Increase signal to noise ratio.  http://www.targabot.com

On Tue, 20 Feb 2001, Joseph Shraibman wrote:

> > > But the index should give the upper bounds of the query and show that
> > > this that this query is not going to return 10113 rows.  It appeared to
> > > work like this in my query.  I don't really know what his database is
> > > like or how many times it was updated since he last vacuumed, but it
> > > seems that postgres should have been able to tell that query would have
> > > returned much less than 10113 entries.
> >
> > The problem is that the stats that are kept are woefully inadequate for
> > these cases.  The problem is basically that IIRC it's taking the
> > most common value's # of appearances and using a fraction of that
> > as the estimate for any other value.  This is not a really meaningful
> > estimate of the number of rows to return and there's been talk of how
> > to add more detailed statistics to make this number more meaningful.
> > And btree indexes really aren't all that good for getting the exact
> > number of entries - you'd be better off keeping that number somewhere
> > else, but MVCC would probably make that difficult, since I'd guess
> > that the different versions of rows would each have index entries
> > and not all of them apply to your transaction - which is why I think
> > it goes to the heap to test for visibility.
>
> You didn't address my point.  The point was that an explain shows that
> it is using the index to get an upper bounds, so why isn't it using
> that?

Where are you seeing something that says the estimator/planner using the
index to get an upper bound?  The estimator shouldn't be asking either the
index or the heap for anything, it should be working entirely with the
statistics that were generated from vacuum.

Stephan Szabo wrote:

> Where are you seeing something that says the estimator/planner using the
> index to get an upper bound?  The estimator shouldn't be asking either the
> index or the heap for anything, it should be working entirely with the
> statistics that were generated from vacuum.

Index Scan using usertable_p_key on usertable  (cost=0.00..25.68 rows=50
width=72)

That rows=50, which is an overestimate by the way.

--
Joseph Shraibman
jks@selectacast.net
Increase signal to noise ratio.  http://www.targabot.com

On Tue, 20 Feb 2001, Joseph Shraibman wrote:

> Stephan Szabo wrote:
>
> > Where are you seeing something that says the estimator/planner using the
> > index to get an upper bound?  The estimator shouldn't be asking either the
> > index or the heap for anything, it should be working entirely with the
> > statistics that were generated from vacuum.
>
> Index Scan using usertable_p_key on usertable  (cost=0.00..25.68 rows=50
> width=72)
>
> That rows=50, which is an overestimate by the way.

That's because the estimate in this case was 50 and so it's estimating
that going through the index and checking the heap is faster than a
sequence scan.  The *estimator* didn't use the index to figure that out,
it's just saying that the best plan to actually *run* the query uses
the index.
IIRC, There's something which is effectively :
estimated rows = <most common value's frequency>*<fraction>
I think fraction defaults to (is always?) 1/10 for the standard
index type.  That's where the 50 comes from. And the frequency is
probably from the last vacuum analyze.

Stephan Szabo wrote:
>
> On Tue, 20 Feb 2001, Joseph Shraibman wrote:
>
> > Stephan Szabo wrote:
> >
> > > Where are you seeing something that says the estimator/planner using the
> > > index to get an upper bound?  The estimator shouldn't be asking either the
> > > index or the heap for anything, it should be working entirely with the
> > > statistics that were generated from vacuum.
> >
> > Index Scan using usertable_p_key on usertable  (cost=0.00..25.68 rows=50
> > width=72)
> >
> > That rows=50, which is an overestimate by the way.
>
> That's because the estimate in this case was 50 and so it's estimating
> that going through the index and checking the heap is faster than a
> sequence scan.  The *estimator* didn't use the index to figure that out,
> it's just saying that the best plan to actually *run* the query uses
> the index.
> IIRC, There's something which is effectively :
> estimated rows = <most common value's frequency>*<fraction>
> I think fraction defaults to (is always?) 1/10 for the standard
> index type.  That's where the 50 comes from. And the frequency is
> probably from the last vacuum analyze.

Then it should do the same thing no matter what value I use, but when I
do different searches in one case it estimates 50 when there are 16 and
in the other it estimeates 502 where there are 502.


--
Joseph Shraibman
jks@selectacast.net
Increase signal to noise ratio.  http://www.targabot.com

On Tue, 20 Feb 2001, Joseph Shraibman wrote:

> > That's because the estimate in this case was 50 and so it's estimating
> > that going through the index and checking the heap is faster than a
> > sequence scan.  The *estimator* didn't use the index to figure that out,
> > it's just saying that the best plan to actually *run* the query uses
> > the index.
> > IIRC, There's something which is effectively :
> > estimated rows = <most common value's frequency>*<fraction>
> > I think fraction defaults to (is always?) 1/10 for the standard
> > index type.  That's where the 50 comes from. And the frequency is
> > probably from the last vacuum analyze.
>
> Then it should do the same thing no matter what value I use, but when I
> do different searches in one case it estimates 50 when there are 16 and
> in the other it estimeates 502 where there are 502.

It knows enough to do the special case where you are searching for the
most common value.  I'd guess that's what's happening on the 502.
I think it stores the most common value and the fraction of rows that
represents as of last vacuum analyze.

Joseph Shraibman <jks@selectacast.net> writes:
> Then it should do the same thing no matter what value I use, but when I
> do different searches in one case it estimates 50 when there are 16 and
> in the other it estimeates 502 where there are 502.

Well, it does know the difference between searching for the most common
value and searching for other values, but whether that's relevant to
your example is impossible to say with no details.

            regards, tom lane

On Tue, Feb 20, 2001 at 05:02:22PM -0800, Stephan Szabo wrote:
>
> IIRC, There's something which is effectively :
> estimated rows = <most common value's frequency>*<fraction>
> I think fraction defaults to (is always?) 1/10 for the standard
> index type.  That's where the 50 comes from. And the frequency is
> probably from the last vacuum analyze.

Is there a way to change this fraction?

We have a table with over 1 million rows and the statistics Postgres gathers
are not particularly useful. There is not one (non-null) value that occurs
significantly more often than other values but the distribution looks a lot
like a 1/x curve I guess. The most common value occurs 5249 times but the
average is only 95, so Postgres chooses seq scan almost always. We actually
now set enable_seqscan=off in many areas of our code to speed it up to a
useful rate. (This table also happens to have an (accedental) clustering on
this column also).

What is the reasoning behind estimating like that? Why not just the average
or the average + 1 SD?

Another idea, is there a use for making a "cohesiveness" index. ie. if
you're looking X by looking up the index, on average, how many also matching
tuples will be in the next 8k (or whatever size). Since these are likely to
be in the cache the cost of retreival would be much lower. This would mean
that an index on a clustered column would have a much lower estimated cost
than an index on other columns. This would make clustering more useful.

I think I'll stop rambling now...

Martijn

On Wed, 21 Feb 2001, Martijn van Oosterhout wrote:

> On Tue, Feb 20, 2001 at 05:02:22PM -0800, Stephan Szabo wrote:
> >
> > IIRC, There's something which is effectively :
> > estimated rows = <most common value's frequency>*<fraction>
> > I think fraction defaults to (is always?) 1/10 for the standard
> > index type.  That's where the 50 comes from. And the frequency is
> > probably from the last vacuum analyze.
>
> Is there a way to change this fraction?
>
> We have a table with over 1 million rows and the statistics Postgres gathers
> are not particularly useful. There is not one (non-null) value that occurs
> significantly more often than other values but the distribution looks a lot
> like a 1/x curve I guess. The most common value occurs 5249 times but the
> average is only 95, so Postgres chooses seq scan almost always. We actually
> now set enable_seqscan=off in many areas of our code to speed it up to a
> useful rate. (This table also happens to have an (accedental) clustering on
> this column also).
>
> What is the reasoning behind estimating like that? Why not just the average
> or the average + 1 SD?
>
> Another idea, is there a use for making a "cohesiveness" index. ie. if
> you're looking X by looking up the index, on average, how many also matching
> tuples will be in the next 8k (or whatever size). Since these are likely to
> be in the cache the cost of retreival would be much lower. This would mean
> that an index on a clustered column would have a much lower estimated cost
> than an index on other columns. This would make clustering more useful.

Well, there's been talk about keeping better statistics in the future (see
hackers archives, I can't remember the thread though, it was a while ago).
Keeping the most common frequency and some kind of frequency graph or
standard deviation would probably be useful.  As for cohesiveness, that
gets kind of difficult to keep track of as changes are made but could
probably be of some use to the estimator.

As far as I know the only way to change the fraction is through
recompiling but Tom would probably know better about that, unfortunately
that's a really big stick to hit the problem with.

> Well, who said about keeping track of changes? If the table is large chances
> are that this value would change very quickly. If the table is small it
> doesn't matter. It just seems to me to be the best way make clustering work
> better.

Yes, it probably is.  I have some concerns about when it's wrong, but if
you're doing that many changes you probably need to run vacuum analyze
again anyway.

> > As far as I know the only way to change the fraction is through
> > recompiling but Tom would probably know better about that, unfortunately
> > that's a really big stick to hit the problem with.
>
> I realize that keeping better statistics is the best solution. However, not
> all types data can have a standard deviation since you need some form of
> order and that is not obvious in many cases...

True, but the same thing is pretty much true for a btree index.  Maybe
in those cases, you just want to keep those kind of statistics on the
frequencies themselves.  Since you can't really determine if something
is more likely to be high by its value (unless it's the most common),
you can try to keep info about where the most common frequency is and how
dispersed the frequencies are.

The big stick wasn't against the doing of it, just that there might exist
some tables where the current estimate is closer and you can't easily
change that per-table, except...
One thing that might be interesting is to see what it does if you tried
changing stacommonfraq in pg_statistic for that relation after a vacuum
analyze.  That should change how many rows it thinks the most common value
has.  I'm not sure of any side effects, but it seems to immediately change
my row estimates from explain.  If you set it high enough that you still
get a sequence scan for the most common, but low enough that the others
given index scan, you might be okay.

Martijn van Oosterhout <kleptog@svana.org> writes:
> We have a table with over 1 million rows and the statistics Postgres gathers
> are not particularly useful. There is not one (non-null) value that occurs
> significantly more often than other values but the distribution looks a lot
> like a 1/x curve I guess. The most common value occurs 5249 times but the
> average is only 95, so Postgres chooses seq scan almost always. We actually
> now set enable_seqscan=off in many areas of our code to speed it up to a
> useful rate. (This table also happens to have an (accedental) clustering on
> this column also).

> What is the reasoning behind estimating like that? Why not just the average
> or the average + 1 SD?

Can you think of a reasonable algorithm for VACUUM to obtain the true
average frequency?  It has a tough enough time estimating the most
common frequency with any reliability.  Given complaints in nearby
threads that VACUUM ANALYZE is too slow, it'd be a good idea if your
algorithm was faster than the current one, too ;-)

We have kicked around the idea of scanning a btree index (if available)
rather than the main table.  This would make it a *lot* easier to obtain
reliable frequency statistics, since you'd know that all the instances
of a given value would be seen in sequence, and you could count them
with trivial logic rather than having a difficult estimation problem.
(The fact that some might represent dead tuples probably isn't a problem,
especially since we just vacuumed.)  Not done yet though, and there's
some issues still to be surmounted.

> Another idea, is there a use for making a "cohesiveness" index. ie. if
> you're looking X by looking up the index, on average, how many also matching
> tuples will be in the next 8k (or whatever size). Since these are likely to
> be in the cache the cost of retreival would be much lower. This would mean
> that an index on a clustered column would have a much lower estimated cost
> than an index on other columns. This would make clustering more useful.

Again, estimating this number with any reliability seems a hard problem.
Got any ideas?

What I've been thinking of is simply maintaining a flag that says "this
table has been clustered on this index" (a fact not now stored anywhere)
and having the planner change cost estimates accordingly.  The accuracy
of the cost estimates would degrade as the table is updated and drifts
away from clustered order, but it seems *very* hard to estimate that
process.  One answer is not to try, but to assume that the dbadmin will
re-cluster the table often enough so that it stays in pretty good order.

At the moment I'm hesitant to do anything that encourages use of CLUSTER
at all, because of the horrible side-effects it has.  So personally I
think this is further down the to-do queue than rewriting CLUSTER.

            regards, tom lane

Stephan Szabo <sszabo@megazone23.bigpanda.com> writes:
> One thing that might be interesting is to see what it does if you tried
> changing stacommonfraq in pg_statistic for that relation after a vacuum
> analyze.  That should change how many rows it thinks the most common value
> has.  I'm not sure of any side effects, but it seems to immediately change
> my row estimates from explain.

AFAIK there aren't any side effects; you can manually twiddle
pg_statistic as much as you like.  Of course, your hacks will get
overwritten at the next vacuum analyze of the table, but if you're
convinced you've got the perfect numbers in there, you could just not
ever do a vacuum analyze ;-)

            regards, tom lane

From: "Tom Lane" <tgl@sss.pgh.pa.us>

> Martijn van Oosterhout <kleptog@svana.org> writes:
> > We have a table with over 1 million rows and the statistics Postgres
gathers
> > are not particularly useful. There is not one (non-null) value that
occurs
> > significantly more often than other values but the distribution looks a
lot
> > like a 1/x curve I guess. The most common value occurs 5249 times but
the
> > average is only 95, so Postgres chooses seq scan almost always. We
actually
> > now set enable_seqscan=off in many areas of our code to speed it up to a
> > useful rate. (This table also happens to have an (accedental) clustering
on
> > this column also).
>
> > What is the reasoning behind estimating like that? Why not just the
average
> > or the average + 1 SD?
>
> Can you think of a reasonable algorithm for VACUUM to obtain the true
> average frequency?  It has a tough enough time estimating the most
> common frequency with any reliability.  Given complaints in nearby
> threads that VACUUM ANALYZE is too slow, it'd be a good idea if your
> algorithm was faster than the current one, too ;-)

I'm don't see that there's any way that you're going to get an analyser that
_always_ gets it right. Might there not be some way of explicitly telling
the analyser the distribution of the data. Like Martijn says above, he
thinks the distribution is something like 1/x. In the cases where you really
care you probably do know what sort of values are stored.

I have to admit my maths isn't good enough to say how sensible an idea this
is, but figured I'd put my tuppence-worth in.

- Richard Huxton

On Tue, Feb 20, 2001 at 11:44:15PM -0800, Stephan Szabo wrote:
> On Wed, 21 Feb 2001, Martijn van Oosterhout wrote:
>
> > On Tue, Feb 20, 2001 at 05:02:22PM -0800, Stephan Szabo wrote:
> > >
> > > IIRC, There's something which is effectively :
> > > estimated rows = <most common value's frequency>*<fraction>
> > > I think fraction defaults to (is always?) 1/10 for the standard
> > > index type.  That's where the 50 comes from. And the frequency is
> > > probably from the last vacuum analyze.
> >
> > Is there a way to change this fraction?
> >
> > We have a table with over 1 million rows and the statistics Postgres gathers
> > are not particularly useful. There is not one (non-null) value that occurs
> > significantly more often than other values but the distribution looks a lot
> > like a 1/x curve I guess. The most common value occurs 5249 times but the
> > average is only 95, so Postgres chooses seq scan almost always. We actually
> > now set enable_seqscan=off in many areas of our code to speed it up to a
> > useful rate. (This table also happens to have an (accedental) clustering on
> > this column also).
> >
> > What is the reasoning behind estimating like that? Why not just the average
> > or the average + 1 SD?
> >
> > Another idea, is there a use for making a "cohesiveness" index. ie. if
> > you're looking X by looking up the index, on average, how many also matching
> > tuples will be in the next 8k (or whatever size). Since these are likely to
> > be in the cache the cost of retreival would be much lower. This would mean
> > that an index on a clustered column would have a much lower estimated cost
> > than an index on other columns. This would make clustering more useful.
>
> Well, there's been talk about keeping better statistics in the future (see
> hackers archives, I can't remember the thread though, it was a while ago).
> Keeping the most common frequency and some kind of frequency graph or
> standard deviation would probably be useful.  As for cohesiveness, that
> gets kind of difficult to keep track of as changes are made but could
> probably be of some use to the estimator.

Well, who said about keeping track of changes? If the table is large chances
are that this value would change very quickly. If the table is small it
doesn't matter. It just seems to me to be the best way make clustering work
better.

> As far as I know the only way to change the fraction is through
> recompiling but Tom would probably know better about that, unfortunately
> that's a really big stick to hit the problem with.

I realize that keeping better statistics is the best solution. However, not
all types data can have a standard deviation since you need some form of
order and that is not obvious in many cases...

Oh well,

--
Martijn van Oosterhout <kleptog@cupid.suninternet.com>
http://cupid.suninternet.com/~kleptog/