Poor performance on Oracle where clause

Question

I have the following Oracle table:

create table my_table(
   start int,
   end int
);

insert into my_table values(1, 3);
insert into my_table values(5, 7);
insert into my_table values(11, 200);
insert into my_table values(311, 5000);
insert into my_table values(60004, 60024);
insert into my_table values(123213, 12312312);

This table has 1M rows and stores number range ('start', 'end'), all numbers are unique, it has no duplicate range and any numbers can only be in one range in this table, I have the following query which passes a variable my_number to identity the 'start' of the range.

 execute immediate 
    'select start from my_table where :1 between start and end' using my_number

I have built combine index on the two fields. the question is when my_number is small, the performance of query is good, but when the my_number is increasing, the query time is increasing continuously. if the my_number is much bigger, it take big considerable time to finish. anybody has way to improve this query? the way can includes re-design my_table. thanks.

Answer 1

Create an index for each column and use this query:

select start_num
from my_table
where
    start_num =
    (
        --Last start <= number
        select start_num
        from
        (
            select start_num
            from my_table
            where :1 >= start_num
            order by start_num desc
        )
        where rownum = 1
    ) and
    end_num =
    (
        --First end >= number
        select end_num
        from
        (
            select end_num
            from my_table
            where :1 <= end_num
            order by end_num
        )
        where rownum = 1
    );

Yuck. There's probably a better way to write this. Or you may want to wrap this in a function.

The problem

Test data (with non-reserved word column names):

drop table my_table;
create table my_table(
   start_num int,
   end_num int
);
insert into my_table select level*2,level*2+1 from dual connect by level <= 1000000;
commit;
create index my_table_index on my_table(start_num, end_num);
begin
    dbms_stats.gather_table_stats(user, 'MY_TABLE', no_invalidate => false);
end;
/

Low numbers are almost instantaneous - 0.015 seconds

select start_num from my_table where 2 between start_num and end_num;

Larger numbers are slower - 0.125 seconds

select start_num from my_table where 1000000 between start_num and end_num;

There's a single point between range scan and full table scan.

explain plan for select start_num from my_table where 402741 between start_num and end_num;
select * from table(dbms_xplan.display);

Plan hash value: 3804444429

------------------------------------------------------------------------------
| Id  | Operation         | Name     | Rows  | Bytes | Cost (%CPU)| Time     |
------------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |          |   160K|  1570K|   622   (2)| 00:00:08 |
|*  1 |  TABLE ACCESS FULL| MY_TABLE |   160K|  1570K|   622   (2)| 00:00:08 |
------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   1 - filter("START_NUM"<=402742 AND "END_NUM">=402742)


explain plan for select start_num from my_table where 402742 between start_num and end_num;
select * from table(dbms_xplan.display);


Plan hash value: 3804444429

------------------------------------------------------------------------------
| Id  | Operation         | Name     | Rows  | Bytes | Cost (%CPU)| Time     |
------------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |          |   160K|  1570K|   622   (2)| 00:00:08 |
|*  1 |  TABLE ACCESS FULL| MY_TABLE |   160K|  1570K|   622   (2)| 00:00:08 |
------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   1 - filter("START_NUM"<=402742 AND "END_NUM">=402742)

But the problem isn't that Oracle doesn't use the index. Using the index in a naive way does not help. In fact, this is even slower, at 0.172 seconds:

select /*+ index(my_table my_table_index) */ start_num
from my_table
where 1000000 between start_num and end_num;

Solution

Create new indexes:

drop index my_table_index;
create index my_table_index1 on my_table(start_num);
create index my_table_index2 on my_table(end_num);
begin
    dbms_stats.gather_table_stats(user, 'MY_TABLE', no_invalidate => false);
end;
/

Results are instantaneous again, for any number:

select start_num
from my_table
where
    start_num =
    (
        --Last start <= number
        select start_num
        from
        (
            select start_num
            from my_table
            where 1000000 >= start_num
            order by start_num desc
        )
        where rownum = 1
    ) and
    end_num =
    (
        --First end >= number
        select end_num
        from
        (
            select end_num
            from my_table
            where 1000000 <= end_num
            order by end_num
        )
        where rownum = 1
    );

The plan looks great - this is probably the best performance you can get.

Plan hash value: 522166032

--------------------------------------------------------------------------------------------------
| Id  | Operation                      | Name            | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT               |                 |     1 |    10 |    10   (0)| 00:00:01 |
|*  1 |  TABLE ACCESS BY INDEX ROWID   | MY_TABLE        |     1 |    10 |     4   (0)| 00:00:01 |
|*  2 |   INDEX RANGE SCAN             | MY_TABLE_INDEX2 |     1 |       |     3   (0)| 00:00:01 |
|*  3 |    COUNT STOPKEY               |                 |       |       |            |          |
|   4 |     VIEW                       |                 |     3 |    39 |     3   (0)| 00:00:01 |
|*  5 |      INDEX RANGE SCAN          | MY_TABLE_INDEX2 |     3 |    18 |     3   (0)| 00:00:01 |
|*  6 |   COUNT STOPKEY                |                 |       |       |            |          |
|   7 |    VIEW                        |                 |     2 |    26 |     3   (0)| 00:00:01 |
|*  8 |     INDEX RANGE SCAN DESCENDING| MY_TABLE_INDEX1 |   500K|  2929K|     3   (0)| 00:00:01 |
--------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   1 - filter("START_NUM"= (SELECT "START_NUM" FROM  (SELECT "START_NUM" "START_NUM" FROM 
              "MY_TABLE" "MY_TABLE" WHERE "START_NUM"<=1000000 ORDER BY "START_NUM" DESC) 
              "from$_subquery$_002" WHERE ROWNUM=1))
   2 - access("END_NUM"= (SELECT "END_NUM" FROM  (SELECT "END_NUM" "END_NUM" FROM 
              "MY_TABLE" "MY_TABLE" WHERE "END_NUM">=1000000 ORDER BY "END_NUM") "from$_subquery$_004" 
              WHERE ROWNUM=1))
   3 - filter(ROWNUM=1)
   5 - access("END_NUM">=1000000)
   6 - filter(ROWNUM=1)
   8 - access("START_NUM"<=1000000)

Answer 2

This is a case of trying to fool Oracle into behaving like its competitors, and without access to Oracle I'm just guessing. Maybe a self-join can do this? With indexes on each column separately,

SELECT t1.start
FROM my_table t1 JOIN my_table t2
ON t1.start=t2.start AND t2."end"=t1."end"
AND t1.start <= :1
AND t2.end >= :1

This is silly looking, but the straightforward solution is Joe Frambach's. It fools Postgres, which I do have, to doing only index searches.

BTW, Postgres is very unhappy about end as a column name. I hope your real table doesn't use a reserved word there.

Answer 3

I think you should make 2 indexes, one on the start column and one on the end column. Then select not with the between option but where greater then start and smaller then end. Then you will use an index for each where clause.

I hope this helps out on performance.

Answer 4

Do you have this done?

create table my_table(
start int,
end int
constraint PK_comp primary key (start, end)
) ;

Answer 5

If you change your schema to this:

create table my_table(
   start int,
   range_size int
);

insert into my_table values(1, 2);
insert into my_table values(5, 2);
insert into my_table values(11, 189);
insert into my_table values(311, 4689);
insert into my_table values(60004, 20);
insert into my_table values(123213, 12300001);

Then you can index only on the start column.

execute immediate 
    'select start from (select start, range_size from my_table where start < :1 order by start asc limit 1) tmp where :1 < start+range_size' using my_number

This may have some performance increase.