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

i interested in theoretical big-o analysis of following mysql query:

select id, value mytable lat between %s , %s , lon between %s , %s; 

in particular, know how between clause affects complexity of query.

---

mysql version 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 | | +----------+---------------------+------+-----+---------+-------+ | 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 mytable lat between '40' , '60' , lon between '-10' , '10'; +----+-------------+------------+------+---------------+------+---------+------+------+----------+-------------+ | id | select_type | table      | type | possible_keys | key  | key_len | ref  | rows | filtered |       | +----+-------------+------------+------+---------------+------+---------+------+------+----------+-------------+ |  1 | simple      | mytable    |  | lat           | null | null    | null |    7 |    42.86 | using | +----+-------------+------------+------+---------------+------+---------+------+------+----------+-------------+ 

type = all means query performs full scan on table. key = null means no index used. in case o(n), n number of rows.

as between, same performing 2 compare opearations (>= , <=). if executed on indexes (which b-trees in mysql), o(log n) in both average , worst cases. because b-tree stores values sequentially, such things range searches fast.

as know secondary indexes, innodb stores primary id secondary index values, if select id mytable lat ... , lon ... (selecting id), wouldn't inside 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 case, recommend set index on lat , lon fields (separately) , experiment works best data. maybe worth add fields contain rouded lat , lon values (as small ints) speed index - in case can add multicolumn index on fields.