Subject: index vs. seq scan choice?

From: "George Pavlov" <[email-masked]>
Date: Thu, 24 May 2007 16:15:54 -0700

I am trying to figure out how the distribution of data affects index
usage by the query because I am seeing some behavior that does not seem
optimal to my uneducated eye. 

I am on PG 8.1.8. I have two tables foo and foo_detail, both have been
vacuum analyzed recently. Both have a property_id column, both have an
index on it. The foo table has a state_code, also indexed, and the
relative share of rows for the two state_codes used in the example below
is:
  PA 	2842	2.80%
  MN 	2858	2.81%

The distribution of distinct property_ids is fairly similar:
  PA 	719	2.90%
  MN 	765	3.09%

A simple query filtered by PA vs. MN produces different results (see
below). The PA query does a Seq Scan, the MN query uses the index and is
>20 times faster. Both return about the same number of rows. I tried it
with all state_codes that have rows in foo and it seems that the cutoff
is somewhere around 3%, but there isn't a direct correlation (there are
state_codes that are < 3% that trigger a Seq Scan and there are ones
above 3% that result in an Index scan).

I am curious what could make the PA query to ignore the index. What are
the specific stats that are being used to make this decision? Would it
perform better if it were to use the index? Anything I can do to "nudge"
it towards using the index, which seems like a rather beneficial thing?

The actual queries:

explain analyze
select
  f.property_id
from foo f
  inner join foo_detail fd using (property_id)
where f.state_code = 'PA'

Merge Join  (cost=17842.71..18436.30 rows=3347 width=4) (actual
time=594.538..972.032 rows=2842 loops=1)
  Merge Cond: ("outer".property_id = "inner".property_id)
  ->  Sort  (cost=4381.72..4390.09 rows=3347 width=4) (actual
time=14.092..18.497 rows=2842 loops=1)
        Sort Key: f.property_id
        ->  Bitmap Heap Scan on foo f  (cost=22.71..4185.78 rows=3347
width=4) (actual time=0.826..7.008 rows=2842 loops=1)
              Recheck Cond: (state_code = 'PA'::bpchar)
              ->  Bitmap Index Scan on mv_search_state
(cost=0.00..22.71 rows=3347 width=0) (actual time=0.734..0.734 rows=2842
loops=1)
                    Index Cond: (state_code = 'PA'::bpchar)
  ->  Sort  (cost=13460.99..13732.84 rows=108742 width=4) (actual
time=580.312..754.012 rows=110731 loops=1)
        Sort Key: fd.property_id
        ->  Seq Scan on foo_detail fd  (cost=0.00..4364.42 rows=108742
width=4) (actual time=0.006..210.846 rows=108742 loops=1)
Total runtime: 991.852 ms

explain analyze
select
  f.property_id
from foo f
  inner join foo_detail fd using (property_id)
where f.state_code = 'MN'

Nested Loop  (cost=7.62..8545.85 rows=1036 width=4) (actual
time=0.877..44.196 rows=2858 loops=1)
  ->  Bitmap Heap Scan on foo f  (cost=7.62..2404.44 rows=1036 width=4)
(actual time=0.852..6.579 rows=2858 loops=1)
        Recheck Cond: (state_code = 'MN'::bpchar)
        ->  Bitmap Index Scan on mv_search_state  (cost=0.00..7.62
rows=1036 width=0) (actual time=0.744..0.744 rows=2858 loops=1)
              Index Cond: (state_code = 'MN'::bpchar)
  ->  Index Scan using ix_fd on foo_detail fd  (cost=0.00..5.92 rows=1
width=4) (actual time=0.005..0.007 rows=1 loops=2858)
        Index Cond: ("outer".property_id = fd.property_id)
Total runtime: 48.439 ms

---

From: Tom Lane <[email-masked]>
Date: Thu, 24 May 2007 21:08:11 -0400

"George Pavlov" <[email-masked]> writes:
> the specific stats that are being used to make this decision?

The frequency of the specific value being searched for, and the overall
order-correlation of the column.  Since the latter is not dependent on a
particular value, my guess at the reason for the inconsistent results is
that you don't have the column's statistics target set high enough to
track all the interesting values --- or maybe just not high enough to
acquire sufficiently accurate frequency estimates for them.  Take a look
at the pg_stats row for the column ...

(The default statistics target is 10, which is widely considered too
low --- you might find 100 more suitable.)

			regards, tom lane

---

From: Alvaro Herrera <[email-masked]>
Date: Thu, 24 May 2007 22:39:22 -0400

> low --- you might find 100 more suitable.)

