How to index for multiple inequality WHERE search conditions? I am thinking on the problem, if there is a multiple columns on which search must work as fast as possible.

For example, see the table TEST(COL_A, COL_B) with a (tree) index TEST_IDX(COL_A, COL_B). This index can be used for the following WHERE conditions:


WHERE COL_A='x' AND COL_B='y'
WHERE COL_A='x' AND COL_B&lt;'y'


But what to do, if both of the condition terms are using inequality? So I am thinking on a WHERE COL_A&lt;'x' AND COL_B&lt;'y'? AFAIK, normal record-tree indices in such cases can't work. I can imagine some data structure which could make such queries also fast, but I think it should use a much sophisticated data structure as a simple tree.

Do this in MySQL exist? Or in another SQL servers?
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