I have a table with 1 million records and I am trying to use following query:

select count(*) from TABLE where col1 = 'value' and col2 = 'flag'
and col3 =11 and col4 in ('A','B')

col1 is non-unique with three distinct values.
col2 is a flag with two values.
col3 is again non-uinque with 2 lacs records with 11 as value.
and col4 is again non-unique with 6 distinct values.

I am using sybase 12.0 on HP-UX

I have indexes on col1 named idx1, composite indexes on col2 and col3 as idx2.

Its using idx1 (from showplan o/p) and with MRU replacement strategy and I/O size of 2KB for both index as well data pages.

This query is taking more than 5 minutes to execute.

Now I am trying to execute the same query on a different server with same config. but sybase version here is 11.9.2
and TABLE is having around 0.7 million rows.Schema is same as on first server with same indexes.
Here I am able to execute the same query in less than 10 secs and
in showplan o/p the only difference i saw is that it is using LRU replacement strategy.

My first purpose is to reduce the execution time for first server.

Secondly I want to know why there is such a diff betwn execution time?

What things I can start with for server1 from performance point of view....(may be some config parameters etc.)