Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

Re-post of a question asked on Stack Overflow when it was suggested this would be a better forum.

I'm trying a little experiment at pushing a data set which is not geo-spatial but fits it quite well and am finding the results somewhat unsettling. The data set is genomic data e.g. the Human Genome where we have a region of DNA where elements like genes occupy specific start and stop coordinates (our X axis). We have multiple regions of DNA (chromosomes) which occupy the Y axis. The goal is to bring back all the items which intersect two X coordinates along a single Y coordinate e.g. LineString(START 1, END 2).

The theory seemed sound so I pushed it into an existing MySQL based genome project and came up with a table structure like:

CREATE TABLE `spatial_feature` (
  `spatial_feature_id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `external_id` int(10) unsigned NOT NULL,
  `external_type` int(3) unsigned NOT NULL,
  `location` geometry NOT NULL,
  PRIMARY KEY (`spatial_feature_id`),
  SPATIAL KEY `sf_location_idx` (`location`)
) ENGINE=MyISAM;

external_id represents the identifier of the entity we have encoded into this table & external_type encodes the source of this. Everything looked good and I pushed in some preliminary data (30,000 rows) which seemed to work well. When this increased past the 3 million row mark MySQL refused to use the spatial index and was slower when it was forced to use it (40 seconds vs. 5 seconds using a full table scan). When more data was added the index started to be used but the performance penalty persisted. Forcing the index off brought the query down to 8 seconds. The query I'm using looks like:

select count(*)
from spatial_feature
where MBRIntersects(GeomFromText('LineString(7420023 1, 7420023 1)'), location);

The data going into this is be very dense along the Y dimensions (think of it like you've recorded the position of every building, telephone box, post box and pigeon on a very long road). I've done tests of how R-Indexes behave with this data in Java as well as others in the field have applied them to flat-file formats with success. However no one has applied them to databases AFAIK which is the goal of this test.

Has anyone out there seen a similar behaviour when adding large quantities of data to a spatial model which is not very disparate along a particular axis? The problem persists if I reverse the coordinate usage. I'm running the following setup if that's a cause

  • MacOS 10.6.6
  • MySQL 5.1.46

Help!

share|improve this question
add comment

3 Answers 3

Something must be wrong with your mysql installation or the .ini settings. Just tested a geospatial index on my old mac (10.6.8 / MySQL 5.2). That configuration is similar to yours and I tested the big geodata dump (9 million records). I did this query:

SET @radius = 30;
SET @center = GeomFromText('POINT(51.51359 7.465425)');
SET @r = @radius/69.1;
SET @bbox = CONCAT('POLYGON((', 
  X(@center) - @r, ' ', Y(@center) - @r, ',', 
  X(@center) + @r, ' ', Y(@center) - @r, ',', 
  X(@center) + @r, ' ', Y(@center) + @r, ',', 
  X(@center) - @r, ' ', Y(@center) + @r, ',', 
  X(@center) - @r, ' ', Y(@center) - @r, '))' 
);

SELECT geonameid, SQRT(POW( ABS( X(point) - X(@center)), 2) + POW( ABS(Y(point) - Y(@center)), 2 ))*69.1 
AS distance
FROM TABLENAME AS root
WHERE Intersects( point, GeomFromText(@bbox) ) 
AND SQRT(POW( ABS( X(point) - X(@center)), 2) + POW( ABS(Y(point) - Y(@center)), 2 )) < @r 
ORDER BY distance; 

It took just 0.0336 sec.

I do use the above query e.g. for comparisons between tables where the table where just the lat/lng values for @center come from has a plain INDEX from city_latitude/city_longitude and the 9-12 Mio. table from geonames.org has a geospatial index.

And I just wanted to add that when anybody inserts the big data in a table it might be more performant to add the index after INSERT. If not it will take longer for each row you add ... [but that's not important]

share|improve this answer
    
Wow that's really good. Now I'm not sure what I was doing wrong in my own tests. One thing that might be causing an issue is the nature of my data sets compared to more traditional geospatial data sets. That said I'm just guessing and have no basis for this. It's brilliant to see that you don't need to force the index into memory to get the speed. –  andeyatz Apr 5 '13 at 12:31
    
The WHERE clause with the radius could be filtering out a good portion of the table from using an index. –  tmarthal Jul 29 '13 at 23:05
add comment

MySQL, like PostGIS, stores it’s spatial index data in an R-tree structure so it can find stuff fast. An R-tree, like a B-tree, is organized in such a manner that it is optimized for retrieving only a small fraction of the total data in the table. It is actually faster to ignore the index for queries that need to read a large section of the table to return data or perform a huge join, a classic case which gives rise to many database forum [posters] complaining about a query that returns half their table "not using the new index they just created."

From http://rickonrails.wordpress.com/2009/03/30/big-ole-mysql-spatial-table-optimization-tricks/

If you can fit all of your table data into memory, your performance is good. If/when you need to start doing disk reads, the performance quickly goes bad. Were you doing memory usage patterns of your mysql instance for the two cases: 30k rows vs. 3000k rows?

share|improve this answer
    
I think this could be closer to the issue. TBH its the R-index I want; the other spatial maths is a nice bonus since that would have to be done in the API layer under the old system. I did try a bit of tuning but increasing key buffers did not help (other buffers will not help here like table buffer since its a 1 table query on my personal server). What is odd is that MySQL hammers my machine into the ground when the queries are run (100% during query run). That said its doing a full table scan so maybe it isn't that strange –  andeyatz Feb 1 '11 at 11:53
add comment

Have you thought about breaking it up into two 1D columns instead of a single 2D column?

The optimizer could be choking on all the similar data and having two columns with greater variety might help.

What you might also check is the order in which items are checked. I had a problem in Oracle Spatial where I was search on Last Name and an IN_REGION filter. Oracle decided the fastest way was to use the last name and then do a region check. Let me tell you, doing an in region check on all the Robinson's in Cleveland is slow. I remember I had to pass an Oracle specific argument to force it to use the spatial index first.

share|improve this answer
    
Unfortunately 1 dimension is vastly less populated than another dimension. To put this into context the human genome has 24 unique chromosomes (22 pairs and the two sex chromosomes) along with a bags of data which has been assembled to different levels. Which means if you map elements to the basic use case that is only 24 unique identifiers in one dimension. The original hope was that the R-tree index would have been able to perform not only more performant overlapping range checks but also differentiate between these regions in a single query. –  andeyatz Feb 1 '11 at 11:48
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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