Any way to get 'set explain' explanation?
Just curious, but I was wondering if there was any way
to get some data/info/analysis on WHY informix chooses
some index(es) over another. Or is it black box rocket science?
I did all the update statistics on the tables involved, and the
optimizer still insisted on choosing an inefficient index
(for the query) over a better one.
The query was something like:
select stuff
from claims h, claim_detail d
where h.claim_id=d.claim_id
and h.member_id=?
and d.service_date between ? and ?
For a date range of a month, there might be
a couple hundred thousand claims, but overall,
maybe a couple hundred for any one member.
I ran this with both prepared placeholders and
hardcoded values where the placeholders are,
and it always wanted to use the date index,
and not the member index. So I ended up
doing:
'and d.service_date+0 between ? and ?'
(I know there's index directives now, but this
is less typing :-)
Or maybe there's DBA related tuning that can be done?
Anyway, TIA,
Douglas Wilson
Hi!
Please post version of Informix database and type of engine you are
using,
optimizer was changed quite a few times.
I am assuming IDS, 7.x. Please check the value of OPTCOMPIND in the
onconfig file. Default is 2, change this to 0 and try again.
Please post the results, so everyone can learn from this.
HTH
Michael
Douglas Wilson wrote:
> Just curious, but I was wondering if there was any way
> to get some data/info/analysis on WHY informix chooses
> some index(es) over another. Or is it black box rocket science?
>
> I did all the update statistics on the tables involved, and the
> optimizer still insisted on choosing an inefficient index
> (for the query) over a better one.
>
> The query was something like:
>
> select stuff
> from claims h, claim_detail d
> where h.claim_id=d.claim_id
> and h.member_id=?
> and d.service_date between ? and ?>
> For a date range of a month, there might be
> a couple hundred thousand claims, but overall,
> maybe a couple hundred for any one member.
> I ran this with both prepared placeholders and
> hardcoded values where the placeholders are,
> and it always wanted to use the date index,
> and not the member index. So I ended up
> doing:
> 'and d.service_date+0 between ? and ?'
> (I know there's index directives now, but this
> is less typing :-)
>
> Or maybe there's DBA related tuning that can be done?
>
> Anyway, TIA,
> Douglas Wilson
Hi,
if you want to understand the optimizer rules,
you can use your set-explain output and compare
the output to the real number of rows returned.
If you ommit the Update Statistics High/Medium
statements for the column "service_date", the
optimizer will use the statistics for indexed
columns from "syscolumns." ( colmin and colmax )
as well as the appropriate entry in "sysindexes".
Most of the problems - even if you run Update
Statistics High - occur when you compare a
single column vs. multiple values.
f1 >= 10 and f1 <= 300
Each comparison will be evaluated and the resulting
value is called "Selectivity" or "Filterfactor".
There are two Filterfactors. One for all columns
of a table and one for each column.
Here's an example:
f1 isn't indexed and the where-clause contains the
following expression:
where f1 = 10
The Filterfactor F will be: 1/10 ( default non-indexed columns )
The set-explain-output will show 1/10th of all rows
of the table as the Estimated Number of Rows Returned.
where f1 > 10
The Filterfactor F will be: 1/3
And now your problem!!!
where f1 > 10 AND f1 < 100
The Filterfactors for each expression will be multiplied.
F(f1>10) * F(f1<100)
The result will be 1/9.
You might try the following:
where f1 > 10 and f1 < 11
The Filterfactor will be 1/9 again. The easiest way
to see the problem is by using the following where-
clause.
where f1 = 10 and f1 = 10
The Filterfactor will be:
F(f1=10) * F(f1=10) = 1/10 * 1/10 = 1/100
Now, you have indexed columns and therefore you will
get other Filterfactors for each column. To find
the Filterfactors you can check your set-explain
results.
select 1 from claims where member_id = ?; -- F(one)
select 1 from claim_detail where service_date >= ?; -- F(two)
select 1 from claim_detail where service_date <= ?; -- F(three)
For each of the statements above get the Estimated
Number of Rows Returned and divide this value by the
number of estimated rows in "systables.nrows".
Multiply F(one) by the "systables.nrows" value of "claims";
Multiply F(two)*F(three) by "systables.nrows" value in
"claim_detail";
Then I think you will know, why Informix implemented
the Optimizer Directives.
BTW, where did you learn the trick "+0" ???
Best regards,
Stefan Weideneder
Douglas Wilson wrote:
>
> Just curious, but I was wondering if there was any way
> to get some data/info/analysis on WHY informix chooses
> some index(es) over another. Or is it black box rocket science?
>
> I did all the update statistics on the tables involved, and the
> optimizer still insisted on choosing an inefficient index
> (for the query) over a better one.
>
> The query was something like:
>
> select stuff
> from claims h, claim_detail d
> where h.claim_id=d.claim_id
> and h.member_id=?
> and d.service_date between ? and ?>
> For a date range of a month, there might be
> a couple hundred thousand claims, but overall,
> maybe a couple hundred for any one member.
> I ran this with both prepared placeholders and
> hardcoded values where the placeholders are,
> and it always wanted to use the date index,
> and not the member index. So I ended up
> doing:
> 'and d.service_date+0 between ? and ?'
> (I know there's index directives now, but this
> is less typing :-)
>
> Or maybe there's DBA related tuning that can be done?
>
> Anyway, TIA,
> Douglas Wilson
Douglas Wilson wrote:
> The query was something like:
>
> select stuff
> from claims h, claim_detail d
> where h.claim_id=d.claim_id
> and h.member_id=?
> and d.service_date between ? and ?
Welcome to the wonderful, complex world of query optimization. What
you're looking at is a query where the optimizer is choosing the wrong
access path, but it's doing so for "all the right reasons". I'll try to
explain why in this note, but for anyone who's really interested, I
have appended a set of papers and book references that go a fair way
towards explaining -- at least at a high level -- how commercial query
optimizers work.
1. The task of the optimizer is not really "pick the best plan".
Picking the best plan is a very hard problem and no commercial
optimizers even attempt to do so. Rather, the optimizer picks "the best
plan under reasonably worst case circumstances".
Internally, the query processor decomposes a plan like this into
a set of atomic operations that correspond to the operators in
relational algebra; filter, project, join, etc. These operations are all
"closed", which means that the output of one of them can be used as the
input to another. In certain circumstances they are also "commutative",
which means that you can re-arrange their order without affecting the
correctness of the result. (All of the steps in this plan can be; OUTER
JOINS, ANTI-JOINS, and certain JOINS where more than two tables are
involved cannot ).
The optimizer picks plans based on their "cost", which is
calculated as a function of I/O, record-processing, and in the case of
IDS.2000, function cost. (It might alternatively pick plans based on
"fastest first row", and the difference is significant in a lot of
cases.)
So why is picking the best plan so hard? Well, consider your
query:
i. FILTER < INPUT, "Claims.Member_Id = ?" >
ii. PROJ < INPUT, { Claim.Stuff, Claim.Claim_Id } >
iii. FILTER < INPUT, "Claim_Detail.Service_Date BETWEEN ? AND ?" >
iv. PROJ < INPUT, { Claim_Detail.Stuff, Claim_Detail.Claim_Id } >
v. JOIN < INPUT_1, INPUT_2, "Claim.Claim_Id = Claim_Detail.Claim_Id"
>
Permuting this list of operations, there are 5! or 120 possible
orderings. In addition, there are at least two alternatives for steps i.
and iii. (INDEX_SCAN or SEQ_SCAN), and there are 3 alternatives for step
v. (HASH, MERGE, NEST_LOOP). So for this simple query the optimizer
would be required to evaluate about 800 alternative plans. Computing
this kind of "plan space" is quite computationally expensive.
In the general case, query optimization is "NP-hard" in the number
of "relational operators". In other words, the number of plans to
evaluate grows exponentially with the number of tables plus the number
of expressions in the where clause.
So to reduce the number of plans they need to evaluate, commercial
optimizers employ a battery of "heuristics" (read: guesses). A popular
one is "always do indexed filters before JOINS". The consequence of
using these heuristics is that you may get a non-optimal (but not
generally awful) plan. Intuitively, if there's an index for this filter,
it ought to help.
Anyway, the net-net is that getting SET EXPLAIN to tell you how it
costed alternative plans may not solve your problem: the optimizer might
not even be considering the actual best plan!
2. So, scratching a bit deeper. Here are the two alternative plans:
Plan 1: < i, ii, v, iv, iii > - As it turns out, this is the best
plan. Note that step v. here is an INDEX probe inner on NEST_LOOP.
Plan 2: < i, ii, iii, iv, v > - This is the plan it's choosing.v
is a HASH join, iii. is an INDEX_SCAN.
(Note that in the lowest level operations in each case, the INPUT is
substituted for by the appropriate table name.)
# include <anthropomorphism.h>
The optimizer is by nature a pessimistic creature. It's highly
logical, bit not as smart as a DBA. It looks at the situation, and it
says unto itself;
"Look. If I'm wrong about the number of rows returned in step i (are
there more than a couple of rows per member_id ) I might get really
screwed up in Plan 1. Suppose 1% of the rows in the claim_details table
correspond to each member in the claims table (step v). So if I get 20
rows from the claims table, I'm going to end up index scanning the
claim_details table 20 times in step v, and doing lots of random I/O on
the table heap in the process. This might cause me to have to read pages
multiple times (I know it's all too large to fit in memory).
On the other hand, if I use Plan 2 and index_filter on the date
column's index, and then do a HASH join, I am guaranteed to read each
relevant record off the disk exactly once, and only to read relevant
data. So the 'best plan under reasonably bad assumption' is Plan 2."
OK. So it doesn't really think in this way at all. Rather, its
designed in such a way that it picks a plan that it is pretty sure won't
*really* screw you up.
3. Were you to replace the BETWEEN filter (step iii) with a more
selective predicate (and another poster has pointed out the related
importance of selectivity estimation) then Plan 2 is more likely to be
the right thing to do. For example, consider what happens when you want
to see what claim activity occured for a member on a particular (single)
day. On the other hand, depending on the length of the interval between
the dates you supply, the plan ought to change from Plan 2 to Plan 1, as
when you drop the index, or render it un-usable with the "+0" trick. I
bet if you expanded the range of dates in the query to cover all dates
(MIN and MAX values are kept for date columns) you would find that you
would get Plan 1.
Anyway - the optimizer is making a mistake in this query, for this
particular range of dates.
You might also try the following:
i. Cluster Claim_Detail on Claim_Id. I'm assuming that this is a
pretty insert intensive problem, and that claim processing happens in
sequential bursts. Over time, the quality of the clustering will degrade
but with a sufficiently smart partitioning scheme you ought to be able
to mitigate this.
ii. Drop the Service_Date index (might not be such a great idea,
depending).
Some reading:
Ullman, Jeffrey. "Principles of Database and Knowledge-Base Systems"
Volume II.
Chaudhuri, Surajit. "An Overview of Query Optimization in Relational
Systems". Tutorial in the Proceedings of Principles of Database Systems.
Seattle 1998. [This is available from ACM library, and it has a superb
set of References.]
Selinger, Pat. et al. "Access Path Selection in a Relational
DataBase Management System" SIGMOD 79. [ This is the grand-mother of all
commercial optimization work ]
This might not answer the question, but I hope it helps explain some
things.
KR
Pb