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?

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .