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:

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.


Comments

Post a Comment

Popular posts from this blog

django - How can I change user group without delete record -

-
on website user have 1 group. , user can change group. it's made user.groups.clear() and user.groups.add(new_group) but it's not efficient, because there 2 sql query: delete, insert. how can change group update query? user , group related each other using manytomanyfield . means intersection table exists relating both entities, , if don't specify model map (using through attribute) django creates 1 you. looking @ sources django.contrib.auth.models see that's case. fortunatly, can access intermediary model using through attribute of manager (in case, user.groups.through ). can use regular model. example: >>> alice = user.objects.create_user('alice', 'alice@example.com', 'alicepw') >>> employee = group.objects.create(name='employee') >>> manager = group.objects.create(name='manager') >>> alice.groups.add(employee) >>> alice.groups.all() [<group: employee...
Read more

java - Need to add SOAP security token -

-
i need set custom soap header attribute on jax-ws generated webservice client. case webservice calls must go through proxy server requiring specific token (recieved web request header) present in soap request header. e.g.: 1 carserviceservice service = null; 2 service = new carserviceservice(new url(url), new qname(qname); 3 carserviceendpoint port = service.getcarserviceport(); it seems in line 3 wsdl retrieved , call fails due missing security token. 1 point direction on how done? a detailed example has been mentioned here: creating , deploying jax-ws web service on tomcat 6 this article shows how create , use security token .
Read more

java - EclipseLink JPA Object is not a known entity type -

-
i have strange problem eclipselink , object want persist. have 1 object (keypointlistimpl) stores object keypointimpl in list. persisting keypointimpl objects works great if try persist keypointlistimpl object java.lang.illegalargumentexception says object keypointimpl isn't known entity type. here keypointimpl code: @entity @table(name="keypoints") public class keypointimpl implements keypoint { @id @generatedvalue(strategy = generationtype.identity) private int id; @enumerated(enumtype.string) private detectortype keypointtype; private float x; private float y; private float size; private float angle; private float response; private int octave; private int classid; ... } here keypointlistimpl code: @entity @table(name="keypointlists") public class keypointlistimpl implements keypointlist { @id @generatedvalue(strategy = generationtype.identity) private int id; @onetoone(cascade={ca...
Read more