Does this mean that we should look into raising the default a bit?

-- 
Alvaro Herrera                                http://www.CommandPrompt.com/
The PostgreSQL Company - Command Prompt, Inc.

---

From: Tom Lane <[email-masked]>
Date: Thu, 24 May 2007 22:45:17 -0400

> Does this mean that we should look into raising the default a bit?

Probably ... the question is to what.

The default of 10 was chosen in our usual spirit of conservatism ---
and IIRC it was replacing code that tracked only *one* most common
value, so it was already a factor of 10 better (and more expensive)
than what was there before.  But subsequent history suggests it's
too small.  I'm not sure I want to vote for another 10x increase by
default, though.

			regards, tom lane

---------------------------(end of broadcast)---------------------------
TIP 1: if posting/reading through Usenet, please send an appropriate
       subscribe-nomail command to [email-masked] so that your
       message can get through to the mailing list cleanly

--ELM1205260229-7949-1_--

---

From: "Joshua D. Drake" <[email-masked]>
Date: Thu, 24 May 2007 19:57:10 -0700

> too small.  I'm not sure I want to vote for another 10x increase by

Outside of longer analyze times, and slightly more space taken up by the 
statistics, what is the downside? I mean in reality... what is setting 
to 100 going to do to effect actual production usage of even a modest 
machine?

Sincerely,

Joshua D. Drake

-- 

       === The PostgreSQL Company: Command Prompt, Inc. ===
Sales/Support: +1.503.667.4564 || 24x7/Emergency: +1.800.492.2240
Providing the most comprehensive  PostgreSQL solutions since 1997
              http://www.commandprompt.com/

Donate to the PostgreSQL Project: http://www.postgresql.org/about/donate
PostgreSQL Replication: http://www.commandprompt.com/products/

---

From: Tom Lane <[email-masked]>
Date: Thu, 24 May 2007 23:26:08 -0400

"Joshua D. Drake" <[email-masked]> writes:
> Tom Lane wrote:
>> I'm not sure I want to vote for another 10x increase by
>> default, though.

> statistics, what is the downside?

Longer plan times --- several of the selfuncs.c routines grovel over all
the entries in the pg_statistic row.  AFAIK no one's measured the real
impact of that, but it could easily be counterproductive for simple queries.

			regards, tom lane

---

From: Steve Atkins <[email-masked]>
Date: Thu, 24 May 2007 21:25:23 -0700

> impact of that, but it could easily be counterproductive for simple  

The lateness of the hour is suppressing my supposed statistics savvy,
so this may not make sense, but...

Would it be possible to look at a much larger number of samples  
during analyze,
then look at the variation in those to generate a reasonable number of
pg_statistic "samples" to represent our estimate of the actual  
distribution?
More datapoints for tables where the planner might benefit from it,  
fewer
where it wouldn't.

Cheers,
   Steve

---

From: PFC <[email-masked]>
Date: Fri, 25 May 2007 10:09:17 +0200

> Would it be possible to look at a much larger number of samples during  
> analyze,
> More datapoints for tables where the planner might benefit from it, fewer
> where it wouldn't.

	Maybe it would be possible to take note somewhere of the percentage of  
