4

I am building an automated system that has to process several hundred spatial queries in the form of a polygon every day. The queries have to return both spatial and nonspatial data from different database tables. Each table consists of over 500 000 records.

What would be a better approach when performance is a top priority? I) execute a spatial query every time i need (spatial) data? II) first bulk-load all data in-memory into spatial datastructure, and then perform those same spatial queries onto the spatial datastructures?

If the latter is the better approach, which kind of datastructure would be recommended? A few possible datastructures could be: - PR-trees - tries - quadtrees - R-trees Notes: It's safe to assume that there will be no data changes during the processing. The spatial data is 2-dimensional (points, linestrings, polygons)

  • 2
    You need to define this problem more completely. What does "performance is a top priority" mean? Do you have specific requirements for response under certain inputs? How many tables are involved? How many columns in each table? Of what datatypes? How many vertices per geometric feature? Until these things are exposed, discussion of the relative merits of data structures is premature. – Vince Feb 26 '14 at 16:02
  • as for performance: the system would process the requests in batch at night, so it needs to finish its job preferably before users start using system resources. So if the difference between bulkloading everything into a datastructure would mean it can save up some serious processing time, it would be the preferred choice of method. In total about 10 tables are used, each containing over 1000 columns, and over 50 000 records. – user9124 Feb 26 '14 at 18:04
  • Geometric features are usually Points, (Multi)LineStrings, Polygons. LineStrings and Polygons can consist of up to 100 nodes, but are usually not that large. – user9124 Feb 26 '14 at 18:12
  • See also gis.stackexchange.com/questions/85042/… and gis.stackexchange.com/questions/90/…. The spatial DBMS PostGIS will probably more than suffice for your needs -- and there's much expertise on it here. – Martin F Feb 27 '14 at 17:34
  • Thanks. Yes, i've seen these posts as well, but they don't really answer my question in specific: "which is more performant when querying spatial bulkdata repeatedly in a batch"? I guess i'll just have to make a proof of concept myself, benchmark the results, and compare them next to each other. – user9124 Mar 3 '14 at 9:16
1

Not answer but only way to make long comment about test that OP made.

Test data Finnish OSM routing table, 379293 lines (allmoust 400k lines) OP had 300k lines. Test machine was highend desktop i7 + 8G ram , database on normal hardisk, database postgresql 9.2 , non default conf. (Table size 118Mb , Index Size 44Mb. Shared memory 2G)

select count(*) FROM hh_2po_4pgr as h, hh_2po_4pgr as h2 WHERE h.id != h2.id 
AND ST_Intersects(h.geom_way,h2.geom_way)IS TRUE 

= ( i add time later, but it is slow ) (Compares all geoms to another geom in database)

select count(*) FROM hh_2po_4pgr as h, hh_2po_4pgr as h2 WHERE h.id != h2.id 
AND ST_DWithin(h.geom_way, h2.geom_way ,0.0001 )AND ST_Intersects(h.geom_way,h2.geom_way)IS TRUE 

= 2.3 min (ST_DWithin limits Intersected data to 0.0001 degrees (at equator 1.1132 m ) more about decimal degrees

select count(*) FROM hh_2po_4pgr as h, hh_2po_4pgr as h2 WHERE h.id != h2.id 
AND h.geom_way && h2.geom_way AND ST_Intersects(h.geom_way,h2.geom_way)IS TRUE

= 1.9 min h.geom_way && h2.geom_way limits data using intersecting bounding boxes

Conclusion : Your database test probably did not work as you intended, or your hardware is completely different than my or MS SQL is alot slower than postgresql

And yes i know , these test are not comparable. But i have feeling that OP results are not correct.

Answer : my opinion is that prober spatial database with indexes is more than sufficient for job.

  • 1
    You don't need to do the bounding box comparassion manually. It is built into ST_Intersets. – Nicklas Avén Mar 7 '14 at 12:15
  • Yes, I think PostgreSQL is much faster. That is often the case :-) – Nicklas Avén Mar 7 '14 at 12:16
  • First query was a lot slower than those with bounding box or st_DWithin before and after database was warm. Hmm. i have have to check why – simplexio Mar 7 '14 at 12:31
  • 1
    Thanks for the response. I should have mentioned that i did the test on a client/server architecture, which means that the database is shared by other real-time applications, and that network latency affect test results, which is why i have repeated the tests multiple times. What might also affect the results is that in my scenario i queried for data (uids), whereas the other scenario queried for a number using the aggregate function count. I still am convinced that an in-memory solution (0.7s) is still much faster than one using the hard drive (2.3min), especially when data has to travel LAN. – user9124 Mar 8 '14 at 11:32
  • indeed. specially if you logic was like: in client, get geom do spatial search into db, get another geom ... That adds. In my test case everything is in db so no time wasted for moving data. – simplexio Mar 10 '14 at 7:50
0

I have created two testcases using java and one MS SQL server database Table with 366634 rows with two columns: uid (varchar 255), geom (Geometry). The data access layer is implemented using Hibernate Spatial in order to have a bulkloading mechanism.

The first testcase bulkloads the data into an RTree model (JTS) and then performs a search for each geometry that is encountered. So basically every item is searched for in the tree.

The second test testcase also bulkloads all the spatial data in memory first, but then performs a spatial database query for each geometry. So basically every item is searched for in the database using an STIntersects()-function.

Now comes the interesting part: which one is faster? I ran each testcase ten times, and then calculated the average time from the results.

Database-only-approach: The query time for 1000 elements is on average 2.3s. So after extrapolating the results in order to have an approximate idea of how long it takes to do 366634 elements, we come to a result of 14,1min.

Rtree-and-Database-approach: Bulkloading and insertion into the RTree took on average 6.2s. Search time for all the elements is on average 0.7s. So in total: 6.2s + 0.7s = 6.8s.

Conclusion: 6.8s < 14.1min. Using an Rtree is 120 times faster initially! And subsequent searches are 1180 times faster!

ps: the above testdata used (Multi)Lines that were converted to bounding boxes using their internal envelope. I have also used other testdata using Point(x,y)-data, and the results were even more disadvantageous for the Database-only approach. (1146 times slower initially and 9803 subsequently)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.