Re: Cost Based Optimizer
In <1993Sep29.170723.19834@pyra.co.uk> graeme@pyra.co.uk (Graeme Sargent) writes:
>In <1993Sep28.130906.26091@mnemosyne.cs.du.edu> aburt@mnemosyne.cs.du.edu (Andrew Burt) writes:
>>In <1993Sep28.104721.9014@pyra.co.uk> graeme@pyra.co.uk (Graeme Sargent) writes:
>>>In <1993Sep27.185056.23855@mnemosyne.cs.du.edu> aburt@mnemosyne.cs.du.edu (Andrew Burt) writes:
>>>>In <1993Sep27.130957.8224@pyra.co.uk> graeme@pyra.co.uk (Graeme Sargent) writes:
>>>>>This is to be expected. OnLine uses a Selectivity Factor of
>>>>>1/sysindexes.nunique for an indexed_col = <literal> filter and a
>>>>>Selectivity Factor of 0.2 for a matches expression.
>>>>I'd be happy to be allowed to write,
>>>> select * from foo where bar matches "blurfl*" selectivity 1/100000 ...
>>>>Or even being able to tell it the estimated #rows directly (or better yet,>>>>allow either).
>>>But this is clumsy! How are you going to know the selectivity in
>>>advance? And what is going to maintain it as it changes?
>>Er, right, and a constant selectivity factor of 0.2 for "matches" changes?
>>I'd like to at least give it a hint that this match is pretty selective,
>>1 in 10^5 rather than 1 in 5.
>IMHO this is going about it the wrong way. What I want to do is tell it
>how to access the table, I don't want to have to know or care about
>details like selectivity factors (and I suspect I am not alone!!!).
I agree, in principle, that I'd like to just tell it how to do its job.
My concern is that my hint "use an index" may not be sufficient in the
face of complex queries, e.g., "select ... where field1 in (select...)...".
Even if I say to use an index for that, the optimizer would well decide
that since "in" returns "a bunch" of rows, it would be best to scan the *entire*
index ("yes, Mr. Programmer, I used your index, as you asked!") but what I
*want* it to do is look up each value from the 'in' individually. Maybe
this whole thing is a carryover from 'or' selectivity being mishandled
somehow (since it seems almost any 'or' will cause a sequential scan).
Or perhaps informix isn't actually accumulating the set of 'in' data before
it computes the cost? (I mean, if the 'in' data returns 1 or 2,
I'd expect it not to do a sequential scan, yet it does.)
>>As for how would I know the hint: (a) sometimes you just do, based on how
>But is "sometimes" good enough?
It is when you find yourself in one of those situations! The rest of the
time you have my (b) option of fiddling it via variable.
>>users enter data; e.g., if you "highly suspect" users enter "lastname *"
>>then it'd be a _much_ better guess to assume 1/10^5 than 1/5 (at least
>>knowing my data). Sure, if they do "S*", but, ah, I doubt they'll _really_
>>want to look at all two million names starting with S. And (b) if it's a
>>variable, I could twiddle it dynamically, after looking at counts, etc.
>I hadn't thought of that admittedly. Nor would Informix were they to
>implement this suggestion, I'd wager.
They've heard it now, I hope.
Maybe they need to fine tune "matches" optimization; I don't know how they
do it, but assigning it 0.2 as a constant implies "not well". To wit: Why,
oh why, must informix do a sequential scan when an index exists on the field,
and we have a prefix of the index values ("smith *") -- even if there are a
"lot" of "smith *" matches, it should use the index to locate the first of them
to do the sequential scan (search for any "smith" in the index, reverse seq.
search for the first non-smith, bing! the first smith; now follow the index
sequentially from there until done).
Clearly "*smith*" is going to force a sequential search, but any front-anchored
string should not when that field is indexed.
>>Chances are the _only_ time it'd be needed by anyone is when they've
>>proven that the optimizer doesn't optimize their particular case, in
>>which case even an order of magnitude or two guess is fine. (1/10^3 would
>>still be far better than 0.2 and would no doubt cause selecting the
>>index.)
>But you're still not seeing the forest for the trees (IMHO).
>...
>>I'm not familiar with oracle. If by this you're implying it _forces_
>>the optimizer to use the index to do individual lookups, rather than a
>>sequential search on the index, that's fine. But if the optimizer says
>>"of _course_ I'll use the index -- to do my sequential scan, I'll just
>>scan the index" -- bzzzzt!
>I don't follow you. Yes, this should force the optimiser to use the
>index (assuming it exists, of course, but non-existence should not
>generate an error, just leave the optimiser to it's own devices again).
>And yes it would scan the index, I don't see what's wrong with that. In
>my book, even if it's unique it's still a scan, just a very short one!
No, I meant an O(N) sequential scan of the index, not an O(log_k_ N) search.
I.e., a sequential scan can be done on the data itself (ignoring the
index) or on the index (read all the index pages from 1st to last). I
want to force it to do an O(log_k_ N) search for each item in my list
rather than an O(N) scan of *anything*.
Nor need it be "very short" -- the index itself has as many unique tuples
as the table it indexes, so a million row table may have a million row
index. It still takes a long time to scan that million rows; my point is
that sometimes M individual O(log_k_ N) lookups will be faster than one
O(N) scan. Indeed, set them equal to find M. Does informix do this?
I guess "no".
>...
>>clause in a query is performed first, as this "no doubt" would do:
>> select * from foo where field1 matches "blufl *" selectivity 1/100000
>> and field2 matches "[a-m]*" selectivity 1/2>>thus forcing the first 'matches' to be performed before the second, etc.
>Not sure what you're getting at here. With Informix' current
>restriction of one index per table, a full table scan will give best
>throughput on this query.
No! No! No! Er, wait, "one index per table", umm, you mean those tables I
have with five indices aren't really there? I don't follow you.
Here's what I mean: I want this query to be executed like so:
0) Suppose table foo has 10e6 rows, and indices on both field1 & field2.
1) Using the index on field1 locate all "blurfl *" rowids;
suppose my estimate is about right and there are about 10 of these.
2) Look up each of those 10 rows in the main table, and note whether
field2 matches "[a-m]*".
I'm trying to *avoid* in any way doing:
i) a field2-index lookup of all rowids matching [a-m]* (with
the presumed intent of finding the intersection of rowids with
those found from searching index1); and
ii) looking at all rows in the database (ignoring index on field2).
>If you're assuming that restriction has been lifted then:
> --+ FIRST_ROWS INDEX(foo idx1 idx2)
>should do the trick and IMHO is a lot more readable/maintainable.
I'm not clear what Oracle's "first_rows" means...?
>>[And, oh yes, f