Pervasive

Query:
select c1, c2, c3
from t1
where c4 = 'XXXX-XX-XX'
order by c2, c1, c3

The table involved has 3.5M records, there is an index on c4.  If I run the query without the order by clause, the query completes within a minute and the monitor indicate that ~5000 records are read.  If I run the query with the order by clause, the query takes several minutes to complete and the monitor indicates the 3,500,000 records were read.

 It looks to me like the order by clause is ordering the entire table and then applying the where clause rather than using the index on c4 to generate results and ordering just the result.

 Does this make sense to anyone?

To tell for sure, dump out the query plan and load it up in the Query Plan Viewer (W3SQLQPV.EXE). 

If that's the case, the optimizer might be a little off.  You might be able to force it by adding C4 to your ORDER BY clause, like this:

    ORDER BY C4, C2, C1, C3

Or, try hinting, which I believe was added to the v9.5.  The format is WITH (INDEX(C4)).

You may also wish to patch to the latest v9.71 update, in case this issue has already been fixed.

Is there also an index on c2 + c1 + c3 (in that order)?  The optimizer will choose one index for optimizing the query.  It may be choosing the order by index to avoid building a temp sort file, not knowing how many results will be in the query.  In this case, it has to read the entire table along the order-by-index to find the rows matching the restriction.

As Bill said, try the index hint in the from clause, or force the order by to not match the index by adding in the c4, or doing something like:  
     ORDER BY c2+0, c1, c3  (if c2 is a number)

or: ORDER BY c2+'', c1, c3  (if c2 is a string)

 Thanks for the input.

 I dumped out the query plan and it was using an index on C2 (there is not one index containing all of C1, C2, and C3 together).  I tried using an index hint to get it to use the index on C4, but it seemed to ignore it.  Adding C4 to the order by did the trick though; query is returning in a few seconds now.