Have you confirmed that Oracle is not using an index -- I would guess that it might be performing a fast full index scan.

A few things occur to me.

Have you benchmarked something like ...
Code:
Select digits
from
(
select digits
from routestepent
where digits in
   (
   substr(‘6022241234',1,1),
   substr(‘6022241234',1,2),
   substr(‘6022241234',1,3),
   substr(‘6022241234',1,4),
   ..
   etc
   )
   order by length(digits) desc
)
where rownum =1
/
You'd only need to go up to your longest digit string, of course.

Another approach:
  • What is the distribution of lengths for the 'digits' column?
  • Is it possible to work out the probability of a match at a given length of digits?
  • Can you then use that information to say something like "30% of the dialled numbers get a match on a digit length of 6"?
  • Now if that were so can you query for a match at that length where there are no matches at a longer length?

Code:
select digits
from routestepent
WHERE 'DEFAULT' = tblnm AND
     substr(‘6022241234',1,6) = digits and
     not exists (select 1 from routestepent
WHERE 'DEFAULT' = tblnm and digits like substr(‘6022241234',1,7)||'%'
   )
In other words, can you leverage your own knowledge to try and get a quick hit on the most common one or two cases?

You might be able to optimize that last example by placing a (technically redundant) code in the table to indicate whether there are longer matches available, say a "terminal_string" code ... so in the examples you give, '4', '44', '4424' would have a terminal_string of 'N' and '442467' would have a terminal_string of 'Y', hence the code would become:

Code:
select digits
from routestepent
WHERE 'DEFAULT' = tblnm AND
     substr(‘6022241234',1,6) = digits and
     (terminal_string = 'Y' or
     (terminal_string = 'N' and 
     not exists (select 1 from routestepent
WHERE 'DEFAULT' = tblnm and digits like substr(‘6022241234',1,7)||'%'
   )))
(I think i got the right number of parens on that)

Lastly, would it be possible once a match has been found to log that for future use against the dialed number in an index-organized lookup table? How often does this routing table change?

How many tblnm's are there? Maybe instead of indexing on tblnm you could list-partition your table on tblnm and use local indexes to reduce the index size to be scanned. A poor man's alternative would be to use multiple oracle tables for each tblnm, then use your application code to execute a query to the appropriate table.

By the way, you're using bind variables here, right?