Q:

What is the Big-O complexity of a MySQL SELECT statement that uses BETWEEN clause?

I am interested in theoretical Big-O analysis of the following MySQL query:
SELECT id, value FROM MyTable WHERE lat BETWEEN %s AND %s AND lon BETWEEN %s AND %s;

In particular, I would like to know how the BETWEEN clause affects the complexity of this query.

MySQL version is 5.1
MyTable defintion:
CREATE TABLE MyTable (
    id VARCHAR(255) NOT NULL UNIQUE, \
    value DECIMAL(12,9) NOT NULL, \
    lat DECIMAL(9,6), \
    lon DECIMAL(9,6), \
PRIMARY KEY(id(50)), \
INDEX(lat, lon)) ENGINE=InnoDB;

Describe MyTable;
+----------+---------------------+------+-----+---------+-------+
| Field    | Type                | Null | Key | Default | Extra |
+----------+---------------------+------+-----+---------+-------+
| id       | varchar(255)        | NO   | PRI | NULL    |       |
| value    | decimal(12,9)       | NO   |     | NULL    |       |
| lat      | decimal(9,6)        | YES  | MUL | NULL    |       |
| lon      | decimal(9,6)        | YES  |     | NULL    |       |
+----------+---------------------+------+-----+---------+-------+

EXPLAIN EXTENDED SELECT id, value FROM MyTable WHERE lat BETWEEN '40' AND '60' AND lon BETWEEN '-10' AND '10';
+----+-------------+------------+------+---------------+------+---------+------+------+----------+-------------+
| id | select_type | table      | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra       |
+----+-------------+------------+------+---------------+------+---------+------+------+----------+-------------+
|  1 | SIMPLE      | MyTable    | ALL  | lat           | NULL | NULL    | NULL |    7 |    42.86 | Using where |
+----+-------------+------------+------+---------------+------+---------+------+------+----------+-------------+

A:

type = ALL means that this query performs a full scan on the table. key = NULL means that no index is used. In this case it is O(n), where n is the number of rows.
As for BETWEEN, it is the same as performing two compare opearations (>= and <=). If those are executed on indexes (which are B-Trees in MySQL), it is O(log n) in both average and worst cases. Because B-Tree stores values sequentially, such things as range searches are very fast.
As I know for secondary indexes, InnoDB stores primary ID together with secondary index values, so if you do SELECT id FROM MyTable WHERE lat ... AND lon ... (selecting only id), it wouldn't even look inside the actual rows.
Find out more here:

http://dev.mysql.com/doc/refman/5.1/en/explain-output.html
http://dev.mysql.com/doc/refman/5.1/en/mysql-indexes.html

For your case, I recommend you to set some index on lat and lon fields (separately) and experiment which works best for your data. Maybe it is even worth to add extra fields which will contain rouded lat and lon values (as SMALL INTs) to speed up index - in that case you can add multicolumn index on that fields.

