Poor Performance when using Spatial Indexes in MySQL

Question

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

Answer 1

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]

Answer 2

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 https://web.archive.org/web/20120618090340/https://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?

Answer 3

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.