How to index for multiple inequality WHERE search conditions?
Create two separate indexes: idxA(COL_A) and idxB(COL_B).
MySQL will use both indexes and then merge the result. 

http://dev.mysql.com/doc/refman/5.0/en/index-merge-optimization.html

Secion: 8.3.1.4.3 The Index Merge Sort-Union Access Algorithm