Search architecture for moving geotagged objects
I currently have a Postgres DB populated with approx. 300,000 sets of moving vehicles around the world. My very recurring request: Give me all vehicles within a 5/10/20 mile radius. I am currently spending 600 to 1200ms in the DB to prepare a set of disposed vehicle objects.
I want to significantly improve this time, if possible, by one or two orders of magnitude. I am working in Ruby on Rails 3.0beta environment, if that matters.
Any ideas on how to architect the whole system to speed up this request? Any NoSQL database capable of providing this kind of geolocation performance? I know MongoDB is working on an extension to make this scenario easier, but haven't tried it yet. Any reasonable use of Redis to achieve this?
One of the problems with SQL-DB here seems to be that I can't use indexes because my vehicles are mostly moving around, meaning I had to constantly create DB indexes, which in themselves are probably more expensive than just search without index.
We look forward to yours, thank you!
a source to share
If you use the right algorithm to organize your data, you can use a spatial index , which can speed up your queries significantly.
Best practice for a geolocation domain is to use a geohash , quad-tree , R-tree or similar data structure (R-trees are the most versatile, but it looks like you are querying point data, so it might not matter). In each case, you can create a spatial index that uses a single, linear column, where each value is a bounding box of a different size and shape. This will allow you to answer most queries with a single range query on your database. Spatial indexes can be implemented in SQL ( PostGIS , MS SQL , MySQLall have spatial data types and spatial indexes that use one of these methods) or NoSQL (popular for its horizontal scalability, AppEngine has geomodel , SimpleGeo uses Cassandra , Foursquare uses MongoDB ).
Index usage can be difficult with constant moving points, but I suspect that records, even slightly heavier ones, write that update indexes won't be your bottleneck.
a source to share
Despite the fact that your vehicles are constantly moving, I assume that they have a certain speed limit. What you can do is create some kind of discrete coordinate system, one example would be the integer part of the lat / long coordinate. You then put those values in separate columns, keeping the exact location in the other column. You will then be able to index entire columns, since the vehicles will not move so much that they change these values very often.
When doing a search, you first find out which "squares" are interesting and limit your query to vesicles within those quests using indexed columns. Then you need to do a full search for all vehicles in each square. The number of vehicles you have to do a full search should now represent only a small fraction of all milestones. The effectiveness of this strategy, of course, depends on the distribution of your vechiles. If 50% of them are in a specific city then this will not work, but assuming that the largest group of vehicles in one location is 5-10% this should improve performance.
a source to share