Search operations in non-spatial databases can be optimized using indexes. This is true for spatial databases as well. With the help of a great variety of multi-dimensional indexing methods that have previously been designed, it is possible to optimize spatial searches. The most typical of these are:
-
Point queries that search for all objects that contain a given point
-
Region queries that search for all objects that overlap a given region
MySQL uses R-Trees with quadratic splitting to index spatial columns. A spatial index is built using the MBR of a geometry. For most geometries, the MBR is a minimum rectangle that surrounds the geometries. For a horizontal or a vertical linestring, the MBR is a rectangle degenerated into the linestring. For a point, the MBR is a rectangle degenerated into the point.
It is also possible to create normal indexes on spatial columns.
Beginning with MySQL 5.0.16, you must declare a prefix for any
(non-spatial) index on a spatial column except for
POINT columns.
MySQL can create spatial indexes using syntax similar to that
for creating regular indexes, but extended with the
SPATIAL keyword. Currently, spatial columns
that are indexed must be declared NOT NULL.
The following examples demonstrate how to create spatial
indexes:
-
With
CREATE TABLE:CREATE TABLE geom (g GEOMETRY NOT NULL, SPATIAL INDEX(g));
-
With
ALTER TABLE:ALTER TABLE geom ADD SPATIAL INDEX(g);
-
With
CREATE INDEX:CREATE SPATIAL INDEX sp_index ON geom (g);
For MyISAM tables, SPATIAL
INDEX creates an R-tree index. For other storage
engines that support spatial indexing, SPATIAL
INDEX creates a B-tree index. A B-tree index on
spatial values will be useful for exact-value lookups, but not
for range scans.
To drop spatial indexes, use ALTER TABLE or
DROP INDEX:
-
With
ALTER TABLE:ALTER TABLE geom DROP INDEX g;
-
With
DROP INDEX:DROP INDEX sp_index ON geom;
Example: Suppose that a table geom contains
more than 32,000 geometries, which are stored in the column
g of type GEOMETRY. The
table also has an AUTO_INCREMENT column
fid for storing object ID values.
mysql>DESCRIBE geom;+-------+----------+------+-----+---------+----------------+ | Field | Type | Null | Key | Default | Extra | +-------+----------+------+-----+---------+----------------+ | fid | int(11) | | PRI | NULL | auto_increment | | g | geometry | | | | | +-------+----------+------+-----+---------+----------------+ 2 rows in set (0.00 sec) mysql>SELECT COUNT(*) FROM geom;+----------+ | count(*) | +----------+ | 32376 | +----------+ 1 row in set (0.00 sec)
To add a spatial index on the column g, use
this statement:
mysql> ALTER TABLE geom ADD SPATIAL INDEX(g);
Query OK, 32376 rows affected (4.05 sec)
Records: 32376 Duplicates: 0 Warnings: 0
The optimizer investigates whether available spatial indexes can
be involved in the search for queries that use a function such
as MBRContains() or
MBRWithin() in the WHERE
clause. The following query finds all objects that are in the
given rectangle:
mysql>SET @poly =->'Polygon((30000 15000,31000 15000,31000 16000,30000 16000,30000 15000))';mysql>SELECT fid,AsText(g) FROM geom WHERE->MBRContains(GeomFromText(@poly),g);+-----+---------------------------------------------------------------+ | fid | AsText(g) | +-----+---------------------------------------------------------------+ | 21 | LINESTRING(30350.4 15828.8,30350.6 15845,30333.8 15845,30 ... | | 22 | LINESTRING(30350.6 15871.4,30350.6 15887.8,30334 15887.8, ... | | 23 | LINESTRING(30350.6 15914.2,30350.6 15930.4,30334 15930.4, ... | | 24 | LINESTRING(30290.2 15823,30290.2 15839.4,30273.4 15839.4, ... | | 25 | LINESTRING(30291.4 15866.2,30291.6 15882.4,30274.8 15882. ... | | 26 | LINESTRING(30291.6 15918.2,30291.6 15934.4,30275 15934.4, ... | | 249 | LINESTRING(30337.8 15938.6,30337.8 15946.8,30320.4 15946. ... | | 1 | LINESTRING(30250.4 15129.2,30248.8 15138.4,30238.2 15136. ... | | 2 | LINESTRING(30220.2 15122.8,30217.2 15137.8,30207.6 15136, ... | | 3 | LINESTRING(30179 15114.4,30176.6 15129.4,30167 15128,3016 ... | | 4 | LINESTRING(30155.2 15121.4,30140.4 15118.6,30142 15109,30 ... | | 5 | LINESTRING(30192.4 15085,30177.6 15082.2,30179.2 15072.4, ... | | 6 | LINESTRING(30244 15087,30229 15086.2,30229.4 15076.4,3024 ... | | 7 | LINESTRING(30200.6 15059.4,30185.6 15058.6,30186 15048.8, ... | | 10 | LINESTRING(30179.6 15017.8,30181 15002.8,30190.8 15003.6, ... | | 11 | LINESTRING(30154.2 15000.4,30168.6 15004.8,30166 15014.2, ... | | 13 | LINESTRING(30105 15065.8,30108.4 15050.8,30118 15053,3011 ... | | 154 | LINESTRING(30276.2 15143.8,30261.4 15141,30263 15131.4,30 ... | | 155 | LINESTRING(30269.8 15084,30269.4 15093.4,30258.6 15093,30 ... | | 157 | LINESTRING(30128.2 15011,30113.2 15010.2,30113.6 15000.4, ... | +-----+---------------------------------------------------------------+ 20 rows in set (0.00 sec)
Use EXPLAIN to check the way this query is
executed:
mysql>SET @poly =->'Polygon((30000 15000,31000 15000,31000 16000,30000 16000,30000 15000))';mysql>EXPLAIN SELECT fid,AsText(g) FROM geom WHERE->MBRContains(GeomFromText(@poly),g)\G*************************** 1. row *************************** id: 1 select_type: SIMPLE table: geom type: range possible_keys: g key: g key_len: 32 ref: NULL rows: 50 Extra: Using where 1 row in set (0.00 sec)
Check what would happen without a spatial index:
mysql>SET @poly =->'Polygon((30000 15000,31000 15000,31000 16000,30000 16000,30000 15000))';mysql>EXPLAIN SELECT fid,AsText(g) FROM g IGNORE INDEX (g) WHERE->MBRContains(GeomFromText(@poly),g)\G*************************** 1. row *************************** id: 1 select_type: SIMPLE table: geom type: ALL possible_keys: NULL key: NULL key_len: NULL ref: NULL rows: 32376 Extra: Using where 1 row in set (0.00 sec)
Executing the SELECT statement without the
spatial index yields the same result but causes the execution
time to rise from 0.00 seconds to 0.46 seconds:
mysql>SET @poly =->'Polygon((30000 15000,31000 15000,31000 16000,30000 16000,30000 15000))';mysql>SELECT fid,AsText(g) FROM geom IGNORE INDEX (g) WHERE->MBRContains(GeomFromText(@poly),g);+-----+---------------------------------------------------------------+ | fid | AsText(g) | +-----+---------------------------------------------------------------+ | 1 | LINESTRING(30250.4 15129.2,30248.8 15138.4,30238.2 15136. ... | | 2 | LINESTRING(30220.2 15122.8,30217.2 15137.8,30207.6 15136, ... | | 3 | LINESTRING(30179 15114.4,30176.6 15129.4,30167 15128,3016 ... | | 4 | LINESTRING(30155.2 15121.4,30140.4 15118.6,30142 15109,30 ... | | 5 | LINESTRING(30192.4 15085,30177.6 15082.2,30179.2 15072.4, ... | | 6 | LINESTRING(30244 15087,30229 15086.2,30229.4 15076.4,3024 ... | | 7 | LINESTRING(30200.6 15059.4,30185.6 15058.6,30186 15048.8, ... | | 10 | LINESTRING(30179.6 15017.8,30181 15002.8,30190.8 15003.6, ... | | 11 | LINESTRING(30154.2 15000.4,30168.6 15004.8,30166 15014.2, ... | | 13 | LINESTRING(30105 15065.8,30108.4 15050.8,30118 15053,3011 ... | | 21 | LINESTRING(30350.4 15828.8,30350.6 15845,30333.8 15845,30 ... | | 22 | LINESTRING(30350.6 15871.4,30350.6 15887.8,30334 15887.8, ... | | 23 | LINESTRING(30350.6 15914.2,30350.6 15930.4,30334 15930.4, ... | | 24 | LINESTRING(30290.2 15823,30290.2 15839.4,30273.4 15839.4, ... | | 25 | LINESTRING(30291.4 15866.2,30291.6 15882.4,30274.8 15882. ... | | 26 | LINESTRING(30291.6 15918.2,30291.6 15934.4,30275 15934.4, ... | | 154 | LINESTRING(30276.2 15143.8,30261.4 15141,30263 15131.4,30 ... | | 155 | LINESTRING(30269.8 15084,30269.4 15093.4,30258.6 15093,30 ... | | 157 | LINESTRING(30128.2 15011,30113.2 15010.2,30113.6 15000.4, ... | | 249 | LINESTRING(30337.8 15938.6,30337.8 15946.8,30320.4 15946. ... | +-----+---------------------------------------------------------------+ 20 rows in set (0.46 sec)
In future releases, spatial indexes may also be used for optimizing other functions. See Section 16.5.4, “Functions for Testing Spatial Relations Between Geometric Objects”.