MySQL Bugs: #32100: contains, intersects functions never return. Query disconnects or times out.

Bug #32100	contains, intersects functions never return. Query disconnects or times out.
Submitted:	5 Nov 2007 10:43	Modified:	22 Nov 2007 17:04
Reporter:	John Powell	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: MyISAM storage engine	Severity:	S4 (Feature request)
Version:	Ver 8.42 Distrib 5.1.20-beta	OS:	Linux
Assigned to:	Alexey Botchkov	CPU Architecture:	Any
Tags:	contains, gis, intersects

Description:
The new contains and intersects functions cause disconnection of the query or the query never completes.
When the number of rows returned is small, in my experience less than 50, and the polygon being used for the intersects or contains call is simple, ie, a rectangle or triangle, the functions appear to work. Above this level, my machine locks up, cpu use goes to 100%, swap space increases by 2gb, and either mysqld dies or the query gets disconnected. I have observed this behavior both on linux, where I built from source, and on the provided windows binary. My config files are properly configured for the machines in question. I have tried this on dedicated mysql servers with 4gb ram available and on a desktop and the same problems occur.

I work on very large real world spatial datasets with geometric objects with many thousands of points. I have attempted to create a procedure below that can be used to create an arbitrary number of geometric objects (circles in this case).

How to repeat:
The following sp allows for the creation of an arbitrary number of geometric objects.

DELIMITER $$

DROP PROCEDURE IF EXISTS `gml`.`testGeom`$$
CREATE DEFINER=`root`@`localhost` PROCEDURE `testGeom`(numGeoms int, circlePoints int)
BEGIN
	declare counter, circlecount int;
	declare g varchar(15000);
	
	declare x, y, width, cx, cy, radians real;
	declare line geometry;
	declare len int;
	set g='';
	
	set cy=0;set cx=0;

	drop table if exists coords;
	create table coords(geom geometry not null, spatial index (geom)); 
	
	set counter=0;
	set circlecount=0;
	set radians=2*PI()/circlePoints;	
	
	while  counter<numGeoms do
		set width=rand()*100;
		set cx=rand()*100;
		set cy=rand()*100;
		
		while circlecount<circlePoints do
			set x=cos(circleCount*radians)*width+cx;
			set y=sin(circleCount*radians)*width+cy;
			set g=concat(x, ' ', y, ', ',g);			
			set circlecount=circlecount+1;		
		end while;
		
		set len=length(g)-2;		
		set g=substring(g,1,len);		
		set g=concat('LINESTRING(',g,')');		
		
		insert into coords values(geomfromtext(g));
		
		set circlecount=0;
		set counter=counter+1;
		set g='';

	end while;
END$$

DELIMITER ;

To test:

mysql> call testGeom(10000,100);

mysql> set @g=geomfromtext('POLYGON((-20 -20, -10 -20, -10 -10, -20 -10, -20 -20))');
mysql> select count(*) from coords where mbrintersects(@g, geom);
+----------+
| count(*) |
+----------+
|     2490 | 
+----------+
1 row in set (0.03 sec)

mysql> select count(*) from coords where intersects(@g, geom);

mysql> show full processlist;
|  6 | root | localhost | gml  | Query   |  433 | Sending data | select count(*) from coords where intersects(@g, geom) | 

After 433 seconds, I gave up.

Suggested fix:
Apologies, but this has taken a lot of time already, and so getting to the bottom of the source code is not something I can do at this time.

John,
thanks for the testcase!

Patch is available from here:
http://mysql.bkbits.net:8080/mysql-5.1-wl1326/?PAGE=gnupatch&REV=1.2573.25.2

This bug is also in 5.1.23-gis. I abort the testcase after 15 minutes on a Intel Dual Core - 2GHz - win32.

In which version is this fixed? 

The Link to the Patch don't work.

Verified as fixed with a recent 5.1 snapshot build:

mysql> DELIMITER $$
mysql>
mysql> DROP PROCEDURE IF EXISTS `gml`.`testGeom`$$
Query OK, 0 rows affected, 1 warning (0.00 sec)

mysql> CREATE DEFINER=`root`@`localhost` PROCEDURE `testGeom`(numGeoms int, circ
lePoints int)
    -> BEGIN
    ->  declare counter, circlecount int;
    ->  declare g varchar(15000);
    ->
    ->  declare x, y, width, cx, cy, radians real;
    ->  declare line geometry;
    ->  declare len int;
    ->  set g='';
    ->
    ->  set cy=0;set cx=0;
    ->
    ->  drop table if exists coords;
    ->  create table coords(geom geometry not null, spatial index (geom));
    ->
    ->  set counter=0;
    ->  set circlecount=0;
    ->  set radians=2*PI()/circlePoints;
    ->
    ->  while  counter<numGeoms do
    ->          set width=rand()*100;
    ->          set cx=rand()*100;
    ->          set cy=rand()*100;
    ->
    ->          while circlecount<circlePoints do
    ->                  set x=cos(circleCount*radians)*width+cx;
    ->                  set y=sin(circleCount*radians)*width+cy;
    ->                  set g=concat(x, ' ', y, ', ',g);

    ->                  set circlecount=circlecount+1;
    ->          end while;
    ->
    ->          set len=length(g)-2;
    ->          set g=substring(g,1,len);
    ->          set g=concat('LINESTRING(',g,')');
    ->
    ->          insert into coords values(geomfromtext(g));
    ->
    ->          set circlecount=0;
    ->          set counter=counter+1;
    ->          set g='';
    ->
    ->  end while;
    -> END$$
Query OK, 0 rows affected (0.05 sec)

mysql> DELIMITER ;
mysql> call testGeom(10000,100);
Query OK, 1 row affected, 1 warning (18.62 sec)

mysql> set @g=geomfromtext('POLYGON((-20 -20, -10 -20, -10 -10, -20 -10, -20 -20
))');
Query OK, 0 rows affected (0.01 sec)

mysql> select count(*) from coords where mbrintersects(@g, geom);
+----------+
| count(*) |
+----------+
|     2424 |
+----------+
1 row in set (0.76 sec)

mysql> select count(*) from coords where intersects(@g, geom);
+----------+
| count(*) |
+----------+
|      653 |
+----------+
1 row in set (0.09 sec)