occurence of the most common value (in the OP's case, about 3%), in which  
case a quick decision can be taken to use the index without even looking  
at the value, if we know the most common one is below the index use  
threshold...

---

From: "John D. Burger" <[email-masked]>
Date: Fri, 25 May 2007 08:55:24 -0400

> More datapoints for tables where the planner might benefit from it,  

You could definitely try to measure the variance of the statistics  
(using, say, bootstrap resampling), and change the target 'til you  
got a "good" tradeoff between small sample size and adequate  
representation of the distribution.  Unfortunately, I think the  
definition of "good" depends strongly on the kinds of queries that  
get run.  Basically, you want the statistics target to be just big  
enough that more stats wouldn't change the plans for common queries.   
Remember, too, that this is not just one number, it'd be different  
for each column (perhaps zero for most).

I could imagine hillclimbing the stats targets by storing common  
queries and then replaying them, while varying the sample size.   
There was a discussion last year related to all of this, see:

   http://archives.postgresql.org/pgsql-general/2006-10/msg00526.php

- John D. Burger
   MITRE

---

From: "George Pavlov" <[email-masked]>
Date: Thu, 7 Jun 2007 14:56:06 -0700

> From: Tom Lane [mailto:[email-masked]] 
> you don't have the column's statistics target set high enough to
> acquire sufficiently accurate frequency estimates for them.  
> Take a look at the pg_stats row for the column ...
> 

Well, it seems that it would be more beneficial for me to set it LOWER
than the default 10. I get better performance if the stats are less
accurate because then the optimizer seems more likely to choose the
index! States that are in pg_stats.most_common_vals most often result in
a Seq Scan, whereas ones that are not in it definitely get the Index
Scan. For all states, even the largest ones (15% of the data), the Index
Scan performs better. So, for example, with SET STATISTICS 10 my
benhcmark query in a state like Indiana (2981 rows, ~3% of total) runs
in 132ms. If I SET STATISTICS 100, Indiana gets on the most_common_vals
list for the column and the query does a Seq Scan and its run time jumps
to 977ms! If I go the other way and SET STATISTICS 1 (or 0) I can bring
down the list to one entry (setting to 0 seems equivalent and still
keeps the one most common entry!?) and I will get the Index scan for all
states except for that one most common state. But, of course, I don't
want to undermine the whole stats mechanism, I just want the system to
use the index that is so helpful and brings runtimes down by a factor of
4-8! What am I missing here?

George

---

From: "Joshua D. Drake" <[email-masked]>
Date: Thu, 07 Jun 2007 15:01:51 -0700

> 4-8! What am I missing here?

In those rare cases wouldn't it make more sense to just set 
enable_seqscan to off; run query; set enable_seqscan to on;

??

Joshua D. Drake

> TIP 3: Have you checked our extensive FAQ?
> 
>                http://www.postgresql.org/docs/faq
> 

--

---

From: "George Pavlov" <[email-masked]>
Date: Thu, 7 Jun 2007 15:21:14 -0700

> From: Joshua D. Drake [mailto:[email-masked]]
> 

1. these cases are not that rare (to me);

2. setting enable_seqscan (in JDBC, say) from the application makes the
whole thing quite a mess (need to do a batch of statements: each query
wrapped in its enable/disable seq scan?) -- ideally, one would like to
issue mostly SQL statements, not config parameters from the application;

3. if this is the recommended suggestion on how to run queries then why
don't we just add HINTS to the system and be done with it...

---

From: "Joshua D. Drake" <[email-masked]>
Date: Thu, 07 Jun 2007 15:29:44 -0700

> 1. these cases are not that rare (to me);

I find that surprising.

> issue mostly SQL statements, not config parameters from the application;

Uh no. You do it at the beginning of the transaction, run your queries 
then reset it right before (or after) commit.

> don't we just add HINTS to the system and be done with it...

I suggest you read the archives, twice, before suggesting hints.

--

---

From: Tom Lane <[email-masked]>
Date: Thu, 07 Jun 2007 18:33:48 -0400

> 1. these cases are not that rare (to me);

It strikes me that you probably need to adjust the planner cost
parameters to reflect reality on your system.  Usually dropping
random_page_cost is the way to bias the thing more in favor of
index scans.

			regards, tom lane

---

From: "George Pavlov" <[email-masked]>
Date: Thu, 7 Jun 2007 15:52:16 -0700

> From: Tom Lane

Thanks, Tom, I will try that. Seems better than fiddling with
enable_seqscan around every query/transaction.

Joshua, I fail to understand why setting and unsetting enable_seqscan on
a per query/transaction basis is in any way preferable to query hints?
Don't get me wrong, I don't like the idea of hints, and I have read the
archives on the subject and I agree with the philosophy, but if the
optimization toolkit for routine application queries is going to include
setting config parameters that just smacks of hints by another name...

George

---

From: "Joshua D. Drake" <[email-masked]>
Date: Thu, 07 Jun 2007 15:59:06 -0700

> setting config parameters that just smacks of hints by another name...

I actually have zero opinion on hints, my comment was more about opening 
the wasps nest of the hints discussion more than anything :)

Joshua D. Drake

--

---

From: [email-masked] (Patrick TJ McPhee)
Date: Fri, 08 Jun 2007 04:13:54 -0000

In article <[email-masked]>, Tom Lane <[email-masked]> wrote:
% "George Pavlov" <[email-masked]> writes:
% >> From: Joshua D. Drake [mailto:[email-masked]]
% >> In those rare cases wouldn't it make more sense to just set
% >> enable_seqscan to off; run query; set enable_seqscan to on;
% 
% > 1. these cases are not that rare (to me);
% 
% It strikes me that you probably need to adjust the planner cost
% parameters to reflect reality on your system.  Usually dropping
% random_page_cost is the way to bias the thing more in favor of
% index scans.

Also, increasing effective_cache_size.
(And increasing statistics...)
-- 

Patrick TJ McPhee
North York  Canada
[email-masked]