Thread: Index Puzzle for you
Hi all. Once again I come to you with a puzzle...
I have the following structures (related to this question) in my
[PostgreSQL 6.5.2 on i686-pc-linux-gnu, compiled by gcc egcs-2.91.66]
database according to a pg_dump of the schema (reformatted for
readability):
---------------------------------------------------------------------------
CREATE TABLE "tblissuearticle" ( "ixissue" int4 NOT NULL, "ixarticle" int4 NOT NULL, "ixprocessor"
int4, "ixmember" int4, "iorder" int4, "sstatus" character);
REVOKE ALL on "tblissuearticle" from PUBLIC;
CREATE INDEX "tblissuearticle_oid" on "tblissuearticle" using btree ("oid" "oid_ops" );
CREATE INDEX "tblissuearticle_idx1" on "tblissuearticle" using btree ( "ixissue" "int4_ops",
"ixarticle""int4_ops", "iorder" "int4_ops" );
CREATE INDEX "tblissuearticle_idx2" on "tblissuearticle" using btree ("ixissue" "int4_ops" );
---------------------------------------------------------------------------
Now I enter trusty psql to run some SQL statements. Notice the SECOND
EXPLAIN which I run. I aded the _idx2 index above after this statement
didn't catch _idx1 (partial index). Neither parts matched. I tried
dropping _idx1 and it still didn't use _idx2.
---------------------------------------------------------------------------
mail=> vacuum tblissuearticle ;
VACUUM
mail=> vacuum analyze tblissuearticle ;
VACUUM
mail=> explain select 1 from tblissuearticle where ixissue = 7 and ixarticle = 9;
NOTICE: QUERY PLAN:
Index Scan using tblissuearticle_idx1 on tblissuearticle (cost=228.04 rows=1 width=0)
EXPLAIN
mail=> explain select 1 from tblissuearticle where ixissue = 7;
NOTICE: QUERY PLAN:
Seq Scan on tblissuearticle (cost=4076.63 rows=76338 width=0)
EXPLAIN
mail=> explain verbose select 1 from tblissuearticle where ixissue = 7;
NOTICE: QUERY DUMP:
{ SEQSCAN :cost 4076.63 :size 76338 :width 0 :state <> :qptargetlist ({
TARGETENTRY :resdom { RESDOM :resno 1 :restype 23 :restypmod -1 :resname
"?column?" :reskey 0 :reskeyop 0 :resgroupref 0 :resjunk false } :expr {
CONST :consttype 23 :constlen 4 :constisnull false :constvalue 4 [ 1 0 0 0
] :constbyval true }}) :qpqual ({ EXPR :typeOid 0 :opType op :oper { OPER
:opno 96 :opid 65 :opresulttype 16 } :args ({ VAR :varno 1 :varattno 1
:vartype 23 :vartypmod -1 :varlevelsup 0 :varnoold 1 :varoattno 1} { CONST
:consttype 23 :constlen 4 :constisnullfalse :constvalue 4 [ 7 0 0 0 ]
:constbyval true })}) :lefttree <> :righttree <> :extprm () :locprm ()
:initplan <> :nprm 0 :scanrelid 1 }
NOTICE: QUERY PLAN:
Seq Scan on tblissuearticle (cost=4076.63 rows=76338 width=0)
EXPLAIN
---------------------------------------------------------------------------
Hoping someone can shed some light on this for me. Happy Holidays...
- K
Kristofer Munn * KMI * 973-509-9414 * AIM KrMunn * ICQ 352499 * www.munn.com
Kristofer Munn <kmunn@munn.com> writes:
> [ why does the second example not use an index? ]
> mail=> explain select 1 from tblissuearticle where ixissue = 7
> and ixarticle = 9;
> Index Scan using tblissuearticle_idx1 on tblissuearticle
> (cost=228.04 rows=1 width=0)
> mail=> explain select 1 from tblissuearticle where ixissue = 7;
> Seq Scan on tblissuearticle (cost=4076.63 rows=76338 width=0)
The thing that jumps out at me from this example is the much larger
estimate of returned rows in the second case. The planner is clearly
estimating that "ixissue = 7" alone is not very selective. That might
or might not be reasonable (how many rows are in the table, and what's
the actual distribution of ixissue values?), but if it is reasonable
then a sequential scan might indeed be the right choice. Index scans
are not always better than sequential scans --- the planner's job would
be far simpler if they were ;-)
regards, tom lane
Tom Lane wrote: > The thing that jumps out at me from this example is the much larger > estimate of returned rows in the second case. The planner is clearly Good catch! There were 296 possible issues the table. One had 86,544 articles associated with it. The next highest was 5,949. Then the numbers drop to 630, 506, 412, 184 and then the rest are all under 62. Out of curiosity, how does vacuum decide on the large estimate? The maximum is 86,544. The average row return for ixissue = x is 3412. The median is 25. The mode is 25. ixissue is the result of a sequence. Thanks for the heads up on this... - K Kristofer Munn * KMI * 973-509-9414 * AIM KrMunn * ICQ 352499 * www.munn.com
> Tom Lane wrote: > > The thing that jumps out at me from this example is the much larger > > estimate of returned rows in the second case. The planner is clearly > > Good catch! There were 296 possible issues the table. One had 86,544 > articles associated with it. The next highest was 5,949. Then the > numbers drop to 630, 506, 412, 184 and then the rest are all under 62. > Out of curiosity, how does vacuum decide on the large estimate? > > The maximum is 86,544. > The average row return for ixissue = x is 3412. > The median is 25. > The mode is 25. > > ixissue is the result of a sequence. > > Thanks for the heads up on this... Here is the relevent comment from vacuum.c. It is not perfect, but was the best thing I could think of. --------------------------------------------------------------------------- /** vc_attrstats() -- compute column statistics used by the optimzer** We compute the column min, max, null and non-nullcounts.* Plus we attempt to find the count of the value that occurs most* frequently in each column. These figuresare used to compute * the selectivity of the column.** We use a three-bucked cache to get the most frequent item.* The 'guess' buckets count hits. A cache miss causes guess1* to get the most hit 'guess' item in the most recentcycle, and* the new item goes into guess2. Whenever the total count of hits* of a 'guess' entry is larger than 'best','guess' becomes 'best'.** This method works perfectly for columns with unique values, and columns* with only twounique values, plus nulls.** It becomes less perfect as the number of unique values increases and* their distributionin the table becomes more random.**/ -- Bruce Momjian | http://www.op.net/~candle maillist@candle.pha.pa.us | (610) 853-3000+ If your life is a hard drive, | 830 Blythe Avenue + Christ can be your backup. | Drexel Hill, Pennsylvania19026
Kristofer Munn <kmunn@munn.com> writes:
> Good catch! There were 296 possible issues the table. One had 86,544
> articles associated with it. The next highest was 5,949. Then the
> numbers drop to 630, 506, 412, 184 and then the rest are all under 62.
> Out of curiosity, how does vacuum decide on the large estimate?
The estimate is made using a "disbursion" statistic calculated by VACUUM
ANALYZE. I don't know the whole statistical theory here, but if you
think of disbursion as the fraction of values in the column that are
equal to the most common value, you won't be too far off.
I gather from your numbers that your table has about 1 million rows,
so the disbursion of ixissue would be somewhere around 86544/1000000.
The planner uses the disbursion in a way that amounts to assuming that
any "WHERE column = constant" search is in fact searching for the most
common value, so we get an estimate of returned rows that is in the
vicinity of the number of rows with the most common value. (It's not
exact, first because VACUUM can't estimate that number perfectly
accurately, and second because the disbursion actually has some second-
order terms in it too.)
When the most common value is much more common than anything else,
this essentially means that queries are always optimized for retrieving
the most common value, even when they're retrieving some other value.
In your particular case, the optimizer is estimating that the runtime
of an index scan that needs to retrieve almost 10% of the rows in the
table will be worse than the runtime of a plain sequential scan. I'm
not sure if that's right or not (the cost models could use more work),
but the first-order mistake is that the estimate of retrieved rows is
way off --- unless you are actually retrieving that one hugely popular
issue.
In current sources (7.0-to-be), VACUUM records the most common value
along with the disbursion, and the planner checks to see if the
"constant" in the WHERE clause is that value or not. If not, it doesn't
use the disbursion straight-up, but a smaller estimate. This helps a
good deal on drastically skewed column distributions such as you are
describing. It's still easily fooled :-(, but it's hard to see how to
do much better without expending a lot more space to store a lot more
statistics.
regards, tom lane