1

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<'y'

But what to do, if both of the condition terms are using inequality? So I am thinking on a WHERE COL_A<'x' AND COL_B<'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?

1
  • 1
    Spatial indexes (R-trees and other types) can be used for such queries. MySQL has R-trees (but can be added for MyISAM tables only.) Postgres has also some other types of indexes that can useful. You are right that simple b-trees will not be very efficient. May 28, 2014 at 23:19

2 Answers 2

2

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

2
  • 1
    Good but it won't be very efficient. May 28, 2014 at 23:18
  • @ypercubeᵀᴹ Yes, this is a very ineffective solution, but this is the most what mysql can offer. :-( Fortunately I managed to avoid to use MySQL in the latest years.
    – peterh
    Mar 30, 2019 at 14:03
0

Spatial indices/R-tree are the way

Just to highlight what ypercube said in the comments, spatial indices such as R-trees are basically exactly what you need for multiple inequalities, they are basically designed for that case.

Spatial indices are somewhat documented at: https://dev.mysql.com/doc/refman/8.0/en/creating-spatial-indexes.html for MySQL, but I don't do MySQL so I won't bother creating an example.

Here I try to explain why composite indices don't cut it for multiple inequalities: https://stackoverflow.com/questions/2256364/what-is-a-spatial-index-and-when-should-i-use-it/76685445#76685445 That answer contains a SQLite example.

And here's a PostgreSQL example I made: https://stackoverflow.com/questions/28292198/how-to-port-simple-spatial-index-using-sqlite-r-trees-to-postgres/76682767#76682767

Related question: Why we can't have more than one inequality condition in MySQL indexing?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.