在MySQL空间索引中进行连接

Question

我有两张表：一张包含点，另一张包含多边形。

CREATE TABLE `points` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `point` point NOT NULL,
  PRIMARY KEY (`id`)
) ENGINE=MyISAM;

CREATE TABLE `ranges` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `poly` polygon NOT NULL,
  PRIMARY KEY (`id`),
  SPATIAL KEY `poly` (`poly`)
) ENGINE=MyISAM;

我想将范围连接到多边形内部的点上。查询看起来很简单：

SELECT * 
  FROM points 
    LEFT JOIN ranges 
      ON MBRCONTAINS(poly, point) 
  WHERE points.id = 2;

这个查询非常快且使用索引，部分的执行计划如下：

table  | type  | possible_keys | key  | key_len
ranges | range | poly          | poly | 34

但是，当我尝试与表格points中的多行进行连接时：

SELECT * 
  FROM points 
   LEFT JOIN ranges 
    ON MBRCONTAINS(poly, point) 
  WHERE points.id IN (1,2,3);

一切都崩溃了：

+----+-------------+------------+-------+---------------+---------+---------+------+--------+-------------+
| id | select_type | table      | type  | possible_keys | key     | key_len | ref  | rows   | Extra       |
+----+-------------+------------+-------+---------------+---------+---------+------+--------+-------------+
|  1 | SIMPLE      | points     | range | PRIMARY       | PRIMARY | 4       | NULL |      3 | Using where |
|  1 | SIMPLE      | ranges     | ALL   | poly          | NULL    | NULL    | NULL | 155183 |             |
+----+-------------+------------+-------+---------------+---------+---------+------+--------+-------------+

添加 FORCE INDEX (poly) 没有起到帮助作用。

用于测试查询的样本数据（抱歉，只提供php版本，我不熟悉SQL程序）：

//points
for($i=0;$i<=500;$i++) {
    $point = mt_rand();
    mysql_query('INSERT INTO points (point) VALUES (POINTFROMWKB(POINT('.$point.', 0)))');
}

$qty = 20000;
$max = mt_getrandmax();
$add = $max / $qty
$end = 0;

//polys
while($end < $max) {
    $start = $end;
    $end = mt_rand($start, $start + $add);
    mysql_query('INSERT INTO ranges (poly) VALUES (
        GEOMFROMWKB(POLYGON(LINESTRING(
            POINT('.$start.', -1),
            POINT('.$end.',   -1),
            POINT('.$end.',    1),
            POINT('.$start.',  1),
            POINT('.$start.', -1)
          )))
    )');
}

- Oroboros102

---

http://dba.stackexchange.com/ - Laurynas Biveinis

你能解释一下“一切都崩溃”的意思吗？错误信息很难读懂吗？ - Micromega

您能否提供这些表的插入示例？您尝试过重写那个IN条件来使用连接吗？ - Pentium10

@David “一切都崩溃了”- 查询未使用索引。 - Oroboros102

在这个例子中，你的多边形似乎都是正方形... 这种情况会一直存在吗？或者你还会处理其他可能不标准的多边形形状（例如：规则的五边形、不规则的简单房屋形状、凹形的像蝴蝶结一样、复杂的星形轮廓）等等。 - DRapp

Answer 1

我认为这是因为MySQL不支持合并空间索引。不确定这是否仍然正确，但我曾经在某个地方读到过。如果有一个OR语句，则不使用空间索引

在您的情况下，当您执行points.id = 1时，这是一个直接查询，返回一个结果，并用于mbrcontains。这将使用索引。

当您添加points.in（1,2,3）时，这会返回3个结果，并且每个结果都需要映射到ranges表，因此无法工作

结果

id  select_type     table   type    possible_keys   key     key_len     ref     rows    filtered    Extra
1   SIMPLE  points  range   PRIMARY     PRIMARY     4   NULL    3   100.00  Using where
1   SIMPLE  ranges  ALL     poly    NULL    NULL    NULL    6467418     100.00   

您可以通过这种方式简化测试，而不需要点表格：SELECT * FROM 范围 WHERE mbrcontains(多边形, GEOMFROMWKB(POINT(0, 0)))

id  select_type     table   type    possible_keys   key     key_len     ref     rows    filtered    Extra
1   SIMPLE  ranges  range   poly    poly    34  NULL    1   100.00  Using where

现在是这样的; SELECT * FROM ranges WHERE mbrcontains(poly, GEOMFROMWKB(POINT(0,0))) OR mbrcontains(poly, GEOMFROMWKB(POINT(10,10)))

