database: nearest point query

years back, my team deployed a web service that gives location description, given a point. since we have a large number of points (about 600k) we decided to segregate areas in polygons and assign a point per polygon. that dropped the number of points (to about 200k) and made a faster query.

early this year, my team deployed a web service that translates requests and responses of another service to a different format. i was surprised when i learned that this service is processing transactions 100 times more than the first service at a much lower processing load.

well, of course they have different processes, but that made me want to improve the first service. with much reading, i drafted a design that makes subsets of the main data set and uses a look-up for mapping. this will mean having two queries, instead of one. but it'll have much quicker queries at that.

then i got to read somewhere that it's similar to what spatial database functions do. so i checked if spatial queries are really faster than my normal distance queries. guessed right, they are.

spatial database is an easy solution for faster nearest point queries! now i have to plan a harder implementation which involves upgrading my database servers. hahaha sheesh

mysql: spatial function

a few months back, i tried using mysql spatial functions

* tables with spatial columns have to be myisam
mysql> alter table lookup engine=myisam;

i created a column to contain spatial values of points:
mysql> alter table lookup add loc point not null
mysql> update lookup set loc = POINT(x, y);
mysql> create spatial index idx_loc on lookup(loc);

i created a column to contain mbr of polygons:
mysql> alter table lookup add mbr polygon not null;
mysql> update lookup set mbr = envelope(geomfromtext(concat('LINESTRING(',minx,' ',miny,',',maxx,' ',maxy,')')));
mysql> create spatial index idx_mbr on lookup(mbr);

i created a column to contain perimiter of polygons:

mysql> alter table lookup add perimiter polygon not null; mysql> update table lookup set perimeter =  geomfromtext(concat("polygon((",area,"))"));
mysql> create spatial index idx_perimiter on lookup(perimiter);

queries to search if a point is inside an area:
mysql> select name from lookup where contains(mbr,geomfromtext('point(121.08440300 14.55762000)'));
# 14 rows in set (0.16 sec)

mysql> select name from lookup where within(geomfromtext('point(121.08440300 14.55762000)'),mbr);
14 rows in set (0.02 sec)

mysql> select brgy from brgy where within(geomfromtext('point(121.08440300 14.55762000)'),perimeter);
# 2 rows in set (0.00 sec)

queries to search nearest polygon given a point:
mysql> select name, sqrt(pow(abs(x(loc)-125.08955),2)+pow(abs(y(loc)-7.00048),2)) as dist from lookup where contains(Buffer(geomfromtext('point(125.08955 7.00048)'), .05), loc) having dist < .05 order by dist limit 1;
# 1 row in set (0.01 sec)

** next improvement would be to check perimeter nearest to point since centroids are based on the dimension/shape of polygon