0

If I have 2 indexed fields(X, Y both doubles) and I have query

SELECT * 
FROM locations LIMIT 10
WHERE x < 25.65434 AND x > 23.54654 
  AND y < 37.67345 AND y > 32.98564

what is the time complexity for this query. If there is just 1 query it would have been O(log(n)) but given that there are 2 fields I could not think of any data structure which can solve in O(log(n)). How do sql databases store the indexes and how do they search if the query is on 2 fields like I mentioned above.

raju
  • 4,788
  • 15
  • 64
  • 119
  • did you look at http://dev.mysql.com/doc/refman/5.7/en/select-speed.html – frankgreco Jul 29 '16 at 17:29
  • 2
    interesting question. but you probably will have to calculate yourself. Create sample data with 10k, 100k and 1000k and check the explain plan. For perfomance question you have to include [QUERY PLAN](http://stackoverflow.com/questions/7359702/how-do-i-obtain-a-query-execution-plan) MySQL index [**TIPS**](http://mysql.rjweb.org/doc.php/index_cookbook_mysql) – Juan Carlos Oropeza Jul 29 '16 at 17:36

1 Answers1

0

SQL Fiddle Demo

Just to give you an idea.

ROWS        |   MATCH     | TIME
1.000.000   |  149 rows   |  3 ms
  100.000   |   15 rows   |  1 ms

   10.000   |    2 rows   |  1 ms
Juan Carlos Oropeza
  • 47,252
  • 12
  • 78
  • 118