结果

id  select_type     table   type    possible_keys   key     key_len     ref     rows    filtered    Extra
1   SIMPLE  ranges  ALL     poly    NULL    NULL    NULL    6467418     100.00  Using where

请注意在第二种情况下，您没有使用索引而只是进行了扫描。

您可以通过为每个特定点创建 UNION 强制查询使用索引，但我不确定是否会更快。我在本地进行了一些测试，结果比您的第一个查询略慢。

EXPLAIN EXTENDED 
SELECT *
FROM points
FORCE INDEX (PRIMARY )
LEFT JOIN ranges
FORCE INDEX ( poly ) ON mbrcontains( poly, point )
WHERE points.id = 1
UNION DISTINCT
SELECT *
FROM points
FORCE INDEX (PRIMARY )
LEFT JOIN ranges
FORCE INDEX ( poly ) ON mbrcontains( poly, point )
WHERE points.id = 2
UNION DISTINCT
SELECT *
FROM points
FORCE INDEX (PRIMARY )
LEFT JOIN ranges
FORCE INDEX ( poly ) ON mbrcontains( poly, point )
WHERE points.id = 3

结果

id  select_type     table   type    possible_keys   key     key_len     ref     rows    filtered    Extra
1   PRIMARY     points  const   PRIMARY     PRIMARY     4   const   1   100.00   
1   PRIMARY     ranges  range   poly    poly    34  NULL    1   100.00  Using where
2   UNION   points  const   PRIMARY     PRIMARY     4   const   1   100.00   
2   UNION   ranges  range   poly    poly    34  NULL    1   100.00  Using where
3   UNION   points  const   PRIMARY     PRIMARY     4   const   1   100.00   
3   UNION   ranges  range   poly    poly    34  NULL    1   100.00  Using where
NULL    UNION RESULT    <union1,2,3>    ALL     NULL    NULL    NULL    NULL    NULL    NULL     

- Alexey Gerasimov

---

@oroboros102，如果您需要的话，这是参考链接：http://dev.mysql.com/doc/refman/5.0/en/range-optimization.html。请看7.3.1.3.1中的最后一段。 - Alexey Gerasimov

Answer 2

我曾成功使用类似的查询，唯一不同之处在于数据模型上点数据库有一个空间键。在我的情况下：

CREATE TABLE geopoints (
  pid int(11) NOT NULL AUTO_INCREMENT,
  description varchar(255) NOT NULL DEFAULT '',
  geopoint point NOT NULL,
  PRIMARY KEY (pid),
  SPATIAL KEY geopoint (geopoint) 
) ENGINE=MyISAM DEFAULT CHARSET=utf8;

在像这样的查询中，一切都进行得很顺利：

SELECT pt.pid, x(geopoint), Y(geopoint), pl.pid, AsText(geopolygon) 
  FROM geopoints pt INNER JOIN geopolygons pl ON MBRCONTAINS(geopolygon, geopoint)
 WHERE pt.pid IN (1,2,4,5) AND pl.pid BETWEEN 1 AND 5;

我的见解：

- Athanassios Stavrakoudis

Answer 3

如果你所处理的都是正方形，我会在你的表格中仅处理可索引的4个数字，分别代表顶部、左侧、高度、宽度，然后运行查询，在这个问题点的“X”坐标在Left和Left+Width之间，“Y”坐标在Top和Top+Height之间。

- DRapp

---

但我使用几何，因为它比“BETWEEN”快得多。 - Oroboros102

实际上，MySQL 无法在 BETWEEN 上进行连接。因此，我想到了利用空间索引进行这样的连接。但是，仍然没有成功。 - Oroboros102

Answer 4

你可以通过将子查询封装在函数中来强制 MySQL 使用索引。

例如：

DELIMITER $$

DROP FUNCTION IF EXISTS `GetMyPolygon`$$
CREATE DEFINER=`root`@`localhost` FUNCTION `GetMyPolygon`(p POINT) RETURNS INTEGER
BEGIN

DECLARE ret INTEGER;

SET ret = (SELECT range_id FROM ranges WHERE ST_CONTAINS(poly, p) ;

RETURN ret;

END$$

如果多边形不重叠，那么你可以进行如下操作：

SELECT *, GetMyPolygon(point) FROM points 

如果它们有重叠，但只有几个，您可以编写一个类似的函数来执行group_concat...

- Pablo