Re: Cost Based Optimizer

>= <1993Oct4.134502.4804@pyra.co.ukgs4> graeme@pyra.co.uk (Graeme Sargent) ab3>= <1993Sep30.132942.498@mnemosyne.cs.du.edu> aburt@mnemosyne.cs.du.edu (Andrew Burt) gs2>= <1993Sep29.170723.19834@pyra.co.uk> graeme@pyra.co.uk (Graeme Sargent) ab1>= <1993Sep28.130906.26091@mnemosyne.cs.du.edu> aburt@mnemosyne.cs.du.edu (Andrew Burt) gs4>[stuff deleted] gs2>IMHO this is going about it the wrong way. What I want to do is tell it gs2>how to access the table, I don't want to have to know or care about gs2>details like selectivity factors (and I suspect I am not alone!!!). ab3>I agree, in principle, that I'd like to just tell it how to do its job. ab3>My concern is that my hint "use an index" may not be sufficient in the ab3>face of complex queries, e.g., "select ... where field1 in (select...)...". ab3>Even if I say to use an index for that, the optimizer would well decide ab3>that since "in" returns "a bunch" of rows, it would be best to scan the *entire* ab3>index ("yes, Mr. Programmer, I used your index, as you asked!") but what I ab3>*want* it to do is look up each value from the 'in' individually. Maybe gs4>I don't understand your concern. The only time OnLine would choose to gs4>do that is for key-only access of all rows, in which case it is the gs4>desirable thing to do! No, it may *not* be the desirable thing. Suppose: 1) table foo has a million rows, say 25 rows/page 2) index on field1 in foo, say 200 keys/page. 3) I write, "select * from foo where field1 in (select field1 from bar where field2 = 42) 4) The "in (select..." returns, say, 100 rows. 5) Now, 100 index lookups on foo ought to cost, say, 4 page reads each, or 400 pages read (or less, assuming most of the upper-tree index pages remain cached). 6) However, the optimizer, seeing this as an 'or' with 100 components, decides to do a sequential scan of the whole table. We pay 40,000 page reads. 7) If it decided to do a sequential scan on the index (rather than the table itself in row order), that's 5,000 page reads. We can't use lower/upper filters because we have 100 "randomly" distributed values to search for. My point is, I'm seeing the #6 behavior (and on a table with more like 10 million records, and where the # rows returned by the 'in' is usually <10). Net effect is that what "ought" to be a blindingly fast search (high end of 40 page reads, though with the cache, I'd guess maybe 25) ends up running for a couple hours reading the whole table. Even telling it "use the index" may not be sufficient -- it my "use" it in the manner of #7, which is still sub-optimal. I want #5 behavior, which is easily conveyed by a selectivity factor to the optimizer (it would make the cost of the 'or' sufficiently low that it would choose to look each up individually). ab3>this whole thing is a carryover from 'or' selectivity being mishandled ab3>somehow (since it seems almost any 'or' will cause a sequential scan). gs4>No, I don't think so. Only those which would need more than one index. Empirically not so -- my problems are on tables with only one index. ab3>Or perhaps informix isn't actually accumulating the set of 'in' data before gs4>No, of course it doesn't actually accumulate them. It estimates how gs4>many "would" be accumulated. It ought to. It doesn't affect the final result, since the subquery must be performed anyway. I can imagine an optimizer rewriting the query such that it wouldn't necessarily do the subquery first, but in my example case it _should_ do it first since it returns so few rows. My suggestion would be: If the subquery has a "low" cost relative to the estimated total cost, do the subquery then recalculate the total cost & change plan if necessary. ab3>it computes the cost? (I mean, if the 'in' data returns 1 or 2, ab3>I'd expect it not to do a sequential scan, yet it does.) gs4>Mine doesn't! It uses the index (if present). What if the subquery returns 10, 100 rows? gs4>[more stuff deleted] ab3>Maybe they need to fine tune "matches" optimization; I don't know how they ab3>do it, but assigning it 0.2 as a constant implies "not well". To wit: Why, ab3>oh why, must informix do a sequential scan when an index exists on the field, ab3>and we have a prefix of the index values ("smith *") -- even if there are a gs4>Why indeed? It doesn't! It may have been something else in the query that caused it. However, I'd wager that select * from foo where field1 matches "smith*" or field1 matches "jones*" or field1 matches "sargent*" or field1 matches "burt*"would cause a sequential scan on foo. The optimizer assumes each returns about 1/5th of all the rows, then the probability of a 4-way 'or' comes out at about 0.6. Even a two way or with matches on both is 0.2+0.2-0.2*0.2 = 0.36 which is likely to cause a sequential scan. [delete] ab3>Here's what I mean: I want this query to be executed like so: ab3> 0) Suppose table foo has 10e6 rows, and indices on both field1 & field2. ab3> 1) Using the index on field1 locate all "blurfl *" rowids; ab3> suppose my estimate is about right and there are about 10 of these. ab3> 2) Look up each of those 10 rows in the main table, and note whether ab3> field2 matches "[a-m]*". gs4>And the problem is that OnLine is presented with a choice of two indexes gs4>to which it assigns equal selectivity estimates. Thus it is pot-luck gs4>whether it chooses the right one (index_on_field1) or not. It will gs4>choose the one which occurs first in sysindexes, so you can "optimise" gs4>this query be ensuring that index_on_field2 was created more recently gs4>than index_on_field1. Exactly! QED! But if I say the selectivity of the blurfl* is really low, and I say the selectivity of the [a-m]* is high, the optimizer knows what to do. gs4>It would be better (IMHO) were it to use index_selectivity_*_matches_factor gs4>in this scenario, and then no hints or other workarounds would usually gs4>be necessary. If you mean using my idea, right. But if you mean some global variable, no, since we need it used _twice_, because the two matches have very different selectivities. ab3>I'm trying to *avoid* in any way doing: ab3> i) a field2-index lookup of all rowids matching [a-m]* (with ab3> the presumed intent of finding the intersection of rowids with ab3> those found from searching index1); and ab3> ii) looking at all rows in the database (ignoring index on field2). gs4>The only way to do it that I know of is to juggle sysindexes. Not good; therefore, something needs to be done. I've merely advanced one possible solution. ab1>[And, oh yes, full regexps would be nice too, egrep --better yet, perl-- style.] ab1>[Or, the ability to call user-defined functions in a query; then one could ab1>put the RE code in as "...and mymatch(field2, "[a-m]*|\\d")..."] gs2>one step at a time would do for me! ab3>But these are orthogonal changes! gs4>H