Re: Cost Based Optimizer

In <1993Sep30.132942.498@mnemosyne.cs.du.edu> aburt@mnemosyne.cs.du.edu (Andrew Burt) writes: >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: [stuff deleted] >>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 I don't understand your concern. The only time OnLine would choose to do that is for key-only access of all rows, in which case it is the desirable thing to do! >this whole thing is a carryover from 'or' selectivity being mishandled >somehow (since it seems almost any 'or' will cause a sequential scan). No, I don't think so. Only those which would need more than one index. >Or perhaps informix isn't actually accumulating the set of 'in' data before No, of course it doesn't actually accumulate them. It estimates how many "would" be accumulated. >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.) Mine doesn't! It uses the index (if present). [more stuff deleted] >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 Why indeed? It doesn't! >"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). No it only does one indexed access, followed by an index scan. What's the point of searching for a non-smith when you're only interested in smiths??? This is called a Lower Index Filter. Try looking at your optimiser plans. >Clearly "*smith*" is going to force a sequential search, but any front-anchored >string should not when that field is indexed. Correct. [yet more stuff deleted] >>>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*. Quite. That's what an index scan is. The only time you'll get to end-of-index is when your upper filter value is > max(column_value(s)) (assuming it's an ascending scan). >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". Informix estimates how many blocks it would have to read and how many comparisons it would have to make in each case, and chooses the access method with the lowest "cost". Hence the term Cost-Based Optimiser. >>... >>>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. Sorry, that's rubbish. I read it as an "OR" condition not an "AND" condition. >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. No they're there. But the current optimiser can only use one index per query plan component (ie one per table access). >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]*". And the problem is that OnLine is presented with a choice of two indexes to which it assigns equal selectivity estimates. Thus it is pot-luck whether it chooses the right one (index_on_field1) or not. It will choose the one which occurs first in sysindexes, so you can "optimise" this query be ensuring that index_on_field2 was created more recently than index_on_field1. It would be better (IMHO) were it to use index_selectivity_*_matches_factor in this scenario, and then no hints or other workarounds would usually be necessary. >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). The only way to do it that I know of is to juggle sysindexes. >>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.@@N