| Oracle FAQ | Your Portal to the Oracle Knowledge Grid | |
 |
 | |||
| Oracle FAQ | Your Portal to the Oracle Knowledge Grid | |
|
| |||
Home -> Community -> Usenet -> c.d.o.server -> Re: sql query (all about indexing)
A copy of this was sent to scott_at_baygate.bayarea.net (Scott Silvey)
(if that email address didn't require changing)
On 5 Apr 1999 20:37:29 GMT, you wrote:
>> You are saying "if (a = b) or ( a = somevalue and b = somevalue )".
>> Cannot use an index for that logic either.
>
>Wouldn't individual indexes on a and b improve evaluation performance of
>this expression considerably? And then if you also did a composite index
>for a and b you would get another significant improvement as well, right?
>
No it wouldn't in most cases, it definitely wouldn't in the case presented by the original post (somevalue in that post what the value NULL which is not stored in the b*tree indexes).
they had the equivalent of:
select * from t1, t2
where ( t1.a = t2.b ) or ( t1.a = x and t2.b = y );
(where x and y are constant).
If the query was just:
select * from t1, t2
where t1.a = t2.b
then an index on either A or B would be useful (assume an index on b for example) as we could then full scan T1 and for each row we find in T1 do an index scan on the index on B to find the rows in T2 that match. In the event an index was missing -- we would have to full scan T1 and for each and every row in T1, full scan T2 (using CBO we might dynamically hash join but thats another story).
If the where clause is
where ( t1.a = t2.b ) or ( t1.a = x and t2.b = y );
there is no single index we would use to do this join.
>Also, how precisely does the engine get an improvement from individual
>indexing on the (a = b) term? Does it, for example, scan all 2M rows
>for different values of b and then do a (very fast) test for (a = bvalue)?
>So that's an O(n) operation, right? Where as (a = bvalue) is an O(1)
>operation.
>
see above, yes you have it.
>So my understanding is that the entire expression above is O(n) if a, b,
>and a&b are indexed. But missing just one of these three indexes would
>suddenly turn the expression into an O(n^2), right? (Or perhaps you
>could get O(n) if one of a or b was indexed and a&b were composite
>indexed?)
>
If the query was rewritten as:
select * from t1, t2 where t1.a = t2.b
UNION ALL
select * from t1, t2 where t1.a = x and t2.b = x
We could in fact use the three indexes.
>Thanks,
>
>Scott
Thomas Kyte
tkyte_at_us.oracle.com
Oracle Service Industries
Reston, VA USA
--
http://govt.us.oracle.com/ -- downloadable utilities
 |
 |