Re: Usage of indexes with greater/lower then operators

In article <7hmomq$39v$1_at_news.netvision.net.il>,   "Maoz Mussel" <maoz_at_mindcti.com> wrote:
> Hi there,
>
> I have the following xxx table:
> id NUMBER
> lowerval NUMBER
> upperval NUMBER
> I have indexes on both fields. When I'm running a query to get rows
that
> falls between
> the lower and the upper values, e.g.:
> SELECT id FROM xxx
> WHERE lowerval <= 1000 AND upperval >= 1000
>
> Only one index is used (and it is the index on the upperval column
from some
> reason).
> If xxx is a big table, indexes will not help much on such case. My
questions
> are:
> - Is this (Oracle use only one index) is a normal behavior ?
> - Any idea for different implementation of such case, e.g., getting
> specific row that
> a value is locate between lower and upper values, still with
reasonable
> performance ?
>
> Thanks for any info,
> Maoz

I have an answer for you, but first a lecture:

Not only is that (using one index per table in a query) normal behavior for Oracle, it's normal behavior for pretty much all databases out there. If you think about it, it makes sense. An index is nothing more than a tree structure you traverse to get to a value. Once you get to the value, you can't really use a second tree - trees are only good for getting from the 'trunk' (starting point) to the leaf (end point) and moving from one leaf to an adjacent leaf. Just because one index gets you to a particular leaf, doesn't mean this will do you any good when using a second index - the tree structure is completely different.

Now for the answer. Just create an index using both columns:

 CREATE INDEX xxx_Both on xxx (lowerval, upperval);

This way, the database will find the first record where lowerval is less than your constraint, then traverse across the index picking values where upperval is greater than the constraint, until it hits an entry where lowerval is greater than the constraint.

I created a test example with this table:  CREATE TABLE fu (l integer, u integer);

 CREATE INDEX fu1 (l);
 CREATE INDEX fu2 (u);
 CREATE INDEX fu3 (l,u);

I then inserted 8192 records in it, where l & u were separted by 500, creating records like (1,500), (2,501)... (8192,8691). The query "SELECT * FROM fu where 787 BETWEEN l AND u; returned the following statistics:

Execution Plan

   0 SELECT STATEMENT Optimizer=CHOOSE    1 0 INDEX (RANGE SCAN) OF 'FU3' (NON-UNIQUE) Statistics

          0  recursive calls
          0  db block gets
         45  consistent gets
         11  physical reads
          0  redo size
      11843  bytes sent via SQL*Net to client
       4333  bytes received via SQL*Net from client
         37  SQL*Net roundtrips to/from client
          1  sorts (memory)
          0  sorts (disk)
        500  rows processed

Notice that the index with both columns is used, and the query was completed with a mere 45 gets. When I dropped fu3, it was forced to use the single-column index:

Execution Plan

   0 SELECT STATEMENT Optimizer=CHOOSE    1 0 TABLE ACCESS (BY INDEX ROWID) OF 'FU'    2 1 INDEX (RANGE SCAN) OF 'FU2' (NON-UNIQUE) Statistics

        111  recursive calls
          1  db block gets
       8034  consistent gets
        134  physical reads
          0  redo size
      11843  bytes sent via SQL*Net to client
       4333  bytes received via SQL*Net from client
         37  SQL*Net roundtrips to/from client
          4  sorts (memory)
          0  sorts (disk)
        500  rows processed

A big difference, with 8034 gets. The example is somewhat biased, since I was searching for a value at the beginning of the index, which allowed use to exit out of the index traversal early, but even if I choose a value towards the end of the table (6787), I get these results:

With fu3: 113 consistent gets
With fu2: 1958 consistent gets

Don't worry much about physical reads. Even though these are the most 'costly', most of the time they are not a function of your query, but of the tuning on your server (cache size) & the access patterns of your data.

You should put the column with the highest cardinality first in these indexes. A column is said to have high cardinality when it has many different values in the table. For example, if lowerval & upperval were dates, maybe there are lots of rows (like half the table) where lowerval is '1 Jan 1999', since this is the day the system went online, whereas the values of upperval are evenly distributed. In this case, it would make sense to write the index as:

 CREATE INDEX xxx_Both on xxx (upperval,lowerval);

The only exception to the rule of "1 index per table" is if you are using bitmap indexes. These are a really cool invention that was introduced in Oracle 7.3. Bitmap indexes are used in tables where the column being indexed has a relatively low cardinality (for example, there are no more than 10,000 distinct values for a column). If this is the case, queries using bitmapped indexes can be insanely fast - anywhere from 10 - 50 times faster. In addition, bitmaps work well with 'OR's and IN clauses, which can be a problem for regular b-tree indexes. Bitmap indexes work well for queries like:

  select (...)
    from fu
   where (a = 6 or b = 9) and c in (3,7,9,12) or d not in (3,2,1);

The downside of bitmap indexes is that you don't want to use them for unique indexes, and that they can be a problem for high-transaction applications, since all inserts tend to lock the same page in all the indexes (the last page), so locking contention increases. I'm not positive, but I'm fairly certain they don't work well with range scanning either, so your problem isn't a candidate for bitmaps.

See <your oracle directory>/doc/database.804/a58227/ch5.htm#5381 for more information.

--== Sent via Deja.com http://www.deja.com/ ==-- ---Share what you know. Learn what you don't.--- Received on Tue May 18 1999 - 18:30:37 CDT